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

Мета роботи – навчитися розв’язувати задачі лінійного програмування з використанням двоїстого методу.

У результаті виконання роботи студент повинен:

ЗНАТИ умови допустимості та оптимальності під час розв’язання задачі двоїстим методом;

УМІТИ здійснювати перехід від одного плану до іншого;

МАТИ УЯВЛЕННЯ про виконання критеріїв оптимальності.

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

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

Двоїста умова допустимості. В якості змінної, що виключається з базису, обирається змінна, що має найбільше за абсолютним значенням від’ємне значення. Якщо таких змінних декілька, то вибір є довільним. Якщо всі базисні змінні є невід’ємними, то процес обчислень закінчується.

Двоїста умова оптимальності. Змінна, що вводиться до базису, визначається як змінна, на якій досягається наступний мінімум:

min

небазисні j

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