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