Алгоритм симплексного метода решения задач линейного программирования

Для того, чтобы решить задачу симплексным методом необходимо выполнить следующее:

1. Привести задачу к каноническому виду

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

3. Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода

4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается

5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения

Симплексный метод включает в себя:

1. Нахождение начального опорного решения;

2. Способ перехода от одного опорного решения к другому, на котором целевая функция ближе к оптимальности;

3. Критерий оптимальности (этот критерий позволяет остановить поиск решений).

1. Предполагая, что заданная запись в канонической форме, т.е. в форме равенств:

F(x) = c₁x₁ + …+ c_nx_n → max

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

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

a_m1x₁+a_m2x₂+…+a_mnx_n=b_n

Для нахождения начального опорного решения применяем метод Гаусса и приводим систему ограничений к разрешенной системе.

После приведения к разрешенной системе получим:

x₁+ … a_1m+1x_m+1+… a_1kx_k+… a_1nx_n=b₁

x₂+… a_2m+1x_m+1+… a_2kx_k+ … a_2nx_n=b₂

x_m+ a_mm+1x_m+1+… a_mkx_k+… 2_mnx_n=b_m

Ā₁= (10...0), Ā₂=(01..0), Ā_m=(00..1)

X₁= (x₁,x₂,x₃)

X₁= (b₁,b₂,b_m)

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

2. Возьмем столбец с номером k и на этом столбце выберем a_ek (разрешенный элемент)

Применим метод Жордана:

а) Делим строку L на a_ek

b'_e = b_e/ a_ek,треб.a_ek>0

b) далее получаем 0 для другого элемента этого столбца

b'_i = b_i – b_e/a_ek * a_ik ≥0 => b_i/a_ik ≥b_e/a_ek.

Из этого неравенства выводим критерий выбора е, при условии, что знаем как выбрать k

min= b_i/a_ik

Рассмотрим способ выбора столбца k.

Для этого 1-ое решение будем сравнивать с новым 2-ым решением.

F(X₂)= Ʃ c_ib_i – b_e/a_ek (Ʃ c_ia_ik – c_k)

Обозначаем Ѳ_k= b_e/a_ek

∆k = Ʃ c_ia_ik – c_k

Называется оценкой разложения вектора услов. A_k по базису опорного решения.

F(X₂) = F(X₁)- Ѳ_k*∆k

Если оценка меньше 0 (∆k < 0), то отсюда вывод:

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

Утверждение 2. Критерий выбора k: выбираем из условий max{-Ѳ_k*∆k}, другими словами, перебираем все отрицательные оценки и берем наибольшее значение по модулю.

Утверждение 3. Опорное решение является оптимальным, если все оценки не отрицательны.

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