Модель задачи линейного программирования может быть записана в одной из приведенных ниже форм:
1. Общая, или произвольная, форма записи:
max(min)Z=
при ограничениях:
2.Симметричная, или стандартная, форма записи:
maxZ= minZ=
3.Каноническая, или основная, форма записи:
maxZ=
Указанные выше три формы записи ЗЛП эквивалентны в том смысле, что каждая из них с помощью несложных преобразований может быть сведена к другой форме, т.е. если имеется способ нахождения оптимального решения задачи в одной из указанных форм, то тем самым может быть определен оптимальный план задачи в любой другой форме (говорят о стратегической эквивалентности задачи в любой из форм).
Так, при необходимости задачу минимизации можно заменить задачей максимизации, и наоборот. Очевидно, что минимальное значение функции z(x) равно максимальному значению функции- z(x), взятому с противоположным знаком, т.е.
min z(x)=-max(-z(x)).
Неравенство типа > путем умножения левых и правых частей на -1 можно превратить в неравенство типа <, и наоборот. Ограничения-неравенства
|
|
преобразуются в ограничения-равенства путем прибавления (вычитания) к левым частям дополнительных (балансовых) неотрицательных переменных xn+i > 0:
В случае необходимости ограничение-равенство
можно записать в виде системы неравенств
Если в ЗЛП какая-то переменная xkне подчинена условию неотрицательности, ее заменяют разностью двух других неотрицательных переменных х'k > 0 и х"k > 0:
xk= х'k - х"k.