应用运筹学补充练习题参考答案

1、应用运筹学补充练习题参考答案1、某商店要制定明年第一季度某种商品的进货和销售计划，已知该店的仓库容量最多可储存 该种商品500件，而今年年底有200件存货。该店在每月月初进货一次。已知各个月份进 货和销售该种商品的单价如下表所示：月份1月2月3月进货单彳（元/件）869销售单价（元/件）9810现在要确定每个月进货和销售多少件，才能使总利润最大，把这个问题表达成一个线性规划模型。解：设Xi是第i个月的进货件数，Yi是第ij月的销货件数（i=1, 2, 3），Z是总利润, 于是这个问题可表达为：目标函数：Max Z=9Y 1+8Y2+10Y 3- 8X1 - 5X2- 9X3约束条件：200+X

2、 i w 500200+X1-Yi+X2<500L月初库存约束200+X 1-Y1 + X2-Y2+X3< 500-200+X 1-Y1 > 0200+X1-Y1+X 2-Y2> 0 月末库存约束200+X1 Y1+X 2 Y2+X3-Y 3 > 0JX1，X2，X3，丫1，丫2，Y3>0EXCEL 求解最优解结果： X1*= 300 ， X2*=500 ， X3*=0, Y1*=500,Y 2*=0 , Y3*=500, Z*=41002、一种产品包含三个部件，它们是由四个车间生产的，每个车间的生产小时总数是有限的， 下表中给出三个部件的生产率，目标是要确

3、定每个车间应该把多少工时数分配到各个部件 上，才能使完成的产品件数最多。把这个问题表示成一个线性规划问题车间生产能力（小时）生产举（件数/小时）部件1部件2部件3甲10010155乙15015105丙8020510丁200101520解：设Xj是车间i在制造部件j上所花的小时数，Y是完成产品的件数。最终的目的是Y要满足条件：min10X 11+15X21+20X31+10X41, 15X12+10X22+5X32+15X42, 5X13+5X23+10X33+20X43可将以上非线性条件转化为以下线性规划模型：目标函数：Max Z = Y约束条彳牛：Y w 10X11+15X 21+20X31

4、+10X 4115X12+10X 22+5X32 + 15X42Y W 5X13+ 5X 23 + 10X 33+20X 43X11+X12+X13W 100X21+X 22+X23<150X31+X 32+X33<80X41+X 42+X43W200Xij>0 (i=1, 2, 3, 4； j=1 , 2, 3), Y>0EXCEL 求解最优解结果： X 11*=X 12*=， X13*= ，X 21*= ，X 22*= ， X 23*=X 31*=， X32*=X 33*= ，Y* =3、一个投资者打算把它的100000元进行投资，有两种投资方案可供选择。第一种投资

5、保证每1元投资一年后可赚7角钱。第二种投资保证每1元投资两年后可赚2元。但对第二种投资，投资的时间必须是两年的倍数才行。假设每年年初都可投资。为了使投资者在第三年年底赚到的钱最多，他应该怎样投资？把这个问题表示成一个线性规划问题。解：设Xi1和Xi2是第一种方案和第二种方案在第i年年初的投资额（i =1,2, 3），Z是总利润，于是这个问题的线性规划模型是：目标函数： Max Z= 2X 22+0.7X 31（第三年年末的收益为当年第一方案和第二年第二方案的收益）约束条件：X11+X12<100 000（第一年年初总投资额不超过计划投资额）X21+X 22< 1.7X11（第二年年

6、初投资额不超过第一年第一方案投资收回的本利值）X 31W 3X 12+1.7X21 （第三年年初投资额不超过第二年年底收回的本利值） X" Xi2>0（i=1，2，3）EXCEL 求解最优解结果： X 11*=， X 12*=， X21*= ，X 22*= ，X 31*= ，Z*=4、 有 A， B 两种产品，都需要经过前后两道化学反应过程。每一个单位的A 产品需要前道过程2小时和后道过程3小时。每一个单位的B产品需要前道过程3小时和后道过程4小时。可供利用的前道过程有16 小时，后道过程时间有24 小时。每生产一个单位B 产品的同时，会产生两个单位的副产品C,且不需要外加任何

