Общие правила составления двойственных задач
При составлении двойственных задач используют следующие правила:
Правило 1. Во всех ограничениях исходной задачи свободные члены должны находится в правой части, а члены с неизвестными – в левой.
Правило 2. Ограничения-неравенства исходной задачи должны быть записаны так, чтобы знаки неравенств у них были направлены в одну сторону.
Правило 3. Если знаки неравенств в ограничениях исходной задачи «≥», то целевая функция должна максимизироваться, а если «≤», то минимизироваться.
Правило 4.Каждому ограничению исходной задачи соответствует неизвестное в двойственной задаче; при этом неизвестное, отвечающее ограничению-неравенству, должно удовлетворять условию неотрицательности, а неизвестное, отвечающее ограничению-неравенству, может быть любого знака.
Правило 5. Целевая функция двойственной задачи имеет вид: где -свободный член целевой функции Z(X) исходной задачи; - свободные члены в ограничениях исходной задачи, при этом -свободный член именно того ограничения, которому соответствует неизвестная неизвестные в двойственной задаче.
Правило 6. Целевая функция F(Y) двойственной задачи должна оптимизироваться противоположным по сравнению с Z(X) образом, т.е. если то и если то
Правило 7. Каждому неизвестному исходной задачи соответствует ограничение в двойственной задаче. Совокупность этих nограничений (вместе с условиями неотрицательности неизвестных , соответствующих ограничениям-неравенствам исходной задачи) образует систему ограничений двойственной задачи. Все ограничения двойственной задачи имеют вид неравенств, свободные члены которых находятся в правых частях, а члены с неизвестными в левых. Все знаки неравенств имеют вид «≥», если и «≤», если
Коэффициенты, с которыми неизвестные входят в ограничение, соответствующее неизвестному совпадают с коэффициентами при этом неизвестном в ограничениях исходной задачи, а именно: коэффициент при совпадает с тем коэффициентом при , с которым входит в ограничение исходной задачи, соответствующее неизвестному . Взаимная симметрия прямой и двойственной задач определяет существование определенного соответствия между их оптимальными решениями, которое устанавливают теоремы двойственности: если прямая и двойственная задачи линейного программирования имеют оптимальные решения, то экстремальные значения их целевых функций равны, т.е. справедливо равенство: min CX = max YB. (первая теорема двойственности) Не менее важное соответствие оптимальных решений прямой и двойственных задач устанавливают условия дополняющей нежесткости, которые связывают необходимые и достаточные условия оптимальности допустимых решений X и Yобеих задач со следующими соотношениями: Y(AX-B)=0 (C-YA)X=0. (вторая теорема двойственности) Таким образом всегда имеется возможность выбора: решать прямую или двойственную задачу, используя модификацию задачи, для которой легче найти решение. Пример. Составить задачу, двойственную к данной: Р е ш е н и е. Используем общие правила составления двойственных задач. Умножим ограничения-неравенства на -1, так как в задаче на минимум они должны иметь вид «≥» (см. правило 3). Исходная задача запишется в виде:
Составим двойственную задачу: Неизвестная соответствующая ограничению-неравенству, может быть любого знака (см. правило 4).
5. ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ КАК ЧАСТНЫЙ СЛУЧАЙ ОБЩЕЙ РАСПРЕДЕЛИТЕЛЬНОЙ ЗАДАЧИ.
Популярное: Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (788)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |