Задача распределения капиталовложений методом динамического программирования.

Методом динамического программирования решить задачу распределения капитальных вложений между четырьмя предприятиями производственного объединения, располагающего суммой в 700 тыс. руб., по исходным данным, приведенным в приложении 3 (выделяемые суммы кратны 100 тыс.).

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

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

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

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

0 X

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

F₁()=f₁().

Рассмотрим конкретный пример. Пусть производственное объединение состоит из четырех предприятий (n=4). Общая сумма капитальных вложений равна 700 тыс. рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей. Значения функций f_j(x_j) приведены в таблице 1.

Таблица 1.

Xj	0	100	200	300	400	500	600	700
f1(xj)	0	15	26	38	45	52	58	63
f2(xj)	0	10	17	23	29	34	38	41
f3(xj)	0	11	19	26	30	33	35	36
f4(xj)	0	25	34	41	46	50	53	56

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

Таблица 2.

	-х2	0	100	200	300	400	500	600	700
х2		0	15	26	38	45	52	58	63
0	0	0	15	26	38	45	52	58	63
100	10	10	25	36	48	55	62	68	---
200	17	17	32	43	55	62	69	---	---
300	23	23	38	49	61	68	---	---	---
400	29	29	44	55	67	---	---	---	---
500	34	34	49	60	---	---	---	---	---
600	38	38	53	---	---	---	---	---	---
700	41	41	---	---	---	---	---	---	---

Таблица 3.

	0	100	200	300	400	500	600	700
F2()	0	15	26	38	48	55	62	69
x2()	0	0	0	0	100	100	100	200
x2()						200	200

Продолжая процесс, табулируем функции F₃(),() и т.д.

Таблица 4.

	-x3	0	100	200	300	400	500	600	700
x3		0	15	26	38	48	55	62	69
0	0	0*	15*	26*	38*	48	55	62	69
100	11	11	26*	37	49*	59*	66	73	---
200	19	19	34	45	57	67*	74*	---	---
300	26	26	41	52	64	74*	---	---	---
400	30	30	45	56	68	---	---	---	---
500	33	33	48	59	---	---	---	---	---
600	35	35	50	---	---	---	---	---	---
700	36	36	---	---	---	---	---	---	---

Таблица 5.

	0	100	200	300	400	500	600	700
F3()	0	15	26	38	49	59	67	74
x3()	0	0	0	0	100	100	200	200
x3()			100					300

Таблица 6.

	-x4	0	100	200	300	400	500	600	700
x4		0	15	26	38	49	59	67	74
0	0	0	15	26	38	49	59	67	74
100	25	25						92
200	34	34					93*
300	41	41				90
400	46	46			84
500	50	50		76
600	53	53	68
700	56	56

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

Z_max= 93 тыс. руб.,

причем четвертому предприятию должно быть выделено

х^*₄ =₄ (700) = 200 тыс. руб.

На долю остальных трех предприятий остается 500 тыс. руб. Из табл. 5 видно, что третьему предприятию должно быть выделено

x^*₃=₃(700-x^*₄) =₃ (500) = 100 тыс. руб.

Продолжая обратный процесс, находим

x*₂=₂(700 - x*₄- x*₃) =₂(400) = 100 тыс. руб.

На долю первого предприятия остается

x*₁= 700 - x*₄- x*₃- x*₂= 300 тыс. руб.

Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям:

x*₁=300; x*₂=100; x*₃= 100; x*₄= 200.

Оно обеспечивает производственному объединению наибольший воможный прирост прибыли 93 тыс. руб.

f₁(x*₁) + f₂(x*₂) + f₃(x*₃) + f₄(x*₄) = z _max=38+10+11+34=93

Ответ: Оптимальная производственная программа имеет вид:

Х1* = 300 ; Х2* = 100 ; Х3* = 100 ; Х4* = 200 , при этом максимальная прибыль составляет 93 тыс. руб.

