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

Основным численным методом решения ЗЛП является так называемый симплекс-метод. В настоящее время теоретические и вычислительные аспекты этого метода хорошо разработаны. Симплекс-метод находит широкое применение при решении разнообразных задач линейного программирования. Наряду с этим он используется в численных методах нелинейной и дискретной оптимизации как вспомогательный инструмент для решения возникающих задач линейного программирования.

Следует отметить, что сам термин “симплекс-метод” не отражает существа этой вычислительной процедуры. Он связан с тем историческим обстоятельством, что первоначально метод был разработан применительно к ЗЛП, допустимое множество которой имело вид Х = { x Î R ⁿ | x ₁ + x ₂ + … + x_n = 1, x_i ³ 0, i = 1, …, n } (это множество именуется стандартным симплексом). В литературе данный метод называют также методом последовательного улучшения плана.

Симплекс-метод предназначен для решения ЗЛП в канонической форме.

f (x) = c ₁ x ₁ + c ₂ x ₂ +... + c_n x_n ® min, (3.8)

a_{i 1} x ₁ + a_{i 2} x ₂ +_… + a_in x_n = b_i, i = 1, 2, _…, m, (3.9)

x_j ³ 0, j = 1, …, n. (3.10)

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

Запишем систему равенств (3.9) в матричной форме

Ax = B, (3.11)

полагая, что

Обозначим через А ₁, …, А_n столбцы матрицы А, т. е.

Тогда систему (3.11) можно записать в виде

А ₁ x ₁ + A ₂ x ₂ + … + A_n x_n = b. (3.12)

В дальнейшем без ограничения общности мы можем полагать, что число уравнений задающих множество Х, меньше или равно числу переменных задачи (m £ n). Действительно, если это не так, то либо система уравнений Ах = b несовместна (и, значит, множество Х пусто), либо содержит избыточные (линейно зависимые) уравнения. Соотношение (3.12) является ни чем иным, как разложением вектора b по векторам А_i, i = 1, 2, …, n, а x_i – коэффициентами этого разложения. Такое разложение получило название второй геометрической интерпретации ЗЛП. Если некоторые m столбцов А_{j 1}, A_{j 2}, …, A_jm матрицы А линейно независимы, то они образуют базис в пространстве R ^m, и вектор b представим в виде их линейной комбинации.

Определение 3.7. Точка x ⁽⁰⁾ = (x ₁⁽⁰⁾, …, x_n ⁽⁰⁾) называется опорной точкой допустимого множества Х, если существуют номера j ₁, …, j_m, 1 £ j_k £ n, такие, что система векторов A_{j 1}, …, A_jm линейно независима и

x_jk ⁽⁰⁾ ³ 0, k = 1, 2, …, m, x_s ⁽⁰⁾ = 0, если s ¹ j_k.

Система векторов { A_{j 1}, …, А _jm} называется базисом опорной точки (х ⁽⁰⁾), а переменные x_{j 1}, …, x_jm - базисными переменными.

Переменные, которые не входят в список базисных переменных, называются небазисными или свободными.

Понятие опорной точки является одним из фундаментальных понятий теории линейного программирования. Следующая теорема трактует понятие опорной точки в терминах первой геометрической интерпретации ЗЛП. Сформулируем ее без доказательства.

Теорема 3.2. Каждая опорная точка является угловой точкой допустимого множества Х.

Если среди базисных переменных нет равных нулю, то опорная точка x ⁽⁰⁾ называется невырожденной, в противном случае - вырожденной опорной точкой. Соответственно, если среди опорных точек ЗЛП нет вырожденных, то она называется невырожденной, в противном случае – вырожденной задачей линейного программирования.

Основная идея и алгоритм симплекс-метода. Исходя из свойства ЗЛП, рассмотренных в предыдущем параграфе, можно заключить, что на принципиальном уровне поиск ее решений сводится к последовательному перебору угловых точек допустимого множества или, что тоже самое, перебору соответствующих опорных точек. Следует подчеркнуть, что такой перебор для реальных многомерных задач крайне не эффективен даже при условии использования мощной вычислительной техники, ибо при больших n и m он требует огромной вычислительной работы.

