|
|||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Постановка двойственной задачиЛюбой задаче линейного программирования определённым образом соответствует некоторая другая задача линейного программирования, называемая двойственной или сопряженной. Первоначальная задач называется исходной или прямой. Тесная связь между исходной и двойственной задачами, составляющими так называемую двойственную пару, проявляется в том, что, зная решение одной из этих задач, можно построить решение другой на основании теоремы о двойственности. Запишем задачи двойственной пары в случае рассматриваемой нами прикладной задачи. Введём обозначения:
Нашу исходную задачу (2.5) – (2.7) сформулируем, используя матричную форму записи, следующим образом: требуется определить вектор
при условиях
Тогда двойственная задача формулируется так: определить вектор
при условии
Целевая функция (2.33) двойственной задачи может быть записана в эквивалентной форме:
Транспонируя обе части неравенства (2.34), записанного в виде строки, и учитывая что
Отметим, что в двойственной задаче переменные Таким образом, для получения двойственной задачи из прямой необходимо выполнить следующие действия: - транспонировать векторы ограничений - транспонировать матрицу условий - заменить знаки равенства в ограничениях (2.31) знаками неравенств - исключить условия неотрицательности (2.32); - заменить требование максимизации целевой функции требованием её минимизации. Выполним эти действия применительно к рассматриваемой нами исходной задаче (2.15), (2.16). Применительно к ней матрицы (2.29) запишутся так:
Двойственная задача имеет вид
Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.) |