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

4.1 Загальні аспекти застосування симплекс-методу

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

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

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

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

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

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

.

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

(4.1)

(4.2)

(4.3)

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

, (4.4)

де , ,..., ,

, …, , ,

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

(4.5)

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

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

(4.6)

де — лінійно незалежні вектори і за властивістю 3 розв’язків задачі лінійного програмування (п.3.4) план є кутовою точкою багатогранника розв’язків, а отже, може бути почат­ковим опорним планом.