§ 7.4. графический метод решения задачи линейного программирования при малом числе переменных

§ 7.4. графический метод решения задачи линейного программирования при малом числе переменных

Графический метод решения задачи линейного программирования в его непосредственной форме применяется только в случае двух переменных. Выпуклая многогранная область X, заданная системой линейных ограничений для двух переменных, является выпуклой многоугольной областью. Ниже угловые точки X называются вершинами.

Пусть область допустимых решений X задается системой неравенств вида

аих + а]2У>Ьх , a2lx + а12у > Ь2 ,

amx + amly>bm,

целевая функция /= схх + с2^.Предположим, что требуется найти максимум (или минимум)/на множестве X, а также точку, в которой достигается этот максимум (или минимум).

При описании графического метода используется понятие линии уровня: линией уровня функции /{х, у) называется множество всех точек (х,у), в которых функция принимает некоторое постоянное значение а. В случае линейной функции^*,у) = СХ+С2У все линии уровня являются прямыми, перпендикулярными общему вектору нормали с = (с,; с^.

Графический метод состоит в следующем.

Строится множество X всех допустимых решений.

Если Х= 0, то задача неразрешима.

3. Если Х*0, то рассматриваются прямые уровня /=а при монотонном изменении а от -оо до +оо. При увеличении а прямая/= а смещается параллельно в направлении вектора с. Если А — первая точка встречи прямой уровня с областью X, ЛА) = а0, то прямая уровня Дх) = а при а < а0 не имеет общих

точек с X. Откуда следует, что а0 = min/ на X. Аналогичным образом, если А — последняя точка пересечения линии уровня с X, то j(A) = max /на X.

Если первой точки пересечения линии уровня с А" не существует (т. е. при всех а из некоторого промежутка вида [оо; а0] прямая

/= а пересекает X), то min /= <ю, и задача на минимум неразрешима. Если не существует последней точки пересечения, то max/= + оо, и задача на максимум неразрешима.

Таким образом, из чертежа всегда видно, разрешима задача или нет. Из чертежа также видно, имеются ли у допустимого множества вершины. Отметим сразу, что отсутствие вершины — явление довольно редкое. При ограниченной целевой функции допустимое множество X без вершины может быть только двух видов:

X— полуплоскость;

Х— область, ограниченная двумя параллельными прямыми.

Если у X есть хотя бы одна вершина, то (при ограниченной целевой функции) оптимальное значение может быть найдено методом перебора вершин (см. § 7.3). Для вычисления целевой функции в некоторой вершине V допустимого множества необходимо знать точное значение ее координат. Для определения координат вершины V решается система линейных уравнений вида

апх + ai2y = />,, ajXx + aj2y = bp

где / иу — номера прямых, ограничивающих область X, на пересечении которых находится вершина V.

Графический метод позволяет избежать полного перебора вершин. Действительно, если из чертежа видно, что А — единственная первая (или последняя) точка пересечения линии уровня с X, то незачем вычислять координаты других вершин, так как А — единственное оптимальное решение. Для некоторых задач, однако, из чертежа не ясно, в какой именно точке линия уровня пересекает в первый раз допустимое множество. В этом случае необходимо найти координаты всех «подозрительных» на оптимальность вершин, вычислить для них значения целевой функции и выбрать из них вершины с оптимальным значением. Заметим, что могут оказаться две оптимальные вершины АнВ. Тогда множество всех оптимальных решений X* — это отрезок АВ.

Пусть do = max / (или clq = min J) — оптимальное значение / на X

Множество всех оптимальных решений X * является подмножеством линии уровня / = а0, причем х' выпукло, так как задается системой линейных неравенств. Поэтому возможны лишь следующие случаи:

а) А'* — точка на прямой уровня/ = а0;

б) X * — отрезок на прямой уровня/= а0;

в) X * — луч, содержащийся в прямой/= а0;

г) X * совпадает с прямой уровня/= а0.

Рассмотрим теперь несколько примеров.

Пусть X — квадрат, стороны которого параллельны осям координат. Каждая из его вершин может быть как точкой максимума, так и точкой минимума в зависимости от того, в какой четверти находится вектор с (рис. 7.1-7.4).

О

max

A<c. 7.i

sal

mm

У *

О

mm

Л/с. 7.4

max

Решим графическим методом задачу о банке из § 7.1:

jc + ^ < 100;

х > 35;

>>>0,3(х + .у);

х > 0;

^>0;

/= 0,15х + 0,у-+ max.

Построим в плоскости х, у полуплоскости, заданные неравенствами 1)-5). Общая их часть (заштрихованный треугольник на рис. 7.5) — область Л'допустимых решений. Построим вектор с и прямую уровня, перпендикулярную вектору с и проходящую через начало координат. Перемещая эту прямую параллельно в направлении вектора с, найдем последнюю точку пересечения прямой уровня и допустимого множества X.

Найденная точка максимума находится на пересечении прямых 1 и 3. Ее координаты получаются путем решения следующей системы линейных уравнений:

х + у= 100, у = 0Хх+у).

Итак, оптимальный портфель активов (точка максимума) имеет структуру (х /) = (70, 30) .

Максимальная прибыль составит;