7、费用。副产品 C最多可售出5个单位，其余的只能加以销毁，每个单位的销毁费用是2元。出售A产品每单位可获利4元，B产品每单位可获利10元，而出售副产品C每单位可获利3元。试建立为了使 获得的总利润达到最大的线性规划模型。解：设X1, X2分别是产品A,产品B的产量，X3是副产品C的销售量，X4是副产品C 的销毁量， Z 是总利润，于是这个问题的线性规划模型是：目标函数： Max Z=4X 1+10X 2+3X 3 2X4约束条件： 2X2= X3+X 4X3<52X1+3X3W 163X1+4X2< 24X1, X2, X3, X4>0EXCEL 求解最优解结果：X1*=， X

8、2*=， X3*= ，Z*=5、考虑下面的线性规划问题：目标函数： Max Z=30X 1+20X2约束条件：2X1+X2W40X1+X225X1，X20用图解法找出最优解X1和X2。解:6、某厂生产甲，乙两种产品，每种产品都要在 A,B两道工序上加工。其中B工序可由B1 或B2设备完成，但乙产品不能用B1加工。生产这两种产品都需要 C,D,E三种原材料, 有关数据如下所示。又据市场预测，甲产品每天销售不超过30件。问应如何安排生产才能获利最大？试建立线性规划模型。产品单耗日供应量单位成本甲乙数量单位数量单位工序A2180工时6元/工时B13-60工时2元/工时B21470工时5元/工时原材料

9、C312300米2元/米D53100件1元/件E41.5150千克4元/千克其他费用（元/件）2629单价（元/件）80100解：设甲、乙两种产品分别生产X 1, X2件，其中，甲广品在 bi设备上加工x3工时、在B2设备上加工X4工时，则获利为：Z=80X 1 + 100X2-6(2X 1+X2)-2X3-5*(X 4+4X2)-2*(3X 1+12X2)-1*(5X 1+3X2)-4*(4X 1+1.5X2)-26X1-29X2化简后得到：目标函数:s.t.Max Z=15X 1+12X22X3 5X4 2X1+X2<80X3<604X2+X4W703X1 + 12X2300

10、5X1+3X21004X1 + 1.5X2< 150X1<30X1=X-+X4 （B1每工时完成 t件甲产品，共X3个工时，B2完成X4件） 33Xj>0,j=1,2,3,4EXCEL 求解最优解结果： Xi*=，X2*=, X3*= ,X4*=,Z*=7、制造某机床需要A、B、C三种轴，其规格和需要量如下表所示。各种轴都用长5.5米长的圆钢来截毛坯。如果制造100台机床，问最少要用多少根圆钢？试建立线性规划模型。轴类规格：长度（米）每台机床所需件数A3. 11B2. 12C1. 24解：用5.5米圆钢截所需规格长度的所有各种可能性如下表所示:轴件 所截各种轴件数量剩余料头（

11、m）所需圆钢 的量A (3.1 )B (2.1 )C (1.2 )11100.3X121020X230210.1X340121.0X450040.7X5设按第j种截法截Xj根圆钢，则相应的线性规划模型为：目标函数：Min Z = 5 X jj is.t: X1+X2>100Xi+2X3+ X4>2002X2+X 3+2X4+4X5400K>0且为整数（j=1,2.,5）EXCEL 求解最优解结果： X1*= 0，X2*=100 ，X3*= 100 ,X4*= 0 , X5*= 25 , Z*= 2258、某木材公司经营的木材贮存在仓库中，最大贮存量为20万米3,由于木材价格随

12、季节变化，该公司于每季初购进木材，一部分当季出售，一部分贮存以后出售。贮存费为a+bu,其中a=7元/米3, b=10元/米3, u为贮存的季度数。由于木材久贮易损，因此当年所有库存应于秋末售完。各季木材单价及销量如下表所示。为获全年最大利润，该公司各季应分别购销多少木材？试建立线性规划模型。季节购进价（元/米3售出价（元/米3最大销售量（万米3）冬31032110春32533314夏34835220秋34034416解：设Yi 6=1,2,3,4）分别为冬，春，夏，秋四季采购的木材量（单位：m3）,Xj （" j=1'2, 3, 4）代表第i季节采购用于第j季节销售的木材量

