Практические задания по курсу Компьютерные методы оптимизации

Практические задания по курсу Компьютерные методы оптимизации

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

Жизненный цикл процесса управления состоит из циклического повторения трех фаз:

·  Выявление проблемной ситуации;

·  Анализ ситуации, принятие решения, его реализация;

·  Оценка результатов решения, переосмысление проблемной ситуации.

Для повышения эффективности принятия решений на всех его этапах широко используются экономико-математические методы.

Этапы принятия решений с использованием экономико-математических методов:

1) Подготовительный этап:

-  уяснение и изучение проблемной ситуации;

-  формирование целей;

-  выявление управляемых величин, оценка ограничений (по времени, по ресурсам, правовых, экологических и т. д.);

-  формализация проблемной ситуации (построение экономико-математических моделей);

-  выбор математических методов и программных средств для решения задачи;

-  поиск и анализ вариантов решений;

2) Принятие решения:

-  оценка и окончательное ранжирование альтернативных решений;

-  выбор и утверждение решения;

-  разработка и утверждение плана реализации решения;

3) Реализация решения (контроль и анализ выполнения решения, оперативное управление)

4) Оценка эффективности результатов выполнения решения, переоценка проблемной ситуации.

Задание на состоит из двух частей. Работа считается выполненной при выполнении обоих индивидуальных заданий. Номер варианта задания выбирается согласно порядковому номеру студента по журналу. Для студентов с номерами больше 15 варианты первого задания равны №-15. Выполнение контрольной работы не по своему варианту является основанием для отклонения данной работы.

Задание№1
Поиск решения однокритериальных задач в условиях определенности

1.1.  Цель задания:

Изучение математических моделей и методов решения однокритериальных задач в условиях определенности. Изучение методики решения оптимизационных задач при помощи пакета Excel с использованием надстройки «Поиск решения» на примере задачи оптимизации производственной программы предприятия.

1.2. Построение экономико-математических моделей в условиях определенности внешних факторов.

Построение экономико-математической модели задачи принятия решения в условиях определенности состоит из следующих этапов:

1)  Формирование цели принятия решения;

2)  Формирование множества управляемых переменных, т. е. независимых внутренних параметров, которые мы можем изменять по своему усмотрению для достижения поставленной цели;

3)  Выявление ограничений на значения управляемых переменных и других (зависимых от них) неизвестных внутренних параметров;

4)  Построение математических зависимостей цели и зависимых внутренних параметров от значений управляемых переменных (в виде линейных или нелинейных уравнений);

Математические методы для решения однокритериальных оптимизационных задач носят общее название «методы математического программирования» (такое название не имеет отношения к программированию на компьютере).

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

1.3. Решение оптимизационных задач с помощью Excel.

Для решения оптимизационной задачи с помощью Excel необходимо:

1.  Выделить на рабочем листе ячейки для каждой из управляемых переменных и заполнить их какими-либо начальными значениями.

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

3.  Выделить на рабочем листе ячейки для зависимых внутренних параметров и ввести формулы для вычисления их значений.

4.  Выделить ячейку для функции цели и ввести соответствующую формулу.

5.  Сохранить книгу Excel (на всякий случай).

6.  Вызвать надстройку «Поиск решения» (меню «Сервис»). Если этой надстройки нет, то установить ее с помощью пункта «Надстройки» меню «Сервис».

7.  В полученном диалоговом окне указать:

·  целевую ячейку;

·  направление ее оптимизации (минимум или максимум);

·  управляемые переменные (в строке «изменяя ячейки»);

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

·  Если какие-либо внутренние переменные должны быть целочисленными, двоичными, или неотрицательными, то отразить это требование, добавив соответствующие ограничения.

·  Если все управляемые переменные должны быть неотрицательными, то можно указать это в диалоговом окне, вызываемом с помощью кнопки «Параметры»;

8.  Выполнить поиск решения с помощью кнопки «Выполнить»;

9.  Проанализировать полученное решение. Если оно корректное, сохранить его.

1.4. Составление детерминированной математической модели на примере задачи оптимизации производственной программы предприятия.

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

1) Целью оптимизации является получение максимальной прибыли.

2) Внутренние переменные: – объем производства i-й продукции; – объем потребления j-го ресурса. Среди этих переменных объемы производства являются независимыми, т. е. управляемыми переменными, а объемы потребления ресурсов – зависимыми от них.

3) Ограничения: – нижние и верхние границы объема производства i-й продукции; – запасы ресурсов.

4) Построение математических зависимостей:

Известные величины:

– удельный расход i-го ресурса на единицу j-й продукции;

– цена единицы ресурса;

– цена единицы продукции;

