82
1. На плоскости
X
1
OX
2
строят прямые, уравнения которых получаются в
результате замены в ограничениях знаков неравенств на знаки точных равенств.
2. Находят полуплоскости, определяемые каждым из ограничений задачи.
3. Строят многоугольник решений.
4. Строят вектор
) , (
2 1
c
cN
, который указывает направление возрастания
целевой функции.
5. Строят начальную прямую целевой функции
c
1
x
1
+
c
2
x
2
= 0 и затем пе-
редвигают ее в направлении вектора
N
до крайней угловой точки многоуголь-
ника решений. В результате находят точку, в которой целевая функция прини-
мает максимальное значение, либо множество точек с одинаковым максималь-
ным значением целевой функции, если начальная прямая сливается с одной из
сторон многоугольника решений, либо устанавливают неограниченность свер-
ху функции на множестве планов
X
F
.
6. Определяют координаты точки максимум функции и вычисляют зна-
чение целевой функции в этой точке.
Минимальное значение линейной функции цели находится путем пере-
движения начальной прямой
c
1
x
1
+
c
2
x
2
= 0 в направлении, противоположном
вектору
) , (
2 1
c
c
N
.
Рассмотрим применение графического метода на примере задачи плани-
рования производства.
Компания производит два типа холодильников. Обе модели приносят
прибыль, причем модель
A
– 70 дол. за каждый холодильник, а модель
B
– со-
ответственно 60 дол. Для производства модели
A
требуется 3 человеко-часа, а
модели
B
– 2 человеко-часа. Общее количество человеко-часов не должно пре-
вышать 3000 в неделю. Далее, стоимость сырья для модели
A
составляет 50
долл., а для модели
B
– 60 дол. Потолок недельной сметы по сырью для этих
двух моделей составляет 75000 дол. Компания ставит своей целью максимиза-
цию прибыли.
Обозначим за
x
и
y
соответственно количество моделей холодильников
типа
A
и
B
, произведенных за неделю. Общее количество человеко-часов, необ-
ходимое для производства двух моделей, составляет 3
x
+ 2
y
. Общие затраты со-
ставят 50
x
+ 60
y
. Имеем систему ограничений:
3
x
+ 2
y
3000; 50
x
+ 60
y
75000.
Задача заключается в максимизации функции прибыли
L
= 70
x
+ 60
y
.
