Загальна характеристика симплекс-методу

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

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

Будь-яку задачу лінійного програмування можна звести до стандартної форми – основної задачі лінійного програмування (ОЗЛП), де замість обмежень-нерівностей переходять до обмеження-рівностей. Такий запис умов – обмежень зручний для розв’язування задач лінійного програмування симплекс-методом.

Отже, кожне обмеження – нерівність виду

(1)

або у розгорнутому виді:

(1а)

можна замінити рівністю, якщо ввести додаткову змінну . Тоді маємо

(2)

тобто

(3)

Таким чином, система обмежень приймає вигляд:

(4)

а цільову функцію можна записати так:

(5)

Система рівнянь (4), (5) відповідає всім вимогам задач лінійного програмування і використовується для розв’язання симплекс-методом

Вимоги алгоритму симплекс-метода:

обмеження представляються у вигляді системи лінійних рівнянь;

вільні члени повинні бути не менше нуля: ;

всі змінні повинні бути не менше нуля: .

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

План задачі – будь-яке рішення (розв’язок) системи рівнянь .

Компоненти плану – окремі значення змінних.

Допустимий план – план, всі компоненти якого не менше 0, тобто .

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

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