Править]Алгоритм симплекс-метода

Править]Усиленная постановка задачи

Рассмотрим следующую задачу линейного программирования:

Править]Алгоритм симплекс-метода - student2.ru

Теперь поставим эту задачу в эквивалентной усиленной форме. Необходимо максимизировать Z, где:

Править]Алгоритм симплекс-метода - student2.ru

Здесь x — переменные из исходного линейного функционала, xs — новые переменные, дополняющие старые таким образом, что неравенство переходит в равенство,c — коэффициенты исходного линейного функционала, Z — переменная, которую необходимо максимизировать. Полупространства Править]Алгоритм симплекс-метода - student2.ru и Править]Алгоритм симплекс-метода - student2.ru в пересечении образуют многогранник, представляющий множество допустимых решений. Разница между числом переменных и уравнений даёт нам число степеней свободы. Проще говоря, если мы рассматриваем вершину многогранника, то это число рёбер, по которым мы можем продолжать движение. Тогда мы можем присвоить этому числу переменных значение 0 и назвать их «непростыми». Остальные переменные при этом будут вычисляться однозначно и называться «простыми». Полученная точка будет вершиной в пересечении соответствующих непростым переменным гиперплоскостей. Для того, чтобы найти т. н. начальное допустимое решение (вершину, из которой мы начнём движение), присвоим всем изначальным переменным x значение 0 и будем их считать непростыми, а все новые будем считать простыми. При этомначальное допустимое решение вычисляется однозначно : Править]Алгоритм симплекс-метода - student2.ru .

Править]Алгоритм

Теперь приведём шаги алгоритма. На каждом шаге мы будем менять множества простых и непростых векторов (двигаться по рёбрам), и матрица будет иметь следующий вид:

Править]Алгоритм симплекс-метода - student2.ru

где cB — коэффициенты вектора c соответствующие простым переменным (переменным xs соответствуют 0), B — столбцы Править]Алгоритм симплекс-метода - student2.ru , соответствующие простым переменным. Матрицу, образованную оставшимися столбцами обозначим D. Почему матрица будет иметь такой вид поясним в описании шагов алгоритма.

Первый шаг.

Выбираем начальное допустимое значение, как указано выше. На первом шаге B — единичная матрица, так как простыми переменными являются xs. cB — нулевой вектор по тем же причинам.

Второй шаг

Покажем, что в выражении Править]Алгоритм симплекс-метода - student2.ru только непростые переменные имеют ненулевой коэффициент. Заметим, что из выражения Ax+xs=bпростые переменные однозначно выражаются через непростые, так как число простых переменных равно числу уравнений. Пусть x ' — простые, а x ' ' — непростые переменные на данной итерации. Уравнение Ax+xs=b можно переписать, как Bx '+Dx ' '=b. Умножим его на Править]Алгоритм симплекс-метода - student2.ru слева: Править]Алгоритм симплекс-метода - student2.ru . Таким образом мы выразили простые переменные через непростые, и в выражении Править]Алгоритм симплекс-метода - student2.ru , эквивалентному левой части равенства, все простые переменные имеют единичные коэффициенты. Поэтому, если прибавить к равенству Править]Алгоритм симплекс-метода - student2.ru равенство Править]Алгоритм симплекс-метода - student2.ru , то в полученном равенстве все простые переменные будут иметь нулевой коэффициент — все простые переменные вида x сократятся, а простые переменные вида xs не войдут в выражение Править]Алгоритм симплекс-метода - student2.ru .

Выберем ребро, по которому мы будем перемещаться. Поскольку мы хотим максимизировать Z, то необходимо выбрать переменную, которая будет более всех уменьшать выражение

Править]Алгоритм симплекс-метода - student2.ru .

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

Третий шаг

Теперь необходимо понять, какая простая переменная первой обратится в ноль по мере увеличения входящей переменной. Для этого достаточно рассмотреть систему:

Править]Алгоритм симплекс-метода - student2.ru

При фиксированных значениях непростых переменных система однозначно разрешима относительно простых, поэтому мы можем определить, какая из простых переменных первой достигнет нуля при увеличении входящей. Эту переменную назовем выходящей. Это будет означать, что мы натолкнулись на новую вершину. Теперь входящую и выходящую переменную поменяем местами — входящая «войдёт» в простую, а выходящая из них «выйдет» в непростые. Теперь перепишем матрицу B и вектор cB в соответствии с новыми наборами простых и непростых переменных, после чего вернёмся ко второму шагу. x''

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

Наши рекомендации