logo

Решение контрольных по математике!!!

Home Методички по математике Линейное программирование 06. Анализ решения (модели) на чувствительность

06. Анализ решения (модели) на чувствительность

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

Пример 3.3.

Компания производит краску для внутренних и наружных работ из сырья двух типов: М1 и М2.

Необходимая информация представлена в следующей таблице:

Расход сырья

На 1 тонну краски

Максимально
возможный

Ежедневный
расход сырья

Для наружных работ

Для внутренних работ

Сырье М1

6

4

24

Сырье М2

1

2

6

Доход на тонну краски (тыс. дол.)

5

4

Отдел маркетинга компании ограничил ежедневное производство краски для внутренних работ до 2 т, а кроме того этот показатель не должен превышать более чем на тонну показатель выпуска краски для внешних работ.

Цель компании:

Определить оптимальное соотношение между видами выпускаемой продукции для максимизации общего ежедневного дохода.

Составленная математическая модель задачи выглядит следующим образом:

Максимизировать Z(x) = 5X1 + 4X2

При выполнении ограничений

6Х1 + 4Х2 ≤ 24

Х1 + 2Х2 ≤ 6

Х2 ≤ 2

X2 –X1 ≤ 1

Х1 ≥ 0

Х2 ≥ 0

В результате применения графического метода решения ЗЛП, рассмотренного в параграфе 3.2, получен график (рис. 3.6).

Рис. 3.6. Решение задачи

Решением задачи является точка с координатами: Х1 = 3;Х2 = 1,5. Целевая функция при таком решении принимает значение Z = 21 тыс. дол.

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

1) изменение коэффициентов целевой функции;

2) изменение значений констант в правой части неравенств-ограничений.

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

Максимизировать или минимизировать Z(X) = С1 X1 + C2 X2

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

На рис. 3.6 видно, что функция Z(x) = 5X1 + 4X2 достигает максимального значения в угловой точке С. При изменении коэффициентов целевой функции Z(x) = С1 X1 + C2 X2 точка С останется точкой оптимального решения до тех пор, пока угол наклона линии Z будет лежать между углами наклона двух прямых, пересечением которых является точка С. Этими прямыми являются 6Х1 + 4Х2 ≤ 24 (ограничение на сырье М1) и Х1 + 2Х2 ≤ 6 (ограничение на сырье М2). Алгебраически это можно записать следующим образом:

Или

.

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

Рис. 3.7. Интервал оптимальности

Итак, если коэффициенты С1 и С2 удовлетворяют приведенным выше неравенствам, оптимальное решение по-прежнему будет достигаться в точке С. Отметим, если прямая Z(x) = С1 X1 + C2 X2 совпадет с прямой Х1 + 2Х2 ≤ 6, то оптимальным решением будет любая точка отрезка CD. Аналогично, если прямая, соответствующая целевой функции, совпадет с прямой 6Х1 + 4Х2 = 24, тогда любая точка отрезка ВС будет оптимальным решением. Однако очевидно, что в обоих случаях точка С остается точкой оптимального решения.

Приведенные выше неравенства можно использовать при определении интервала оптимальности для какого-либо одного коэффициента целевой функции, если предположить, что другой коэффициент остается неизменным. Например, зафиксируем значение коэффициента С2 (пусть С2 = 4), тогда интервал оптимальности для коэффициента С1 получаем из неравенств путем подстановки туда значения С2 = 4. После выполнения элементарных арифметических операций получаем неравенства для коэффициента С1: 2 ≤ С1 ≤ 6.

Это означает, что при фиксированной цене на краску для внутренних работ цена на краску для наружных работ может меняться в интервале от 2 тыс. дол. за тонну до 6 тыс. дол. за тонну, при том, что оптимальное соотношение (решение) останется неизменным.

Аналогично, если зафиксировать значение коэффициента С1 (пусть С1 = 5), тогда из неравенства получаем интервал оптимальности для коэффициента С2: .

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

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

В данной задаче оптимальное решение достигается в точке С, являющейся точкой пересечения прямых, соответствующих ограничениям на сырье М1 и М2. При изменении уровня доступности материала М1 (увеличение или уменьшение текущего уровня, равного 24 т) точка С оптимального решения «плывет» вдоль отрезка DG (рис. 3.8).

Рис. 3.8

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

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

.

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

(тыс. дол. на тонну материала М1).

Этот результат показывает, что изменение количества ресурса М1 на одну тонну приводит к изменению в оптимальном решении значения целевой функции на 750 дол.

Рассмотрим ресурс М2. На рис. 3.9 видно, что интервал осуществимости для ресурса М2 определяется концевыми точками В и Н отрезка ВН, где В = (4,0) и Н = (8/3,2).

Рис. 3.9

Точка Н находится на пересечении прямых ЕD и ВС. Находим, что количество сырья М2, соответствующего точке В, равно Х1 + 2Х2 = 4 + 2 ´ 0 = 4т, а в точке Н – 20/3 т. Значение целевой функции в точке В равно Z = 5 ´ 4 + 4 ´ 0 = 20 тыс. дол., а в точке Н: Z = 5 ´ ´ 8/3 + 4 ´ 2 = 64/3 тыс. дол. Отсюда следует, что количество сырья М2 может изменяться от 4 до 20/3 тонн, а стоимость единицы ресурса М2, обозначенная как y2, равна (тысяч долларов на тонну материала М2).

 
Яндекс.Метрика
Наверх