Форум » Логические выражения » Двойственность в Линейном Программировании и Задача 18 по Досрочному ЕГЭ Информатика 2018 » Ответить
Двойственность в Линейном Программировании и Задача 18 по Досрочному ЕГЭ Информатика 2018
dbaxps: Найти наибольшее А для всех х1,х2,х3 >=0 (16x1+7x2+6x3+4 > A)v(2x1-4x2+3x3<3)v(4x1+5x2-2x3<8) = 1 Используя двойстенность в ЛП задачу с многими переменными ( >= 3 ) и не болле чем двумя дизъюнкциями ( 2 переменных в двойственной задаче) мы сведем к графической задаче Симплекс метода ======================================== Соответствующая задача ЛП имеет вид :- ======================================== Z = 16x1+7x2+6x3+4=> Min1 2x1-4x2+3x3 >= 3 4x1+5x2-2x3 >=8 =========================== Двойственная задача ЛП =========================== W= 3u1 + 8u2 +4 => Max2 2u1+4u2 <= 16 -4u1+5u2 <= 7 3u1-2u2 <= 6 u1 >=0 u2 >=0 Решается графически смотри :- Линк01 Само решение :- Линк02 Теорема. (Первая основная теорема двойственности.) Если одна из двойственных задач имеет оптимальное решение, то двойственная ей задача также имеет оптимальное решение, причем экстремумы целевых функций равны. Если одна из двойственных задач не имеет оптимального решения, то другая задача также не имеет оптимального решения, причем если одна из задач не имеет оптимального решения из-за неограниченности целевой функции, то другая из-за несовместности системы ограничений.
Ответов - 0
полная версия страницы