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

1、习 题 1 1 用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷最优解、 无界解还是无可行解。0 xx42x4x66x4x3x2xminz)a(21212121，0 x,x124x3x2x2x2x3xmaxz)b(212121218x310 x512010 x6xxxmaxz)c(2121210 x,x23x2x2x2x6x5xmaxz)d(21212121答案：(a)唯一解3*,)5.0,75.0(*zxt); (b) 无可行解 ; (c)唯一解16*,)6,10(*zxt); (d)无界解）2 用单纯形法求解下列线性规划问题。0 x,x82x5x94x3x5x10 xmaxz)

2、a(212121210 x,x5xx242x6x155xx2xmaxz)b(212121221答案：(a)唯一解5.17*,)5.1 , 1(*zxt)， 对偶问题5.17*,)786.1 ,357.0(*wyt; (b)唯一解5.8*,)5. 1, 5. 3(*zxt） ，5.8*,)5.0,25.0, 0(*wyt3 用大 m 法和两阶段法求解下列线性规划问题，并指出属于哪一类解。0 xxx0 x2x2x2x6xxx2xx2xmaxz)a(3,2,132313213210 x,x,x62x3x82x4xxx3x2xminz)b(32121321321答案：(a)无界解； (b)唯一解8*,

3、)0, 8. 1, 8. 0(*zxt)，对偶问题8*,)0, 1(*wyt4 已知线性规划问题的初始单纯形表（如表1-54 所示）和用单纯形法迭代后得到的表（如表 1-55 所示）如下，试求括弧中未知数al 的值。精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 1 页，共 10 页 - - - - - - - - -表 1-54 初始单纯形表b x1 x2 x3 x4 x5x4 6 (b) (c) (d) 1 0 x5 1 -1 3 (e) 0 1 cj-zj (a) -1 2 0 0 表 1-55 单纯形法迭代后的表b x1 x2 x3 x4 x

4、5x1 (f) (g) 2 -1 1/2 0 x5 4 (h) (i) 1 1/2 1 cj-zj 0 -7 (j) (k) (l) 表 1-55 基变量 x1列向量011p，所以 g=1,h=0 （2）初始表,jpb某步表jpbbb11,有已知表查出12/102/11b, 341612/102/141fffbb201112/102/10111bbpb5,42312/102/1221icicipb2,21112/102/11131ededpb（ 3）初始表主元行（-主元检验数 /主元）加到检验数行得下一步表的检验数行。表 1-54 第一行系数（-a/b）+表 1-54 检验数行 =表 1-54

5、 检验数行即：0,21,2,712lakjaa故：0,23, 5, 3lkja。精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 2 页，共 10 页 - - - - - - - - -5 某厂生产、三种产品，都分别经a、b 两道工序加工。设a 工序可分别在设备a1或 a2上完成，有b1、b2、b3三种设备可用于完成b 工序。已知产品可在a、b 任何一种设备上加工；产品可在任何规格的a 设备上加工，但完成b 工序时，只能在b1设备上加工； 产品只能在a2与 b2设备上加工。 加工单位产品所需工序时间及其他各项数据见下表 1-56，试安排最优生产计划，使

6、该厂获利最大。表 1-56 产品的有关数据表设备产品设备有效台时设备加工费（元 /小时）a1a2b1b2b35 7 6 4 7 10 9 812 116 000 10 000 4 000 7 000 4 000 0.05 0.03 0.06 0.11 0.05 原料费（元 /件）售价（元 /件）0.25 1.25 0.35 2.00 0.50 2.80 6 一家糖果商店出售三种不同品牌的果仁糖，每个品牌含有不同比例的杏仁、核桃仁、 胡桃仁。为了维护商店的质量信誉，每个品牌中所含有的果仁的最大、最小比例是必须满足的，如下表 1-57 所示：表 1-57 每个品牌中所含有的果仁的比例表品牌含量需求

7、每磅售价（美元）普通腰果仁不超过20% 胡桃仁不低于40% 核桃仁不超过25% 杏仁没有限制0.89 豪华腰果仁不超过35% 杏仁不低于40% 核桃仁、胡桃仁没有限制1.10 蓝带腰果仁含量位于30%50%之间杏仁不低于30% 核桃仁、胡桃仁没有限制1.80 表 1-58 列出了商店从供应商每周能够得到的每类果仁的最大数量和每磅的价格：表 1-58 每类果仁的最大数量和每磅的价表果仁类型每磅价格（美元）每周最大供应量（磅）杏仁0.45 2000 核桃仁0.55 4000 腰果仁0.70 5000 胡桃仁0.50 3000 精品学习资料 可选择p d f - - - - - - - - - -

8、- - - - 第 3 页，共 10 页 - - - - - - - - -商店希望确定每周购进杏仁、核桃仁、腰果仁、胡桃仁的数量，使周利润最大。建立数学模型，帮助该商店管理人员解决果仁混合的问题。7 写出下列线性规划问题的对偶问题。无约束321321321321321x0,x,x53x4xx33xx2x24x3xx4x2x2xminz)a()n, 1nj (x)nn, 1j (0 x)m, 1mi (bxa)mm, 1i (bxaxcmaxz)b(1j1j1in1jjij1in1jjijn1jjj无约束答案：（a）无约束321321321321321x0,x,x43x3y4y24yy3y2y

9、2yy5y3y2ymax（b）)m, 1i (v)n, 1i (0u)n,.,1nj (cvaua)nn, 1j (cvauavbubmin1i1i1jm1im1miiijiij1jm1im1miiijiijm1miiim1iii111111mm无约束精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 4 页，共 10 页 - - - - - - - - -8 已知线性规划问题：0 xxx1xx2x2xxxxxmaxz32132132121，试应用对偶理论证明上述线性规划问题最优解为无界。答案：显然t(0,0,0)x为该问题的可行解，其对偶问题为：0yy

10、0yy1yy12yyyy2min2121212121，显然第一个约束与变量非负要求矛盾，故对偶问题无可行解。由无界性该问题最优解为无界。9 已知线性规划问题：)4, 1j (0 x)4(9xxx)3(6xxx)2(6x2x) 1(8x3xxxx4x2xmaxzj321432214214321要求： （1）写出其对偶问题； （2）已知原问题最优解为x*=(2,2,4,0)t，试根据对偶理论求出对偶问题最优解。答案：对偶问题精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 5 页，共 10 页 - - - - - - - - -)4, 1j (0y(4)1

11、yy(3)1yy(2)4yyy3y(1)2y2yy9yy66y8yminj314343214214321设对偶问题的最优解为),(*4*3*2*1*yyyyy将 x*=(2,2,4,0)t代入原问题，约束（4）为严格不等式（即x*s1，x*s2，x*s3）0） ，由互补松弛性， y*4=0。又因为x*1=2,x*2=2,x*3 =4 都大于 0，由互补松弛性，对偶问题对应（1）-（3）约束为等式， （即 y*s1= y*s2 =y*s3=0）故有(3)1y(2)4yy3y(1)22yy*1*2*3321，解得 对偶问题的最优解为)0, 1 , 5/3,5/4(*yy。10 已知线性规划问题：0

12、 x,x,x42xx6xxxxx2xmaxz32121321321先用单纯形法求出最优解，再分析在下列条件单独变化的情况最优解的变化。（1）目标函数变为321x3x2xmaxz；（2）约束右端项由46变为43；（3）增添一个新的约束条件：22xx31。精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 6 页，共 10 页 - - - - - - - - -答案：最终表cj 2 -1 1 0 0 b cb xb x1 x2 x3 x4 x5 2 x10 x51 1 1 1 0 0 3 1 1 1 6 10 j0 -3 -1 -2 0 该问题的最优解tx)

