清华大学《运筹学教程》胡运权主编课后习题答案(第一章)PPT课件

1、1第一章习题解答第一章习题解答 1.1 用图解法求解下列线性规划问题。用图解法求解下列线性规划问题。并指出问题具有惟一最优解、无穷多最优解、并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。无界解还是无可行解。 0,423664.32min)1(21212121xxxxxxstxxZ0,124322.23max)2(21212121xxxxxxstxxZ85105120106.max)3(212121xxxxstxxZ0,23222.65max)4(21212121xxxxxxstxxZ2是是其其中中一一个个最最优优解解优优解解）蓝蓝色色线线段段上上的的点点都都是是最最无无穷穷多多最

2、最优优解解,51,56(0,423664.32min)1(2121212121 xxxxxxxxstxxZ该该问问题题无无可可行行解解 0,124322.23max)2(21212121xxxxxxstxxZ3166,1085105120106.max)3(21212121 ZxxxxxxstxxZ唯唯一一最最优优解解，该问题有无界解0,23222.65max)4(21212121xxxxxxstxxZ4 1.2 1.2 将下述线性规划问题化成标准形式。将下述线性规划问题化成标准形式。 ., 0,2321422245243min) 1 (43214321432143214321无约束xxxxx

3、xxxxxxxxxxxstxxxxZ无约束321321321321,0,0624322min)2(xxxxxxxxxstxxxZ5., 0,2321422245243min) 1 (43214321432143214321无约束xxxxxxxxxxxxxxxxstxxxxZ 0,232142222455243max, 0,6424132164241321542413214241321424132165424142414xxxxxxxxxxxxxxxxxxxxxxxstxxxxxwxxxxxxxZw，则则标标准准形形式式为为：，剩剩余余变变量量同同时时引引入入松松弛弛变变量量，其其中中解解：令令

4、6无约束321321321321,0,0624322min)2(xxxxxxxxxstxxxZ 0,6243322max432312114323121132312113231211xxxxxxxxxxxxxxstxxxxW，则则标标准准形形式式为为：同同时时引引入入松松弛弛变变量量解解：令令433231111,xxxxxxZW 7 1.3 1.3 对下述线性规划问题找出所有基解，对下述线性规划问题找出所有基解，指出哪些是基可行解，并确定最优解。指出哪些是基可行解，并确定最优解。 ）（6 , 1,0031024893631223max)1 (6153214321321jxxxxxxxxxxxst

5、xxxZj)4, 1( ,0322274322325min)2(432143214321jxxxxxxxxxstxxxxZj8）（6 , 1,0031024893631223max)1 (6153214321321jxxxxxxxxxxxstxxxZjx1x2x3x4x5x6是否基可行解Z(x1,x2,x3)061/3-7/6000否(x1,x2,x4)0100-700否(x1,x2,x5)03007/20是3(x1,x2,x6)7/4-400021/4否(x1,x3,x4)00-5/2800否(x1,x3,x5)001.5080是3(x1,x3,x6)10-0.5003否(x1,x4,x5)

6、000350是0(x1,x4,x6)5/400-2015/4否(x1,x5,x6)3/400029/4是9/4(x2,x3,x6)016/3-7/6000否(x2,x4,x6)0100-700否(x2,x5,x6)03007/20是3(x3,x4,x6)00-5/2800否(x3,x5,x6)003/2080是3(x4,x5,x6)000350是0所有基可行解中最优解为X=(0,3,0,0,3.5,0)T和X=(0,0,1.5,0,8,0)T10)4, 1( ,0322274322325min)2(432143214321jxxxxxxxxxstxxxxZjx1x2x3x4是否基可行解Z(x1

7、,x2)-411/200否(x1,x3)2/5011/50是43/5(x1,x4)-1/30011/6否(x2,x3)01/220是5(x2,x4)0-1/202否(x3,x4)0011是5所有基可行解中最优解为X=(0,1/2,2,0)T和X=(0,0,1,1)T11 1.4 分别用图解法和单纯形法求解下述分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。可行解对应图解法中可行域的哪一顶点。 0,825943.510max)1 (21212121xxxxxxstxxZ105000934100852

8、0110500jjzc jcBCBxb4x2x3x4x3x1x021/5014/51-3/5108/512/501/5010-2jjzc 1x3x53/2015/14-3/1410110-1/72/700-5/14-25/141x2xjjzc 0点A1点A2点所以最优解为X*=(1,3/2,0,0)T130,24261553.2max)2(21212121xxxxxxstxxZ l.5 上题上题(1)中，若目标函数变为中，若目标函数变为max Z = cx1 + dx2，讨论，讨论c,d的值如何变化，使该问题可行域的每个顶点依次使目标函数的值如何变化，使该问题可行域的每个顶点依次使目标函数达到

9、最优。达到最优。 最优值1)c0d0O点OA3线段A3点2)c=0d0OA1线段A3点3)c0d0A1点A1点A3点A2A3线段A2点A1A2线段A1点430 dc43 dc2543 dc25 dc25 dc17 式中，式中，1c13, 4c26, -1a113, 2a125, 8b112, 2a215, 4a226, 10b214,试确定目标函数最优值的下界和试确定目标函数最优值的下界和上界。上界。 0,.max21222212112121112211xxbxaxabxaxastxcxcZ l.6 考虑下述线性规划问题：考虑下述线性规划问题： 18 目标函数最优值的上界为：目标函数最优值的上

