Задача распределения ресурсов

Постановка задачи.

Задана функция

.

Найти максимум этой функции при ограничениях:

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

,

где

Для решения данной задачи необходимо иметь алгоритм решения сформулированной выше задачи методом динамического программирования.

Алгоритм решения задачи

1) ,

2)

3)

4)

5)

6)

7) ?, если условие выполняется, то переход к пункту 8, иначе переход к пункту 9.

8)

9)

10) , если условие выполняется, то переход к пункту 11, иначе к пункту 6.

11) ,

12)

13) , если условие выполняется, то переход к пункту 14, иначе переход к пункту 4.

14) Вывод и

15) Перенос блока

16)

17) , если условие выполняется, то переход к пункту 18, иначе переход к пункту 3.

18)

19)

20)

21) Печать и

22)

23)

24) , если условие выполняется, то переход к пункту 25, иначе переход к пункту 20.

25) Stop.

Проиллюстрируем изложенный алгоритм на следующей тестовой задаче:

Максимизировать

при условиях

Сформулированная задача часто встречается в различных экономических приложениях и характеризует процесс распределения ресурсов.

Пусть необходимо распределить однотипных автомобилей для выполнения перевозок у клиентов. Считаются известными вероятности выполнения требуемых объемов перевозок одним автомобилем у каждого из клиентов и относительно важности этих перевозок.

Пусть - количество автомобилей , выделяемые - му клиенту, тогда вероятность выполнения всех перевозок -го клиента составляет

,

а математическое ожидание выполненного объема перевозок с учетом их важности у всех клиентов будет

Требуется распределить автомобили так, что бы максимизировать математическое ожидание .

Текст программы.

Решение задачи методом динамического программирования на алгоритмическом языке PASCAL.ABC.

Program dp;

const

h=3;

M=9;

var

x:array[1..1000] of integer;

k:array[0..1000] of integer;

p,w:array[1..1000] of real;

F:array[0..1000,0..1000] of real;

Ps:array[0..1000,0..1000] of integer;

j,i,N,g:integer;

T,R:real;

Begin

p[1]:=0.4; p[2]:=0.2; p[3]:=0.3;

w[1]:=0.5; w[2]:=0.2; w[3]:=0.3;

for i:=1 to h do

begin

for j:=0 to M do

F[i,j]:=0;

end;

j:=1;

repeat

N:=0;

repeat

T:=-1000000;

x[j]:=0;

repeat

begin

R:=p[j]*(1-power(1-w[j],x[j]))+F[j-1,N-x[j]];

if R>T then begin

T:=R;

g:=x[j];

end;

x[j]:=x[j]+1;

end;

until x[j]>N;

F[j,N]:=T;

ps[j,N]:=g;

N:=N+1;

until N>M;

j:=j+1;

until j>h;

writeln (' N',' |','F1(x1) ','|','Ps1(x1)','|','F2(x2) ','|','Ps2(x2)','|','F3(x3) ','|','Ps3(x3)','|');

for j:=0 to M do

begin

write (j:2,' |');

for i:=1 to h do

begin

write (F[i,j]:7:5,'|');

write (ps[i,j]:4,' |');

end;

writeln;

end;

j:=h;

k[j]:=M;

repeat

j:=j-1;

k[j]:=k[j+1]-Ps[j+1,k[j+1]];

until j=0 ;

T:=0;

for j:=1 to h do

if T<F[j,k[j]] then T:=F[j,k[j]];

writeln('F(x1опт,x2опт,x3опт)=',T:7:5);

for j:=1 to h do

write('x',j,'опт= ',Ps[j,k[j]],'; ');

end.

Контрольный расчет

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

	0.5		0.4
	0.2		0.3
	0.3		0.3

Все промежуточные вычисления по предыдущему алгоритму сведены в таблицу 1: Табл.1

N	F1(x1)	Ps1(x1)	F2(x2)	Ps2(x2)	F3(x3)	Ps3(x3)
	0.00000		0.00000		0.00000
	0.20000		0.20000		0.20000
	0.32000		0.32000		0.32000
	0.39200		0.39200		0.41000
	0.43520		0.45200		0.48200
	0.46112		0.49520		0.54500
	0.47667		0.53720		0.60500
	0.48600		0.56660		0.64910
	0.49160		0.59252		0.69230
	0.49496		0.61310		0.73430

Хопт = {4;2;3}.

Математическое ожидание равно 0.7343.

Применение программы для исходной задачи. Вариант 2821

Исходные данные для данного варианта:

N = 12	J = 3
	0.291		0.496
	0.192		0.297
	0.893		0.198

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

Таблица результатов: Табл.2

N	F1(x1)	Ps1(x1)	F2(x2)	Ps2(x2)	F3(x3)	Ps3(x3)
	0.00000		0.00000		0.00000
	0.41818		0.58548		0.58548
	0.62100		1.00366		1.00366
	0.71936		1.20648		1.20648
	0.76707		1.37392		1.37392
	0.79021		1.47229		1.48221
	0.80143		1.52018		1.58058
	0.80687		1.56789		1.67598
	0.80951		1.59103		1.76003
	0.81079		1.60472		1.83408
	0.81142		1.61595		1.89932
	0.81172		1.62139		1.95679
	0.81186		1.62531		2.00743

Хопт = {3;2;7}.

Математическое ожидание равно 2.00743.

В таблице 3 показаны результаты вычислений, когда .

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

	0.812		0.715
	0.82		0.714
	0.91		0.119

Таблица результатов: Табл.3

N	F1(x1)	Ps1(x1)	F2(x2)	Ps2(x2)	F3(x3)	Ps3(x3)
	0.00000		0.00000		0.00000
	0.58058		0.58548		0.58548
	0.74605		1.16606		1.16606
	0.79320		1.33351		1.33351
	0.80664		1.49897		1.49897
	0.81047		1.54686		1.60726
	0.81156		1.59402		1.70267
	0.81188		1.60772		1.78672
	0.81196		1.62116		1.86077
	0.81199		1.62507		1.92600
	0.81200		1.62890		1.98348
	0.81200		1.63002		2.03411
	0.81200		1.63112		2.08200

Хопт = {2;3;7}.

Математическое ожидание равно 2.08200.

В таблице 4 показаны результаты вычислений, когда .

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

	0.812		0.915
	0.82		0.714
	0.91		0.119

Таблица результатов: Табл.4

N	F1(x1)	Ps1(x1)	F2(x2)	Ps2(x2)	F3(x3)	Ps3(x3)
	0.00000		0.00000		0.00000
	0.74298		0.74298		0.74298
	0.80613		1.32846		1.32846
	0.81150		1.49591		1.49591
	0.81196		1.55906		1.60420
	0.81200		1.60695		1.69960
	0.81200		1.62065		1.78365
	0.81200		1.62602		1.85770
	0.81200		1.62993		1.92294
	0.81200		1.63105		1.98609
	0.81200		1.63151		2.04356
	0.81200		1.63183		2.09420
	0.81200		1.63192		2.14209

Хопт = {2;3;7}.

Математическое ожидание равно 2.14209.