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

Ранее было рассмотрено (п. 1.3), как с помощью симплекс-метода можно получить решение задачи линейного программирования, предварительно приведя её к канонической форме (задача 1.18).

Двойственный симплекс-метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой не обязаны быть неотрицательными (как в задаче 1.18), (), т.е. могут быть любыми числами.

, (1)

Применив к системе (1) метод Жордана – Гаусса, можно привести её к виду:

(2)

где - базисные переменные, а - свободные переменные и - любого знака. Выразив базисные переменные через свободные, получим общее решение системы ограничений (2):

.

Однако это решение не является планом задачи (1), т.к. среди его компонент имеются отрицательные числа.