查看: 4008|回复: 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;
) F( H+ D* u% C6 ~5 {) r$ j6 N             if (tmp>maxn)$ y. o, g+ k9 D8 k
                  maxn=tmp;
( V7 N: X6 @* K. }. C7 j          }- m- F0 n' q# F, Q5 o- y
         if (k>0)
1 q% o8 k% x/ X0 @2 E          {0 f0 P7 O0 S& i7 u4 U. v7 I
            tmp=dp[j][k-1]+6;! l: A+ _; O/ B: ~7 C% P- v6 h
            if (tmp>maxn)
) e& g8 }" e( n5 E: w% a$ H2 A4 a                   maxn=tmp;
" s; f7 A: I8 J* V3 J          }
' ]* i# T& U$ ~8 A          dp[j][k]=maxn;
+ E# D) g7 q, O+ l$ Y' m$ w+ @+ [: i       }# M3 [, i6 B8 w% C0 Z# E
- a! ?; w9 x* Z( h  @
ans=0;- ~+ Y8 v5 W+ B# t9 c) Q' d
for (i=0;i<=5;i++)3 T, c/ t6 w6 o" R
for (j=0;j<=2;j++)8 l+ ?9 l: }* X  T
      for (k=0;k<=3;k++)4 i0 v: Z; B/ S* z) M4 c
      {) `$ i2 a, ?7 F2 ]- o
         if (i+3*j+2*k>6)) `& Q4 _$ a0 }
            continue;
9 B. r* o: g! ^) B/ i          if (i+j>5)
4 q3 H6 B/ o  c+ y* T             continue;
0 l' g2 U4 N/ Z0 t% m' h: t          tmp=dp[j][k];
' G# z6 [5 n3 R+ v$ R6 D          if (k>0)
4 M4 g% {5 }' d3 H" E, L5 t, @             tmp-=6;+ v: b8 X0 Q& T0 f! ?! H7 ?
         if (tmp>ans)' P/ ]2 k! \" x' {. M5 W. E
            ans=tmp;9 _, k' _3 p8 H, \' B; c
      }+ i. p# {) |2 I7 f5 @& C
printf("%d\n", ans);
4 P" n; r7 g+ dans极为目标函数的最大值。
% m/ R; P; D1 s* l0 M! V