规划数学第三版课后习题答案习题

1、文档编码 : CS5Z9Z5L9Y9 HK5H1Q3X5I1 ZH5S3W8Q9J5习 题 1 1 用图解法求解以下线性规划问题,并指出问题具有唯独最优解、无穷最优解、 无界解仍是无可行解；a minz2x13x2bmaxz3x12x24x16x26T2x1x2224x12x243x14x212x1,x20 x1,x20c maxzx1x2dmaxz5x16x6x110 x21202x1x225x1102x13x223x28x1,x20答案：a唯独解X*0. 75 ,0 . 5 T,z *3; b 无可行解 ; c唯独解X* 10 ,6 ,z *16; d 无界解）2 用单纯形法求解以下线性规

2、划问题；amaxz10 x15x2b maxz2x1x25x2153x14x2096x12x2245x12x28x1x25x1,x2x1,x20答案：a唯独解X* 1,1. 5 T,z *z *17 .5,对偶问题Y*00 .357 1, .786 T,w *17 .5; b唯独解X*.3,5 .15T,8. 5）,Y*,0. 25 ,0. 5 T,w *8 .53 用大 M 法和两阶段法求解以下线性规划问题,并指出属于哪一类解；a maxz2x1x232x3bminz2x1x3x2x3x1x2x6x14x22x382x1x22x233x12x236x03x1,x2,0 x1,x2,x30答案

3、：a无界解； b唯独解X*.0,8 .1,80 T,z *8,对偶问题Y* ,1 0 T,w *84 已知线性规划问题的初始单纯形表（如表1-54 所示）和用单纯形法迭代后得到的表（如表 1-55 所示）如下,试求括弧中未知数 al 的值；表 1-54 初始单纯形表fx4 ,3x 5e2b x1 x 2 x 3 x4 6 b c d 1 0 x5 1 -1 3 e 0 1 cj-zj a -1 2 0 0 表 1-55 单纯形法迭代后的表x4 x 5b x1 x 2 x 3 x1 f g 2 -1 1/2 0 x5 4 h i 1 1/2 1 cj-zj 0 -7 j k l 表 1-55 基

4、变量 x 1 列向量p1,所以 g=1,h=0 01（2）初始表b,pj,某步表B1 ,B1pjf有已知表查出B11/201/21B1 bf1/20641/211451B1p 111/20bb201/2110B1p 221 /20c2c4 ,ii1 /213iB1p 311/20d1d2 ,11/21e1验数行；（ 3）初始表主元行 （-主元检验数 /主元）加到检验数行得下一步表的检表 1-54 第一行系数 （-a/b）+表 1-54 检验数行 =表 1-54 检验数行即：2 a 1 7 , a 2 j , k 1a , l 02故：a ,3 j ,5 k 3 , l 0；25 某厂生产、三种

5、产品,都分别经 A 、B 两道工序加工；设 A 工序可分别在设备A 1 或 A 2 上完成,有 B1、B 2、B3 三种设备可用于完成 B 工序；已知产品可在 A 、B 任何一种设备上加工；产品可在任何规格的 A 设备上加工,但完成 B 工序时,只能在 B1 设备上加工； 产品只能在 A 2 与 B2 设备上加工； 加工单位产品所需工序时间及其他各项数据见下表 1-56,试支配最优生产方案,使该厂获利最大；表 1-56 产品的有关数据表设备有效台时设备加工费设备产品（元 /小时）A 15 10 6 000 0.05 A 27 9 12 10 000 0.03 B16 84 000 0.06 1

6、17 000 B24 0.11 B37 4 000 0.05 原料费（元 /件）0.25 0.35 0.50 核桃仁、 胡桃售价（元 /件）1.25 2.00 2.80 6 一家糖果商店出售三种不同品牌的果仁糖,每个品牌含有不同比例的杏仁、仁；为了爱护商店的质量信誉,每个品牌中所含有的果仁的最大、最小比例是必需中意的,如下表 1-57 所示：表 1-57 每个品牌中所含有的果仁的比例表每磅售价（美元）品牌含量需求一般腰果仁不超过20% 0.89 胡桃仁不低于40% 核桃仁不超过25% 杏仁没有限制豪华腰果仁不超过35% 1.10 杏仁不低于40% 核桃仁、胡桃仁没有限制蓝带腰果仁含量位于30%

