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

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

1. Ввести размерность задачи. Ввести коэффициенты в канонической форме, базисные переменные и задать небазисные переменные.

2. Найти наименьший из коэффициентов C '_m+1, …, C '_s, …,C '_n. Пусть это коэффициент C '_s. Если C '_s ³ 0, то конец, оптимум найден. Иначе: C'_s<0, и переменная X_s войдет в базис, перейти к 3.

3. Если все a ' _is £ 0, то конец.

Решение лежит вне заданных границ. Иначе: вычислить  B'_i / a ' _is  для всех a ' _is>0 и найти минимум B'_i / a ' _is.

Пусть этот минимум равен b_r / a ' _is. Тогда X_s – базисная переменная, а X_r – свободная переменная.

4. Построить новую каноническую форму, изменить базис и перейти к 2.

Б. Двойственный симплекс-метод.

1. Пусть все коэффициенты целевой функции положительны.

2. Найти отрицательную базисную переменную. Если ее нет, то оптимальное решение найдено; если их более чем одна, надо взять из них наименьшую. Пусть эта базисная переменная в r-м ограничении, она является переменной для исключения из базиса.

3. В r-й строке найти отрицательный коэффициент a_rj.

4. Если такого коэффициента нет, то не существует допустимого решения задачи. Для отрицательных коэффициентов в этой

 строке найти .

5. Если этот минимум найден в S-м столбце, переменная X_s должна быть включена в базис.

6. Провести обычные симплекс-преобразования, выбрав в качестве ведущего элемента a ' _rs.

В. Улучшенный симплекс-алгоритм.

1. Пусть задача представлена в канонической форме. Базисные переменные X_n+1, …, X_n+m равны соответственно b₁, …, b_m. Обращение базиса есть просто I_m – единичная матрица размерностью m´m. Соответствующие симплекс-множители – это p₁ = 0, …,  p_m = 0, поскольку в целевую функцию Z не входят базисные переменные.

2. На k-й итерации базисные переменные – это X₁, …, X_m, которые принимают значения b'₁, …, b'_m. Обращение базиса – матрица B^–1 размерностью m´m, а симплекс-множители равны p₁, …, p_m.

3. Вычислить коэффициенты небазисных переменных в канонической форме целевой функции в текущем базисе:

,

где p_i- текущие симплекс-множители, a_ij - исходные коэффициенты из уравнения.

4. Величины C'_j вычисляются для каждой небазисной переменной. Найти наименьший из коэффициентов C'_m+1 , …, C'_n.

5. Если C'_s ³ 0, то минимум функции Z найден, конец. Иначе:   C'_s < 0, и переменная X_s войдет в базис.

6. Определить переменную, которая будет заменена переменной X_s. С этой целью вычислить a'_s = B^–1*a_s.

7. Определить строку базисной переменной, предназначенной для исключения из базиса .

Заменить старый базис X₁, …, X_r, …, X_m на новый X₁, …, X_s, …, X_m. Новые значения базисных переменных равны

; X_i = b_i⁺ = b'_i – a_is *b_r⁺; (i ¹ r).

8. Cформировать матрицу:

- r-я строка

5-я строка

9. Вычислить (новое обращение) =Е (исходное обращение).

10. Найти новые симплекс-множители. Исходные значения симплекс-множителей .

11. Новые значения симплекс множителей

.

Вернуться к 2.

Контрольные вопросы и задания

1. Как определяется направление возрастания целевой функции в графическом методе решения задачи линейного программирования (ЛП)?

2. Дайте характеристику стандартной формы задач линейного программирования.

3. Приведите основные правила для преобразования задачи ЛП к стандартному виду.

4. Каким соотношением задается отрезок в n-мерном пространстве?

5. Дайте определение экстремальной точки.

6. Какое множество называется выпуклым?

7. Докажите, что если ограничения имеют допустимое решение, то они имеют и базисное решение.

8. Докажите, что допустимая область является выпуклым множеством.

9. Докажите, что базисные допустимые решения соответствуют вершинам выпуклого множества.

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

11. Дайте характеристику канонической формы задачи ЛП.

12. Выведите основные соотношения для симплекс-метода.

13. Назовите основные шаги симплекс-метода.

14. Какой базис называется вырожденным?

15. Рассмотрите изменения значений правых частей.

16. Рассмотрите изменения коэффициентов целевой функции.

17. Как решается задача ЛП при появлении дополнительных переменных?

18. Опишите решение задачи ЛП при включении дополнительных ограничений.

19. Приведите основные шаги двойственного симплекс-метода.

20. Приведите основные шаги улучшенного симплекс-метода.

21. Основные правила перехода к двойственной задаче.

22. Докажите, что двойственной задачей к двойственной  задаче есть прямая задача.

23. Докажите, что Z ³ W, где W – целевая функция двойственной задачи.

24. Докажите, что если прямая задача имеет конечное решение, то двойственная задача имеет конечное решение W_max = Z_min.

25. Докажите, что значения симплекс-множителей оптимального решения двойственной задачи являются значениями переменных в оптимальном решении прямой задачи.