13、（m3）,因此，冬季以310元/ m3购入Y1,当季以321元/ m3卖出X11,同时，以7+10*1的成本存储 到春季出售的有 X12，以7+10*2的成本存储到夏季出售的有 X13,以7+10*3的成本存 储到秋季出售的有 X14;同样地，春季购入 。相应的线性规划模型为:目标函数：MaxZ= ( 321X11+316X12+325X13+307X14310Y1)+(333X22+335X23+317X24 325丫2) + ( 352X33+327X34 348丫3) +(344X44 340Y4)s.t: Y 1<200 000丫1- X11 X12X13 X14=0X11W 1

14、00 000X12+X13+X14+Y2< 200 000Y2X22X23X24=0X12+X22 w 140 000X 13+X 14+X23+X 24+Y 3< 200 000Y 3 X 33 X 34 = 0X 13+X23+X33 <200 000X 14+X24+X34+Y4W 200 000Y4X44=0X 14+X24+X34+X44 & 160 000x产 0，yi-0(i,j=1,2,3,4)EXCEL求解最优解结果：X11*=，X12*二，X13*=X22*二，X23*=，X24*=X33*=，X34*二，丫3*二X44*二，Y4*=,Z*=，X1

15、4*=Y1*=，丫2*二,9、对以下线性规划问题：Min Z = 2X1+3X2+5X3+2X4+3X5s.t. X1+X2+2X3+X4+3X5>44 2X1-X2+3X3+X4+X5>3X X1, X2,X3,X4X5 >0已知其对偶问题的最优解为 Y1*=4/5, Y2*=3/5, W* =5。试求出原问题的解。X6 ,X7解：设原问题的两个剩余变量分别为: 原问题的对偶问题为：Max W 4Y1+3Y2s.t.Y Y1+2Y2 <2Y1-Y2 <3松弛变量松弛变量丫3丫42Y1+3Y2 <5松弛变量丫5Y1+Y2 <2松弛变量丫63Y1+ 丫2

16、 <3松弛变量丫70、丫1,Y2,Y3,Y4 > 因为 丫1*=4/5,丫2*=3/5,因此，计算对偶问题松弛变量值为：Y3*=0, 丫4*=14/3, 丫5*=8/5 , 丫6*=3/5 , 丫7*=0根据对偶性质（互补松弛定理）则有：X2*=0, X3*=0, M*=0, X6*=0, X7*=0进一步有：2Xi+3X5=5Xi+3X5=42Xi+X5=3得到：Xi*=1,X5*=1原问题的解为：Xi*=1, X2*=0, X3* =0, X4*=0, X5*=1,Z * = 510、某厂拟生产甲、乙、丙三种产品，都需要在 A、B两种设备上加工，有关数据如下表。产品设单耗（台时

17、/件）设备有效台时（每月）甲乙丙A121400B212500产值（千兀/每件）321利用对偶性质分析以下问题：1）如何充分发挥设备潜力，使产品的总产值最大？2）该厂如果以每台时350元的租金租外厂的A设备，是否合算？解：设生产甲、乙、丙三种产品分别为X1,X2,X3件，线性规划模型为:目标函数：MaxZ = 3X1+2X2+M松弛变量为X4松弛变量为X约束条彳:X1+2X2+X3 w 400'2X1+X2+2X3W 500X1,X2,X3>0此原问题的对偶问题为:目标函数：Min W= 400Y1+500Y2约束条件:广丫1+2丫2 >32Y1+ Y2>2Y1+2Y2

