КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Соотношения двойственности
Тесная связь между двумя взаимно двойственными задачами проявляется не только в равенстве оптимальных значений их целевых функций, но и в том, что оптимальное решение одной из этих задач непосредственно можно получить из данных симплексной таблицы, содержащей оптимальное решение другой задачи.
Пусть даны две взаимно двойственные задачи. Если каждую из этих задач решать симплекс-методом, то необходимо привести их к каноническому виду, для чего в систему ограничений прямой задачи вводятся неотрицательных дополнительных переменных , а в систему ограничений обратной задачи неотрицательных дополнительных переменных .
Системы ограничений ПЗ и ОЗ примут вид: , ; , . Первоначальным (свободным) переменным прямой задачи соответствуют дополнительные (базисные) переменные обратной задачи, а дополнительным (базисным) переменным ПЗ соответствуют первоначальные (свободные) переменные ОЗ.
Пример 2).
Соответствие между переменными
Чтобы найти оптимальное решение ОЗ по известному оптимальному решению ПЗ, нужно воспользоваться следующим правилом: значение переменной ОЗ равно коэффициенту в целевой функции при соответствующей переменной ПЗ, взятому с противоположным знаком из последней симплексной таблицы.
Р е ш е н и е ПЗ.
Ответ ПЗ: при , . Ответ ОЗ: при , , .
Пример 3).
Соответствие между переменными
Чтобы найти оптимальное решение ПЗ по известному оптимальному решению ОЗ, нужно воспользоваться следующим правилом: значение переменной ПЗ равно коэффициенту в целевой функции при соответствующей переменной ОЗ, взятому с противоположным знаком из последней симплексной таблицы.
Р е ш е н и е ОЗ.
Ответ ОЗ: при ; ; . Ответ ПЗ: при ; . Двойственный симплекс-метод (ПР № 8)
В результате использования двойственного симплекс-метода сначала получается решение, для которого выполняется условие оптимальности, но которое не является допустимым. Этот метод обеспечивает выполнение условия оптимальности решения и систематическое ‘приближение’ его к области допустимых решений. Когда полученное решение оказывается допустимым, процесс вычисления заканчивается, т.к. это решение является и оптимальным.
Алгоритм метода
1. В столбце ‘ В ’ выбирается наибольшая по абсолютной величине отрицательная базисная переменная; если все базисные переменные неотрицательны, то процесс вычислений заканчивается, т.к. полученное решение допустимое и оптимальное.
2. Включаемая в базис переменная выбирается из числа свободных следующим образом. Вычисляются отношения коэффициентов строки целевой функции к соответствующим коэффициентам ключевой строки. Отношения с положительным или нулевым значением знаменателя не учитываются. Вводимой переменной должно соответствовать наименьшее из указанных отношений. Если знаменатели всех отношений равны нулю или положительные, то задача не имеет допустимых решений.
3. После выбора ключевого столбца для получения следующего решения осуществляется обычная процедура пересчёта элементов симплексной таблицы.
Пример. ОЗЛП
Поэтому для нахождения оптимального решения задачи можно использовать двойственный симплекс-метод, который поз-воляет обойтись без искусст-венных переменных.
Ответ: при ; Пример 2. Составить ОЗ к данной задаче, решить ОЗ двойственным симплекс-методом. Записать ответ ПЗ по известному решению ОЗ.
. Р е ш е н и е. ОЗ формулируется следующим образом:
Нахождение оптимального решения ОЗ двойственным симплекс-методом. ОЗЛП В качестве первоначальных базисных переменных
выбираются :
Ответ ОЗ: , , .
Чтобы записать ответ ПЗ, нужно воспользоваться соответствием между переменными прямой и обратной задач.
Ответ ПЗ: , , , .
Задания к практической № 7 (Двойственность в ЛП)
Задание 1. Составить обратные (двойственные) задачи к данным задачам ЛП. (по примеру 1) Задача а)
Задача б)
Задание 2. Составить обратные (двойственные) задачи к данной задаче ЛП. Записать ответ по известному решению прямой задачи. (по примеру 3)
Дата добавления: 2014-01-07; Просмотров: 943; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |