нализ моделей на чувствительность

 

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

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

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

Рассматривают три задачи анализа на чувствительность:

1. На сколько можно увеличить или сократить запасы ресурсов?

2. Увеличение запаса какого из ресурсов наиболее выгодно?

3. Каков диапазон изменения коэффициентов целевой функции, при котором не меняется оптимальное решение?

Методику графического анализа чувствительности проиллюстрируем на примере следующей задачи ЛП:

(1)

(2)

(3)

.

Графическое решение данной задачи приведено на рис. 1.

Рис. 1

На рис. 1 видно, что задача ЛП имеет решение x *=(2, 1), при этом f (x *)=3. Ограничения (1) и (3) являются связывающими, а ограничение (2) – несвязывающим. Соответственно, 1-й и 3-й ресурсы являются дефицитными, а 2-й ресурс – недефицитным.

 

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

 

В рамках первой задачи анализа модели на чувствительность определяются:

1) предельно допустимое увеличение запаса дефицитного ресурса, позволяющее улучшить найденное оптимальное решение;

2) предельно допустимое снижение запаса недефицитного ресурса, не изменяющее найденное оптимальное решение.

Методика определения предельно допустимого увеличения запаса дефицитного ресурса заключается в следующем.

1. Перемещают прямую, соответствующую i -му связывающему ограничению, в направлении увеличения целевой функции до тех пор, пока это ограничение станет несвязывающим.

2. Определяют координаты точки , в которой i -е ограничение становится несвязывающим.

3. Подставляют координаты точки в левую часть i -го ограничения и вычисляют:

Обратимся к иллюстративному примеру. На рис. 2 видно, что при увеличении запаса 1-го ресурса прямая (1) перемещается по направлению градиента. Перемещение ограничено прямой (1′), проходящей через точку , являющуюся новым оптимальным решением. В точке ограничение становится несвязывающим, так как любой дальнейший рост запаса 1-го ресурса не влияет на оптимальное решение.

Координаты точки являются решением системы уравнений

x ₁+2 x ₂=4 [прямая(3)];

x ₂=0 [прямая(4)].

В результате получаем =(4, 0).

Подставляя координаты точки в левую часть ограничения (1), вычисляем максимально допустимый запас 1-го ресурса:

p ₁()=2×4+0=8.

Рис. 2

Целевая функция при этом равна

f ()=4+0=4.

На рис. 3 видно, что при увеличении запаса 3-го ресурса прямая (3) перемещается по направлению градиента до её предельного положения (3′), проходящего через точку , являющуюся новым оптимальным решением.

Координаты точки являются решением системы уравнений

2 x ₁+ x ₂=5 [прямая(1)];

3 x ₁ +4 x ₂=15 [прямая(2)].

В результате получаем =(1, 3).

Подставляя координаты точки в левую часть ограничения (3), вычисляем максимально допустимый запас 3-го ресурса:

P ₃()=1+2×3=7.

Целевая функция при этом равна

f ()=1+3=4.

Методика определения предельно допустимого уменьшения запаса недефицитного ресурса заключается в следующем.

 

Рис. 3

1. Перемещают прямую, соответствующую i -му несвязывающему ограничению, до пересечения с оптимальной точкой x *.

2. Подставляют координаты точки x * в левую часть i -го ограничения и вычисляют:

Из рис. 1 следует, что при уменьшении запаса 2-го ресурса прямая (2) перемещается против направления градиента. При этом оптимальное решение не изменится, если перемещение происходит до пересечения с оптимальной точкой x *=(2, 1).

Подставляя координаты точки x * в левую часть ограничения (2), вычисляем минимально допустимый запас 2-го ресурса:

p ₂(x *)=3×2+4×1=10.

 

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

 

Для оценки выгодности увеличения запаса i -го ресурса используют такой показатель, как ценность дополнительной единицы ресурса y_i. Величина y_i определяется из соотношения

где – максимальное приращение оптимального значения целевой функции;

– максимальное приращение объема i -го ресурса.

Как следует из изложенного выше, для i -го дефицитного ресурса имеем

для i -го недефицитного ресурса имеем

Результаты вычислений для рассматриваемого примера представлены в табл. 4.

Таблица 4

 