18、>1剩余变量为Y3剩余变量为Y4剩余变量为Y5丫1,丫2 >0对偶问题可通过图解法求解，得到最优解结果为:Y1* = 1/3，Y2* = 4/3进一步可知： Y3*=0, Y4*=0, Y5* = 2根据互补松弛定理可知：X3*=0,X4*=0, X5*=0可得到：Xi+2X2=4002X1+X2=500可解得：X1*=200, X2*=100根据以上计算结果可知：1）应该生产甲产品200件，乙产品100件，丙产品不生产，此时总产值最大为800千元。2）因为Y3*=1/3 ,设备A的影子价格为1/3千元，小于租金350元，因此，该厂 不应该租用外厂的 A设备。11、某打井队要从10

19、个可供选择的井位中确定5个进行探油，使总的探油费用最小。若 10 个井位的代号为S1,S2,S3,S10,相应的探油费用为C1,C2,C3,C10,并且井位 选择要满足下列限制条件：1）或选择S1和S7,或选择S8;2）选择了 S3或S4,就不能选S5,或反过来也一样；3）在S5,S6,S7,S8中最多只能选两个。试建立线性规划模型。解：变量Xi取0或1，。表示不选、1表示选第i井位；模型如下：10目标函数： MinZ Ci Xii 110s.tXi 51 1X1 X81 （S1和S8只能选一个）X7 X 81 （S7和S8只能选一个）（以上两式同时满足时表明：S1 S7与S8必须且只能选一）

20、X3 X51 （S3和S5不能同时选中，也可都不选）X4 X51 （S4和S5不能同时选中，也可都不选）X5 X6 X 7 X 82Xi=0,1 i=1,2,10EXCEL 求解最优解结果：X1*=，X2*=,X3*=,X4*=,X5*=,X6*=，X7*= ，X8*= , Z*=12、某厂可生产四种产品，对于三种主要资源的单位消耗及单位利润见下表：品资源、1234可供量钢110305000人力26413000能源20253000单位利润1784如果产品3的生产需要用一特殊机器，这机器的固定成本（启用成本）为 3000,产品2 和产品4的生产也同样需要共用一特定的机器加工，其固定成本（启用成本

21、）为 1000, 写出此时求利润最大的线性规划模型。解：1）变量：Xi为第i种产品的产量（i=1,2,3,4 ）Y3为0-1变量，丫3X30X301 X2 X40Y24为 0-1 变量，Y24 J0 X2 X402）目标函数：MaxZ = X1+7X2+8X3+4X4-3000Y3-1000Y243）约束条件:资源约束：X1 + 10X2+3X3 w 50002X1+6X2+4X3+X4W 30002X1+2X3+5X43000启用约束：X3< MY3 （Mi为一足够大的正数，比如取 5000 ）X2+X4W MY24 （M2为一足够大的正数，比如取 5000 ）非负约束：Xi>0

22、 （i=1,2,3,4）; 丫3,丫24=0, 1EXCEL 求解最优解结果：Xi*= 0，X2*=400，X3*= 0 , X4*= 600 , 丫3=0,丫24=1,Z*=420013、某化工厂要用三种原料 D,P,H混合配置三种不同规格的产品 A,B,C。各产品的规格、单 价如左表所示，各原料的单价及每天的最大供应量如右表所示，该厂应如何安排生产才 能使利润最大？产 品规格单价（元/千克）A原料D不少于50%原料P不超过25%50B原料D不少于25%原料P不超过50%35C不限25原料最大供应单，（千克/天）（元/千克）D10065P10025H6035X21 ,X22,X23X31 ,

23、X32,X33X11,X12,X13解：1）变量：产品A中D,P,H含量分别为 产品B中D,P,H含量分别为 产品C中D,P,H含量分别为 令：X11+X12+X13=X1X21+X?2+X?3=X?X31+X52+X53=XS2）目标函数：MaxZ = -15X11+25X12+15X13- 30X21+10X22-40X31-10X333）约束条件：根据规格条件有：Xn> 0.5X1X12W 0.25X 1X21> 0.25X2X22W 0.5X2进一步得到：-X11+ X12+X13WO-X11+3X12- X13<0-3X21+ X22+X23W 0-X21+ X22

