Алгоритм графического метода

1. Построить область допустимых решений.

2. Построить вектор-градиент целевой функции =(с₁;с₂).

3. Построить семейство линий уровня, перпендикулярных вектору-градиента и проходящих через область допустимых решений.

4. Определить угловые точки, через которые проходит наиболее удаленная в направлении градиента линия уровня (в задаче на минимум – в направлении, противоположном градиенту).

5. Найти координаты точек экстремума и значение целевой функции в этих точках.

Пример2. Найти f(x)=(3 x₁+4 x₂)→ extr

при ограничениях

g1: 2 x₁+ x₂ ≥ 10

g2: x₁+ x₂ ≤ 15

g3: x₁- 3x₂ ≤ -2

g4: 3 x₁- 2x₂ ≥ -10

x₁ ≥ 0, x₂ ≥ 0

Решение.

1. Область допустимых решений представляет собой выпуклый четырехугольник ABCD.

2. Строим вектор-градиент =(3;4) и перпендикулярно ему линии уровня L_i, проходящие через область. Через точку С проходит наиболее удаленная в направлении градиента линия уровня, а через точку А – ближайшая. Следовательно, точки А и С являются соответственно точками минимума и максимума функции. Так как точка А лежит на пересечении прямых g1 и g3, то для нахождения её координат надо решить систему из уравнений этих прямых, то есть

2 x₁+ x₂ = 10

x₁- 3x₂ = -2

Получим х_min = (4,2), f_min =20. Аналогично находим координаты точки максимума (точки С) х_мах = (4;11), f_мах = 56.

Дата добавления: 2014-01-07