运筹学习题集二

1、(1)minz=6x1+4x2st.2x1+x2>13x1+4x2>1.5x1,x2>0(3)maxz=x1+x2st.8x1+6x2>244x1+6x2n122x2>4x1,x2>0(5)maxz=3x1+9x2st.x1+3x2<22x1+x2<4x2<6x1,x2>0运筹学习题集二习题一1.1用法求解以下线性规划问题并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解.(2)maxz=4x1+8x2st.2x1+2x2<10-x1+x2>8x1,x2>0(4)maxz=3x12x2st.x1+x2<

2、;12x1+2x2>4x1,x2>0(6) maxz=3x1+4x2st.-x1+2x2<8x1+2x2<122x1+x2<162x15x2<0x1,x2A06.2. 在以下线性规划问题中找出所有根本解指出哪些是根本可行解并分别代入目标函数比拟找出最优解.(1) maxz=3x1+5x2st.x1+x3=4=32x2+x4=123x1+2x2+x5=18(2) minz=4x1+12x2+18x3st.x1+3x3x42x2+2x3-x5=5xj>0(j=1,5)xj>0(j=1,-,5)6.3. 分别用法和单纯形法求解以下线性规划问题并对照指出

3、单纯形法迭代的每一步相当于法可行域中的哪一个顶点.(1) maxz=10x1+5x2st.3x1+4x2w95x1+2x2<8x1,x2>0(2) maxz=100x1+200x2st.x1+x2<500x1<2002x1+6x2<1200x1,x2>01.4.分别用大M法和两阶段法求解以下线性规划问题并指出问题的解属于哪一类：(1)maxz=4x1+5x2+x3st.3x1+2x2+x3>182x1+x2<4x1+x2x3=5xj>0(j=1,2,3)maxz=x1+x2st.8x1+6x2A244x1+6x2n12maxz=2x1+x2

4、+x3st.4x1+2x2+2x3A42x1+4x2<204x1+8x2+2x3W16xj>0(j=1,2,3)(4)maxz=x1+2x2+3x3x4st.x1+2x2+3x3=152x1+x2+5x3=202x2>4x1,x2>0(5)maxz=4x1+6x2st.2x1+4x2<1803x1+2x2<150x1+x2=57x2>22x1,x2>0x1+2x2+x3+x4=10xj>0(j=1,4)(6)maxz=5x1+3x2+6x3st.x1+2x2+x3<182x1+x2+3x3<16x1+x2+x3=10x1,x2A

5、0x3无约束1.5线性规划问题maxz=CXA注bX>0如X*是该问题的最优解又入0为某一常数分别讨论以下情况时最优解的变化：(1)目标函数变为maxz=入CX;(2)目标函数变为maxz=(C+入)X;(3)目标函数变为maxz=X约束条件变为AX=入b.1.6下表中给出某求极大化问题的单纯形表问表中a1,a2,c1,c2,d为何值时以及表中变量属于哪一种类型时有：(1)表中解为唯一最优解；(2)表中解为无穷多最优解之一；(3)表中解为退化的可行解；(4)下一步迭代将以x1替换基变量x5;(5)该线性规划问题具有无界解；(6)该线性规划问题无可行解.x1x2x3x4x5x3d4a110

6、0x4215010x53a23001cj-zjc1c20001.7 战斗机是一种重要的作战工具但要使战斗机发挥作用必须有足够的驾驶员.因此生产出来的战斗机除一局部直接用于战斗外需抽一局部用于驾驶员.每年生产的战斗机数量为aj(j=1,n)又每架战斗机每年能出k名驾驶员问应如何分配每年生产出来的战斗机使在n年内生产出来的战斗机为空防作出最大奉献?1.8 .某石油管道公司希望知道在以下图所示的管道络中可以流过的最大流量是多少及怎样输送弧上数字是容量限制.请建立此问题的线性规划模型不必求解.2 54103 1114365687351.9. 某昼夜效劳的公交线每天各时间区段内所需司机和乘务人员数如下：

7、班次时间所需人数16:00-10:0060210:00-14:0070314:00-18:0060418:00-22:0050522:00-2:002062:00-6:0030设司机和乘务人员分别在各时间区段一开始时上班并连续工作八小时问该公交线至少配备多少名司机和乘务人员.列出此问题的线性规划模型.1.10. 班有男生30人女生20人周日去植树.根据经验一天男生平均每人挖坑20个或栽树30棵或给25棵树浇水；女生平均每人挖坑10个或栽树20棵或给15棵树浇水.问应怎样安排才能使植树包括挖坑、栽树、浇水最多请建立此问题的线性规划模型不必求解.1.11. 某糖果用原料A、B、C加工成三种不同牌号

8、的糖果甲、乙、丙.各种牌号糖果中A、B、C含量原料本钱各种原料的每月限制用量三种牌号糖果的单位加工费及售价如下表所示.问该每月应生产这三种牌号糖果各多少千克使该获利最大试建立此问题的线性规划的数学模型.甲乙丙原料本钱/千克每月限量千克20001.5025001.001200A>60%>15%2.00BC<20%<60%<50%力口工费/千克0.500.400.30售价3.402.852.251.12. 某商店制定7-12月进货售货方案商店仓库容量不得超过500件6月底已存货200件以后每月初进货一次假设各月份此商品买进售出单价如下表所示问各月进货售货各多少才能使总

9、收入最多请建立此问题的线性规划模型不必求解.月份789101112买进单价282425272323售出单价2924262822251.13. .某农场有100公顷土地及15000资金可用于开展生产.农场劳动力情况为秋冬季3500人日春夏季4000人日如劳动力本身用不了时可外出干活春夏季收入为2.1/人日秋冬季收入为1.8/人日.该农场种植三种作物：大豆、玉米、小麦并饲养奶牛和鸡.种作物时不需要专门投资而饲养动物时每头奶牛投资400每只鸡投资3.养奶牛时每头需拨出1.5公顷土地种饲草并占用人工秋冬季为100人日春夏季为50人日年净收入400/每头奶牛.养鸡时不占土地需人工为每只鸡秋冬季需0.6人

10、日春夏季为0.3人日年净收入为2/每只鸡.农场现有鸡舍允许最多养3000只鸡牛栏允许最多养32头奶牛.三种作物每年需要的人工及收人情况如下表所示大豆玉米麦子秋冬季需人日数203510春夏季需人日数507540建立线性规划模型不年净收入/公顷175300120试决定该农场的经营方案使年净收人为最大需求解习题二2.1 写出以下线性规划问题的对偶问题(1) maxz=10x1+x2+2x3st.x1+x2+2x3<10<54x1+x2+x3<20xj>0(j=1,2,3)x1x3>0x2x4无约束(3)minz=3x1+2x23x3+4x4st.x12x2+3x3+4x