24、- X23W 0原材料供应条件：X11+X21+X31 & 100X12+X22+X32W100X13+X23+X33W 60Xj >0,i,j=1,2,3非负约束：EXCEL 求解最优解结果：Xii*= 100 ，Xi2*=50 , Xi3*= 50 , X21*=0,X22*=0X23*=0X31*=0，X32*=0，X 33*=0 ,Z*=500Xi*=X 11*+X 12*+X 13*=200,X2*=0,X3*=0;每天只生产 A 200kgXii*+X2i*+X 31*=100 使用 D 100kg;Xi2*+X 22*+X 32*=50 使用 P 50kg;X13*

25、+X 23*+X 33*=50 使用 H 50kg;14、某产品有Ai和A2两种型号，需经过Bi、B2 B3三道工序，单位工时、利润、各工序每周工时限制如下表所示，问工厂如何安排生产，才能使总利润最大（B3工序有两种加工方式B31和B32,只能选择其中一种；产品为整数）。、工时/型号B1B2B3利润（元/件）B31B32A1323225A2715440每周工时（小时/周）2501001501201）设变量如下：A1生厂里为 Xi，A2生厂里为 X2；选B31时Yi=0；不选时丫 1=1选B32时丫2=0；不选时丫2=12）目标函数：Max Z = 25X1+40X23）约束条件： 3Xi+7X

26、2<2502Xi+ X2W100J 3Xi+5X2<150+M*Y1（M为足够大的正数，如取5000）2Xi+4X2<120+M*Y>丫1+丫2=1Ix1,X2-0 且为整数，丫 1,丫2=0,1EXCEL 求解最优解结果： Xi*= ，X2*= , Yi*=，丫2*=0 , Z*=15、甲、乙、丙、丁四人加工 A、B、C、D四种工件所需时间（分钟）如表所示，应指派何 人加工何种工件，能使总的加工时间最少？要求建立数学模型并求解。件ABCD甲149415乙117910丙132105丁1791513解：（匈牙利方法过程及模型略）答案：甲：C;乙：A;丙：D; 丁： B 1

27、6、某厂生产柴油机，14月份订货任务为：1月2000台；2月3000台；3月5500台；4月6000台；该厂的月正常生产能力为3000台，每台的生产成本为1500元，每月加班生 产能力为2000台，加班生产成本为每台2000元，月库存费用为每台50元，1月初库存 为0。建立求成本最低生产计划的线性规划模型。解：设X （i=1,2,3,4 ）为第i个月正常生产的柴油机数，Y为第i个月加班生产的数量，W为第i月月初的库存数。该问题的线性规划模型为：目标函数：Min Z= 1500（X1+&+X3+X4）+2000（Y 1+Y2+Y3+Y4）+50（也+W+W4）约束条件：X1+Y1-W2

28、= 2000X2+Y2+W2-W3 = 3000X3+Y3+W3-W4=5500X4+Y4+W=6000X < 3000(i=1,2,3,4 )Y <2000(i=1,2,3,4 )X,Yi,W >0,(i=1,2,3,4 ),且均为侬EXCEL 求解最优解结果：X1*=, X2*= , X3*= ,X4*=，丫1*=，丫2*=Y3*=, Y4*=, W1*=,W2*=, W3*=,W4*=Z*=17、某铸造厂接到一笔订货，要生产1000公斤（一吨）铸件，其成分是镒的含量至少达到 0.45% ,硅达到3.25% 5.50%。铸件的售价是4.5元/公斤。工厂现存三种可以利用的生

29、 铁（A、B、C）,存量很多，其性质如下表所示。此外，生产过程允许把纯镒直接加到融 化金属中。各种可能的炉料费用如下：生铁 A 210元/吨，生铁B250元/吨，生铁 C 150元/吨，Z镒80元/公斤。每融化一吨生铁要花费50元。应如何选择炉料才能使 利润最大。兀素生铁种类ABC硅4%1%0.6%镒0.45 %0.5%0.4%解：1)变量：设所需生铁A X1吨，生铁B X2吨，生铁CX3吨，纯镒 X4公斤 2)目标函数：MaxZ = 1000*4.5-210*X 1-250*X 2-150*X 3-80*X 4-50* (X1+X2+X3)即：Max Z = 450-260X1-300X2-

