Быстрый поиск

Реферат: Линейное и динамическое программирование

Xоpt1 = 15 30 0 0

0 0 29 33

Однако, так как оценка клетки D32=0, делаем вывод о наличие другого возможного оптимального решения. Для его нахождения строим цикл пересчета клетки 32: 32-22-21-11-14-34, производим перераспределение:

Таблица 3

Потребл Произв	b1=48	b2=30	b3=29	b4=40	b5=8
a1=40	3 3	6	4	37 3	0	p1=0
a2=45	45 2	3	1	3	0	p2=-1
a3=70	6	30 5	29 1	3 4	8 0	p3=1
	q1=3	q2=4	q3=0	q4=3	q5= -1

Находим новые потенциалы. Получаем рi и qj соответственно равные потенциалам первого базисного оптимального решения (см. табл. 2). Исходя из этого Dmax=D32, однако элемент с индексом 32 уже присутствует в базисе, поэтому пересчет не имеет смысла. Таким образом получаем второе и последнее базисное оптимальное решение:

3 0 0 37

Xоpt2 = 45 0 0 0

0 30 29 3

Оптимальное распределение инвестиций

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

Пусть 4 фирмы образуют объединение. Рассмотрим задачу распределения инвестиций в размере 700 тыс. рублей по этим 4 фирмам. Размер инвестиций пусть будет кратен 100 тыс. рублей. Эффект от направления i-й фирме инвестиций в размере ξ (сотен тыс. рублей) выражается функцией fi(xi). Приходим к задаче fl(xl)+f2(x2)+f3(x3)+f4(x4)àmax , где xi - пока еще неизвестный размер х1+х2+х3+х4≤7; х1,х2,х3.х4≥0 инвестиций i-й фирме. Эта задача решается методом динамического программирования: последовательно ищется оптимальное распределение для k=2,3 и 4 фирм.

Пусть первым двум фирмам выделено ξ инвестиций. обозначим z2(ξ) величину инвестиций 2-й фирме, при которой сумма f2(z2j)+fl(ξ-z2j), 0≤j≤ ξ максимальна, саму эту максимальную величину обозначим F2(ξ). Далее действуем также: находим функции z3 и F3 и т.д. На k-ом шаге для нахождения Fk(ξ) используем основное рекуррентное соотношение: Fk(ξ)=max{fkj(хk)+F(k-1)( ξ-хk); 0 ≤ хk ≤ ξ

xj	100	200	300	400	500	600	700
f1	28	45	65	78	90	102	113
f2	25	41	55	65	75	80	85
f3	15	25	40	56	62	73	82
f4	20	33	42	48	53	56	58

Таблица 1

x2	ξ-х2	0	100	200	300	400	500	600	700
x2	F1(ξ-x2) f2(x2)	0	28	45	65	78	90	102	113
0	0	0	28	45	65	78	90	102	113
100	25	25	53	70	90	103	115	127
200	41	41	69	86	*106*	119	131
300	55	55	83	100	*120*	*133*
400	65	65	93	110	130
500	75	75	103	120
600	80	80	108
700	85	85

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

ξ	100	200	300	400	500	600	700
F2	28	53	70	90	106	120	133
x2	0	100	100	100	200	300	300

Таблица 2

х3	ξ-х2	0	100	200	300	400	500	600	700
х3	F3(ξ-x3) f3(x3)	0	28	53	70	90	106	120	133
0	0	0	28	53	70	90	*106*	120	133
100	15	15	43	68	85	105	*121*	*135*
200	25	25	53	78	95	115	131
300	40	40	68	93	110	130
400	56	56	84	109	125
500	62	62	90	115
600	73	73	101
700	82	82