Матричная игра как модель конкуренции

и сотрудничества

Рассмотреть матричную игру как модель сотрудничества и конкуренции, взяв исходные данные из приложения 5. Найти графически решение игры. Указать, как проявляется конкуренция между игроками и сотрудничество между ними.

Пусть игроки – Первый и Второй , играют в матричную игру с матрицей A=a_{i j} . Пусть стратегия Первого естьР, а ВторогоQ.Тогда выигрыш Первого есть с.в.W(P,Q)cрядом распределения:

W(P*,j)	a1j		...		aij		...		amj
	p1*		...		pi*		...		pm*

Математическое ожидание этой с.в., т.е.есть средний выигрыш Первого. ПустьD[W(P,Q)]есть дисперсия этой с.в. Естественно назвать среднее квадратическое

отклонение с.в. W(P,Q)т.е. риском для Первого при игре со стратегиямиP,Q.

Поскольку выигрыш Первого есть проигрыш для Второго, то W(P,Q)есть случайный проигрыш Второго иrвполне естественно можно назвать риском игры с такими стратегиями и для Второго.

Предположу сначала, что игроки озабочены только максимизацией среднего дохода за партию игры – обычная цель в таких играх. Тогда игроки будут играть со своими оптимальными стратегиями: – Первый игрок и– Второй.

Математическое ожидание с. в. называется ценой игры, обозначу ее.

Вычислю дисперсию выигрыша Первого при оптимальных стратегиях игроков.

.

Так как , а черезсумма обозначена.

Замечу, что в сумме можно оставить лишь те слагаемые, у которых

Замечу теперь, что если Первый играет со стратегией , а Второй отвечает-й чистой стратегией, то выигрыш первого есть с.в. с рядом распределения:

W(P*,j)	a1j		...		aij		...		amj
	p1*		...		pi*		...		pm*

Если есть оптимальная стратегия Первого, а, то из теории матричных игр с нулевой суммой известно, что выигрыш Первого при таких стратегиях по-прежнему равен цене игры, а дисперсия выигрыша Первого при этом равна, то есть равна. Таким образом, что происходит с риском выигрыша Первого, можно понять, сравнив дисперсию при оптимальных стратегияхи дисперсиюили величиныи. ПустьКак легко понять, если средиесть разные числа, то

Теперь можно сделать следующий вывод:

Чуть-чуть отойдя от своей оптимальной стратегии (смотрите ниже Задачу) и таким образом почти не уменьшив свой выигрыш, Первый может значительно уменьшить свой риск. При этом уменьшается и риск Второго, что отвечает и его интересам.

Чисто математически можно сказать, что в описанной ситуации риск выигрыша Первого не зависит от его стратегии непрерывно.

Рассмотрю подробно пример матричной игры с матрицей с матрицейa_{i j}. Как известно, общий случай в окрестности оптимальных стратегий игроков сводится к анализу такой игры.

Исходные данные:

0. -3 -5 0

1. 0 2 -5

Так как ни один столбец не доминирует над другим, оставляем все без изменений.

Рассмотрим варианты: первый играет по смешанной стратегии, а второй по чистой. Подсчитаем математическое ожидание выигрыша:

M₁X=1*x*1+(2)*(1-x)*1

M₂X=-3*x*1+0*(1-x)*1

M₃X=-5*x*1+2*(1-x)*1

M₄X=0*x*1+(-5)*(1-x)*1

Графическое решение:

М(х)

|

2

1 х

0

||

M -3

|V |||

-5 -5

На рисунке ищем верхнюю точку нижней огибающей. Это точка М. Точка М показывает цену игры и оптимальную стратегию первого игрока.

Точка М находится на пересечении прямых 3 и 4:

-5*x*1+2*(1-x)*1=0*x*1+(-5)*(1-x)*1

-5x + 2 – 2x = -5 + 5x

-5x – 2x – 5x = -2 – 5

-12x = -7

