Решение задач линейного программирования симплекс методом

 

 

 

 

Далее эта система оформляется  в виде симплекс-таблиц:

 

 

 

 

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

 

Порядок работы с симплекс таблицей

 

Первая симплекс-таблица  подвергается преобразованию, суть которого заключается в переходе к новому опорному решению.

 

Алгоритм перехода к следующей  таблице такой:

 

·просматривается последняя  строка (индексная) таблицы и среди  коэффициентов этой строки (исключая столбец свободных членов) выбирается наименьшее отрицательное число  при отыскании max, либо наибольшее положительное при задачи на min. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;

 

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

 

·среди выбранных коэффициентов  столбца выбирается тот, для которого абсолютная величина отношения соответствующего свободного члена (находящегося в столбце  свободных членов) к этому элементу минимальна. Этот коэффициент называется разрешающим, а строка в которой  он находится ключевой;

 

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

 

·разделим каждый элемент  ключевой строки (исключая столбец  свободных членов) на разрешающий  элемент и полученные значения запишем  в строку с измененной базисной переменной новой симплекс таблицы.

 

·строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу  на то же место.

 

·в новой таблице все  элементы ключевого столбца = 0, кроме  разрезающего, он всегда равен 1.

 

·столбец, у которого в  ключевой строке имеется 0, в новой  таблице будет таким же.

 

·строка, у которой в  ключевом столбце имеется 0, в новой  таблице будет такой же.

 

·в остальные клетки новой  таблицы записывается результат  преобразования элементов старой таблицы:

 

 

 

 

В результате получают новую  симплекс-таблицу, отвечающую новому базисному  решению.

 

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

 

Рассмотрим порядок решения  задачи с помощью симплекс-таблиц на примере.

 

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

 

Пусть задача линейного программирования задана в канонической форме, состоящей  из m независимых уравнений с n переменными (или же она приведена к такому виду после введения добавочных неотрицательных  переменных).

 

Выберем группу m основных переменных, которые позволяют найти исходное базисное решение (не нарушая общности, можем считать, что основными  переменными являются первые m переменных). Выразив эти основные переменные через неосновные, получим следующую  систему ограничений:

 

 

 

 

Этому способу разбиения  переменных на основные и неосновные соответствует базисное решение (k1, k2,…, km, 0, 0,…, 0). Рассмотрим общий случай, когда это решение является недопустимым. От полученного базисного решения следует сначала перейти к какому-нибудь допустимому базисному решению. Причем не обязательно, чтобы этот переход осуществлялся сразу, за один шаг.

 

По предположению исходное базисное решение недопустимо. Следовательно, среди свободных членов системы  ограничений (2.16) имеется хотя бы один отрицательный (число отрицательных  свободных членов этой системы совпадает  с числом отрицательных компонент  исходного базисного решения). Пусть  им является свободный член i-го уравнения ki, т.е. основная переменная xi в соответствующем базисном решении отрицательна.

 

Для перехода к новому базисному  решению необходимо: выбрать переменную, которую следует перевести из неосновных в основные; установить, какая основная переменная при этом перейдет в число неосновных переменных. При переводе неосновной переменной в основные ее значение, как правило, возрастает: вместо нуля в исходном базисном решении оно будет положительно в новом базисном решении (исключая случай вырождения). Вернемся к i-му уравнению системы (2.16), содержащему отрицательный свободный член k1. Оно показывает, что значение переменной xi растет при возрастании значений тех неосновных переменных, которые в этом уравнении имеют положительные коэффициенты. Отсюда следует, что в основные можно переводить те неосновные переменные, которые в уравнении системы (2.16) с отрицательным свободным членом имеют положительные коэффициенты.

 

Здесь может быть три исхода:

 

1.в i-м уравнении системы  (2.16) нет основных переменных с  положительными коэффициентами, т.е.  все коэффициенты bi, m+j (как и свободный член ki) отрицательны. В этом случае система ограничений несовместна, она не имеет ни одного допустимого решения, а следовательно, и оптимального;

 

2.в i-м уравнения имеется  одна переменная xm+j, коэффициент b при которой положителен. В этом случае именно эта переменная переводится в основные;

 

.в i-м уравнении имеется несколько переменных с положительными коэффициентами bi, m+j. В этом случае в основные можно перевести любую из них.

 

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

 

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

 

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

 

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

 

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

 

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

 

2. Алгоритм симплекс-метода

 

 

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

 

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

 

 

 

 

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

 

 

 

 

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

 

Алгоритм

 

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

 

 

 

 

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

 

Первый шаг

 

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

 

Второй шаг

 

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

 

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

 

 

.

 

 

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

 

Третий шаг

 

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

 

 

 

 

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

 

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

 

 

 

 

3. Двухфазный симплекс-метод

 

 

Причины использования

 

Если в условии задачи линейного программирования не все  ограничения представлены неравенствами  типа «?», то далеко не всегда нулевой  вектор будет допустимым решением. Однако каждая итерация симплекс-метода является переходом от одной вершины  к другой, и если неизвестно ни одной  вершины, алгоритм вообще не может быть начат.

 

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

 

Модификация ограничений

 

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

 

·ограничения типа «?»  переводятся на равенства созданием  дополнительной переменной с коэффициентом  «+1». Эта модификация проводится и в однофазном симплекс-методе, дополнительные переменные в дальнейшем используются как исходный базис.

 

·ограничения типа «?»  дополняются одной переменной с  коэффициентом «?1». Поскольку такая  переменная из-за отрицательного коэффициента не может быть использована в исходном базисе, необходимо создать ещё одну, вспомогательную, переменную. Вспомогательные  переменные всегда создаются с коэффициентом  «+1».