| مدرس | ایمیل |
|---|---|
| محمدهادی فروغمند اعرابی | foroughmand@sharif.ir |
برنامه‌ریزی ریاضی به صورت کلی به حل مسئله‌های بهینه‌سازی با استفاده از مدل‌سازی آن به صورت زیر می‌پردازد:
| f(x) | بهینه کن |
| برخی قیود روی x | با شرط |
| x ∊ Rm |
یک حالت خاص از برنامه‌ریزی ریاضی، برنامه‌ریزی خطی است که در آن تابع هدف و خطی است و مجموعه قیدها بر روی متغیرها از تعدادی نیم‌فضا تشکیل شده است. برنامه‌ریزی خطی کاربردهای فراوانی مخصوصا در حل مسئله‌های الگوریتمی دارد، زیرا از طرفی تبدیل کردن یک مسئله الگورتیمی به یک برنامه‌ریزی خطی معمولا کار سختی نیست و از طرف دیگر برنامه‌ریزی‌های خطی را، حتی بعضا وقتی تعداد قیدهای آن نمایی باشد، می‌توان به سرعت حل کرد.
حالت خاص دیگری از برنامه‌ریزی ریاضی، برنامه‌ریزی صحیح است که مانند برنامه‌ریزی خطی است با این تفاوت که در برنامه‌ریزی صحیح می‌توان برروی برخی یا تمام متغیرها قید صحیح بودن را اضافه کرد. بدین صورت دیگر لزوما نمی‌توان برنامه‌ریزی صحیح را در زمان سریع حل کرد، اما تبدیل مسئله‌های الگوریتمی و مسئله‌های بهینه‌سازی ترکیبیاتی به برنامه‌ریزی صحیح کاری بسیار ساده‌تر است. از برنامه‌ریزی صحیح مخصوصا برای ارائه الگوریتم‌های تقریبی بسیار استفاده می‌شود.
اما حالت‌های دیگری نیز از برنامه‌ریزی ریاضی وجود دارد که نه برنامه‌ریزی خطی هستند و نه برنامه‌ریزی صحیح. برنامه‌ریزی نیمه معین، برنامه‌ریزی محدب، و برنامه‌ریزی غیر خطی برخی از انواع برنامه‌ریزی‌های ریاضی است.
درس برنامه‌ریزی ریاضی به بررسی انواع برنامه‌ریزی‌های ریاضی، کاربردهای آن در حل مسئله‌های مختلف و الگوریتم‌های یافتن جواب برای یک برنامه‌ریزی ریاضی می‌پردازد. این درس می‌تواند با سوگیری‌های مختلفی ارائه شود.
در این ترم، تاکید بر برنامه‌ریزی نیمه معین، تعریف آن، روش‌های حل آن، و کاربردهای آن در ارائه الگوریتم‌های تقریبی برای مسئله‌های ترکیبیاتی است.
این درس به عنوان درسی بعد از تحقیق در عملیات ۱ در نظر گرفته می‌شود. پس برای این کلاس لازم است دانشجویان با جبرخطی و برنامه‌ریزی خطی و تعبیرهای هندسی و دوگانی در برنامه‌ریزی خطی کاملا آشنا باشند. از طرف دیگر لازم است دانشجویان با درس الگوریتم آشنایی کامل داشته باشند تا بتوانند الگوریتم‌های تقریبی ارائه شده را دنبال کنند.
آشنایی با بهینه‌سازی ترکیبیاتی و بهینه‌سازی محدب و الگوریتم‌های تقریبی و پیچیدگی محاسباتی به همراهی با درس کمک فراوانی خواهد کرد.