روش سیمپلکس (Simplex Method)، در ریاضیات (Mathematics)
انواع روش های بهینه سازی (Optimization Methods) را در آموزش زیر شرح دادیم :
روش سیمپلکس (Simplex Method) :
📌 معرفی روش
روش سیمپلکس (Simplex Method) که توسط جورج دانتزیگ در سال ۱۹۴۷ ابداع شد، معروف ترین و پرکاربردترین الگوریتم برای حل مسائل برنامه ریزی خطی است. این روش به صورت سیستماتیک روی رئوس ناحیه موجه حرکت می کند تا به نقطه بهینه برسد. ایده اصلی این است که اگر جواب بهینه وجود داشته باشد، در یکی از رئوس (نقاط گوشه) ناحیه موجه قرار دارد.
⚙️ مراحل الگوریتم
تبدیل به فرم استاندارد: نامعادلات به معادلات تبدیل می شوند (با اضافه کردن متغیرهای کمکی Slack Variables).
ایجاد جدول سیمپلکس: ضرایب در یک جدول ماتریسی مرتب می شوند.
تشخیص جواب موجه اولیه: معمولا با قرار دادن متغیرهای اصلی (غیرکمکی) برابر صفر شروع می شود.
شرط بهینگی: بررسی می شود که آیا ضرایب سطر Z (هزینه های کاهش یافته) همه غیرمنفی هستند (برای مسائل کمینه سازی). اگر بله، جواب بهینه است.
انتخاب ستون محور (Pivot Column): منفی ترین ضریب در سطر Z انتخاب می شود (متغیر ورودی).
انتخاب سطر محور (Pivot Row): کوچکترین نسبت (مقدار سمت راست تقسیم بر ضریب مثبت ستون محور) انتخاب می شود (متغیر خروجی).
انجام عملیات سطری: سطر محور به ۱ تبدیل می شود و سایر سطرها به صفر می رسند.
تکرار: مراحل ۴ تا ۷ تکرار می شوند تا شرط بهینگی برقرار شود.
📊 مثال با جدول سیمپلکس
برای مثال قبلی (محصولات A و B)، فرم استاندارد با متغیرهای کمکی
\[ s_1 \]و
\[ s_2 \]:
\[ \text{Maximize} \quad Z = 40x_1 + 30x_2 + 0s_1 + 0s_2 \] \[ 2x_1 + x_2 + s_1 = 100 \] \[ x_1 + 2x_2 + s_2 = 80 \] \[ x_1, x_2, s_1, s_2 \geq 0 \]