2.3 Симплекс-метод

Симплекс-метод є універсальним аналітичним методом розв’язку задач лінійного програмування. Симплекс ‑ поняття геометричне, означає сукупність вершин багатомірного тіла. Ідея симплекс-методу полягає в послідовному переборі розв’язків ‑ у послідовному переході від однієї вершини до іншої. Однак цей перебір не хаотичний, а такий, що на кожному кроці розв’язок поліпшується.

Метод складається з двох етапів: на першому етапі шукається допустимий розв’язок; на другому етапі цей допустимий розв’язок покращується до оптимального.

Канонічний вигляд задач ЛП має вигляд:

при

Для того, щоб перейти від обмежень типу нерівностей до рівностей необхідно ввести додаткові змінні на одну більше кількості керованих змінних. Будь-яку задачу на максимум можна перевести в задачу на мінімум і навпаки, для цього треба замінити знаки цільової функції на протилежні.

Задачі ЛП розв’язуються з використанням симплексних таблиць.

В загальному вигляді симплекс-таблиця має вигляд (табл. 2.3):

Таблиця 2.3

C			C₁	C₂	C₃	…	C_j	…	C_n
	B_x	a_io	A₁	A₂	A₃	…	A_j	…	A_n
C₁	x₁	a₁₀	a₁₁	a₁₂	a₁₃	…	a_1j	…	a_1n
C₂	x₂	a₂₀	a₂₁	a₂₂	A₂₃	…	a_2j	…	a_2n
…	…	…	…	…	…	…	…	…	…
C_i	x_i	a_i0	a_i1	a_i2	a_i3	…	a_ij	…	a_in
…	…	…	…	…	…	…	…	…	…
C_m	x_m	a_m0	a_m1	a_m2	a_m3	…	a_mj	…	a_mn
	∆	a₀₀	∆₁	∆₂	∆₃	…	∆_j	…	∆_n

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

Значення цільової функції а₀₀визначається:

В стовпчику В_хзаписують базисні змінні {x_i}. Їх значення визначаються стовпчиком вільних членів а_іо, тобто х_і= а_іо, і=1,2,...,m.

Розв’язуючі рядок і стовпчик позначають стрілками. Для покращення плану вибирають розв’язуючий стовпчик (РС) серед від’ємних елементів індексного рядка, і при цьому його беруть максимальним за модулем.

Розв’язуючий рядок (РР) вибирають з виразу: .

На перетині РС та РР буде знаходитися а_ij – розв’язуючий елемент (РЕ).

Далі роблять перший крок симплекс-перетворення з РЕ а_ij.

1. Ділимо елементи РР на РЕ.

2. Елементи РС заповнюються 0, включаючи індексний рядок.

3. Всі інші елементи симплекс-таблиці розраховуємо за правилом прямокутника: в чисельнику різниця добутків елементів, які лежать на діагоналях, в знаменнику – розв’язуючий елемент.

Симплекс-перетворення виконують до тих пір, поки усі а₀_g≥0 – є умовою оптимальності базису останньої таблиці. Або знайдеться такий а₀_j=∆_j<0, що усі елементи цього стовпця а_rj≤0. Це є ознакою необмеженості цільової функції на множині допустимих розв’язків.

Особливості застосування табличного симплекс-методу:

· Якщо в якості початкового базису вибирають базис із вільних змінних, для яких с_і=0, то оцінки для усіх небазисних змінних дорівнюють , а відповідне значення цільової функції .

· Відсутність векторів з від’ємними оцінками (при розв’язуванні задач максимізації) є ознакою оптимальності відповідного базисного розв’язку.

· Якщо є хоча б одна від’ємна оцінка для небазисного вектора, а його стовпчик містить тільки не додатні елементи, то в області допустимих розв’язків цільова функція не обмежена.

· При розв’язуванні задачі мінімізації в базис вводиться вектор з найбільшою додатною оцінкою.