运筹学习题集二

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

2、, x2> 0(4) max z =3x1 2x2st.x1 +x2< 12x1+ 2x2 >4x1, x2> 0(6) max z = 3x1 + 4x2st. -x1 + 2x2<8x1 + 2x2< 122x1+ x2<16x1, x2A 01.2. 在下列线性规划问题中找出所有基本解指出哪些是基本可行解并分别代入目标函数比较找出最优解。(1) max z =3x1 + 5x2st. x1 + x3=4=32x2+ x4=123x1+ 2x2+ x5 =18(2) min z =4x1+12x2+18x3st. x1 3x3x42x2+ 2x3

3、- x5 = 5xj >0(j=1,5)xj >0(j = 1,- -,5)1.3. 分别用法和单纯形法求解下列线性规划问题并对照指出单纯形法迭代的每一步相当于法可行域中的哪一个顶点。(1) max z = 10x1 + 5x2st. 3x1 + 4x2 w 95x1 + 2x2< 8x1, x2> 0(2) max z =100x1 + 200x2st.x1+ x2<500x1<2002x1 + 6x2< 1200x1, x2> 01.4. 分别用大M 法和两阶段法求解下列线性规划问题并指出问题的解属于哪一类：(1) max z =4x1 +

4、5x2+ x3st. 3x1+ 2x2+ x3>182x1 + x2 <4x1+ x2 x3=5xj >0(j = 1,2,3) max z = x1 + x2st.8x1+ 6x2 A 244x1+ 6x2 n 12 max z =2x1+ x2+ x3st. 4x1 + 2x2+2x3 A 42x1 + 4x2< 204x1 + 8x2+2x3W 16xj >0(j=1,2,3)(4) max z =x1 + 2x2+ 3x3 x4st.x1 + 2x2+3x3= 152x1+ x2+5x3=202x2 >4x1, x2> 0(5) max z =

5、 4x1 + 6x2st. 2x1+ 4x2 < 1803x1 + 2x2 < 150x1 + x2=57x2>22x1, x2> 0x1 + 2x2+ x3+ x4= 10xj >0 (j=1,4)(6) max z =5x1+ 3x2+6x3st. x1 + 2x2+ x3<182x1+ x2 + 3x3<16x1+ x2+ x3= 10x1, x2 A 0x3无约束6.5 线性规划问题max z= CXA注bX> 0如X*是该问题的最优解又 入0为某一常数分别讨论下列情况时最优解的变化：(1) 目标函数变为max z=入CX;(2)目标函数

6、变为maxz= （C+ 入）X;（3）目标函数变为max z= X约束条件变为AX=入b。6.6 下表中给出某求极大化问题的单纯形表问表中a1, a2, c1, c2, d为何值时以及表中变量属于哪一种类型时有：（1） 表中解为唯一最优解；（2） 表中解为无穷多最优解之一；（3） 表中解为退化的可行解；（4） 下一步迭代将以x1替换基变量x5；（5） 该线性规划问题具有无界解；（6） 该线性规划问题无可行解。x1x2x3x4x5x3d4a1100x4215010x53a23001cj zjc1c20001.7 战斗机是一种重要的作战工具但要使战斗机发挥作用必须有足够的驾驶员。因此生产出来的战斗

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

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

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

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

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

12、+ 4x4st. x1 2x2+3x3+ 4x4< 3x2+3x3+4x4> 52x1 3x2 7x3 -4x4 = 2=(2) max z =2x1+ x2+3x3+ x4st. x1x2x3 x42x1 x2+ 3x3=-4x1 x3+ x4>1(4) min z = - 5 x1 6x2 7x3st. -x1 + 5x2- 3x3 >15 5x1 6x2+ 10x3 <20x1 x2 x3= 5x1 A 0x4 w 0x2x3 无约束x1<0 x2> 0x3 无约束2.2 已知线性规划问题 max z= CXAX=bX0。分别说明发生下列情况时其

