Упражнения, для закрепления понимания понятия - пространство решений

Упражнение 1.2. Используя рисунок 1.3. проверьте, являются ли допустимыми следующие решения:

х ₁ = 1, х ₂= 4_________________________________________________________________

х ₁ = 2, х ₂= 3_________________________________________________________________

х ₁ = 10/3, х ₂= 4/3_____________________________________________________________

х ₁ = 2, х ₂= 1_________________________________________________________________

х ₁ = 1, х ₂= 4_________________________________________________________________

Упражнение 1.3. Используя рисунок 1.3, рассмотрите допустимое решение х₁ = 1, х₂ = 2. Определите указанные ниже величины.

1. Остаток (неиспользованную часть) исходного продукта А:___________________

2. Остаток исходного продукта В:__________________________________________

Упражнение 1.4. Определите, какое из допустимых решений упражнения 1.2. является наилучшим.

___________________________________________________________________________

Упражнение 1.5. Как вы считаете сколько допустимых решений имеет рассматриваемая задача?

___________________________________________________________________________

Упражнение 1.6. Определите пространство решений и найдите оптимальное решение задачи № 1, считая, что каждое из указанных ниже условий заменяет, а не дополняет соответствующие исходные данные, причем все остальные заданные соотношения остаются неизменными. Решите графически

1. Максимальный спрос на краску №2 равен 3 т в сутки. Используйте рисунок 1.4.

Напишите новое ограничение:_____________________________________________

2. Спрос на краску №2 не менее 2 т в сутки. Используйте рисунок 1.5.

Напишите новое ограничение:_____________________________________________

3. Спрос на краску №2 ровно на 1 т превышает спрос на краску №1. Используйте рисунок 1.6.

Напишите новое ограничение:_____________________________________________

4. Допустимый расход исходного продукта В не меньше 8 т в сутки. Используйте рисунок 1.7.

Напишите новое ограничение:_______________________________________________

5. Допустимый суточный расход исходного продукта В не меньше 8 т, а спрос на краску №2 превышает спрос на краску №1 не менее чем на 1 т. Используйте рисунок 1.8.

Напишите новое ограничение:_____________________________________________

Упражнение 1.7. Найдите оптимальные решения при следующих целевых функциях:

1. W = 3 х ₁ + х ₂. Используйте рисунок 1.9.

2. W = 3 х ₁ + 1,5 х ₂. Используйте рисунок 1.10.

3. W = х ₁ + 3 х ₂. Используйте рисунок 1.11.

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

6. Анализ на чувствительность (анализ моделей после нахождения оптимального решения)

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

В задаче № 1, например, может представить интерес вопрос о том, как повлияет на оптимальное решение увеличение и уменьшение спроса и (или) изменения запасов ресурсов. Можно, также определить влияние на оптимальное решение изменения рыночных цен.

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

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

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

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

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

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

На Рис. 1.1. связывающими ограничениями являются только ограничения (4) и (5), т. е. те, которые лимитируют запасы исходных продуктов (ресурсов) А и В.

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

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

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

В задаче № 1 используемые продукты А и В (ограничения (4) и (5)) являются дефицитными ресурсами. Рассмотрим сначала ресурс А.

При увеличении запаса этого ресурса прямая (4) перемещается вверх параллельно самой себе, постепенно “стягивая” в точку треугольник DКЕ. (Стороны DK и КЕ этого треугольника представляют собой продолжения прямых, соответствующих ограничениям (4) и (6).) В точке К ограничения (2) и (4) становятся связывающими; оптимальному решению при этом соответствует точка К, а пространством (допустимых) решений становится многоугольник АВСКF. В точке К ограничение (4) (для ресурса А) становится избыточным, так как любой дальнейший рост запаса соответствующего ресурса не влияет ни на пространство решений, ни на оптимальное решение [3]. Таким образом, объем ресурса А не следует увеличивать сверх того предела, когда соответствующее ему ограничение (4) становится избыточным, т. е. прямая (4) проходит через новую оптимальную точку К. Этот предельный уровень определяется следующим образом.

Во-первых, устанавливаются координаты точки К, в которой пересекаются прямые (5) и (7), т. е. находится решение системы уравнений

2 х ₁ + х ₂ = 8 (прямая KF),

х ₂ = 2 (прямая CK).

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

х ₁ + 2х₂ = 3+2 · 2 = 7 т.

