Методы оптимальных решений

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ТЕХНОЛОГИЙ И УПРАВЛЕНИЯ имени К.Г.Разумовского

(образован в 1953 году)

Кафедра «Высшая математика»

Садыкова А.Р., Родионова Е.Н., Воробьева А.В.

Методы оптимальных решений

УДК 519.8    

Содержание

Рабочая программа……………………………………………………………..…4

Краткие теоретические сведения………………………………………………...5

1. Математическая модель 3ПР………………………………………..…………5

1.1. Примеры составления математических моделей………………..…………5

2. 3ПР в условиях определенности……………………………………………....7

2.1. Графический метод решения……………………………………………..….8

2.2. Симплексный метод……………………………………………..………….11

3. Принятие решения в условиях неопределенности……………...……..……14

4. Принятие решения в условиях риска……………………………...………....18

5. Элементы теории игр………………………………………………..………21

5.1. Матричная игра……………………………………………………………...22

5.2. Биматричная игра…………………………………………………………...26

Контрольные задания…………………………………………………………....28

Рекомендуемая литература……………………………………………………...34

 

Рабочая программа

1. Системное описание процесса принятия решений. 2. Альтернативы. Критерии. 3. Математическая модель задачи принятия решений.

Краткие теоретические сведения

Математическая модель задачи принятия решения (ЗПР)

Х - множество допустимых альтернатив, Y – множество возможных состояний среды, А – множество возможных исходов.

Примеры составления математических моделей

Рассмотрим примеры математических моделей, которые относятся к задачам линейного программирования.

1.Задача об использовании ресурсов (задача планирования производства).

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

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

 

 

 

2. Задача о составлении рациона питания (задача о диете, задача о смесях).

Животные должны получать ежедневно питательных веществ в количестве не менее . В рацион животных входят корма видов. Известно: содержание го питательного вещества в единице го вида корма; стоимость единицы го вида корма. Составить суточный рацион кормления животных, обеспечивающий минимальные затраты.

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

 

 

 

3. Транспортная задача (задача о перевозках ).

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

–мощности всех поставщиков были реализованы;

–спросы всех потребителей были удовлетворены;

–суммарные затраты на перевозку были минимальны.

Исходные данные транспортной задачи записываются в виде таблицы

 

Пункты отправления	Пункты назначения	Запасы
	…		…
		…		…
…	…	…	…	…	…	…
		…		…
…	…	…	…	…	…	…
		…		…
Потребности		…		…

 

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

 

при условиях

 

 

Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.

,

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

ЗПР в условиях определенности

Итак, построение математической модели сводится к указанию множества допустимых альтернатив X и заданию целевой функции f : Х R. В этом случае… Замечание.Если целевая функция рассматривается как функция потерь, то… Алгоритм нахождения максимального (минимального) значения функции одной переменной изложен в курсе математического…

Графический метод решения

     

Симплексный метод

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

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

Итак, математическая модель ЗПР в условиях неопределенности может быть задана в виде тройки объектов <X,Y,f>, где Х – множество допустимых… Фактически построение такой математической модели принятия решения сводится к… Ограничимся случаем, когда множества X и Y являются конечными; тогда целевая функция может быть задана табличным…

Решение.

L(А1)= ( 7+5+1+10 ) = ;   L(А2)= ( 5+2+8+4 ) = ;

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

Как известно из теории вероятностей, наиболее естественной числовой характеристикой случайной величины является ее математическое ожидание. Таким… В теории вероятностей в качестве меры отклонения случайной величины от ее… Предпочтение альтернатив будем устанавливать по обобщенному критерию вида

Элементы теории игр

Типичный конфликт характеризуется тремя основными составляющими: 1. Заинтересованными сторонами. 2. Возможными действиями этих сторон.

Матричная игра

Рассмотрим следующий пример. Пример . Два игрока А и В, не глядя друг на друга, кладут на стол по…  

α υ β.

Рассмотрим пример наиболее простой матричной игры, в которой один из игроков имеет две стратегии. Решение такой игры можно найти графически.

Пример.Найдите решение следующей матричной игры .

Решение:

 

			min
		-2	-2
mах:

- нижняя цена игры

- верхняя цена игры

Т.к. , то имеет место матричная игра в смешанных стратегиях, седловой точки нет.

 

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

 

	-2

Получим,

 

 

(1)

(2)

(3)

.

.

.

.

.

.

.

.

.

q

q0

-2

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

, значит Q = { }

Полагая , получим:

р
1-р		-2

 

, значит Р = { , }

Цена игры υ = ω₀ =

Ответ: Р = { , }; Q = { }; υ = .

 

Биматричная игра

Рассмотрим конфликтную ситуацию, в которой каждый из двух участников имеет следующие возможности для выбора своей линии поведения: игрок А – может выбрать любую из стратегий А1, А2,…, Аm, игрок В – любую из стратегий В1, В2,…, Вn.

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

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

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

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

Задача № 1.Составить математические модели следующих задач:

Варианты 1 – 5. Кондитерский цех выпускает три вида конфет A,B,C, используя три вида сырья (какао, сахар, наполнитель). Нормы расхода сырья на производство 10 кг конфет, а также прибыль от реализации 10 кг конфет каждого вида приведены в таблице:

 

Сырье	Нормы расхода сырья	Запасы сырья
A	B	C
какао
сахар
наполнитель
прибыль

 

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

 

№ вар.

а11

а12

а13

а21

а22

а23

а31

а32

а33

b1

b2

b3

c1

c2

с3

 

Варианты 6 – 10. В рационе бройлерных цыплят птицеводческой фермы используется два вида кормов A и B. Цыплята должны получать три вида питательных веществ (известняк, зерно, соевые бобы). Содержание единиц питательных веществ в 1 кг каждого из видов корма приведено в таблице:

 

 

Питательные вещества	Содержание питательного вещества в единице корма	Необходимое количество питательного вещества
A	B
известняк
зерно
соевые бобы
стоимость единицы корма

 

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

 

№ вар.	а11	а12	а21	а22	а31	а32	b1	b2	b3	c1	c2

Задача № 2.Решить задачу линейного программирования графическим методом

 

 

 

 

 

Исходные данные записаны в таблице.

 

№ вар.	а11	а12	а21	а22	а31	а32	b1	b2	b3				c1	c2	f
		-1	-1			-3								-3	min
			-2												max
		-3	-5											-1	min
			-5												max
			-4												max
	-4		-1												max
				-2									-3		max
		-2	-1			-3								-2	min
			-1											-2	max
				-1											max

 

Задача № 3. Решить симплексным методом задачу, математическая модель которой имеет следующий вид:

F(X) = c₁ x₁ + c₂ x₂ + c₃ x₃ max (min)

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ b₁,

a₂₁x₁ + a₂₂x₂ + a₂₃x₃ b₂,

a₃₁x₁ + a₃₂x₂ + a₃₃x₃ b₃,

x_i .

 

№	a11	a12	a13	a21	a22	a23	a31	a32	a33	b1	b2	b3				c1	c2	c3	F
		-1			-2						-6						-1	-3	min
																			max
																			min
				-1					-1										min
																			max
																			max
								-1								-3	-2	-2	min
	-1								-1							-1		-3	min
	-3															-3	-2		min
	-3			-3				-4								-5	-2	-3	min

 

Задача № 4.Целевая функция ЗПР в условиях неопределенности задана таблицей

	В1	В2	В3	В4
А1
А2
А3
А4

 

 

Выбор, какой альтернативы здесь следует считать оптимальным? Решить четырьмя способами, применив критерии Лапласа, Вальда, Гурвица, Сэвиджа.

 

 

а11

а12

а13

а14

а21

а22

а23

а24

а31

а32

а33

а34

а41

а42

а43

а44

Задача № 5.

  № варианта   Д Ж У № варианта   Д Ж У … Задача № 6.Найдите решение следующей матричной игры   …  

Основная литература

1. Лунгу К.Н. Линейное программирование. Руководство к решению задач. – М.: ФИЗМАТЛИТ, 2005.

2. Красс М.С., Чупрынов Б.П. Математические методы и модели для магистрантов экономики: Учебное пособие. – СПб.: Питер, 2006.

Дополнительная литература

1. Бережная Е.М., Бережной В.И. Математические методы моделирования экономических систем. – М.: Финансы и статистика, 2001.

2. Таха Х.А. Введение в исследование операций. – М.: Вильямс, 2001.

3. Шелобаев С.И. Математические методы и модели. Уч.пособие. – М.: ЮНИТИ, 2000.

4. Краснов М.Л., Киселев А.И. и др. Высшая математика. Учебник. Т.5. – М.: Эдиториал УРСС, 2002.

5. Розен В.В. Математические модели принятия решений в экономике. Учебное пособие. – М.: Книжный дом “ Университет”, Высшая школа, 2002.