Итак, метод полного перебора опорных точек практической ценности не имеет. Но он естественным образом подводит к основной идее симплекс-метода: полный перебор заменяется упорядоченным, при котором осуществляется переход от текущей опорной точки только к тем опорным точкам, в которых значение целевой функции меньше, чем в текущей. В самом деле, если уже вычислена некоторая опорная точка х, то нет необходимости просматривать те опорные точки, в которых целевая функция принимает большее значение, чем в х: они заведомо не могут быть решением задачи. Несмотря на то что при таком переборе возврат к однажды просмотренным опорным точкам уже невозможен, теоретически не исключается (и такие примеры существуют), что в процессе решения будут пройдены все опорные точки допустимого множества Х. Однако большой практический опыт показал, что для подавляющего числа канонических ЗЛП количество итераций находится в пределах от m до 2 m.

Приступим к более детальному описанию симплекс-метода применительно к невырожденной канонической ЗЛП.

Пусть известна некоторая опорная точка х ⁽⁰⁾ = (х ₁⁽⁰⁾,..., х_n ⁽⁰⁾) допустимого множества задачи (3.8)-(3.10). Предположим, что столбцы матрицы А образуют базис угловой точки x ⁽⁰⁾, а переменные являются базисными переменными. Решая систему уравнений (3.9) относительно переменных и исключая базисные переменные из целевой функции, приходим к следующей ЗЛП, эквивалентной первоначальной задаче: минимизировать функцию

(3.13)

при условиях

(3.14)

............................

x_i ³ 0, i = 1, 2,..., n.

Так как x ⁽⁰⁾ - невырожденная опорная точка, то k = 1, 2,..., m. Функцию f ₁(x), будем называть приведенным (к небазисным переменным) выражением для целевой функции f (x), а коэффициенты - оценками соответствующих свободных переменных k = m+ 1, …, n.

Дальнейшая стратегия определяется основной теоремой симплекс-метода, которую мы приведем без доказательства.

Теорема 3.3. Если после выполнения очередной итерации в опорной точке x ⁽⁰⁾:

1) все оценки окажутся неотрицательными, т. е. для всех k = m+ 1, …, n, то x ⁽⁰⁾ - решение задачи (3.8)-(3.10);

2) существует номер j_r, m+ 1 £ r £ n такой, что и все i = 1, 2, …, m, то целевая функция f (x) неограниченно убывает на допустимом множестве (3.9), (3.10), то есть задача (3.8)-(3.10) не имеет решения;

3) найдется номер j_r, m+ 1 £ r £ n, такой, что , но среди коэффициентов есть положительные числа то можно перейти к другой опорной точке x ⁽¹⁾, в которой f (x ⁽¹⁾) £ f (x ⁽⁰⁾).

Третий случай означает, что решение ещё не достигнуто и необходимо выполнить следующую итерацию. Действительно, так как x ⁽⁰⁾ - опорная точка, то k = m+ 1, …, n, и f ₁(x ⁽⁰⁾) = f (x ⁽⁰⁾) (см.(3.13)). Структура допустимого множества задачи (3.8)-(3.10) такова, что оно обязательно содержит хотя бы одну точку x, у которой j_r -я координата строго положительна, а координаты при k = m +1, …, n, k ¹ r, равны нулю. Тогда из (3.13) вытекает, что f (x) = f ₁(x) £ f (x ⁽⁰⁾). Значит f (х ⁽⁰⁾)не является минимумом f (x) на допустимом множестве (3.9), (3.10).

Следующая итерация включает в себя переход от х ⁽⁰⁾ к новой опорной точке х ⁽¹⁾ и проверку последней на оптимальность. Для такого перехода мы вводим в список базисных переменных в точке х ⁽⁰⁾ новую базисную переменную m+ 1 £ r £ n, выбирая ее из тех свободных переменных, которые входят в приведенное выражение f ₁(x) с отрицательным коэффициентом, и выводим из списка переменную определяя номер j_l с помощью положительных коэффициентов при в (3.14). А именно, выбираем номер j_l из условия

(3.15)

По условию, рассматриваемая задача невырожденная, а поэтому условие (3.15) определяет единственное число j_l. Переменные будут новыми базисными переменными. Элемент называют разрешающим элементом, а j_l – e уравнение системы (3.14) - разрешающим уравнением. Исключим с помощью разрешающего уравнения переменную из функции f ₁(x) и всех других уравнений системы (3.14).

