运筹学习题集二

1、运筹学习题集二 习题一1.1 用法求解下列线性规划问题并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。(1) min z 6x14x2 (2) max z 4x18x2 st. 2x1 x21 st. 2x12x2103x1 4x21.5 x1 x28x1, x20 x1, x20(3) max z x1 x2 (4) max z 3x12x2 st. 8x16x224 st. x1x214x16x212 2x12x242x24 x1, x20x1, x20(5) max z 3x19x2 (6) max z 3x14x2st. x13x222 st. x12x28x1 x24

2、x12x212x26 2x1 x2162x15x20 x1, x20x1, x201.2. 在下列线性规划问题中找出所有基本解指出哪些是基本可行解并分别代入目标函数比较找出最优解。(1) max z 3x15x2 (2) min z 4x112x218x3st. x1 x3 4 st. x1 3x3 x4 32x2 x4 12 2x22x3 x553x1 2x2 x5 18 xj 0 （j1,5）xj 0 （j1,5）1.3. 分别用法和单纯形法求解下列线性规划问题并对照指出单纯形法迭代的每一步相当于法可行域中的哪一个顶点。(1) max z 10x15x2 st. 3x14x295x12x2

3、8x1, x20(2) max z 100x1200x2st. x1 x2500x1 2002x16x21200 x1, x201.4. 分别用大M法和两阶段法求解下列线性规划问题并指出问题的解属于哪一类：(1) max z 4x15x2 x3 (2) max z 2x1 x2 x3st. 3x12x2 x318 st. 4x12x22x342x1 x2 4 2x14x2 20x1 x2 x35 4x18x22x316xj 0 （j1,2,3） xj 0 （j1,2,3）(3) max z x1 x2 (4) max z x12x23x3x4 st. 8x16x224 st. x12x23x3

4、154x16x212 2x1 x25x3202x24 x12x2 x3 x410x1, x20 xj 0 （j1,4）(5) max z 4x16x2 (6) max z 5x13x26x3 st. 2x14x2 180 st. x12x2 x3183x12x2 150 2x1 x23x316x1 x257 x1 x2 x310x222 x1, x20x3无约束x1, x201.5 线性规划问题max zCXAXbX0如X*是该问题的最优解又0为某一常数分别讨论下列情况时最优解的变化：（1）目标函数变为max zCX；（2）目标函数变为max z（C）X；（3）目标函数变为max z X约束条

5、件变为AXb。1.6 下表中给出某求极大化问题的单纯形表问表中a1, a2, c1, c2, d为何值时以及表中变量属于哪一种类型时有：（1）表中解为唯一最优解；（2）表中解为无穷多最优解之一；（3）表中解为退化的可行解；（4）下一步迭代将以x1替换基变量x5 ；（5）该线性规划问题具有无界解；（6）该线性规划问题无可行解。x1 x2 x3 x4 x5x3 d 4 a1 1 0 0 x4 2 1 5 0 1 0x5 3 a2 3 0 0 1cj zj c1 c2 0 0 01.7 战斗机是一种重要的作战工具但要使战斗机发挥作用必须有足够的驾驶员。因此生产出来的战斗机除一部分直接用于战斗外需抽一

6、部分用于驾驶员。已知每年生产的战斗机数量为aj（j1,n）又每架战斗机每年能出k名驾驶员问应如何分配每年生产出来的战斗机使在n年内生产出来的战斗机为空防作出最大贡献？1.8. 某石油管道公司希望知道在下图所示的管道络中可以流过的最大流量是多少及怎样输送弧上数字是容量限制。请建立此问题的线性规划模型不必求解。2 5 410 3 111 4 3 656 8 73 51.9. 某昼夜服务的公交线每天各时间区段内所需司机和乘务人员数如下：班 次 时 间 所需人数1 6:00-10:00 602 10:00-14:00 703 14:00-18:00 604 18:00-22:00 505 22:00-

