Курсовая работа: Использование линейного программирования для решения задач оптимизации
то, очевидно, 
. В силу единственности решения (3) 
.
С другой стороны, если 
-- крайняя точка, то можно обозначить через 
множество равенств
Обозначим через 
матрицу, составленную из строк 
Если предположить, что 
, то существует нетривиальное нуль-пространство
2)
Выбирая 
достаточно малым по норме, можно добиться того, что для 
вектор 
или 
для 
и 
для достаточно малых 
. Аналогично можно показать, что при этом и 
. Так как 
то получаем противоречие с определением крайней точки. Для направленного просмотра крайних точек допустимого многогранника применяют симплекс-метод, предложенный Дж. Данцигом и затем усовершенствованный многочисленными математиками. Основная идея метода заключается в разбиении множества переменных x = x 1 , x 2 , . . ., xn на базисные 
и небазисные 
. Не умаляя общности, можно считать, что базисные переменные являются первыми в векторе x, т.е. x = ( xB , xN ) .
Система ограничений канонической формы задачи линейного программирования может быть соответственно переписана в виде:
(3)
Предположим, что матрица 
имеет полный ранг, т.е. - невырожденная. Тогда из равенства (5) следует
4)
Целевая функция задачи ЛПР также может быть разбита на базисную и не базисную части:
Подстановка (6) дает
5)
Предположим, что мы находимся в некоторой начальной точке 
со значением целевой функции
Каким образом можно уменьшить далее значение целевой функции? Из соотношения (5) следует, что для этого достаточно сделать положительными те компоненты вектора 
, которым соответствуют отрицательные значения координат вектора модифицированных стоимостей
сохраняя при этом неотрицательность базисных переменных 
.
Увеличение 
может быть проделано различным образом, и за время существования симплекс-метода были проделаны многочисленные эксперименты по поиску наиболее эффективных стратегий увеличения 
Здесь будет рассмотрена простейшая:
· среди компонент вектора 
находится минимальная;
· соответствующая небазисная переменная 
получает максимально возможное приращение, сохраняющее неотрицательность базисных переменных.
Поскольку при увеличении 
-й компоненты вектор приобретает вид: