В общем виде задача линейного программирования* (в дальнейшем ЗЛП) может быть сформулирована как задача нахождения наибольшего значения линейной функции
на некотором множестве D Ì Rn, где х Î D удовлетворяют системе ограничений
и, возможно, ограничениям
х 1 ≥0, х 2 ≥0,..., хj ≥0,..., хn ≥0. (1.3)
* Напомним, что частные примеры, сводящиеся к задаче линейного программирования, были описаны во введении.
Не умаляя общности, можно считать, что в системе (1.2) первые m ограничений являются неравенствами, а последующие — l -уравнениями. Очевидно, этого всегда можно добиться за счет простого переупорядочения ограничений. Относительно направления знака неравенства будем предполагать, что левая часть меньше или равна правой. Добиться этого можно, умножив на (-1) обе части тех неравенств, которые имеют противоположный знак. Ограничения (1.3), вообще говоря, могут быть рассмотрены как частный случай ограничений в форме неравенств, но в силу особой структуры их обычно выделяют отдельно и называют условиями неотрицательности (или тривиальными ограничениями).
|
|
Дополнительно следует заметить, что выбор типа искомого экстремума (максимума или минимума) также носит относительный характер. Так, задача поиска максимума функции
эквивалентна задаче поиска минимума функции
Часто условия задачи (1.1)-(1.3), содержащей ограничения только типа неравенств, бывает удобно записывать в сокращенной матричной форме
f(x) = сх → max, Ax ≤ b, х ≥ 0, (1.6)
где с и х — векторы из пространства Rn, b — вектор из пространства Rm, а А — матрица размерности m х n.
Задачу линейного программирования, записанную в форме (1.1)-(1.3), называют общей задачей линейного программирования (ОЗЛП).
Если все ограничения в задаче линейного программирования являются уравнениями и на все переменные хj наложены условия неотрицательности, то она называется задачей линейного программирования в канонической форме, или канонической задачей линейного программирования (КЗЛП). В матричной форме КЗЛП можно записать в следующем виде:
Поскольку любая оптимизационная задача однозначно определяется целевой функцией f и областью D, на которой отыскивается оптимум (максимум), будем обозначать эту задачу парой (D, f).
Условимся относительно терминологии, которая используется в дальнейшем и является общепринятой в теории линейного программирования.
Планом ЗЛП называется всякий вектор х из пространства Rn.
Допустимым планом называется такой план ЗЛП, который удовлетворяет ограничениям (1.2)-(1.3), т. е. содержится в области D. Сама область D называется при этом областью допустимых планов. Оптимальным планом х* называется такой допустимый план, при котором целевая функция достигает оптимального (в нашем случае — максимального) значения, т. е. план, удовлетворяющий условию
|
|
max f(x) = f(x*).
Величина f* =f(х*) называется оптимальным значением целевой функции.
Решением задачи называется пара (х*, f*), состоящая из oптимального плана и оптимального значения целевой функции, а процесс решения заключается в отыскании множества всех решений ЗЛП.
1.1.2. Переход к канонической форме. Подавляющее большинство известных методов решения задач линейного программирования предназначены для канонических задач. Поэтому начальный этап решения всякой общей задачи линейного программирования обычно связан с приведением ее к некоторой эквивалентной канонической задаче.
Общая идея перехода от ОЗЛП к КЗЛП достаточно проста:
Ø Ø ограничения в виде неравенств преобразуются в уравнения за счет добавления фиктивных неотрицательных переменных хi, (i Î 1 :m), которые одновременно входят в целевую функцию с коэффициентом 0, т. е. не оказывают влияния на ее значение;
Ø Ø переменные, на которые не наложено условие неотрицательности, представляются в виде разности двух новых неотрицательных переменных:
- = - =
хj = хj – хj, (xj ≥ 0, хj ≥ 0 ).
Проиллюстрируем применение описанных выше рекомендаций на примере. Пусть задана задача линейного программирования (D, f) в общей форме с целевой функцией
f(x) = 5 х 1 + 3 x 2 + x 3 + 2 х 4 -2 х 5 → max
и множеством допустимых планов D, определенным системой уравнений и неравенств,
2 х 1 | + 4 х 2 | + 5 x 3 | =7, | |
- 3 x 2 | + 4 x 3 | – 5 x 4 – 4 x 5 | ≤ 2, | |
3 х 1 | - 5 x 3 | + 6 x 4 – 2 x 5 | ≤ 4, | |
х 1≥ 0, | x 3 | ≥ 0. |
Тогда в соответствии со сформулированными правилами эквивалентная каноническая задача будет иметь вид (D',f'), где:
а множество D' определено как:
Нетрудно заметить, что «платой» за переход от общей формы задачи линейного программирования к канонической является рост ее размерности, что, при прочих равных условиях, является фактором, усложняющим процесс решения.