7、2:00 206 2:00-6:00 30设司机和乘务人员分别在各时间区段一开始时上班并连续工作八小时问该公交线至少配备多少名司机和乘务人员。列出此问题的线性规划模型。1.10 某班有男生30人女生20人周日去植树。根据经验一天男生平均每人挖坑20个或栽树30棵或给25棵树浇水；女生平均每人挖坑10个或栽树20棵或给15棵树浇水。问应怎样安排才能使植树（包括挖坑、栽树、浇水）最多？请建立此问题的线性规划模型不必求解。1.11.某糖果用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C含量原料成本各种原料的每月限制用量三种牌号糖果的单位加工费及售价如下表所示。问该每月

8、应生产这三种牌号糖果各多少千克使该获利最大？试建立此问题的线性规划的数学模型。甲 乙 丙 原料成本(/千克) 每月限量（千克）A 60 15 2.00 2000B 1.50 2500C 20 60 50 1.00 1200加工费（/千克） 0.50 0.40 0.30售 价 3.40 2.85 2.251.12. 某商店制定712月进货售货计划已知商店仓库容量不得超过500件6月底已存货200件以后每月初进货一次假设各月份此商品买进售出单价如下表所示问各月进货售货各多少才能使总收入最多？请建立此问题的线性规划模型不必求解。月 份 7 8 9 10 11 12买进单价 28 24 25 27 2

9、3 23售出单价 29 24 26 28 22 251.13 .某农场有100公顷土地及15000资金可用于发展生产。农场劳动力情况为秋冬季3500人日春夏季4000人日如劳动力本身用不了时可外出干活春夏季收入为2.1人日秋冬季收入为1.8人日。该农场种植三种作物：大豆、玉米、小麦并饲养奶牛和鸡。种作物时不需要专门投资而饲养动物时每头奶牛投资400每只鸡投资3。养奶牛时每头需拨出1.5公顷土地种饲草并占用人工秋冬季为100人日春夏季为50人日年净收入400每头奶牛。养鸡时不占土地需人工为每只鸡秋冬季需0.6人日春夏季为0.3人日年净收人为2每只鸡。农场现有鸡舍允许最多养3000只鸡牛栏允许最多

10、养32头奶牛。三种作物每年需要的人工及收人情况如下表所示。大豆玉米麦子秋冬季需人日数203510春夏季需人日数507540年净收入(公顷)175300120试决定该农场的经营方案使年净收人为最大。(建立线性规划模型不需求解)习题二2.1 写出下列线性规划问题的对偶问题(1) max z 10x1 x22x3 (2) max z 2x1 x23x3 x4st. x1 x22 x310 st. x1 x2 x3 x4 54x1 x2 x320 2x1 x23x3 4xj 0 （j1,2,3） x1 x3 x41x1x30x2x4无约束(3) min z 3x12 x23x34x4 (4) min

11、z 5 x16x27x3st. x12x23x34x43 st. x15x23x3 15x23x34x45 5x16x210x3 202x13x27x3 4x42 x1 x2 x35x10x40x2x3 无约束 x10 x20x3 无约束2.2 已知线性规划问题max zCXAX=bX0。分别说明发生下列情况时其对偶问题的解的变化：（1）问题的第k个约束条件乘上常数（0）；（2）将第k个约束条件乘上常数（0）后加到第r个约束条件上；（3）目标函数改变为max zCX（0）；（4）模型中全部x1用3 代换。2.3 已知线性规划问题 min z8x16x23x36x4st. x12x2 x433x

12、1 x2 x3 x46x3 x42 x1 x3 2xj0（j1,2,3,4）(1) 写出其对偶问题；(2) 已知原问题最优解为x*（1120）试根据对偶理论直接求出对偶问题的最优解。2.4 已知线性规划问题 min z2x1x25x36x4 对偶变量st. 2x1 x3 x48 y12x12x2x32x412 y2xj0（j1,2,3,4）其对偶问题的最优解y1*=4；y2*=1试根据对偶问题的性质求出原问题的最优解。2.5 考虑线性规划问题 max z2x14x23x3 st. 3x14 x22x3602x1 x22x340x13x22x380xj0 （j1,2,3）（1）写出其对偶问题（2