Рассмотрим вопрос о целесообразности увеличения запаса дефицитного ресурса (2) (исходного продукта В).

Новой оптимальной точкой становится точка J (Рис. 1.13.), где пересекаются прямые (6) и (1), т. е. х ₂ = 0 и х ₁ + 2 х ₂ = 6. Отсюда следует, что х ₁ = 6, х ₂ = 0, причем запас продукта В можно увеличить до значения, равного 2 х ₁ + х ₂ =2·6+1·0=12 т.

Рассмотрим теперь вопрос об уменьшении правой части не связывающих ограничений. Ограничение (4), х ₂ £ 2, фиксирует предельный уровень спроса на краску №2. Из рисунка 1.14. видно, что, не изменяя оптимального решения, прямую (4) (СD) можно опускать вниз до пересечения с оптимальной точкой E. Так как точка E имеет координаты х ₁=3¹/₃ и х ₂ =1¹/₃, уменьшение спроса на краску №2 до величины х ₂ =1¹/₃ т никак не повлияет на оптимальность ранее полученного решения.

Рассмотрим ограничение (3), - х₁+ х₂ £ 1, которое представляет соотношение между спросом на краску №2 и спросом на краску №1. И в этом случае правую часть ограничения можно уменьшать до тех пор, пока прямая (3) (BC) не достигнет точки E (Рис. 1.15.) При этом прямая часть ограничения (5) станет равной - х ₁ + х _{2 =} (- 3¹/₃)+(1¹/₃) = -2, что позволяет записать это ограничение в виде: - х₁ + х₂ £ -2, или в эквивалентной форме: -х₁- х₂ ³ 2. Этот результат показывает, что ранее полученное оптимальное решение не изменится, если спрос на краску №1 превысит спрос на краску №1 не более чем на 2 т.

Результаты проведенного анализа можно свести в следующую таблицу.

Ресурс	Тип ресурса	Максимальное изменение запаса ресурса, т	Максимальное изменение дохода от реализации тыс. ден. ед.
	Дефицитный	7 - 6=+1	13 - 122/3=+1/3
	Дефицитный	12 - 8 =+4	18 - 122/3=+51/3
	Недефицитный	-2 - 1= - 3	122/3 - 122/3 =0
	Недефицитный	11/3 - 2 =-2/3	122/3 - 122/3=0

Упражнение 1. 8. Укажите связывающие, не связывающие и избыточные ограничения для каждого из указанных ниже условий. Сравните результаты с данными приведенной выше таблицы. Изпользуйте Рис. 1.16.

1) Объем ресурса (2) увеличивается до предельного значения (равного 12 т).

___________________________________________________________________________

___________________________________________________________________________

___________________________________________________________________________

2) Объем ресурса (3) уменьшается до минимально допустимого значения.

___________________________________________________________________________

___________________________________________________________________________

___________________________________________________________________________

3) Объем ресурса (4) уменьшается до минимально допустимого значения.

___________________________________________________________________________

___________________________________________________________________________

___________________________________________________________________________

Упражнение 1. 9. В исходных данных ограничение, имеющее вид х₁ +2х₂ £ 6, замените ограничением 2х₁ +3х₂ £ 10. Найдите оптимальное решение для новых условий и определите максимально допустимый в этом случае прирост объема продукта А и соответствующее приращение целевой функции (дохода) W. Используйте Рис. 1.16.

Вторая задача анализа на чувствительность. Необходимо определить увеличение объема, какого из ресурсов наиболее выгодно?

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

Обозначим ценность дополнительной единицы ресурса i через y _i. Величина y _i определяется из соотношения: Максимальное приращение оптимального значения W / Максимально допустимый прирост объема ресурса i.

Воспользовавшись данными указанной таблицы, для ограничения по продукту А, получим: y _i = (13 - 12²/₃) / (7 – 6) = 1/3 тыс. ден. ед./тонна.

Аналогичным образом можно определить ценность единицы каждого из ресурсов и представить результаты в следующей таблице:

Ресурс	Тип ресурса	Значение yi тыс. ден.ед./тонна
	Дефицитный	y i = 1/3
	Дефицитный	y i = 4/3
	Недефицитный	y i = 0
	Недефицитный	y i = 0

