روش سیمپلکس دوگانه (Dual Simplex Method)، در ریاضیات (Mathematics)
انواع روش های بهینه سازی (Optimization Methods) را در آموزش زیر شرح دادیم :
روش سیمپلکس دوگانه (Dual Simplex Method) :
📌 مفهوم دوگانگی در سیمپلکس
روش سیمپلکس دوگانه (Dual Simplex Method) نسخه ای از الگوریتم سیمپلکس است که بر روی مسئله دوگان (Dual Problem) عمل می کند، اما مستقیما روی جدول مسئله اصلی (Primal) اجرا می شود. این روش زمانی مفید است که یک جواب شدنی اولیه برای مسئله اصلی نداریم، اما جواب شدنی برای مسئله دوگان داریم.
🔄 تفاوت با سیمپلکس معمولی
در سیمپلکس معمولی، از یک جواب شدنی (Feasible) اما غیربهینه (Non-optimal) شروع می کنیم و به سمت بهینگی حرکت می کنیم.
در سیمپلکس دوگانه، از یک جواب غیرشدنی (Infeasible) اما بهینه (Optimal) برای مسئله دوگان شروع می کنیم و به سمت شدنی شدن حرکت می کنیم.
شرط توقف: وقتی همه متغیرهای اصلی غیرمنفی شدند (یعنی جواب شدنی شد).
🔧 کاربردها
سیمپلکس دوگانه کاربردهای مهمی دارد:
زمانی که قیود از نوع
\[ \geq \]هستند و اضافه کردن متغیرهای مصنوعی اجتناب ناپذیر است.
در تحلیل حساسیت (Sensitivity Analysis) و اضافه کردن قیود جدید به مسئله.
در مسائل برنامه ریزی خطی که با روش دو فازی نیز قابل حل هستند، سیمپلکس دوگانه ممکن است کارآمدتر باشد.
📝 مثال
فرض کنید مسئله زیر را داریم:
\[ \text{Minimize} \quad Z = 2x_1 + 3x_2 \] \[ \text{Subject to:} \quad x_1 + x_2 \geq 3 \] \[ \quad 2x_1 + x_2 \geq 4 \] \[ \quad x_1, x_2 \geq 0 \]برای حل با سیمپلکس دوگانه، ابتدا قیود را با ضرب در منفی یک به فرم
\[ \leq \]تبدیل می کنیم، سپس متغیرهای کمکی اضافه کرده و جدول اولیه را تشکیل می دهیم. الگوریتم از یک جواب غیرشدنی شروع کرده و به تدریج آن را شدنی می کند.
