ВУЗ:
Составители:
Рубрика:
138
а) б)
Рис. 7.10. Выпуклая (а) и невыпуклая (б) области решений
Опорной прямой называется прямая, которая имеет с областью решений,
по крайней мере, одну общую точку, при этом вся область расположена по одну
сторону от этой прямой (прямые
1
l
и
2
l
на рис. 7.10, а).
При геометрической интерпретации системы неравенств с тремя пе-
ременными каждое неравенство описывает полупространство, а вся система –
пересечение полупространств, т. е. многогранник, который также обладает
свойством выпуклости. Здесь опорная плоскость проходит через вершину, реб-
ро или грань многогранной области.
Основываясь на введенных понятиях, рассмотрим геометрический метод
решения задачи линейного программирования.
Пусть задана линейная целевая функция f = c
0
+ c
1
x
1
+ c
2
x
2
двух независи-
мых переменных, а также некоторая совместная система линейных неравенств,
описывающих область решений G.
Требуется среди допустимых решений (х
1
, х
2
) є G найти такое, при кото-
ром линейная целевая функция f принимает наименьшее значение.
Положим функцию f равной некоторому постоянному значению с: f = c
0
+
+ c
1
x
1
+ c
2
x
2
= c. Это значение достигается в точках прямой, удовлетворяющих
уравнению
c
0
+ c
1
x
1
+ c
2
x
2
= с. (107)
При параллельном переносе этой прямой в положительном направлении
вектора нормали )c,c(n
21
r
линейная функция f будет возрастать, а при переносе
прямой в противоположном направлении – убывать.
Предположим, что прямая, записанная в виде (107), при параллельном пе-
реносе в положительном направлении вектора
n
r
первый раз встретится с обла-
стью допустимых решений G в некоторой ее вершине, при этом значение целе-
вой функции равно с
1
, и прямая становится опорной. Тогда значение с
1
будет
минимальным, поскольку дальнейшее движение прямой в том же направлении
приведет к увеличению функции f.
L
2
L
1
A
1
B
1
G
1
A
2
B
2
G
2
Страницы
- « первая
- ‹ предыдущая
- …
- 138
- 139
- 140
- 141
- 142
- …
- следующая ›
- последняя »
