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