Методы решения задач линейного программирования

Симплекс-метод

Сведём задачу линейного программирования к просмотру крайних точек допустимого множества. Именно направленный перебор крайних точек допустимого множества и осуществляется в симплекс-методе, изложенном ниже.

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

 

 

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

 (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, то есть целевая функция уменьшается при переходе к новому базису.

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

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

Геометрический метод

 

 

Рассмотрим задачу линейного программирования в стандартной форме с двумя переменными (n = 2). К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных n больше числа уравнений m на 2, т. е. n – m = 2.

Пусть геометрическим изображением системы ограничений является многоугольник ABCDE (рис. 1). Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция F=c₁x₁+c₂x₂ принимает максимальное (или минимальное) значение.

Рассмотрим так называемую линию уровня линейной функции F, т. е. линию вдоль которой эта функция принимает одно и тоже значение a, т.е. F = a, или

 

c₁x₁+c₂x₂ = а (1)

 

линии уровня широко используются, например, на картах прогноза погоды, где извилистые линии – так называемые изотермы есть ничто иное, как линии уровня температуры Т = с. Ещё более простым примером линий уровня являются параллели на географической карте. Это линии уровня широты.

Предположим надо найти самую северную точку какой-либо области, например страны или материка. Это будет точка, имеющая наибольшую широту, т. е. точка через которую проходит параллель (линия уровня) с самой большой широтой (уровнем).

Именно так и надо поступать при геометрическом решении задач линейного программирования . на многоугольнике решений следует найти точку, через которую проходит линия уровня функции F с наибольшим (если линейная функция максимизируется) или наименьшим (если она минимизируется) уровнем.

Уравнение линии функции (1) есть уравнение прямой линии. При различных уровнях а

Линии уровня параллельны, так как их угловые коэффициенты определяются только соотношением между коэффициентами c₁ и c₂ и следовательно, равны. Таким образом, линии уровня функции F – это своеобразные “параллели ”, расположенные обычно под углом к осям координат.

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

Пусть имеются три линии уровня :

 

F=c₁x₁ + c₂x₂ = а₁ (I)

F=c₁x₁ + c₂x₂ = а₂ (II)

F=c₁x₁ + c₂x₂ = а₃ (III)

 

Причём линия II заключена между линиями I и III. Тогда а₁ < а₂ < а_{3 и} а₁ > а₂ > а_3.

В самом деле, на штриховой линии (перпендикулярной к линиям уровня на рис. 2) уровень является линейной функцией, а значит, при смещении в одном направлении возрастает, а в другом – убывает.

 

 

Для определения направления возрастания рекомендуется изобразить две линии уровня и определить, на какой них уровень больше. Например, одну из линий взять проходящей через начало координат (если линия функция имеет вид F=c₁x₁ + c₂x₂, т. е. без свободного члена, то это соответствует нулевому уровню). Другую линию можно провести произвольно, так, например, чтобы она проходила через множество решений системы ограничений. Далее найдём точку, в которой функция принимает максимальное значение, подобно тому как на карте находится самая северная или самая южная точка (на рис. 1 – это точка С или А).