РЕШЕНИЕ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ КАПВЛОЖЕНИЙ МЕТОДОМ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ.

Динамическое программирование - это вычислительный метод для решения задач управления определённой структуры. Данная задача с 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
f1(xj)
f2(xj)
f3(xj)
f4(xj)

 

Таблица 2.

	x-х2
х2
		85*	160*						---
			175*	190*				---	---
				201*	211*	219*	---	---	---
						---	---	---	---
					---	---	---	---	---
				---	---	---	---	---	---
			---	---	---	---	---	---	---

 

Таблица 3.

x
F2(x)
x2(x)

 

Таблица 4.

	x-x3
x3
			85*	160*
				202*					---
				218*	233*	248*		---	---
						261*	---	---	---
						---	---	---	---
					---	---	---	---	---
				---	---	---	---	---	---
			---	---	---	---	---	---	---

Таблица 5.

x
F3(x)
x3(x)

 

 

Таблица 6.

	x-x4
x4
						284*

 

 

Наибольшее число диагонали в табл.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:

	-2	-4
			-3

 

Û

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

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

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

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

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

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

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

n - цена игры

	В1	В2
А1
А2

Имеем:

 

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

{

{

{

{

1p1+6p2=n

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

p1+p2=1 p1+p2=1 p1+p2=1 p2=1/2

P*=(1/2;1/2)

{

{

{

{

1q1+5q2=n

6q1+2q2=n Þ q1+5q2=6q1+2q2 Þ q1=3/5q2Þ q1=3/8

q1+q2=1 q1+q2=1 1+q2=1 q2=5/8

Q*=(3/8;5/8)

Найдем риски игры и среднее значение выигрыша.

M3–среднее значение выигрыша, если противник применит стратегию В3.

r – риск; r = s

M3=1/2*1+1/2*6=3,5

M4=1/2*1+1/2*6=3,5

D3=1*1/2+36*1/2-12,25=6,25; r3=Ö6,25=2,5

D4=25*1/2+4*1/2-12,25=2,25; r4=Ö2,25=1,5

Mобщ.=1*1/2*3/8+6*1/2*5/8+5*1/2*3/8+2*1/2*5/8=58/16=3,625

Среднее значение выигрыша равно 3,625.

Dобщ.=1*1/2*3/8+36*1/2*5/8+25*1/2*3/8+4*1/2*5/8-3364/256=4,18

sобщ.= 4,18=2,04