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

Дополнительные переменные сообщают, насколько соответствующее им ограничение «недоиспользовано». Значение дополнительной переменной, равное нулю, соответствует равенству значений правых и левых частей ограничения.

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

То есть ненулевое значение дополнительной переменной может (но не должно) сигнализировать о неоптимальности решения. Ненулевое значение вспомогательной переменной сигнализирует о недопустимости решения.

После того, как было модифицировано условие, создаётся вспомогательная  целевая функция. Если вспомогательные  переменные были обозначены, как yi, i{1, .., k}, то вспомогательную функцию определим, как.

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

Когда будет найдено оптимальное  значение вспомогательной целевой  функции, могут возникнуть две ситуации:

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

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

Для реализации двойственного  метода необходимо перейти от задачи на минимум к задаче на максимум путем транспонирования матрицы  коэффициентов.

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

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

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

В полученной задаче первоначальный опорный план очевиден. При применении к этой задаче симплекс-метода оценки теперь будут зависеть от числа М. Для сравнения оценок нужно помнить, что М – достаточно большое положительное число, поэтому из базиса будут выводиться в первую очередь искусственные переменные.

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

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

Табличный симплекс метод - для его применения необходимо, чтобы знаки в ограничениях были вида «меньше либо равно», а компоненты вектора b - положительны.

Алгоритм решения сводится к следующему:

• приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам;
• если в исходной системе ограничений присутствовали знаки «равно» или «больше либо равно», то в указанные ограничения добавляются;
• искусственные переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума;
• формируется симплекс-таблица;
• рассчитываются симплекс - разности;
• принимается решение об окончании либо продолжении счёта;
• при необходимости выполняются итерации.

На каждой итерации определяется вектор, вводимый в базис, и вектор, выводимый из базиса. Таблица пересчитывается  по методу Жордана - Гаусса или каким-нибудь другим способом.

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

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

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

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

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

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

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

Таким образом, алгоритм симплекс-метода состоит  из следующих этапов:

• находят начальный базис и связанное с ним допустимое базисное решение;
• вычисляют симплекс - разность для каждой переменной, не входящей в базисное решение;
• вводят в базис наиболее «выгодную» переменную с максимальной положительной симплексом - разностью;
• ее значение rmax определяют из соотношения для всех соответствующих коэффициентов > 0;
• выводят из базисного решения соответствующую переменную;
• переходят ко второму этапу составления новой таблицы;
• при переходе на новую таблицу, то выше перечисленные этапы повторяют до тех пор, пока симплекс - разности для всех переменных, не входящих в базис, не станут отрицательными.

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

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

1.2 Общая идея  симплексного метода

Общая идея симплексного метода (метода последовательного улучшения плана) для решения задач линейного программирования (ЗЛП) состоит:

• умение находить начальный опорный план;
• наличие признака оптимальности опорного плана;
• умение переходить к не худшему опорному плану.

Пусть ЗЛП представлена системой ограничений в каноническом виде:

(1.1)

Говорят, что ограничение  ЗЛП имеет предпочтительный вид, если при неотрицательной правой части левая часть ограничений содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения равенства - с коэффициентом, равным нулю.

Пусть система ограничений  имеет вид

(1.2)

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

(1.3)

которая имеет предпочтительный вид

(1.4)

В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю

 Пусть далее система ограничений имеет вид

(1.5)

Сведём её к эквивалентной вычитанием дополнительных переменных

(i=1,..,m) из левых частей неравенств системы. Получим систему

(1.6)

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

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

Пусть исходная ЗЛП имеет вид:

(1.7)

причём ни одно из ограничений  не имеет предпочтительной переменной. М-задача запишется так:

1.8)

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

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

Теорема: Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т.е. ее условия несовместны.

Признаки оптимальности.

Теорема: Пусть исходная задача решается на максимум. Если для некоторого опорного плана все оценки (j=) неотрицательны, то такой план оптимален.

Теорема: Если исходная задача решается на минимум и для некоторого опорного плана все оценки (j=) неположительные, то такой план оптимален.

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

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

	(1.9)
	(1.10)
	(1.11)
	(1.12)

Симплекс-метод применяется  к задачам, приведенным к каноническому виду и состоит из двух частей:

• 1 я часть – построение опорного плана;
• 2 я часть – улучшение полученного опорного плана до оптимального.

Опорное решение будет  найдено, если будут выполнены два условия: