Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
пример. min z = 4 x 1 + x 2.
max (– z) = – 4 x 1 – x 2.
Если начальное решение x 1 = x 2 = 0, то
– не является допустимым решением.
Добавляем искусственные переменные Ri.
Начальное решение x1 = x2 = 0.
– не является допустимым решением.
Исходная задача будет иметь решение только в том случае, когда полученная задача имеет решение R 1 = R 2 = 0.
Двухэтапный метод
1) min r = R 1 + R 2.
Если эта задача имеет решение при r = 0 при R 1 = R 2 = 0, то исходная задача также имеет решение, причем оптимальное решение составленной задачи является начальным решением исходной.
Если же r = R 1 = R 2 = 0 не выполняется, то исходная задача решений не имеет.
2) Решается исходная задача
min r = R 1 + R 2; max (– r) = – R 1 – R 2.
Б | С | X опт | – 1 | – 1 | r | ||||
x 1 | x 2 | s 1 | s 2 | R 1 | R 2 | ||||
R 1 | – 1 | 3/3 | |||||||
R 2 | – 1 | – 1 | 3/2 | ||||||
s 2 | |||||||||
– r | – 9 | – 7 | – 4 | ||||||
x 1 | 1/3 | 1/3 | |||||||
R 2 | – 1 | 5/3 | – 1 | – 4/3 | 3/4 | ||||
s 2 | 5/3 | – 1/3 | 9/5 | ||||||
– r | – 2 | – 5/3 | 7/3 | ||||||
Б | С | X опт | – 4 | – 1 | – 1 | – 1 | |||
x 1 | x 2 | s 1 | s 2 | R 1 | R 2 | ||||
x 1 | 0 (– 4) | 3/5 | 1/5 | 3/5 | – 1/5 | r = 0 R 1 = 0 R 2 = 0 | |||
x 2 | 0 (– 1) | 6/5 | – 3/5 | – 4/5 | 3/5 | ||||
s 2 | 0 (0) | – 1 | |||||||
– r | |||||||||
– z | – 18/5 | – 1/5 | |||||||
x 1 | – 4 | 2/5 | – 1/5 | ||||||
x 2 | – 1 | 9/5 | 3/5 | ||||||
s 2 | |||||||||
– z | – 17/5 | 1/5 |
Итак,
Метод больших штрафов (М – метод)
max (– z) = – 3 x 1 – 2 x 2 – 3 x 3 – MR 1 – MR 2.
M >>1.
R 1 = R 2 = 0 – Если это получим, то исходная задача имеет решение, если этого не получим, то исходная задача не имеет решения.
Б | С | X опт | – 3 | – 2 | – 3 | – M | – M | ||
x 1 | x 2 | x 3 | s 1 | s 2 | R 1 | R 2 | |||
R 1 | – M | – 1 | |||||||
R 2 | – M | – 1 | |||||||
– z | –10 M | M | M | ||||||
R 1 | – M | 5/4 | 1/2 | – 1 | 1/4 | не надо | |||
x 2 | – 2 | 3/4 | 1/2 | – 1/4 | не надо | ||||
– z | –4 | M | не надо | ||||||
x 1 | – 3 | 2/5 | – 4/5 | 1/5 | не надо | не надо | |||
x 2 | – 2 | 1/5 | 3/5 | – 2/5 | не надо | не надо | |||
– z | –4 | 7/5 | 6/5 | 1/5 | не надо | не надо |
x 1 = 0; x 2 = 0; x 3 = 0; max (– z) = – 4; min z = 4.
Дата публикования: 2015-09-17; Прочитано: 193 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!