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

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

Опорное решение задано, если среди коэффициентов системы ограничений можно выделить единичный минор порядка m, где m – число уравнений. Допустим, что условия выполнены: задача имеет n переменных, m ограничений и при первых m переменных коэффициенты составляют единичный минор, m < n.

Симплекс - метод позволяет перейти к соседней вершине области определения, в которой более оптимальное решение.

z = c₁  x₁ + c₂  x₂ +...+ c_n  x_n → max

x₁ + … a_{1, m+1}  x _m+1 +…+ a_1j  x_j +…+ a_1n  x_n = b₁,

x₂ + … a_{2, m+1}  x _m+1 +…+ a_2j  x_j +…+ a_2n  x_n = b₂,

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

x_m + … a_{m, m+1}  x _m+1 +…+ a_mj  x_j +…+ a_mn  x_n = b_m.

где х₁, х₂,… х_n  0.

Исходное оптимальное решение: х₁ = b₁, x₂ = b₂, x_m = b_m, x_m+1 = 0, x_n = 0 – опорный план, т.е. вектор p – линейно не зависимый.

№ строки	Базисные перемен-ные	С	План	c1 x1	…	cm xm	cm+1 xm+1	… …	cj xj	… …	cn xn
1 2 … m	x1 x2 … xm	c1 c2 … cm	b1 b2 … bm	1 0 … 0	… 1 … …	0 0 … 1	a1, m+1 a2, m+2 … am, m+1	… … … …	a1j a2j … amj	… … … …	a1n a2n … amn
m +1				∆1	…	∆m	∆m+1	…	∆j		∆n

∆_j = (1) - оценка j-той переменной

Алгоритм Симплекс – метода:

1) Анализ опорного плана на оптимальность. Если все оценки ∆_j  0, то план оптимален. Если хотя бы одна оценка < 0, то необходим переход к другому плану, т.е. пересчет всех коэффициентов.

2) Выбор разрешающего элемента. Решаем вопрос о том, какую переменную ввести, а какую вывести: вводим переменную, у которой ∆_j < 0. Если таких много, то наибольшую по модулю. Рассматриваем отношение элементов вектора плана к положительным коэффициентам вводимой переменной: (b₁ / a_1j ; b₂ / a_2j ; … b_m / a _mj), a  0

Минимальное отношение покажет строку выводимой переменной, например, b₂ / a_2j – min, тогда выводим х₂, x_j – вводим.

а_2j – разрешающий элемент, находится на пересечении х_j и х₂.

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

Два способа пересчета оценочной строки: по формуле (1) или по правилу треугольника, а затем переходим к пункту 1.

Возможны различные случаи:

1. Единственное решение: если в оптимальном плане для всех небазисных переменных оценки больше нуля.

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

3. Оптимальное значение достигается в ∞ (бесконечности): если только одна переменная имеет отрицательную оценку, но среди коэффициентов нет ни одного положительного, т.е. мы не можем делить.