《应用运筹学补充练习题参考答案.docx》由会员分享，可在线阅读，更多相关《应用运筹学补充练习题参考答案.docx（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、?应用运筹学?补充练习题参考答案1、某商店要制定明年第一季度某种商品的进货和销售方案，该店的仓库容量最多可储存该种商品500件，而今年年底有200件存货。该店在每月月初进货一次。各个月份进货和销售该种商品的单价如下表所示：月份1月2月3月进货单价元/件869销售单价元/件9810现在要确定每个月进货和销售多少件，才能使总利润最大，把这个问题表达成一个线性规划模型。解：设Xi是第i个月的进货件数，Yi是第i个月的销货件数i=1, 2, 3，Z是总利润，于是这个问题可表达为： 目标函数： Max Z=9Y1+8Y2+10Y38X15X29X3约束条件： 200+X1500200+X1Y1+X250
2、0 月初库存约束200+X1Y1X2Y2X3500 200+X1-Y1 0200+X1-Y1+X2-Y2 0 月末库存约束200+X1-Y1+X2-Y2+X3-Y3 0X1，X2，X3，Y1，Y2，Y30 EXCEL求解最优解结果：X1*= 300 ，X2*=500 ，X3*=0，Y1*=500,Y2*=0，Y3*=500, Z*=41002、一种产品包含三个部件，它们是由四个车间生产的，每个车间的生产小时总数是有限的，下表中给出三个部件的生产率，目标是要确定每个车间应该把多少工时数分配到各个部件上，才能使完成的产品件数最多。把这个问题表示成一个线性规划问题车间生产能力小时生产率件数/小时部件
3、部件部件甲10010155乙15015105丙8020510丁200101520 解：设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+15X42 Y5X13+5X23+10X33+20X43 X11+X12+X13100X21+X22+
4、X23150X31+X32+X3380X41+X42+X43200Xij0i=1，2，3，4；j=1，2，3, Y0 EXCEL求解最优解结果：X11*= ，X12*= ，X13*=， X21*=， X22*=， X23*= X31*= ，X32*= ，X33*=， Y* = 3、一个投资者打算把它的100000元进展投资，有两种投资方案可供选择。第一种投资保证每元投资一年后可赚角钱。第二种投资保证每元投资两年后可赚元。但对第二种投资，投资的时间必须是两年的倍数才行。假设每年年初都可投资。为了使投资者在第三年年底赚到的钱最多，他应该怎样投资？把这个问题表示成一个线性规划问题。 解：设Xi1和X
5、i2是第一种方案和第二种方案在第i年年初的投资额i =1, 2, 3，Z是总利润，于是这个问题的线性规划模型是：目标函数：Max Z= 2X22+0.7X31 第三年年末的收益为当年第一方案和第二年第二方案的收益约束条件：X11+X12100 000 (第一年年初总投资额不超过方案投资额)X21+X221.7X11 第二年年初投资额不超过第一年第一方案投资收回的本利值X313X12+1.7X21 第三年年初投资额不超过第二年年底收回的本利值Xi1，Xi20i=1，2，3 EXCEL求解最优解结果：X11*= ，X12*= ，X21*=， X22*=， X31*=， Z*=4、有A，B两种产品，
6、都需要经过前后两道化学反响过程。每一个单位的A产品需要前道过程小时和后道过程小时。每一个单位的B产品需要前道过程小时和后道过程小时。可供利用的前道过程有16小时，后道过程时间有24小时。每生产一个单位B产品的同时，会产生两个单位的副产品C，且不需要外加任何费用。副产品C最多可售出个单位，其余的只能加以销毁，每个单位的销毁费用是元。出售A产品每单位可获利元，B产品每单位可获利10元，而出售副产品C每单位可获利3元。试建立为了使获得的总利润到达最大的线性规划模型。 解：设X1，X2分别是产品A，产品B的产量，X3是副产品C的销售量，X4是副产品C的销毁量，Z是总利润，于是这个问题的线性规划模型是：
7、目标函数：Max Z=4X1+10X2+3X32X4约束条件： 2X2= X3+X4X352X1+3X3163X1+4X224X1，X2，X3，X40 EXCEL求解最优解结果：X1*= ，X2*= ，X3*=， Z*= 5、考虑下面的线性规划问题：目标函数：Max Z=30X1+20X2约束条件： 2X1+ X240X1+X225X1，X20用图解法找出最优解X1和X2。 解：图解法结果如下，最优解：X1*=15; X2=10; Z*=650X120301040可行域X1+ X2=25605510203040060X22X1+X2=40最优解：X1*=15; X2=10; Z*=6506、某
8、厂生产甲，乙两种产品，每种产品都要在A,B两道工序上加工。其中B工序可由B1或B2设备完成，但乙产品不能用B1加工。生产这两种产品都需要C,D,E三种原材料，有关数据如下所示。又据市场预测，甲产品每天销售不超过30件。问应如何安排生产才能获利最大？试建立线性规划模型。产品单耗日供给量单位本钱甲乙数量单位数量单位工序A2180工时6元/工时B13-60工时2元/工时B21470工时5元/工时原材料C312300米2元/米D53100件1元/件E41.5150千克4元/千克其他费用元/件2629单价元/件80100 解：设甲、乙两种产品分别生产X1，X2件，其中，甲产品在B1设备上加工X3工时、在
9、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=+X4 (B1每工时完成件甲产品，共X3个工时，B2完成X4件)Xj0, j=1,2,3,4 EXCEL求解最优解结果：X1*= ，X2*= ，X3*=， X4*= , Z*=7、
10、制造某机床需要A、B、C三种轴，其规格和需要量如下表所示。各种轴都用长5.5米长的圆钢来截毛坯。如果制造100台机床，问最少要用多少根圆钢？试建立线性规划模型。轴类规格：长度米每台机床所需件数ABC312112124解：用5.5米圆钢截所需规格长度的所有各种可能性如下表所示：轴件j所截各种轴件数量剩余料头m所需圆钢的量A3.1B2.1C1.211100.3X121020 X230210.1X340121.0X450040.7X5设按第j种截法截Xj根圆钢，那么相应的线性规划模型为：目标函数： Min Z =X js.t: X1+X2 100X1+ 2X3+ X4 2002X2+ X3+2X4+
11、4X5400xj0且为整数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冬31
12、032110春32533314夏34835220秋34034416 解：设Yii=1,2,3,4分别为冬，春，夏，秋四季采购的木材量单位：m3，Xiji，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；同样地，春季购入 .。相应的线性规划模型为：目标函数：MaxZ=321X11+316X12+325X13+307X14310Y1 +333X22+335X23+
13、317X24325Y2352X33+327X34348Y3 +344X44340Y4s.t: Y1200 000Y1X11X12X13X14=0X11100 000X12+X13+X14+Y2200 000Y2X22X23X24 =0X12+X22140 000X13+X14+X23+X24+Y3200 000Y3X33X340X13+X23+X33200 000X14+X24+X34+Y4200 000Y4X44=0X14+X24+X34+X44160 000xij0，yi0i,j=1,2,3,4 EXCEL求解最优解结果：X11*= ，X12*= ，X13*= ，X14*= Y1*= ,
14、X22*= ，X23*= ，X24*= ，Y2*= , X33*= ，X34*= ，Y3*= , X44*= ，Y4*= , Z*= 9、对以下线性规划问题： Min Z2X1+3X2+5X3+2X4+3X5 s. t. X1+X2+2X3+X4+3X5 4 2X1 X2+3X3+X4+X5 3 X1, X2, X3, X4,X5 0其对偶问题的最优解为 Y1*=4/5, Y2*=3/5, W* = 5。试求出原问题的解。解：设原问题的两个剩余变量分别为：X6 ,X7 原问题的对偶问题为：Max W4Y1+3Y2 s.t. Y1+2Y2 2 松弛变量 Y3 Y1-Y2 3 松弛变量 Y4 2Y
15、1+3Y2 5 松弛变量 Y5 Y1+Y2 2 松弛变量 Y6 3Y1+ Y2 3 松弛变量 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=5X1+3X5=42X1+X5=3得到：X1*=1,X5*=1 原问题的解为：X1*=1, X2*=0，X3*=0，X4*=0，X5*=1,Z* = 510、某厂拟生产甲、乙、丙三种产品，都需要在A、B两
16、种设备上加工，有关数据如下表。 产品设备单耗台时/件设备有效台时每月甲乙丙A121400B212500产值千元/每件321利用对偶性质分析以下问题：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+2Y2 3 剩
17、余变量为Y3 2Y1+ Y22 剩余变量为Y4 Y1+2Y21 剩余变量为Y5Y1,Y2 0 对偶问题可通过图解法求解，得到最优解结果为： 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元，因此，该厂不应该租用外厂的
18、A设备。11、某打井队要从10个可供选择的井位中确定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，0表示不选、1表示选第i井位； 模型如下： 目标函数： Xi=0,1 i=1,2, 10 EXCEL求解最优解结果：X1*= ，X2*= ，X3*= , X4*= , X5*= ,X6*= ，X7*= ，X8*
19、= , Z*= 12、某厂可生产四种产品，对于三种主要资源的单位消耗及单位利润见下表：产品资源1234可供量钢110305000人力26413000能源20253000单位利润1784如果产品3的生产需要用一特殊机器，这机器的固定本钱启用本钱为3000，产品2和产品4的生产也同样需要共用一特定的机器加工，其固定本钱启用本钱为1000，写出此时求利润最大的线性规划模型。解：1)变量：Xi为第i种产品的产量i=1,2,3,4, Y3为0-1变量， Y24为0-1变量，2)目标函数：Max Z = X1+7X2+8X3+4X4-3000Y3-1000Y243)约束条件： 资源约束：X1+10X2+3
20、X35000 2X1+6X2+4X3+X43000 2X1+2X3+5X43000 启用约束：X3 M1Y3 (M1为一足够大的正数，比方取5000 ) X2+X4 M2Y24 (M2为一足够大的正数，比方取5000 ) 非负约束：Xi0 (i=1,2,3,4)；Y3,Y24=0，1EXCEL求解最优解结果：X1*= 0，X2*=400，X3*= 0 , X4*= 600 , Y3=0,Y24=1, Z*=420013、某化工厂要用三种原料D,P,H混合配置三种不同规格的产品A,B,C。各产品的规格、单价如左表所示，各原料的单价及每天的最大供给量如右表所示，该厂应如何安排生产才能使利润最大？产
21、品规格单价元/千克原料最大供给千克/天单价元/千克A原料D不少于50原料P不超过2550D10065B原料D不少于25原料P不超过5035P10025C不限25H6035 解：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-10X333)约束条件：根据规格条件有：X110.
22、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,3EXCEL求解最优解结果：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
23、,X2*=0,X3*=0;每天只生产A 200kg X11*+X21*+X31*=100 使用D 100kg; X12*+X22*+X32*=50 使用P 50kg;X13*+X23*+X33*=50 使用H 50kg;14、某产品有A1和A2两种型号，需经过B1、B2、B3三道工序，单位工时、利润、各工序每周工时限制如下表所示，问工厂如何安排生产，才能使总利润最大B3工序有两种加工方式B31和B32，只能选择其中一种；产品为整数。 工序 工时/件型号B1B2B3利润(元/件)B31B32A1A2372135242540每周工时小时/周250100150120解： 1设变量如下： A1生产量为
24、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,1EXCEL求解最优解结果：X1*= ，X2*= ，Y1 *= , Y2 *=0 , Z*= 15、甲、乙、丙、丁四人加工A、B、C、D四种工件所需时间分钟如表所示，应指派何人加工何种工件，能使总的加工时间最少？要求建立数学模型并求解。 工件
25、人A B C D甲乙丙丁 14 9 4 15 11 7 9 10 13 2 10 517 9 15 13 解：匈牙利方法过程及模型略答案：甲：C；乙：A；丙：D；丁：B16、某厂生产柴油机，14月份订货任务为：1月2000台；2月3000台；3月5500台；4月6000台；该厂的月正常生产能力为3000台，每台的生产本钱为1500元，每月加班生产能力为2000台，加班生产本钱为每台2000元，月库存费用为每台50元，1月初库存为0。建立求本钱最低生产方案的线性规划模型。 解：设Xii=1,2,3,4为第i个月正常生产的柴油机数，Yi为第i个月加班生产的数量，Wi为第i月月初的库存数。该问题的线
26、性规划模型为： 目标函数：Min Z = 1500(X1+X2+X3+X4)+2000(Y1+Y2+Y3+Y4)+50(W2+W3+W4) 约束条件：X1+Y1-W2 = 2000 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、某
27、铸造厂接到一笔订货，要生产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-5
28、0*X1+X2+X3 即：Max Z = 450-260X1-300X2-200X3-80X43约束条件： (0.45%X1+0.5%X2+0.4%X3)*1000+X40.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、有三个产地给四个销地供给某产品，产销地之间的供需量和单位运价如下： 销地产地B1B2B3B4产量A1A2A
29、3534255642763300200400销量200100400200900要求：1建立此运输问题的线性规划模型不需要求解；2由于市场情况的变化，B3 和 B4 的销量各增加了50单位运用表上作业法可求得此时最小运费为2950元。有关部门在研究调运方案时还需要依次考虑以下情况已规定其优先等级 P1P5： P1: B4是重点保证单位，必须尽可能满足其需要； P2: A3向B1提供的量不少于100； P3: 因道路问题，尽量防止安排A2产品运往B4; P4: 给B1和B3的需求供给率要相等； P5: 及最小运费调运方案相比，总运费的增加不超过最小调运方案的10%。 试建立求解满意调运方案的目标规
30、划模型。解：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 = 约束条件： 2目标规划求解：销量增加后供不应求，因此，供给仍为绝对约束： 需求约束为目标约束： (已包含了B4要尽可能满足的条件) X31+d5- - d5+=100 (A3向B1提供的量不少于100) X24+ d6- - d6+=0 尽量防止安排A2产品运往B4 (给B1和B3的需求供给率
31、要相等) + 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
32、每天的纯收入最大。建立此问题的目标规划模型。 解：设安排商业节目时间X1小时，新闻节目时间X2小时，音乐节目时间X3小时。 目标函数： Min Z = P1(d1-+d2-+d3+)+P2d4- 约束条件： X1+X2+X3+ d1- d1+ =12 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项工作需在两台机器上加工，各自的加工时间如下，如何安排加工顺序使系统效率最高(只要求写出加工顺序)。 ABCDEFGHIJ机器11
33、4192422640204125机器221083235183063528解：约翰逊原那么求解过程略 结果： I, H, E, G, D, J, F, B, C, A21、求出以下图中从A到E的最短路线及其长度。AB1B2B3C1C2D1 D2D3E21344313353241352315解：方法一：动态规划在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 方法过程略
34、结果：A 到 E 的最短距离为 8 ,最短路为：A-B2-C1-D1-E4671312225452345671Fij752267213642345671Lij22、求以下图22题图所示网络的最大流写出线性规划模型，并用图上标注的方法求解。 22题图 23题图 解：线性规划模型：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+
35、f65=f57 (节点5的净流量为0) f46+f36=f65+f67 (节点6的净流量为0) fijFij 对一切可能的弧i-j (弧的容量限制) fij0 对一切可能的弧i-j 图上标注过程略，最大流量结果为：923、求网络23题图从节点1到节点7的最短路径写出线性规划模型，并用图上标注的方法求解 。 解：方法一：线性规划模型求解，假设通过网络的最大流量为1，1） 变量：设Xij为弧i-j节点i 节点j 是否流过，流过取值1，不流过取值02） 目标函数：通过网络的总长度最小，因此，有： 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