运筹学例题解析

《运筹学例题解析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、（一）线性规划建模与求解B.样题：活力公司准备在5小时闪生产甲、乙两种产品。甲、乙两种产品每生产1单位分别消耗2小时、1小时。又根据市场需求信息，乙产品的产量应该至少是甲产品产量的3倍。已知甲、乙两种产品每销售1单位的利润分别为3百元和1百元。请问：在5小时闪，甲、乙两种产品各生产多少单位，才能够使得总销售利润最大？要求：1、建立该问题的线性规划模型。2、用图解法求出最优解和最大销售利润值，并写出解的判断依据。如果不存在最优解，也请说明理由。解：1、（1）设定决策变量：设甲、乙两种产品分别生产七、乜单位。（2）0标函数:maxz=2X1+X2•2x,+x2<5x

2、2>xA,x2>02、该问题中约束条件、目标函数、可行域和顶点见图1所示，其中可行域用阴影部分标记，不等式约束条件及变量约束要标出成立的方向，目标函数只须画出其中一条等值线，顶点用大写英文字母标记。（3）约束条件如下:SJ.X2>3X

3、x7<5'A(5,0)求解过程如下：1.各个约束条件的边界及其方向如图1屮直线和箭头所示，其屮阴影部分为可行域，由直线相交可得其顶点A（5,0）、B（l，3）和0（0,0）o2.画出目标函数的一条等值线CD:2x,+x2=0,它沿法线向上平移，目标函数值z越来越大。3.当FI标函数平移到线段AB时时，z—MaxZ。-2-1/V2

4、34—5-1图1结论：本题解的情形是：无穷多最优解，理由：B标函数等值线2=2%1+&与约束条件的边界T•行。甲、乙两种产品的最优产量分别为（5,0）或（1，3）单位;最大销售利润值等于百元。（二）图论问题的建模与求解样题A.正考样题（最短路问题的建模与求解，清华运筹学教材编写组第三版267-268页例13）某企业使用一台没备，每年年初，企业都要做出决定，如果继续使用旧的，要付维修费;若购买一台新设备，要付购买费。但是变卖旧设备可以获得残值收入，连续使用1年、2年、3年、4年以上卖掉的设备残值分别为8万元、6万元、3万元和0万元。试制定一个5年的更新计划，使总支

5、出最少。已知设备在各年的购买赀与维修赀如表2所示。要求：（1）建立某种图论模型；（2）求出最少总支出金额。拓U

6、•:策2<

7、:3R3什:354年355年的买货11II1212U机器年於0〜11〜22〜33*-44〜5fttt货56RII18解：（1）建立图论一一最短路问题模型。①设点％表示第i年年初，虚设一个点V6,表示第五年年底；②弧（Vi，VJ表示第i年初购进一台设备-•直使用到第j年初（即第i-1年年底）再卖掉并获得残值收入；③弧（％，％）上的权数表示第i年初购进一台没备，一直使用到第j年初所需支付的购买、维修及抵扣残值收入以后的全部费用（单位：万元）。例

8、如：弧（VhV4）上的费用权数30=11+（5+6+8）-3=27（万元）。模型如图2所示：(2)用Dijkstra法求解从V丨到V6的最短路。给起点标号(Ow);l.l={vj;J={v2,v3,v4，v5，v6}弧集合{［vbv2］、［vbv3］、［vbv4］、［vbv5］、［vbv6］}Si2=/i+bi2=0+8=8;Si3=li+bi3=0+16=16;S

9、4=/

10、+bi4=0+27=27;s15=Zi+b15=0+41=41;s16=11+b16=0+59=59Vmin{si2,Si3,Si4,Si5,Si6}=min{8,16,27,41,59)=

11、8=s、2=h•••给％标号(8,Vi)2.1={vi,v2}J={v3，v4，v5，v6}弧集合{［vbv3］、［vhv4］、［vi,v5］>［vi,v6］>［v2，v3］、［v2，v4］、［v2，v5］、［v2，v6］}S23=/2+b23=8+8=16;S24=/2+b24=8+16=24;S25=/2+b25=8+27=35;S26=/2+b26=8+41=497min{sB,Si4,Si5,Si6,S23,S24,S25,S26}=min{16,27,41,59,16,24,35,49)=16=s13或s23=/3，•••任选一个s13，选择给v3标号

12、(16,Vi)o3.1={vbv2,v3}J={v4,v5,v6}弧集合Uvi，v4］、［Vbv5］、［vbv6］、［v2，v4］、［v2，v5］、［v2，v6］、［V3，V4］、［V3，v5］、［V3，V6］}S34=6+t>34=16+9=25；S35=/3+b35=l6+27=35；S26=/2+b26=8+41=49•••min{s14，s15，s16，S24，S25，S26，S34，S35，S36}=min{27,41，59,24,35,49,25,35,49}=24=s24=/4•••给v4标号(24,v2)4.I={vi,v2,v3,v4}J={v

13、5,v6}弧集合{［vb