10、界为：2121 0,14421221.63max21212121xxxxxxstxxZ 解：上界对应的模型如下（解：上界对应的模型如下（c,b取大，取大，a取小）取小） 19 目标函数最优值（下界）为：目标函数最优值（下界）为：6.46.4 0,1065853.4max21212121xxxxxxstxxZ 解：下界对应的模型如下（解：下界对应的模型如下（ c,b取小，取小，a取大）取大）20 l.7 l.7 分别用单纯形法中的大分别用单纯形法中的大M M法和两阶法和两阶段法求解下列线性规划问题，并指出属哪段法求解下列线性规划问题，并指出属哪类类解。解。 。）（ 3 , 1, 00222623

11、max) 1 (3231321321jxxxxxxxxstxxxZj26 0,623824.32min)2(2121321321xxxxxxxstxxxZ见下表。31 ）（4 , 1, 042634334max)3(4213212121jxxxxxxxxxstxxZj方法一：大方法一：大M法法引入人工变量引入人工变量x6和和x7,线性规划问题变为：线性规划问题变为： ）（4 , 1, 042634334max42163215216521jxxxxxxxxxxxstMxMxxxZj00-M4M-17M-4010214000-1346-M100133-M-M00-1-4jjzc jcBCBxb6x

12、2x3x4x5x5x1x4x01013/246x0-7M/3+4/30-M5M/3+1/30-1/3105/3030-4/30-15/302-M1/3001/311-4jjzc 6x1x4x106/59/5003-Mi -M+8/501/5001110010-4/50-3/5106/5-13/501/5013/5-4-M00-1-4jjzc jcBCBxb2x2x3x4x5x1x1x4x-1/5-3/5-1316x-M-1/5-M+7/5-1/50001110010-1/53/50105/9-12/5-1/50012/5-4jjzc 2x1x3x0-1-M0-Mi 由于上表中所有检验数都小于等

13、于零由于上表中所有检验数都小于等于零(且非基变量检验数都且非基变量检验数都小于小于0)，因此已经得到唯一最优解，最优解为：，因此已经得到唯一最优解，最优解为： TX0 , 0 , 0 , 1 , 5/9 ,52* 方法二：两阶段法方法二：两阶段法第一阶段：第一阶段： ）（4 , 1, 04263433421632152165jxxxxxxxxxxxstxxmimWj00-147010214000-1346-1100133-1-10000jjzc jcBCBxb6x2x3x4x5x5x1x4x01013/246x0-7/30-15/30-1/3105/3030-4/30-15/302-11/30

14、01/3110jjzc 6x1x4x106/59/5003-1i -100001110010-4/50-3/5106/503/501/5013/50-M0000jjzc jcBCBxb2x2x3x4x5x1x1x4x-1/5-3/5-16x-1-Mi 该模型最优解为该模型最优解为X=（3/5，6/5，0，1，0，0）T，其基变量不含人工变量，说明原问题的一个基可行解为其基变量不含人工变量，说明原问题的一个基可行解为X=（ 3/5，6/5，0，1 ）T，转入第二阶段。，转入第二阶段。01/5001100100-3/5106/5-101/5013/5-400-1-4jjzc jcBCBxb2x2x

15、3x4x1x1x4x3-1/50001100103/50105/9-1-1/50012/5-4jjzc 2x1x3xi 由于上表中所有检验数都小于等于零由于上表中所有检验数都小于等于零(且非基变量检验数都且非基变量检验数都小于小于0)，因此已经得到唯一最优解，最优解为：，因此已经得到唯一最优解，最优解为： TX0 , 1 , 5/9 ,52* 139 ）（3 , 1, 052151565935121510max)4(321321321321jxxxxxxxxxxstxxxZj43 1.8 1.8 已知某线性规划问题的初始单纯形已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到下面表格，试求

16、括表和用单纯形法迭代后得到下面表格，试求括弧中未知数弧中未知数a a l值。值。 项 目X1X2X3X4X5X46(b)(c)(d)10X51-13(e)01CjZja-1200X1(f)(g)2-11/20X54(h)(i)1 1/21CjZj0-7(j)(k)(l) b=2, c=4, d= -2, g=1, h=0, f=3, i=5, e=2, l=0, -7=-1-(c/b)*a -7=-1-2a a=3 j=2-(d/b)*a j=2+3=5 k=-(1/b)*a k=-3/2 45 1.9 若若X(1)、X(2)均为某线性规划问题的均为某线性规划问题的最优解，证明在这两点连线上的

17、所有点也是最优解，证明在这两点连线上的所有点也是该问题的最优解。该问题的最优解。 连连线线上上的的点点和和表表示示)2()1()2()1()10()1(XXaXaaXX 的的最最优优解解是是问问题题：和和证证明明：设设 0max)2()1(XbAXCXZXX是是问问题题的的可可行行解解因因此此 XbbababAXaAXaAXXaAAaXAX )2()2()1()2()1()1(是问题的最优解是问题的最优解因此因此又因为又因为XCXCXaCXCaXXaCCaXCX)2()2()2()1()2()1()1( 47 1.10 1.10 线性规划问题线性规划问题max Zmax ZCX,AXCX,AX

18、b b，X0X0，设，设X X0 0为问题的最优解。若目标函数中用为问题的最优解。若目标函数中用C C* *代替代替C C后，问题后，问题的最优解变为的最优解变为X X* *，求证，求证(C(C* *-C)(X-C)(X* *-X-X0 0)0)010 max为为问问题题称称问问题题 XbAXCXZ20 max*为为问问题题称称问问题题 XbAXXCZ证证明明：的可行解的可行解一定是问题一定是问题的最优解，则的最优解，则是问题是问题12*X*X*的可行解的可行解一定是问题一定是问题的最优解，则的最优解，则是问题是问题2100XX; 011*0*0 CXCXXX故有：故有：的可行解的可行解是问题

19、是问题的最优解，的最优解，是问题是问题0)(*00*0* CXCXXCXCXXCC因此：因此：; 0220*0* XCXCXX故有：故有：的可行解的可行解是问题是问题的最优解，的最优解，是问题是问题49 1.11 1.11 考虑线性规划问题考虑线性规划问题0,)(75232)(24.42min432143214214321xxxxiixxxxixxxstxxxxZ 模型中模型中，为参数，要求：为参数，要求： (1)(1)组成两个新的约束组成两个新的约束(i)(i)( (i)+(iii)+(ii) )，(ii)(ii)(ii)(ii)一一2(i)2(i)，根据，根据(i)(i)，(ii)(ii)

20、以以x x1 1,x,x2 2为基变量，列出为基变量，列出初始单纯形表；初始单纯形表；50 33)(431 xxxiCja21-4CBxBbx1x2x3x4ax13+3011-12x21- 10-10j003-aa-4 1)(32xxii解解:51 (2)(2)在表中，假定在表中，假定0 0，则，则为何值时，为何值时，x x1 1, x, x2 2为为问题的最优基问题的最优基变量变量； 解：解： 如果如果=0，则当3-a0且 a-4 0时，即3a 4时，x x1 1, x, x2 2为问题的最优基为问题的最优基变量变量； (3)(3)在表中，假定在表中，假定3 3，则，则为何值时，为何值时，x

21、 x1 1, x, x2 2为为问题的最优基。问题的最优基。 解：解： 如果如果a=3，则当3+3 0 且1- 0时，即时，即 -1 1时，x x1 1, x, x2 2为问题的最优基为问题的最优基变量。变量。52 1.12 1.12 线性规划问题线性规划问题max Zmax ZCXCX，AXAXb b，X0X0，如，如X X* *是该问题的最优解，又是该问题的最优解，又0为某一为某一常数，分别讨论下列情况时最优解的变化。常数，分别讨论下列情况时最优解的变化。 (1)(1)目标函数变为目标函数变为max Zmax ZCXCX； (2)(2)目标函数变为目标函数变为max Zmax Z( (C+

22、C+)X)X； (3)(3)目标函数变为目标函数变为max Zmax ZC/C/*X X，约束条，约束条件变为件变为AXAXb b。 解解:(1)最优解不变最优解不变; (2)C为常数时最优解不变，否则可能发生变化。为常数时最优解不变，否则可能发生变化。 (3)最优解变为最优解变为: X* 。53 1.13 1.13 某饲养场饲养动物出售，设每头某饲养场饲养动物出售，设每头动物每天至少需动物每天至少需700g700g蛋白质、蛋白质、30g30g矿物质、矿物质、100mg100mg维生素。现有五种饲料可供选用，各种维生素。现有五种饲料可供选用，各种饲料每饲料每kgkg营养成分含量及单价如营养成分

23、含量及单价如下下表所示。表所示。饲料饲料 蛋白质蛋白质(g)(g)矿物质矿物质(g)(g)维生素维生素(mg)(mg) 价格（元价格（元/kg/kg）1310.50.2220.51.00.7310.20.20.446220.35180.50.80.854 要求确定既满足动物生长的营养需要，要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。又使费用最省的选用饲料的方案。( (建立这个建立这个问题的线性规划模型，不求解问题的线性规划模型，不求解) ) 5 , 4 , 3 , 2 , 1, 01008 . 022 . 05 . 0305 . 022 . 05 . 0700186238

24、. 03 . 04 . 07 . 02 . 0min5 , 4 , 3 , 2 , 1),(54321543215432154321ixxxxxxxxxxxxxxxxxxxxxZikgixii单单位位：种种饲饲料料数数量量表表示示第第解解：设设55 1.14 1.14 某医院护士值班班次、每班工作某医院护士值班班次、每班工作时间及各班所需护士数如时间及各班所需护士数如下页下页表表格格所示。所示。班次班次工作时间工作时间所需护士数所需护士数（人）（人）1 16:00 6:00 10:0010:0060602 210:0010:00 14:0014:0070703 314:0014:00 18:0

25、018:0060604 418:0018:00 22:0022:0050505 522:0022:00 2:002:0020206 62:00 2:00 6:006:00303056 (1)(1)若护士上班后连续工作若护士上班后连续工作8h8h，该医院最，该医院最少需多少名护士，以满足轮班需要；少需多少名护士，以满足轮班需要； 且且为为整整数数，班班开开始始上上班班的的护护士士人人数数表表示示第第设设)6 , 5 , 4 , 3 , 2 , 1(0302050607060min65 , 4 , 3 , 2 , 1,655443322161654321 ixxxxxxxxxxxxxxxxxxxZ

26、iixii解：解： 57 (2)(2)若除若除2222：0000上班的护士连续工作上班的护士连续工作8h8h外外( (取消第取消第6 6班班) )，其他班次护士由医院排定上，其他班次护士由医院排定上1-41-4班的其中两个班，班的其中两个班，则该医院又需多少名护士满足轮班需要。则该医院又需多少名护士满足轮班需要。 解解: 4 , 3 , 2 , 1,10, , 0302050607060min54 , 3 , 2 , 1,5534241434231324231214131253424231413125jiyxxxxxxxxxxxxxxxxxxxxxxZxijiixijiij变变量量是是班班上上

27、班班的的护护士士人人数数；表表示示第第班班的的护护士士人人数数班班开开始始上上班班且且上上第第表表示示第第设设58 1.15 1.15 艘货轮分前、中、后三个舱位，艘货轮分前、中、后三个舱位，它们的容积与最大允许载重量见后面的表格。它们的容积与最大允许载重量见后面的表格。现有现有3 3种货物待运，已知有关数据列于后面的种货物待运，已知有关数据列于后面的表格。表格。 又为了航运安全，前、中、后舱的实际载又为了航运安全，前、中、后舱的实际载重量大体保持各舱最大允许载重量的比例关系。重量大体保持各舱最大允许载重量的比例关系。具体要求：前、后舱分别与中舱之间载重量比具体要求：前、后舱分别与中舱之间载重

28、量比例的偏差不超过例的偏差不超过1515，前、后舱之间不超过，前、后舱之间不超过1010。问该货轮应装载。问该货轮应装载A A，B B，C C各多少件运费收各多少件运费收入才最大入才最大? ?试建立这个问题的线性规划模型。试建立这个问题的线性规划模型。59商品商品数量数量（件）（件）每件体积每件体积(m(m3 3/ /件件) )每件重量每件重量(t/(t/件件) )运价运价（元（元/ /件）件）A A60060010108 810001000B B100010005 56 6700700C C8008007 75 5600600项目项目前舱前舱中舱中舱后舱后舱最大允许载重量（最大允许载重量（t

29、 t）200020003000300015001500容积（容积（m m3 3）400040005400540015001500)(600)(700)(1000max333231232221131211xxxxxxxxxZ 解：设解：设x xijij表示第表示第i i种商品在第种商品在第j j舱的数量。舱的数量。60 3/4*9 . 0)568/()568(3/4*1 . 1)568/()568(2/1*95. 0)568/()568(2/1*15. 1)568/()568(3/2*95. 0)568/()568(3/2*15. 1)568/()568(15005683000568200056815007510540075104000