运筹学复习模拟题解答.doc

运筹学复习模拟题1、 用图解法求解下列LP问题，并指出各问题的解的类型（1）min z=6x1+4x2s.t. (2) max z=2.5x1+x2s.t. (3) max z=2x1+2x2s.t. (4) max z=x1+x2s.t. 解答：（1）X*=（1/2，0）T，Z*=3;（2）多重最优解，Z*=5;（3）无最优解（无界）；（4）无可行解；2、 把下列线性规划问题化成标准形。(1) min z=2x1+3x2+5x3s.t. 标准形式：(2) min z=3x1+4x2+2x3+x4s.t. 标准形式：3、在下列线性规划问题中，找出所有基解。指出哪些是基可行解，并分别代入目标函数，比较找出最优解maxz=3x1+5x2s.t.x1+x3=42x2+x4=123x1+2x2+x5=18xj0(j=1,5)所有的基解如下表所示：X1X2X3X4X5zX1X2X3X4X500412180000-3-5400126123000-560-2120180010-34306027-9/205/200064063005/20-30262003603/21004600-64235/2000094-6045005/29/204、用单纯形法求解下述线性规划问题：(1) max z=2x1+2x2s.t. (2) max z=10x1+5x2s.t. (3) max z= 5x1+3x2+2x3+4x4s.t. (4) min w= 2x1+3x2+x3s.t. 解答：（1）无最优解；（2）无可行解；（3）X*=（5/3,5/3,0,0）T，z*=40/3;（4）X*=（2,0,3）T，或（4/5,9/5,0）T，*=7;5、写出下列线性规划问题的对偶问题：（1）max z=4x1+3x2+6x3s.t. （2）min w=60x1+10x2+20x3s.t. （3）min w=5x1-3x2s.t. （4）max z=4x1+3x2+6x3s.t. 根据表格对应过去即可，注意对应的方向6、已知线性规划问题：maxz=x1-x2+x3s.t.x1-x34x1-x2+2x33xi0（1,3)试应用对偶理论证明上述线性规划问题无最优解解答：该问题存在可行解，如X=(4,0,0)，其对偶问题为可知该问题无可行解，所以由对偶问题的性质得原问题有无界解7、已知线性规划问题maxz=x1+2x2+3x3+4x4 s.t.x1+2x2+2x3+3x4202x1+x2+3x3+2x420xi0i=1,4 其对偶问题最优解为y1=1.2,y2=0.2.试根据对偶理论求出原问题的最优解解答：写出对偶问题并根据互补松弛性质可求得原问题最优解为X=(0,0,4,4)8、已知线性规划问题max z=5x1+2x2+3x3s.t. 对于给定的常数和，其最优单纯形表是：cj5 2 3 0 0 基解x1 x2 x3 x4 x550x1x530101 1 2 1 00 2 -8 -1 1检验行1500 3 7 4 5其中1，2，3，4，5是常数。试求：（1）b1和b2的值。（2）对偶问题的最优解。（3）1，2，3的值。（4）参数c1, c2, c3的影响范围。（5）参数b1，b2的影响范围。 解答：（1）b1=30，b2=40；（2）y1*=4=5 ，y2*=5=0；（3）1=5，2= -10，3=23；（4）c13/2，）；c2（-，25；c2（-，10；（5）b10，40；b230，）；9、列出下列运输问题的数学模型并用表上作业法求解（1） 销 地产地 产量126 4 8 524销 量 3 3最优运输方案产地 销地最小费用Z* =35II12213(2) 销地产地B1 B2 B3 B4产量A1A2A34 8 7 53 5 4 3 5 4 9 6736销 量 4 4 3 3最优运输方案产地 销地B1B2B3B4最小费用Z* =59B5（虚）A143A23A34210、某肉食品加工厂按合同要在今后两个月内为某个肉蛋禽联营商店加工某种熟肉制品14500公斤。其中第一个月需交货8000公斤，若未交够，不足的部分可由第二个月补交，但补交的数量须回扣给商店0.1元/公斤。全部加工任务必须在第二个月末前完成，否则将重金赔偿商店损失。另若加工好的肉制品当月不交货，则每贮存一个月需花冷藏费0.05元/公斤。该厂的加工能力及加工费用如下表所示。试为该项目合同拟订一个总费用最少的生产调度方案。 月份生产方式加工能力（公斤）加工费（元/公斤） 1 2 1 2正常生产加班生产外协生产5500200020006000250020000.600.750.850.600.700.80最优解： 产地 销地12虚正常155最小总费用Z* =9150元加班120外协120正常260加班25515外协22011、用匈牙利法求解下列指派问题，已知效率矩阵分别如下：(1)791012131216171516141511121516最优指派方案为x13=x22=x34=x41=1，最优值为48(2)3821038729764275842359106910最优指派方案为x15=x23=x32=x44=x51=1，最优值为2112、在下列网络中，求点s到各点的最短路。2t32563447122437S123456t86194318216512916311427258971714736S (a) s 1 , s 3 2 1 ,路长7； S 3 2 ,路长6； S 3 , 路长8； S 3 2 4 , 路长8； S 3 5 , 路长6； S 6 , 路长3； S 3 2 4 t , s 3 5 t , s 6 t , 路长9；(b) (2) (3) (4) (7) (8) (12) S 1 4 8 6 9 t s 2 , s 1 2 , s 1 4 2 (8)(15) s 2 3 , s 1 2 3 s 1 4 2 3 s 1 4 8 5 (10) s 1 4 8 7 (11)13、求下列网络的最大流与最小截集。弧旁的数字为其容量。64157433332613s1234t(a)109554495613s12345t45(b)（a）最大流量f（X*）=21；最小截集（S*，*）=（s，1），（s，2），（s，3）。（b）最大流量f（X*）=20；最小截集（S*，*）=（s，2），（1，4），（1，3）。14、有四根同一规格的轴A,B,C,D四个同一规格的齿轮，现要将轴与齿轮配对使用。由于精度不高，不能任意匹配。已知A只能与配合，B能与，配合，C能与，配合，D能与，配合.应如何匹配才能充分利用这些零件。试用网络分析的方法求解。转化为最大流问题，画出最大流问题的网络图SABCIIIIIIIVDT其中每条弧的容量均为1；求起点到终点的最大流可得为3，即最多3个轴与齿轮匹配15、已知下面信息： 工 序A B C D E F G H I J 紧前工序 A A B B、CB D、FD、E E G、H工序时间2 7 6 3 5 9 4 4 6 5 要求：（1）绘制网络图；（2）计算各项时间参数；（3）确定关键路线项目计划网络图：G12A23B74C65D36E57F9849H4I610J5求出每个作业网络时间来判断关键路线:作业代号ABCDEFGHIJ作业时间2763594465紧前作业-AABB,CBD,FD,EEG,HES02299918141422EF29812141822182027LS0271513918182122LF291318181822222727总时差0056400470关键路线：A-B-F-G-J16、下图给出了某工程项目的网络图，下表给出了该项目各项作业正常进度和赶工进度的时间及费用。若该项目必须在38d内完成，是否需采取措施以及采取什么措施使全部费用为最低？976104215854672131211100975864321 作业正常工作赶工工作作业时间/d费用/元作业时间/d费用/元(1,2)2120011500(2,3)4250032700(3,4)10550076400(4,5)4340024100(4,6)6190042200(4,7)7140051600(5,7)5110031400(6,8)7930049900(7.9)8460064800(8,10)9130051700(9,11)490031000(9,12)5180032100(10.13)23001400(12,13)6260033000 解答：由项目网络图所得关键路线知工期总长为44d，故应采取措施。先计算出每项作业最多可以缩短的作业时间以及赶工时每缩短1d额外增加的费用，见下表作业可缩短时间/d缩短1d增加的费用/元(1,2)1300(2,3)1200(3,4)3300(4,5)2250(4,6)2150(4,7)2100(5,7)2150(6,8)3200(7.9)2100(8,10)4100(9,11)1100(9,12)2150(10.13)1100(12,13)3133.3再按关键路线上缩短1d增加费用由小到大的次序排列操作，可得为使总工期缩短至38d，应压缩作业（7,9），（12,13）工期各2d，缩短作业（2,3）（8,10）（9,12）工期各1d，累计增加赶工费用916.6元。17、试建立下述问题的数学模型：（1）某省外贸局拟从下列应试者中招聘四名工作人员，希望所招四人平均业务能力评分最高，且满足下述要求：专业不得相同；女性最多不超过二人；至少有一名精通日语者；精通英语者最多入选一人。姓名性别专业精通语种业务能力评分戴胜春杨光马跃李玉芬康平姜洁男女男女男女纺织机械化工电子机械食品英英德法日日959387878373设每个人是否被录用为xi(i=1,6)问题的数学模型为（2）某厂为生产某种新产品设计了三种生产方案，如下表所示：方案一次性投资（万元）生产费用（元/件）生产能力（万件）101625 543 814 22该产品销价为每件10元。据市场调研，在该产品生命周期内的需求量为30万见。应如何拟订生产计划能使经济效益最佳？设方案I生产x1件，方案II生产x2件，方案III生产x3件；方案I是否实施为y1，方案II是否实施为y2，方案III是否实施为y3问题的数学模型为：（3）某石油化学工业公司的某项产品售价为每公升1.20元，产量随生产过程中温度的升高而增加，其数量关系如下图所示。假定产品成本与生产中的温度成正比，每提高一度的费用为30元，则应生产多少公升该项产品，才能使利润为最大？设0-10间生产的产品数量为x1百公升，10-20间生产的产品数量为x2百公升，20-40间生产的产品数量为x3百公升根据下图可得温度y和产量x的关系函数问题的数学模型如下：公升*1020246840302010（4）某人要去A市探亲，由于他已领取了个体经营（干鲜水果）的执照，因此打算顺便贩运本地产的橘子，香蕉两种鲜果。橘子，香蕉在本地的购价分别为每箱4，5元，每箱毛重分别为8，12公斤。由于春节将临，因此他考虑两种贩运方式：若乘飞机，能在除夕前赶到，从而能卖高价，且能保证果品无损；若乘轮船，则在初四赶到，只能卖中高价格，且因途中果品会有损伤而使每箱收入减少10%，有关数据如下表所示。另外，他已决定要用相当于毛重各为半箱数量的橘子，香蕉馈赠亲友，而且途中要携带2公斤的生活日用品。问他应乘坐哪种交通工具且携带两种果品各多少箱，才能使这次贩运预计盈利最高。贩运方式单程票价（元）免费携重（公斤）超重收费（元/公斤）限重（公斤）限容 （箱数）A市时价（元/箱）橘子香蕉飞机450101.005052428轮船60300.40100102023提示：对两种贩运方式分别各设携带两种果品的箱数为x1 ，x2以及x3 ，x4。先按每种贩运方式单独建立一个IP模型，然后引入0-1变量，将两个模型并为一个。（5）制造某机床需要A,B,C三种轴，其规格、需要量如下表所示。各种轴都用长7.4米的圆钢来截毛坯。如果制造100台机床，问最少要用多少根圆钢？试建立数学模型。轴件规格：长度（米）每台机床所需轴件数量ABC2.92.11.2111列出所有7.4米圆钢截成三种规格轴件的可能组合为2.9+2.9+1.2；2.9+2.1+2.1；2.9+2.1+1.2+1.2；2.9+1.2+1.2+1.2；2.1+2.1+2.1；2.1+2.1+1.2+1.2；2.1+1.2+1.2+1.2+1.2；1.2+1.2+1.2+1.2+1.2+1.2；设每种截法的数量分别为2.9+2.9+1.2X12.9+2.1+2.1X22.9+2.1+1.2+1.2X32.9+1.2+1.2+1.2X42.1+2.1+2.1X52.1+2.1+1.2+1.2X62.1+1.2+1.2+1.2+1.2X71.2+1.2+1.2+1.2+1.2+1.2X8原问题的数学模型为：（6）某木材公司经营的木材储存在仓库中，最大贮存量为20万米3。由于木材价格随季节变化，该公司于每季初购进木材，一部分当季售出，一部分贮存以后出售。贮存费为a+bu, 其中a=7元/米3，b=10元/米3 /季，u为贮存的季度数。由于木材久贮易损，因此当年所有库存木材应于秋末售完。各季度木材单价及销量如下表所示。为获全年最大利润，该公司各季应分别购销多少木材？试建立数学模型。季购时价（元/米3）售出价（元/米3）最大销售量（万米3）冬春夏秋31032534834032133335234410142016将