Методы оптимальных решений. Страницы 3-4

Каждое неравенство в системе ограничений определяет полуплоскость, причем эта полуплоскость содержит точку, координаты которой удовлетворяют соответствующему строгому неравенству.

Построим нормальный вектор целевой функции n = (4, 2). Его направление указывает направление возрастания целевой функции L(X ) = 4x + 2y.

Прямая с уравнением 4x + 2y = 0представляет собой «нулевую» линию уровня функции  L =4x+2y. Эта прямая проходит через начало координат и перпендикулярна нормальному вектору n = (4, 2). Передвигаем эту прямую параллельно себе, или перпендикулярно n = (4, 2), и фиксируем два ее крайних положения.

Эти крайние прямые, которые обозначим буквами p и q , должны иметь с границей G либо общую вершину, либо общий отрезок, причем направление от p к q совпадает с направлением n = (4, 2). В рассматриваемом примере p проходит через точку A, а q – через точку B. Эти прямые называются соответственно нижней и верхней опорными прямыми для G.

Определим координаты точек A и B. На рис. видим, что точка A является точкой пересечения прямых 1) и 2), а B – 1) и 3).

A

-x+3y=9 → y=x/3+3

2x+3y=18→y=-2x/3+6

 

X=3

y=x/3+3=4

L(A) = 4*3+ 2*4=20

B

-x+3y=9 → y=x/3+3

2x-y=10→ y=2x-10

 

 

X=7,8

y=x/3+3=7.8/3+3=5,6

L(B  ) = 4*7,8+ 2*5,6=42,4 – это максимум L

 

Решить задачу при дополнительном условии (ДУ):

ДУ: Найти минимум целевой функции L=2x+3y при тех же ограничениях