Алгоритм симплексного методу

З.Л.П. зображена в канонічній формі (22).

1. Заповнюємо початкову симплекс-таблицю. Її вид

Таблиця

Баз.	З	Xб(Ā0)	C1	C2		Cm	Cm+1		Cn
перем.	базис.		Ā0(X1)	Ā2(X2)	……….	Ām(Xm)	Ām+1(Xm+1)	…	Ān(Xn)
X1	C2	X1					X1m+1
X2	C2	X2					X2m+2
---	------	------	-------	-------	-------	--------	----------	----	----
Xm	Cm	Xm					Xmm+1		Xmm
∆j=Zj-Cj	Z0					∆m+1	…	∆n

У перших m рядках таблиці стоять вектори Ā_j, компоненти яких є коефіцієнтами в рівняннях обмежень при X_j . Остання m+1 рядок оцінна. Вона заповнюється в такий спосіб: стовпець З, як вектор, скалярно збільшується на всі наступні стовпці-вектори, причому Z₀=( • Ā_j), а ∆j=(Ā_j• )-C_j. Якщо в останньої, m+1, рядку всі оцінки ∆j≤0, то план X_on=(b₁;b₂;..,b_m;0;..,0) - оптимальний і min Z=Z₀. Якщо є ∆j>0, то X₀ план не оптимальний і включаючи кожної з векторів Āj (перемінну Xj) у базис можна одержати інший опорний план з меншою функцією мети. Якщо ∆j>0 трохи, то існують два шляхи перерахування таблиці. Перший шлях прискорений: у базис уводиться той вектор Ā_j (змінна X_j), якому відповідає max/Θ_0j· ∆_j/,де max береться по j, для яких ∆j>0 і Θ_0j визначається для кожного Ā_j, що вводиться в базис. При цьому функція мети для нового плану X зменшується (39) максимально. Це дозволяє знайти оптимальний план при меншому числі кроків перерахування симплекса-таблиці. Другий шлях спрощений: у базис уводиться вектор Ā_j з max∆_j

2. Після визначення вектора, що вводиться в базис, по спрощеному шляху, наприклад, Ā_k, знаходимо для нього мінімальне симплексне відношення

(40)

Зауваження 6

Якщо хоча б для однієї ∆j>0 всі компоненти вектора Ā_j X_ij≤0 , то функція мети Z не обмежена на багатограннику рішень. У цьому випадку багатогранник рішень необмежений (зауваження 5). Вибираючи Θ>0 як завгодно великим, одержуємо з (39), що min Z = -∞

Нехай у (40) , тобто симплексне відношення досягається для базисної змінний X_e що стоять у е-рядку і к-ий стовпець, на перетинанні яких стоїть X_ek називаються теж дозволяють.

Застосуємо формули повного виключення методу Жордана-Гаусса і введемо вектор Ā_k(Xk) у базис на місце вектора Ā_e(X_e). За цими формулами

(41)

перераховуються всі елементи старої таблиці та заповнюється нова таблиця, у тому числі й елементи оцінної m+1 рядка.

Якщо в m+1 рядку всі ∆j≤0, то отриманий у новій таблиці план оптимальний. Якщо є ∆j>0, то знову шукається новий опорний план і перераховується таблиця по (41). Процес продовжується або до одержання оптимального плану, або до встановлення необмеженості.

Зауваження 7. Якщо в отриманого оптимального плану оцінки ∆j>0 відповідають тільки базисним змінної, то цей план єдиний. У противному випадку цей оптимальний план не єдиний, тому що при введенні в базис вектора з ∆j>0 функція мети й оцінки ∆j, перелічувані по (41), не міняються. У випадку не одиничності оптимального плану в силу опуклості багатогранника рішень таких планів нескінченна безліч.

Зауваження 8. При рішенні З.Л.П. на max алгоритм перерахування симплексів-таблиць не міняється, тільки в базис треба вводити вектори з ∆j<0, тому що в цьому випадку план оптимальний, якщо всі ∆j≥0

Приклад 2. Вирішимо симплексом-методом задачу, розглянуту в попередньому прикладі. За початковий опорний план візьмемо перший опорний план =(3;0;4;0;4), якому відповідає функція мети Z₁=-3 зі значенням, більшим, ніж для другого опорного плану (Z₂=-9). Це дозволить зробити симплексним методом, принаймні, одне перерахування таблиці, тому що неоптимальний.

У цьому випадку З.Л.П. має канонічну форму виду

X₁+X₂-2X₄ =3

X₂-X₄+X₅ =4

-X₂+X₃+3X₄=4

___

X_j≥0 (j=1,..,5)

Min Z=3X₁-X₃+X₄-2X₅

Вирішимо цю задачу за алгоритмом симплекса-методу. Для цього заповнимо симплекс-таблицю.

Баз.	З	Xбаз			-1		-2	Θ0
перем.	базис.		X1	X2	X3	X4	X5
X1						-2		3/4
X5	-2					-1		4/1
X3	-1			-1				-
Z	=	-3				-8
X2						-2
X5	-2		-1
X3	-1
Z=-9	-2			-4

Обчислюємо й оцінки . Тому що ∆2=2>0, то план не оптимальний. Тому шукаємо інший опорний план, уводячи перемінну X₂, вектор Ā₂, у базис. Для перерахування таблиці знаходимо симплексне відношення для X₂ Θ₀ = min(3/1; 4/1)=3. Тоді X₁₂ =1 є елементом, що дозволяє, стовпець з _X 2 і рядок з _X 1 що дозволяють. По формулах (41) перераховуємо всю таблицю, у тому числі і

елементи останнього оцінного рядка. Тому що всі , то отриманий опорний план =(X₁=0; X₂=3; X₃=7; X₄=0; X₅=1) оптимальний, причому функція мети Z( )=-9

Зауваження 9. Для простоти перерахування таблиці можна використовувати таку схему (правило прямокутника):

(42)

Де Н.э - елемент у новій таблиці, що займає ту саму позицію, що і С_Е елемент у старій таблиці, P_Е - елемент, що дозволяє, D₁ і D ₂ - додаткові елементи, що стоять на другій діагоналі прямокутника, якщо вважати, що першу діагональ складають елементи СЭ і РЭ.

Якщо розділити почленно чисельник (42) на P_Е, то одержимо правило трикутника, перша формула в (41).