Эквивалентность различных форм ЗЛП

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

Правила преобразования различных форм ЗЛП:

а) максимизация целевой функции эквивалентна минимизации целевой функции ;

б) ограничение-неравенство «≤» с помощью введения неотрицательной переменной можно заменить системой:

где s_i – остаточная переменная;

в) ограничение-неравенство «≥» с помощью введения неотрицательной переменной можно заменить сис­темой:

где s_i – избыточная переменная.

Остаточные и избыточные переменные называются еще свободными, балансовыми, дополнительны­ми;

г) ограничение-равенство можно заменить двумя неравенствами:

д) неравенство «≥» переводится в неравенство «≤» умножением его на –1.

е) m ограничений-равенств можно заменить на (m+1) неравенство:

ж) если на x_j не накладывается ограничение не отрицательности, то, введя новые две неотрицатель­ные переменные x_j⁺≥0, x_j^–≥0, исходную переменную x_j можно исключить путем замены: x_j=x_j⁺–x_j^–. Следовательно, всегда найдутся такие неотрицательные x_j⁺, x_j^–, что их разность даст x_j.