 |
 |
 |
 |
|
 |
 |
17
Доказательство.
Ради простоты положим, что базисными векторами являются первые m столбцов матрицы A, т. е.
?={a
l
,
a²,...,a
m
}. Тогда утверждение теоремы 1.3 может быть переформулировано следующим образом:
Если существует такой n-мерный вектор
что x1 a¹ +х2 а² +...+x
k
a
k
=b, то х есть угловая точка множества D.
Проведем доказательство от противного, т. е. предположим, что рассматриваемый базисный план х
не является угловой точкой множества D. Тогда ее можно представить в виде выпуклой
комбинации
некоторых двух различных допустимых планов х¹ и х²:
x = ?x¹+(1-?)x², 0<?<1.
В координатной форме последнее утверждение означает
Поскольку последние (n - k) компоненты вектора х по предположению равны 0, а числа х
j
1
,
x
j
2
? 0
и ?,
(1
-? )>0, то эти же компоненты в векторах x1 и х2 также равны 0. Поэтому, с учетом допустимости
планов х¹ и х², можно утверждать, что
Вычитая из (1.15) (1.16), получим
Так как векторы а¹,
а²,...,а
k
— линейно независимы, то коэффициенты х¹1
–х²1 =0,..., х¹
k
–х²
k
=0, из
чего следует, что x¹ =х². Это противоречит предположению, что х¹ и х² являются различными угловыми
точками множества D. Следовательно, х не может быть представлен в виде выпуклой комбинации двух
точек D и по определению является угловой точкой данного множества.
Интересно отметить, что справедливо и обратное утверждение, которое приведем без доказательства:
Если х — угловая точка множества D, то она является допустимым базисным планом задачи (D, f).
В завершение параграфа необходимо отметить практическое значение установленной связи между
угловыми точками и допустимыми базисными решениями: она позволяет формализовать (и тем самым
существенно упростить) процесс перехода от одной угловой точки к другой.
1.4. СИМПЛЕКС-МЕТОД
1.4.1. Основные этапы симплекс-метода. Исходя из свойств линейных экстремальных задач,
рассмотренных в предыдущих параграфах, можно заключить, что на принципиальном уровне поиск их
решений сводится к последовательному перебору угловых точек множества допустимых планов или,
что то же самое, перебору соответствующих допустимых базисных планов. Следует подчеркнуть, что
такой перебор для реальных многомерных задач возможен только в теоретическом плане и на практике
неосуществим (или крайне неэффективен) даже при условии использования
мощной вычислительной
техники. Средством решения данной проблемы явились прикладные оптимизационные методы,