2.3.2. Доступность ресурсов

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

Пример 2.3.2

В модели для компании Reddy Mikks (пример 2.2.1) первые два неравенства представляют собой ограничения на использование сырья Ml и М2 соответственно. Напомним, что в данной задаче оптимальное решение достигается в угловой точке С, являющейся точкой пересечения прямых, соответствующих ограничениям на сырье Ml и М2 (рис. 2.6). При изменении уровня доступности материала Ml (увеличение или уменьшение текущего уровня, равного 24 т) точка С оптимального решения плывет вдоль отрезка DG. Любое изменение уровня доступности материала Ml, приводящее к выходу точки пересечения С из этого отрезка, ведет к неосуществимости оптимального решения в точке С. Поэтому можно сказать, что конечные точки 0=(2,2)иС= (6, 0) отрезка DG определяют интервал осуществимости для ресурса Ml. Количество сырья Ml, соответствующего точке D = (2, 2), равно бх, + 4х2 = 6x2+4x2 = 20 т. Аналогично количество сырья, соответствующего точке G = (6, 0), равно 6x6 + 4x0 = 36т. Таким образом, интервал осуществимости для ресурса Ml составляет 20 < Mt < 36 (здесь через Ml

Рис. 2.6. Интервал осуществимости для ресурса Ml

обозначено количество материала Ml). Если мы определим М, как Л/, = 24 + Dv где Dj - отклонение количества материала Ml от текущего уровня в 24 т, то последние неравенства можно переписать как 20 < 24 + D; < 36 или -4 < D, < 12. Это означает, что текущий уровень ресурса Ml может быть уменьшен не более чем на 4 т и увеличен не более чем на 12 т. В этом случае гарантируется, что оптимальное решение будет достигаться в точке С- точке пересечения прямых, соответствующих ограничениям на ресурсы Ml и М2.

Теперь рассмотрим ресурс М2. На рис. 2.7 видно, что интервал осуществимости для ресурса М2 определяется конечными точками В и Н отрезка ВН, где В = (4, 0) и Н = (8/3, 2). Точка Н находится на пересечении прямых ED и ВС. Определяем, что количество сырья М2, соответствующего точке В, равно л:, + 2х2 = 4 + 2x0=4 т, а точке Н- 8/3 + 2x2= 20/3т. Значение целевой функции в точке В равно 5х1 + 4х2 = 5x4 + 4x0 = 20 (тыс. долл.), а в точке Н - 5 х 8/3 + 4x2 = 64/3 (тыс. долл.). Отсюда следует, что количество сырья М2 может изменяться от 4 до 20/3 тонн.

2 Интервал осуществимости для материала М2

Рис. 2.7. Интервал осуществимости для ресурса М2

2.3.3. Стоимость ресурсов

На рис. 2.8 показано, что модель ЛП можно представить как модель вход-выход , где ограниченные ресурсы соответствуют входу модели, а значение целевой функции - выходу. Чувствительность модели можно оценить по степени влияния входа (ресурсов) на выход (значение целевой функции). Простую меру чувствительности можно получить как побочный продукт вычисления интервалов осуществимости для ресурсов, выполненного в разделе 2.3.2. В частности, определим стоимость единицы ресурса, как отношение изменения значения целевой функции к изменению доступного количества ресурсов.

Обозначим через yt стоимость ресурса i. Эта стоимость вычисляется по формуле изменение значения z, соответствующего интервалу осуществимости ресурса i интервал осуществимости ресурсаi

Проиллюстрируем этот показатель на примере модели Reddy Mikks.

Ресурсы модели

Значение целевой функции модели

Рис. 2.8. Представление модели ЛП как модели вход-выход

Пример 2.3.3

На рис. 2.6 видно, что при изменении количества сырья Ml от 20 до 36 тонн (интервал осуществимости ресурса Ml) значения целевой функции z будут соответствовать положению точки Сна отрезке DG. Обозначив через у, стоимость единицы ресурса Ml, получим следующую формулу.

изменение значения z при перемещении т. С от D до G

У1 =

изменение количества Л/, при перемещении т. С от D до G

Если точка С совпадает с точкой D = (2, 2), то z = 5 х 2 + 4 х 2 = 18 (тыс. долл.), если же точка С совпадает с точкой G = (6, 0), тогда г = 5х6 + 4х0 = 30 (тыс. долл.). Отсюда следует, что

30 - 18 з

у, =--- = - (тыс. долл. на тонну материала Ml).

Этот результат показывает, что изменение количества ресурса Ml на одну тонну (если общее количество этого ресурса не меньше 20 и не больше 36 тонн) приводит к изменению в оптимальном решении значения целевой функции на 750 долл. Теперь рассмотрим ресурс М2. Для него интервал осуществимости составляет от 4 до 20/3 тонн. На рис. 2.7 видно, что этот интервал определяется конечными точками В и Я отрезка ВН. Таким образом,

изменение значения z при перемещении т. С от В до

У г

изменение количества Л/, при перемещении т. С от В до

Значение целевой функции в точке В равно 5х, + 4х, = 5x4 + 4x0 = 20 (тыс. долл.), а в точке Н - 5 х 8/3 + 4 х 2 = 64/3 (тыс. долл.). Отсюда следует, что

64/3-20 1 . ил1

у, = -- = - (тыс. долл. на тонну материала М2).

Этот результат показывает, что изменение количества ресурса М2 на одну тонну (если общее количество этого ресурса не меньше 4 и не больше 20/3 тонн) приводит к изменению в оптимальном решении значения целевой функции на 500 долл.