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

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

Для применения симплекс-метода необходимо, чтобы заданная система ограничений выражалась равенствами, причем в этой системе ограничений должны быть выделены базисные неизвестные. Решение задачи при помощи симплекс-метода распадается на ряд шагов. На каждом шаге от данного базиса Б переходят к другому, новому базису Б1 с таким расчетом, чтобы функции Z уменьшалось, то есть Z_Б1 ≤ Z_Б. Для перехода к новому базису из старого базиса удаляется одна из переменных и вместо нее вводится другая из числа свободных. После конечного числа шагов находится некоторый базис Бк, для которого Z_Бк есть искомый минимум для линейной функции Z, а соответствующее базисное решение является оптимальным либо выясняется, что задача не имеет решения.

Рассмотрим систему-ограничений и линейную форму вида:

a₁₁x₁ + a₁₂x₂ + …+ a_1nx_n = b₁

a₂₁x₁ + a₂₂x₂ + …+ a_2nx_n = b₂

_{………………………………………………..}

a_m1x₁ + a_m2x₂ + …+ a_mnx_n = b_m

Z = c₀ + c₁x₁ + c₂x₂ + …+ c_nx_n àmin;

x_i ≥ 0, i = (1,n).

Используя метод Жордана-Гаусса, записанная система приводится к виду, где выделены базисные переменные.

Вводятся следующие условные обозначения:

x₁, x₂, …x_r - базисные переменные;

x_r+1, x_r+2, …x_n - свободные переменные.

x₁ = β₁ – (a_1r+1x_r+1 + a_1r+2x_r+2 + …+ a_1nx_n)

x₂ = β₂ – (a_2r+1x_r+1 + a_2r+2x_r+2 + …+ a_2nx_n)

………………………………………….

x_r = β_r – (a_rr+1x_r+1 + a_rr+2x_r+2 + …+ a_rnx_n)

Z = γ₀ – (γ ₁x_r+1 + γ ₂x_r+2 + …+ γ _nx_n àmin).

По последней системе ограничений и целевой функции строится таблица 1.

Таблица 1

Симплекс-таблица

Свободные неизвестные     Базисные неизвестные	Свободный член	xr+1	xr+2	…	xn
x1 x2 … xr Zmin	β1 β2 … βr γ0	a1r+1 a2r+1 … arr+1 γr+1	a1r+2 a2r+2 … arr+1 γr+2	… … … … …	a1n a2n … arn γn

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

Алгоритм симплекс-метода сводится к следующему.

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

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

3. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

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

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

6. Элемент новой таблицы, соответствующий разрешающему элементу первоначальной таблицы равен обратной величине разрешающего элемента.

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

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

9. Остальные элементы вычисляются по правилу прямоугольника.

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

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

Дата добавления: 2014-01-15