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