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