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

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

Симплекс-метод, впервые разработал Г.Данциг в 1947 г, данный метод известен также под названием метода последовательного улучшения плана. Его суть заключается в последовательном переборе угловых точек области допустимых решений, а алгоритмы позволяют установить, является ли данная ЗЛП разрешимой.

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

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

1. Если ЗЛП имеет канонический вид, то можно выразить первые m переменных через остальные, используя, например, метод Гаусса.

Например:

max Z = 2x₁ + 3x₂ – x₃

Можно свести к виду:

max Z = 2x₁ + 3x₂ – x₃

х₁ и х₂ – базисные переменные, х₃ – свободная.

Опорный план следующий: Х^* = (11,5; 14; 0)

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

Например:

max Z = x₁ – x₂

Предпочтительный вид будет следующий:

max Z = x₁ – x₂ + 0∙x₃ + 0∙x₄

х₃ и х₄ – базисные переменные, х₁ и х₂ – свободные.

Опорный план следующий: Х^* = (0; 0| 5; 4)

Вертикальная черта отделяет исходные переменные задачи от введенных.

3. Сведением к М-задаче. А именно, необходимо ввести искусственный базис (v_s): переменные, удовлетворяющих описанному выше условию (+ условию неотрицательности) и входящих в целевую функцию с коэффициентом ±М, где М – очень большое число, знак «+» при решении задачи на min, знак «-» при решении задачи на max. Данное правило используется для задач, содержащих в системе ограничений неравенства типа «≥».

Например:

max Z = x₁ – x₂

Предпочтительный вид будет следующий:

max Z = x₁ – x₂ – M∙v₁ – M∙v₂

v₁ и v₂ – базисные переменные, х₁ и х₂ – свободные.

Опорный план следующий: Х^* = (0; 0| 5; 4)

M-задачу по другому называют задачей с искусственным базисом.

При решении М-задачи симплекс-методом используют следующие теоремы:

1. Если в оптимальном плане Х^* = (х₁, х₂, ..., х_n| v₁, v₂, ..., v_m) M-задачи все искусственные переменные равны 0, т.е. v_S = 0, то план Х^* = (х₁, х₂, ..., х_n) является оптимальным планом исходной задачи.

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

Построение оптимального плана симплекс методом происходит в 3 этапа:

1. Построение начального опорного плана;

2. Проверка плана на оптимальность;

3. Переход к «нехудшему» опорному плану.

1. Построение начального опорного плана

Пусть в ЗЛП, заданной в канонической форме, имеется n переменных и m независимых линейных ограничений.

max(min) Z=c₁x₁+ c₂x₂+…+ c_nx_n

X= (x_1, x_2, … x_n) (1)

Известно, что оптимальное решение (если оно существует) достигается в одной из опорных точек (вершин ОДР), где по крайней мере k = n – m из переменных не равны 0. Выберем некоторые k переменных в качестве свободных и выразим остальные m базисных переменных.

Пусть базисными являются x₁, x₂, …, x_m. Тогда свободными являются x_m+1, x_m+2, …, x_n. Выразим базисные переменные, через свободные:

(2)

Если положить все свободные переменные x_m+1, x_m+2, …, x_n равными 0, получим:

… ;

Это решение может быть допустимым или недопустимым. Оно будет допустимым, если все свободные члены … неотрицательны. Предположим, что это условие выполнено, тогда полученное решение является опорным планом. Т.о. опорным планом называется любое допустимое решение ЗЛП.

2. Проверка плана на оптимальность

Выполним некоторые преобразования: Пусть исходная ЗЛП имеет канонический вид (1). Подставим выражения базисных переменных (2) в целевую функцию. Получим:

Введем обозначения:

где

– вектор коэффициентов целевой функции;

– вектор-столбец свободных членов;

– вектор-столбец коэффициентов при переменных х_j.

Таким образом задача исходная задача преобразуется в следующую:

X= (x_1, x_2, … x_n)

(3)

Такую задачу можно записать в виде симплексной таблицы:

БП	сБ	х1	х2	...	xi	...	xm	xm+1	...	xj	...	xn	А0
		c1	c2	...	ci	...	cm	cm+1	...	cj	...	cn
х1	c1	1	0	...	0	...	0	α1,m+1	...	α1,j	...	α1,n	β1
х2	c2	0	1	...	0	...	0	α2,m+1	...	α2,j	...	α2,n	β2
...	...	...	...	...	...	...	...	...	...	...	...	...	...
xi	ci	0	0	...	1	...	0	αi,m+1	...	αi,j	...	αi,n	βi
...	...	...	...	...	...	...	...	...	...	...	...	...	...
xm	cm	0	0	...	0	...	1	αm,m+1	...	αm,j	...	αm,n	βm
Δj		0	0	...	0	...	0	Δm+1	...	Δj	...	Δn	Δ0

В симплексной таблице

• Последнюю строку в таблице называют индексной строкой (или строкой целевой функции);

• Число – значение целевой функции для начального опорного плана;

• Числа – называют индексными оценками свободных переменных.