Двоїстий симплексний метод

Проілюструємо особливості двоїстого симплексного методу на прикладі наступної задачі:

Складемо двоїсту задачу стосовно заданої

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

Виявляється, що відзначений факт є необхідною й достатньою умовою існування оптимального плану ЗЛП.

Теорема.

Для того, щоб рішення деякої ЗЛП містило оптимальний план, необхідно й достатньо, щоб воно було прямо - і двоїсто - припустимим.

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

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

У прямому симплексному методі розв'язувальний стовпець вибирають по від’ємному коефіцієнту в рядку лінійної форми F. Далі, маючи невід’ємний розв'язувальний елемент щораз домагаються невід’ємних значень у рядку лінійної форми F, за винятком вільного члена. Таким чином, зберігаючи прямо – припустимість рішення, домагаються двоїстої припустимості.

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

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

Ідея рішення ЗЛП двоїстим симплексним методом у наступному: зберігаючи двоїсту допустимість рішення, домагаються, щоб воно було й прямо - припустимим.

У зв'язку з відзначеним, алгебру двоїстого симплексного методу можна вказати у вигляді набору наступних правил:

1. Розв'язувальний рядок вибирається по від’ємному значенню вільного члена (за винятком вільного члена цільової функції)

2. Вибирають розв'язувальний стовпець по мінімуму двоїстого симплексного співвідношення (тобто по мінімальному відношенню коефіцієнтів при невідомих цільової форми до модуля від’ємних коефіцієнтів розв'язувального рядка).

Дата добавления: 2014-12-07