– удельная себестоимость изготовления и реализации единицы i-й продукции без учета стоимости ресурсов. При необходимости следует учитывать уменьшение удельной себестоимости при увеличении объемов производства;

Математическая модель задачи поиска оптимального производственного плана имеет вид:

Целевая функция – прибыль от выпуска и реализации продукции:

(1.1)

Ограничения:

по объему выпуска продукции: (1.2)

по объему потребления ресурсов: (1.3)

Для решения полученной задачи применяются методы линейного или нелинейного математического программирования.

1.5. Пример решения оптимизационной задачи с помощью Excel.

Предприятие выпускает телевизоры, мониторы и акустические системы, используя взаимозаменяемые комплектующие. Количество некоторых из них, а также фонд рабочего времени ограничены. Объемы производства также ограничены (снизу – требованиями технологии, сверху – величиной спроса). Математическая модель такой задачи была рассмотрена ранее и имеет вид (1.1)-(1.3).

Исходные данные из этой модели заносятся в таблицу Excel, которая может, например, иметь вид табл.1.1. Формулы, входящие в модель приведены в табл.1.2, расположение переменных по ячейкам показано в табл.1.3.

Таблица 1.1

	A	B	C	D	E	F	G
1	Наименование изделия	Телевизор	Монитор	Ак. сист.
2	Минимальный объем производства	20	20	0
3	Объем производства	20	450	0
4	Максимальный объем производства	200	1000	1000
5	Наименование ресурса	Цена ресурса	Запас ресурса	Суммарный расход ресурса	Удельные расходы ресурсов
6	Фонд рабочего времени	0	10000	10000	50	20	20
7	Кинескоп	300	1000	470	1	1	0
8	Динамик	50		40	2	0	4
9	Блок пит.	50		470	1	1	1
10	Электрон. плата	50	500	490	2	1	1
11	Цена единицы продукции	1100	700	400
12	Себестоимость единицы продукции (без ресурсов)	500	250	100
13	Стоим. ресурсов	191000		Прибыль:	23500

Таблица 1.2.

Ячейка	Формула
B13	=СУММПРОИЗВ(B6:B10;D6:D10)
E13	=(E11-E12)*E3+(F11-F12)*F3+(G11-G12)*G3-B13
D6 D7 D8 D9 D10	=E6*E$3+F6*F$3+G6*G$3 =E7*E$3+F7*F$3+G7*G$3 =E8*E$3+F8*F$3+G8*G$3 =E9*E$3+F9*F$3+G9*G$3 =E10*E$3+F10*F$3+G10*G$3

Таблица 1.3.

Переменная	П
Ячейка	Е13	E3-G3	D6-D10	E2-G2	E4-G4	C6-C10	E6-G10	B6-B10	E11-G11	E12-G12

Целевой ячейкой служит ячейка E13, управляемые переменные – E3-G3, ограничения сформированы ячейками D6, D7, D10, E3-G3 и C6, C7, C10, E2-G2, E4-G4.

Согласно проведенному расчету оптимальным планом является выпуск 20 телевизоров и 450 мониторов, что даст наибольшую прибыль в 23500грн. Все численные результаты расчета также приведены в табл. 1.1.

1.6. Индивидуальные задания:

Решить задачу оптимизации производственного плана предприятия (1.1)-(1.3) с использованием пакета Excel. Коэффициенты математической модели выбираются согласно номеру варианта:

№ варианта	a	b	q	p	c
1	50 20 20 1 1 0 2 1 4 1 1 1 2 1 1	5000 1000 1000 1000 1000	0 300 40 50 50	1000 500 500	500 300 200	0 0 0	100 500 1000
2	40 20 20 1 1 0 2 1 4 1 1 1 2 1 1	5000 1000 1000 1000 1000	0 300 50 50 40	1100 500 500	500 300 200	0 0 0	100 500 1000
3	50 25 20 1 1 0 2 1 4 1 1 1 2 1 1	5000 1000 1000 1000 1000	0 250 50 50 50	1200 500 500	500 300 200	0 0 0	100 500 1000
4	50 20 25 1 1 0 2 1 4 1 1 1 2 1 1	5000 1000 1000 1000 1000	0 350 50 50 50	1000 600 500	500 300 200	0 0 0	100 500 1000
5	50 20 15 1 1 0 2 1 4 1 1 1 2 1 1	5000 1000 1000 1000 1000	0 300 40 50 50	1000 700 500	500 300 200	0 0 0	100 500 1000
6	50 15 20 1 1 0 2 1 4 1 1 1 2 1 1	5000 1000 1000 1000 1000	0 300 50 70 50	1000 500 600	500 300 200	0 0 0	100 500 1000
7	40 20 20 1 1 0 2 1 4 1 1 1 2 1 1	5000 1000 1000 1000 1000	0 300 50 60 50	1000 500 700	500 300 200	0 0 0	100 500 1000
8	40 15 25 1 1 0 2 1 4 1 1 1 2 1 1	5000 1000 1000 1000 1000	0 300 50 50 60	1000 500 800	500 300 200	0 0 0	100 500 1000
9	55 20 15 1 1 0 2 1 4 1 1 1 2 1 1	5000 1000 1000 1000 1000	0 250 40 50 50	900 700 500	500 300 200	0 0 0	100 500 1000
10	60 20 20 1 1 0 2 1 4 1 1 1 2 1 1	5000 1000 1000 1000 1000	0 300 40 50 40	1200 500 500	500 300 200	0 0 0	100 500 1000
11	60 15 15 1 1 0 2 1 4 1 1 1 2 1 1	5000 1000 1000 1000 1000	0 300 60 50 60	1200 700 500	500 300 200	0 0 0	100 500 1000
12	50 25 25 1 1 0 2 1 4 1 1 1 2 1 1	5000 1000 1000 1000 1000	0 250 60 50 60	1200 600 500	500 300 200	0 0 0	100 500 1000
13	45 20 25 1 1 0 2 1 4 1 1 1 2 1 1	5000 1000 1000 1000 1000	0 300 50 40 50	1100 600 400	500 300 200	0 0 0	100 500 1000
14	55 25 15 1 1 0 2 1 4 1 1 1 2 1 1	5000 1000 1000 1000 1000	0 300 60 50 40	1200 500 600	500 300 200	0 0 0	100 500 1000
15	50 20 15 1 1 0 2 1 4 1 1 1 2 1 1	5000 1000 1000 1000 1000	0 300 50 40 40	1200 500 600	500 300 200	0 0 0	100 500 1000

1.7. Требования к оформлению:

Описать проблемную ситуацию, записать экономико-математическую модель задачи, привести таблицу Excel, содержащую результаты расчета, и таблицу использованных расчетных формул (аналогично таблицам 1.1-1.2).

Задание№2
Методы принятия решения в условиях неопределенности или риска

2.1. Цель задания:

Изучение методов принятия решения в условиях неопределенности или риска.

2.2. Методика принятия решения в условиях неопределенности или риска.

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

Этапы принятия решений в условиях риска или неопределенности:

1)  Формирование цели принятия решения;

2)  Построение экономико-математической модели задачи принятия решения (происходит так же, как и в случае определенности внешних факторов);

3)  Формирование множества альтернативных решений;

4)  Выявление неопределенных внешних факторов, влияющих на достижение цели, формирование возможных состояний внешней среды;

5)  Расчет эффективности вариантов решения при различных состояниях внешней среды, формирование матрицы ценности альтернатив;

6)  Оценка вероятности состояний внешней среды (если возможно);

7)  Выбор предпочтительного варианта решения.

Матрица ценности альтернатив имеет вид:

Таблица 2.1.

Номер альтернативного решения	Номер состояния внешней среды
1	…	j	…	m
1		…		…
i		…		…
n		…		…

В этой матрице величина обозначает ценность i-го решения при реализации j-го состояния внешней среды.

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

2.3. Выбор решения в условиях неопределенности

Для этого существует ряд критериев: максиминный критерий Вальда, максимаксный критерий («оптимистический»), критерий Гурвица, критерий Лапласа.

Критерий Вальда соответствует пессимистической оценке: выбирается та альтернатива, для которой пессимистическая оценка наибольшая, т. е. максимум из минимумов, лучшая из худших. .

Максимаксный критерий: выбирается альтернатива с наибольшей оптимистической оценкой (лучшая из лучших).

Критерий Гурвица (взвешенный критерий): альтернативы оцениваются согласно выражению ., где – коэффициент оптимизма. Значение a=0 соответствует пессимистичной оценке (т. е. критерию Вальда), a=1 соответствует оптимистичной оценке (т. е. максимаксному критерию). Промежуточные значения a соответствуют взвешенному, т. е. пессимистично-оптимистичному, взвешенному подходу. Задав фиксированное значение коэффициента оптимизма, выбирают альтернативу с наибольшей оценкой.

Критерий Лапласа: альтернативы оцениваются с учетом всего диапазона ценностей (а не только худшего и/или лучшего значений): . Выбирается альтернатива с наибольшей оценкой.

Вычисления можно проводить вручную, а можно использовать табличный процессор Excel.

2.4. Числовой пример:

Матрица ценностей представлена в табл. 2.2. Там же приведены значения критериев. Лучшие по каждому из критериев решения показаны жирным шрифтом:

Таблица 2.2.

