运筹学习题集二

1、(1)minz=6x1+4x2st.2x1+x213x1+4x21.5x1,x20(3)maxz=x1+x2st.8x1+6x2244x1+6x2n122x24x1,x20(5)maxz=3x1+9x2st.x1+3x222x1+x24x20运筹学习题集二习题一1.1用法求解下列线性规划问题并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。(2)maxz=4x1+8x2st.2x1+2x28x1,x20(4)maxz=3x12x2st.x1+x24x1,x20(6) maxz=3x1+4x2st.-x1+2x28x1+2x2122x1+x2162x15x20(j=1,5)xj0(j

2、=1,-,5)6.3. 分别用法和单纯形法求解下列线性规划问题并对照指出单纯形法迭代的每一步相当于法可行域中的哪一个顶点。(1) maxz=10x1+5x2st.3x1+4x2w95x1+2x20(2) maxz=100x1+200x2st.x1+x2500x12002x1+6x201.4.分别用大M法和两阶段法求解下列线性规划问题并指出问题的解属于哪一类：(1)maxz=4x1+5x2+x3st.3x1+2x2+x3182x1+x20(j=1,2,3)maxz=x1+x2st.8x1+6x2A244x1+6x2n12maxz=2x1+x2+x3st.4x1+2x2+2x3A42x1+4x20

3、(j=1,2,3)(4)maxz=x1+2x2+3x3x4st.x1+2x2+3x3=152x1+x2+5x3=202x24x1,x20(5)maxz=4x1+6x2st.2x1+4x21803x1+2x222x1,x20x1+2x2+x3+x4=10xj0(j=1,4)(6)maxz=5x1+3x2+6x3st.x1+2x2+x3182x1+x2+3x30如X*是该问题的最优解又入0为某一常数分别讨论下列情况时最优解的变化：(1)目标函数变为maxz=入CX;(2)目标函数变为maxz=(C+入)X;(3)目标函数变为maxz=X约束条件变为AX=入b。1.6下表中给出某求极大化问题的单纯形

4、表问表中a1,a2,c1,c2,d为何值时以及表中变量属于哪一种类型时有：(1)表中解为唯一最优解；(2)表中解为无穷多最优解之一；(3)表中解为退化的可行解；(4)下一步迭代将以x1替换基变量x5;(5)该线性规划问题具有无界解；(6)该线性规划问题无可行解。x1x2x3x4x5x3d4a1100x4215010x53a23001cj-zjc1c20001.7 战斗机是一种重要的作战工具但要使战斗机发挥作用必须有足够的驾驶员。因此生产出来的战斗机除一部分直接用于战斗外需抽一部分用于驾驶员。已知每年生产的战斗机数量为aj(j=1,n)又每架战斗机每年能出k名驾驶员问应如何分配每年生产出来的战斗

5、机使在n年内生产出来的战斗机为空防作出最大贡献?1.8 .某石油管道公司希望知道在下图所示的管道络中可以流过的最大流量是多少及怎样输送弧上数字是容量限制。请建立此问题的线性规划模型不必求解。2 54103 1114365687351.9. 某昼夜服务的公交线每天各时间区段内所需司机和乘务人员数如下：班次时间所需人数16:00-10:0060210:00-14:0070314:00-18:0060418:00-22:0050522:00-2:002062:00-6:0030设司机和乘务人员分别在各时间区段一开始时上班并连续工作八小时问该公交线至少配备多少名司机和乘务人员。列出此问题的线性规划模型

6、。1.10. 班有男生30人女生20人周日去植树。根据经验一天男生平均每人挖坑20个或栽树30棵或给25棵树浇水；女生平均每人挖坑10个或栽树20棵或给15棵树浇水。问应怎样安排才能使植树（包括挖坑、栽树、浇水）最多？请建立此问题的线性规划模型不必求解。1.11. 某糖果用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C含量原料成本各种原料的每月限制用量三种牌号糖果的单位加工费及售价如下表所示。问该每月应生产这三种牌号糖果各多少千克使该获利最大？试建立此问题的线性规划的数学模型。甲乙丙原料成本（/千克）每月限量（千克）20001.5025001.001200A60

