![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Основные теоремы двойственностиСвязь между оптимальными решениями двойственных задач устанавливается с помощью теорем двойственности. Основное неравенство теории двойственности.Пусть имеется пара двойственных задач I и II. Покажем, что для любых допустимых решений
Доказательство. Умножив неравенства системы ограничений (7.2) прямой задачи
Аналогично преобразовав систему ограничений (7.5) двойственной задачи
Так как левые и правые части неравенств (7.8) и (7.9) представляют одно и то же выражение Теперь можно перейти к признакам оптимальности решений. Достаточный признак оптимальности. Сформулируем теорему. Теорема 1. Если
то Доказательство. Пусть Кроме достаточного признака оптимальности взаимодвойственных задач существуют и другие важные соотношения между их решениями. Прежде всего возникают вопросы: всегда ли для каждой пары двойственных задач есть одновременно оптимальные решения; возможна ли ситуация, когда одна из двойственных задач имеет решение, а другая нет. Ответ на эти вопросы дает следующая теорема. Первая (основная) теорема двойственности. Если одна из взаимодвойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их линейных функций равны:
Если линейная функция одной из задач не ограничена, то условия другой задачи противоречивы и она не имеет решения. Из первой части утверждения теоремы (которую принимаем без доказательства) следует, что условие (7.10) является не только достаточным признаком оптимальности решений (доказанным выше), но и необходимым признаком оптимальности решений взаимодвойственных задач. Утверждение второй части легко доказывается методом от противного. Предположим, что в прямой задаче линейная функция не ограничена, т.е. Экономический смысл первой (основной) теоремы двойственности. План производства Экономический смысл первой теоремы двойственности можно интерпретировать и так: предприятию безразлично, производить ли продукцию по оптимальному плану Замечание. Утверждение, обратное по отношению ко второй части основной теоремы двойственности, в общем случае неверно, т.е. из того, что условия исходной задачи противоречивы, не следует, что линейная функция двойственной задачи не ограничена. Тесная связь между двумя взаимодвойственными задачами проявляется не только в равенстве оптимальных значений их линейных функций, о чем утверждалось в первой (основной) теореме двойственности. При приведении каждой из взаимодвойственных задач к каноническому виду в систему ограничений прямой задачи I (7.2) вводят m неотрицательных переменных xn+1, xn+2, ¼ xn+m, а в систему ограничений двойственной задачи II – n неотрицательных переменных ym+1, ym+2, ¼ ym+n. Системы ограничений каждой из взаимодвойственных задач примут вид:
Установим соответствие между первоначальными переменными одной из двойственных задач и дополнительными переменными другой задачи (табл. 7.2). Таблица 7.2
Теорема 2 (примем без доказательства). Положительным (ненулевым) компонентам оптимального решения одной из взаимодвойственных задач соответствуют нулевые компоненты оптимального решения другой задачи, т.е. для любых i = 1, 2, ¼, m и j = 1, 2, ¼, n: если если и аналогично, если если Из рассмотренной теоремы следует важный вывод о том, что введенное ранее соответствие (7.14) между переменными взаимодвойственных задач при достижении оптимума (т.е. на последнем шаге решения каждой задачи симплексным методом) представляет соответствие между основными (как правило, не равными нулю) переменными одной из двойственных задач и неосновными (равными нулю) переменными другой задачи, когда они образуют допустимые базисные решения. Рассмотренная теорема является следствием следующей теоремы. Вторая теорема двойственности. Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных линейной функции прямой задачи, выраженной через неосновные переменные ее оптимального решения. Замечание. Если в одной из взаимодвойственных задач нарушается единственность оптимального решения, то оптимальное решение двойственной задачи вырожденное. Это связано с тем, что при нарушении единственности оптимального решения прямой задачи в выражении линейной функции ее оптимального решения через неосновные переменные отсутствует хотя бы одна из основных переменных. Третья теорема двойственности. Компоненты оптимального решения двойственной задачи равны значениям частных производных линейной функции fmax(b1, b2, ¼, bm) по соответствующим аргументам, т.е.
Из данной теоремы следует, что объективно обусловленные оценки показывают, насколько денежных единиц изменится максимальная выручка от реализации продукции при изменении запасов соответствующего i-го ресурса на одну единицу.
|