Линейная производственная задача

 

Итак, выполняется  условие оптимальности: Dij £ 0, и мы получили оптимальный план затрат.

Lоптим.=56*2+4+35*4+15*3+29*4+30*3=507

LD=519-507=12

 

 

 

 

 

 

 

 

 

Динамическое  программирование.

 

Распределение капитальных вложений

 

 

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

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

Z=f₁(x₁)+f₂(x₂)+...+f_n(x_n)

при ограничении  по общей сумме капвложений 

х₁ + х₂ +...+х_n = b

причём  будем считать, что все переменные x_j принимают только целые значения x_j =1,2,...

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

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

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

F_k(x) = max {f_k(x_k) + F_k-1(x-x_k)}

         0 £ X £ x

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

F₁(x)=f₁(x).

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

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

Прежде  всего заполняем табл.3. Значения f₂(x₂) складываем со значениями F₁(x-x₂)=f₁(x-x₂) и на каждой побочной диагонали находим наибольшее число, которое помечаем звёздочкой. Заполняем табл .3.

Продолжая процесс табулируем функции F₃(x), x₃(x) и т.д. В табл.6 заполняем только одну диагональ для значения x=700.

 

Таблица 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.

	x-х2	0	100	200	300	400	500	600	700
х2		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.

x	0	100	200	300	400	500	600	700
F2(x)	0	85	160	175	190	201	211	219
x2(x)	0	100	100	200	200	300	300	300

 

Таблица 4.

	x-x3	0	100	200	300	400	500	600	700
x3		0	85	160	175	190	201	211	219
0	0	0	85*	160*	175	190	201	211	219
100	42	42	127	202*	117	232	243	253	---
200	58	58	143	218*	233*	248*	259	---	---
300	71	71	156	231	246	261*	---	---	---
400	80	80	165	240	255	---	---	---	---
500	89	89	174	249	---	---	---	---	---
600	95	95	180	---	---	---	---	---	---
700	100	100	---	---	---	---	---	---	---

Таблица 5.

x	0	100	200	300	400	500	600	700
F3(x)	0	85	160	202	218	233	248	261
x3(x)	0	0	0	100	200	200	200	300

 

 

 

 

Таблица 6.

	x-x4	0	100	200	300	400	500	600	700
x4		0	85	160	202	218	233	248	261
0	0	0	85	160	202	218	233	248	261
100	28	28						276
200	45	45					278
300	66	66				284*
400	78	78			280
500	90	90		250
600	102	102	187
700	113	113

 

 

Наибольшее  число диагонали в табл.6 :

Z_max = 284 тыс. рублей

X4*  = 300      

X3*+X2*+X1*=700–300=400

 

В табл.5:   

   где  сумма равна 400       

Х3* = 200                               

Х1*+Х2*=400-200=200

 

В табл.3.

   где сумма равна 200

Х2*=100   

Х1*=100

Оптимальная программа:  1)  Х1*=100 ;       Х2*=100 ;

                                                  Х3*=200 ;       Х4*=300

Z_max(X1*;... X4*)=284 

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

 

Два игрока играют в матричную игру

 

-9	0	3	-1	3
2	-3	2	1	-2
4	-5	8	8	-7
2	-3	2	1	-2

 

Требуется найти решения игры для  каждого игрока, а именно пару оптимальных  стратегий, при которых каждому  из игроков не выгодно отступать  от них, поскольку это приведёт к  их проигрышу.

Проведем анализ на доменирование и получим следующую матрицу:

 

-9	0	-1	3
2	-3	1	-2
4	-5	8	-7

 

При анализе игры на седловую точку, нижняя цена игры будет a= -3, верхняя b= 4. Решения в чистых стратегиях нет, будем искать решение в смешанных.

Прибавим к каждому элементу константу, равную 9. Решение игры при  этом не изменится, а цена игры возрастет  на 9 и будет больше 0.

Матрица примет следующий вид:

 

0	9	8	12
11	6	10	7
13	4	17	2