Математическое программирование и моделирование экономических процессов. Коробов П.Н. - 96 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

96
Докажем теперь обратное утверждение теоремы. Пусть точка Х
0
=
[
]
00
2
0
1
,...,,
n
xxx
является вершиной области М. Допустим противное, что точка Х
0
не является одним из
опорных решений системы (2.2.124). Тогда, изменяя, если это нужно, нумерацию
неизвестных, можно считать, что первые k ≤ m положительных координат
[
]
00
2
0
1
,...,,
k
xxx точки Х
0
будут связаны с линейно зависимым набором векторов А
1
, А
2
,…, A
k
,
и поэтому существуют числа
λ
1
,
λ
2
,…,
λ
k
, не все равные нулю, такие, что
.0...
2211
=+++
kk
AAA
λλλ
(2.2.126)
Так как точка Х
0
принадлежит области М, то имеем тождество (2.2.125).
Умножая равенство (2.2.126) на произвольное число t и складывая его почленно с
равенством (2.2.125), получим
(
)
(
)
(
)
....
0
22
0
211
0
1
BAtxAtxAtx
kkk
=++++++
λλλ
Так как числа
00
2
0
1
,...,,
k
xxx положительны, то и числа
kk
txtxtx
λλλ
+++
0
2
0
21
0
1
,...,,
при достаточно малом t положительны.
Взяв два таких значения t, отличающихся друг от друга знаками, t=
ε
и t= -
ε
,
получим две точки:
[
]
[ ]
,0,...,0,0,,...,,
;0,...,0,0,,...,,
0
2
0
21
0
12
0
2
0
21
0
11
kk
kk
xxxX
xxxX
ελελελ
ελελελ
−−−=
+++=
принадлежащие области М, для которых точка Х
0
является выпуклой комбинацией:
Х
0
=(1-
λ
)Х
1
+
λ
Х
2
при
λ
= 1/2,
т. е. не является вершиной области М.
Полученное противоречие показывает, что любая вершина области М должна
являться одним из опорных решений системы (2.2.124). Теорема полностью доказана.
Геометрический смысл задачи линейного программирования
Было показано, что всякая разрешимая задача линейного программирования может
быть представлена в эквивалентной стандартной форме. В начале обратимся к
стандартной задаче максимизации целевой функции с тремя переменными:
z=сx
1
+ c
2
x
2
+ c
3
x
3
(2.2.127)
при условиях:
≤+++
≤+++
≤+++
,...
...............................................
;...
;...
332211
2323222121
1313212111
mmmm
bxaxaxa
bxaxaxa
bxaxaxa
(2.2.128)
.0,0,0
321
≥≥≥ xxx (2.2.129)
Система неравенств (2.2.128)—(2.2.129) определяет в прямоугольной системе
координат 0 х
1
, х
2
, х
3
некоторый выпуклый многогранник М (рассматривается случай
ограниченной области). Неравенства (2.2.129) показывают, что эта область М
расположена в первом октанте.
Рассмотрим далее целевую функцию (2.2.127). При каждом фиксированном
значении параметра z = a уравнение (2.2.127) определяет в пространстве некоторую
плоскость, которая называется плоскостью уровня целевой функции (2.2.127). Совокуп-
ность всех плоскостей уровня образует семейство параллельных плоскостей,

Страницы