运筹学清华版习题答案(第五章)

第一部分线性规划的基本概念一、填空题1．线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。

2．图解法适用于含有两个变量的线性规划问题。

3．线性规划问题的可行解是指满足所有约束条件的解。

4．在线性规划问题的基本解中，所有的非基变量等于零。

5．在线性规划问题中，基可行解的非零分量所对应的列向量线性无关6．若线性规划问题有最优解，则最优解一定可以在可行域的顶点（极点）达到。

7．线性规划问题有可行解，则必有基可行解。

8．如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其基可行解_的集合中进行搜索即可得到最优解。

9．满足非负条件的基本解称为基本可行解。

10．在将线性规划问题的一般形式转化为标准形式时，引入的松驰数量在目标函数中的系数为零。

11．将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左_端加入松弛变量。

12．线性规划模型包括决策（可控）变量，约束条件，目标函数三个要素。

13．线性规划问题可分为目标函数求极大值和极小_值两类。

14．线性规划问题的标准形式中，约束条件取等式，目标函数求极大值，而所有变量必须非负。

15．线性规划问题的基可行解与可行域顶点的关系是顶点多于基可行解16．在用图解法求解线性规划问题时，如果取得极值的等值线与可行域的一段边界重合，则这段边界上的一切点都是最优解。

17．求解线性规划问题可能的结果有无解，有唯一最优解，有无穷多个最优解。

18.如果某个约束条件是“≤”情形，若化为标准形式，需要引入一松弛变量。

19.如果某个变量X j为自由变量，则应引进两个非负变量X j′,X j〞,同时令X j＝X j′－X j。

20.表达线性规划的简式中目标函数为max(min)Z=∑c ij x ij。

21..(2.1 P5))线性规划一般表达式中，a ij表示该元素位置在i行j列。

二、单选题1．如果一个线性规划问题有n个变量，m个约束方程(m<n)，系数矩阵的数为m，则基可行解的个数最为_C_。

清华第三版 运筹学 答案[键入文字] [键入文字] [键入文字]运筹学教程1. 某饲养场饲养动物出售,设每头动物每天至少需700g 蛋白质、30g 矿物质、100mg 维生素.现有五种饲料可供选用，各种饲料每kg 营养成分含量及单价如表1所示. 表1要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。

解:设总费用为Z.i=1,2,3,4,5代表5种饲料.i x 表示满足动物生长的营养需要时，第i 种饲料所需的数量.则有：⎪⎪⎩⎪⎪⎨⎧=≥≥++++≥++++≥++++++++=5,4,3,2,1,01008.022.05.0305.022.05.07008623..8.03.04.07.02.0min 54321543215432154321i x x x x x x x x x x x x x x x x t sx x x x x Z i2. 某医院护士值班班次、每班工作时间及各班所需护士数如表2所示。

