Составители:
Рисунок 9.8 Выпуклая G
1
и не выпуклая G
2
области
Областью решений системы неравенств является пересечение конечного числа полуплоскостей, описываемых
каждым отдельным неравенством. Это пересечение представляет собой многоугольную область G. Она может
быть как ограниченной, так и неограниченной и даже пустой (если система неравенств противоречива).
Область решений G обладает важным свойством выпуклости. Область называется выпуклой, если произволь-
ные две ее точки можно соединить отрезком, целиком принадлежащим данной области. На Рисунок 9.8
Выпуклая G1 и не выпуклая G2 области показаны выпуклая область G
1
и невыпуклая область G
2
. В области
G
1
, две ее произвольные точки A
1
и B
1
можно соединить отрезком, все точки которого принадлежат
области G
1
. В области G
2
можно выбрать такие две ее точки А
2
и В
2
, что не все точки отрезка А
2
В
2
принадлежат области G
2
.
Опорной прямой называется прямая, которая имеет с областью по крайней мере одну общую точку, при этом
вся область расположена по одну сторону от этой прямой. На Рисунок 9.8 Выпуклая G1 и не выпуклая G2
области показаны две опорные прямые l
1
и l
2
, т. е. в данном случае опорные прямые проходят соответственно
через вершину многоугольника и через одну из его сторон.
Аналогично можно дать геометрическую интерпретацию системы неравенств с тремя переменными. В этом
случае каждое неравенство описывает полупространство, а вся система — пересечение полупространств, т. е.
многогранник, который также обладает свойством выпуклости. Здесь опорная плоскость проходит через
вершину, ребро или грань многогранной области.
Основываясь на введенных понятиях, рассмотрим геометрический метод решения задачи линейного
программирования. Пусть заданы линейная целевая функция f = с
о
+ c
1
x
1
+ с
2
х
2
двух независимых
переменных, а также некоторая совместная система линейных неравенств, описывающих область решений G.
Требуется среди допустимых решений (x
1
, x
2
)
∈
G найти такое, при котором линейная целевая функция f
принимает наименьшее значение.
Положим функцию f равной некоторому постоянному значению С: f = с
о
+ c
1
x
1
+ с
2
х
2
= С. Это значение дости-
гается, в точках прямой, удовлетворяющих уравнению
.
22110
Cxcxcc
=
+
+
(9.27)
При параллельном переносе этой прямой в положительном направлении вектора нормали n(c
1
, c
2
) линейная
функция f будет возрастать, а при переносе прямой в противоположном направлении — убывать.
Предположим, что прямая, записанная в виде (9.27), при параллельном переносе в положительном
направлении вектора n первый раз встретится с областью допустимых решений G в некоторой ее вершине,
при этом значение целевой функции равно С
1
и прямая становится опорной. Тогда значение
1
c
!!!
(9.28)!!!
будет минимальным, поскольку дальнейшее движение прямой в том же направлении приведет к увеличению
значения f.
Если в задаче оптимизации нас интересует максимальное значение целевой функции, то параллельный
перенос прямой (9.27) осуществляется в направлении, противоположном n, пока она не станет опорной.
Тогда вершина многоугольника G, через которую проходит опорная прямая, будет соответствовать
максимуму функции f. При дальнейшем переносе прямой целевая функция будет убывать.
Таким образом, оптимизация линейной целевой функции на многоугольнике допустимых решений
происходит в точках пересечения этого многоугольника с опорными прямыми, соответствующими данной
целевой функции. При этом пересечение может быть в одной точке (в вершине многоугольника) либо в
бесконечном множестве точек (на ребре многоугольника).
В заключение вернемся к рассмотренной ранее транспортной задаче (см. п. 2). На Рисунке 9.9 изображен
многоугольник ABCDEF допустимых решений. Он получен как пересечение полуплоскостей, описываемых
неравенствами (9.23). Опорная прямая U соответствует уравнению 9.25 при f=22.9. Точка А пересечения
опорной прямой с многоугольником решений дает минимум целевой функции.
Страницы
- « первая
- ‹ предыдущая
- …
- 140
- 141
- 142
- 143
- 144
- …
- следующая ›
- последняя »