13、）用单纯形法求解原问题列出每步迭代计算得到的原问题的解与互补的对偶问题的解；（3）用对偶单纯形法求解其对偶问题并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解；（4）比较（2）和（3）计算结果。2.6 已知线性规划问题 max z10x15x2st. 3x14x295x12x28xj0（j1,2）用单纯形法求得最终表如下表所示：x1x2x3x4bx201 x110 1?j=cj-Zj00 试用灵敏度分析的方法分别判断：（1）目标函数系数c1或c2分别在什么范围内变动上述最优解不变；（2）约束条件右端项b1b2当一个保持不变时另一个在什么范围内变化上述最优基保持不变；（3）问题的目标函

14、数变为max z 12x14x2时上述最优解的变化；（4）约束条件右端项由 变为 时上述最优解的变化。2.7 线性规划问题如下： max z5x15x213x3 st. x1x23x320 12x14x210x390 xj0 （j1,2,3）先用单纯形法求解然后分析下列各种条件下最优解分别有什么变化？（1）约束条件的右端常数由20变为30；（2）约束条件的右端常数由90变为70；（3）目标函数中x3的系数由13变为8；（4）x1的系数列向量由（112）T变为（05）T；（5）增加一个约束条件：2x13x25x350；（6）将原约束条件改变为：10x15x210x3100。2.8 用单纯形法求解

15、某线性规划问题得到最终单纯形表如下：cj基变量50401060Sx1x2x3x4ac01 16bd10 24?j=cj-Zj00efg（1）给出abcdefg的值或表达式；（2）指出原问题是求目标函数的最大值还是最小值；（3）用a+?ab+?b分别代替a和b仍然保持上表是最优单纯形表求?a?b满足的范围。2.9 某文教用品用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该现有工人100人每月白坯纸量为30000千 克。已知工人的劳动生产率为：每人每月可生产原稿纸30捆或日记本30打或练习本30箱。已知原材料消耗为：每捆原稿纸用白坯纸 千克每打日记本用白坯纸 千克每箱练习本用白坯纸 千克。又知

16、每生产一捆原稿纸可获利2生产一打日记本获利3生产一箱练习本获利1。试确定：（1）现有生产条件下获利最大的方案；（2）如白坯纸的数量不变当工人数不足时可招收临时工临时工工资支出为每人每月40则该要不要招收临时工？如要的话招多少临时工最合适？2.10 某生产甲、乙两种产品需要A、B两种原料生产消耗等参数如下表（表中的消耗系数为千克/件）。产品原料甲乙可用量（千克）原料成本（/千克）A241601.0B321802.0销售价（）1316（1）请构造数学模型使该利润最大并求解。（2）原料A、B的影子各为多少。（3）现有新产品丙每件消耗3千克原料A和4千克原料B问该产品的销售至少为多少时才值得投产。（4

17、）工可在市场上买到原料A。工是否应该购买该原料以扩大生产？在保持原问题最优基的不变的情况下最多应购入多少？可增加多少利润？习题三3.1 求解下表所示的运输问题分别用最小素法、西北角法和伏格尔法给出初始基可行解：B1B2B3B4量A1（10）（6）（7）（12）4A2（16）（10）（5）（9）9A3（5）（4）（10）（10）5需要量5346183.2由产地A1A2发向销地B1B2的单位费用如下表产地允许存贮销地允许缺货存贮和缺货的单位运费也列入表中。求最优调运方案使总费用最省。B1B2量存贮费/件A1854003A2693004需要量200350缺货费/件253.3 对如下表的运输问题：AB

18、量X100（6）（4）100Y30（5）50（8）80Z（2）60（7）60需要量130110240(1)若要总运费最少该方案是否为最优方案?(2)若产地Z的量改为100求最优方案。3.4 某利润最大的运输问题其单位利润如下表所示：B1B2B3B4量A1（6）（7）（5）（8）8A2（4）（5）（10）（8）9A3（2）（9）（7）（3）7需要量865524(1)求最优运输方案该最优方案有何特征?(2)当A1的量和B3的需求量各增加2时结果又怎样?3.5 某玩具公司分别生产三种新型玩具每月可量分别为1000、2000、2000件它们分别被送到甲、乙、丙三个百货商店销售。已知每月百货商店各类玩具