11、4<3x2+3x3+4x4>52x13x27x3-4x4=2=(2) maxz=2x1+x2+3x3+x4st.x1x2x3x42x1x2+3x3=-4x1x3+x4>1(4)minz=-5x16x27x3st.x1+5x23x3>155x16x2+10x3<20x1x2x3=5x1A0x4w0x2x3无约束x1<0x2>0x3无约束2.2 线性规划问题maxz=CXAX=b»0.分别说明发生以下情况时其对偶问题的解的变化：(1)问题的第k个约束条件乘上常数入(入#0)；(2)将第k个约束条件乘上常数入(入?0)后加到第r个约束条件上；(3)

12、目标函数改变为maxz=?<CX(?i#0);(4)模型中全部x1用3代换.2.3线性规划问题minz=8x1+6x2+3x3+6x4st.x1+2x2+x4>33x1+x2+x3+x4>6x3+x4=2x1+x3>2xj>0(j=1,2,3,4)(1)写出其对偶问题；原问题最优解为x*=(1120)试根据对偶理论直接求出对偶问题的最优解.对偶变量2.4线性规戈ij问题minz=2x1+x2+5x3+6x4st.2x1+x3+x4<8y12x1+2x2+x3+2x4<12y2xj>0(j=1,2,3,4)其对偶问题的最优解y1*=4;y2*=1试

13、根据对偶问题的性质求出原问题的最优解.2.5考虑线性规划问题max片2x1+4x2+3x3st.3x1+4x2+2x3<602x1+x2+2x3<40x1+3x2+2x3<80xj>0(j=1,2,3)(1)写出其对偶问题(2)用单纯形法求解原问题列出每步迭代计算得到的原问题的解与互补的对偶问题的解；(3)用对偶单纯形法求解其对偶问题并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解；(4)比拟(2)和(3)计算结果.2.6 线性规划问题max片10x1+5x2st.3x1+4x2<95x1+2x2<8用单纯形法求得最终表如下表所示:x1x2x3x4

14、bx201一x1101?j=cj-Zj00试用灵敏度分析的方法分别判断：(1)目标函数系数c1或c2分别在什么范围内变动上述最优解不变；(2)约束条件右端项b1b2当一个保持不变时另一个在什么范围内变化上述最优基保持不变；(3)问题的目标函数变为maxz=12x1+4x2时上述最优解的变化;(4)约束条件右端项由变为时上述最优解的变化.2.7 线性规划问题如下：maxz=-5x1+5x2+13x3st.x1+x2+3x3<2012x1+4x2+10x3<90xj>0(j=1,2,3)先用单纯形法求解然后分析以下各种条件下最优解分别有什么变化(1)约束条件的右端常数由20变为3

15、0;(2)约束条件的右端常数由90变为70;(3)目标函数中x3的系数由13变为8;(4) x1的系数列向量由(一112)T变为(05)T;(5) 增加一个约束条件：2x1+3x2+5x3W50;(6) 将原约束条件改变为：10x1+5x2+10x3<100.2.8用单纯形法求解某线性规划问题得到最终单纯形表如下：cj基变量50401060Sx1x2x3x4ac011 6bd102 4?j=cj-Zj00efg(1)给出abcdefg的值或表达式；(2)指出原问题是求目标函数的最大值还是最小值；(3)用a+?ab+?t#别彳弋替a和b仍然保持上表是最优单纯形表求?a?b满足的范围.2.9

16、 某文教用品用原材料白坯纸生产原稿纸、日记本和练习本三种产品.该现有工人100人每月白坯纸量为30000千克.工人的劳动生产率为：每人每月可生产原稿纸30捆或日记本30打或练习本30箱.原材料消耗为：每捆原稿纸用白坯纸千克每打日记本用白坯纸千克每箱练习本用白坯纸千克.又知每生产一捆原稿纸可获利2生产一打日记本获利3生产一箱练习本获利1.试确定：(1)现有生产条件下获利最大的方案；(2)如白坯纸的数量不变当工人数缺乏时可招收临时工临时工工资支出为每人每月40那么该要不要招收临时工如要的话招多少临时工最适宜2.10 某生产甲、乙两种产品需要A、B两种原料生产消耗等参数如下表(表中的消耗系数为千克/

17、件).产品原料甲乙可用量(千克)原料本钱(/千克)A241601.0B321802.0销售价()1316(1)请构造数学模型使该利润最大并求解.(2)原料A、B的影子各为多少.(3)现有新产品丙每件消耗3千克原料A和4千克原料B问该产品的销售至少为多少时才值得投产.(4)工可在市场上买到原料A.工是否应该购置该原料以扩大生产在保持原问题最优基的不变的情况下最多应购入多少可增加多少利润习题三3.1 求解下表所示的运输问题分别用最小素法、西北角法和伏格尔法给出初始基可行解：B1B2B3B4量A1(10)(6)(7)(12)4A2(16)(10)(5)9A3(4)(10)(10)5需要量534618

18、3.2 由产地A1A2发向销地B1B2的单位费用如下表产地允许存贮销地允许缺货存贮和缺货的单位运费也列入表中.求最优调运方案使总费用最省.B1B2量存贮费/件A1854003A2693004需要量200350缺货费/件253.3 对如下表的运输问题：AB量X100(6)(4)100Y30(5)50(8)80Z(2)60(7)60需要量130110240(1)假设要总运费最少该方案是否为最优方案(2)假设产地Z的量改为100求最优方案.3.4 某利润最大的运输问题其单位利润如下表所示:B1B2B3B4量A1(6)A2(4)(5)A3(9)需要量(8)8(10)(8)9(3)7865524(1)求

19、最优运输方案该最优方案有何特征当A1的量和B3的需求量各增加2时结果又怎样3.5 某玩具公司分别生产三种新型玩具每月可量分别为1000、2000、2000件它们分别被送到甲、乙、丙三个百货商店销售.每月百货商店各类玩具预期销售量均为1500件由于经营方面原因各商店销售不同玩具的盈利额不同,见下表.又知丙百货商店要求至少C玩具1000件而拒绝进A玩具.求满足上述条件下使总盈利额最大的销分配方案.甲乙丙可量A54一1000B16892000C12101120003.6 目前城市大学能存贮200个文件在硬盘上100个文件在计算机存贮器上300个文件在磁带上.用户想存贮300个字处理文件100个源程序

20、文件100个数据文件.每月一个典型的字处理文件被访问8次一个典型的源程序文件被访问4次一个典型的数据文件被访问2次.当某文件被访问时重新找到该文件所需的时间取决于文件类型和存贮介质如下表.时间分钟处理文件源程序文件数据文件硬盘544存贮器211磁带1086如果目标是极小化每月用户访问所需文件所花的时间请构造一个运输问题的模型来决定文件应该怎么存放并求解.3.7 以下五名运发动各种姿势的游泳成绩各为50米如表5-2:试用运输问题的方法来决定如何从中选拔一个参加200混合泳的接力队使预期比赛成绩为最好.赵钱张王周仰泳37.732.933.837.035.4蛀泳43.433.142.234.741.

21、8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.13.8 求总运费最小的运输问题其中某一步的运输图如下表B1B2B3量A13(3)(5)(7)3A22(4)4(4)6A31(6)5(3)d需要量abce(1)写出a,b,c,d,e的值并求出最优运输方案；(2)A3到B1的单位运费满足什么条件时表中运输方案为最优方案.3.9 某一实际的运输问题可以表达如下：有n个地区需要某种物资需要量分别为bj(j=1,n).这些物资均由某公司分设在m个地区的工各工的产量分别为ai(i=1,m)从i地区的工至第j个需求地区的单位物资的运价为cij又=试阐述其对偶问题并解

22、释对偶变量的经济意义.3.10 .为保证飞行平安飞机上的发动机每半年必须强迫更换进行大修.某维修估计某种型号战斗机从下一个半年算起的今后三年内每半年发动机的更换需要量分别为：100708012021014(1更换发动机时可以换上新的也可以用经过大修的旧的发动机.每台新发动机的购置费为10万而旧发动机的维修有两种方式：快修每台2万半年交货(即本期拆下来送修的下批即可用上)；慢修每台1万但需一年交货(即本期拆下来送修的需下下批才能用上).设该新接受该项发动机更换维修任务又知这种型号战斗机三年后将退役退役后这种发动机将报废.问在今后三年的每半年内该为满足维修需要各新购、送去快修和慢修的发动机数各是多

23、少使总的维修费用为最省?将此问题归结为运输问题只列出产销平衡表与单位运价表不求数值解.3.11 甲、乙两个煤矿分别生产煤500万吨A、B、C三个电发电需要各电用量分别为300、300、400万吨.煤矿之间、煤矿与电之间以及各电之间相互距离单位：公里如以下三个表所示.又煤可以直接运达也可经转运抵达,试确定从煤矿到各电间煤的最优调运方案最小总吨公里数.从到甲乙从到ABC从到A甲0120甲15012080A0701001000乙6016040B500120C1001500习题四4.1分别用法和单纯形法求解下述目标规划问题(1)minz=1(+)+2st.x1+x2+d1d+1=10.5x1+x2+d

24、-2-d+2=23x1+3x2+d-3-d+3=50x1x2>0;d-id+i>0(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=12x1x2>0;d-id+i>0(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=60x1x2>0;d-id+i>0(i=14)(1)求满意解

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

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

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

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

29、35x1x2>0且为整数(2) minz=4x1+5x2st.3x1+2x2>7x1+4x2>53x1+x2>2x1,x2>0且为整数5.5 用隐枚举法求解01整数规划问题maxz=3x1+2x25x32x4+3x5st.x1+x2+x3+2x4+x5<47x1+3x3-4x4+3x5<811x1-6x2+3x43x5>3xj=0或1(j=15)5.6 请用解01整数规划的隐枚举法求解下面的两维01背包问题:maxf=2x1+2x2+3x3s.t.x1+2x2+2x3<42x1+x2+3x3<5xj=0或1j=1,2,35.7 用匈牙

30、利法求解如下效率矩阵的指派问题7910121312161715161415111215165.8 分配甲、乙、丙、丁四人去完成五项任务.每人完成各项任务时间如下表所示.由于任务数多于人数故规定其中有一个人可兼完成两项任务其余三人每人完成一项.试确定总花费时间为最少的指派方案.人任务ABCDE甲252931乙3938262033丙3427284032丁244236234542375.9 以下五人各种姿势的游泳成绩各为50米试问如何进行指派从中选拔一个参加200米混合泳的接力队使预期比赛成绩为最好.赵钱张王周仰泳37.732.933.837.035.4蛀泳43.433.142.234.741.8蝶

31、泳33.328.538.930.433.6自由泳29.226.429.628.531.15.10 .运筹学中著名的旅行商贩货郎担问题可以表达如下：某旅行商贩从某一城市出发到其它几个城市去推销商品规定每个城市均须到达而且只到达一次然后回到原出发城市.城市i和j之间的距离为dij问该商贩应选择一条什么样的线顺序旅行使总的旅程为最短.试对此问题建立整数规划模型.5.11 .有三个不同的产品要在三台机床上加工每个产品必须首先在机床1上加工然后依次在机床23上加工.在每台机床上加工三个产品的顺序应保持一样假定用tij表示在第j机床上加工第i个产品的时间问应如何安排使三个产品总的加工周期为最短.试建立此问

32、题的整数规划模型.习题参考第一章线性规划及单纯形法1.1(1)解：1-1第一求可行解集合.令两个约束条件为等式得到两条直线在第一象限划出满足两个不等式的区域其交集就是可行集或称为可行域如下图交集为(1/2,0).第二绘制目标函数图形.将目标函数的系数组成一个坐标点(64)过原点O作一条矢量指向点(64)矢量的长度不限矢量的斜率保持4比6再作一条与矢量垂直的直线这条直线就是目标函数图形目标函数图形的位置任意如果通过原点那么目标函数值Z=0如图1-2所示.第三求最优解.图1-2的矢量方向是目标函数增加的方向或称梯度方向在求最小值时将目标函数图形沿梯度方向的反方向平行移动(在求最大值时将目标函数图形

33、沿梯度方向平行移动)直到可行域的边界停止移动其交点对应的坐标就是最优解如图1-3所示.最优解x=(1/2,0),目标函数的最小值Z=3o(2)无可行解；求解方法与(1)类似(3)无界解；(4)无可行解；(5)无穷多最优解z*=66(6)唯一最优解z*=92/3,x1=20/3,x2=3/81.2(1)解：由题目可知其系数矩阵为因线性独立故有令非基变量得一得到一个基可行解线性独立故有令非基变量得一得到一个根本解但非可行解同理可以求出得根本可行解.得根本可行解.得根本可行解.得根本可行解.得根本非可行解.得根本非可行解.(1)、(2)如下表所示其中打三角符号的是根本可行解打星号的为最x5zx1x2

34、121800126123018006027-9/2x3x4x500-3-5000-510-305/200优解：x1x2x3x400440060-212430*4600-64235/200029/20A1.3305/2-3*363/2(1)解：单纯形法首先将问题化为标准型加松弛变量x3x4得其次列出初始单纯形表计算最优值.CBXB105X1X2X3X40X330X451050X3014/5-3/521/510X12/501/58/5-25X25/14-3/143/210X1-1/72/71-5/14-25/14(表一)由单纯形表一得最优解为法:略1.4解：大M法首先将数

35、学模型化为标准形式式中x4x5为松弛变量x5可作为一个基变量第一、三约束分别参加人工变量x6x7目标函数中参加-Mx6-Mx7一项得到大M单纯形法数学模型由单纯形表计算:CBXB45100-M-MbX1X2X3X4- MX63210X5210- MX711-1(rj4+4M5+3M- MX6-1015X2210- MX7-10-1oj4-2M011X3-1010X2210-MX7-200oj5-2M00表1.4-1.1X5X6X7-1010100001 -M0- 1-21010000- M-2M- 1-201- 1-2018041500010041100010041111-M2-2M0在迭代过

36、程中人工变量一旦出基后不会在进基所以当人工变量X6出基后对应第六列的系数可以不再计算以减少计算量.当用大M单纯形法计算得到最优解并且存在人工变量大于零时那么表明原线性规划无可行解.两阶段单纯形法首先化标准形同大M法第一、三约束分别参加人工变量x6x7后构造第一阶段问题用单纯形法求解得到第一阶段问题的计算表1.4-1.2CBXB00X1X2X3X4X5X6X7X63-118X52X71-1-4-31X601/21-1-3/20120X111/201/201X701/2-1-1/20-11X6-1-1-2100X221X7-1-1-1表1.4-1.2在第一阶段的最优解中人工变量不为零那么原问题无可

37、行解.注：在第二阶段计算时初始表中的检验数不能引用第一阶段最优表的检验数必须换成原问题的检验数.无穷多最优解如X1=(400);X2=(008)(3)无界解(4)唯一最优解X*=(5/25/25/20)唯一最优解X*=(2433)(6)唯一最优解X*=(1404)1.5(4)X*仍为最优解maxz=入CX;(5)除C为常数向量外一般X*不再是该问题的最优解；(6)最优解变为入X*目标函数值不变.1.6(7) d>0,c1<0,c2c0(8) d>0,c1<0,c2<0,但c1c2中至少一个为零(9) d=0或d0而c10且d/4=3/a2(10) c10,d/43

38、/a2(11) c20,a1<0(12) x5为人工变量且c1<0,c2<01.7解：设xj表示第j年生产出来分配用于作战的战斗机数；yj为第j年已出来的驾驶员；(ajxj)为第j年用于驾驶员的战斗机数；zj为第j年用于驾驶员的战斗机总数.那么模型为maxz=nx1+(n1)x2+2xfh+xns.t.zj=zj-1+(aj-xj)yj=yj-1+k(aj-xj)x1+x2+xjwyjxj,yj,zj>0(j=1,2,n)1.8提示：设出每个管道上的实际流量那么发点发出的流量等于收点收到的流量中间点那么流入等于流出再考虑容量限制条件即可.目标函数为发出流量最大.设刈=从

39、点i到点j的流量maxz=x12+x13st.x12=x23+x24+x25x13+x23=x34+x35x24+x34+x54=x46x25+x35=x54+x56以上为流量平衡条件x12+x13=x46+x56始点=收点x12<10x13<6x23<4x24<5x25<3x34<5x35<8x46<11x54<3x56<7xij>0对所有ij1.9提示：设每个区段上班的人数分别为x1x2x6即可1.10解：设男生中挖坑、栽树、浇水的人数分别为x11、x12、x13女生中挖坑、栽树、浇水的人数分别为x21、x22、x23,S为

40、植树棵树.由题意模型为：maxS=20x11+10x21s.t.x11+x12+x13=30x21+x22+x23=2020x11+10x21=30x12+20x22=25x13+15x23Xij>0i=1,2;j=1,2,31.11解：设各生产x1,x2,x3maxz=1.2x1+1.175x2+0.7x3s.t.0.6x1+0.15x2<20000.2x1+0.25x2+0.5x3C25000.2x1+0.6x2+0.5x31200x1,x2,x3>01.12解：设712月各月初进货数量为xi件而各月售货数量为yi件i=12一-6s为总收入那么问题的模型为：maxS=29

41、y1+24y2+26y3+28y4+22y5+25y6-(28x1+24x2+25x3+27x4+23x5+23x6)st.y1<200+x1<500y2<200+x1-y1+x2<500y3<200+x1-y1+x2-y2+x3<500y4<200+x1-y1+x2-y2+x3-y3+x4<500y5<200+x1-y1+x2-y2+x3-y3+x4-y4+x5<500y2<200+x1-y1+x2-y2+x3-y3+x4-y4+x5y5+x6<500xi>0yi>0i=12-6整数1.13解：用x1x2x3

42、分别代表大豆、玉米、麦子的种植面积hm2公顷；x4x5分别代表奶牛和鸡的饲养数；x6x7分别代表秋冬和春夏季多余的劳动力人日那么有第二章对偶理论和灵敏度分析2.1 对偶问题为2.2(1)由于对偶变量Y=CBB-mk个约束条件乘上入(入#0)即B-1的k列将为变化前的1/入由此对偶问题变化后的解(y'1,y'2,y'k,y'm)=(y1,y2,(1/入)yk,ym)(2)与前类似y'r=y'i=yi(i#r)(3) y'i=入yi(i=1,2,m)(4) yi(i=1,2,m)不变2.3(1)对偶问题为(2)由互补松弛性(分别为松弛变量和最

43、优解)可得从而可知又由对偶性质的最优性一一可得四方程联立即可求得对偶问题的最优解：Y*=(2210)2.4解：其对偶问题为minw=8y1+12y22y1+2y2>2(1)2y2>1(2)y1+y2>5(3)y1+2y2>6(4)y1,y2>0将y1*,y2*代入约束条件得(1)与(2)为严格不等式由互补松弛性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

44、)略(2)原问题的解互补的对偶问题的解第一步(000604080)(000-2-4-3)第二步(015002535)(100101)第三步(020/350/30080/3)(5/62/3011/600)(3)对偶问题的解对偶问题互补的对偶问题的解第一步(000243)(000604080)第二步(100101)(015002535)第三步(5/62/3011/600)(020/350/30080/3)(4)比拟(2)和(3)计算结果发现对偶单纯形法实质上是将单纯形法应用于对偶问题的求解又对偶问题的对偶即原问题因此两者计算结果完全相同.2.6(1)15/4<c1<50,4/5<

45、c2<40/324/5<b1<169/2<b2<15(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&gt尸-90,?a+2?b&gt尸-802.9(1)x1,x2,x3代表原稿纸、日记本和练习本月产量建模求解最终单纯形表如下：x1x2x3x4x5x22000017/31/10-10x1100010-4/3-1/1040cj-zj00-10/3-1/10-50(2)临时工影子高于市场故应招收.招200人

46、最适宜2.10(1)S=13x1-(2x1*1.0+3x1*2.0)+16x2-(4x2*1.0+2x2*2.=5x1+8x2maxz=5s.t.2x1+4x2<1603x1+2x2<180x1,x2>0X*=(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)a+15,50-a/4)>0得到-40Wa<200a=200增加利润350X1X2X3X4X215+(3/8)a013/8-1/4X150-a/410-1/41

47、/2s-370-7a/400-7/4-1/2第三章运输问题3.1解：表3.1-1B1B2B3B4量A1(10)(6)(12)4A2(16)(10)(5)(9)9A3(5)(4)(10)(10)5西北角法是优先从运价表的西北角的变量赋值当行或列分配完毕后再在表中余下局部的西北角赋值以此类推直到右下角素分配完毕.表3.1-1西北角素是x11,x11=mina1,bl=min4,5=4将4填在C11的左侧表示A14单位给B2.同时将第一行划去表示A1的产量全部运出得表3.1-2.在表3.1-2中西北角素是x21x21=min9,5-4=1同时降第一列划去表示B1已满足需要得到表3.1-3.依次向右下

48、角安排运量结果如表3.1-4所示表3.1-2B1B2B3B4量A14(10)(6)A2(16)(10)A3(5)(4)(10)需要量534表3.1-3B1B2B3B4量A14(10)(6)A21(16)(10)A3(5)(4)(10)需要量5表3.1-4B1B2B3B4量(4(5)(9)9(10)5618(4(5)9(10)534618A21(16)3(10)4(5)1(9)9A3(5)(4)(10)5(10)5需要量534618最小素法的思想是就近优先运送即最小运价cij对应的变量刈优先赋值xij=minai,bj然后在剩下的运价中取最小运价对应的变量赋值并满足约束依次下去直到最后得到一个初

49、始根本可行解.表3.1-1中最小素是C32令x32=mina3,b2=min5,3=3同时将第二列划去得到表3.1-5.在表3.1-5中最小素为C23C31任意选取其一这里选C31令x31=min5-3,5=2同时将第三行划去得表3.1-6.依次进行下去其结果见表3.1-7.表3.1-5B1B2B3B4量A1(10)(6)(12)4A2(16)(10)(5)(9)9A33(10)(10)5需要量534618表3.1-6B1B2B3B4量A1(10)(6)(12)4A2(16)(10)(5)(9)9A33(10)(10)5表3.1-7B1B2B3B4量A13(10)(6)1(12)4A2(16)

50、(10)459A32(5)3(4)(10)(10)5需要量534618伏格尔法是最小素法的改良考虑到产地到销地的最小运价和此小运价之间的差额如果差额很大就选最小运价处险调运否那么会增加总运费.在表3.1-1中求行差额和列差额.计算公式为假设同时将第三行与第一列划去最后即变量个数比小于3+4-1=6个因而应再x32x33,x34和x11,x12中任意选一个变量作为即变量运量为零这里选x11如表3.1-8所示.求第二个基变量仍然是求差额由于第三行和第一列已满足所以只求u1,u2和v2V3V4即可结果见表3.1-9.此时有两个最大差额u2v2任选一个即可这里选v2.第二列最小运价为c12故x12=m

51、in4,3=3.同时将第二列划去.这样依次下去其结果见表3.1-10.B1B2B3B4量uiA10(10)(6)(12)41A2(16)(10)(5)(9)94A35(5)(4)(10)(10)51需要量534618vj5221表3.1-9B1B2B3B4量uiA10(10)(6)(12)A2(16)(10)(5)A35(5)(4)10)10)18B1B2B3B4A10(10)3(6)(12)A2(16)(10)(5)A35(5)(4)(10)10)需要量46183.4需要量vj表3.1-10B1B2B3B4量A18(6)0(5)A2(4)(5)4(10)A3(2)6(9)1(7)需要量865524(2)B1B2B3B4量A18(6)2(5)A2(4)(5)4(10)A3(2)6(9)1(7)需要