30、200X3-80X43)约束条件：广(0.45%X 什0.5%X 2+0.4%X 3)*1000+X4 > 0.45%*1000(镒的含量)J 4%X1+1%X 2+0.6%X3 5.5% 4%X 1+1%X 2+0.6%X33.25% JX1+X2+X3)*1000+X 4=1000X1,X2,X3,X4>0EXCEL求解最优解结果：X1*=（硅的含量上限）（硅的含量上限），X2*=，X3*=, X4*=, Z*=18、已知有三个产地给四个销地供应某产品，产销地之间的供需量和单位运价如下:销地产B1B2B3B4A15267300A23546200A34523400销量200100

31、400200900要求：1）建立此运输问题的线性规划模型（不需要求解）；2）由于市场情况的变化，B3和B4的销量各增加了 50单位（运用表上作业法可 求得此时最小运费为2950元）。有关部门在研究调运方案时还需要依次考虑以 下情况（已规定其优先等级 P1- P5）:P1: B4是重点保证单位，必须尽可能满足其需要；P2: A3向B1提供的量不少于100;P3:因道路问题，尽量避免安排 A2产品运往B4;P4:给B1和B3的需求供应率要相等；P5:与最小运费调运方案相比，总运费的增加不超过最小调运方案的10%。试建立求解满意调运方案的目标规划模型。解：1）运输问题线性规划模型：bj此问题为供需平

32、衡问题，用 Cj表示Ai运到Bj的单位运价，ai为Ai的最大产量, 为Bj的最大销量（i=1,2,3 ; j=1,2,3,4）,则线性规划模型：变量：设 Xj表示Ai运到Bj的运量（i=1,2,3 ; j=1,2,3,4）34目标函数：Min Z = C j ?Xji 1 j 13Xij b j 1,2,3,4-14约束条件：X Xij a i 1,2,3j 1、Xj 0, i 1,2,3j 12342）目标规划求解：销量增加后供不应求，因此，供应仍为绝对约束：4Xjai i 1,2,3j 1需求约束为目标约束：3Xijd.d.bj j 1,2,3 ,4 （已包含了 B4要尽可能满足的条件）i

33、 1X31+d5-d5+=100（A3向B1提供的量不少于 100）X24+d6-d6+=0（尽量避免安排 A2 产品运往 B4）X 11 + X21 + X31200X 13 + X23 + X33450d7 d 70 （给B1和B3的需求供应率要相等）34C ij ?X + d8- d8+= 2950(1+10%)(总运费的增加不超过最小的10%) i 1 j 1非负约束：xj， dk- ， dk+.0(i=1,2,3； j=1,2,3,4； k=1,2,3, 8)目标函数：Min Z = P1* d4- + P2* d5-+P3* d6+P4*( d7-+ d7+)+P5* d8+19、

34、某电台根据政策每天允许播出12小时，其中商业节目每分钟可收入 250元，新闻节目每分 钟支出40元，音乐节目每播一分钟支出17.5元。依政策规定：正常情况下商业节目只能 占广播时间的20%而每小时至少安排5分钟的新闻节目。试问该电台每天如何安排节目？ 其优先级如下：Pi一满足政策的要求；P2每天的纯收入最大。建立此问题的目标规划 模型。解：设安排商业节目时间 Xi小时，新闻节目时间X2小时，音乐节目时间 为小时。目标函数：Min Z = P1(d 1-+d2-+d3+)+P2d4-约束条件：X1+X2+X3+ d1- d1+ =12Xi + d2- d2+ =2.4X2 + d3- - d3+

35、 =1250X1-40X2-17.5X 3+ d4- d4+ =250*2.4X1,X2,X3>0,d i- ,d i+ >0 (i=1,2,3,4)20、AJ 共10项工作需在两台机器上加工，各自的加工时间如下，如何安排加工顺序使系 统效率最高(只要求写出加工顺序)。ABCDEFGHIJ机器1 :14192422640204125机器221083235183063528解：(约翰逊原则求解过程略)结果：I, H, E, G, D, J, F, B, C, A21、求出下图中从A到E的最短路线及其长度。4,而C3至ij D1的距离为0;3,而C4到D3的距离为0;解：方法一：动态规

