Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
1) Если в ограничении есть знак ≤, то мы прибавляем к левой части остаточную переменную
x 1 – 2 x 2 ≤ 5; x 1 – 2 x 2 + s 1 = 5; s 1 – остаточная переменная s 1 ≥ 0;
2 x 1 + 3 x 2 ≥ 10; 2 x 1 + 3 x 2 – s 2 = 10; s 2 – избыточная переменная s 2 ≥ 0.
2) max z = (– a) Û min (– z) = a.
Решение, полученное занулением n – m переменных называется базисным. Переменные не равные нулю называются базисными переменными, а равные нулю – небазисными.
шаг 0 начальное решение (xi = 0).
базис | С | X опт | r | |||||
x 1 | x 2 | s 1 | s 2 | s 3 | ||||
s 1 | ||||||||
s 2 | 30 | |||||||
s 3 | ||||||||
z | – 2 | – 3 |
z – строка оценок;
“С” ´ столб – (оценка в верхней строчке);
X опт = 0·120 + 0·300 + 0·600 – 0 = 0;
x 1: 0·2 + 0·3 + 0·8 – 2 = – 2 и т.д.
шаг 1
Если в строке нет отрицательных, то оптимальное решение получено. Столбец, в котором стоит наибольшая по модулю отрицательная оценка является разрешающим. Переменная этого столбца вводится в базис. x 2 – разрешающая; x 2 вводится в базис.
шаг 2
Находим отношение элементов столбца X опт к положительным элементам разрешающего столбца. Строка, в которой отношение наименьшее является разрешающей, соответствующая переменная выводится из базиса.
s 2 выводится из базиса, разрешающая.
На пересечении разрешающей строки и разрешающего столбца стоит главный элемент.
шаг 3
Пересчитываем коэффициенты таблицы с помощью преобразований Гаусса.
базис | С | X опт | r | |||||
x 1 | x 2 | s 1 | s 2 | s 3 | ||||
s 1 | ||||||||
x 2 | ||||||||
s 3 | ||||||||
z | ||||||||
s 1 | ||||||||
x 2 | ||||||||
x 1 | ||||||||
z | ||||||||
s 2 | ||||||||
x 2 | ||||||||
x 1 | ||||||||
z |
Особые случаи применения симплекс-метода
1. Вырождение решение
Одна из базисных переменных на некотором этапе равна 0. Графически это означает избыточное ограничение.
пример. max z = 3 x 1 + 9 x 2.
Б | С | X опт | r | ||||
x 1 | x 2 | s 1 | s 2 | ||||
s 1 | 2; | ||||||
s 2 | 2; | ||||||
z | – 3 | – 9 | |||||
s 1 | – 1 | – 2 | |||||
x 2 | |||||||
z |
x 2 = 2; s 1 = 0; x 1 = s 2 = 0; z = 18.
2. Альтернативное решение
пример. max z = 2 x 1 + 4 x 2.
АВ – множество решений
Б | С | X опт | r | ||||
x 1 | x 2 | s 1 | s 2 | ||||
s 1 | |||||||
s 2 | |||||||
z | – 2 | – 4 | |||||
x 2 | |||||||
s 2 | |||||||
z | |||||||
x 2 | – 1 | ||||||
x 1 | – 1 | ||||||
z |
Используем формулу: x = a ·α + b ·(1 – α); α Î [0; 1]
3. Неограниченное решение
пример. max z = 2 x 1 + x 2.
max z = ∞
Б | С | X опт | r | ||||
x 1 | x 2 | s 1 | s 2 | ||||
s 1 | – 1 | ||||||
s 2 | |||||||
z | – 2 | – 1 |
Столбец x 2 не содержит положительных, значит сразу можно сделать вывод о неограниченности максимума.
max z = ∞
Дата публикования: 2015-09-17; Прочитано: 151 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!