Основы исследования операций (стр. 8 )

Статус ресурсов можно также оценить по значению двойственных переменных в оптимальном решении (на основе второй теоремы двойственности). Оценки красителей к1и к2 () положительны, следовательно, запасы этих красителей полностью используются и они относятся к "дефицитным" ресурсам.

6.4.2. Определение значимости ресурсов (факторов производства)

Значимость ресурса характеризуется величиной улучшения оптимального значения целевой функции , приходящейся на единицу прироста этого ресурса. Как следует из теоремы об оценках, значимость ресурса всегда можно определить по значению двойственных переменных в оптимальном решении, ибо В нашем примере Следовательно, из двух дефицитных факторов производства (красители к1 и к2, краситель к2 имеет большую значимость с точки зрения получения прибыли. Если объем красителя к1 увеличить на 1, то прибыль f(x1,x2) возрастет на Df=1´1/3=0.33, а при увеличении объемов красителя к2 на единицу, прибыль увеличится на Df = 1´y2= 1´4/3 = 1.33.

6.4.3. Определение допустимого интервала изменения запасов ресурсов

При анализе модели представляет интерес исследование следующих вопросов:

1.  Насколько можно увеличить запас некоторого дефицитного ресурса для улучшения полученного оптимального решения так, чтобы технология производства и статус ресурсов остались неизменными.

2.  Насколько можно снизить запас недефицитного ресурса при сохранении полученного оптимального значения целевой функции.

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

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

(6.7)

Легко показать, что изменение правых частей ограничений исходной задачи будет оказывать влияние только на элементы столбца свободных членов симплексной таблицы, матрицаВ при этом остается неизменной. Следовательно, если выбираем новый вектор ресурсов , то соответствующее ему оптимальное решение задачи

(6.8)

где – столбец свободных членов в оптимальной симплексной таблице.

Чтобы новое базисное решение осталось допустимым необходимо, чтобы все компоненты вектора были неотрицательны, т. е. Из вышесказанного следует следующее правило вычисления допустимого интервала изменений правых частей ограничений:

1.  Изменим свободный член в некотором ограничении, например, полагаем

2.  Вычисляем новое базисное решение

(6.9)

Компоненты нового базисного решения зависят от Di.

3.  Решаем систему неравенств:

(6.10)

Решением системы неравенств (6.10) будет допустимый интервал изменения свободного члена в i-ом ограничении.

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

Проиллюстрируем вышеизложенное на рассматриваемом примере.

Краситель к2, используемый для изготовления красок является "дефицитным", причем имеет наибольшую значимость. Определим диапазон допустимых изменений объема запасов этого ресурса.

Оптимальная симплексная таблица представлена ранее в табл.1.

Так как начальными базисными переменными являлись x3, x4, x5, x6, то в оптимальной симплексной таблице в соответствующих столбцах расположена матрица B-1

Изменим запас ресурса к2 на D2, тогда его новый объем 8+D2.

Найдем оптимальное решение, соответствующее измененным значениям объема ресурса к2

Легко заметить, что новая правая часть (bi*) каждого ограничения представляет сумму двух величин: постоянной и члена, линейно зависимого от D2.

Постоянная часть совпадает с элементами столбца свободных членов в оптимальной симплексной таблице (соответствует компонентам оптимального решения до изменения объемов ресурсов). Коэффициенты при D2 совпадают с элементами столбца для x4 в оптимальной симплексной таблице (x4 – дополнительная базисная переменная ограничения, соответствующего ресурсу к2).

Для того, чтобы было допустимым, необходимо, чтобы выполнялись условия:

Отсюда следует, что

Таким образом, первоначальный запас красителя к2 (8 кг) может быть увеличен до 12 кг или уменьшен до 6 кг без нарушения допустимости решения и статуса ресурсов.

6.4.4. Исследования зависимости оптимального значения целевой функции от изменения запаса ресурсов

По теореме об оценках В диапазоне допустимых изменений свободных членов это условие можно записать следующим образом:

Так как в этом диапазоне двойственные оценки остаются неизменными, то изменение целевой функции будет линейно зависеть от изменений запасов ресурсов.

В нашем примере В таблице 2 отражено изменение дохода от реализации в зависимости от изменения объемов использования красителя к2

Таблица 2

D2 (кг)	0	1	2	3	4
b2(кг)	8	9	10	11	12
Df(т. руб.)	0	4/3	8/3	12/3	16/3
f (т. руб.)	38/3	42/3	46/3	50/3	54/3

Уменьшение объемов использования "дефицитного" ресурса к2 нецелесообразно, так как приведет к уменьшению прибыли.

6.5. Геометрическая интерпретация анализа модели

Найдем решение задачи графическим методом (рис. 2).

рис. 2

OABCD – область допустимых решений.

– вектор градиента целевой функции.

Оптимальное решение находится в точкеС (10/3, 4/3). ТочкаС является пересечением первой и второй ограничивающих прямых. Эти прямые называют связывающими или активными, они соответствуют "дефицитным" ресурсам. Если менять объем использования "дефицитного" ресурса, то соответствующая прямая будет передвигаться параллельно самой себе. При этом возможны следующие случаи:

1)  до некоторого изменения объема ресурса (свободного члена в ограничении) прямая остается связывающей, тогда интересно определить интервалы изменения запасов ресурса.

2)  прямая перестает быть связывающей, что соответствует смене базиса в оптимальном решении и статуса ресурсов.

Будем увеличивать объем использования красителя к2, тогда прямая CD будет передвигаться вверх параллельно самой себе. Чтобы не изменились статус и значимость ресурсов, это движение допустимо пока прямые CD и BC остаются связывающими, то есть до точки F. Прохождение прямой CD через точку F соответствует b2=12, то есть границе допустимых изменений объемов второго ресурса.

В точке F(6,0) то есть прибыль по сравнению с найденным оптимальным решением (точка C) увеличится на

Допустимому объему использования первого ресурса соответствует движение связывающей прямой BC до точки E(3,2). В точке E все ограничивающие прямые становятся связывающими, , что соответствует увеличению прибыли на Действительно, в точке E объем использования первого ресурса увеличивается на то есть