Переход к канонической форме

Подавляющее большинство известных методов решения задач линейного программирования предназначены для канонических задач. Поэтому начальный этап решения всякой общей задачи линейного программирования обычно связан с приведением ее к некоторой эквивалентной канонической задаче.

Общая идея перехода от ОЗЛП к КЗЛП достаточно проста:

Øограничения в виде неравенств преобразуются в уравнения за счет добавления фиктивных неотрицательных переменных , которые одновременно входят в целевую функцию с коэффициентом 0, т. е. не оказывают влияния на ее значение;

Øпеременные, на которые не наложено условие неотрицательности, представляются в виде разности двух новых неотрицательных переменных:

Øпеременные, на которые наложено условие неположительности, представляются в виде новой неотрицательной переменной помноженной на -1:

Нетрудно заметить, что «платой» за переход от общей формы задачи линейного программирования к канонической является рост ее размерности, что, при прочих равных условиях, является фактором, усложняющим процесс решения.

СИМПЛЕКС-МЕТОД