Наиболее важными формами задачи линейного программирования являются каноническая и стандартная.
В канонической форме задача является задачей на максимум (минимум) некоторой линейной функции F, ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи х1, х2, ..., хn являются неотрицательными:
a11x1+a12x2+...+a1nxn=b1
a21x1+a22x2+...+a2nxn=b2
............................
a11x1+a12x2+...+amnxn=bm
x1>=0, x2>=0,...,xn>=0
F=c1x1+c2x2+...+cnxn ->max(min)
К канонической форме можно преобразовать любую задачу линейного программирования.
Правило приведения ЗЛП к каноническому виду:
1. Если в исходной задаче некоторое ограничение (например, первое) было неравенством, то оно преобразуется в равенство, введением в левую часть некоторой неотрицательной переменной, при чем в неравенства «≤» вводится дополнительная неотрицательная переменная со знаком «+»; в случаи неравенства «≥» - со знаком «-»
a11x1+a12x2+...+a1nxn<=b1
Вводим переменную
xn+1=b1-a11x1-a12x2+...+a1nxn.
Тогда неравенство запишется в виде:
a11x1+a12x2+...+a1nxn +xn+1=b1
В каждое из неравенств вводится своя "уравнивающая” переменная, после чего система ограничений становится системой уравнений.
2. Если в исходной задаче некоторая переменная не подчинена условию неотрицательности, то ее заменяют (в целевой функции и во всех ограничениях) разностью неотрицательных переменных
Xk=Xk-Xl
Xk>=0, Xl>=0
l - свободный индекс
3. Если в ограничениях правая часть отрицательна, то следует умножить это ограничение на (-1)
4. Наконец, если исходная задача была задачей на минимум, то введением новой целевой функции F1 = -F мы преобразуем нашу задачу на минимум функции F в задачу на максимум функции F1.
Таким образом, всякую задачу линейного программирования можно сформулировать в канонической форме.
В стандартной форме задача линейного программирования является задачей на максимум (минимум) линейной целевой функции. Система ограничений ее состоит из одних линейных неравенств типа « = ». Все переменные задачи неотрицательны.
a11x1+a12x2+...+a1nxn=b1
a21x1+a22x2+...+a2nxn=b2
............................
a11x1+a12x2+...+amnxn=bm
F=c1x1+c2x2+...+cnxn ->max(min)
x1>=0, x2>=0,...,xn>=0
Всякую задачу линейного программирования можно сформулировать в стандартной форме. Преобразование задачи на минимум в задачу на максимум, а также обеспечение не отрицательности переменных производится так же, как и раньше. Всякое равенство в системе ограничений равносильно системе взаимопротивоположных неравенств:
ai1x1+ai2x2+...+ainxn=bi ai1x1+ai2x2+...+ainxn<=bi
-ai1x1-ai2x2-...-ainxn<=bi
Существует и другие способы преобразования системы равенств в систему неравенств, т.е. всякую задачу линейного программирования можно сформулировать в стандартной форме.
