资源描述：
《运筹学例题解析.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、(一)线性规划建模与求解B.样题：活力公司准备在5小时内生产甲、乙两种产品。甲、乙两种产品每生产1单位分别消耗2小时、1小时。又根据市场需求信息，乙产品的产量应该至少是甲产品产量的3倍。已知甲、乙两种产品每销售1单位的利润分别为3百元和1百元。请问：在5小时内，甲、乙两种产品各生产多少单位，才能够使得总销售利润最大？要求：1、建立该问题的线性规划模型。2、用图解法求出最优解和最大销售利润值，并写出解的判断依据。如果不存在最优解，也请说明理由。解：1、(1)设定决策变量：设甲、乙两种产品分别生产x1、x2单位。(2)目标函数：m
2、axz=2x1+x2(3)约束条件如下：求解过程如下：1.各个约束条件的边界及其方向如图1中直线和箭头所示，其中阴影部分为可行域，由直线相交可得其顶点A(5,0)、B(1,3)和O(0,0)。2.画出目标函数的一条等值线CD：2x1+x2=0，它沿法线向上平移，目标函数值z越来越大。3.当目标函数平移到线段AB时时，z→Maxz。2、该问题中约束条件、目标函数、可行域和顶点见图1所示，其中可行域用阴影部分标记，不等式约束条件及变量约束要标出成立的方向，目标函数只须画出其中一条等值线，顶点用大写英文字母标记。2x1+x2≤5O5
3、4321-1x2-2-1012345x1图1A(5,0)B(1,3)CDMaxx2≥3x1结论：本题解的情形是：无穷多最优解，理由：目标函数等值线z=2x1+x2与约束条件2x1+x2≤5的边界平行。甲、乙两种产品的最优产量分别为(5,0)或(1,3)单位；最大销售利润值等于5百元。（二）图论问题的建模与求解样题A.正考样题（最短路问题的建模与求解，清华运筹学教材编写组第三版267-268页例13）某企业使用一台设备，每年年初，企业都要做出决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。但是变卖旧设备可以获得
4、残值收入，连续使用1年、2年、3年、4年以上卖掉的设备残值分别为8万元、6万元、3万元和0万元。试制定一个5年的更新计划，使总支出最少。已知设备在各年的购买费与维修费如表2所示。要求：（1）建立某种图论模型；（2）求出最少总支出金额。表2解：（1）建立图论——最短路问题模型。①设点Vi表示第i年年初，虚设一个点V6，表示第五年年底；②弧(Vi,Vj)表示第i年初购进一台设备一直使用到第j年初(即第i-1年年底)再卖掉并获得残值收入；171741282741v6v527v4v2v31616988v110959图2③弧(Vi,Vj
5、)上的权数表示第i年初购进一台设备，一直使用到第j年初所需支付的购买、维修及抵扣残值收入以后的全部费用（单位：万元）。例如：弧(V1,V4)上的费用权数30=11+(5+6+8)-3=27(万元)。模型如图2所示：（2）用Dijkstra法求解从V1到V6的最短路。给起点V1标号（0,v1）；1.I={v1};J={v2,v3,v4,v5,v6}弧集合{[v1,v2]、[v1,v3]、[v1,v4]、[v1,v5]、[v1,v6]}s12=l1+b12=0+8=8;s13=l1+b13=0+16=16;s14=l1+b14=0
6、+27=27;s15=l1+b15=0+41=41;s16=l1+b16=0+59=59∵min{s12,s13,s14,s15,s16}=min{8,16,27,41,59}=8=s12=l2∴给v2标号（8,v1）2.I={v1,v2}J={v3,v4,v5,v6}弧集合{[v1,v3]、[v1,v4]、[v1,v5]、[v1,v6]、[v2,v3]、[v2,v4]、[v2,v5]、[v2,v6]}s23=l2+b23=8+8=16;s24=l2+b24=8+16=24;s25=l2+b25=8+27=35;s26=l2+
7、b26=8+41=49∵min{s13,s14,s15,s16,s23,s24,s25,s26}=min{16,27,41,59,16,24,35,49}=16=s13或s23=l3，∴任选一个s13，选择给v3标号（16,v1）。3.I={v1,v2,v3}J={v4,v5,v6}弧集合{[v1,v4]、[v1,v5]、[v1,v6]、[v2,v4]、[v2,v5]、[v2,v6]、[v3,v4]、[v3,v5]、[v3,v6]}s34=l3+b34=16+9=25;s35=l3+b35=16+27=35;s26=l2+b2
8、6=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=l4∴给v4标号（24,v2）4.I={v1,v2,v3,v4}J={v5,v6}弧集合{[v1
