سیمپلکس دوگان

مسئلهٔ اولیه (کمینه‌سازی) و دوگان آن:

\min\; c^{T}x \;\; (Ax \ge b,\, x \ge 0) \qquad \Longleftrightarrow \qquad \max\; b^{T}y \;\; (A^{T}y \le c,\, y \ge 0)

در سیمپلکس دوگان با پایه‌ای شروع می‌کنیم که «بهینه ولی غیرشدنی» است: همهٔ $z_j - c_j$ نامنفی‌اند اما برخی $b_i$ منفی.

گام‌ها:

۱. سطری را که $b_i$ آن منفی‌ترین است به‌عنوان سطر خروجی بگیرید. اگر هیچ $b_i$ منفی نبود، جدول بهینه است.

۲. در آن سطر، برای ستون‌هایی با $a_{rj} < 0$ نسبت $\left|\dfrac{z_j - c_j}{a_{rj}}\right|$ را حساب کنید؛ کمترین نسبت ستون ورودی است. اگر هیچ $a_{rj} < 0$ نبود، مسئله شدنی نیست.

۳. محوری‌سازی کنید و تکرار نمایید.

این روش وقتی مفید است که پس از افزودن یک قید جدید به جدول بهینه، شدنی بودن از بین می‌رود.

روش‌های مرتبط