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

Графічний метод для визначення оптимального плану задач лінійного програмування доцільно застосовувати лише для задач із двома змінними. За більшої кількості змінних необхідно застосовувати інший метод. З властивостей розв'язків задачі лінійного програмування відомо: оптимальний розв'язок задачі має знаходитись в одній з кутових точок багатогранника допустимих розв'язків. Тому найпростіший спосіб відшукання оптимального плану потребує перебору всіх кутових точок (допустимих планів задачі, які ще називають опорними). Порівняння вершин багатогранника можна здійснювати тільки після відшукання якоїсь однієї з них, тобто знайшовши початковий опорний план. Кожний опорний план визначається системою m лінійно незалежних векторів, які містяться в системі обмежень задачі з n векторів . Отже, загальна кількість опорних планів визначаєтьсякількістю комбінацій . Задачі, що описують реальні економічні процеси, мають велику розмірність, і простий перебір всіх опорних планів таких задач є дуже складним, навіть за умови застосування сучасних ЕОМ. Тому необхідне використання методу, який уможливлював би скорочення кількості обчислень. 1949 року такий метод був запропонований американським вченим Дж.Данцігом — так званий симплексний метод, або симплекс-метод.

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

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

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

5.1. Початковий опорний план

Розглянемо задачу лінійного програмування, записану в канонічній формі: ,

Не порушуючи загальності, допустимо, що система рівнянь містить перші m одиничних векторів. Отримаємо:

(5.1.1)

(5.1.2)

(5.1.3)

Система обмежень (5.1.2) у векторній формі матиме вигляд:

, (5.1.4)

де

, ,…, , , …, , ,

- лінійно незалежні одиничні вектори m -вимірного простору, що утворюють одиничну матрицю і становлять базис цього простору. Тому в розкладі (5.1.4) базисними змінними будуть , а інші змінні – вільні. Прирівняємо всі вільні змінні до нуля, тобто . Оскільки , а вектори - одиничні, то отримаємо один із розв’язків системи обмежень (5.1.2):

, (5.1.5)

тобто допустимий план.

Такому плану відповідає розклад

, (5.1.6)

де - лінійно незалежні вектори і за теоремою 4.3 план є кутовою точкою багатогранника розв’язків, а отже, може бути початковим опорним планом.

5.2. Оптимальний розв’язок. Критерій оптимальності плану

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

Розглянемо задачу лінійного програмування (5.1.1)-(5.1.3).

Допустимо, що вона має опорні плани і вони є не виродженими. Розглянемо початковий опорний план виду (5.1.5), якому відповідає розклад за базисними векторами (5.1.6) та значення функціонала

.

Кожен з векторів можна розкласти за векторами базису, причому у єдиний спосіб:

,

тому такому розкладу відповідатиме і єдине значення функціонала:

.

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

,

то план є оптимальним розв’язком задачі лінійного програмування (5.1.1-5.1.3).

Аналогічно формулюється умова оптимальності плану задачі на відшукання мінімального значення функціонала: якщо для деякого плану розклад всіх векторів у даному базисі задовольняє умову:

,

то план є оптимальним розв’язком задачі лінійного програмування.

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

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

Теорема 5.2.1. Якщо для деякого вектора виконується умова , то план не є оптимальним і можна відшукати такий план X, для якого виконуватиметься нерівність .

Теорема 5.2.2. Якщо для деякого вектора виконується умова , то план не є оптимальним і можна відшукати такий план X, для якого виконуватиметься нерівність .