7、50%之间1.80 杏仁不低于30% 核桃仁、胡桃仁没有限制表 1-58 列出了商店从供应商每周能够得到的每类果仁的最大数量和每磅的价格：表 1-58 每类果仁的最大数量和每磅的价表每周最大供应量（磅）果仁类型每磅价格（美元）杏仁0.45 2022 核桃仁0.55 4000 腰果仁0.70 5000 胡桃仁0.50 3000 商店期望确定每周购进杏仁、核桃仁、腰果仁、胡桃仁的数量,使周利润最大；建立数学模 型,帮忙该商店治理人员解决果仁混合的问题；7 写出以下线性规划问题的对偶问题；aminz2x12x24x3,m 1,mx13x24x322x1x23x33x14x23x35x1,x20,x3

8、无约束bmaxzjncjxj1jnaijxjb ii,11jna ijxjbiim1,1m1xj0j,1,n 1nxj无约束jn1,1,n答案：（a）max2y 13y25y3y 12y2y323y 1y24y324y13y23x34x1,x20,x3无约束（b）minm1biuiimbivi,j,11,n1ni1m11m1aijuim1a ijvicji1im1m1aijuim1aijvicjjn1 ,.,ni1im1ui0,1,m 1nmivi无约束im 1,18 已知线性规划问题：maxzx1xx20 x32x122x12,x2x31x1,xx3试应用对偶理论证明上述线性规划问题最优解为

9、无界；答案：明显X0,0,0T为该问题的可行解,其对偶问题为：miny22 y1y210y 12y2y1y2y21y1y1,0明显第一个约束与变量非负要求冲突,故对偶问题无可行解；由无界性该问题最优解 为无界；9 已知线性规划问题：maxz2x14x2x3x4 1x13x2x482x1x2462x2x3x63 x1x2x394xj0j,1,4X*=2,2,4,0T,试依据对偶理论求出要求：（1）写出其对偶问题； （2）已知原问题最优解为对偶问题最优解；答案：对偶问题min8y16y26y39y4x*S1,x*S2,x*S3）0）,由互补松y12y2y4213y1y2y3y442y3y413y1

10、y314yj0j,1,4设对偶问题的最优解为Y* y 1,* y 2,* y 3,* y 4将 X*=2,2,4,0T 代入原问题,约束（4）为严格不等式（即弛性, y* 4=0；又由于 x*1 =2,x*2 =2,x*3 =4 都大于 0,由互补放松性,对偶问题对应（1）-（3）约束为等式, （即 y*S1= y*S2 =y*S3=0）y*2y*2112故有3y*y*y*42,123y*133解得 对偶问题的最优解为Y*4/5 ,y 3/,1,50 ；10 已知线性规划问题：maxz2,2x1x2x36x1x2x3x12x24x1,xx30先用单纯形法求出最优解,再分析在以下条件单独变化的情

11、形最优解的变化；（1）目标函数变为maxz2x13x22xx3；（2）约束右端项由6变为3；3244x1（3）增加一个新的约束条件：答案：最终表cj X B 2 -1 1 0 0 b 12 12CB x 1 x 2 x 3 x4 x5 2 x11 1 1 1 0 6 0 x50 3 1 1 1 10 j0 -3 -1 -2 0 该问题的最优解X* 6 ,0 ,00, 10 T,最优值*z26对偶问题的最优解Y* 2 ,0 ,1,32 ,最优值*62（1）目标函数中非基变量x 的系数c 由 -1 变为 3 重新运算x2的检验数22c2CBp320 110j33代入最终表,用单纯形法求最优解发生变

12、化,将x2的检验数21,系数c2解之,见下表cj 2 3 1 0 0 x5 b 431046CB X B x 1 x 2 x 3 x4 2 x11 1 1 1 0 6 0 x50 3 1 1 1 10* j0 （1）-1 -2 0 2 x 11 0 2/3 2/3 -1/3 8/3 3 x 20 1 1/3 1/3 1/3 10/3 j0 0 -4/3 -7/3 -1/3 该问题的最优解X* 8/3 , 10/3 0, 0,0 T,最优值*z28333对偶问题的最优解Y* 7/1,3 /,3 0 , ,04/3,最优值*67146333（2）B1b 21323 13 13 70,故最优基不变4