Полученные результаты свидетельствуют о том, что дополнительные вложения в первую очередь следует направить на увеличение ресурса - продукта В и лишь затем - на увеличение ресурса - продукта А. Что касается недефицитных ресурсов, то, как и следовало ожидать, их объем увеличивать не следует.

Упражнение 1.10. В задаче № 1 замените ограничение для исходного продукта А, х₁ +2х₂ £ 6 на ограничение 2х₁ + 3х₂ £10, не меняя остальных исходных данных. Определите величину у_i для всех видов ресурсов (Рис. 1.17)

___________________________________________________________________________

___________________________________________________________________________

___________________________________________________________________________

___________________________________________________________________________

Третья задача анализа на чувствительность. Необходимо ответить на вопрос в каких пределах допустимо изменение коэффициентов целевой функции?

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

1. Каков диапазон изменения (увеличения или уменьшения) того или иного коэффициента целевой функции, при котором не происходит изменения оптимального решения?

2. Насколько следует изменить тот или иной коэффициент целевой функции, чтобы сделать некоторый недефицитный ресурс дефицитным и, наоборот, дефицитный ресурс сделать недефицитным?

Обсудим поставленные вопросы на примере задачи № 1. Рассматривая первый вопрос, обозначим через с₁ и с₂ доходы фирмы от продажи 1 т краски №1 и 1 т краски №2 соответственно. Тогда целевую функцию можно представить в следующем виде:

W = с₁ x ₁ + с₂ x ₂.

Из рисунка 1.18. видно, что при увеличении с₁ или уменьшении с₂ прямая, представляющая целевую функцию W, вращается (вокруг точки Е) по часовой стрелке. Если же с₁- уменьшается или с₂ увеличивается, эта прямая вращается - против часовой стрелки. Таким образом, точка Е будет оставаться оптимальной точкой до тех пор, пока наклон прямой не выйдет за пределы, определяемые наклонами прямых для ограничений (4) и (5). Когда наклон прямой W станет равным наклону прямой для ограничения (4), получим две альтернативные оптимальные угловые точки Е и D. Аналогично, если наклон прямой станет равным наклону прямой для ограничения (5), будем иметь альтернативные оптимальные угловые точки Е и F. (Наличие альтернативных оптимумов свидетельствует о том, что одно и то же оптимальное значение W может достигаться при различных значениях переменных. Как только наклон прямой W выйдет за пределы указанного выше интервала с₁, получим некоторое новое оптимальное решение (точка D или точка F).

Чтобы проиллюстрировать эту процедуру вычислений, рассмотрим, каким образом можно найти допустимый интервал изменения с₁, при котором точка E остается оптимальной, Исходное значение коэффициента с₂ = 2 оставим неизменным. Из рисунка видно, что значение с₂ можно увеличивать до тех пор, пока прямая не совпадет с прямой (5), или уменьшать, пока прямая W не совпадет с прямой (2). Эти крайние значения коэффициента с₁ можно определить из равенства наклонов прямой W и прямой (5) (максимальное значение с₁) и равенства наклонов прямой W и прямой (4) (минимальное значение с₁). Так как тангенс угла наклона для прямой W равен с₁/2, а для прямых (1) и (2) соответственно 1/2 и 2/1, минимальное значение с₁ определяем из равенства с₁/2 = 1/2, откуда с₁ = 1, а максимальное значение с₁ находим из равенства с₁/2=2/1, откуда с₁=4.

Интервал изменения с₁, в котором точка Е по-прежнему остается единственной оптимальной точкой, определяется неравенством 1<с₁< 4. При с₁=1 оптимальными угловыми точками будут как точка Е, так и точка D. Как только коэффициент с₁ становится меньше 1, оптимум смещается в точку D. Аналогичную интерпретацию можно дать и тому случаю, когда коэффициент с₁ оказывается равным или начинает превосходить максимальный предел, равный 4.

Можно заметить, что, как только коэффициент с₁ оказывается меньше 1, ресурс В становится недефицитным, а ресурс А - дефицитным. Для фирмы это означает, что если доход от продажи одной тонны краски №1 станет меньше 1 тыс. ден. ед., то наиболее выгодная производственная программа фабрики должна предусматривать выпуск максимально допустимого количества краски 1 (т. е. х₂=2 т в сутки). При этом общее потребление продукта В (ограничение - 5) снизится, что обусловит не дефицитность этого ресурса. Соответствующие выводы легко сделать и для случая, когда значение с₁ превысит максимальное значение, равное 4.