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

 

Наиболее популярным универсальным алгебраическим методом решения ЗЛП является симплекс-метод, разработанный американским ученым Дж. Данцигом в 1949 г. [1]

Для того чтобы понять суть этого метода, рассмотрим сначала его геометрическую интерпретацию. Напомним определение выпуклого множества, играющего важную роль в линейном программировании.

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

Согласно этому определению, фигуры а и б на рис. 2.9 являются выпуклыми, а фигуры в и г – не являются таковыми.

 

 

Рис. 2.9

 

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

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

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

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

Аналогично, при n > 3 каждое неравенство а_{i 1} x ₁ + а_{i 2} x ₂ + …+ а_inx_n ≤ b_i, i = , определяет полупространство n- мерного пространства (в случае уравнения – гиперплоскость). Их пересечение также называют многогранником решений, и оно является выпуклым множеством.

Геометрическая интерпретация симплекс-метода состоит в следующем:

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

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

Для описания алгоритма симплекс-метода нам потребуется ряд определений.

Определение 2.4. Система линейных уравнений называется системой с базисом, если в каждом уравнении содержится неизвестное с коэффициентом, равным 1, отсутствующее в остальных уравнениях системы. Эти неизвестные называются базисными, остальные – свободными. Система с базисом имеет вид:

(2.3)

где р + m = n, т. е. p = n – m.

Система (2.3) всегда имеет решение (0, 0, , 0, b ₁, b ₂, , b_m). Оно называется базисным решением.

Определение 2.5. Систему линейных уравнений будем называть канонической, если она является системой с базисом и все b_i ≥ 0. Базисное решение в этом случае оказывается планом, т. к. его компоненты неотрицательны. Назовем его базисным (или опорным) планом канонической системы.

Определение 2.6. ОЗЛП будем называть канонической (КЗЛП) [2], если система линейных уравнений этой задачи – каноническая, а целевая функция выражена только через свободные неизвестные.

Пример 2.5. Рассмотрим систему ограничений ЗЛП из примера 2.1. Вводя дополнительные переменные, приведем ее к системе уравнений

(2.4)

при условии неотрицательности переменных x_i (i = ).

Эта система является канонической, переменные x ₃, x ₄, x ₅, x ₆ являются базисными, а переменные x ₁, x ₂ – свободными. Так как целевая функция f(x ₁, x ₂ ) = 3 x ₁ + 2 x ₂ выражена через свободные неизвестные, то мы получили КЗЛП.

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

 

f(x ₁, , x_n) = c ₀ – c ₁ x ₁ – − c_px_p (2.5)

 

на множестве планов канонической линейной системы (2.3).

Этой задаче соответствует следующая симплекс-таблица.

Таблица 2.2

 

Базис	х 1 х 2∙ ∙ ∙ хp хp+ 1 хp+ 2∙ ∙ ∙ хn	Значение
хр+ 1 хр+ 2 хn	а 11 а 12∙ ∙ ∙ а 1 p 1 0∙ ∙ ∙ 0 а 21 а 22∙ ∙ ∙ а 2 p 0 1 ∙ ∙ ∙ 0 аm 1 а 12∙ ∙ ∙ аmp 0 0∙ ∙ ∙ 1	b 1 b 2 bn
f	c 1 c 2∙ ∙ ∙ cp 0 0 ∙ ∙ ∙ 0	c 0

 

Последняя строка этой таблицы называется индексной. Она соответствует уравнению с ₁ x ₁ + c ₂ x ₂ + + c_px_p = с ₀ (это уравнение гиперплоскости, являющейся поверхностью уровня целевой функции). Именно по этой причине коэффициенты при неизвестных в целевой функции (2.5) удобно обозначать –c ₁, –c ₂, , –c_р.

Сформулируем теперь ряд теорем, которые лежат в основе симплекс-метода. Для определенности будем рассматривать задачу максимизации.

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

Доказательство. Пусть, например, среди коэффициентов при x ₁ есть положительные и . называется ключевым отношением. Пусть, например, . Элемент а ₁₁ называется тогда ключевым элементом. Используя метод Гаусса, исключим неизвестное х ₁ из всех уравнений, кроме первого. Для этого разделим первую строку на а ₁₁, а затем вычтем из каждой i -й строки первую, умноженную на а_{i 1} (i = ). Из индексной строки также вычтем первую, умноженную на с ₁. Получим следующую симплекс-таблицу:

 

Таблица 2.3

 

Базис	х 1	х 2	...	хp	хр +1	хp +2	...	хn	Значение
х 1			...				...
хр +2			...				...
хn			...				...
f			...				...

 

Теперь х ₁ – базисное неизвестное, а х_{р +1} – свободное. В последнем столбце все элементы положительны, т. е. табл. 2.3 соответствует канонической задаче. Действительно, для неположительных а_i1 (i = ) это очевидно, т. к. b_i ≥ 0 и . Для положительных а_i1 это следует из выбора : и, следовательно, , (i = ).

