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

Рассмотрим нелинейную задачу распределения  ресурсов между предприятиями отрасли. Предположим, что указано 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 

 

ТЕОРИЯ МАТРИЧНЫХ ИГР.

Дана матрица:      1   -2   -4   0

                             2    2    1   -3

У первого игрока 2 чистых стратегии, у второго 4 чистых стратегий.

Формула математического  ожидания  выигрыша:

 М(R, Q) = å å a_ij p_iq_j

Для выявления активных стратегий воспользуемся рисунком 4 и преобразуем исходную матрицу добавив 5:

1	-2	-4	0
2	2	1	-3

 

6	3	1	5
7	7	6	2

 Û

• М –точка минимально

                                                                  гарантированных выигрышей 

                                                         В3 и В4 – активные стратегии

                                                         Pi – вероятность выигрыша первого

                                                              игрока, применяя i-ую стратегию

                                                         Qj – вероятность выигрыша второго

                                                               игрока, применяя j-ую стратегию

                                                          n - цена игры

	В1	В2
А1	1	5
А2	6	2

Имеем:

 

 

 

Найдем оптимальные стратегии: P*=(p1;p2), Q*=(q1;q2).

    1p1+6p2=n

    5p1+2p2=n  Þ   p1+6p2=5p1+2p2   Þ       p1=p2     Þ    p1=1/2