Методы принятия решений - лекции, расчёты и ЛР / Лабораторная работа 1

Методы принятия решений. Лабораторная работа № 1

11

Пример решения задачи

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

	Расход сырья (т) на тонну краски		Ежедневный запас
	для наружных	для внутренних	сырья, т
	работ	работ
Сырье A	6	4	24
Сырье B	1	2	6
Цена реализации тонны	5	4
краски, тыс. д.е.

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

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

Решение и пояснения.

1. Переменными в данной задаче являются:

x1 – ежедневный объем производства краски для наружных работ;

x2 – ежедневный объем производства краски для внутренних

работ.

z =5x1 +4x2 → max,

С учетом всех ограничений, заданных в 6x1 +4x2 ≤ 24, условии задачи, оптимизационная модель бу- x +2x ≤ 6,

дет иметь вид: 1 2

x2 − x1 ≤1,x2 ≤ 2;

x1 ≥ 0, x2 ≥ 0.

Методы принятия решений. Лабораторная работа № 1

12

2. Организуем данные на листе Excel так, как это показано на рис. (подробнее см. файл Лабораторная работа 1 – Пример.xls).

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

3. Вызываем надстройку «Поиск решения» (меню Сервис → Поиск решения).

3.1. Задаем целевую ячейку (D10), выбираем максимизацию и определяем диапазон изменяемых ячеек (F3:F4).

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

Методы принятия решений. Лабораторная работа № 1

13

После ввода последнего ограничения нажимаем кнопку ОК. Результат показан на рис.

3.3. В окне задания параметров поиска решения (кнопка Параметры) следует включить опции «Линейная модель» и «Неотрицательные значения» (последняя опция избавляет от необходимости задавать неотрицательность переменных в числе ограничений). Состояния остальных полей на линейную модель влияния не оказывают.

Методы принятия решений. Лабораторная работа № 1

14

3.4. Возвращаемся в окно «Поиск решения» и нажимаем кнопку Выполнить. Если все было сделано правильно, появляется следующее окно:

Рабочий лист Excel, соответствующий найденному оптимальному решению, имеет вид:

Таким образом, при заданных ограничениях максимальный доход, равный 21 тыс. д.е., обеспечивается при производстве 3 т краски для наружных работ и 1,5 т краски для внутренних работ.

В ячейках B6:C6 содержатся значения фактического расхода сырья A и B (как видно из рис., оба вида сырья расходуются полностью).В ячейках F6:F7 содержатся фактические значения левых частей неравенств, соответствующих дополнительным ограничениям.

Примечание. В случае, если при построении оптимизационной модели были допущены ошибки, либо если оптимизационная задача не имеет решения,

вокне появляется одно из следующих сообщений:

−«Значения целевой ячейки не сходятся»;

−«Поиск не может найти решения»;

−«Условия линейной модели не выполняются».

Вэтом случае в окне «Результаты поиска решения» следует выбрать вариант «Восстановить исходные значения» и проверить правильность построения оптимизационной модели и задания ее параметров.

Методы принятия решений. Лабораторная работа № 1

15

4. По результатам поиска решения Excel формирует отчет об устойчивости, который содержит информацию о теневых ценах ограничений и об интервалах устойчивости целевых коэффициентов и правых частей ограничений. Для получения этого отчета следует в окне «Результаты поиска решения», перед тем, как нажать на кнопку OK, выбрать элемент «Устойчивость» в списке «Тип отчета».

После нажатия на кнопку OK в документе Excel будет создан дополнительный лист «Отчет об устойчивости». Вид такого отчета для рассматриваемой задачи показан на рис.

4.1. Первая таблица («Изменяемые ячейки») содержит информацию об интервалах устойчивости коэффициентов целевой функции. Границы интервалов устойчивости определяются значениями, содержащимися в столбцах «Допустимое увеличение» и «Допустимое уменьшение».

Применительно к рассматриваемой задаче, значения в столбцах «Допустимое увеличение» и «Допустимое уменьшение» показывают, на сколько можно изменить доходность (цену реализации) краски

Методы принятия решений. Лабораторная работа № 1

16

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

В общем случае, если в оптимальном решении xj* > 0 (j-й вид продукции входит в оптимальный план), то имеется как верхний, так и нижний предел диапазона изменения соответствующего коэффициента целевой функции. Если же xj* = 0, то допустимое уменьшение может быть сколь угодно велико – продукт все равно не войдет в оптимальный план. Допустимое увеличение в этом случае определяет минимальную величину, на которую следует увеличить соответствующий целевой коэффициент, чтобы j-й продукт вошел в оптимальный план. Величина, противоположная этому увеличению, называется нормированной стоимостью и определяет на сколько текущее значение цены продукта ниже минимальной цены (или текущие издержки выше максимальных), при которой j-й продукт может войти в оптимальный план.

Необходимо иметь в виду, что интервал устойчивости коэффициента cj определяется при условии, что значения всех остальных целевых коэффициентов ck (k ≠ j) остаются неизменными. Одновременное изменение двух или более целевых коэффициентов, каждого внутри своего интервала устойчивости, может привести к изменению оптимального решения.