19、预期销售量均为1500件由于经营方面原因各商店销售不同玩具的盈利额不同,见下表。又知丙百货商店要求至少C玩具1000件 而拒绝进A玩具。求满足上述条件下使总盈利额最大的销分配方案。甲 乙 丙 可量A 5 4 1000B 16 8 9 2000C 12 10 11 20003.6 目前城市大学能存贮200个文件在硬盘上100个文件在计算机存贮器上300个文件在磁带上。用户想存贮300个字处理文件100个源程序文件100个数据文件。每月一个典型的字处理文件被访问8次一个典型的源程序文件被访问4次一个典型的数据文件被访问2次。当某文件被访问时重新找到该文件所需的时间取决于文件类型和存贮介质如下表。时

20、 间（分钟） 处理文件 源程序文件 数据文件硬盘 5 4 4存贮器 2 1 1磁带 10 8 6如果目标是极小化每月用户访问所需文件所花的时间请构造一个运输问题的模型来决定文件应该怎么存放并求解。3.7 已知下列五名运动员各种姿势的游泳成绩（各为50米）如表5-2：试用运输问题的方法来决定如何从中选拔一个参加200混合泳的接力队使预期比赛成绩为最好。赵钱张王周仰 泳37.732.933.837.035.4蛙 泳43.433.142.234.741.8蝶 泳33.328.538.930.433.6自由泳29.226.429.628.531.13.8 求总运费最小的运输问题其中某一步的运输图如下表

21、。B1B2B3量A13（3）（5）（7）3A22（4）4（2）（4）6A3（5）1（6）5（3）d需要量abce（1）写出a,b,c,d,e的值并求出最优运输方案；（2）A3到B1的单位运费满足什么条件时表中运输方案为最优方案。3.9 某一实际的运输问题可以叙述如下：有n个地区需要某种物资需要量分别为bj（j1,n）。这些物资均由某公司分设在m个地区的工各工的产量分别为ai（i1,m）已知从i地区的工至第j个需求地区的单位物资的运价为cij又 试阐述其对偶问题并解释对偶变量的经济意义。3.10. 为确保飞行安全飞机上的发动机每半年必须强迫更换进行大修。某维修估计某种型号战斗机从下一个半年算起的

22、今后三年内每半年发动机的更换需要量分别为：50140。更换发动机时可以换上新的也可以用经过大修的旧的发动机。已知每台新发动机的购置费为10万而旧发动机的维修有两种方式：快修每台2万半年交货（即本期拆下来送修的下批即可用上）；慢修每台1万但需一年交货（即本期拆下来送修的需下下批才能用上）。设该新接受该项发动机更换维修任务又知这种型号战斗机三年后将退役退 役后这种发动机将报废。问在今后三年的每半年内该为满足维修需要各新购、送去快修和慢修的发动机数各是多少使总的维修费用为最省？（将此问题归结为运输问题只列出产销平衡表与单位运价表不求数值解。）3.11 甲、乙两个煤矿分别生产煤500万吨A、B、C三个

23、电发电需要各电用量分别为300、300、400万吨。已知煤矿之间、煤矿与电之间以及各电之间相互距离（单位：公里）如下列三个表所示。又煤可以直接运达也可经转运抵达,试确定从煤矿到各电间煤的最优调运方案（最小总吨公里数）。从 到 甲 乙 从 到 A B C 从 到 A B C 甲 0 120 甲 150 120 80 A 0 70 100乙 100 0 乙 60 160 40 B 50 0 120C 100 150 0习题四4.1 分别用法和单纯形法求解下述目标规划问题（1）min z 1（ ）2 st. x1 x2 d1 d110.5x1 x2 d2d223x13x2 d3 d350x1x20；

24、didi0（i =123）（2） min z 1（2 3 ）2 3 st. x1 x2d1d1 10x1 d2d2 45x13x2d3d3 56x1 x2d4d4 12x1x20；didi 0（i =14）4.2考虑下述目标规划问题min z 1（d1d2）22d42d33d1st. x1 d1d120x2d2d2355x13x2d3d3220x1x2d4d460x1x20；didi 0（i =14）（1）求满意解；（2）当第二个约束右端项由35改为75时求解的变化；（3）若增加一个新的目标约束：4x1x2d5d58该目标要求尽量达到目标值并列为第一优先级考虑求解的变化；（4）若增加一个新的变

