数学建模社区-数学中国

标题: 有没有哪位高人会用动态规划来解线性规划的题？ 附题一道 [打印本页]
作者: zhaobener    时间: 2011-3-17 11:29
标题: 有没有哪位高人会用动态规划来解线性规划的题？ 附题一道
Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  + N! W# t* O  o' K+ \
                       x1 + 3 x2 + 2 x3  <= 6( g3 Z$ d  g8 f, \/ n6 \# D# n7 D( `
                       x1 + x2 <= 5! X. U) q- _+ Z9 [
and% m) O9 a- O, V. [1 i3 H( C
                       x1>=0; x2>=0; x3>=0  X5 e+ Y4 d2 R- o5 x6 Z

5 z3 s! Z  o1 G" @% M; d; D当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
& ]7 X+ l7 C% b6 G% p1 Q7 u$ q& X& q3 H: e. x$ p
用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）
0 D! R  c& G3 H% }  q8 y$ G* S
作者: jerrybond6    时间: 2011-3-17 16:41
本帖最后由 jerrybond6 于 2011-3-17 16:45 编辑
4 j5 Z' N* H- l* e# Z* L/ ?1 g3 ]) b  k' T) M! W7 `! v2 A+ `1 V- W3 H
根据 s.t.可知 :
% C7 F& ^7 Y- h0<=x1<=5;
/ r0 T1 t2 h2 G# q0<=x2<=2;
0 n" g; C) }: C. p4 L# q# R# x0<=x3<=3;* h3 n7 d" h2 |$ [  U3 v
: D8 N! I" [1 j2 d0 i9 \$ W
动态规划过程如下：: D' z7 @, S/ j2 `

& c. h; P. e. w5 J- v1 q+ fint dp[6][3][4], maxn, tmp, ans;! i2 i+ I% `% y' f
5 ]$ ?- }& ^8 W) Z& |
memset(dp,0,sizoef(dp));
7 M6 x) }/ f  \- r) d3 F( l7 z9 d* {' {- d5 `0 Q  O
for (i=0;i<=5;i++)" l# O4 l  ~: z' U* L
    for (j=0;j<=2;j++)1 z- C7 }1 y+ |0 X
        for (k=0;k<=3;k++)
  j5 ^7 a- [: U7 L& w        {2 @6 k' u& U% n3 s4 r! o
            maxn=0;- i1 K, w1 H' h( @
            if (i>0)
9 O! x9 z) |- l5 ?            {
& p' r5 P6 w( i  X) {                tmp=dp[i-1][j][k]+3;
- Q$ \. J$ h* i. ]8 U" }                if (tmp>maxn). C  H2 B( d/ e2 ]
                    maxn=tmp;
$ G9 ~+ P" |2 G/ f& ]            }: H/ \; S6 K2 w  Y
            if (j>0)- H; k! s* K6 i2 f, R/ N8 k
            {# K$ [) o! ]( s" p% E
                tmp=dp[j-1][k]+7;4 W( \1 J. ~2 b% V9 k$ ]
                if (tmp>maxn)7 M/ G: r& b8 E$ q
                    maxn=tmp;$ D2 o% u, C2 B8 G1 s
            }
6 }) ~) M/ n; Q1 L) F. ]: N            if (k>0)
6 D$ u* I  m1 \2 ?0 e* _: U            {. }* n/ T. G! B3 R" g, J- q
                tmp=dp[j][k-1]+6;+ R- C+ m! b  Q6 ^7 Q
                if (tmp>maxn). A4 W, E$ z6 W, I  R/ X, E
                    maxn=tmp;! b$ O) x2 k" f  g9 z8 U
            }& v9 t* z% g( U( [/ L
            dp[j][k]=maxn;
4 `6 x( V. I" {* k: W        }
% O3 E8 B% E0 X3 J2 K% a% M+ l$ g; z& V+ e
ans=0;  _% g9 s% P+ x$ [5 N1 R2 ~1 N' n
for (i=0;i<=5;i++)
2 N6 o6 [* B  G7 \- z2 t* L    for (j=0;j<=2;j++)& V" j2 o; j  `  ?( f
        for (k=0;k<=3;k++)
; e. W& q# M7 q0 Q        {2 G5 f4 U7 f4 g( {  N1 L/ y! y
            if (i+3*j+2*k>6)
. ]' a% F: G/ l8 Y# D                continue;
9 a* }6 r. q0 n1 m9 O& ]$ ^" l            if (i+j>5)& \$ x7 o' I, V6 C& E. ?! s
                continue;, Q/ X% E7 b4 G, U* @
            tmp=dp[j][k];7 g7 n: Y' U; o: S. A; f
            if (k>0)
5 _0 Q. r) b2 n( a- p                tmp-=6;# L2 F0 A9 ^; \, z' w* T8 g; ^
            if (tmp>ans)
% R7 L8 b( J  |2 ?. M                ans=tmp;
; q/ q2 A8 y) ^$ \# ^9 z8 U  W: }        }: ~  x8 a5 l* _8 X, y5 y
printf("%d\n", ans);8 ?$ S7 {- c5 L' B) T* m- Z
ans极为目标函数的最大值。  B, [) x. I& A$ ?1 A9 Q
作者: jerrybond6    时间: 2011-3-17 16:46
本帖最后由 jerrybond6 于 2011-3-17 16:50 编辑
5 v+ E5 |1 N; x# N
+ P3 _, N. N" L7 H9 N网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了
作者: gaoshanliu水    时间: 2011-3-17 22:19




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5