Численные методы оптимизации. Рейзлин В.И. - 64 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

64
7.4. Геометрическое толкование задач линейного программирования
Геометрический смысл основной задачи линейного программирования
становится предельно прозрачным, если перейти от нее к эквивалентной ей за-
даче с ограничениями-неравенствами, то есть к задаче (А):
Дана система
1
2
11 1 1 1
11
0,
0,
..........
0,
... 0,
.........................................
... 0,
k
kk
r rk k r
x
x
x
xx
xx
(7.22)
содержащая
n k r
линейных неравенств относительно
k
неизвестных
1
,...,
k
xx
, и линейная форма
0 1 1
...
kk
F x x
(7.20)
относительно тех же неизвестных. Требуется среди всех решений системы (7.22)
выбрать такое, которое минимизирует форму F.
Для большей наглядности геометрическому толкованию основной задачи
в общем случае предпошлем разбор задач 1–4.
Рассмотрим задачу 1 в форме (А), она имеет вид:
1
2
12
12
2
1
0,
0,
19 2 3 0,
13 2 0,
15 3 0,
18 3 0.
x
x
xx
xx
x
x


(3.23)
1 1 2
75F x x
.
Введем на плоскости прямоугольную декартову систему координат
12
x Ox
.
Известно, что геометрическое место точек на плоскости, координаты которых
удовлетворяют системе линейных неравенств, образует выпуклый многоуголь-
ник. Этот многоугольник называется многоугольником решений данной систе-
мы неравенств. Стороны этого многоугольника располагаются на прямых, урав-
нения которых получаются, если в неравенствах системы знаки неравенств за-
менить точными равенствами. Сам же этот многоугольник есть пересечение по-
луплоскостей, на которые делит плоскость каждая из указанных прямых. В
нашем случае такими прямыми являются

Страницы