25、量x3其系数列向量为（0111）T则满意解如何变化？4.3 一个小型的无线电广播台考虑如何最好地来安排音乐、新闻和商业节目时间。依据法律该台每天允许广播12小时其中商业节目用以赢利每小时可收入250美新闻节目每小时需支出40美音乐节目每播一小时费用为17.50美。法律规定正常情况下商业节目只能占广播时间的20每小时至少安排5分钟新闻节目。问每天的广播节目该如何安排？优先级如下：1：满足法律规定要求；2：每天的纯收入最大。试建立该问题的目标规划模型。4.4 某企业生产两种产品产品售出后每件可获利10产品售出后每件可获利8。生产每件产品需3小时的装配时间每件产品需2小时装配时间。可用的装配时间共计

26、为每周120小时但允许加班。在加班时间内 生产两种产品时每件的获利分别降低1。加班时间限定每周不超过40小时企业希望总获利最大。试凭自己的经验确定优先结构并建立该问题的目标规划模型。4.5 某生产A、B两种型号的微型计算机产品。每种型号的微型计算机均需要经过两道工序I、II。已知每台微型计算机所需要的加工时间、销售利润及工每周最大加工能力的数据如下：AB每周最大加工能力I46150II3270利润（/台）300450工经营目标的期望值及优先级如下：1：每周总利润不得低于10000；2：因合同要求A型机每周至少生产10台：B型机每周至少生产15台；3：由于条件限制且希望充分利用工的生产能力工序I

27、的每周生产时间必须恰好为150小时工序II的每周生产时间可适当超过其最大加工能力（允许加班）。试建立此问题的目标规划模型习题五5.1 试将下述非线性的01规划问题转换为线性的01规划问题max z x12x2x3x33st. 2x13x2x3 3xj0或1（j1,2,3）5.2 某钻井队要从以下10个可选择的井位中确定5个钻井探油使总的钻探费用为最小。若10个井位的代号为s1s2s10相应的钻探费用为c1c2c10并且井位选择上要满足下列限制条件：（1）或选择s1和s7或选择钻探s8；（2）选择了s3或s4就不能选s5或反过来也一样；（3）在s5s6s7s8中最多只能选两个。试建立此问题的整数

28、规划模型。5.3 用分枝定界法求解下列整数规划问题(1) max z x1x2st. x1 x2 2x1 x2 x1x20且为整数(2) max z 2x13x2st. 5x17x235 4x19x236 x1x20且为整数5.4 用割平面法求解下列整数规划问题(1) max z 7x19x2 st. x13 x2 67x1 x2 35 x1x20且为整数(2) min z 4x15x2st. 3x12x27x14x253x1 x22x1, x20且为整数5.5用隐枚举法求解01整数规划问题max z 3x12x25x32x43x5st. x1 x2 x32x4 x5 47x1 3x34x43

29、x5 811x16x2 3x43x5 3xj 0或1（j15）5.6 请用解01整数规划的隐枚举法求解下面的两维01背包问题：max f = 2x1+2x2+3x3s.t. x1+2x2+2x342x1+x2+3x35xj=0或1j=1,2,3 5.7 用匈牙利法求解如下效率矩阵的指派问题7 9 10 1213 12 16 1715 16 14 1511 12 15 165.8 分配甲、乙、丙、丁四人去完成五项任务。每人完成各项任务时间如下表所示。由于任务数多于人数故规定其中有一个人可兼完成两项任务其余三人每人完成一项。试确定总花费时间为最少的指派方案。人 任务 A B C D E甲 25 2

30、9 31 42 37乙 39 38 26 20 33丙 34 27 28 40 32丁 24 42 36 23 455.9 已知下列五人各种姿势的游泳成绩（各为50米）试问如何进行指派从中选拔一个参加200米混合泳的接力队使预期比赛成绩为最好。赵钱张王周仰 泳37.732.933.837.035.4蛙 泳43.433.142.234.741.8蝶 泳33.328.538.930.433.6自由泳29.226.429.628.531.15.10. 运筹学中著名的旅行商贩（货郎担）问题可以叙述如下：某旅行商贩从某一城市出发到其它几个城市去推销商品规定每个城市均须到达而且只到达一次然后回到原出发城市

