روش سیمپلکس

مسئله‌ی برنامه‌ریزی خطی را حل می‌کند: از گوشه‌ای از ناحیه‌ی شدنی شروع می‌کند و تا وقتی تابع هدف بهتر می‌شود به گوشه‌ی مجاور می‌رود؛ با کسرهای دقیق.

برنامه‌ریزی خطی: بیشینه کردن تابع خطی c·x با قیدهای خطی A·x ≤ b و x ≥ 0. ناحیه‌ی شدنی یک چندوجهی است و اگر جواب بهینه‌ای باشد، روی یکی از گوشه‌هاست.

ادامه‌ی توضیح ↓

زمان: exponential worst case, fast in practice
حافظه: O(m·n)
CLRS، بخش ۲۹.۳

ورودی:

A 3×3 · b 3×1 · c 1×3خروجی PDF

بیشینه‌ی 3x1 + x2 + 2x3 با سه قید؛ جواب ۲۸ در x = (8, 4, 0).

from fractions import Fraction
def simplex(A, b, c):
# Maximize c·x subject to A·x ≤ b and x ≥ 0 (with b ≥ 0, so x = 0 is a starting corner).
m, n = len(A), len(c[0])
# The tableau: [A | I | b] for the constraints, and [−c | 0 | 0] for the objective at the bottom.
T = [[Fraction(v) for v in A[i]] + [Fraction(int(i == k)) for k in range(m)] + [Fraction(b[i][0])] for i in range(m)]
T.append([Fraction(-v) for v in c[0]] + [Fraction(0)] * (m + 1))
basis = [n + i for i in range(m)]
while True:
# Bland's rule: the first variable whose objective entry is negative enters.
col = next((j for j in range(n + m) if T[m][j] < 0), None)
if col is None:
break
rows = [i for i in range(m) if T[i][col] > 0]
if not rows:
return None
row = min(rows, key=lambda i: (T[i][-1] / T[i][col], basis[i]))
pivot = T[row][col]
T[row] = [v / pivot for v in T[row]]
for i in range(m + 1):
if i != row and T[i][col] != 0:
f = T[i][col]
T[i] = [v - f * w for v, w in zip(T[i], T[row])]
basis[row] = col
x = [Fraction(0)] * n
for i, var in enumerate(basis):
if var < n:
x[var] = T[i][-1]
return str(T[m][-1]), [str(v) for v in x]

ناوردا: جدول همیشه یک گوشه‌ی شدنی را نشان می‌دهد (ستون آخر نامنفی است) و مقدار تابع هدف با هر محورگیری بدتر نمی‌شود.

شروع اجرا

basis—

جدول هنوز خالی است.

متغیرهای محلی

نارنجی = در همین گام عوض شد

`A` list

[1, 1, 3][2, 2, 5][4, 1, 2]

`b` list

[30][24][36]

`c` list

[3, 1, 2]

Call stack

simplex()خط 4

گام ۱ از ۶۸

توضیح

ایده

سیمپلکس

از گوشه‌ی x = 0 شروع کن (چون b ≥ 0 شدنی است). متغیرهای کمبود (slack) اول در «پایه»اند.
اگر در سطر هدف ضریب منفی هست، افزایش آن متغیر سود دارد: وارد پایه می‌شود.
آزمون نسبت تعیین می‌کند تا کجا می‌شود جلو رفت و کدام متغیر از پایه بیرون می‌رود.
محورگیری (مثل حذف گاوسی) جدول را برای گوشه‌ی تازه بازنویسی می‌کند.
وقتی هیچ ضریب منفی‌ای نماند، جواب بهینه است.

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

هزینه

در بدترین حالت نمایی است، ولی در عمل خیلی سریع است و هنوز پرکاربردترین روش است.

در trace به چه چیزی نگاه کنی

جدول T را بعد از هر محورگیری ببین؛ ستون آخر مقدار متغیرهای پایه و گوشه‌ی پایین-راست مقدار تابع هدف است.