13、333最优解为X*2/3 7,/,3,00 0, T,最优值z *223725 3x1 的系数列向33（3）最优解X*6 0, 0,0 10 T不中意新加的约束将约束化为等式,选放松变量作为基变量得x12x3x6-2将其添加到最终表得过渡表,然后将第一行乘-1 加到第三行将基变量量化为单位向量cj 2 -1 0,31 22/0 0 0 b 828CB X B x 1 x 2 x 3 x4 x5 x 6 2 x11 1 1 1 0 0 6 0 x5 0 3 1 1 1 0 10 0 x61 0 -2 0 0 1 -2 2 x11 1 1 1 0 0 6 0 x5 0 3 1 1 1 0 10 0

14、 x60 -1 -3 -1 0 1 （-8）10/3 0 -3 -1* -2 0 0 j2 x11 2/3 0 2/3 0 1/3 0 x5 0 8/3 0 2/3 1 1/3 22/3 1 x30 1/3 1 1/3 0 -1/3 8/3 j0 -8/3 0 -5/3 0 -1/3 210 3新的最优解X*10/8,/,30 ,3 T,最优值z *3311 用分支定界法求解以下整数规划问题：maxz2x13x2j2x25x32 maxzx1x21 5x17x2352x15x2164x19x2366x15x230 x1,x20,且为整数2x4x1,x20 ,且为整数12 用隐枚举法求解以下0-

15、1 规划问题：3x5maxz3x1 x 1x2x32x4x547x13x3-4x43x5811x16x23x45x53x0或1j,15, xj=0 或 1,j = 1,2,3,4, 5 13 某航运公司承担六个港口城市A、B、C、D、E、F 的四条固定航线的物资运输任务已知各条航线的起点、终点城市及每天航班数见表 1-59；假定各条航线使用相同型号的船只,又各城市之间的航程天数见表 1-60；又知每条船只每次装卸货物的时间各需 1 天,就该航运公司至少应配备多少条船 ,才能中意全部航线的运货需求 . 建立模型并用软件求解；表 1-59 各条航线的起点、终点城市及每天航班数表航线 起点 终点 每

16、天航班1 E D 3 2 B C 2 3 A F 1 4 D B 1 表 1-60 各城市之间的航程天数表终点A B C D E F 起点A 0 1 2 14 7 7 B 1 0 3 13 8 8 C 2 3 0 15 5 5 D 14 13 15 0 17 20 E 7 8 5 17 0 3 F 7 8 5 20 3 0 14 设某公司有五个人可以完成五项工作,每人做每项工作的用时如表 1-61 所示；每人仅做一项工作,每项工作仅一人做；如何支配是用时最少？建立数学模型并用软件求解表 1-61 每人完成任务的用时表C D 单位：天工作A B E 人员人员甲12 7 9 7 9 人员乙8 9

17、6 6 6 人员丙7 17 12 14 9 人员丁15 14 6 6 10 人员戊4 10 7 10 9 15 摸索题（1）线性规划问题在数学模型的形式、可行域的组成和最优点的位置等方面与非线性规划问题有什么不同？（2）如何懂得线性规划问题的求解其实就是可行域顶点的转换方法？（3）线性规划的基解、基可行解和最优解之间有什么关系？（4）在解得转换中,如何保证从一个基可行解转换得到的仍然是一个基可行解？（5）在解的转换中,如何保证目标函数的值不仅下降,而且下降得最多？（6）在单纯形算法中,如何选择主元？主元可以是负的吗？（7）线性规划问题的约束条件是等式约束时,如何通过建立帮忙规划问题的一个初始基

18、本可行解？（9） 简述对偶单纯形法的优点、适用条件和求解步骤；10 试从经济上说明对偶问题和对偶变量的含义；（11）分支定界法求解极大化问题时,任何一个可行解的目标函数是否都是该问题目标函数值的下界？16 案例练习题目 ：木材的储存和收购售出最优化问题问题背景 ：在实际的销售模型中,往往会遇到一类由于每个时期的需求和供应量不同,而需要囤积货物在后期高价出售的问题,由于受到储存的成本,储存的空间, 每个时期的销量等各方面的限制,使这个问题显得愈加复杂；目标 ：要求就一个实际的木材的储存和收购售出的问题,简化该模型, 使用线性规划的方法对其进行求解,并对各个参数进行灵敏度分析,最终给出合理的方案；问题提出 ：江苏省某木材储运公司有一个特殊大的仓库以用来储备和出售木材,由于木材的每季度价格不同, 该公司方案在每季度初购入木材,依据实际的市场需求,一部分用于出售,另一部分就储备起来,等待以后出售；已知该公司的仓库的最大储备量为200 万立方米,储存费用为a+bu元/万立方米,其中a=7 万, b=10 万, u 为储备的时间（季