روش برنامه ریزی خطی (Linear Programming Methods - e.g., Simplex Method)، در ریاضیات (Mathematics)
انواع روش های عددی (Numerical Methods) را در آموزش زیر شرح دادیم :
روش برنامه ریزی خطی (Linear Programming Methods - e.g., Simplex Method) :
بهینه سازی توابع خطی با قیود خطی
توضیح ساده: برنامه ریزی خطی (LP) شاخه ای از بهینه سازی است که به کمینه یا بیشینه کردن یک تابع هدف خطی تحت قیود خطی می پردازد. مسائل LP در اقتصاد، مدیریت، مهندسی و علوم نظامی بسیار رایج هستند. معروف ترین روش برای حل LP، روش سیمپلکس (Simplex Method) است که توسط جورج دانتزیگ در دهه ۱۹۴۰ توسعه یافت. روش های دیگر شامل روش نقاط داخلی (Interior Point Methods) هستند که برای مسائل بزرگ مقیاس کارآمدتر می باشند.
شرح گام به گام: فرم استاندارد LP: minimize cᵀx subject to Ax = b, x ≥ 0.
روش سیمپلکس:
۱. یک جواب پایه اولیه شدنی (Basic Feasible Solution) پیدا کنید.
۲. در هر تکرار:
- یک متغیر غیرپایه (Nonbasic) که با وارد شدن به پایه می تواند تابع هدف را بهبود بخشد انتخاب کنید (بر اساس ضرایب کاهش یافته).
- یک متغیر پایه را برای خروج انتخاب کنید (با آزمون نسبت).
- با عملیات سطری (مشابه حذف گاوس)، جواب پایه جدید را محاسبه کنید.
۳. تا بهینه شدن (همه ضرایب کاهش یافته ≥۰ برای کمینه سازی) ادامه دهید.
روش نقاط داخلی (مانند روش کرمارکر): با حرکت در داخل ناحیه شدنی و با استفاده از روش نیوتن برای حل معادلات KKT، به سمت جواب بهینه حرکت می کنند. این روش ها برای مسائل بزرگ مقیاس بسیار کارآمدتر از سیمپلکس هستند.
مثال عددی: یک کارخانه دو محصول تولید می کند. هر محصول نیاز به مواد اولیه و زمان ماشین دارد. هدف حداکثر سود با محدودیت منابع است. این یک مسئله LP است که با روش سیمپلکس حل می شود. نرم افزارهایی مانند LINDO و MATLAB (دستور linprog) این مسائل را حل می کنند.
مزایا: روش های کارآمد و بالغ، تضمین یافتن بهینه سراسری.
معایب: فقط برای مسائل خطی کاربرد دارد. روش سیمپلکس در بدترین حالت زمان نمایی دارد (اما در عمل سریع است).
کاربردها: در برنامه ریزی تولید، در حمل و نقل، در تخصیص منابع، در اقتصاد.
نکته: روش سیمپلکس یکی از تأثیرگذارترین الگوریتم های قرن بیستم است.
