Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Искусственное начальное решение
пример. 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.
Итак, Метод больших штрафов (М – метод) max (– z) = – 3 x 1 – 2 x 2 – 3 x 3 – MR 1 – MR 2. M > > 1. R 1 = R 2 = 0 – Если это получим, то исходная задача имеет решение, если этого не получим, то исходная задача не имеет решения.
x 1 = 0; x 2 = 0; x 3 = 0; max (– z) = – 4; min z = 4.
|