7、%15%2.00BC20%60%50%力口工费（/千克）0.500.400.30售价3.402.852.251.12. 某商店制定7-12月进货售货计划已知商店仓库容量不得超过500件6月底已存货200件以后每月初进货一次假设各月份此商品买进售出单价如下表所示问各月进货售货各多少才能使总收入最多？请建立此问题的线性规划模型不必求解。月份789101112买进单价282425272323售出单价2924262822251.13. .某农场有100公顷土地及15000资金可用于发展生产。农场劳动力情况为秋冬季3500人日春夏季4000人日如劳动力本身用不了时可外出干活春夏季收入为2.1/人日秋冬季

8、收入为1.8/人日。该农场种植三种作物：大豆、玉米、小麦并饲养奶牛和鸡。种作物时不需要专门投资而饲养动物时每头奶牛投资400每只鸡投资3。养奶牛时每头需拨出1.5公顷土地种饲草并占用人工秋冬季为100人日春夏季为50人日年净收入400/每头奶牛。养鸡时不占土地需人工为每只鸡秋冬季需0.6人日春夏季为0.3人日年净收入为2/每只鸡。农场现有鸡舍允许最多养3000只鸡牛栏允许最多养32头奶牛。三种作物每年需要的人工及收人情况如下表所示大豆玉米麦子秋冬季需人日数203510春夏季需人日数507540（建立线性规划模型不年净收入（/公顷）175300120试决定该农场的经营方案使年净收人为最大需求解）

9、习题二2.1 写出下列线性规划问题的对偶问题(1) maxz=10x1+x2+2x3st.x1+x2+2x31054x1+x2+x30(j=1,2,3)x1x30x2x4无约束(3)minz=3x1+2x23x3+4x4st.x12x2+3x3+4x452x13x27x3-4x4=2=(2) maxz=2x1+x2+3x3+x4st.x1x2x3x42x1x2+3x3=-4x1x3+x41(4)minz=-5x16x27x3st.x1+5x23x3155x16x2+10x320x1x2x3=5x1A0x4w0x2x3无约束x10x3无约束2.2 已知线性规划问题maxz=CXAX=b0。分别说

