Министерство образования и науки рф

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

ФГАОУ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ «МИСиС»

ИНСТИТУТ ЭУПП

КАФЕДРА БИСУП

Лабораторная работа №7 по дисциплине

Современные математические методы моделирования и
оптимизации управленческих решений
На тему: «Динамическое программирование»

Выполнили: Елпашев Д.В.

гр. МИБ-12-1

Вариант № 5

Проверил: Литвяк В.С.

Москва, 2012

1. Содержательная постановка задачи

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

2. Формальная постановка задачи

Коммерческому банку нужно (методом динамического программирования) распределить 100 у.е. в виде кредитов между четырьмя фирмами. В таблице 1 указаны значения прироста выпуска продукции на предприятиях в зависимости от выделенных средств х:

Таблица 1 – Прирост выпуска продукции

предприятие	g1(x)	g2(x)	g3(x)	g4(x)
x
	30+0,02*5 = 30,1
	55+5 = 60	49+5 = 54	58+5 = 63	39+5 = 44

Необходимо:

– решить игру, используя метод динамического программирования;

– решить задачу в среде EXCEL.

3. Решение задачи

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

Столбцы в таблице 1 это и есть частные критерии, оценивающие каждый шаг.

Следуя принципу Беллмана, оптимизацию начинаем с последнего 4-го шага.

1. Оптимизация 4-го шага (таблица 2), т.е. решение задачи:

max {g₄(x₄)} = (обозначим) = Z₄(S₃)

Таблица 2 – Оптимизация 4-го шага

x4 S3							Z4(S3)	x4^*
		-	-	-	-	-
			-	-	-	-
				-	-	-
					-	-
						-

2. Оптимизация 3-го шага (таблица 3), т.е. решение задачи:

max {g₃(x₃) + Z₄(S₂ - x₃)} = Z₃(S₂)

Таблица 3 – Оптимизация 3-го шага

x3 S2							Z3(S2)	x3^*
	0+0=0	-	-	-	-	-
	0+15=15	15+0=15	-	-	-	-		0 / 20
	0+15=15	15+15=30	30+0=30	-	-	-		20 / 40
	0+22=22	15+15=30	30+15=45	45+0=45	-	-		40 / 60
	0+36=36	15+22=37	30+15=45	45+15=60	57+0=57	-
	0+44=44	15+36=51	30+22=52	45+15=60	57+15=72	63+0=63

3. Оптимизация 2-го шага (таблица 4), т.е. решение задачи:

max {g₂(x₂) + Z₃(S₁ - x₂)} = Z₂(S₁)

Таблица 4 – Оптимизация 2-го шага

x2 S1							Z2(S1)	x2^*
	0+0=0	-	-	-	-	-
	0+15=15	26+0=26	-	-	-	-
	0+30=30	26+15=41	32+0=32	-	-	-
	0+45=45	26+30=56	32+15=47	50+0=50	-	-
	0+60=60	26+45=71	32+30=62	50+15=65	48+0=48	-
	0+72=72	26+60=86	32+45=77	50+30=80	48+15=54	54+0=54

4. Оптимизация 1-го шага (таблица 5), т.е. решение задачи:

max {g₁(x₁) + Z₂(S₀ - x₁)} = Z₁(S₀)

Таблица 5 – Оптимизация 1-го шага

x1 S0							Z1(S0)	x1^*
	0+86=86	10+71=81	30,1+56=86,1	49+41=90	51+26=77	60+0=60

5. Обратный ход – окончательный оптимальный набор шаговых уравнений

60 20 0/20 20/0

S₀ → S₁ → S₂ → S₃ → S₄

100 40 20 20/0 0

4. Анализ результатов

Две стратегии:

1) Выделим 1-му – 60, 2-му – 20, 3-му – 0, 4-му – 20, прибыль составит 49+26+0+15=90 у.е.

1) Выделим 1-му – 60, 2-му – 20, 3-му – 20, 4-му – 0, прибыль составит 49+26+15+0=90 у.е.

Дата добавления: 2015-09-29