31、。已知城市i和j之间的距离为dij问该商贩应选择一条什么样的线顺序旅行使总的旅程为最短。试对此问题建立整数规划模型。5.11. 有三个不同的产品要在三台机床上加工每个产品必须首先在机床1上加工然后依次在机床23上加工。在每台机床上加工三个产品的顺序应保持一样假定用tij表示在第j机床上加工第i个产品的时间问应如何安排使三个产品总的加工周期为最短。试建立此问题的整数规划模型。习题参考第一章 线性规划及单纯形法1.1（1）解：第一求可行解集合。令两个约束条件为等式得到两条直线在第一象限划出满足两个不等式的区域其交集就是可行集或称为可行域如图1-1所示交集为（1/2, 0）。第二绘制目标函数图形。将

32、目标函数的系数组成一个坐标点（64）过原点O作一条矢量指向点（64）矢量的长度不限矢量的斜率保持4比6再作一条与矢量垂直的直线这条直线就是目标函数图形目标函数图形的位置任意如果通过原点则目标函数值Z=0如图1-2所示。第三求最优解。图1-2的矢量方向是目标函数增加的方向或称梯度方向在求最小值时将目标函数图形沿梯度方向的反方向平行移动（在求最大值时将目标函数图形沿梯度方向平行移动）直到可行域的边界停止移动其交点对应的坐标就是最优解如图1-3所示。最优解x=（1/2, 0）,目标函数的最小值Z=3。（2）无可行解；求解方法与（1）类似（3）无界解；（4）无可行解；（5）无穷多最优解 z*=66（6

33、）唯一最优解 z*=92/3,x1=20/3,x2=3/81.2 （1）解：由题目可知其系数矩阵为因 线性独立故有 令非基变量 得 得到一个基可行解 。线性独立故有 令非基变量 得 得到一个基本解但非可行解 。同理可以求出得基本可行解 。得基本可行解 。得基本可行解 。得基本可行解 。得基本 非可行解 。得基本非可行解 。（1）、（2）如下表所示其中打三角符号的是基本可行解打星号的为最优解：x1 x2 x3 x4 x5 z x1 x2 x3 x4 x5 0 0 4 12 18 0 0 0 0 -3 -5 4 0 0 12 6 12 3 0 0 0 -56 0 -2 12 0 18 0 0 1

34、0 -3 4 3 0 6 0 27 -9/2 0 5/2 0 0 0 6 4 0 6 30 0 5/2 0 -3 0* 2 6 2 0 0 36 0 3/2 1 0 0 *4 6 0 0 -6 42 3 5/2 0 0 0 0 9 4 -6 0 45 0 0 5/2 9/2 0 1.3(1)解：单纯形法首先将问题化为标准型。加松弛变量x3x4得其次列出初始单纯形表计算最优值。CBXB10500bX1X2X3X40X3341090X452018j105000X3014/51-3/521/510X112/501/58/5j010-25X2115/14-3/143/210X100-1/72/71j0

35、0-5/14-25/14（表一）由单纯形表一得最优解为 法：（2）略1.4 (1) 解：大M法首先将数学模型化为标准形式式中x4x5为松弛变量x5可作为一个基变量第一、三约束分别加入人工变量x6 x7目标函数中加入-Mx6-Mx7一项得到大M单纯形法数学模型由单纯形表计算：CBXB45100-M-MbX1X2X3X4X5X6X7-MX6321-1010180X521001004-MX711-100015j4+4M5+3M1-M000-MX6-101-1-210105X221001004-MX7-10-100011j4-2M01-M-2M001X3-101-1-20100X22100104-MX

36、7-200-1-2111j5-2M001-M2-2M0表1.4-1.1在迭代过程中人工变量一旦出基后不会在进基所以当人工变量X6出基后对应第六列的系数可以不再计算以减少计算量。当用大M单纯形法计算得到最优解并且存在人工变量大于零时则表明原线性规划无可行解。两阶段单纯形法首先化标准形同大M法第一、三约束分别加入人工变量x6 x7后构造第一阶段问题用单纯形法求解得到第一阶段问题的计算表1.4-1.2CBXB0000011bX1X2X3X4X5X6X71X6321-1010180X5210010041X711-100015j-4-3010001X601/21-1-3/210120X111/2001/

