Смекни!
smekni.com

Исследование математических операций 2 (стр. 7 из 28)

Рис. 2.3. Оптимум функции Z недостижим


Рис. 2.4. Область допустимых решений – пустая область

Для практического решения задачи линейного программирования (2.34) – (2.36) на основе ее геометрической интерпретации необходимо следующее:

1. Построить прямые, уравнения которых получаются в результате замены в ограничениях (2.35) – (2.36) знаков неравенств на знаки равенств.

2. Найти полуплоскости, определяемые каждым из ограничений.

3. Определить многоугольник решений.

4. Построить вектор

.

5. Построить прямую

, проходящую через начало координат и перпендикулярную вектору
.

6. Передвигать прямую Z в направлении вектора

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

7. Определить точки координаты максимума функции и вычислить значение целевой функции в этой точке.

Пример 2.9. Рассмотрим решение задачи об ассортименте продукции (пример 2.2) геометрическим способом.

Решение

Построим многоугольник решений (рис.2.5). Для этого в системе координат X10X2 на плоскости изобразим граничные прямые:

1 + 3х2 = 9 (L1);

1 + 2х2 = 13 (L2);

х1 - х2 = 1 (L3);

х2 = 2 (L4).

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

Для построения прямой Z = 3х1 + 4х2 = 0 строим вектор-градиент

и через точку 0 проводим прямую, перпендикулярную ему. Построенную прямую Z = 0 перемещаем параллельно самой себе в направлении вектора
. Из рис. следует, что по отношению к многоугольнику решений опорной эта прямая становится в точке C, где функция принимает максимальное значение. Точка С лежит на пересечении прямых L1 и L3. Для определения ее координат решим систему уравнений:

Оптимальный план задачи х1=2,4; х2=1,4. Подставляя значения х1 и х2 в линейную функцию, получим:

.

Полученное решение означает, что объем производства продукции П1 должен быть равен 2,4 ед., а продукции П2 – 1,4 ед. Доход, получаемый в этом случае, составит: Z = 12,8 д.е.

Рис. 2.5. Решение задачи линейного программирования геометрическим способом

Назад | Содержание | Далее

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

Анализ моделей на чувствительность — это процесс, реализуе­мый после получения оптимального решения. В рамках такого анализа выявляется чувствительность оптимального решения к опре­деленным изменениям исходной модели. В задаче об ассортименте продукции (пример 2.2) может представлять интерес вопрос о том, как повлияет на оптимальное решение увеличение и уменьшение спроса на продукцию или запасов исходного сырья. Возможно, также потребуется анализ влияния рыночных цен на оптимальное решение.

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

Рассмотрим основные задачи анализа на чувствительность на примере 2.9.

Задача 1. Анализ изменений запасов ресурсов.

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

1. На сколько можно увеличить запас некоторого ресурса для улучшения полученного оптимального значения целевой функ­ции Z?

2. На сколько можно снизить запас некоторого ресурса при со­хранении полученного оптимального значения целевой функции Z?

Прежде чем ответить на поставленные вопросы, классифицируем ограничение линейной модели как связывающие (активные) и несвязывающие (неактивные) ограничения. Прямая, представляющая связывающее ограничение, должна проходить через оптимальную точку, в противном случае, соответствующее ограничение будет несвязываюшим. На рис. 2.5 связывающими ограничениями являются ограничения (1) и (3), представленные прямыми L1 и L3 соответственно, т.е. те, которые определяют запасы исходных ре­сурсов. Ограничение (1) определяет запасы сырья А. Ограничение (3) определяет соотношение спроса на выпускаемую продукцию.

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

При анализе модели на чувствительность к правым частям ог­раничений определяются: 1) предельна допустимое увеличение за­паса дефицитного ресурса, позволяющее улучшить найденное оп­тимальное решение, и 2) предельно допустимое снижение запаса недефицитного ресурса, не изменяющее найденное ранее опти­мальное значение целевой функции.

В нашем примере сырье А и соотношение спроса на выпускае­мую продукцию П1 и П2 являются дефицитными ресурсами (в таб­лице - ресурсы 1, 3).

Рассмотрим сначала ресурс - сырье А. На рис. 2.6 при увеличе­нии запаса этого ресурса прямая L1 перемещается вверх, парал­лельно самой себе, до точки К, в которой пересекаются линии ог­раничений L2, L3 и L4. В точке К ограничения (2), (3) и (4) стано­вятся связывающими; оптимальному решению при этом соответст­вует точка К, а пространством (допустимых) решений становится многоугольник AKD0. В точке К ограничение (1) (для ресурса А) становится избыточным, так как любой дальнейший рост запаса соответствующего ресурса не влияет ни на пространство решений, ни на оптимальное решение.

Рис. 2.6. Геометрическая интерпретация решения задачи линейного программирования (изменение ресурса А)

Таким образом, объем ресурса А не следует увеличивать сверх того предела, когда соответствующее ему ограничение (1) стано­вится избыточным, т.е. прямая (1) проходит через новую опти­мальную точку К. Этот предельный уровень определяется следую­щим образом. Устанавливаются координаты точки К, в которой пересекаются прямые L2, L3 и L4, т.е. находится решение системы уравнений

.

В результате получается х1 = 3 и х2 = 1. Затем, путем подста­новки координат точки К в левую часть ограничения (1), определя­ется максимально допустимый запас ресурса А:

.

Рис. 2.7иллюстрирует ситуацию, когда рассматривается вопрос об изменении соотношения спроса на продукцию П1 и П2.

Рис. 2.7. Геометрическая интерпретация решения задачи линейного программирования (изменение спроса на продукцию)

Новой оптимальной точкой становится точка Е, где пересека­ются прямые L1 и L2. Координаты данной точки находятся путем решения системы уравнений (1) и (2) следующим образом:

.

В результате получается х1 = 4,2; х2 = 0,2, причем суточный спрос на продукцию П1 не должен превышать спрос на продукцию П2 на величину х1 - х2 = 4,2 -0,2= 4 ед.

Дальнейшее увеличение разрыва в спросе на продукцию П1 и П2 не будет влиять на оптимальное решение.

Рассмотрим вопрос об уменьшении правой части несвязываю­щих ограничений. Ограничение (4) фиксирует предельный уровень спроса на продукцию П2 . Из рис. 2.5 следует, что, не из­меняя оптимального решения, прямую L4 (АВ) можно опускать вниз до пересечения с оптимальной точкой С. Так как точка С име­ет координаты х1 = 4,2; х2 =1,4 уменьшение спроса на продукцию П2 до величины х2 =1,4 никак не повлияет на оптимальность ра­нее полученного решения.