Графический анализ чувствительности

Модель линейного программирования является как бы «моментальным снимком» реальной ситуации, когда параметры модели (коэффициенты целевой функции и неравенств ограничений) предполагаются неизменными. Естественно изучить влияние изменения параметров модели на полученное оптимальное решение задачи ЛП. Такое исследование называется анализом чувствительности.

В этом разделе анализ чувствительности основывается на графическом решении задачи ЛП. Рассмотрим два случая: (1) изменение коэффициентов целевой функции и (2) изменение значений констант в правой части неравенств ограничений. Хотя проведенное исследование будет элементарным и ограниченным, оно покажет основные идеи методов анализа чувствительности.

Изменение коэффициентов целевой функции

Применим процедуру анализа чувствительности к примеру 1.1. На рисунке 1.3 видно, что функция z =5x ₁ +4x ₂ достигает максимальное значение в угловой точке С. При изменении коэффициентов целевой функции z =с₁x ₁ +с₂x ₂ точка С останется оптимальной до тех пор, пока угол наклона линии z будет лежать между углами наклонов двух прямых, пересечением которых является точка С. Этими прямыми являются  (ограничение на сырье М1) и  (ограничение на сырье М2). Алгебраически это можно записать следующим образом:

или

Итак, если коэффициенты с₁ и с₂ удовлетворяют приведенным выше неравенствам, оптимальное решение будет достигаться в точке С.

Приведенные выше неравенства можно использовать при определении интервала оптимальности для какого-либо одного коэффициента целевой функции, если предположить, что другой коэффициент остается неизменным. Например, если в нашей модели зафиксировано значение коэффициента с₂=4, тогда интервал оптимальности для коэффициента с₁ получаем из неравенств
  путем подстановки туда значения с₂=4. После выполнения элементарных арифметических операций получаем неравенства для коэффициента с₁:2≤с₁≤6. Если зафиксировать значение с₁=5, тогда из неравенства
 получаем интервал оптимальности для с₂: 10/3 ≤ с₂ ≤10.

 

Рисунок 1.3 - Определение интервала оптимальности коэффициентов ЦФ

 

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

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

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

Начнем с ограничений для сырья М1. Напомним, что в данной задаче оптимальное решение достигается в угловой точке С, являющейся точкой пересечения прямых, соответствующих ограничениям на сырье М1 и М2 (рисунок 1.4). При изменении уровня доступности материала М1 (увеличения или уменьшения текущего уровня, равного 24т) точка С оптимального решения «плывет» вдоль отрезка DG. Любое изменение уровня доступности материала М1, приводящее к выходу точки пересечения С из этого отрезка, ведет к неосуществимости оптимального решения в точке С. Поэтому можно сказать, что концевые точки D =(2,2) и G =(6,0) отрезка DG определяют интервал осуществимости для ресурса М1. Количество сырья М1, соответствующего точке D =(2,2), равно 6х₁+4х₂=6 × 2+4 × 2=20 т. Аналогично количество сырья, соответствующего точке G =(6,0), равно 6х₁+4х₂=6 × 6+4 × 0=36 т. Таким образом, интервал осуществимости для ресурса М1 составляет 20≤М₁≤36 (здесь через М₁ обозначено количество материала М1). Если мы определим М₁ как М₁=24+ D ₁, где D ₁ - отклонение количества материала М1 от текущего уровня в 24т, тогда последнее неравенство можно переписать как 20≤24+ D ₁ ≤36 или -4≤ D ₁ ≤12. Это означает, что текущий уровень ресурса М1 может быть уменьшен не более чем на 4т и увеличен не более чем на 12т. В этом случае гарантируется, что оптимальное решение будет достигаться в точке С - точке пересечения прямых, соответствующих ограничениям на ресурсы М1 и М2.

 

Рисунок 1.4 - Нахождение интервала осуществимости для ресурса М1

 

Теперь вычислим стоимость единицы материала М1. При изменении количества сырья М1 от 20 до 36 тонн, значения целевой функции z будут соответствовать положению точки С на отрезке DG. Обозначим через y ₁ стоимость единицы ресурса М1, получим следующую формулу:

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

.

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

Теперь рассмотрим ресурс М2. На рисунке 1.5 видно, что интервал осуществимости для ресурса М2 определяется концевыми точками B и H отрезка BH, где B =(4,0) и H =(8/3,2). Точка H находится на пересечении прямых ED и BC. Находим, что количество сырья М2, соответствующее точке В, равно х₁+2х₂=1 × 4+2 × 0=4 т, а в точке H - х₁+2х₂=1 × 8/3+2 × 2=20/3 т. Значение целевой функции в точке В равно z =5 × 4+4 × 0=20 (тыс.руб.), а в точке H - z =5 × 8/3+4 × 2=64/3 (тыс.руб.). Отсюда следует, что количество сырья М2 может изменяться от 4 до 20/3 тонн, а стоимость единицы ресурса М2, обозначенная как y ₂, равна

.

 

Рисунок 1.5 - Нахождение интервала осуществимости для ресурса М2

 

 

Контрольные вопросы

1 Что подразумевается под графическим решением задачи ЛП?

2 Как определяются интервалы оптимальности для коэффициентов оптимальности для целевой функции графическим способом?

3 Как находятся интервалы осуществимости для ресурсов?

4 Как определяются стоимости ресурсов графически?

 

Тема 2 Симплекс-метод