36、划在B1与D1之间增设一虚拟节点 C3,使B1到C3的距离为在B3与D3之间增设一虚拟节点 C4,使B3到C4的距离为用动态规划方法，可求得A到E的最短距离为 8最短路为：A-B2-C1-D1-E。方法二：Dijkstra 方法（过程略）结果：A到E的最短距离为 8 ,最短路为：A-B2-C1-D1-E22题图23题图解：线性规划模型:i 一节点j ）的流量 （出发点流出的总流量最大 （节点2的净流量为0） （节点3的净流量为0） （节点4的净流量为0） （节点5的净流量为0） （节点6的净流量为0）1）变量：设fj为通过弧i-j （节点2）目标函数：MaxZ = fi2+fi33）约束条件：

37、9f12=f25+f24+f23fl3+f23=f34+f36f24+f34=f45+f46J f25+f45+f65=f57fijWRj对一切可能的弧i-j （弧的容量限制）f46+f36=f65+f67< fij > 0对一切可能的弧i-j图上标注过程略，最大流量结果为：923、求网络（23题图）从节点1到节点7的最短路径（写出线性规划模型，并用图上标注的方法求解）。解：方法一：线性规划模型求解，假设通过网络的最大流量为1,）变量：设Xij为弧i-j （节点i 一节点j ）是否流过，流过取值，不流过取值02）目标函数：通过网络的总长度最小，因此，有：Min Z = 5X12 +

38、2X 23+ 7X 25+ 2X 24+ 7X 34 +4X 36+6X 45+ 2X 46+ 3X 57+X65+X673）约束条件：X X12+X 13=1（节点1的流出量为1）X12=X 25+X 24（节点2的净流量为0）X13=X 34+X 36（节点 3的净流量为 0）J X24+X34=X 45+X46（节点4的净流量为0）| X25+X 45+X 65=X57（节点5的净流量为0）X36+X46=X 65+X67（节点6的净流量为0）X57+X 67=1（节点7的流入量为1），Xij=0,1所有可能的弧i-j方法二：Dijkstra 方法（过程略）结果：最短距离为10,最短路为

39、：1-3-6-5-724、某工厂的某台机器可连续工作 4年，决策者在每年年初都要决定机器是否更新。若购置新机器，就要支付购置费；若继续使用，则需要支付维修与运行费用，而且随着机器使 用年限的增加费用也会逐年增加。已知计划期（4年）中每年的购置价格及维修运行费 用如下表所示，试制定今后4年的机器更新计划，使总支付费用最小。年限1234购置费（力兀）2.52.62.83.1维修运行费（力兀）11.524解：把该问题看作最短路问题。设节点 1和节点5表示计划期的始点和终点（节点 5可 理解为第4年年末）。下图中各弧（i , j）表示第i年年初购进的机器使用到第 j年 年初（即第j-1年年底），弧旁的

40、数字（弧长）为购置价格与使用多年后的维修与 运行总费用，如考虑节点 1到节点3的弧，这条弧对应的是在第 1年初购进的机器， 使用到第3年年初（使用了两年），所以从节点1到节点3的弧长为购置2.5万元 加上第一年维修运行费 1万和第二年维修运行费 1.5万元，合计5万元。其余类似 求得。求解结果：最短距离为10.3,最短路为：-，即:计划期内第1年、第3年年初各购置一台新机器，4年总费用10.3万元。25、某地拟进行石油勘探。统计资料表明，在相似地理区域钻探的井中，有 7 口油井和16 口 干井，每口油井收入都是大约130万元。若请勘探人员自行开发需花费 30万元，如出租 给别的公司开采可稳得租