Для этого применяется простой приём - преобразование Жордана-Гаусса (или метод полного исключения). В данном случае он состоит в том, что мы должны “заработать” единицу на месте разрешающего элемента и нули на месте коэффициентов при в остальных уравнениях. Первое достигается посредством деления разрешающего уравнения на , второе - путём прибавления вновь полученного j_l -го уравнения, умноженного на подходящий коэффициент, к остальным уравнениям (3.14). Правые части получившейся при этом системы уравнений определяют положительные координаты новой опорной точки х ⁽¹⁾. Приведённое выражение для функции f (x) примет вид:

Используя теорему 3.3, проверяем точку х ⁽¹⁾ на оптимальность по оценкам и при необходимости делаем следующую итерацию по той же схеме применительно к вновь полученной задаче для f ₂(x).

Замечание 1. Вообще говоря, индекс j_r в третьей части теоремы 3.3. определяется неоднозначно. Другими словами, приведённое выражение (3.13) для функции f (x) может содержать несколько отрицательных оценок На практике обычно выбирают наименьшую из них.

Замечание 2. В условии (3.15) возможны два случая: a = 0 или a > 0. При a = 0 имеем х ⁽⁰⁾ = х ⁽¹⁾, т. е. происходит лишь замена одного базиса точки х ⁽⁰⁾ другим. При a > 0 заведомо х ⁽⁰⁾ ¹ х ⁽¹⁾и f (х ⁽¹⁾) < f (х ⁽⁰⁾). Если точка х ⁽⁰⁾ невырожденная, то обязательно a > 0. Но для вырожденной точки х ⁽⁰⁾ случай a = 0 не исключается. Таким образом, для вырожденной задачи возможна ситуация, когда итерации описанной процедуры сведутся к перебору базисов одной и той же опорной точки, не являющейся решением; причем с некоторого момента эти базисы начнут повторяться, так как число их конечно. В таком случае говорят, что произошло зацикливание симплекс-метода. Это явление возможно, когда в системе (3.2)-(3.3) имеются несущественные ограничения. Однако большой практический опыт показал, что при решении реальных ЗЛП, многие из которых вырождены, зацикливание встречается крайне редко: если даже в процессе вычислений некоторая опорная точка повторяется, то, как правило, рано или поздно обнаруживается такой ее базис, который позволяет перейти к новой опорной точке.

3. Пример решения ЗЛП симплекс-методом. Рассмотрим на конкретном примере процесс решения канонической ЗЛП симплекс-методом. Пусть дана задача

f (x) = 4 x ₁ - 5 x ₂ - x ₃ - 3 x ₄ - 5 x ₅® min; (3.16)

X: -x ₁ + 3 x ₂ + 2 x ₄ + x ₅ = 5,

-x ₁ +3 x ₂ + x ₃ + 3 x ₄ + 2 x ₅ = 9, (3.17)

-3 x ₁ + 2 x ₂ + x ₃ + 2 x ₄ + x ₅ = 6,

x_i ³ 0, i = 1, …, 5.

Начнем поиск решения с точки х ⁽⁰⁾ = (0, 0, 1, 2, 1). Убедимся в том, что х ⁽⁰⁾ - опорная точка допустимого множества Х. Для этого проверим, являются ли столбцы матрицы системы (3.17)

линейно независимыми. Как известно из аналитической геометрии, три вектора в R³ линейно независимы, если составленный из них определитель не равен нулю. В нашем случае

Итак, х ⁽⁰⁾действительно является опорной точкой. Ее базис - А ₃, А ₄, А ₅, а базисные переменные - х ₃, х ₄, х ₅.

Первая итерация. Решая систему уравнений (3.17) относительно базисных переменных и исключая их из функции f (x), получим задачу:

f ₁(x) = -12 + 18 x ₁ - 5 x ₂ ® min

при условиях

-2 х ₁ - х ₂ + х ₃ = 1,

-3 х ₁ + 2 х ₂ + х ₄ = 2, (3.18)

5 х ₁ - х ₂ + х ₅ = 1.

Как видно, в приведенном выражении f ₁(x) имеется одна отрицательная оценка ­­-5 при переменной х ₂.Последнее означает согласно теореме 3.3, что опорная точка х ⁽⁰⁾ не является решением задачи (3.16)-(3.17). Среди коэффициентов при переменной х₂ в системе (3.18) есть один положительный. Он находится в уравнении, содержащем базисную переменную х ₄. Значит, можно перейти к другой опорной точке.

