2015-01-30
354
Пусть требуется найти неотрицательные значения переменных Х1, Х2, …, Хn, для которых функция цели принимает максимальное значение
f(x) = C1 Х1 + C2Х2 + …+ CnХn ® max
при ограничениях
а11Х1 + а12Х2 + …+ а1nХn £ b1,
а21Х1 + а22Х2 + …+ а2nХn £ b2,
………………………………..
аm1Х1 + аm2Х2 + …+ аmnХn £ bm,
Хj ³ 0, (j = 
).
Поскольку в ограничениях левая часть меньше, чем правая (или равна ей), чтобы перейти к строгому равенству, необходимо к левой части каждого неравенства добавить соответствующую переменную.
Найти максимум функции цели
f(x) = C1 Х1 + C2Х2 + …+ CnХn + …+ 0×Хn+1 + …+ 0×Хn+m ® max
при ограничениях
а11Х1 + а12Х2 + …+ а1nХn + Хn+1 = b1,
а21Х1 + а22Х2 + …+ а2nХn + Хn+2 = b2,
……………………………………………….
аm1Х1 + аm2Х2 + …+ аmnХn + Хn+m = bm,
Хj ³ 0, (j = 
).
Пример. Записать следующую задачу в канонической форме:
f(x) = –X1 + 2X2 – X3 + X4® min,
3X1 – X2 + 2X3 + 2X4 £ 10,
X1 + 2X2 + X3 – X4 ³ 8,
2X1 – X2 – X3 + X4 £ 6,
–X1 + 3X2 + 5X3 – 3X4 = 15,
Xj ³ 0, (j = 1 ¸ 4).
Для записи задачи в канонической форме поменяем знаки у всех коэффициентов функции цели на противоположные. Тогда задача будет заключаться в нахождении максимума целевой функции. Для приведения ограничений – неравенств к системе уравнений необходимо приравнять левые и правые части ограничений путем введения дополнительных переменных. Если левая часть ограничения меньше, чем правая, необходимо добавить дополнительную переменную, если же левая часть ограничения больше, из нее следует вычесть некоторое, пока неизвестное, значение.
|
|
|
f(x) = Х1 – 2Х2 + Х3 – Х4 + 0×Х5 + 0×Х6 + 0×Х7 ® max,
3X1 – X2 + 2X3 + 2X4 + X5 = 10,
X1 + 2X2 + X3 – X4 – X6 = 8,
2X1 – X2 – X3 + X4 + X7 = 6,
–X1 + 3X2 + 5X3 – 3X4 = 15,
Xj ³ 0.
Свойства задачи линейного программирования:
1. Множество планов задачи линейного программирования, если оно не пусто, образует выпуклый многогранник. Любая точка внутри области, ограниченной этим многогранником, является допустимым решением задачи.
2. В одной из вершин многогранника решений целевая функция принимает максимальное значение (при условии, что функция ограничена сверху на множестве планов).
3. Если максимальное значение функция принимает более, чем в одной вершине, то это же значение она принимает в любой точке, являющейся выпуклой линейной комбинацией данных вершин.
