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

Теорема 1.7.5 (Теорема об оценках)

Двойственные оценки показывают приращение целевой функции , вызванное малым изменением свободного члена соответствующего ограничения, т.е.

Если задача (1.5) не вырожденная, то существует окрестность U (b) точки такая, что для любой точки . Здесь - оптимальный план в двойственной задаче (1.6).

Если , то оптимальный план двойственной задачи не изменится, а целевая функция исходной задачи изменится следующим образом

.

В частности, если , то

.

В этом случае величина оптимальной двойственной оценки равна приращению целевой функции на оптимальном плане при увеличении i –го ресурса на одну единицу.

Анализ модели на чувствительность – это процесс, реализуемый после того, как оптимальный план найден. При этом выявляется чувствительность оптимального плана к изменению параметров модели. Например: увеличение или уменьшение спроса, изменение запасов ресурса по сравнению с планируемым, изменение цен на продукцию.

Первая задача анализа на чувствительность.

Увеличение какого из ресурсов даст наиболее быстрый рост целевой функции.

Вторая задача на чувствительность.

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

Третья задача на чувствительность.

В каких пределах допустимого изменение j –го коэффициента целевой функции с тем, чтобы план выпуска остался оптимальным.

Рассмотрим проведение анализа на чувствительность на примере задачи о красках.

В пункте 1.5 было получено решение этой задачи . Так как при этом ограничения по спросу не исчерпаны (не являются дефицитными), то руководство предприятия решает увеличить производство краски. С этой целью решено построить еще одну емкость для одного из исходных продуктов. Нужно определить, для какого из исходных продуктов следует построить дополнительную емкость, и какого размера. Для решения первой задачи анализа на чувствительность нам понадобятся двойственные оценки . Найдем двойственные оценки на основании теоремы 1.7.4. Из соотношений (1.9) для нашей задачи

получаем, что

. (1.12)

Для нахождения остальных оценок рассмотрим соотношения (1.10). В нашей задаче они имеют вид

Учитывая соотношения (1.12), получаем систему двух уравнений с двумя неизвестными

Решая эту систему, получаем

И так, увеличение первого ресурса (запаса исходного продукта A) на одну единицу приведет к увеличению целевой функции на четыре единицы, а увеличение на одну единицу второго ресурса (исходного продукта B) приведет к увеличению целевой функции только на одну единицу. Следовательно, отвечая на первую задачу анализа на чувствительность, нужно строить емкость для исходного продукта A. Для графического расчета объема новой емкости обратимся к рисунку 1 пункта 1.5

Выделим на этом рисунке жирно линию, соответствующую первому ограничению задачи (ограничению по исходному продукту A).

(1.13)

Увеличение запаса этого продукта соответствует увеличению правой части уравнения на некоторую величину .

(1.14)

При этом линия будет параллельно сдвигаться вверх и вправо. Целевая функция при этом перемещении будет расти, пока прямая не достигнет точки M (на рис.2 жирная пунктирная линия). Дальнейшее увеличение первого ресурса не приведет к росту целевой функции, так как другие ограничения (в нашей задаче второй ресурс и неотрицательность величины ) не дадут возможности увеличивать производство. Теперь величину новой емкости (величину ) нужно найти из условия прохождения прямой (1.14) через точку M. Эта точка является точкой пересечения двух прямых:

Следовательно, M = (0; 18). Тогда

,

Величина будет равна 4. Таким образом, нужно построить новую емкость для исходного продукта A объемом 4 единицы, при этом новый оптимальный план будет .

Рассмотрим на этом же примере решение третьей задачи анализа на чувствительность. Вернемся снова к найденному оптимальному плану и найдем интервал изменения цены на краску K ₁, при котором этот план останется оптимальным. Запишем уравнение линии уровня целевой функции с неизвестной ценой на краску K ₁.

. (1.15)

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

. (1.16)

Решая уравнение (1.16) получаем нижнюю границу цены = 1.5

Верхнюю границу для величины найдем из условия параллельности линии уровня (1.15) и прямой, задающей границу второго ограничения

.

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

Задание для самостоятельного решения. Проведите анализ на чувствительность оптимальных планов в задачах 1.8, 1.9 пункта 1.6.

Дата добавления: 2014-12-27