数学建模社区-数学中国
标题:
有没有哪位高人会用动态规划来解线性规划的题? 附题一道
[打印本页]
作者:
zhaobener
时间:
2011-3-17 11:29
标题:
有没有哪位高人会用动态规划来解线性规划的题? 附题一道
Max Z=3 x1 + 7 x2 + 6 f(x3)subject to
+ g8 e8 M% y* `3 X
x1 + 3 x2 + 2 x3 <= 6
+ ` K; a) }' Y$ S$ ~! {# t
x1 + x2 <= 5
% w. c4 N# M7 O& s
and
. I+ X7 C% Z8 T( m8 ^
x1>=0; x2>=0; x3>=0
; v6 D* Y5 r( s3 u( e7 h- t( O
6 w3 x' @* O; ^' R& w7 h9 `
当 x3=0 时 f(x3)=0; 当x3>0时, f(x3)= -1 + x3
2 F& g" U+ @, [7 Z! B: o2 v
% u$ V" h! ^* d/ S
用动态规划来解 谢谢(lingo之类的我知道如何求解 主要想知道计算过程)
! w' @) k, R# q6 |9 k% i, l D
作者:
jerrybond6
时间:
2011-3-17 16:41
本帖最后由 jerrybond6 于 2011-3-17 16:45 编辑
* D. H* g& g4 `$ D0 z4 D9 D+ m& p
) l+ X1 \- O0 r# n
根据 s.t.可知 :
/ O4 z9 N/ \6 I8 X! H% q
0<=x1<=5;
9 e7 s9 [1 j7 C" k1 n0 S5 {
0<=x2<=2;
% n8 Q. z( K2 E; s& |$ p
0<=x3<=3;
+ t# W& H9 x' z& c8 f
# O- J% m% o ]2 {) n. U
动态规划过程如下:
2 O5 x: v0 g* v. I
; v8 N$ K" y2 P/ c6 g% V, K) D# z
int dp[6][3][4], maxn, tmp, ans;
7 G" |1 I1 W9 |0 e( Z
5 g. u/ T* K- c1 m; d+ Y, I
memset(dp,0,sizoef(dp));
+ u: i2 F$ e$ D$ l0 I. q' U
5 K+ l' g8 E+ m4 P1 J
for (i=0;i<=5;i++)
1 C. S& ~5 G) z, u0 @ T
for (j=0;j<=2;j++)
, g {+ C9 j$ T! |$ _, [ u
for (k=0;k<=3;k++)
$ A; w. ~3 c; L6 H+ b+ q
{
5 S& o9 g5 `& {. [* F: F
maxn=0;
/ N' P6 p5 u8 _8 D R
if (i>0)
. k. j0 R9 P& R; V+ a: N
{
) X! K& W* K' x7 o0 q' }; h
tmp=dp[i-1][j][k]+3;
2 U+ G; p, x6 k5 s% Y" ]: I
if (tmp>maxn)
) n1 c# | K5 D+ W9 E
maxn=tmp;
5 c; E; [3 D8 X' q3 ?5 X: z
}
: N1 H. G" }6 B# B2 M0 s
if (j>0)
$ h* M- \4 Y8 t+ R# r5 R
{
% Q# t$ u' ?2 P) h! O
tmp=dp
[j-1][k]+7;
: J5 g# L2 s0 p6 H: I
if (tmp>maxn)
8 D. C1 j8 ?$ y2 X) o5 @ Q
maxn=tmp;
6 }8 }* [& B6 o0 q9 v
}
) Z: L3 {$ z1 X
if (k>0)
& i' V* P" j; x: q V
{
9 f o( H7 {: c; ]- K8 n/ i
tmp=dp
[j][k-1]+6;
7 W4 @& o3 r, R3 j
if (tmp>maxn)
# L! |9 W( [+ n3 S5 A/ W
maxn=tmp;
9 Z, W1 S* J/ n& ^7 j
}
* K# U! O4 v. ]/ [+ b7 V0 O# A" O. V
dp
[j][k]=maxn;
/ v6 g' ?- p$ _1 q# A
}
k( \2 P, v* u# o$ Q* V( l
6 i5 n5 E: x8 w2 C1 t) T( O: i
ans=0;
) G% Q' N- j7 `/ p0 E3 l
for (i=0;i<=5;i++)
. ^3 A+ ` m- ?" F1 ?. g3 p9 X" P
for (j=0;j<=2;j++)
9 x4 f; {& j1 g2 a) Q% f4 R# T
for (k=0;k<=3;k++)
& i0 G ^8 T8 D7 W: e8 B1 A* p7 s
{
2 H& V& R- S* A- P9 S& o
if (i+3*j+2*k>6)
2 ~ C# j9 R9 i
continue;
/ |$ }, \8 Q1 t, w8 w" p- [ o
if (i+j>5)
3 ^# s. T: z! I
continue;
6 q* H) Q; F8 n. i, H4 ^
tmp=dp
[j][k];
9 `; q0 J. ^0 u
if (k>0)
! ]) h% N7 j$ u l8 B) `7 h- B, j
tmp-=6;
' |! E5 ^% i& V
if (tmp>ans)
+ D, M) W) w3 x0 C2 r6 l
ans=tmp;
" D1 A- g' W+ b7 x- u5 W: a
}
! Y3 o; f5 L# |4 L/ }( A
printf("%d\n", ans);
, J( w3 _! z: K$ Q2 f( C
ans极为目标函数的最大值。
+ E! x/ s+ g" ^. V: d/ }
作者:
jerrybond6
时间:
2011-3-17 16:46
本帖最后由 jerrybond6 于 2011-3-17 16:50 编辑
; L) n9 ~5 Q$ V2 ^* w
: w. w- k5 p* H
网页有点问题哈 数组有的地方显示的是2维 应该是3维 你自己琢磨琢磨哈 要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了
作者:
gaoshanliu水
时间:
2011-3-17 22:19
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5