Номер альтернативного решения	Состояние внешней среды	Критерий
1.Конкурен­ция на преж­нем уровне	2.Конкурен-ция усилилась	Критерий Вальда	Максимакс­ный	Критерий Гурвица (	Критерий Лапласа
1.Продолжать работу в обычном режиме	125	90	90	125	104	112,5
2.Усилить рекламную деятельность	120	95	95	120	105	112,5

2.5. Методика принятия решения в условиях риска.

Если каким-либо образом (например, экспертным методом) оценены вероятности состояний внешней среды (), то для оценки альтернативных решений используются критерии Байеса-Лапласа или Ходжеса-Лемана:

Критерий Байеса-Лапласа: ,

Критерий Ходжеса-Лемана: , где – коэффициент доверия к вероятности (т. е. к экспертам).

2.6. Варианты индивидуальных заданий

Вариант 1. Предприятие имеет три альтернативных варианта своей рыночной стратегии. Оценка его прибыли в зависимости от состояния внешней среды приведена в табл. 2.3.

А) Принятие решения в условиях неопределенности.

Необходимо найти оптимальные стратегии при пессимистической оценке (по критерию Вальда), оценке Лапласа, взвешенной оценке (по критерию Гурвица). Значение коэффициента оптимизма выбрать самостоятельно. Результаты выбора решения отразить в таблице, аналогично табл.2.2. Сделать выводы о применимости критериев.

Б) Принятие решения в условиях риска.

Пусть получены экспертные оценки вероятностей состояний внешней среды p1=0.5, p2=0.35, p3=0.15. Оценить альтернативные решения по критерию Байеса-Лапласа. Результаты вычисления ценности альтернативных решений занести в ту же таблицу. Выбрать наилучшее решение. Сравнить результат выбора с полученными ранее результатами выбора решения в условиях неопределенности.

Таблица 2.3.

Возможные альтернативные решения	Возможные состояния внешней среды
1.Конкуренция на прежнем уровне	2.Конкуренция немного усилилась	3. Конкуренция резко усилилась
1. Продолжать работу в обычном режиме	100	80	50
2.Активизировать рекламную деятельность	90	90	70
3.Активизировать рекламу и снизить цены	60	70	80

Варианты 2-14.

Постановка задачи такая же, как и для варианта 1. Численные значения матрицы ценности альтернатив (т. е. оценок прибыли предприятия) приведены в табл.2.4.

Таблица 2.4.

№ варианта	Матрица ценности	№ варианта	Матрица ценности	№ варианта	Матрица ценности
1	90 90 70 60 70 80	6	90 100 70 60 90 80	11	90 90 60 50 60 70
2	80 90 70 60 70 80	7	80 90 70 60 90 80	12	80 90 60 60 70 80
3	70 90 60 60 70 80	8	70 90 50 50 70 80	13	70 90 60 60 70 70
4	80 90 40 30 40 80	9	80 90 70 40 70 80	14	70 90 70 40 60 70
5	80 95 70 60 70 80	10	90 90 40 50 60 70	15	80 90 70 50 50 60 80

КОНТРОЛЬНЫЕ ВОПРОСЫ ПО КУРСУ

1  Основные понятия теории принятия решений. Задачи принятия решений. Целеполагание, предпочтение, свойства решений.

2  Основные принципы системного подхода. Их применение к задачам принятия решений.

3  Технология принятия решений. Основные этапы принятия решений. Субъекты принятия решений.

4  Классификация задач принятия решения.

5  Роль и место экономико-математических методов в процессе принятия решений. Технология принятия решений с использованием экономико-математических методов.

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

7  Информационное обеспечение задач принятия решений. Требования к информации. Шкалы измерений. Согласование качественных и количественных измерений.

8  Технология поиска решений в условиях определенности. Составление детерминированных математических моделей оптимизационных экономических задач.

9  Виды задач математического программирования. Применение методов математического программирования для решения детерминированных задач.

10  технология поиска решений в условиях риска. Применение вероятностных методов при поиске оптимального решения в условиях риска.

11  Методы поиска решений в условиях неопределенности. Применение методов теории игр в задачах принятия решений. Основные понятия теории игр.

12  Методы оценки и критерии выбора альтернатив в условиях неопределенности. Критерии Вальда, Гурвица, Лапласа.

13  етоды оценки и критерии выбора альтернатив в условиях риска. Критерий Байеса-Лапласа.

14  Методы поиска оптимальных смешанных стратегий в игровых моделях задач принятия решений.

15  Методы решения многокритериальных задач. Метод главного показателя, метод сводного показателя.

16  Методы решения многокритериальных задач. Область Парето (область доминирования). Метод последовательных уступок.

17  Методы получения, согласования и обработки экспертных оценок.

18  Использование вычислительной техники в задачах принятия решений.