/max =Лх у) = 0,15 ■ 70 + 0,1 ■ 30 = 13,5.

Рассмотрим теперь случай трех переменных. Для функции J(x,y,z) аналогом линии уровня является поверхность уровня, т. е. множество всех точек трехмерного пространства, в которых функция J[x,y,z) принимает определенное значение. Для функции вида /= С|Дс + ctf + c^z всякая поверхность уровня — это плоскость с вектором нормали с = (С|,с2,С3). Теоретически графический метод можно применить и в трехмерном пространстве, заменив прямые уровня на плоскости уровня. На практике, однако, приходится иметь дело с плоскими чертежами, по которым трудно разобраться в характере взаимного расположения допустимого множества и плоскости уровня. Поэтому в следующем примере мы используем метод перебора вершин, применяя графические средства только для упрощения поиска угловых точек.

Рассмотрим производственную задачу с тремя продуктами П|, Я2, Я3 и тремя видами ресурсов Д|, R2, R$. Пусть

bi — количество доступных единиц ресурса Л, (і-1, 2, 3); Pj — цена продукта П} (j: = 1,2, 3);

fly — количество единиц ресурса Rit расходуемых на производство 1 ед. продукта IJj;

х, у, z — количество производимых единиц продуктов Я,, Я2, Я3 соответственно.

Приходим к задаче линейного программирования:

аих + а11у + а1гг<Ь], а21х + аггу + а1Ъг < Ь2,

агх + аггУ + аъъ2 ^з> x>0, y>0,z >0,

f=Pх +РіУ +p$z-> max.

Считаем, что все ресурсы при производстве продуктов только расходуются, а не производятся, т. е. я,у > 0. Кроме того, естественно предположить, что при производстве каждого продукта расходуется хотя бы один ресурс. Предположим для определенности, что при производстве каждого продуктаЯ7 расходуется ресурс Rj (и, возможно, другие ресурсы тоже). Тогда ах х > 0, я22 > 0 и д33 > 0. Учитывая неотрицательность а^, x,ynz, получаем неравенства

b bf b-i

х<—, у<—, z<—. au а22 а33

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

Пусть, например, Ь = (210, 210,300) и

(«,у) =

а числа/>і,/>2,Р3 конкретно не указаны. Грани Ft (і 1,2,6) допустимого многогранника Л'задаются следующими ограничениями:

Грань Fx: S, 2х + у + z = 210. Грань F2. S, х + 2у + г = 210. Грань Fy S, x + y + 2z = 300. Грань F4: S, х = 0. Грань F5: S, у = 0. Грань F6: S, z = 0.

Всякая вершина V многогранника X принадлежит каким-то трем его граням. Если вершина Кне принадлежит граням Fx, F2, Fit то она обязана принадлежать одновременно F4, F5, F6. Такая вершина только одна — О(0,0, 0). Таким образом, множество всех вершин многогранника X состоит из вершин граней Fx, F2, F2 и вершины О. Для каждой грани Fx,F2n Fy, используя единственное уравнение среди ограничений, задающих данную грань, выразим z через х и у и подставим полученное выражение во все остальные неравенства, задающие грань. В результате этих эквивалентных преобразований системы ограничений, задающих грани Fx,F2,Fb, примут следующий вид:

Грань F, Грань F2 Грань F3

z = 210-2х->/, 0)х-у<0, (1)Ъх + у< 120,

х-у>0, (2)z = 210-x-2y, (2) х + Ъу < 120,

0)Ъх + у> 120, (3)jc + 3^> 120, (3)z=150-0,5x-0,5j!,

х > 0, (4) х > 0, (4) х > 0,

>*>0, (5)^>0, {5)у>0,

2х + ^<210. (6)х + 2>><210. (6)х + у<Ш.

Используя неравенства (1), (3), (4), (5), (6) для F2, построим проекцию грани F2. И наконец, на основе неравенств (1), (2), (4), (5), (6) для F3 построим проекцию F3. Из рис. 7.6 видно, что грань Fi задается только неравенствами (2), (3), (5), (6). Поэтому к грани F} примыкают только грани F2, F3, F5, F6. Рис. 7.6 показывает, что вершинами грани F| являются следующие точки:

A=FinF2nF6, B = F{nF5nF6, С = F, П F3 П F5 , D = FlrF2nF3l.

Находим вершины грани F2: A, D, Е = F2 Г F4 Г F6, G = F2 П F3 П /"фзатем вершины^: С,Д (7 и Н = F3 П F4 Г> F5.

Заметим, что в проекции на плоскость х, у две вершины: Я и О слились в одну точку. Найдем координаты вершин.

Точка А, как вершина грани Fx, удовлетворяет системе линейных уравнений:

z = 2U-lx-y, (I) ■ х-у = 0, (2) 2х + / = 210. (6)

Отсюда Л =(70,70, 0). 154

z = 210-2x-j (1)

У = 0, (5) В = (105,0,0).

2x + j> = 210, (6)

Для остальных вершин грани Fx координаты находятся так:

В:

С:

z = 2lQ-2x-y, (I)

Зх + /=120, (3) С =(40, 0, 130).

^ = 0, (5)

D:

z = 2