Курсовая работа по дисциплине «Прикладная математика» (стр. 3 )

Для заполненных клеток α i + β j = Cij, для них Dij = 0

Для незаполненных клеток Dij= α i + β j - cij

Так как не все характеристики отрицательны (например, D13 = 2), то для найденной свободной клетки строим цикл пересчёта. Производим перераспределение поставок вдоль цикла пересчета:

ПН ПО	56	35	48	30	11	αi
60	2	2	2	5	1	1	0	4	-3	0	α1 = -3
56		4
0		-3		0		-4		-3
50	4	4	4	4	3	3	2	2	-1	0	α2 = -1
	35	15
0		0		0		0		-1
70	5	6	5	5	4	4	3	3	0	0	α3 = 0
		29	30	11
-1		0		0		0		0
βi	β1 = 5	β2 = 5	β3 = 4	β4 = 3	β5 = 0

Решение оптимально, так как все D # 0.

Ответ: При этом 11 единиц продукции остаются у 3-ого производителя.

Zопт = 112 + 4 + 140 + 45 + 116 + 90 = 507

DZ = Zопор – Zопт = 519 – 507 = 12

5. Динамическое программирование. Распределение капитальных вложений

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

Рассмотрим нелинейную задачу распределения ресурсов между предприятиями отрасли. Предположим, что указано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через fj(xj) прирост мощности или прибыли на j-том предприятии, если оно получит xj рублей капвложений. Требуется найти такое распределение (х1, х2, ..., хn) капвложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли

Z=f1(x1)+f2(x2)+...+fn(xn)

при ограничении по общей сумме капвложений х1 + х2 +...+хn = b, причём будем считать, что все переменные xj принимают только целые значения xj =1,2,...

Функции fj(xj) мы считаем заданными, заметив, что их определение - довольно трудоёмкая экономическая задача.

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

Введём параметр состояния и определим функцию состояния. За параметр состояния x примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния Fk(x) определим как максимальную прибыль на первых k предприятиях, если они вместе получат x рублей. Параметр x может меняться от 0 до b. Если из x рублей k-ое предприятие получит Хк рублей, то каково бы ни было это значение, остальные x-Хк рублей естественно распределить между предприятиями от 10-го до (к-1)-го предприятия, чтобы была получен максимальная прибыль Fk-1(x-xk). Тогда прибыль k предприятий будет равна fk(xk) + Fk-1(x-xk). Надо выбрать такое значение xk между 0 и x, чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению:

Fk(x) = max {fk(xk) + Fk-1(x-xk)}

0 £ X £ x

для k=2,3,....,n. Если же k=1 ,то

F1(x)=f1(x).

В нашем случае производственное объединение состоит из 4-х предприятий (k=4).Общая сумма капвложений равна 700 тыс. рублей (b=700) , выделяемые предприятиям суммы кратны 100 тыс. рублей.

Значения функций fj(xj) приведены в таблице 1.

Таблица 1

xj	0	100	200	300	400	500	600	700
f1(xj)	0	75	90	100	108	113	115	117
f2(xj)	0	85	100	111	118	124	129	132
f3(xj)	0	42	58	71	80	89	95	100
f4(xj)	0	28	45	66	78	90	102	113

Прежде всего заполняем таблице2. Значения f2(x2) складываем со значениями F1(x-x2)=f1(x-x2) и на каждой побочной диагонали находим наибольшее число, которое помечаем звёздочкой. Продолжая процесс табулируем функции F3(x), x3(x) и т. д. В таблице 6 заполняем только одну диагональ для значения x=700.

Таблица 2

x-х2	0	100	200	300	400	500	600	700
X2	F(x-x2) f2(x2)	0	75	90	100	108	113	115	117
0	0	0	75	90	100	108	113	115	117
100	85	85*	160*	175*	185	193	198	200	---
200	100	100	175	190*	200	208	213	---	---
300	111	111	186	201*	211*	219*	---	---	---
400	118	118	193	208	218	---	---	---	---
500	124	124	199	214	---	---	---	---	---
600	129	129	204	---	---	---	---	---	---
700	132	132	---	---	---	---	---	---	---

Таблица 3