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

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

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

В обшем виде целевую функцию задачи ЛП с двумя переменными можно записать следующим образом.

Максимизировать или минимизировать z = с1x1 + с2х2
Изменение значений коэффициентов c1 и с2 приводит к изменению угла наклона прямой z. Графический способ решения задачи ЛП. описанный в разделе 2.3, показывает, что это может привести к изменению оптимального решения: оно будет достигаться в другой угловой точке пространства решений. Вместе с тем, очевидно, существуют интервалы изменения коэффициентов c1 и с2, когда текущее оптимальное решение сохраняется. Задача анализа чувствительности и состоит в получении такой информации. В частности, представляет интерес определение интервала оптимальности для отношения c1/c2 (или, что то же самое, для c2/c1); если значение отношения c1/c2 не выходит за пределы этого интервала, то оптимальное решение в данной модели сохраняется неизменным. Следующий пример показывает, как можно получить необходимый результат с помощью анализа графического представления модели ЛП.

Пример


На рис. видно, что функция z = 5х1 + 4х2 достигает максимального значения в угловой точке С. При изменении коэффициентов целевой функции z = c1x1 + с2х2 точка С останется точкой оптимального решения до тех пор, пока угол наклона линии z будет лежать между углами наклона двух прямых, пересечением которых является точка С. Этими прямыми являются 6x1+4х2=24 (ограничение на сырье M1) и x1+2х2=6 (ограничение на сырье М2). Алгебраически это можно записать следующим образом:
c1≠0,
или
c2≠0.
В первой системе неравенств условие c1≠0 означает, что прямая, соответствующая целевой функции, не может быть горизонтальной. Аналогичное условие в следующей системе неравенств означает, что эта же прямая не может быть вертикальной. Из рис. 2.4 видно, что интервал оптимальности данной задачи (он определяется двумя прямыми, пересекающимися в точке С) не разрешает целевой функции быть ни горизонтальной, ни вертикальной прямой. Таким образом, мы получили две системы неравенств, определяющих интервал оптимальности в нашем примере. (Когда с1 и с2 могут принимать нулевые значения, интервал оптимальности для отношения с12 (или с21) необходимо разбить на два множества, где знаменатели не обращались бы в нуль. Эта ситуация представлена в упр. 2.4,а(1).)

Итак, если коэффициенты с1 и с2 удовлетворяют приведенным выше неравенствам, оптимальное решение будет достигаться в точке С. Отметим, если прямая z = c1x1 + c2x2 совпадет с прямой х1 + 2х2 = 6. то оптимальным решением будет любая точка отрезка CD. Аналогично, если прямая, соответствующая целевой функции, совпадет с прямой 6х1 + 4x2 = 24, тогда любая точка отрезка ВС будет оптимальным решением. Однако заметим, что в обоих случаях точка С остается точкой оптимального решения.
Приведенные выше неравенства можно использовать при определении интервала оптимальности для какого-либо одного коэффициента целевой функции, если предположить, что другой коэффициент остается неизменным. Например, если в нашей модели зафиксировано значение коэффициента с2 (пусть с2=4), тогда интервал оптимальности для коэффициента c1 получаем из неравенств путем подстановки туда значения с2 = 4. После выполнения элементарных арифметических операций получаем неравенства для коэффициента с1: 2≤с1≤6. Аналогично, если зафиксировать значение коэффициента с1 (например, с1 = 5), тогда из неравенств получаем интервал оптимальности для коэффициента с2: 10/3 ≤ с2 ≤ 10.

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

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

В пример первые два неравенства представляют собой ограничения на использование сырья M1 и М2 соответственно. Определим стоимость единиц этих ресурсов.
Начнем с ограничения для сырья M1. Напомним, что в данной задаче оптимальное решение достигается в угловой точке С, являющейся точкой пересечения прямых, соответствующих ограничениям на сырье M1 и М2 (рис. 2.5). При изменении уровня доступности материала M1 (увеличение или уменьшение текущего уровня, равного 24 т) точка С оптимального решения "плывет" вдоль отрезка DC. Любое изменение уровня доступности материала M1, приводящее к выходу точки пересечения С из этого отрезка, ведет к неосуществимости оптимального решения в точке С. Поэтому можно сказать, что концевые точки D = (2,2) и G = (6,0) отрезка DG определяют интервал осуществимости для ресурса M1. Количество сырья M1, соответствующего точке D= (2,2), равно 6x1+4x2 = 6·2+ 4·2 = 20 т. Аналогично количество сырья, соответствующего точке G = (6,0), равно 6·6 + 4·0 = 36т. Таким образом, интервал осуществимости для ресурса M1 составляет 20≤M1≤36 (здесь через М1 обозначено количество материала M1). Если мы определим М1 как М1 = 24 + D1, где D1 — отклонение количества материала М1 от текущего уровня в 24 т, тогда последние неравенства можно переписать как 20 ≤ 24 + D1 ≤ 36 или -4 ≤ D1 ≤ 12. Это означает, что текущий уровень ресурса M1 может быть уменьшен не более чем на 4 т и увеличен не более чем на 12 т. В этом случае гарантируется, что оптимальное решение будет достигаться в точке С — точке пересечения прямых, соответствующих ограничениям на ресурсы M1 и М2.

Теперь вычислим стоимость единицы материала M1. При изменении количества сырья M1 от 20 до 36 тонн, значения целевой функции z будут соответствовать положению точки С на отрезке DC. Обозначив через у1 стоимость единицы ресурса M1, получим следующую формулу.
y1 = изменение значения z при перемещении т. C от D до G / изменение количества M1 при перемещении т. C от D до G
Если точка С совпадает с точкой D = (2, 2), то z=5·2+4·2= 18 (тысяч долларов), если же точка С совпадает с точкой G = (6,0), тогда z = 5·6 + 4·0 = 30 (тысяч долларов). Отсюда следует, что
(тысяч долларов на тонну материала М1).
Этот результат показывает, что изменение количества ресурса M1 на одну тонну (если общее количество этого ресурса не меньше 20 и не больше 36 тонн) приводит к изменению в оптимальном решении значения целевой функции на $750.
Теперь рассмотрим ресурс М2. На рис. 2.6 видно, что интервал осуществимости для ресурса М2 определяется концевыми точками B и H отрезка ВH, где B = (4,0) и H = (8/3,2). Точка H находится на пересечении прямых ED и ВС. Находим, что количество сырья M2, соответствующего точке В, равно x1 + 2x2 =4 + 2·0 = 4 т, а точке H— 8/3 + 2·2 = 20/3 т. Значение целевой функции в точке В равно 5x1 + 4х2 = 5·4 + 4·0 = 20 (тысяч долларов), а в точке H—5·8/3 + 4·2 = 64/3 (тысяч долларов). Отсюда следует, что количество сырья М2 может изменяться от 4 до 20/3 тонн, а стоимость единицы ресурса М2, обозначенная как у2, равна
(тысяч долларов на тонну материала М2).

см. также Анализ эффективности оптимального решения задачи графическим методом

загрузка...