Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Искусственное начальное решение






пример. min z = 4 x 1 + x 2.

max (– z) = – 4 x 1x 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 1R 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 3MR 1MR 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.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.