2017-11-30
478
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.
