Question

用动态规划法求解静态现行规划问题，过程怎么写啊，求助！

max 3x1+5x2

x1≤4

x2≤6

3x1+2x2≤18

x1,x2≥0

求助啊，过程怎么写啊， 请大哥大姐帮个忙啊， 可以将过程发到我邮箱 xjxjxxjj@qq.com 有过程的话一定加分！

Answer 1

嗯？动态规划和线性规划应该是两回事。
我这里有线性规划的程序。
对于你的问题我的程序得出来的结果是36
const
maxn=2400;
oo=1e30;
xx=1e-6;
var
A:Array[0..maxn,0..maxn] of double;
C:array[0..maxn] of double;
An,Bn,next:array[0..maxn] of longint;
i,j,n,m,x,SA,SB,SC,TQ,TM,_m:longint;
procedure swap(var a,b:longint);
var k:longint;
begin
k:=a; a:=b; b:=k;
end;

procedure pivot(l,e:longint);
var
i,j,k:longint;
temp:double;
begin
swap(An[e],Bn[l]);
temp:=A[l,e]; A[l,e]:=1;k:=Maxn-1;
for i:=0 to n do
if abs(a[l,i])>xx then
begin
A[l,i]:=A[l,i]/temp;
next[k]:=i;
k:=i;
end;
next[k]:=maxn;
for i:=0 to m do
if i<>l then
begin
temp:=A[i,e]; A[i,e]:=0;
j:=next[Maxn-1];
while j<>maxn do
begin
A[i,j]:=A[i,j]-temp*A[l,j];
j:=next[j];
end;
end;
end;
procedure printNoans;
begin
halt;
end;
procedure printMaxans;
begin
halt;
end;
procedure simplex;
var
l,e:longint;
delta:double;
begin
repeat
for e:=1 to n do if a[0,e]>xx then break;
if a[0,e]<=xx then exit;
delta:=oo;
for i:=1 to m do
if (A[i,e]>xx)and (delta>a[i,0]/A[i,e]) then
begin
delta:=a[i,0]/A[i,e];
l:=i;
end;
if delta=oo then PrintMaxans;
pivot(l,e);
until false;
end;

procedure prepare;
var
i,j,k,l:longint;
begin
l:=1;
for i:=2 to m do if a[l,0]>a[i,0] then l:=i;
if a[l,0]>=xx then exit;
C:=a[0];fillchar(a[0],sizeof(a[0]),0);
inc(n); An[n]:=0;
for i:=0 to m do A[i,n]:=-1;
pivot(l,n);simplex;
if a[0,0]>xx then PrintNoans;
for i:=1 to m do
for j:=1 to n do
if (Bn[i]=0)and(abs(a[i,j])>xx) then
begin
pivot(i,j);
break;
end;
for k:=1 to n do if An[k]=0 then break;
for i:=k to n-1 do An[i]:=An[i+1];
An[n]:=0;
for i:=1 to m do
begin
for j:=k to n-1 do A[i,j]:=A[i,j+1];
A[i,n]:=0;
end;
dec(n);
fillchar(a[0],sizeof(a[0]),0);
for k:=1 to n do
if An[k]>0 then
a[0,k]:=C[An[k]];
for k:=1 to m do
if Bn[k]>0 then
for j:=0 to n do
a[0,j]:=a[0,j]-A[k,j]*c[bn[k]];
end;
procedure init;
begin
assign(input,'input.txt');
assign(output,'output.txt');
reset(input);
rewrite(output);
readln(n,m);//读入n个未知数 m个不等式
for i:=1 to m do
begin
for j:=1 to n do
read(a[i,j]);readln(a[i,0]);//读入第i个不等式的系数和常数。
end;
for i:=1 to n do read(a[0,i]);//读入目标函数
for i:=1 to n do An[i]:=i;
for i:=1 to m do Bn[i]:=-i;
end;

begin
init;
prepare;
simplex;
writeln(abs(a[0,0]):0:0);
close(input);
close(output);
end.
//对于你的的样例输入数据为：
//2 3 n个未知数 m个不等式
//1 0 4 1x1+0x2<=4
//0 1 6 0x1+1x2<=6
//3 2 18 3x1+2x2<=18
//3 5 max(3x1+5x2)

Answer 2

分阶段:第1阶段给产品1分配产量，第2阶段给产品2分配产量
在第n阶段的状态 = sn = (sn1,sn2,sn3) = 三种可使用的资源剩下的量
在第n阶段的决策= xn =给产品1分配的产量
在第n阶段的利润: cnxn
目标函数: 3x1 + 5x2
fn(sn) =在第n阶段开始可用的资源为sn= (sn1,sn2,sn3) 的条件下，从第n阶段的到第2阶段的最大利润
递推关系
fn(sn) = max xn {cnxn + fn+1(sn)}
边界条件: f3(s3)= f3(R31, R32, R33)=0
目标: f1(s1) =f1(4,12,18)

第2阶段决策:
f2(s2)=f2(R21,R22,R23)=f2(4-x1,12,18-3x1)
=max 2x2≤12, 2x2≤18-3x1, x2≥0 {5x2+f3(s3)}
=max 2x2≤12, 2x2≤18-3x1, x2≥0 {5x2}
x2*=min{12/2,(18-3x1)/2} = min{6, 9-(3/2)x1}
f2(s2) = 5 min{6, 9-(3/2)x1}
第1阶段决策:
f1(s1)=f1(R11,R12,R13)=f1(4,12,18)
=max x1≤4, 3x1≤18, x1≥0 {3x1+ f2(s2) }
=max x1≤4, 3x1≤18, x1≥0 {3x1+ 5min{6, 9-(3/2)x1}}

Case 1: 9-(3/2)x1 ≥ 6, i.e., x1≤2:
f1(s1) =max x1≤4, 3x1≤18, x1≥0 {3x1+ 5(6)}
=max x1≤4, 3x1≤18, x1≥0 {3x1+ 30}
x1*=2(满足x1≤2） , f1(4,12,18)=3(2)+30=36

Case 2: If 9-(3/2)x1 ≤ 6, i.e., x1≥2:
f1(s1) =max x1≤4, 3x1≤18, x1≥0 {3x1+ 5[9-(3/2)x1]}
=max x1≤4, 3x1≤18, x1≥0 {-(9/2)x1+45}
x1*=2(满足x1≥2）, f1(4,12,18)=-(9/2)(2)+45=36

x1*=2
x2*=min{6,9-(3/2)x1}=min(6,9-(3/2)(2)}=min{6,6}=6