Формы записи задачи линейного программирования, их эквивалентность и способы преобразования

Модель задачи линейного программирования может быть записана в одной из приведенных ниже форм:

1. Общая, или произвольная, форма записи:

max(min)Z=

при ограничениях:

2.Симметричная, или стандартная, форма записи:

maxZ= minZ=

3.Каноническая, или основная, форма записи:

maxZ=

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

Так, при необходимости задачу минимизации можно заменить задачей максимизации, и наоборот. Очевидно, что минимальное значение функции z(x) равно максимальному значению функции- z(x), взятому с противоположным знаком, т.е.

min z(x)=-max(-z(x)).

Неравенство типа > путем умножения левых и правых частей на -1 можно превратить в неравенство типа <, и наоборот. Ограничения-неравенства

преобразуются в ограничения-равенства путем прибавления (вычитания) к левым частям дополнительных (балансовых) неотрицательных переменных x_n+i > 0:

В случае необходимости ограничение-равенство

можно записать в виде системы неравенств

Если в ЗЛП какая-то переменная x_kне подчинена условию неотрицательности, ее заменяют разностью двух других неотрицательных переменных х'_k > 0 и х"_k > 0:

x_k= х'_k - х"_k.