x=7/12

x*- оптимальная смешенная стратегия первого игрока.

x* = (7/12; (1-7/12)

x* = (7/12; 5/12)

v= цена игры

v=-5*7/12 + 2*(1-7/12)=-35/12 + 2 – 14/12 = -49/12 +2 = -25/12

или

v= -5(1-7/12) = -5 + 35/12 = -25/12

Так как точка М лежит на пересечении 3-го и 4-го выражения, то оптимальную смешенную стратегию для 2-го игрока будим выбирать в виде:

1 -3 -5 0

2 0 2 -5

0 0 q 1-q

0<=q<=1

Рассмотрим варианты, когда второй игрок играет в смешанных стратегиях, а первый в чистых.

Можно рассмотреть два варианта, т.к. X^*1 = 7/12 > 0

X^*2 = 5/12 > 0

Можно выбрать любой из них:

M₁(q)=1*0*1-3*0*1-5*q*1+0*(1-q)*1 = -5q

M₁(q)= v

-5q=-25/12

q=25/12*1/5

q = 5/12

Варианты, для которых мат. ожидание выигрыша первого игрока одно и то же и равно цене игры:

M(P*;Q*)=M((1;0);Q*)=M((0;1);Q*)=M(P*(0;0;1;0)= M(P*(0;0;0;1)= v= -25/12

1. M(P*;Q*)= v= -25/12

1 -3 -5 0

2 0 2 -5

P*=(7/12;5/12)

Q*=(0;0;5/12;7/12)

x	1	-3	-5	0	2	0	2	-5
p	0	0	35/144	49/144	0	0	25/144	35/144

DX₁=MX₁²-(MX₁)²

MX₁= v=-25/12; MX₁²=625/144

MX₁²=25*35/144 + 0*49/144 + 4*25/144 + 25*35/144 =

= (875+100+875)/144 = 1850/144

DX₁=1850/144 - 625/144 = 1225/144

σX₁=√DX₁=√8,5≈2,92

2)

P*=(1;0)

Q*=(0;0;5/12;7/12)

x	1	-3	-5	0	2	0	2	-5
p	0	0	5/12	7/12	0	0	0	0

DX₂=MX₂²-(MX₂)²

MX₂= v=-25/12; MX₂²=625/144

MX₂²=25*5/12+ 0*7/12=125/12

DX₂=125/12 - 625/144 = 875/144 = 6,1

σX₂=√DX₂=√6,1≈2,47

3)

P*=(0;1)

Q*=(0;0;5/12;7/12)

x	1	-3	-5	0	2	0	2	-5
p	0	0	0	0	0	0	5/12	7/12

DX₃=MX₃²-(MX₃)²

MX₃= v=-25/12; MX₃²=625/144

MX₃²=4*5/12+25*7/12=195/12

DX₃=195/12 - 625/144 = 11,9

σX₃=√DX₃=√11,9≈3,44

4)

P*=(7/12;5/12)

Q*=(0;0;1;0)

x	1	-3	-5	0	2	0	2	-5
p	0	0	7/12	0	0	0	5/12	0

DX₄=MX₄²-(MX₄)²

MX₄= v=-25/12; MX₄²=625/144

MX₄²=25*7/12+4*5/12=195/12

DX₄=195/12-625/144=11,91

σX₄=√DX₄=√11,91≈3,45

5)

P*=(7/12;5/12)

Q*=(0;0;0;1)

x	1	-3	-5	0	2	0	2	-5
p	0	0	0	7/12	0	0	0	5/12

DX₅=MX₅²-(MX₅)²

MX₅= v=-25/12; MX₅²=625/144

MX₅²=0*7/12+25*5/12=125/12

DX₅=125/12-625/144=6,06

σX₅=√DX₅=√6,06≈2,47

Наибольшая конкуренция достигается в 4-ом варианте.

Наибольшее сотрудничество достигается в 2-ом и в 5-ом варианте.