10、明发生下列情况时其对偶问题的解的变化：(1)问题的第k个约束条件乘上常数入(入#0)；(2)将第k个约束条件乘上常数入(入?0)后加到第r个约束条件上；(3)目标函数改变为maxz=?33x1+x2+x3+x46x3+x4=2x1+x32xj0(j=1,2,3,4)(1)写出其对偶问题；已知原问题最优解为x*=(1120)试根据对偶理论直接求出对偶问题的最优解。对偶变量2.4已知线性规戈ij问题minz=2x1+x2+5x3+6x4st.2x1+x3+x48y12x1+2x2+x3+2x40(j=1,2,3,4)其对偶问题的最优解y1*=4;y2*=1试根据对偶问题的性质求出原问题的最优解。2

11、.5考虑线性规划问题max片2x1+4x2+3x3st.3x1+4x2+2x3602x1+x2+2x340x1+3x2+2x30(j=1,2,3)(1)写出其对偶问题(2)用单纯形法求解原问题列出每步迭代计算得到的原问题的解与互补的对偶问题的解；(3)用对偶单纯形法求解其对偶问题并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解；(4)比较(2)和(3)计算结果。2.6 已知线性规划问题max片10x1+5x2st.3x1+4x295x1+2x28用单纯形法求得最终表如下表所示:x1x2x3x4bx201一x1101?j=cj-Zj00试用灵敏度分析的方法分别判断：(1)目标函数系数c

12、1或c2分别在什么范围内变动上述最优解不变；(2)约束条件右端项b1b2当一个保持不变时另一个在什么范围内变化上述最优基保持不变；(3)问题的目标函数变为maxz=12x1+4x2时上述最优解的变化;(4)约束条件右端项由变为时上述最优解的变化。2.7 线性规划问题如下：maxz=-5x1+5x2+13x3st.x1+x2+3x32012x1+4x2+10x30(j=1,2,3)先用单纯形法求解然后分析下列各种条件下最优解分别有什么变化？(1)约束条件的右端常数由20变为30;(2)约束条件的右端常数由90变为70;(3)目标函数中x3的系数由13变为8;(4) x1的系数列向量由(一112)

13、T变为(05)T;(5) 增加一个约束条件：2x1+3x2+5x3W50;(6) 将原约束条件改变为：10x1+5x2+10x30;d-id+i0(i=123)minz=1(2+3)+2+3st.x1+x2+d1d+1=10x1+d-2-d+2=45x1+3x2+d-3-d+3=56x1+x2+d4d+4=12x1x20;d-id+i0(i=14)4.2考虑下述目标规划问题minz=1(d+1+d+2)+22d-4+2d-3+3d-1st.x1+d-1-d+1=20x2+d-2-d+2=35-5x1+3x2+d-3-d+3=220x1-x2+d-4-d+4=60x1x20;d-id+i0(i=

14、14)(1)求满意解；(2)当第二个约束右端项由35改为75时求解的变化；(3)若增加一个新的目标约束：4x1+x2+d5d+5=8该目标要求尽量达到目标值并列为第一优先级考虑求解的变化；(4)若增加一个新的变量x3其系数列向量为(0111)T则满意解如何变化？4.3 一个小型的无线电广播台考虑如何最好地来安排音乐、新闻和商业节目时间。依据法律该台每天允许广播12小时其中商业节目用以赢利每小时可收入250美新闻节目每小时需支出40美音乐节目每播一小时费用为17.50美。法律规定正常情况下商业节目只能占广播时间的20%每小时至少安排5分钟新闻节目。问每天的广播节目该如何安排？优先级如下：1:满足

15、法律规定要求；2:每天的纯收入最大。试建立该问题的目标规划模型。4.4 某企业生产两种产品产品I售出后每件可获利10产品n售出后每件可获利8。生产每件产品I需3小时的装配时间每件产品II需2小时装配时间。可用的装配时间共计为每周120小时但允许加班。在加班时间内生产两种产品时每件的获利分别降低1。加班时间限定每周不超过40小时企业希望总获利最大。试凭自己的经验确定优先结构并建立该问题的目标规划模型。4.5 某生产A、B两种型号的微型计算机产品。每种型号的微型计算机均需要经过两道工序I、II。已知每台微型计算机所需要的加工时间、销售利润及工每周最大加工能力的数据如下：AB每周最大加工能力I 46

16、150II 3270利润（/台）300450工经营目标的期望值及优先级如下：1:每周总利润不得低于10000;2:因合同要求A型机每周至少生产10台：B型机每周至少生产15台；3:由于条件限制且希望充分利用工的生产能力工序I的每周生产时间必须恰好为150小时工序II的每周生产时间可适当超过其最大加工能力（允许加班）。试建立此问题的目标规划模型习题五5.1 试将下述非线性的01规划问题转换为线性的01规划问题maxz=x12+x2x3x33st.-2x1+3x2+x33xj=0或1(j=1,2,3)5.2 某钻井队要从以下10个可选择的井位中确定5个钻井探油使总的钻探费用为最小。若10个井位的代

17、号为s1s2-s10相应的钻探费用为c1c2-c10并且井位选择上要满足下列限制条件：(1)或选择s1和s7或选择钻探s8;(2)选择了s3或s4就不能选s5或反过来也一样；(3)在s5s6s7s8中最多只能选两个。试建立此问题的整数规划模型。5.3 用分枝定界法求解下列整数规划问题(1) maxz=x1+x2st.x1+x2-2x1+x20且为整数(2) maxz=2x1+3x2st.5x1+7x2354x1+9x20且为整数5.4 用割平面法求解下列整数规划问题(1) maxz=7x1+9x2st.-x1+3x267x1+x20且为整数(2) minz=4x1+5x2st.3x1+2x27

18、x1+4x253x1+x22x1,x20且为整数5.5 用隐枚举法求解01整数规划问题maxz=3x1+2x25x32x4+3x5st.x1+x2+x3+2x4+x547x1+3x3-4x4+3x53xj=0或1(j=15)5.6 请用解01整数规划的隐枚举法求解下面的两维01背包问题:maxf=2x1+2x2+3x3s.t.x1+2x2+2x342x1+x2+3x30,c10,c10,c20,但c1c2中至少一个为零(9) d=0或d0而c10且d/4=3/a2(10) c10,d/43/a2(11) c20,a10(12) x5为人工变量且c10,c20(j=1,2,n)1.8提示：设出每

19、个管道上的实际流量则发点发出的流量等于收点收到的流量中间点则流入等于流出再考虑容量限制条件即可。目标函数为发出流量最大。设刈=从点i到点j的流量maxz=x12+x13st.x12=x23+x24+x25x13+x23=x34+x35x24+x34+x54=x46x25+x35=x54+x56以上为流量平衡条件x12+x13=x46+x56始点=收点x1210x136x234x245x253x345x358x4611x543x560对所有ij1.9提示：设每个区段上班的人数分别为x1x2x6即可1.10解：设男生中挖坑、栽树、浇水的人数分别为x11、x12、x13女生中挖坑、栽树、浇水的人数分

20、别为x21、x22、x23,S为植树棵树。由题意模型为：maxS=20x11+10x21s.t.x11+x12+x13=30x21+x22+x23=2020x11+10x21=30x12+20x22=25x13+15x23Xij0i=1,2;j=1,2,31.11解：设各生产x1,x2,x3maxz=1.2x1+1.175x2+0.7x3s.t.0.6x1+0.15x201.12解：设712月各月初进货数量为xi件而各月售货数量为yi件i=12一-6s为总收入则问题的模型为：maxS=29y1+24y2+26y3+28y4+22y5+25y6-(28x1+24x2+25x3+27x4+23x5

21、+23x6)st.y1200+x1500y2200+x1-y1+x2500y3200+x1-y1+x2-y2+x3500y4200+x1-y1+x2-y2+x3-y3+x4500y5200+x1-y1+x2-y2+x3-y3+x4-y4+x5500y2200+x1-y1+x2-y2+x3-y3+x4-y4+x5y5+x60yi0i=12-6整数1.13解：用x1x2x3分别代表大豆、玉米、麦子的种植面积（hm2公顷）；x4x5分别代表奶牛和鸡的饲养数；x6x7分别代表秋冬和春夏季多余的劳动力（人日）则有第二章对偶理论和灵敏度分析2.1 对偶问题为2.2(1)因为对偶变量Y=CBB-mk个约束条

22、件乘上入(入#0)即B-1的k列将为变化前的1/入由此对偶问题变化后的解(y1,y2,，yk,ym)=(y1,y2,(1/入)yk,ym)(2)与前类似yr=yi=yi(i#r)(3) yi=入yi(i=1,2,m)(4) yi(i=1,2,m)不变2.3(1)对偶问题为(2)由互补松弛性(分别为松弛变量和最优解)可得从而可知又由对偶性质的最优性一一可得四方程联立即可求得对偶问题的最优解：Y*=(2210)2.4解：其对偶问题为minw=8y1+12y22y1+2y22(1)2y21(2)y1+y25(3)y1+2y26(4)y1,y20将y1*,y2*代入约束条件得(1)与(2)为严格不等式

23、由互补松弛性YsX*=0得x1*=x2*=0;又因为y1,y2A0由互补松弛性Y*Xs=0得Xs1=Xs2=0原问题约束条件应取等号故x3+x4=8解之得x3=4x3+2x4=12x4=4所以原问题最优解为X*=(0,0,4,4)T目标函数最优值为Z*=44。2.5(1)略(2)原问题的解互补的对偶问题的解第一步(000604080)(000-2-4-3)第二步(015002535)(100101)第三步(020/350/30080/3)(5/62/3011/600)(3)对偶问题的解对偶问题互补的对偶问题的解第一步(000243)(000604080)第二步(100101)(01500253

24、5)第三步(5/62/3011/600)(020/350/30080/3)(4)比较(2)和(3)计算结果发现对偶单纯形法实质上是将单纯形法应用于对偶问题的求解又对偶问题的对偶即原问题因此两者计算结果完全相同。2.6(1)15/4c150,4/5c240/324/5b1169/2b215(3) X*=(8/5021/50)(4) X*=(11/3002/3)2.8(1)a=40,b=50,c=x2,d=x1,e=-22.5,f=-80,g=s-440(2)最大值(3)2?a+?b>尸-90,?a+2?b>尸-802.9(1)x1,x2,x3代表原稿纸、日记本和练习本月产量建模求解最终单纯形表如下：x1x2x3x4x5x22000017/31/10-10x1100010-4/3-1/1040cj-zj00-10/3-1/10-50(2)临时工影子高于市场故应招收。招200人最合适2.10(1)S=13x1-(2x1*1.0+3x1*2.0)+16x2-(4x2*1.0+2x2*2。=5x1+8x2maxz=5s.t.2x1+4x21603x1+2x20X*=(50,15)maxz=370(2)影子：A:7/4B:1/2(3) CBB-1-(-c3+11)0CB=73/4=18.25(4) b=(160+a,180),B-1b=(3/8