2.2. Понятие о симплекс-методе

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

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

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

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

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

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

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

Пример 2.3:

f(x) = 12x₁ + 15x₂  max

Приводим к канонической форме:

f(x) = 12x₁+15x₂ +0x₃+0x₄+0x₅

Среди переменных задачи можно выделить базисные переменные x₃, x₄, x₅ и не базисные x₁, x₂.

Не базисные те, которые можно приравнять к 0, а остальные базисные.

Приравняв не базисные переменные к 0, получим исходный базисный план:

Значение целевой функции для этого плана f(x) = 0 (прибыль равна нулю)

Данная ситуация не может удовлетворить предприятие, и, тем более, не является оптимальной.

f(x)= 0-(-12x₁-15x₂)  max

Анализируя функцию f можно сделать вывод, что увеличение значения функции (дохода) может произойти только при возрастании значений х₁ и x₂, отсюда увеличение х₁ или x₂ равносильно переходу переменных в число базисных.

В первую очередь увеличиваем значение x₂ , так как единица продукции Р₂ приносит больший доход. Значение х_1, по-прежнему, равно 0 , значение x₂ нельзя увеличивать бесконечно, то есть увеличиваем до тех пор, пока х₃, x₄ и x₅ ≥ 0. Значит, необходимо определить значение x₂, до которого можно его увеличивать:

Для выполнения данных условий необходимо чтобы x₂=5, так как данное значение получилось из 3-го ограничения, то, выразив x₂ через x₁ и x₅, мы заменим (введем) переменную x₂ в число базисных вместо x_5.

Подставим выражение x₂ в целевую функцию и оставшиеся ограничения по x₃ и x₄:

В этом случае новый базисный план после первой итерации будет:

f(x) = 75

На основании результатов можно сделать вывод, что полученный план не является оптимальным, так как значение целевой функции может быть увеличено за счет увеличения значения x₁ (x₅ мы не можем увеличивать, так как это приведет к снижению f).

Значение x₁ также нельзя увеличивать бесконечно, а только до такой величины, чтобы x₃,x₄,x₂ ≥ 0:

- из первого ограничения.

x₁ выразим из 1-го ограничения:

,

В этом случае новый базисный план после второй итерации будет:

f(x)=84

После анализа значения f следует, что данный план является оптимальным так как х₃ и х₅ , то на основании оптимального плана (f* = 84, x₁* = 2 x₂* = 4) делаем вывод, что предприятие для получения максимального дохода, равного 84 единицы должно выпускать из имеющегося количеств сырья 2 ед. продукции Р₁ и 4 ед. продукции Р₂.

Пример 2.4:

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

Приводим к канонической форме:

			х2
						(1) (4)
				(3)
					(2)
							х1

рис . 2.2

.

1) Среди переменных задачи можно выделить базисные переменные x₃, x₄, x₅, x₆ и не базисные x₁, x₂.

Приравняв не базисные переменные к 0, получим исходный базисный план:

В первую очередь увеличиваем значение x₁ , т.к. единица продукции P₁ приносит больший доход. Значение х₂, по-прежнему, равно 0, однако значение x₁ нельзя увеличивать бесконечно, т.е. увеличиваем до тех пор, пока х₃, x₄, x₅ и x₆ ≥ 0. Значит, необходимо определить значение x₁, до которого можно его увеличивать.

Для выполнения данных условий необходимо чтобы x₁=11, т.к. данное значение получилось из четвертого ограничения, то, выразив x₁ через x₂ и x₆, мы введем переменную x₁ в число базисных вместо x₆.

Подставим выражение x₁ в целевую функцию и оставшиеся ограничения по x₃ , x₄ и x₅.

2) В этом случае новый базисный план после первой итерации будет:

.

На основании результатов можно сделать вывод, что полученный план не является оптимальным, т.к. значение целевой функции может быть увеличено за счет увеличения значения x₂ (x₆ мы не можем увеличивать т.к. это приведет к снижению значения целевой функции).

Значение x₂ нельзя увеличивать бесконечно, т.е. увеличиваем до тех пор, пока х₃, x₄, x₅ и x₁ ≥ 0.

Выразив x₂ через x₅ и x₆, мы введем переменную x₂ в число базисных вместо x₅.

Подставим выражение x₂ в целевую функцию и оставшиеся ограничения по x₃ , x₄ и x₁.

3) В этом случае новый базисный план после второй итерации будет:

.

Полученный план не является оптимальным, т.к. значение целевой функции может быть увеличено за счет увеличения значения x₆ (x₅ мы не можем увеличивать т.к. это приведет к снижению значения целевой функции).

Значение x₆ увеличиваем до тех пор, пока х₃, x₄, x₂ и x₁ ≥ 0.

Выразив x₆ через x₄ и x₅, мы введем переменную x₆ в число базисных вместо x₄.

Подставим выражение x₆ в целевую функцию и оставшиеся ограничения по x₃ , x₂ и x₁.

4) В этом случае новый базисный план после третьей итерации будет:

После анализа значения f следует, что данный план является оптимальным т.к. все .

Ответ: