2. Симплексний метод розв’язання задач лп. Теоретичні основи симплекс-метода.

Симплекс метод полягає в послідовних переходах від одних опорних планів до інших так, щоб значення цільової функції зростало (якщо задача ЛП задається на пошук максимуму) або на зменшення цільової функції (якщо задача ЛП задається на пошук мінімуму). Оскільки число опорних планів задачі скінченне, то через скінченне число кроків отримаємо оптимальний опорний план (якщо він існує, або впевненість, що цільова функція на множені планів необмежена).

Розглянемо два різновиди симплексного метода:

• Симплекс – метод із стандартним базисом;

• Симплекс метод із штучним базисом (М- метод).

Симплекс – метод із стандартним базисом

Для застосування цього методу розглянемо задачу ЛП у канонічному вигляді

Z=∑c_ix_i →max

за умов

х₁e₁+ х₂e₂+ х₃e₃ + ….. + х_me_m + х_m+1P_m+1 + ….. + х_nP_n=P₀, де

e_i – одиничні вектори, P_k = (a_1k, a_2k,….. a_mk) (k=m+1,m+2,…. n), P₀ = (b₁, b₂,… b_m)

Оскільки перші m векторів е_i одиничними, то легко бачити, що виконується рівність

b₁e₁+ b₂e₂+ b₃e₃ + ….. + b_me_m =P₀.

Тоді очевидним є початковий опорний план: X=( b₁,b₂,b₃, ….. b_m, 0….0), який перевіряємо на оптимальність. Для цього заповнюємо симплексну таблицю.

Таблиця 1.

i	базис	Сбаз	Р0	c1	c2	…	сm	cm+1	…	cn
				P1	P2	0	Pm	Pm+1	…	Pn
1	P1	c1	b1	1	0	0	0	a1m+1	…	a1n
2	P2	c2	b2	0	1	0	0	a2m+1	…	a2n
…	…	…	...	0	0	1	0	…	…	…
m	Pm	сm	bm	0	0	0	1	amm+1	…	amn
		Δj	0	0	0	0	0	Δm+1	…	Δn

Усі рядки за винятком останнього рядка заповнюються за даними системи обмежень і цільової функції. Останній рядок обчислюється за формулою:

Δ_j=∑c_ia_ij – c_j , (j=1,2, …. n) і Δ₀=∑c_ib_{i .} Останній рядок називається індексним_.

Отриманий план перевіряють на оптимальність, зміст якої розкривається у наступних теоремах.

Теорема 1.

Якщо для деякого вектора P_j, який не входить у базис, виконується умова

Δ_j<0, (j=1,2,3…..n) (для задачі на максимум)

або

Δ_j>0, (j=1,2,3…..n) (для задачі на мінімум),

то можна отримати новий опорний план, для якого значення цільової функції f(x) буде більше (якщо f(x)→max),або менше ( якщо f(x)→min) вихідного; при цьому можуть бути два випадки:

а) якщо координати вектора P_j, який необхідно ввести у базис, недодатні, то задача ЛП не має розв’язку;

б) якщо існує хоча б одна додатня координата вектора P_j, який необхідно ввести у базис, то можна отримати новий опорний план.

Теорема 2.

Якщо для всіх векторів P_j, виконується умова

Δ_j≥0, (j=1,2,3…..n) (для задачі на максимум)

або

Δ_j≤0, (j=1,2,3…..n) (для задачі на мінімум),

то опорний план Х^*=((х₁)^*, (х₂)^*, ......... (х_n)^*) є оптимальним.

Якщо після побудови симплекс-таблиці виявилось, що виконуються умови Т.1 (пункт а)), або Т.2 розв’язання задачі припиняється. Якщо виконуються умови Т.1 (пункт б)), то потрібно перейти до нового оптимального опорного плану, побудувавши наступну симплексну таблицю. Для переходу до нового опорного плану треба один вектор вивести з базису і на його місце ввести новий вектор, який не належить базису. У базис вводять вектор, якому відповідає найбільша за абсолютною величиною від’ємна оцінка Δ_j. Нехай існує така оцінка в k- му стовпці, тобто max| Δ_j | = Δ_k.

Δ_j≤0

Тоді вектор Р_к вводимо у новий базис. Для знаходження вектора Р_r, який необхідно вивести, обчислюють співвідношення

Q= min(b_i/a_ik) ( i=1,2…..m) ,

мінімальне значення якого досягається при i=r. Елемент a_rk називається розв’язувальним .

Рядок Р_r і стовпець Р_к на перетині яких знаходиться розв’язувальний елемент a_rk, називають розв’язувальним. Для перерахунку елементів нової (наступної) симплекс – таблиці користуються методом Жордана – Гауса.