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

Будем рассматривать задачу линейного программирования в канонической форме (2.1)-(2.3).

Выразим целевую функцию через свободные переменные:

(2.6)

или

, (2.7)

где , – исходный план задачи (2.1)-(2.3), , – симплекс-разности, которые рассчитываются по следующей формуле:

, . (2.8)

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

,

а в последней строке записаны симплекс-разности целевой функции в точке .

Таблица 2.1 Общий вид симплекс таблицы

			…		…
			…		…
			…		…
…	…	…	…	…	…	…	…
			…		…
…	…	…	…	…	…	…	…
			…		…
			…		…

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

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

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

Таким образом, если в точке выполняются условия теоремы 3 или теоремы 4, то решение задачи (2.1)-(2.3) на этом завершается. Если же для точки выполнены условия теоремы 5, то совершается переход от к новому допустимому базисному решению , для которого увеличивается. Затем в точке анализ коэффициентов задачи повторяется, и на основании теорем 3‑5 делается одно из трех возможных заключений и т.д. Так как число допустимых базисных решений задачи (2.1)-(2.3) не превосходит , то случай, описанный в теореме 5, может повторяться лишь конечное число раз. Поэтому в результате конечного числа шагов перехода к новому допустимому базисному решению задача будет решена или будет установлена ее неразрешимость.

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

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

1. Канонический вид задачи линейного программирования.

2. Все коэффициенты правых частей системы ограничений неотрицательны ( , ).

3. Наличие базиса, то есть среди векторов , должно быть единичных.

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

Шаг 1. Составляем симплекс-таблицу и рассчитываем симплекс-разности по формуле (2.8).

Шаг 2. Определяем знак симплекс-разностей:

· если все , , то получен оптимальный план;

· если существуют , , то переходим к шагу 2.

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

Шаг 4. Определяем знак элементов ключевого столбца:

· если все , то неограничена ( );

· если , то переходим к шагу 5.

Шаг 5. Определяем ключевую строку. Ключевой строкой называется строка, в которой отношение минимально при условии, что . Пусть минимум достигается при , строка с номером называется ключевой (разрешающей), а элемент – ключевой элемент.

Шаг 6. Переходим к новой симплекс-таблице и новому базису, выводя из него неизвестный , заменяя его на известный . Изменение базиса означает переход к новому плану. Элементы новой симплекс-таблицы вычисляются следующим образом:

, .

Переходим к шагу 1.

Замечание:

1. Если выполняется в нескольких точках, то в качестве ключевого элемента можно выбрать любой из них.

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

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: