Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Искусственное начальное решение
|
|
пример. 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.
|
|