Симплексний метод розв’язування задач лінійного програмування

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

Симплекс-метод – це поетапна обчислювальна процедура, в основу якої покладено принцип послідовного поліпшення значень цільової функції переходом від одного опорного плану задачі ЛП до іншого.

Цей метод можна використовувати для розв’язування задач ЛП, які записані в канонічній формі, тобто:

1) задача ЛП записана в першій стандартній формі (обмеження-рівності);

2) праві частини рівнянь-обмежень (вільні члени) невід’ємні;

3) система рівнянь-обмежень має чітко виділений базис, тобто в кожному рівнянні є невідома з коефіцієнтом 1 і ця невідома відсутня в усіх інших рівняннях системи обмежень. Ці невідомі називаються базисними, а всі інші – вільними;

4) цільова функція залежить тільки від вільних невідомих.

Алгоритм симплексного методу розв’язування задач лінійного програмування складається з таких етапів:

1. Визначення початкового опорного плану задачі лінійного програмування.

2. Побудова симплексної таблиці.

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

4. Перехід до нового опорного плану задачі здійснюється визначенням ключового (генерального) елемента та розрахунком нової симплекс-таблиці.

5. Повторення дій, починаючи з п.3.
Розглянемо детальніше кожен етап цього алгоритму.

1.Визначення початкового опорного плану починають із запису задачі лінійного програмування у канонічній формі. Якщо в системі обмежень є обмеження-нерівності, то до лівої частини обмежень типу «≤» додаємо додаткові невід’ємні невідомі, а від лівих частин обмежень типу «≥» віднімаємо додаткові невід’ємні невідомі. Якщо права частина обмеження від’ємна, то множимо все обмеження на (–1). Якщо цільова функція містить базисні невідомі, то виражаємо їх через вільні з системи обмежень і підставляємо в цільову функцію.

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

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

В першому стовпчику таблиці записуємо номер таблиці (ітерації), в другому стовпчику – номер рядка, в наступному – «Базис» (базисні невідомі), далі – «Опорний план» (значення базисних змінних), а у решті стовпчиків, кількість яких дорівнює кількості невідомих задачі, – відповідні коефіцієнти при невідомих кожного обмеження задачі лінійного програмування.

Звернемо увагу на те, що в нульовому рядочку симплекс-таблиці записуємо дані з цільової функції.

3.Перевіряємо опорний план на оптимальність згідно з теоремою.

Теорема (критерій оптимальності симплекс-методу). Якщо цільова функція максимізується (мінімізується) і в нульовому рядку відсутні від’ємні (додатні) числа, за винятком стовпчика «Опорний план», то опорний план є оптимальним.

У процесі перевірки умови оптимальності можливі такі випадки:

а) умова оптимальності виконується, а отже опорний план є оптимальним;

б) умова оптимальності не виконується, тоді потрібно перейти до нового опорного плану.

4. Перехід від одного опорного плану до іншого виконується зміною базису, тобто виключенням з базису деякої змінної та введенням замість неї нової з числа вільних невідомих задачі.

Змінну, яку потрібно ввести в базис, визначаємо за елементами нульового рядка. Якщо цільова функція досліджується на мінімум і в нульовому рядку симплекс-таблиці є додатні числа (за винятком стовпчика «Опорний план»), то вибираємо найбільше з цих чисел і невідому, що відповідає цьому числу, вводимо в базис. Якщо ж цільова функція досліджується на максимум і в нульовому рядку симплекс-таблиці є від’ємні числа (за винятком стовпчика «Опорний план»), то вибираємо найменше з них (найбільше по модулю) і невідому, що йому відповідає, вводимо в базис. Стовпець, який відповідає невідомій, що вводиться в базис, називається ключовим.

Для визначення змінної, яка має бути виведена з базису, знаходять відношення елементів стовпця «Опорний план» до відповідних додатних елементів ключового стовпця (нульовий рядок не розглядаємо) і вибираємо найменше з цих відношень. Невідому, яка відповідає цьому відношенню, виключаємо з базису. Рядок, який відповідає цьому найменшому відношенню, називається ключовим рядком. На перетині ключового рядка і ключового стовпця знаходиться ключовий (генеральний) елемент. За допомогою генерального елемента і методу Жордана-Гауса переходимо до нової симплекс-таблиці.

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

При застосуванні симплекс-методу для розв’язування задач лінійного програмування можливі такі випадки:

1) Якщо ми отримали оптимальний план задачі ЛП і в нульовому рядку останньої симплекс-таблиці вільній невідомій відповідає коефіцієнт, рівний нулю, то це свідчить про те, що існує неєдиний розв’язок задачі. Альтернативний оптимальний план можна отримати, якщо ввести цю невідому в базис і здійснити ще одну ітерацію.

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