41、金10万元，且若能出油还可额外再得10万元。该地领导应如 何决策？为提高决策的准确性，专家建议可先进行地震试验，从而判断该地区的地质结 构是封闭的或开放的。从地质学知道：有油地区多半是封闭结构，无油地区多半是开放 结构，以往情况是有油地区勘测为封闭结构的概率为0.8,无油地区勘探开放结构的概率是0.6。若做地震t验要花费5万元，该领导又该如何决策？解：在相似地区钻井有油的概率为7/（7+16）=0.3 ,则无油的概率为 0.7。设以A1表示自行开发，A2表示出租，以。T 。纷别表示该地区的有油与无油状 态。1）先验分析：计算 A1、A2两方案的期望收益值EMV(A1)= 100*0.3+(-3

42、0)*0.7=9EMV(A2)= 20*0.3+10*0.7=13由于EMV(A2)>EMV(A1),因此，如不做地震实验的决策是应该选择出租。此时，EMV*=13 (万元)2)预验分析：计算完备信息的价值完备信息下最大期望收益ERPI= 100*0.3+10*0.7= 37 (万元)完备信息价值EVPI=37-13=24 (万元)由于EVPI (24万元)相比地震实验的费用(5万元)大比较多，可尝试进行。 3)后验分析：计算条件概率并决策设A3为进行地震实验，以 S1, S2分别表示勘探结果为封闭结构和开放结构由题意可得以下条件概率：P(S1| 0 1)=0.8 , P(S2| 0 1

43、)=0.2 , P(S1| 0 2)=0.4 , P(S2| 0 2)=0.6进一步利用贝叶斯公式计算决策所需条件概率P(0 I S )(1)(3)=(1)*(2)0 iP(0)P(S1| 0 i)P(S2| 0 i)P(S1 0 i)P(S2 0 i)010.30.80.20.240.06(4) _0 20.7 ；0.40.40.280.42(6)=(4)+(5)0.520.48P(Si) 1(7)=(4)/(6)0.460.125P(0|Si)(8)=(5)/(6)0.540.875得至U： P( 0 S1)=0.46, P( 0 1S1)=0.54, P( 0 |S2)=0.125, P

44、( 0 1S2)=0.875地震实验是封闭结构的决策：计算期望收益值EMV(A1S1)=100*0.46+(-30)*0.54=30( 万元)EMV(A2S1)=20*0.46+10*0.54=14.6( 万元)EMV(A1S1)>EMV(A2S1)因此，此时的决策为选择自行开采(A1)地震实验是开放结构的决策：计算期望收益值EMV(A1S2)=100*0.125+(-30)*0.875=-13.75( 万元)EMV(A2s2)=20*0.125+10*0.875=11.25(万元)EMV(A2s2)>EMV(A1S2)因此，此时的决策为选择出租(A2)以上根据地震实验结果所做决策

45、的总期望收益为：EMV(S)=30*0.52+11.25*0.48- 5= 16(万元)选择做地震实验的期望值增量为：? EMV=EMV(S)-EMV*= 16-13 = 3 (万元)综上所述，最优决策为：先进行地震实验，如果结果为封闭结构则自行钻探开采，如为开放结构则出租该地的开采权，这样可获期望收益16万元。26、画出网络图(不考虑工序时间)网络图1网络图2网络图3工序紧后工序工序紧前工序工序紧前工序AC,DA-A-BC,D,EB-B-CGC-CADH,FDADAEH,FEBEBFGFCFBGIGB,DGD,EHIHEHD,EIG,HID,E,FJE,FJCKE,FKCLI,JLJMD,E,F,G,H,K解：网络图1:网络图2:网络图3:27、已知某项工程的作业程序、作业时间、直接成本、最大可缩短时间、各工序缩短一天工 期所增加的直接费用等信息如下表所示，正常时间完成各工序的直接费用总和为1300元,每天的间接费用为25元：工序紧后工序工序时间（天）最大可缩短 工作天数直接费率g （元/天）AB、C6230BD E、F9440CE、F3130DG10215EH8510FI2150G-10H-4120I-5230要求：1）画出网络图，计算每一节点的最早、最迟时间，确定关键线路;2）建立使该项工程达到最低成本时间的线性规划模型；3）计算使总成本最低的最