论坛 › 运筹学 › 有没有哪位高人会用动态规划来解线性规划的题？ 附题一道

zhaobener 发表于 2011-3-17 11:29

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

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之类的我知道如何求解 主要想知道计算过程）

jerrybond6 发表于 2011-3-17 16:41

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

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

动态规划过程如下：

int dp, 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+3;
                if (tmp>maxn)
                    maxn=tmp;
            }
            if (j>0)
            {
                tmp=dp+7;
                if (tmp>maxn)
                    maxn=tmp;
            }
            if (k>0)
            {
                tmp=dp+6;
                if (tmp>maxn)
                    maxn=tmp;
            }
            dp=maxn;
        }

ans=0;
for (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
        {
            if (i+3*j+2*k>6)
                continue;
            if (i+j>5)
                continue;
            tmp=dp;
            if (k>0)
                tmp-=6;
            if (tmp>ans)
                ans=tmp;
        }
printf("%d\n", ans);
ans极为目标函数的最大值。

jerrybond6 发表于 2011-3-17 16:46

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

网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

gaoshanliu水 发表于 2011-3-17 22:19

{:3_41:}{:3_41:}{:3_41:}

查看完整版本: 有没有哪位高人会用动态规划来解线性规划的题？ 附题一道