Теорема 2.2. (об улучшении базисного плана). Если в индексной строке симплекс-таблицы задачи максимизации содержится отрицательный элемент с_j, а в столбце х_j имеется хотя бы один положительный элемент, причем ключевое отношение ≥ 0, то возможен переход к равносильной канонической задаче с не хужим (а при > 0 – лучшим) базисным планом.

Доказательство. Пусть, например, с₁ < 0 и а ₁₁ > 0 – ключевой элемент. Тогда переход от таблицы 1 к таблице 2 меняет значение целевой функции с с ₀ на , т. к. с ₁ < 0, ≥ 0. При > 0 .

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

Доказательство. Пусть x_b = (0, …, 0, b ₁, …, b_m) – базисный план. Тогда f (x_b) = c ₀. Если
х = (х ₁, …, х_р, х_{р +1}, …, х_n) – произвольный план, то f (х) = c ₀ – c ₁ х ₁ – …– c_рх_р ≤ c ₀, т. к. c_i ≥ 0,
х_i ≥ 0, i = . Теорема доказана.

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

Доказательство. Пусть, например, с ₁ < 0 и а_{i 1} ≤ 0 при i = .

Рассмотрим вектор x _θ = (θ, 0, …, 0, b ₁- a ₁₁ θ, …, b_m – a_{m 1} θ). Легко проверить подстановкой, что θ R x_θ – решение системы (2.3). При θ > 0 это решение допустимое, т. к. b_i – a_{i 1} θ ≥ 0 при i = (b_i ≥ 0, а_{i 1} ≤ 0, θ > 0). f (x _θ ) = c ₀ – с ₁ θ → + ∞ при . Теорема доказана.

Теоремы 2.1–2.4 позволяют сформулировать алгоритм симплекс-метода для задачи максимизации КЗЛП.

1. Записываем данную КЗЛП в исходную симплекс-таблицу.

2. Если все элементы индексной строки симплекс-таблицы неотрицательны, то базисный план задачи является оптимальным (теорема 2.3).

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

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

а) выбираем в таблице ключевой столбец, в основании которого находится какой-либо отрицательный элемент индексной строки;

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

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

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

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

а) через конечное число шагов задача будет решена (возникнут ситуации пп. 2 или 3);

б) начиная с некоторого шага возникает зацикливание (периодическое повторение симплексных таблиц и базисных планов).

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

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

Пример 2.6. Решим симплекс-методом КЗЛП из примера 2.5. При этом добавим в симплекс-таблицу столбец, в который будем записывать отношения b_i к положительным элементам ключевого столбца.

Таблица 2.4

 

Базис	x 1	x 2	x 3	x 4	x 5	x 6	Значение	Отношение
x 3
x 4
x 5	–1							–
x 6								–
f	–3	–2
x 3		3/2		–1/2				4/3
x 1		1/2		1/2
x 5		3/2		1/2				10/3
x 6
f		–1/2		3/2
x 2			2/3	–1/3			4/3
x 1			–1/3	2/3			10/3
x 5			–1
x 6			–2/3	1/3			2/3
f			1/3	4/3

 

Последняя симплекс-таблица соответствует оптимальному решению, т. к. в индексной строке нет отрицательных элементов. Рассмотрим ее интерпретацию.

Столбец значений дает нам оптимальное решение: , и максимальное значение целевой функции . Значения переменных x ₅ = 3 и дают нам остатки ресурсов 3 и 4 (дополнительные переменные x ₅ и x ₆ соответствуют этим ресурсам), т. е. эти ресурсы являются недефицитными, и их запасы могут быть снижены на указанные значения без изменения оптимального решения (ср. табл. 2.1). Переменные x ₃ и x ₄ являются свободными, т. е. x ₃ = x ₄ = 0, и, соответственно, ресурсы 1 и 2 являются дефицитными. Индексная строка дает выражение для целевой функции: , откуда находим , . Из уравнений системы (2.4) следует, что увеличение x ₃ и x ₄ эквивалентны соответственно снижению запасов ресурсов 1 и 2. Поэтому коэффициенты 1/3 и 4/3 представляют собой ценности ресурсов 1 и 2 соответственно. Ценности ресурсов 3 и 4 равны 0, как видно из этой же индексной строки. Это и естественно, т. к. они недефицитные.

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

Определим интервал значений изменения какого-либо ресурса (например, 1-го), при котором его теневая цена остается неизменной. Увеличение запаса ресурса 1 на величину Δ соответствует замене переменной х ₃ в системе (2.4) на х ₃ – Δ. Делая ту же замену в последней симплекс-таблице, а затем перенося Δ в правую часть, получим столбец значений переменных: . Для того чтобы это решение было оптимальным, необходимо и достаточно, чтобы оно было допустимым, т. е.

 

 

Решая эту систему, находим . Аналогично находятся интервалы изменений запасов остальных ресурсов.

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

 

 

Так как из последней симплекс-таблицы имеем

 

и ,
то ,

 

т. е. новая индексная строка получается прибавлением к старой индексной строке строки, отвечающей x ₁, умноженной на Δ. Для того чтобы найденная точка оптимума для f осталась точкой оптимума для f ^*, нужно выполнение условий:

 

 

