سیمپلکس جدولی

مسئلهٔ برنامه‌ریزی خطی در شکل استاندارد بیشینه‌سازی:

با افزودن متغیر کمکی $s_i \ge 0$ به هر قید، دستگاه معادلات $Ax + s = b$ ساخته می‌شود و متغیرهای کمکی پایهٔ اولیه‌اند.

گام‌های الگوریتم:

۱. در سطر $Z$ جدول، ضرایب $z_j - c_j$ را بررسی کنید. اگر همه نامنفی باشند، جدول بهینه است.

۲. ستون ورودی را ستونی بگیرید که $z_j - c_j$ آن منفی‌ترین است.

۳. نسبت $\theta_i = \dfrac{b_i}{a_{ik}}$ را فقط برای $a_{ik} > 0$ حساب کنید؛ کمترین نسبت، سطر خروجی را تعیین می‌کند. اگر هیچ $a_{ik} > 0$ نبود، مسئله بی‌کران است.

۴. عملیات سطری (محوری‌سازی) انجام دهید تا ستون ورودی به بردار یکه تبدیل شود و به گام ۱ برگردید.

مقدار بهینه در ستون سمت راست سطر $Z$ و جواب متغیرهای پایه در ستون $b$ خوانده می‌شود. اگر در جدول بهینه برای یک متغیر غیرپایه $z_j - c_j = 0$ باشد، مسئله جواب بهینهٔ چندگانه دارد.