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

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

Як відомо кожній задачі лінійного програмування можна пос-тавити у відповідність двоїсту задачу. Теоремами двоїстості встановлено зв’язок між розв’язками прямої та двоїстої задач. Для знаходження розв’язку однієї зі спряжених задач можна пе-рейти до двоїстої і, використовуючи її оптимальний план, визна-чити оптимальний план початкової.

Перехід до двоїстої задачі не обов’язковий. Легко помітити, що звичайна симплексна таблиця в стовпчиках містить початкову задачу, а в рядках — двоїсту. Оцінками плану прямої задачі є рядок Неможливо розібрати вираз (невідома помилка): \Delta_{j} =F_{j} -c_{j}

Неможливо розібрати вираз (невідома помилка): (j=\overline {1,n})
а оцінками плану двоїстої — стовпчик «План» з компонентами вектора вільних членів системи обмежень В. Отже, розв’язуючи пряму задачу, симплексний метод дає змогу одночасно знаходити і розв’язок двоїстої задачі. Однак двоїсту задачу можна також розв’язати за таблицею, в якій записана пряма, а відшукавши оптимальний план двоїстої задачі, разом з тим отримати розв’язок початкової задачі. Такий спосіб розв’язання задачі лінійного програмування має назву двоїстого симплексного методу. Прямий та двоїстий симплексні методи пов’язані між собою.

Нехай необхідно розв’язати задачу лінійного програмування, подану в канонічному виді:

Неможливо розібрати вираз (невідома помилка): min \,\,F=CX

                (1)

Неможливо розібрати вираз (невідома помилка): AX=B

                        (2)

Неможливо розібрати вираз (невідома помилка): X\ge 0

                      (3)