Вторая итерация. Мы вводим в список базисных переменных новую переменную х ₂, а выводим из него – х ₄. Теперь базисными являются переменные х ₂, х ₃, х ₅. Второе уравнение системы (3.18) будет разрешающим уравнением системы. Исключим с помощью преобразования Жордана-Гаусса переменную х₂ из других уравнений системы. На этом этапе удобнее оперировать не с самой системой (3.18), а с ее расширенной матрицей

Разделим вторую строку матрицы на 2. Это даст

Прибавим вторую строку к первой, затем - к третьей. Будем иметь

Итак, мы приходим к системе уравнений

-3, 5 x ₁ + x ₃ + 0, 5 x ₄ = 2,

-1, 5 x ₁ + x ₂ + 0, 5 x ₄ = 1, (3, 19)

3, 5 x ₁ + x ₄ + x ₅ = 2,

и новой опорной точке х ⁽¹⁾ = (0, 1, 2, 0, 2).

Теперь исключим базисную переменную х ₂ из функции f ₁(x). Для этого выразим из второго уравнения системы (3.19) переменную х ₂ и подставим в f ₁(x), после чего приведенное выражение для f (x) примет вид

f ₂(x) = -17 + 10, 5 x ₁ + 2, 5 x ₄.

Так как все коэффициенты функции f ₂(x)неотрицательны, то точка х ⁽¹⁾ является решением задачи (3.16)-(3.17).

Ответ: х * = (0, 1, 2, 0, 2), f _min = -17.

4. Нахождение начальной опорной точки и М -метод. Одним из достоинств симплекс-метода является возможность его применения для определения начальной опорной точки х ⁽⁰⁾ = (х ₁⁽⁰⁾, …, х_n ⁽⁰⁾) многогранного множества Х, заданного условиями (3.9), (3.10). Соответствующий алгоритм носит название метода искусственного базиса. Рассмотрим вспомогательную задачу: минимизировать функцию

g (x) = x_{n +1} + x_{n +2} + … + x_n+m

при ограничениях

a_{i 1} x ₁ + … + a_inx_n + x_n+i = b_i, i = 1, …, m, (3.17)

x_k ³ 0, k = 1, …, n + m, (3.18)

где b_i, a_ik, i = 1, …, m, k = 1, …, n, те же что и в условиях (3.9), (3.10). Так как g (x) ограничена снизу, эта задача всегда имеет решение. По условию все b_i ³ 0, поэтому переменные x_{n +1}, …, x_n+m можно принять за базисные переменные, точка (0, …, 0, b ₁, …, b_m) является угловой точкой многогранного множества (3.17), (3.18). Применяя симплекс-метод, находим точку ` х ⁽⁰⁾ = (х ₁⁽⁰⁾, …, х_n ⁽⁰⁾, х_{n +1}⁽⁰⁾, …, х_n+m ⁽⁰⁾), минимизирующую функцию g (x) при ограничениях (3.17), (3.18). Положим g _min=a. Справедлива

Лемма 3.4. Если a = 0, то х ⁽⁰⁾ = (х ₁⁽⁰⁾, …, х_n ⁽⁰⁾) - опорная точка множества Х. Если a > 0, то допустимое множество Х пусто.

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

h (x) = c ₁ x ₁ + … + c_nx_n + M (x_{n+ 1} + … + x_n+m) (3.19)

при ограничениях (3.17), (3.18) и начальной угловой точке (0, …, 0, b ₁, …, b_m). Решение задачи (3.8)-(3.10) этим методом опирается на следующее утверждение.

Лемма 3.5. Если разрешима каноническа задача (3.8)-(3.10), то существует такое число М ₀ > 0, что для всех М ³ М ₀ в любом решении ` х* = (х <sub>1</sub>*, …, х<sub>n</sub> *, x * <sub>n +1</sub>, …, x * <sub>n+m</sub>) задачи (3.17)-(3.19) точка х* = (х <sub>1</sub>*, …, х<sub>n</sub> *) будет решением задачи (3.8)-(3.10), причем f (x*) = h (` x*).

На практике достаточно взять за М произвольное число, превышающее абсолютную величину любого коэффициента функции (3.8) и условий (3.9).