т. е. –2≤ Δ ≤ 1. Отсюда находим пределы изменения коэффициента c ₁ при x ₁ в целевой функции: 1≤ c ₁ ≤ 4 (т. к. c ₁ = 3 + Δ). Аналогично находится интервал изменения коэффициента при x ₂.

Пример 2.7. Решим симплекс-методом задачу примера 2.2. Вводя дополнительные переменные, приведем ее к ОЗЛП, которая будет и канонической:

f (x ₁, x ₂) = 6 x ₁ + 2 x ₂ → max,

 

Таблица 2.5

 

Базис	x 1	x 2	x 3	x 4	Значение	Отношение
x 3						4, 5
x 4
f	–6	–2
x 3
x 1
f

 

Последняя симплекс-таблица является оптимальной. Ей отвечает оптимальное решение x ₁ = 2, x ₂ = 0, f _max = 12. Это решение соответствует точке А на рис. 2.3. Нулевое значение коэффициента при свободной переменной x ₂ в индексной строке говорит о наличии альтернативного оптимума. Мы можем вывести переменную x ₃ из базиса, введя вместо нее переменную x ₂. При этом значение целевой функции не изменяется, но мы получим другое оптимальное решение (соответствующее точке В).

Пример 2.8. Решим симплекс-методом задачу примера 2.3, которая после введения дополнительных переменных принимает вид:

f (x ₁, x ₂) = x ₁ + x ₂ → max,

Мы получили систему с базисными переменными x ₁ и x ₄. Выразим целевую функцию через свободные переменные, найдя x ₁ = 1 + x ₂ + x ₃ из первого уравнения системы:

f = 1 + 2 x ₂ + x ₃.

Полученную КЗЛП запишем в симплекс-таблицу:

 

Базис	x1	x2	x3	x4	Значение
x1		–1	–1
x4
f		–2	–1

 

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

 

Мы рассмотрели алгоритм симплекс-метода применительно к КЗЛП. Однако не любая ОЗЛП является канонической. В таком случае от ОЗЛП переходят к канонической путем добавления искусственных переменных в каждое из уравнений системы, в котором отсутствует базисное неизвестное (предполагаем, что все b _i ≥ 0). В целевую функцию исходной задачи добавляется в случае максимизации слагаемое, представляющее собой произведение числа (–М) на сумму искусственных переменных, где М – достаточно большое положительное число. К полученной КЗЛП применяется симплекс-метод. При этом следует вычеркивать в симплекс-таблице искусственные переменные по мере их перехода в свободные. Если оптимальное решение содержит искусственные переменные в качестве базисных или задача неразрешима, то исходная задача также неразрешима. В противном случае мы получаем оптимальное решение исходной задачи. Описанный выше метод называется М-методом или методом больших штрафов.

Пример 2.9. Найти минимум целевой функции f (x ₁, x ₂) = 3 x ₁ – 2 x ₂ при условиях:

Вводя дополнительные переменные и переходя к задаче на максимум, приведем исходную задачу к ОЗЛП:

g (x ₁, x ₂) = –3 x ₁ + 2 x ₂ → max,

Базисная переменная имеется только в последнем уравнении. Для приведения к КЗЛП введем искусственные переменные y ₁, y ₂:

h (x, y) = –3 x ₁ + 2 x ₂ – M (y ₁ + y ₂) → max.

Выражая y ₁ и y ₂ из соответствующих уравнений системы и подставляя в выражение для h, получим h = – 3 x₁ + 2 x₂ – M( 3 – 2 x₁ + x₂ + x₃) –M ( 2 – x₁ – x₂ + x₄) = – 5 M + (3 M –3) x ₁ + 2 x ₂ –
– Mx ₃ – Mx ₄. Дальнейшее решение проводим в симплекс-таблицах.

Таблица 2.6

 

Базис								Значения	Отношения
		–1	–1						3/2
				–1
h	–3 M +3	–2	M	M				–5 M
		–1/2	–1/2					3/2
		3/2	½	–1			½	1/3
		5/2	1/2				9/2	9/5
h				M
			–1/3	–1/3			5/3
			1/3	–2/3		1/3
			–1/3	5/3		11/3
h			5/3	–1/3		–13/3

Продолжение таблицы 2.6

 

Базис								Значения	Отношения
			–2/5		1/5			12/5
			1/5		2/5	9/5
			–1/5		3/5	11/5
h			8/5		1/5	–18/5

 

Следовательно, f _min = 3, 6 при x ₁ = 2, 4, x ₂ = 1, 8.

 

Пример 2.10. Приведем модель из примера 2.4 к КЗЛП и решим ее симплекс-методом.

g = –2 x ₁ – 3 x ₂ – My ₁ → max.

Выражая y ₁ из первого уравнения, получим g = (M – 2) x ₁ + (М – 3) x ₂ – Mx ₃ – 10 М.

 

Таблица 2.7

 

Базис	x 1	x 2	x 3	x 4	y 1	Значения	Отношения
y 1			–1
x 4
g	2 – M	3 – M	M			–10 M
y 1		–2/3	–1	–1/3
x 1		5/3		1/3
g			M			–5 M –10

 

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