Использование линейного программирования для решения задач оптимизации (стр. 2 из 4)

Рассмотрим связь между геометрическим понятием крайней точки и его аналитической интерпретацией. Для ограниченного множества

, описанного с помощью системы неравенств

крайними точками являются решения невырожденных подсистем вида:

(1)

где

- некоторое подмножество индексов

и

и матрица, составленная из строк-векторов аⁱ, неособенная.

Обозначим единственное решение системы (3) через x. Предположим теперь, что существуют

и такие, что для Поскольку для

то, очевидно,

. В силу единственности решения (3) .

С другой стороны, если

-- крайняя точка, то можно обозначить через множество равенств

Обозначим через

матрицу, составленную из строк Если предположить, что , то существует нетривиальное нуль-пространство

2)

Выбирая

достаточно малым по норме, можно добиться того, что для вектор или

для

и

для достаточно малых

. Аналогично можно показать, что при этом и . Так как то получаем противоречие с определением крайней точки. Для направленного просмотра крайних точек допустимого многогранника применяют симплекс-метод, предложенный Дж. Данцигом и затем усовершенствованный многочисленными математиками. Основная идея метода заключается в разбиении множества переменных x = x₁, x₂, . . ., x_nна базисные и небазисные . Не умаляя общности, можно считать, что базисные переменные являются первыми в векторе x, т.е. x = (x^B, x^N ).

Система ограничений канонической формы задачи линейного программирования может быть соответственно переписана в виде:

(3)

Предположим, что матрица

имеет полный ранг, т.е. - невырожденная. Тогда из равенства (5) следует

4)

Целевая функция задачи ЛПР также может быть разбита на базисную и не базисную части:

Подстановка (6) дает

5)

Предположим, что мы находимся в некоторой начальной точке

со значением целевой функции

Каким образом можно уменьшить далее значение целевой функции? Из соотношения (5) следует, что для этого достаточно сделать положительными те компоненты вектора

, которым соответствуют отрицательные значения координат вектора модифицированных стоимостей

сохраняя при этом неотрицательность базисных переменных

.

Увеличение

может быть проделано различным образом, и за время существования симплекс-метода были проделаны многочисленные эксперименты по поиску наиболее эффективных стратегий увеличения

Здесь будет рассмотрена простейшая:

· среди компонент вектора

находится минимальная;

· соответствующая небазисная переменная

получает максимально возможное приращение, сохраняющее неотрицательность базисных переменных.

Поскольку при увеличении

-й компоненты вектор приобретает вид:

где

это -й орт, а -- степень увеличения этой переменной или шаг алгоритма, то модифицированный базисный вектор выражается следующим образом:

где

- -й столбец матрицы Шаг определяется при этом из условия:

Максимально возможное значение

определится при этом как

6)

Пусть

-- номер , на которой достигается минимум (6). Очевидно, что при этом

При этом говорят, что переменная

выводится из базиса (обращается в нуль), а переменная вводится в базис. Целевая функция при этом уменьшается на величину

Важную роль в теории симплекс-метода играет условие невырожденности, в котором предполагается полный ранг A_Bи строгая положительность базисного решения β. При этом λ > 0 и δcx < 0, то есть целевая функция уменьшается при переходе к новому базису.

Поскольку в задаче линейного программрования может быть лишь конечное число базисов, а на каждой итерации происходит уменьшение целевой функции, базисы не могут повторяться. Следовательно, после конечного числа итераций вектор модифицированных стоимостей станет неотрицательным, а это означает, что дальнейшее уменьшение целевой функции невозможно, т.е. будет получено одно из оптимальных решений.