13、10,0, 0,0,6(*，最优值1262* z对偶问题的最优解)2, 1 , 3,0,2(*y，最优值1226*（1）目标函数中非基变量2x的系数2c由 -1 变为 3 重新计算2x的检验数20131)02(322jbpcc最优解发生变化，将2x的检验数12，系数3c2代入最终表，用单纯形法求解之，见下表cj 2 3 1 0 0 b cb xb x1 x2 x3 x4 x5 2 x10 x51 1 1 1 0 0 3 1 1 1 6 10* j0 （1）-1 -2 0 2 x13 x21 0 2/3 2/3 -1/3 0 1 1/3 1/3 1/3 8/3 10/3 j0 0 -4/3 -7

14、/3 -1/3 该问题的最优解tx)0,0 ,0 ,3/10,3/8(*，最优值3463103382* z对偶问题的最优解) 3/4, 0,0, 3/1 , 3/7(*y,最优值346314376*（2）0373243313131321bb，故最优基不变精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 7 页，共 10 页 - - - - - - - - -最优解为tx)0 ,0, 0, 3/7 ,3/2(*，最优值325373322*z（3）最优解tx)10, 0,0 ,0 ,6(*不满足新加的约束将约束化为等式，选松弛变量作为基变量得-2x2xx6

15、31将其添加到最终表得过渡表，然后将第一行乘-1 加到第三行将基变量x1的系数列向量化为单位向量cj 2 -1 1 0 0 0 b cb xb x1 x2 x3 x4 x5 x6 2 x10 x5 0 x61 1 1 1 0 0 0 3 1 1 1 0 1 0 -2 0 0 1 6 10 -2 2 x10 x5 0 x61 1 1 1 0 0 0 3 1 1 1 0 0 -1 -3 -1 0 1 6 10 （-8）j0 -3 -1* -2 0 0 2 x10 x5 1 x31 2/3 0 2/3 0 1/3 0 8/3 0 2/3 1 1/3 0 1/3 1 1/3 0 -1/3 10/3 2

16、2/3 8/3 j0 -8/3 0 -5/3 0 -1/3 新的最优解tx)3/22,0, 3/8 ,0 , 3/10(*，最优值328383102*z11 用分支定界法求解下列整数规划问题：(1) ，且为整数，0 xx369x4x357x5x3x2xmaxz21212121(2) 且为整数,0 x,x305x6x165x2xxxmaxz2121212112 用隐枚举法求解下列0-1 规划问题：)5 , 1j (10 x35x3x6x11x83x4x-3x7x4x2xxx x3x2x5x2x3xmaxzj542154315432154321或xj=0 或 1，j = 1，2，3，4， 5 13

17、 某航运公司承担六个港口城市a、b、c、d、e、f 的四条固定航线的物资运输任务已知各条航线的起点、终点城市及每天航班数见表1-59。假定各条航线使用相同型号的船只，精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 8 页，共 10 页 - - - - - - - - -又各城市之间的航程天数见表1-60。又知每条船只每次装卸货物的时间各需1 天，则该航运公司至少应配备多少条船,才能满足所有航线的运货需求? 建立模型并用软件求解。表 1-59 各条航线的起点、终点城市及每天航班数表航线起点终点每天航班1 2 3 4 e b a d d c f b 3

18、2 1 1 表 1-60 各城市之间的航程天数表终点起点a b c d e f a b c d e f 0 1 2 14 7 7 1 0 3 13 8 8 2 3 0 15 5 5 14 13 15 0 17 20 7 8 5 17 0 3 7 8 5 20 3 0 14 设某公司有五个人可以完成五项工作，每人做每项工作的用时如表1-61 所示。每人仅做一项工作，每项工作仅一人做。如何安排是用时最少？建立数学模型并用软件求解表 1-61 每人完成任务的用时表单位：天工作人员a b c d e 人员甲12 7 9 7 9 人员乙8 9 6 6 6 人员丙7 17 12 14 9 人员丁15 14

19、 6 6 10 人员戊4 10 7 10 9 15 思考题（1）线性规划问题在数学模型的形式、可行域的组成和最优点的位置等方面与非线性规划问题有什么不同？（2）如何理解线性规划问题的求解其实就是可行域顶点的转换方法？（3）线性规划的基解、基可行解和最优解之间有什么关系？（4）在解得转换中，如何保证从一个基可行解转换得到的仍然是一个基可行解？（5）在解的转换中，如何保证目标函数的值不仅下降，而且下降得最多？（6）在单纯形算法中，如何选择主元？主元可以是负的吗？（7）线性规划问题的约束条件是等式约束时，如何通过建立辅助规划问题的一个初始基本可行解？（9） 简述对偶单纯形法的优点、适用条件和求解步骤。(10) 试从经济上解释对偶问题和对偶变量的含义。（11）分支定界法求解极大化问题时，任何一个可行解的目标函数是否都是该问题目标函数精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 9 页，共 10 页 - - - - - - - - -值的下界？16 案例练习题目 ：木材的储存和收购售出最优化问题问题背景 ：在实际的销售模型中，往往会碰到一类由于每个时期的需求和供给量不同，而需要囤积货物在后期高价出售的