37、20021X701/2-10-1/2013j0-1012001X6-101-1-210100X2210020041X7-10-10-1011j2001300表1.4-1.2在第一阶段的最优解中人工变量不为零则原问题无可行解。注：在第二阶段计算时初始表中的检验数不能引用第一阶段最优表的检验数必须换成原问题的检验数。(2) 无穷多最优解如X1（400）；X2（008）(3) 无界解 (4) 唯一最优解 X*（5/25/25/20）(5) 唯一最优解 X*（2433）(6) 唯一最优解 X*（1404）1.5（4）X*仍为最优解max zCX；（5）除C为常数向量外一般X*不再是该问题的最优解；（6

38、）最优解变为X*目标函数值不变。1.6（7）d0,c10, c20（8）d0,c10, c20,但c1c2中至少一个为零（9）d0或d0而c10且d/4=3/a2（10）c10,d/43/a2（11）c20,a10（12）x5为人工变量且c10, c201.7解：设xj表示第j年生产出来分配用于作战的战斗机数；yj为第j年已出来的驾驶员；（ajxj）为第j年用于驾驶员的战斗机数；zj为第j年用于驾驶员的战斗机总数。则模型为max z = nx1+(n-1)x2+2xn-1+xn s.t. zj=zj-1+(aj-xj)yj=yj-1+k(aj-xj)x1+x2+xjyjxj,yj,zj0 (j

39、=1,2, ,n)1.8 提示：设出每个管道上的实际流量则发点发出的流量等于收点收到的流量中间点则流入等于流出再考虑容量限制条件即可。目标函数为发出流量最大。设xij从点i到点j的流量max zx12x13st. x12x23x24x25x13x23x34x35x24x34x54x46x25x35x54x56 以上为流量平衡条件x12x13x46x56 始点收点x1210x136x234x245x253x345x358x4611x543x567xij0对所有ij1.9 提示：设每个区段上班的人数分别为x1x2x6即可1.10 解：设男生中挖坑、栽树、浇水的人数分别为x11 、x12 、x13女

40、生中挖坑、栽树、浇水的人数分别为x21 、x22 、x23 ,S为植树棵树。由题意模型为：max S20 x11+10 x21 s.t. x11 +x12 +x13 =30x21 +x22 +x23 =2020 x11+10 x21 =30 x12+20 x22=25 x13+15 x23Xij0 i=1,2；j=1,2,31.11 解：设各生产x1,x2,x3max z = 1.2 x1+1.175x2+0.7x3 s.t. 0.6x1+0.15x2 20000.2x1+0.25x2+0.5x325000.2x1+ 0.6x2+0.5x31200x1,x2,x301.12 解：设712月各月

41、初进货数量为xi件而各月售货数量为yi件i126S为总收入则问题的模型为：max S29y124y226y328y422y525y6（28x124x225x327x423x523x6）st. y1200x1500y2200x1y1x2500y3200x1y1x2y2x3500y4200x1y1x2y2x3y3x4500y5200x1y1x2y2x3y3x4y4x5500y2200x1y1x2y2x3y3x4y4x5y5x6500xi0yi0 i126 整数1.13解：用x1x2x3分别代表大豆、玉米、麦子的种植面积（hm2公顷）；x4x5分别代表奶牛和鸡的饲养数；x6x7分别代表秋冬和春夏季多

42、余的劳动力（人日）则有第二 章 对偶理论和灵敏度分析2.1 对偶问题为(1) (2) (3) (4) 2.2（1）因为对偶变量Y=CBB-1,第k个约束条件乘上（0）即B-1的k列将为变化前的1/由此对偶问题变化后的解（y1, y2, , yk,ym）=（y1, y2, , (1/)yk,ym）（2）与前类似yr= yi= yi（ir）（3）yi=yi（i=1,2, ,m）（4）yi（i=1,2, ,m）不变2.3 (1) 对偶问题为(2) 由互补松弛性 （ 分别为松弛变量和最优解）可得 从而可知又由对偶性质的最优性 可得四方程联立即可求得对偶问题的最优解：Y*（2210）2.4 解： 其对偶问题为min w=8y1+12y22y1+2y2 2 (1)2y