每班护士值班开始时间向病房报道，试决定：（1） 若护士上班后连续工作8h ，该医院最少需要多少名护士，以满足轮班需要； （2） 若除22:00上班的护士连续工作8h 外(取消第6班），其他班次护士由医院排定上1～4班的其中两个班,则该医院又需要多少名护士满足轮班需要.表2解：（1）设i x 第i 班开始上班的人数,i=1,2,3,4，5，6⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥≥+≥+≥+≥+≥+≥++++++=且为整数6,5,4,3,2,1,0302050607060..min 655443322161654321i x x x x x x x x x x x x x t s x x x x x x Z i 解：（2）在题设情况下，可知第五班一定要30个人才能满足轮班需要。

则设设i x 第i 班开始上班的人数，i=1，2,3,4。

⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎨⎧=≥=+++=≥+++=+++=≥+++=+++=≥+++=+++=≥+++++++=4,3,2,1,1002150216021702,160..30min i44434241444443342241143433323133443333223113242322212244233222211214131211114413312211114321j i y x y y y y y x y x y x y x y y y y y y x y x y x y x y y y y y y x y x y x y x y y y y y y x y x y x y x y t s x x x x Z ij 变量，—是，，，第四班约束，，第三班约束，，第二班约束，第一班约束3. 要在长度为l 的一根圆钢上截取不同长度的零件毛坯,毛坯长度有n 种,分别为ja （j=1,2，…n ）。

《运筹学》第五章习题1．思考题（1）试述动态规划的“最优化原理”及它同动态规划基本方程之间的关系。

（2）动态规划的阶段如何划分？（3）试述用动态规划求解最短路问题的方法和步骤。

（4）试解释状态、决策、策略、最优策略、状态转移方程、指标函数、最优值函数、边界函数等概念。

（5）试述建立动态规划模型的基本方法。

（6）试述动态规划方法的基本思想、动态规划的基本方程的结构及正确写出动态规划基本方程的关键步骤。

2．判断下列说法是否正确（1）动态规划分为线性动态规划和非线性动态规划。

（2）动态规划只是用来解决和时间有关的问题。

（3）对于一个动态规划问题，应用顺推法和逆推法可能会得到不同的最优解。

（4）在用动态规划的解题时，定义状态时应保证各个阶段中所做的决策的相互独立性。

（5）在动态规划模型中，问题的阶段等于问题的子问题的数目。

（6）动态规划计算中的“维数障碍”，主要是由于问题中阶段数的急剧增加而引起的。

3．计算下图所示的从A 到E 的最短路问题4．计算下图所示的从A 到E 的最短路问题5．计算从A 到B、C、D 的最短路线。

已知各线段的长度如下图所示。

6．设某油田要向一炼油厂用管道供应油料，管道铺设途中要经过八个城镇，各城镇间的路程如下图所示，选择怎样的路线铺设，才使总路程最短？7．用动态规划求解下列各题（1）．222211295max x x x x z -+-=；⎩⎨⎧≥≤+0,52121x x x x ；（2）．33221max x x x z =⎩⎨⎧≥≤++0,,6321321x x x x x x ；8．某人外出旅游，需将3种物品装入背包，但背包重量有限制，总重量不超过10千克。

物品重量及其价值等数据见下表。

试问每种物品装多少件，使整个 背包的价值最大？913 千克。

物品重量及其价值的关系如表所示。

试问如何装这些物品，使整个背包 价值最大？10 量和相应单位价值如下表所示，应如何装载可使总价值最大？303011 底交货量，该厂的生产能力为每月600件，该厂仓库的存货能力为300件，又 每生产100件产品的费用为1000元。

第五章课后习题及解答3 -37穴1 =, $1.求下列矩阵的特征值和特征向量： （1）-3-31丿/\~37 A.所以, （■ 1I - A ）X = 0的基础解系为:(6,1-一 37)T .因此,A 的属于'i 的所有特征向量为:匕(6,1 -、37)丁(匕=0).2I所以，（’2l-A ）x=0的基础解系为:(6,1 . 37)T .因此,A 的属于■ 2的所有特征向量为:k 2(6,1 37)T (k 2 =0).'3 -1九-31-1 ⑵ 2 0 1 : 解： 打-A =-2 丸-1-12」-11h -2nn2亠=('-1)「-2)解:-2 3所以，特征值为：’1=1（单根）,'2=2（二重根）J 2 1 -1、5 0 0、入 1 — A =-21 -1T0 1-11 -b1°0 °」所以，（、| —A ）x =o 的基础解系为：（0,1,1）T .因此，A 的属于-1的所有特征向量为： 匕（0,1,1）丁你1 =0）.'-11 -1、1 -1'花 1 — A =-2 2 -1 T 0 0 1r 11><00 0」所以，（，2l -A ）x =：0的基础解系为：（1,1,0）T .因此，A 的属于-2的所有特征向量为：k 2（1,1,0）T （k 2 =0）.所以，特征值为:1=2 （二重根）*0 0 0 "人I —A= -1 1—1 TIT 1 -b所以，（\l -A ）X=0 的基础解系为：（1,1,0）T ,（-1,0,1）T .九-20 0 扎1—A=-1 丸-1 -1-11九一32 0 0' ⑶ 1 1 1 解:J -1 3」2)-210所以，（■1l -A ）x =0的基础解系为：（1,0,0,0）T .因此，A 的属于 > 的所有特征向量为： k 1（1,0,0,0）T （k^-0）所以，特征值为：'1 - 1 （三重根）'-3 -5 2、「10 1、入1 —A=2 3-1 T ■" T 0 1 -1J1 0」e 0 0」T所以,（‘1l _A ）x =0的基础解系为：（-1,1,1） •q 2 3 4^扎—1-2-3 -4 0 1 2 3解：XJ — A =0 &一1-2-3 0 0 1 2 0 0 九-1-2 1°0 0 bZ-1因此，A 的属于-i 的所有特征向量为：k i （1,1,0）T • k 2（-1,0,1）T （k i ,k 2为不全为零的任 意吊数）。

运筹学习题答案第一章（39页）1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。

（1）max 12z x x =+ 51x +102x ≤501x +2x ≥12x ≤4 1x ，2x ≥0（2）min z=1x +1.52x1x +32x ≥3 1x +2x ≥2 1x ，2x ≥0（3）max z=21x +22x1x -2x ≥-1-0.51x +2x ≤21x ，2x ≥0（4）max z=1x +2x1x -2x ≥031x -2x ≤-31x ，2x ≥0解： （1）（图略）有唯一可行解，max z=14 （2）（图略）有唯一可行解，min z=9/4 （3）（图略）无界解 （4）（图略）无可行解1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。

（1）min z=-31x +42x -23x +54x 41x -2x +23x -4x =-21x +2x +33x -4x ≤14-21x +32x -3x +24x ≥21x ，2x ，3x ≥0，4x 无约束（2）max kkz s p =11nmk ik ik i k z a x ===∑∑11(1,...,)mikk xi n =-=-=∑ik x ≥0 (i=1…n; k=1,…,m)（1）解：设z=-z ',4x =5x -6x , 5x ,6x ≥0 标准型：Max z '=31x -42x +23x -5(5x -6x )+07x +08x -M 9x -M 10x s. t .-41x +2x -23x +5x -6x +10x =21x +2x +33x -5x +6x +7x =14-21x +32x -3x +25x -26x -8x +9x =21x ,2x ,3x ,5x ,6x ,7x ,8x ,9x ,10x ≥0(2)解：加入人工变量1x ，2x ，3x ，…n x ，得： Max s=(1/k p )1ni =∑1mk =∑ik αik x -M 1x -M 2x -…..-M n xs.t.11mi ik k x x =+=∑ (i=1,2,3…,n)ik x ≥0, i x ≥0, (i=1,2,3…n; k=1,2….,m)M 是任意正整数1.3在下面的线性规划问题中找出满足约束条件的所有基解。

运筹学第五章作业题参考答案5．1 解：设在A j 处建Ｘj 幢住宅. 则数学模型为 Max z =∑=ni jx1⎪⎩⎪⎨⎧且为整数01≥≤≤∑=j jj ni jj x a x Ddx5.2 解：设每种毛坯截取Ｘj 根 则数学模型为 Max z =∑=ni jx1⎪⎩⎪⎨⎧≥≤∑=且为整数01jj j ni x l x a 5.4 解：设X i =⎩⎨⎧名队员不上场第名队员上场第i 0i 1数学模型为：Max Z =( 1.92X 1+1.92X 2+…+1.78X 8)/5⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==≤+≤++≥++=+∑=5051211818264187621或i i i X X X X X X X X X X X X5.6 用割平面法解下列整数规划 （1） Max Z = X 1 + X 2 s.t⎪⎩⎪⎨⎧≥≤+≤+且为整数、0X 205462212121X X X X X 解：将其化为标准型为 Max Z = X 1 + X 2 s.t ⎪⎩⎪⎨⎧≥=++=++且为整数0,20546221421321X X X X X X X X从表中第二行产生割平面的约束条件： -1/3 X 3 - 1/3 X 43/2-≤ 引入松弛变量X 5为： -1/3 X 3 – 1/3 X 4 + X 5=-2/3∴X *=(0, 4)T 或 ( 2, 2)T ， Z *=4(2) MinZ=51X +X 2⎪⎪⎩⎪⎪⎨⎧≥≥+≥+≥+且为整数0,8859321212121X X X X X X X X 解: 化为标准型为 max z ‘=-51X -X 2⎪⎪⎩⎪⎪⎨⎧≥-=+---=+---=+--0,,,,8859354321521421321X X X X X X X X X X X X X X因此，原问题的最优解为X=( 0, 9 ) T ，最优值Z * = 9 5.7用分支定界法解下列整数规划 （1） Max Z=2X 1+X 2⎪⎪⎩⎪⎪⎨⎧≥≤+≤+-≤+且为整数0,21260521212121X X X X X X X X解：用图解法求得该整数规划的松弛问题的最优解为 X 1=X 2=21/8 选择X 1=21/8进行分支B1: B2: Max Z =2X 1+X 2 Max Z =2X 1+X 2⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤≤+≤+-≤+0,2212605211212121X X X X X X X X X ⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥≤+≤+-≤+0,3212605211212121X X X X X X X X X 最优解为X 1=2 X 2=3 Z *=7； 最优解X 1=3 X 2= 3/2 Z *=15/2 > 7 选择X 2= 3/2进行分支B3 B4Max Z =2X 1+X 2 Max Z =2X 1+X 2⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥≤≥≤+≤+-≤+0,132126052121212121X X X X X X X X X X ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥≥≥≤+≤+-≤+0,223212605211212121X X X X X X X X X X 最优解为X 1=19/6 X 2=1 Z *=22/3 > 7； 无可行解 选择X 1=19/6 进行分支B5 B6 Max Z =2X 1+X 2⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥≤≤≥≤+≤+-≤+0,31321260521121212121X X X X X X X X X X X ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥≥≤≥≤+≤+-≤+0,41321260521121212121X X X X X X X X X X X 最优解为X 1=3 X 2=1 Z *= 7； B6无可行解综上：原整数规划最优解为 X *= ( 2 , 3)或 ( 3 , 1) Z *=7 5.8 解下列0~1型 整数规划： (2) Max Z =2X 1+X 2- X 3⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥-+≤-+≤+≤++10,44225423,3,2132132132321或X X X X X X X X X X X X X X 解：最优解为X *=(1 , 0 , 0 )T Z *= 25.11（1） 解：引入一个虚拟人A 5,使之成为标准的指派问题，则系数矩阵为C = ⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛0000071011151314129651214101178241110将各行元素减去本行的最小元素得C →⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛0000003486974105734060298 = C ˊ由于只有4个独立零元素，小于系数矩阵阶数n=5，所以将第二行，第三行，第四行都减去1，第一列和第五列加上1得C ˊ→⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛---00012375863014623160298→⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛1000102376963005623070299= C 〞C 〞中有5个独立零元素，则可确定指派问题的最优指派方案。