(完整版)应用运筹学补充练习题参考答案.pdf

应用运筹学补充练习题参考答案1、某商店要制定明年第一季度某种商品的进货和销售计划，已知该店的仓库容量最多可储存该种商品 500 件，而今年年底有200 件存货。该店在每月月初进货一次。已知各个月份进货和销售该种商品的单价如下表所示：月份1 月2 月3 月进货单价（元 /件）8 6 9 销售单价（元 /件）9 8 10 现在要确定每个月进货和销售多少件，才能使总利润最大，把这个问题表达成一个线性规划模型。解：设 Xi是第 i 个月的进货件数，Yi是第 i 个月的销货件数（i=1, 2, 3 ） ，Z 是总利润，于是这个问题可表达为：目标函数：Max Z=9Y1+8Y2+10Y38X15X29X3约束条件：200+X1500 200+X1Y1+X2500 月初库存约束200+X1Y1X2Y2X3500 200+X1-Y1 0 200+X1-Y1+X2-Y2 0 月末库存约束200+X1- Y1+X2- Y2+X3-Y3 0 X1，X2，X3，Y1，Y2，Y30 EXCEL求解最优解结果：X1*= 300 ，X2*=500 ，X3*=0 ，Y1*=500,Y2*=0 ， Y3*=500, Z*=4100 2、一种产品包含三个部件，它们是由四个车间生产的，每个车间的生产小时总数是有限的，下表中给出三个部件的生产率，目标是要确定每个车间应该把多少工时数分配到各个部件上，才能使完成的产品件数最多。把这个问题表示成一个线性规划问题车间生产能力（小时）生产率（件数/小时）部件部件部件甲100 10 15 5 乙150 15 10 5 丙80 20 5 10 丁200 10 15 20 解：设 Xij是车间 i 在制造部件j 上所花的小时数，Y 是完成产品的件数。最终的目的是Y 要满足条件：min10X11+15X21+20X31+10X41，15X12+10X22+5X32+15X42，5X13+5X23+10X33+20X43 可将以上非线性条件转化为以下线性规划模型：目标函数：Max Z = Y 约束条件：Y10X11+15X21+20X31+10X41 Y15X12+10X22+5X32+15X42Y5X13+5X23+10X33+20X43X11+X12+X13100 X21+X22+X23150 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 18 页 - - - - - - - - - - X31+X32+X3380 X41+X42+X43200 Xij0（i=1， 2，3，4；j=1，2，3）, Y0 EXCEL 求解最优解结果：X11*=，X12*=，X13*=，X21*=，X22*= ，X23*= X31*=，X32*=，X33*=，Y* = 3、一个投资者打算把它的100000 元进行投资，有两种投资方案可供选择。第一种投资保证每元投资一年后可赚角钱。第二种投资保证每元投资两年后可赚元。但对第二种投资，投资的时间必须是两年的倍数才行。假设每年年初都可投资。为了使投资者在第三年年底赚到的钱最多，他应该怎样投资？把这个问题表示成一个线性规划问题。解：设 Xi1和 Xi2是第一种方案和第二种方案在第i 年年初的投资额（i =1, 2, 3 ） ，Z 是总利润，于是这个问题的线性规划模型是：目标函数： Max Z= 2X22+0.7X31 （第三年年末的收益为当年第一方案和第二年第二方案的收益）约束条件：X11+X12100 000 (第一年年初总投资额不超过计划投资额)X21+X221.7X11（第二年年初投资额不超过第一年第一方案投资收回的本利值）X31 3X12+1.7X21 （第三年年初投资额不超过第二年年底收回的本利值）Xi1，Xi20（i=1，2，3）EXCEL 求解最优解结果：X11*=，X12*=，X21*=，X22*=，X31*= ，Z*= 4、有 A ，B 两种产品，都需要经过前后两道化学反应过程。每一个单位的A 产品需要前道过程小时和后道过程小时。每一个单位的B 产品需要前道过程小时和后道过程小时。可供利用的前道过程有16 小时，后道过程时间有24 小时。每生产一个单位B 产品的同时，会产生两个单位的副产品C，且不需要外加任何费用。副产品C 最多可售出个单位，其余的只能加以销毁，每个单位的销毁费用是元。出售 A 产品每单位可获利元， B 产品每单位可获利10 元，而出售副产品C 每单位可获利3 元。试建立为了使获得的总利润达到最大的线性规划模型。解：设 X1，X2分别是产品A，产品 B 的产量， X3是副产品C 的销售量， X4是副产品C 的销毁量， Z 是总利润，于是这个问题的线性规划模型是：目标函数： Max Z=4X1+10X2+3X32X4约束条件：2X2= X3+X4X35 2X1+3X316 3X1+4X224 X1，X2，X3，X40 EXCEL 求解最优解结果：X1*=，X2*=，X3*=，Z*= 5、考虑下面的线性规划问题：目标函数： Max Z=30X1+20X2约束条件：2X1+ X240 X1+X225 X1， X20 用图解法找出最优解X1和 X2。解：图解法结果如下，最优解：X1*=15; X2=10; Z*=650 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 18 页 - - - - - - - - - - 6、某厂生产甲，乙两种产品，每种产品都要在A,B 两道工序上加工。其中B 工序可由B1 或B2 设备完成，但乙产品不能用B1 加工。生产这两种产品都需要C,D,E 三种原材料，有关数据如下所示。又据市场预测，甲产品每天销售不超过30 件。问应如何安排生产才能获利最大？试建立线性规划模型。产品单耗日供应量单位成本甲乙数量单位数量单位工序A 2 1 80 工时6 元 /工时B1 3 - 60 工时2 元 /工时B2 1 4 70 工时5 元 /工时原材料C 3 12 300 米2 元/米D 5 3 100 件1 元/件E 4 1.5 150 千克4 元 /千克其他费用（元 /件）26 29 单价（元 /件）80 100 解：设甲、乙两种产品分别生产X1，X2件，其中，甲产品在B1 设备上加工X3工时、在B2 设备上加工X4工时，则获利为：Z=80X1+100X2-6(2X1+X2)-2X3-5*(X4+4X2)-2*(3X1+12X2)-1*(5X1+3X2)- 4*(4X1+1.5X2)-26X1-29X2 化简后得到：目标函数： Max Z=15X1+12X22X35X4s.t. 2X1+X280 X360 4X2+X470 3X1+12X2300 5X1+3X2100 4X1+1.5X2150 X130 X1=3X3+X4( B1 每工时完成31件甲产品，共X3个工时， B2 完成 X4件)Xj0, j=1,2,3,4 X120 30 10 40 可行域X1+ X2=25 60 5 5 10 20 30 40 0 60 X22X1+X2=40 最优解： X1*=15; X2=10; Z*=650 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 18 页 - - - - - - - - - - EXCEL 求解最优解结果：X1*=，X2*=，X3*= ，X4*= , Z*= 7、制造某机床需要A、B、C 三种轴，其规格和需要量如下表所示。各种轴都用长5.5 米长的圆钢来截毛坯。如果制造100 台机床，问最少要用多少根圆钢？试建立线性规划模型。轴类规格：长度（米）每台机床所需件数A B C 31 21 12 1 2 4 解：用 5.5 米圆钢截所需规格长度的所有各种可能性如下表所示：轴件（ j）所截各种轴件数量剩余料头（m）所需圆钢的量A（3.1） B（2.1） C（1.2）1 1 1 0 0.3 X12 1 0 2 0 X23 0 2 1 0.1 X34 0 1 2 1.0 X45 0 0 4 0.7 X5设按第 j 种截法截 Xj根圆钢，则相应的线性规划模型为：目标函数：Min Z =51jX js.t: X1+X2 100 X1+ 2X3+ X4 200 2X2+ X3+2X4+4X5400 xj0 且为整数（ j=1,2.,5）EXCEL 求解最优解结果：X1*= 0 ，X2*=100 ， X3*= 100 , X4*= 0 , X5*= 25 , Z*= 225 8、某木材公司经营的木材贮存在仓库中，最大贮存量为20 万米3，由于木材价格随季节变化，该公司于每季初购进木材，一部分当季出售，一部分贮存以后出售。贮存费为a+bu，其中a=7 元/米3，b=10 元/米3，u 为贮存的季度数。由于木材久贮易损，因此当年所有库存应于秋末售完。各季木材单价及销量如下表所示。为获全年最大利润，该公司各季应分别购销多少木材？试建立线性规划模型。季节购进价（元 /米3）售出价（元 /米3）最大销售量 （万米3）冬310 321 10 春325 333 14 夏348 352 20 秋340 344 16 解：设 Yi（i=1,2,3,4 ）分别为冬，春，夏，秋四季采购的木材量（单位：m3） ，Xij（i，j=1，2，3，4）代表第 i 季节采购用于第j 季节销售的木材量（m3） ，因此，冬季以 310 元/ m3购入 Y1, 当季以 321 元/ m3卖出 X11,同时，以7+10*1 的成本存储到春季出售的有X12,以 7+10*2 的成本存储到夏季出售的有X13, 以 7+10*3 的成本存储到秋季出售的有X14；同样地，春季购入.。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 18 页 - - - - - - - - - - 相应的线性规划模型为：目标函数： MaxZ= （321X11+316X12+325X13+307X14310Y1）+（333X22+335X23+317X24 325Y2）（ 352X33+327X34348Y3）+（344X44340Y4）s.t: Y1200 000 Y1X11X12X13X14=0 X11 100 000 X12+X13+X14+Y2200 000 Y2X22X23X24 =0 X12+X22140 000 X13+X14+X23+X24+Y3200 000 Y3X33X340 X13+X23+X33 200 000 X14+X24+X34+Y4200 000 Y4X44 =0 X14+X24+X34+X44 160 000 xij0，yi0（ i,j=1,2,3,4 ）EXCEL 求解最优解结果：X11*=，X12*=，X13*= ，X14*= Y1*= , X22*=，X23*=，X24*= ，Y2*= , X33*=，X34*=，Y3*= , X44*=，Y4*= , Z*= 9、对以下线性规划问题：Min Z 2X1+3X2+5X3+2X4+3X5s. t. X1+X2+2X3+X4+3X5 42X1 - X2+3X3+X4+X5 3X1, X2, X3, X4,X5 0已知其对偶问题的最优解为Y1*=4/5, Y2*=3/5, W* = 5 。试求出原问题的解。解：设原问题的两个剩余变量分别为：X6 ,X7 原问题的对偶问题为：Max W 4Y1+3Y2 s.t. Y1+2Y22松弛变量 Y3 Y1-Y23 松弛变量 Y4 2Y1+3Y25松弛变量 Y5 Y1+Y22松弛变量 Y6 3Y1+ Y23松弛变量 Y7 Y1,Y2,Y3,Y4 0因为 Y1*=4/5, Y2*=3/5,因此，计算对偶问题松弛变量值为：Y3*=0，Y4*=14/3 ， Y5*=8/5 ，Y6*=3/5 ，Y7*=0 根据对偶性质 ( 互补松弛定理 ) 则有： X2*=0，X3*=0，X4*=0，X6*=0，X7*=0 进一步有： 2X1+3X5=5 X1+3X5=4 2X1+X5=3 得到： X1*=1,X5*=1 原问题的解为：X1*=1, X2*=0，X3*=0，X4*=0，X5*=1,Z* = 5精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 18 页 - - - - - - - - - - 10、某厂拟生产甲、乙、丙三种产品，都需要在A、 B两种设备上加工，有关数据如下表。产品设备单耗（台时 / 件）设备有效台时（每月）甲乙丙A 1 2 1 400 B 2 1 2 500 产值（千元 / 每件）3 2 1 利用对偶性质分析以下问题：1）如何充分发挥设备潜力，使产品的总产值最大？2）该厂如果以每台时350 元的租金租外厂的A设备，是否合算？解：设生产甲、乙、丙三种产品分别为X1,X2,X3件，线性规划模型为：目标函数 : Max Z = 3X1+2X2+X3约束条件： X1+2X2+X3400 松弛变量为X4 2X1+X2+2X3500 松弛变量为X5 X1,X2,X30 此原问题的对偶问题为：目标函数 : Min W = 400Y1+500Y2约束条件： Y1+2Y23 剩余变量为Y3 2Y1+ Y22 剩余变量为Y4 Y1+2Y21 剩余变量为Y5Y1,Y20 对偶问题可通过图解法求解，得到最优解结果为：Y1* = 1/3 ，Y2* = 4/3 进一步可知： Y3* =0，Y4* = 0，Y5* = 2 根据互补松弛定理可知：X3*=0,X4*=0， X5*=0可得到： X1+2X2=400 2X1+X2=500 可解得： X1*=200 ，X2*=100 根据以上计算结果可知：1) 应该生产甲产品200 件，乙产品 100 件，丙产品不生产，此时总产值最大为800千元。2) 因为 Y3*=1/3 ，设备 A 的影子价格为1/3 千元，小于租金350 元，因此，该厂不应该租用外厂的A 设备。11、某打井队要从10 个可供选择的井位中确定5 个进行探油，使总的探油费用最小。若10个井位的代号为S1,S2,S3, ,S10 ，相应的探油费用为C1,C2,C3, ,C10，并且井位选择要满足下列限制条件：1） 或选择 S1和 S7，或选择S8；2） 选择了 S3或 S4，就不能选S5，或反过来也一样；精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 18 页 - - - - - - - - - - 3） 在 S5,S6,S7,S8 中最多只能选两个。试建立线性规划模型。解：变量 Xi取 0 或 1，0 表示不选、 1 表示选第 i 井位；模型如下：目标函数：101iXiCiMinZ254(153(1871S8(S71S8(S115.876554538781101XXXXSSXXSSXXSSSXXXXXitsi不选）不能同时选中，也可都和不选）不能同时选中，也可都和必须且只能选一）与表明：（以上两式同时满足时只能选一个）和只能选一个）和Xi=0,1 i=1,2, 10EXCEL 求解最优解结果：X1*= ，X2*= ，X3*= , X4*= , X5*= , X6*= ，X7*= ，X8*= , Z*= 12、某厂可生产四种产品，对于三种主要资源的单位消耗及单位利润见下表：产品资源1 2 3 4 可供量钢1 10 3 0 5000 人力2 6 4 1 3000 能源2 0 2 5 3000 单位利润1 7 8 4 如果产品3 的生产需要用一特殊机器，这机器的固定成本（启用成本）为3000，产品2和产品 4 的生产也同样需要共用一特定的机器加工，其固定成本（启用成本）为1000，写出此时求利润最大的线性规划模型。解： 1)变量： Xi 为第 i 种产品的产量（i=1,2,3,4）, Y3为 0-1 变量，0030133XYX Y24为 0-1 变量，0024014242XXYXX2)目标函数： Max Z = X1+7X2+8X3+4X4-3000Y3-1000Y243)约束条件：资源约束： X1+10X2+3X35000 2X1+6X2+4X3+X43000 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 18 页 - - - - - - - - - - 2X1+2X3+5X43000 启用约束： X3 M1Y3 (M1为一足够大的正数，比如取5000 ) X2+X4 M2Y24 (M2为一足够大的正数，比如取5000 ) 非负约束： Xi 0 (i=1,2,3,4)；Y3,Y24=0，1 EXCEL 求解最优解结果： X1*= 0，X2*=400 ，X3*= 0 , X4*= 600 , Y3=0,Y24=1, Z*=420013、某化工厂要用三种原料D,P,H 混合配置三种不同规格的产品A,B,C。各产品的规格、单价如左表所示，各原料的单价及每天的最大供应量如右表所示，该厂应如何安排生产才能使利润最大？产品规格单价（元 / 千克）原料最大供应（千克 / 天）单价（元 / 千克）A 原料 D不少于 50原料 P不超过 2550 D 100 65 B 原料 D不少于 25原料 P不超过 5035 P 100 25 C 不限25 H 60 35 解： 1)变量：产品A中D,P,H含量分别为 X11,X12,X13产品B中D,P,H含量分别为 X21,X22,X23产品C中D,P,H含量分别为 X31,X32,X33令： X11+X12+X13=X1 X21+X22+X23=X2 X31+X32+X33=X3 2)目标函数： Max Z = -15X11+25X12+15X13- 30X21+10X22-40X31-10X33 3)约束条件：根据规格条件有：X110.5X1 X120.25X1 X210.25X2 X220.5X2进一步得到： - X11+ X12+X130 - X11+3X12- X130 -3X21+ X22+X230 - X21+ X22- X230 原材料供应条件： X11+X21+X31100 X12+X22+X32100 X13+X23+X3360 非负约束： Xij0, i,j=1,2,3 EXCEL 求解最优解结果：X11*= 100 ，X12*=50 ，X13*= 50 , X21*=0 , X22*=0 , X23*=0 X31*=0 ，X32*=0 ，X33*=0 , Z*=500 X1*=X11*+X12*+X13*=200,X2*=0,X3*=0;每天只生产A 200kg X11*+X21*+X31*=100 使用 D 100kg; X12*+X22*+X32*=50 使用 P 50kg; X13*+X23*+X33*=50 使用 H 50kg; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 18 页 - - - - - - - - - - 14、某产品有 A1和 A2两种型号，需经过B1、B2、B3三道工序，单位工时、利润、各工序每周工时限制如下表所示，问工厂如何安排生产，才能使总利润最大（B3工序有两种加工方式B31和B32，只能选择其中一种；产品为整数）。解： 1）设变量如下：A1 生产量为 X1，A2 生产量为 X2；选 B31 时 Y1=0；不选时 Y1=1 选 B32 时 Y2=0；不选时 Y2=1 2）目标函数：Max Z = 25X1+40X23）约束条件：3X1+7X2250 2X1+ X2100 3X1+5X2150+M*Y1 (M为足够大的正数, 如取 5000) 2X1+4X2120+M*Y2 Y1+Y2=1 X1,X20 且为整数 ,Y1,Y2=0,1 EXCEL 求解最优解结果：X1*= ，X2*= ，Y1 *= , Y2 *=0 , Z*= 15、甲、乙、丙、丁四人加工A、 B、C、D 四种工件所需时间（分钟）如表所示，应指派何人加工何种工件，能使总的加工时间最少？要求建立数学模型并求解。工件人A B C D 甲乙丙丁14 9 4 15 11 7 9 10 13 2 10 5 179 15 13 解： （匈牙利方法过程及模型略）答案：甲： C；乙： A；丙： D；丁： B 16、某厂生产柴油机，14 月份订货任务为：1 月 2000 台； 2 月 3000 台； 3 月 5500 台； 4月 6000 台；该厂的月正常生产能力为3000 台，每台的生产成本为1500 元，每月加班生产能力为 2000 台，加班生产成本为每台2000 元，月库存费用为每台50 元， 1 月初库存为 0。建立求成本最低生产计划的线性规划模型。解：设 Xi（i=1,2,3,4）为第 i 个月正常生产的柴油机数，Yi为第 i 个月加班生产的数量，Wi为第 i 月月初的库存数。该问题的线性规划模型为：目标函数： Min Z = 1500(X1+X2+X3+X4)+2000(Y1+Y2+Y3+Y4)+50(W2+W3+W4) 约束条件： X1+Y1-W2 = 2000 工序工时 / 件型号B1 B2 B3 利润( 元/ 件) B31 B32 A1 A2 3 7 2 1 3 5 2 4 25 40 每周工时（小时/ 周）250 100 150 120 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 18 页 - - - - - - - - - - X2+Y2+W2-W3 = 3000 X3+Y3+W3-W4=5500 X4+Y4+W4=6000 Xi3000 （i=1,2,3,4） Yi2000 （i=1,2,3,4） Xi,Yi,Wi0, （i=1,2,3,4） ，且均为整数EXCEL 求解最优解结果：X1*= ，X2*= ， X3*= , X4*= , Y1*= , Y2*= Y3*= ，Y4*= ，W1*= , W2*= , W3*= , W4*= , Z*= 17、 某铸造厂接到一笔订货，要生产 1000公斤 （一吨）铸件，其成分是锰的含量至少达到0.45，硅达到 3.255.50% 。铸件的售价是4.5 元/公斤。工厂现存三种可以利用的生铁（A、B、C） ，存量很多，其性质如下表所示。此外，生产过程允许把纯锰直接加到融化金属中。各种可能的炉料费用如下：生铁A210 元/吨，生铁B250 元/吨，生铁C150 元/吨，纯锰 80 元/公斤。每融化一吨生铁要花费50 元。应如何选择炉料才能使利润最大。解： 1)变量：设所需生铁A X1吨，生铁 B X2吨，生铁C X3吨，纯锰 X4公斤 2）目标函数： Max Z = 1000*4.5-210*X1-250*X2-150*X3-80*X4-50* （ X1+X2+X3）即： Max Z = 450-260X1-300X2-200X3-80X43）约束条件：(0.45%X1+0.5%X2+0.4%X3)*1000+X4 0.45%*1000 (锰的含量 ) 4%X1+1%X2+0.6%X35.5% (硅的含量上限) 4%X1+1%X2+0.6%X33.25% (硅的含量上限) (X1+X2+X3)*1000+X4=1000 X1,X2,X3,X40 EXCEL 求解最优解结果：X1*= ，X2*= ，X3*= , X4*= , Z*= 18、已知有三个产地给四个销地供应某产品，产销地之间的供需量和单位运价如下：销地产地B1 B2 B3 B4 产量A1 A2 A3 5 3 4 2 5 5 6 4 2 7 6 3 300 200 400 销量200 100 400 200 900 要求： 1）建立此运输问题的线性规划模型（不需要求解）；2）由于市场情况的变化，B3 和 B4 的销量各增加了50单位（运用表上作业法可求得此时最小运费为2950元） 。 有关部门在研究调运方案时还需要依次考虑以下情况（已规定其优先等级P1P5） ：P1: B4是重点保证单位，必须尽可能满足其需要；P2: A3向B1提供的量不少于100；P3: 因道路问题，尽量避免安排A2产品运往 B4; 元素生铁种类A B C 硅锰40.45 1% 0.5% 0.6% 0.4%精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 18 页 - - - - - - - - - - P4: 给B1和B3的需求供应率要相等；P5: 与最小运费调运方案相比，总运费的增加不超过最小调运方案的10% 。试建立求解满意调运方案的目标规划模型。解： 1)运输问题线性规划模型：此问题为供需平衡问题，用Cij表示 Ai运到 Bj的单位运价，ai为Ai 的最大产量，bj为Bj的最大销量（ i=1,2,3 ; j=1,2,3,4 ） ，则线性规划模型：变量：设Xij表示 Ai运到 Bj的运量（ i=1,2,3 ; j=1,2,3,4 ）目标函数： Min Z = ?3141ijijijXC约束条件：1234;3 , 2, 13, 2, 14, 3, 2 , 1, 04131jiXiaXjbXijjiijijij2）目标规划求解：销量增加后供不应求，因此，供应仍为绝对约束：3,2,141iaXjiij需求约束为目标约束：4,3,2, 131jbddXijjjij(已包含了 B4要尽可能满足的条件) X31+d5- - d5+=100 (A3向B1提供的量不少于100) X24+ d6- - d6+=0 （尽量避免安排A2产品运往 B4）0450X+X+X200X+X+X77332313312111dd(给B1和B3的需求供应率要相等)?3141ijijijXC+ d8- - d8+= 2950(1+10%) （总运费的增加不超过最小的10%）非负约束： Xij， 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、某电台根据 政策 每天允许播出 12小时，其中商业节目每分钟可收入250元，新闻节目每分钟支出 40元，音乐节目每播一分钟支出17.5 元。依 政策 规定：正常情况下商业节目只能占广播时间的 20% ，而每小时至少安排5分钟的新闻节目。 试问该电台每天如何安排节目？其优先级如下：P1满足 政策 的要求； P2每天的纯收入最大。建立此问题的目标规划模型。解：设安排商业节目时间X1小时，新闻节目时间X2小时，音乐节目时间X3小时。目标函数： Min Z = P1(d1-+d2-+d3+)+P2d4-约束条件： X1+X2+X3+ d1- d1+ =12 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 11 页，共 18 页 - - - - - - - - - - X1 + d2- d2+ =2.4 X2 + d3- d3+ =1 250X1-40X2-17.5X3+ d4- d4+ =250*2.4 X1,X2,X30,di-,di+0 (i=1,2,3,4) 20、AJ 共 10 项工作需在两台机器上加工，各自的加工时间如下，如何安排加工顺序使系统效率最高 ( 只要求写出加工顺序) 。A B C D E F G H I J 机器 1 14 19 24 22 6 40 20 4 1 25 机器 2 2 10 8 32 35 18 30 6 35 28 解： （约翰逊原则求解过程略）结果：I, H, E, G, D, J, F, B, C, A 21、求出下图中从A 到 E 的最短路线及其长度。解：方法一：动态规划在B1与D1之间增设一虚拟节点C3,使B1到 C3 的距离为 4，而 C3 到D1的距离为 0；在B3与D3之间增设一虚拟节点C4,使B3到 C4 的距离为 3，而 C4 到D3的距离为 0；用动态规划方法，可求得 A 到 E 的最短距离为 8 最短路为： A-B2-C1-D1-E 。方法二： Dijkstra 方法（过程略）结果： A 到 E 的最短距离为 8 ,最短路为： A-B2-C1-D1-E 22、求下图（ 22 题图）所示网络的最大流（写出线性规划模型，并用图上标注的方法求解）。22 题图23 题图4 6 7 1 3 1 2 2 2 5 4 5 2 3 4 5 6 7 1 Fij7 5 2 2 6 7 2 1 3 6 4 2 3 4 5 6 7 1 LijA B1 B2 B3 C1 C2 D1 D2 D3 E 2 1 3 4 4 3 1 3 3 5 3 2 4 1 3 5 2 3 1 5 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 12 页，共 18 页 - - - - - - - - - - 解：线性规划模型：1）变量：设fij为通过弧i-j （节点 i 节点 j ）的流量2）目标函数： Max Z = f12+f13(出发点流出的总流量最大) 3）约束条件： f12=f25+f24+f23(节点 2 的净流量为0) f13+f23=f34+f36(节点 3 的净流量为0) f24+f34=f45+f46(节点 4 的净流量为0) f25+f45+f65=f57(节点 5 的净流量为0) f46+f36=f65+f67(节点 6 的净流量为0) fijFij 对一切可能的弧i-j (弧的容量限制) fij0 对一切可能的弧i-j 图上标注过程略，最大流量结果为：9 23、求网络（ 23 题图）从节点1 到节点 7 的最短路径（写出线性规划模型，并用图上标注的方法求解） 。解：方法一：线性规划模型求解，假设通过网络的最大流量为1，1） 变量：设 Xij为弧 i-j （节点 i 节点 j ）是否流过，流过取值1，不流过取值0 2） 目标函数：通过网络的总长度最小，因此，有：Min Z = 5X12+2X23+7X25+2X24+7X34+4X36+6X45+2X46+3X57+X65+X673） 约束条件：X12+X13=1 (节点 1 的流出量为1) X12=X25+X24(节点 2 的净流量为0) X13=X34+X36(节点 3 的净流量为0) X24+X34=X45+X46(节点 4 的净流量为0) X25+X45+X65=X57(节点 5 的净流量为0) X36+X46=X65+X67(节点 6 的净流量为0) X57+X67=1 (节点 7 的流入量为1) Xij=0,1 所有可能的弧i-j 方法二： Dijkstra 方法（过程略）结果：最短距离为10，最短路为： 1-3-6-5-724、某工厂的某台机器可连续工作4 年，决策者在每年年初都要决定机器是否更新。若购置新机器，就要支付购置费；若继续使用，则需要支付维修与运行费用，而且随着机器使用年限的增加费用也会逐年增加。已知计划期（4年）中每年的购置价格及维修运行费用如下表所示，试制定今后4 年的机器更新计划，使总支付费用最小。年限1 2 3 4 购置费（万元）2.5 2.6 2.8 3.1 维修运行费（万元）1 1.5 2 4 解：把该问题看作最短路问题。设节点1 和节点 5 表示计划期的始点和终点（节点5 可理解为第4 年年末）。下图中各弧（ i , j）表示第 i 年年初购进的机器使用到第j 年年初（即第 j-1 年年底），弧旁的数字（弧长）为购置价格与使用多年后的维修与运行总费用，如考虑节点1 到节点 3 的弧，这条弧对应的是在第1 年初购进的机器，使用到第 3 年年初（使用了两年） ，所以从节点1 到节点 3 的弧长为购置2.5 万元加上第一年维修运行费1 万和第二年维修运行费1.5 万元，合计5 万元。其余类似求得。求解结果：最短距离为10.3，最短路为：- - ，即：计划期内第1 年、第 3年年初各购置一台新机器，4 年总费用10.3 万元。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 13 页，共 18 页 - - - - - - - - - - 25、某地拟进行石油勘探。统计资料表明，在相似地理区域钻探的井中，有7 口油井和16 口干井，每口油井收入都是大约130 万元。若请勘探人员自行开发需花费30 万元，如出租给别的公司开采可稳得租金10 万元，且若能出油还可额外再得10 万元。该地领导应如何决策？为提高决策的准确性，专家建议可先进行地震试验，从而判断该地区的地质结构是封闭的或开放的。从地质学知道：有油地区多半是封闭结构，无油地区多半是开放结构，以往情况是有油地区勘测为封闭结构的概率为0.8，无油地区勘探开放结构的概率是 0.6。若做地震试验要花费5 万元，该领导又该如何决策？解：在相似地区钻井有油的概率为7/(7+16)=0.3 ，则无油的概率为0.7。设以 A1 表示自行开发， A2 表示出租， 以 1、 2 分别表示该地区的有油与无油状态。根据题意可列出以下收益表：状态盈利（万元）方案 1（有油）概率0.3 2（无油）概率0.7 A1 A2 100 20 30 10 1） 先验分析：计算A1、A2两方案的期望收益值EMV(A1)= 100*0.3+(-30)*0.7= 9 EMV(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| 1)=0.8 , P(S2|1)=0.2 , P(S1|2)=0.4 , P(S2|2)=0.6 进一步利用贝叶斯公式计算决策所需条件概率P(| S ) （1）（2）(3)=(1)*(2) i P() P(S1| i) P(S2| i) P(S1i) P(S2i) 1 0.3 0.8 0.2 0.24 0.06 (4) 2 0.7 0.4 0.4 0.28 0.42 (5) (6)=(4)+(5) 0.52 0.48 P(Si) (7)=(4)/(6) 0.46 0.125 P( i|Si) (8)=(5)/(6) 0.54 0.875 1 2 4 3 5 11 7 5.3 5 5.1 7.1 3.5 3.6 3.8 4.1 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 14 页，共 18 页 - - - - - - - - - - 得到： P( 1|S1)=0.46 , P( 2|S1)=0.54 , P( 1|S2)=0.125 , P( 2|S2)=0.875 地震实验是封