查看: 3970|回复: 3

有没有哪位高人会用动态规划来解线性规划的题？附题一道

[复制链接]

字体大小: 正常放大

zhaobener

5 主题	3 听众	44 积分

升级 41.05%

该用户从未签到

电梯直达

1^#

发表于 2011-3-17 11:29 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

Max             Z=3 x1 + 7 x2 + 6 f(x3)subject to
                     x1 + 3 x2 + 2 x3  <= 6
                     x1 + x2 <= 5
and
                     x1>=0; x2>=0; x3>=0

当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3

用动态规划来解谢谢（lingo之类的我知道如何求解主要想知道计算过程）

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

jerrybond6

20 主题	6 听众	841 积分

升级 60.25%

TA的每日心情

	开心 2013-3-1 00:03

签到天数: 44 天

[LV.5]常住居民I

自我介绍: 数学建模与ACM爱好者

群组: 哈尔滨工业大学建模团

群组: 小草的客厅

群组: 数学建模保研联盟

2^#

发表于 2011-3-17 16:41 |只看该作者 |招呼Ta 关注Ta

本帖最后由 jerrybond6 于 2011-3-17 16:45 编辑

根据 s.t.可知 :
0<=x1<=5;
0<=x2<=2;
0<=x3<=3;

动态规划过程如下：

int dp[6][3][4], maxn, tmp, ans;

memset(dp,0,sizoef(dp));

for (i=0;i<=5;i++)
for (j=0;j<=2;j++)
      for (k=0;k<=3;k++)
      {
         maxn=0;
         if (i>0)
         {
            tmp=dp[i-1][j][k]+3;
            if (tmp>maxn)
                  maxn=tmp;
         }
         if (j>0)
         {
            tmp=dp[j-1][k]+7;
4 R5 u6 l( e+ f1 `8 _* E             if (tmp>maxn)3 F- T/ M8 F% z* I: n
                  maxn=tmp;1 M" x* _6 ]0 B9 I* ]' F
         }
. ~# o( ]: J/ T# O, A: ?0 l- F          if (k>0)
3 v" C5 V" m2 r, T! c4 \          {2 p2 q; s( N, j$ e" n! Z% ^
            tmp=dp[j][k-1]+6;- P2 j( D0 o& a% I% {7 ]
            if (tmp>maxn)+ I  A* D' g7 q3 M' o
                  maxn=tmp;
4 T2 ~# f. G2 [          }
! U, _0 `2 u4 @0 v          dp[j][k]=maxn;) f7 m% X" C8 c2 w! i4 K' c
      }
8 q$ \% X4 ^( O5 f- {( r9 M" ~  l2 @2 f2 x( _, R! q4 [- c- f
ans=0;2 U3 G; v( t  \. ?4 K9 ^
for (i=0;i<=5;i++)
4 e# Y' L/ i1 i2 M( `# v+ B1 i) v for (j=0;j<=2;j++)9 ^5 q, A" p) F9 H
      for (k=0;k<=3;k++)
2 r: l0 z7 Q- S! o3 e% P, F       {
6 B8 |. W, n5 s0 Q* t3 b7 ^          if (i+3*j+2*k>6)# |7 O9 Y1 J$ N  E  F
            continue;
1 U0 s' o9 f1 D6 P& J          if (i+j>5)5 d0 K2 `; l9 F  N% Q# P; c, M
            continue;
7 D( f" C1 t5 w7 d/ G/ P  D& d          tmp=dp[j][k];1 y; l+ Z% j  @# h  g, O
         if (k>0)) a1 G" s" T) u1 P; g+ @( i+ H
            tmp-=6;
: H+ v( R* U0 B1 y0 a) J7 s! y          if (tmp>ans)5 v0 g, l: }' d  ^3 U
            ans=tmp;, x# S: v: C9 v8 H' U
      }+ v$ N/ I( _7 A' f$ |
printf("%d\n", ans);
& C. m9 }( Q) k3 e1 s% u  Jans极为目标函数的最大值。9 T7 z! D! g0 X; C3 K