К задаче с ограничениями типа равенств

В задачах линейного программирования ограничения типа неравенств могут быть представлены в виде равенств введением новых переменных, называемых дополнительными. Для этого в каждом соотношении (1.2а) прибавим к левой части дополнительную переменную , которая превращает неравенство в равенство

, .

При этом все дополнительные переменные положительны. Для неравенств (1.2б), можно также записать, учитывая положительность дополнительных переменных

, .

Тогда система ограничений (1.2) может быть записана в виде

, . (1.3)

Любое решение системы уравнений (1.3), состоящее из неотрицательных значений переменных называется допустимым решением.

Допустимое решение, в котором m составляющих отличны от нуля называется допустимым базисным решением или планом.

Задача отыскания оптимального решения заключается в переборе только базисных решений системы (1.3).

Процедурой последовательного улучшения плана или построения базисного решения является симплексный метод [1, 2].