Автоматизация технологического проектирования. Смирнов О.Л. - 21 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

21
ее от начала координат. В ней
достигается наибольшее значе-
ние целевой функции при со-
блюдении условий (25).
Для обхода вершин симплек-
са необходимо преобразовать
неравенства в равенства введе-
нием дополнительных перемен-
ных. Целевая функция y пере-
именовывается в x
0
и записы-
вается
01 2
13
124
125
26
20;
7;
315;
9;
4
xx x
xx
xxx
xxx
xx
−− =
+=
++=
++=
+=
(26)
в виде равенства в системе (26) вместе с неравенствами (25), преобра-
зованными в равенства введением в каждое по одной положительной
дополнительной переменной. Геометрический смысл дополнительных
переменных x
3
, ..., x
6
становится понятным при взгляде на точку L на
рис. 4. Значения x
3
, ..., x
6
есть расстояния от точки L до прямых BC, CD,
DE и EF. Если одно из них равно нулю, то точка L лежит на соответ-
ствующей прямой, если два смежных расстояния равны нулю, то точка
L лежит в вершине симплекса, на пересечении прямых, которым при-
надлежит точка L. Отсюда следует важный вывод: нулевые значения
пары дополнительных переменных, соответствующих смежным ребрам,
определяют вершину симплекса, из которой эти ребра исходят. Назовем
такую пару переменных с нулевыми значениями базисом, хотя обще-
принято называть базисом совокупность остальных переменных с не-
нулевыми значениями.
Из рис. 4 видно, что вершинам A, B, C, D, E, F соответствуют бази-
сы (x
1
, x
2
), (x
1
, x
6
), (x
6
, x
4
), (x
4
, x
5
), (x
5
, x
3
), (x
3
, x
2
). В 3-мерном простран-
стве базисом будет совокупность нулевых значений трех переменных, а
в N-мерном – N переменных.
1
2
3
B
x
2
x
1
x
3
x
5
x
4
x
6
C
D
E
F
L
H
G
A
2 3 6 7
Рис. 4. Графическое решение задачи
линейного программирования

Страницы