![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Вторая теорема двойственности
Пусть взаимно двойственные задачи представлены в симметричной форме
![]()
![]()
Рассматриваемая ниже теорема позволяет утверждать, что на оптимальных решениях прямой и двойственной задач выполняется условие: для каждой пары понятий: (переменная одной задачи – соответствующее ограничение другой) или переменная обращается в ноль, или ограничение выполняется как равенство.
Теорема 2: для того, чтобы допустимое решение прямой задачи
![]() Условия (7)-(8) не означают ничего другого, как только то, что или переменная обращается в ноль, или ограничение выполняется как равенство. Доказательство: · Достаточность: Пусть имеются Для этого просуммируем (7) и (8) по j и по i соответственно:
![]() Левые части соотношений (9) и (10) равны, значит, равны и правые, а это критерии целевых функций
· Необходимость:
![]() ![]() Продолжая неравенство (11) с учетом (12), получим
![]()
Так как Преобразуем
![]() В левой части (14) – сумма неотрицательных слагаемых. Такая сумма равна нулю только тогда, когда каждое слагаемое равно нулю А это и есть соотношения (7). Аналогично доказываются и соотношения (8). Теорема доказана.
Экономическая интерпретация второй теоремы двойственности: 1. Если на оптимальном плане продукция производится ( 2. Если на оптимальном плане затраты на производство единицы продукции превышают доход ( 3. Если на оптимальном плане оценка ресурса больше ноля ( 4. Если на оптимальном плане ресурс расходуется не полностью (
Соотношения (7) и (8) позволяют по оптимальному решению одной задачи найти оптимальное решение другой. Вторая теорема двойственности позволяет сформулировать признак оптимальности допустимого решения. Мы уже знаем один признак оптимального решения (теорема 4 главы 3), но он справедлив только для опорного решения (угловой точки области допустимых решений) и фактически требует построения симплекс-таблицы.
Следствие теоремы 2 (двойственный признак оптимальности): для того, чтобы допустимое решение задачи линейного программирования
![]() существовало хотя бы одно допустимое решение двойственной задачи ![]() Решение
Пример: Предприятие может работать по двум технологиям. При этом используются два типа ресурсов. Запасы ресурсов составляют 12 тонн и 4 литра соответственно. За 1 час работы по первой технологии расходуется 2 тонны первого ресурса и 1 литр второго, а за 1 час работы по второй технологии – 1 тонна первого ресурса. 1 час работы по первой технологии приносит доход 8 тыс. руб., а по второй – 3 тыс. руб. Суммарное время работы по технологиям должно составлять 6-часовую смену. Определить время работы по каждой технологии так, чтобы суммарный доход был наибольшим. · Математическая модель
· Построим двойственную задачу.
· Проверим, является ли оптимальным решение Для этого запишем соотношения дополняющей нежесткости (7). Подставим в эти соотношения компоненты решения Решая данную систему уравнений, получим Мы получили, что найденное нами решение
· Предположим, что нам известно оптимальное решение прямой задачи Таким образом, мы получили оптимальное решение двойственной задачи
|