Анализ чувствительности оптимального решения к изменению свободных членов ограничений

Пусть исходная задача дана в канонической форме:

I.

Тогда двойственная к ней будет иметь вид:

II.

Конечно, оптимальное решение зависит от исходных параметров, поэтому его можно рассматривать как неявно заданную функцию исходных параметров

Изучим влияние пока только одного параметра – ветора на оптимальное решение .

Пусть правые части ограничений (ресурсы) меняются, получая малые приращения:

– возмущенный вектор правых частей ограничений.

– (малые) приращения ресурсов.

Тогда задача с новым вектором правых частей ограничений (возмущенная задача) I’ и двойственная к ней II’ запишутся в виде

I’. (6)

II’.

Как найти оптимальное решение задачи I’, зная оптимальное решение задачи I?

Лемма: пусть – невырожденное оптимальное решение задачи I и – базисная матрица этого плана .

Если выполняется условие

,

то:

·

· оптимальное решение двойственной задачи не меняется

.

Доказательство:

Пусть – оптимальное решение, – его базисная матрица. Значит, существует и обратная матрица , базисные компоненты оптимального плана – , выполняется признак оптимальности .

Покажем, что вектор (10) – оптимальное решение возмущенной задачи.

Сначала покажем, что это допустимое решение, то есть для него должны выполняться ограничения (7) и (8).

Подставляя в левую часть (7), получим

,
то есть ограничение (7) выполняется.

Условие (8) выполняется из условия (9) леммы.

Итак, – допустимое решение задачи I’.

Покажем, что это оптимальное решение. Проверим признак оптимальности. Оценки свободных переменных возмущенной задачи совпадают с оценками свободных переменных исходной задачи , так как в формулах их расчета не участвуют свободные члены ограничений, а остальные параметры обеих задач совпадают

Значит, признак оптимальности выполняется и это есть оптимальное решение возмущенной задачи.

Первая часть леммы доказана.

Справедливость второй части (11) следует из того, что формулы расчета оптимальных решений задач, двойственных к I и I’ задач также совпадают.

Лемма доказана.

Область устойчивости двойственных оценок по отношению к изменению свободных членов ограничений – множество правых частей ограничений, при которых решение двойственной задачи не меняется. В силу доказанной леммы область устойчивости задается условием (9).

Теорема 3 (теорема об оценках, теорема о чувствительности): компоненты оптимального решения двойственной задачи являются оценками влияния свободных членов ограничений на оптимальное значение целевой функции.

Доказательство:

Рассмотрим оптимальное значение критерия как функцию от правых частей ограничений

По первой теореме двойственности критерии на оптимальных решениях прямой и двойственной задач равны

Будем рассматривать малые приращения правых частей ограничений, лежащие в области устойчивости двойственных оценок , тогда по доказанной выше лемме решение двойственной задачи не меняется и в правой части ( ) b_i – переменные, а y_i – константы.

Возьмем производную по b_i от левой и правой части ( ), получим

Это и есть соотношение (15).

Теорема доказана.

Экономическая интерпретация третьей теоремы двойственности

Если соотношение (15) выполняется, то .

То есть если ресурс изменился на 1 , то .

Из соотношения (17) следует, что компонента оптимального решения двойственной задачи показывает, на сколько изменится оптимальное значение критерия при увеличении ресурса на 1.

Двойственные переменные называют также двойственными оценками, модельными ценами, теневыми ценами.

Разлагая функцию оптимального значения критерия в ряд по формуле Тейлора в окрестности , получим

В области устойчивости двойственных оценок приращение критерия может быть получено по формуле (18)

Пример:

Для задачи из раздела 5.2 о работе предприятия по двум технологиям, определим, как изменится оптимальное решение при изменении объемов используемых ресурсов

Математическая модель задачи:

Найдем оптимальное решение этой задачи методом искусственного базиса.

Для этого строим расширенную задачу:

Решение в симплекс-таблицах:

Ранее было найдено оптимальное решение двойственной задачи:

Найти оптимальное решение данной задачи, если вектор ресурсов изменился:

,

Базисная матрица оптимального плана

Обратную к ней возьмем из оптимальной симплекс-таблицы под единичной матрицей исходной симплекс-таблицы

Св	Бп	x1	x2	x3	x4	x5	x6	b
	x3
	x1
	x2
	F

Проверим, что эти матрицы взаимно обратные:

Базисные компоненты решения измененной задачи

неотрицательны, значит по лемме 3 это базисные компоненты оптимального плана измененной задачи

В новых условиях по первой технологии следует работать 5 часов, по второй – 3 часа. Останется неиспользованной одна тонна первого ресурса.

Приращение оптимального значения критерия

Доход на новом оптимальном плане