Ресурс	Тип ресурса	Максимальное изменение запаса ресурса	Максимальное изменение целевой функции	Ценность дополнит. единицы ресурса
	Дефицитный	8-5=3	4-3=1	y 1=1/3
	Недефицитный	10-15=-5	3-3=0	y 2=0
	Дефицитный	7-4=3	4-3=1	y 3=1/3

 

Полученные результаты свидетельствуют о том, что дополнительные вложения можно направить как на увеличение запаса 1-го ресурса, так и на увеличение запаса 3-го ресурса, поскольку оба ресурса равноценны. Запас 2-го ресурса увеличивать не следует.

 

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

 

Изменение коэффициентов целевой функции приводит к вращению целевой прямой c ₁ x ₁+ c ₂ x ₂= f (x ^*) вокруг точки x ^* оптимального решения. При увеличении c ₁или уменьшении c ₂целевая прямая вращается по часовой стрелке; при уменьшении c ₁или увеличении c ₂целевая прямая вращается против часовой стрелке (рис. 4). Таким образом, точка x ^* будет оставаться оптимальной до тех пор, пока наклон целевой прямой не выйдет за пределы, определяемые наклонами прямых, соответствующих связывающим ограничениям (ограничениям (1) и (3) на рис. 4). Как только наклон целевой прямой выйдет за пределы указанного диапазона, получим некоторое новое оптимальное решение (точка (2,5; 0) или точка (0, 2) на рис. 4).

Рис. 4

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

Обозначим через α ₀ угол наклона целевой прямой к оси абсцисс, через α_i – угол наклона прямой i- го, ограниченияк оси абсцисс.

Нетрудно заметить, что

tg α ₀= c ₁/ c ₂;

tg α_i = a_{i 1}/ a_{i 2},

Методика определения границ допустимого диапазона изменения коэффициента c_j, j =1,2, заключается в следующем.

1. Фиксируют значение второго коэффициента целевой функции.

2. Приравнивают тангенс угла наклона целевой прямой поочередно к тангенсам углов наклона прямых для связывающих ограничений.

Обратимся к иллюстративному примеру. Определим границы допустимого диапазона изменения c ₁ – min c ₁ и max c ₁.

Зафиксируем c ₂=1. На рис. 4 видно, что min c ₁ определяется из условия совпадения целевой прямой с прямой (3):

tg α ₀= tg α ₃, → c ₁/ c ₂= a ₃₁/ a ₃₂ → min c ₁=1/2,

а max c ₁ определяется из условия совпадения целевой прямой с прямой (1):

tg α ₀= tg α ₁, → c ₁/ c ₂= a ₁₁/ a ₁₂ → max c ₁=2.

Таким образом, если коэффициент c ₁ целевой функции будет изменяться в диапазоне 1/2< c ₁<2, то оптимальное решение задачи не изменится. Если c ₁ станет меньше 1/2 (c ₁<1/2), то оптимальным решением станет точка (0, 2); если c ₁ станет больше 2 (c ₁>2), то оптимальным решением станет точка (2,5; 0).

 

5. ТРЕБОВАНИЯ К ОФОРМЛЕНИЮ

ПОЯСНИТЕЛЬНОЙ ЗАПИСКИ

Пояснительная записка должна быть выполнена на пронумерованных листах формата А4. Её оформление должно удовлетворять требованиям ГОСТа.

Содержание пояснительной записки:

1. Краткое описание задания.

2. Описание варианта; данные, соответствующие конкретному варианту.

3. Четко оформленные результаты и выводы по каждому из пунктов а, б, в, г.

4. Сводная таблица результатов, выводы и рекомендации по совокупности результатов всех пунктов.

В выводах должны содержаться ответы на вопросы задания.

 

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Таха Х. Введение в исследование операций: В 2-х кн. – М.: Мир, 1985.

2. Зайченко Ю.П. Исследование операций. – Киев: Вища школа, 1979.

3. Алесинская Т.В. Учебное пособие по решению задач по курсу «Экономико-математические методы и модели». – Таганрог: Изд-во ТРТУ, 2002.

СОДЕРЖАНИЕ

1. Цель работы ………………………………….……………..…....3

2. Описание задания ……………………………………………….3

3. Варианты заданий ………………………………………………4

4. Теоретическая часть …………………………………………..14

4.1. Двойственный симплекс-метод………………………………14

4.2. Анализ моделей на чувствительность………………………..17

5. Требования к оформлению пояснительной записки ………24

Библиографический список ……………………………………...24