1.6. Симплексний алгоритм

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

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

Крок 1. Виберемо m змінних, що задають припустиме спробне рішення. Виключимо ці змінні з виразу для цільової функції.

Крок 2. Перевіримо, чи не можна за рахунок однієї зі змінних, прирівняної спочатку до нуля, поліпшити значення цільової функції, додаючи їй відмінні від нуля (причому позитивні) значення. Якщо це можливо, перейдемо до кроку 3. У протилежному випадку припинимо обчислення.

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

Крок 4. Вирішимо систему m рівнянь щодо змінних, що ввійшли в нове спробне рішення. Виключимо ці змінні з виразу для цільової функції. Повернемося до кроку 2.

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

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

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

Вихідна і двоїста задачі. Розглянемо дві наступні задачі лінійного програмування:

максимізувати (1.34)

при обмеженнях

(i = 1, 2, …, m), (1.35)

(j= 1, 2, ..., n). (1.36)

та

мінімізувати (1.37)

при обмеженнях

(j = 1, 2, …, n), (1.38)

(i = 1, 2, …, m). (1.39)

Для визначеності умовно назвемо першу задачу [співвідношення (1.34) – (1.36)] вихідною, а другу [співвідношення (1.37) – (1.39)] двоїстою (стосовно першої).

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

вихідна задача:

максимізувати 4х₁ + 5х₂ + 9х₃, (1.40)

при наступних обмеженнях:

1х₁ + 1х₂ + 2х₃ ≤ 16,

7х₁ + 5х₂ + 3х₃ ≤ 25, (1.41)

двоїста задача:

мінімізувати 16х₁ + 25х₂, (1.42)

при наступних обмеженнях:

1у₁ + 7у₂  4,

1у₁ + 5у₂  5,

2у₁ + 3у₂  9, (1.43)

Інакше кажучи, двоїста задача – це на 90º обернена вихідна задача.

Дійсно,

1) j-й стовпець, складений з коефіцієнтів, що фігурують в обмеженнях вихідної моделі, збігається з j-й рядком, складеної з коефіцієнтів, що фігурують в обмеженнях двоїстої моделі;

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

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

4) напрямок знаків нерівності у вихідній моделі протилежно напрямку знаків нерівності в двоїстій моделі; вимога максимізації у вихідній задачі замінено вимогою мінімізації.

Має місце наступна важлива теорема (теорема подвійності):

а) Якщо вихідна і двоїста їй задачі мають припустиме рішення, то:

1) існує оптимальне рішення (j = 1, 2, …, n) вихідної задачі;

2) існує оптимальне рішення (i = 1, 2, …, m) двоїстої задачі;

3) має місце наступне співвідношення:

(1.44)

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

Оптимальні значення змінних двоїстої задачі.

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

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

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

Оптимальне значення х₀ =  (Константи в правих частинах обмежень) ×

× (Оптимальні значення змінних двоїстої задачі).

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