13、对偶问题的解的变化：(1)问题的第k个约束条件乘上常数入(入#0);(2)将第k个约束条件乘上常数入(入?0)后加到第个约束条件上；(3)目标函数改变为 max z=?<CX(?i#0);( 4)模型中全部x1 用 3 代换。2.3已知线性规划问题 min z= 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已知线性

14、规戈ij问题 min z= 2x1 + x2+ 5x3+6x4st. 2x1+x3+ x4< 8y12x1 + 2x2+ x3+ 2x4< 12y2xj>0 （j = 1,2,3,4）其对偶问题的最优解y1*=4； y2*=1 试根据对偶问题的性质求出原问题的最优解。2.5 考虑线性规划问题 max片2x1+ 4x2+ 3x3st. 3x1 + 4 x2+ 2x3< 602x1+ x2+2x3<40x1 + 3x2+2x3< 80xj>0 （j= 1,2,3）（ 1）写出其对偶问题（ 2）用单纯形法求解原问题列出每步迭代计算得到的原问题的解与互补的对偶

15、问题的解；（ 3）用对偶单纯形法求解其对偶问题并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解；（ 4）比较（2）和（3）计算结果。2.6 已知线性规划问题 max片10x1 + 5x2st.3x1 + 4x2< 95x1 + 2x2< 8 xj>0 (j = 1,2)用单纯形法求得最终表如下表所示：x1 x2 x3 x4 bx2 0 1x1 1 0 1 ?j=cj-Zj 0 0 试用灵敏度分析的方法分别判断：(1)目标函数系数cl或c2分别在什么范围内变动上述最优解不变；(2)约束条件右端项b1b2当一个保持不变时另一个在什么范围内变化上述最优基保持不变；(3)问

16、题的目标函数变为 max z =12x1+ 4x2时上述最优解的变化;( 4)约束条件右端项由变为时上述最优解的变化。2.7 线性规划问题如下：max z= - 5x1 + 5x2 + 13x3st. x1 + x2+3x3< 2012x1 + 4x2+ 10x3< 90xj>0 (j= 1,2,3)先用单纯形法求解然后分析下列各种条件下最优解分别有什么变化？ 1） 1）约束条件的右端常数由20 变为30； 2） 2）约束条件的右端常数由90 变为70； 3） 3）目标函数中x3 的系数由13 变为8； 4） x1的系数列向量由（一112） T变为（05） T; 5） 增加一

17、个约束条件：2x1 + 3x2+ 5x3 W 50; 6） 将原约束条件改变为：10x1 + 5x2+ 10x3< 100。2.8 用单纯形法求解某线性规划问题得到最终单纯形表如下：cj 基变量50 40 10 60 Sx1 x2 x3 x4a c 0 11 6b d 1 02 4?j=cj-Zj 0 0 e f g（1）给出abcdefg的值或表达式；（ 2）指出原问题是求目标函数的最大值还是最小值；（3）用a+?ab+?t#别彳弋替a和b仍然保持上表是最优单纯形表求？a?b 满足的范围。2.9 某文教用品用原材料白坯纸生产原稿纸、日记本和练习本三种产100 人每月白坯纸量为30000

18、 千克。已知工人的劳动生产率为：每人每月可生产原稿纸30 捆或日记本 30 打或练习本30 箱。 已知原材料消耗为：每捆原稿纸用白坯纸千克每打日记本用白坯纸千克每箱练习本用白坯纸千克。又知每生产一捆原稿纸可获利2 生产一打日记本获利3 生产一箱练习本获利1。试确定：（ 1）现有生产条件下获利最大的方案；（ 2）如白坯纸的数量不变当工人数不足时可招收临时工临时工工资支出为每人每月40 则该要不要招收临时工？如要的话招多少临时工最合适？2.10 某生产甲、乙两种产品需要 A、B两种原料生产消耗等参数如下表（表中的消耗系数为千克/件）。产品原料甲 乙 可用量（千克）原料成本（/千克）A 2 4 16

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

20、 4 6 184.2 由产地A1A2发向销地B1B2的单位费用如下表产地允许存贮销地允许缺货存贮和缺货的单位运费也列入表中。求最优调运方案使总费用最省。B1 B2 量 存贮费 /件A1 8 5 4003A2 6 9 3004需要量200350缺货费 /件 2 54.3 对如下表的运输问题：A B 量X 100（ 6） （ 4）100Y 30（ 5）50（ 8）80Z （ 2）60（ 7）60需要量130110240（1）若要总运费最少该方案是否为最优方案?（2）若产地Z的量改为100求最优方案。4.4 某利润最大的运输问题其单位利润如下表所示：B1 B2 B3 B4 量A1 （ 6）（ 7）A

21、2 （ 4）（ 5）A3 （ 2）（ 9）需要量5）（ 8）810）（ 8）97）（ 3）78 6 5 5 24(1)求最优运输方案该最优方案有何特征?当A1的量和B3的需求量各增加2时结果又怎样？4.5 某玩具公司分别生产三种新型玩具每月可量分别为1000、 2000、2000 件它们分别被送到甲、乙、丙三个百货商店销售。已知每月百货商店各类玩具预期销售量均为1500 件由于经营方面原因各商店销售不同玩具的盈利额不同,见下表。又知丙百货商店要求至少C 玩具1000 件而拒绝进A玩具。求满足上述条件下使总盈利额最大的销分配方案。甲乙丙可量A541000B16892000C12101120004

22、.6 目前城市大学能存贮200个文件在硬盘上100个文件在计算机存贮器上 300 个文件在磁带上。用户想存贮300 个字处理文件100 个源程序文件100 个数据文件。每月一个典型的字处理文件被访问8 次一个典型的源程序文件被访问4 次一个典型的数据文件被访问2 次。 当某文件被访问时重新找到该文件所需的时间取决于文件类型和存贮介质如下表。时间（分钟）处理文件源程序文件数据文件硬盘544存贮器211磁带1086如果目标是极小化每月用户访问所需文件所花的时间请构造一个运输问题的模型来决定文件应该怎么存放并求解。4.7 已知下列五名运动员各种姿势的游泳成绩（各为 50米） 如表 5-2：试用运输问

23、题的方法来决定如何从中选拔一个参加200 混合泳的接力队使预期比赛成绩为最好。赵钱张王周仰泳37.732.933.837.035.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.2 26.4 29.6 28.5 31.14.8 求总运费最小的运输问题其中某一步的运输图如下表。B1 B2 B3 量A1 3（ 3）（ 5）（ 7）3A2 2（ 4）4（ 2）（ 4）6A3 （5）1 （6） 5（3）d需要量abc e（1）写出a,b,c,d,e的值并求出最优运输方案；（2）A3到B1的单位运费满足什么条件时表中运输方案为最优方案。3.9 某一实

24、际的运输问题可以叙述如下：有 n 个地区需要某种物资需要量分别为bj （j = 1,n）。这些物资均由某公司分设在 m个地区的 工各工的产量分别为ai （i=1,m）已知从i地区的工至第j个需求 地区的单位物资的运价为 cij又=试阐述其对偶问题并解释对偶变量 的经济意义。3.10 . 为确保飞行安全飞机上的发动机每半年必须强迫更换进行大修。某维修估计某种型号战斗机从下一个半年算起的今后三年内每半年发动机的更换需要量分别为：1007080120150140。 更换发动机时可以换上新的也可以用经过大修的旧的发动机。已知每台新发动机的购置费为 10 万而旧发动机的维修有两种方式：快修每台2 万半年

25、交货（即本期拆下来送修的下批即可用上）；慢修每台1 万但需一年交货（即本期拆下来送修的需下下批才能用上）。设该新接受该项发动机更换维修任务又知这种型号战斗机三年后将退役退役后这种发动机将报废。问在今后三年的每半年内该为满足维修需要各新购、 送去快修和慢修的发动机数各是多少使总的维修费用为最省？（将此问题归结为运输问题只列出产销平衡表与单位运价表不求数值解。 ）3.11 甲、乙两个煤矿分别生产煤 500万吨A、B、C三个电发电需要各电用量分别为300、 300、 400 万吨。已知煤矿之间、煤矿与电之间以及各电之间相互距离（单位：公里）如下列三个表所示。又煤可以直接运达也可经转运抵达,试确定从煤

26、矿到各电间煤的最优调运方案（最小总吨公里数）。从到甲乙从到A B C 从到 A0120150 120 80 A 070100100060 160 40 B 500 120C 100150 0习题四4.1分别用法和单纯形法求解下述目标规划问题(1) min z = 1 ( + ) + 2st. x1+ x2+ d 1 d+1 = 1 0.5x1+ x2+ d-2-d + 2 = 23x1 + 3x2+ d-3- d + 3=50x1x2>0; d-id + i>0 (i =123) min z =1 (2 +3 ) +2 +3st. x1+ x2+d1d+1 = 10x1+d-2-d

27、 + 2 =45x1 + 3x2+d-3-d + 3 =56x1+ x2+d 4d + 4 = 12x1x2>0; d-id + i >0 (i =1 4)4.2 考虑下述目标规划问题min z =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=60 x1x2>0; d-id + i >0 (i =1 4)(1)求满意解；（ 2）当第二个约束右端项由35 改为 75 时求解的变化；（3）若增加一个新

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

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

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

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

32、 max z =7x1+9x2st. -x1 + 3 x2 <67x1 + x2 <35x1x2> 0且为整数(2) min z =4x1+5x2st. 3x1+ 2x2 >7x1 + 4x2>53x1+ x2>2x1, x2> 0且为整数5.5 用隐枚举法求解0 1 整数规划问题max z = 3x1+ 2x2 5x3 2x4+ 3x5st. x1+ x2 + x3+2x4+ x5< 47x1+3x34x4+ 3x5< 811x1 6x2+3x4 3x5 > 3xj =0 或 1 (j=1 5)5.6 请用解01 整数规划的隐枚举法

33、求解下面的两维0 1 背包问题：max f = 2x1+2x2+3x3s.t. x1+2x2+2x3C 42x1+x2+3x3C 5xj=0 或 1j=1,2,35.7 用匈牙利法求解如下效率矩阵的指派问题79 10 1213 12 16 1715 16 14 1511 12 15 165.8 分配甲、乙、丙、丁四人去完成五项任务。每人完成各项任务时间如下表所示。由于任务数多于人数故规定其中有一个人可兼完成两项任务其余三人每人完成一项。试确定总花费时间为最少的指派方案。人任务A B C D E甲252931乙3938262033丙3427284032丁244236234542375.9 已知下

34、列五人各种姿势的游泳成绩（各为50 米）试问如何进行指派从中选拔一个参加200 米混合泳的接力队使预期比赛成绩为最好。赵钱张王周仰泳37.732.933.837.035.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.2 26.4 29.6 28.5 31.15.10 . 运筹学中著名的旅行商贩（货郎担）问题可以叙述如下：某旅行商贩从某一城市出发到其它几个城市去推销商品规定每个城市均须到达而且只到达一次然后回到原出发城市。已知城市i 和 j 之间的距离为 dij 问该商贩应选择一条什么样的线顺序旅行使总的旅程为最短。试对此问题建立整数规划模

35、型。5.11 . 有三个不同的产品要在三台机床上加工每个产品必须首先在机床 1 上加工然后依次在机床23 上加工。在每台机床上加工三个产品的顺序应保持一样假定用tij 表示在第j 机床上加工第i 个产品的时间问应如何安排使三个产品总的加工周期为最短。试建立此问题的整数规划模型。习题参考第一章线性规划及单纯形法1.1（ 1）解：第一求可行解集合。令两个约束条件为等式得到两条直线在第一象限1-1划出满足两个不等式的区域其交集就是可行集或称为可行域如图所示交集为（1/2, 0） 。第二绘制目标函数图形。将目标函数的系数组成一个坐标点（64）过原点 O 作一条矢量指向点（64）矢量的长度不限矢量的斜率

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

37、）解：由题目可知其系数矩阵为因线性独立故有令非基变量得一得到一个基可行解。线性独立故有令非基变量得一得到一个基本解但非可行解。同理可以求出得基本可行解。得基本可行解。得基本可行解。得基本可行解。得基本非可行解。得基本非可行解。1） 、 （ 2） 如下表所示其中打三角符号的是基本可行解打星号的为最x5zx1x2121800126123018006027-9/2x3 x4 x500-3 -5000 -510 -305/200优解：x1x2x3x4 004 40060-212 4304600-64235/2000094-6045005/29/201.3305/2-3*363/2(1)解：单纯形法首先

38、将问题化为标准型。加松弛变量加松弛变量x3x4 得其次列出初始单纯形表计算最优值。CB XB 10 5X1 X2 X3 X40 X3 30 X4 510 50 X3 014/5-3/521/510 X12/5 01/5 8/5-25 X25/14 -3/14 3/210 X1-1/72/7 1-5/14 -25/14(表一)由单纯形表一得最优解为 法：( 2)略1.4(1) 解：大 M 法首先将数学模型化为标准形式式中x4x5为松弛变量x5可作为一个基变量第一、三约束分别加入人工变量 x6 x7 目标函数中加入-Mx6-Mx7 一项得到大M 单纯形法数学模型由单纯形表计算:CB XB 4 5

39、1 0 0 -M -M bX1 X2 X3 X4- M X6 3 2 10 X5 2 1 0- M X7 1 1 -1(rj4+4M 5+3M- M X6 -1 0 15 X2 2 1 0- M X7 -1 0 -1o 4 4-2M 0 11 X3 -1 0 10 X2 2 1 0-M X7 -2 0 0(T j 5-2M 0 0表 1.4-1.1X5 X6 X7-1 0 10 1 00 0 01 -M 0- 1 -2 10 1 00 0 0- M -2M- 1 -20 1- 1 -20 180 41 50 00 100 41 10 00 100 41 111-M2-2M0在迭代过程中人工变量

40、一旦出基后不会在进基所以当人工变量X6 出基后对应第六列的系数可以不再计算以减少计算量。当用大 M 单纯形法计算得到最优解并且存在人工变量大于零时则表明原线性规划无可行解。两阶段单纯形法首先化标准形同大M 法第一、 三约束分别加入人工变量x6 x7 后构造第一阶段问题用单纯形法求解得到第一阶段问题的计算表1.4-1.2CB XB 0 0X1X2 X3 X4X5 X6 X7X6 3-118X5 2X7 1-1-4 -31 X6 01/2 1-1-3/20 120 X1 11/2 01/2 01 X7 01/2 -1-1/20 -11 X6 -1-1-2100 X2 21 X7 -1-1-1表 1

41、.4-1.2在第一阶段的最优解中人工变量不为零则原问题无可行解。注： 在第二阶段计算时初始表中的检验数不能引用第一阶段最优表的 检验数必须换成原问题的检验数。无穷多最优解如 X1= (400); X2= (008)(3) 无界解(4)唯一最优解 X*= (5/25/25/20 )唯一最优解X*= (2433)(6)唯一最优解 X*= (140 4)1.5(4) X*仍为最优解max z=入CX;(5)除C为常数向量外一般X*不再是该问题的最优解；(6)最优解变为入X*目标函数值不变。1.6(7) d>0,c1<0, c2c 0(8) d>0,c1<0, c2< 0

42、,但 c1c2 中至少一个为零(9) d = 0或 d0 而 c10且 d/4=3/a2(10) 10)c10,d/43/a2(11) c20,a1<0(12) x5为人工变量且c1<0, c2< 01.7解：设 xj 表示第 j 年生产出来分配用于作战的战斗机数；yj 为第 j 年已出来的驾驶员；(aj xj)为第j年用于驾驶员的战斗机数；zj为第 j年用于驾驶员的战斗机总数。则模型为max z = 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

43、,n)1.8提示：设出每个管道上的实际流量则发点发出的流量等于收点收到的 流量中间点则流入等于流出再考虑容量限制条件即可。目标函数为发出流量最大。设刈=从点i到点j的流量max z= 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>

44、; 0对所有ij1.9提示：设每个区段上班的人数分别为 x1x2x6即可1.10解：设男生中挖坑、栽树、浇水的人数分别为x11 、 x12 、 x13 女生中挖坑、栽树、浇水的人数分别为x21、x22、x23 ,S为植树棵树。由题意模型为：max S= 20 x11+10 x21s.t. x11 +x12 +x13 =30x21 +x22 +x23 =2020 x11+10 x21 =30 x12+20 x22=25 x13+15 x23Xij>0 i=1,2; j=1,2,31.11解：设各生产x1,x2,x3max z = 1.2 x1+1.175x2+0.7x3s.t. 0.6x1

45、+0.15x2<20000.2x1+0.25x2+0.5x3C 25000.2x1+ 0.6x2+0.5x3C 1200x1,x2,x3> 01.12解：设712月各月初进货数量为xi件而各月售货数量为yi件i=12一-6s为总收入则问题的模型为：max S= 29y1 + 24y2+ 26y3+ 28y4+ 22y5+ 25y6- (28x1 + 24x2+ 25x3 27x4 23x5 23x6)st. y1<200+x1<500y2<200 + x1-y1+ x2< 500y3 w 200 + x1 y1 + x2y2 + x3W 500y4W200

46、+ x1 y1+x2y2 + x3 y3 + x4<500y5<200 + x1-y1+x2-y2 + x3-y3 + x4-y4+x5< 500y2<200 + x1-y1+x2-y2 + x3-y3 + x4-y4+ x5 y5+ x6< 500xi>0yi>0 i=12-6 整数1.13解：用 x1x2x3 分别代表大豆、玉米、麦子的种植面积（hm2 公顷） ；x4x5 分别代表奶牛和鸡的饲养数；x6x7 分别代表秋冬和春夏季多余的劳动力（人日）则有第二章对偶理论和灵敏度分析2.1 对偶问题为(1)(2)(3) (4)2.2(1)因为对偶变量Y=

47、CBB-mk个约束条件乘上入(入#0)即B-1的k列将为变化前的"入由此对偶问题变化后的解(y'1, y 2,，yky' 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) 由互补松弛性(分别为松弛变量和最优解)可得从而可知又由对偶性质的最优性可得四方程联立即可求得对偶问题的最优解：Y*= (2210)2.4解：其对偶问题为min w=8y1+12y22y1+2y2 >

48、2(1)2y2 > 1(2)y1+y2 >5(3)y1, y2 >0将 y1*,y2* 代入约束条件得（1）与（2）为严格不等式由互补松弛性YsX*=0得x1*=x2*=0;又因为 y1, y2>0由互补松弛性 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 43）第二步（015002535）（100101）第三步（020/350/300

49、80/3 ） （ 5/62/3011/600 ）（ 3）对偶问题的解对偶问题互补的对偶问题的解第一步（000 2 4 3） （ 000604080）第二步（10010 1） （ 015002535）第三步（ （ 5/62/3011/600 ） （ 020/350/30080/3 ）（ 4）比较（2）和（3）计算结果发现对偶单纯形法实质上是将单纯形法应用于对偶问题的求解又对偶问题的对偶即原问题因此两者计算结果完全相同。2.6(1) 15/4 < c1< 50,4/5 < c2< 40/3 24/5<b1< 169/2 <b2< 15( 3) X*=

50、( 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 人最合适。2.10(1) s=13x1-(2x1*1.0+3x

51、1*2.0)+16x2-(4x2*1.0+2x2*2.0)=5x1+8x2max z=5s.t.2x1+4x2W 1603x1+2x2W 180x1,x2> 0X*= (50,15) max z=370( 2)影子：A ： 7/4B： 1/2(3) CBB-1-(-c3+11) >0CB=73/4=18.25(4) b' = (160+a,180),B-1 b =(3/8)a +15,50-a/4) >0得到-40W a <200a=200 增加利润350X1 X2 X3 X4X2 15+(3/8)a 0 1 3/8 -1/4X1 50- a/41 0 -1/41/2s -370- 7a/4 0 0 -7/4-1/2第三章运输问题3.1解：表 3.1-1B1 B2 B3 B4 量A1 (10)(6)(7)(12)4A2 (16)(10)(5)(9)9A3 (5) (4)(10)(10)5西北角法是优先从运价表的西北角的变量赋值当行或列分配完毕后 再在表中余下部分的西北角赋值以此类推直到右下角素分配完毕。表 3.1-1 西北角素是 x11, x11=min a1, bl = min 4, 5 = 4将 4填在 C11 的左侧表示A14 单位给B2。 同时将第