4.2. Вторая таблице («Ограничения») содержит результаты анализа устойчивости при изменении по отдельности правых частей bi ограничений (т.е. запасов ресурсов). Так, текущее оптимальное решение сохраняется до тех пор, пока ежедневный запас сырья A будет находиться в пределах от 20 до 36 тонн (допустимое увеличение – 12 тонн и допустимое уменьшение – 4 тонны).

Столбец «Результирующее значение» содержит фактические значения правых частей ограничений, соответствующие оптимальному решению. На основании этих данных можно определить, какие ресурсы расходуются полностью (т.е. являются дефицитными), а какие – не полностью.

Методы принятия решений. Лабораторная работа № 1

17

Значения 1Е+30 означают неограниченное увеличение или уменьшение (1030 – максимальное число, известное Excel). Так, ресурсы 3 и 4 являются недефицитными, т.е. использованы не полностью, поэтому любое увеличение их запасов не повлияет на оптимальное решение. При этом столбец «Допустимое уменьшение» показывает, на сколько может быть уменьшено значение правой части ограничения (т.е. запас ресурса) при условии неизменности полученного оптимального решения.

Теневые цены соответствуют значениям yi* компонентов оптимального решения двойственной задачи и определяют, как изменяется значение целевой функции при изменении значения bi на единицу: Z* = yi* bi. Например, теневая цена 0,75 для первого ресурса (запас сырья A) показывает, что каждая дополнительная тонна данного сырья увеличит доход на 750 д.е. Заметим, что этот вывод справедлив только при условии, что запас сырья A находится в пределах от 20 до

36тонн (т.е. в пределах интервала устойчивости).

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

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

устойчивости для изменения bi даются при условии, что остальные значения правых частей bk (k ≠ j) остаются неизменными. Одновременное изменение двух или более значений правых частей, каждого внутри своего интервала устойчивости, может привести к изменению теневых цен.

Методы принятия решений. Лабораторная работа № 1

18

Контрольные вопросы и задания

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

2.Для оптимизационной модели, построенной при выполнении индивидуального задания, указать основные элементы задачи принятия решений: множество альтернатив, множество исходов, критерий оценки исходов, систему предпочтений ЛПР. Обосновать, что все эти задачи относятся к классу однокритериальных ЗПР в условиях определенности.

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

4.Объяснить различие между общей, стандартной и канонической формами представления линейных оптимизационных моделей.

5.Объяснить, что означает эквивалентность различных форм представления линейных оптимизационных моделей. Привести правила преобразования стандартной формы в каноническую и канонической в стандартную.

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

7.С какой целью выполняется анализ устойчивости линейных оптимизационных моделей? На какие вопросы он позволяет отвечать?

8.Какая информация содержится в отчете об устойчивости, формируемом по результатам поиска решения линейной оптимизационной задачи в среде Microsoft Excel?

9.Что характеризуют интервалы устойчивости целевых коэффициентов и правых частей ограничений?

10.Каким образом связаны между собой параметры прямой и двойственной задач линейной оптимизации (на примере модели задачи производственного планирования)?

11.Как связаны между собой оптимальные решения прямой и двойственной задач линейной оптимизации, а также факты наличия/отсутствия решений у этих задач?

12.Дать содержательную интерпретацию оптимального решения задачи, двойственной по отношению к задаче производственного планирования. Что характеризуют теневые цены ресурсов?

Методы принятия решений. Лабораторная работа № 1

19

Ответы к первым пунктам заданий (для контроля)

1.Модель A – 20 шт., модель B – 552,63 шт., модель C – 602,63 шт. После округления: модель A – 20 шт., модель B – 552 шт., модель C –

603шт.

2.Акции A – 75 тыс. руб., акции B – нет, акции C – 25 тыс. руб., облигации долгосрочные – 300 тыс. руб., облигации краткосрочные – нет, срочный вклад – 100 тыс. руб.

3.Сок яблочный – 600 л, сок апельсиновый – 1410 л, сок персиковый – 1240 л, сок «Яблоко-апельсин» – 300 л, сок «Яблоко-персик» – 1650 л, сок «Фруктовая смесь» – 2000 л.

4.Акции А – 2,08 тыс. ден.ед., акции В – 47,92 тыс. ден.ед., инвести-

ционный фонд – 20 тыс. ден.ед., государственные облигации –

30тыс. ден.ед.

5.Regular – 300 кг, Extra – 3600 кг, Puppy Delite – нет.

6.

	Предприятие		План производства
		RC-11	RC-18	RC-20	RC-22
	Предприятие 1	0	148,48	557,58	0
	Предприятие 2	116	525,80	92,42	0
	Предприятие 3	0	25,71	0	300

7.Возможны 4 способа распила бревен: 12+8 футов, 10+10 футов, 10+8 футов, 8+8 футов. 255 бревен распиливаются 1-м способом,

50бревен – 2-м и 10 бревен – 4-м.

8.Если требуется засеять весь участок, то кукуруза – 166,67 га, горох – 173,37 га, рожь – 357,14 га, пшеница – 302,82 га. Если данное

требование отсутствует, то кукуруза – 100 га, горох – 210,53 га,

рожь – 357,14 га, пшеница – 297,39 га.

9.Стул – 10, стол – 0, бюро – 4, книжный шкаф – 15, передвижной столик – 6.

10.A – 300, B – 188, C1 – 500, C2 – 400, D – 220, E6 – 50, F – 300.