《运筹学教程》课后习题答案(第一章)课件.ppt

《《运筹学教程》课后习题答案(第一章)课件.ppt》由会员分享，可在线阅读，更多相关《《运筹学教程》课后习题答案(第一章)课件.ppt（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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(15005683000568200056

30、81500751054007510400075108001000600332313312111332313312111322212332313322212332313322212312111322212312111332313322212312111332313322212312111333231232221131211xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxst61 1-16 时代服装公司生产时代服装公司生产款新的时装，款新的时装，据预测今后据预测今后6个月的需求量如下表所示。每件个月的需求量如下表所示。每

31、件时装用工时装用工2h和和10元原材料费，售价元原材料费，售价40元。该元。该公司公司1月初有月初有4名工人，每人每月可工作名工人，每人每月可工作200h，月薪月薪2000元。该公司可于任何元。该公司可于任何个月初新雇工个月初新雇工人，但每雇人，但每雇1人需人需次性额外支出次性额外支出1500元，也元，也可辞退工人，但每辞退可辞退工人，但每辞退1人需补偿人需补偿1000元。如元。如当月生产数超过需求，可留到后面月份销售，当月生产数超过需求，可留到后面月份销售，但需付库存费每件每月但需付库存费每件每月5元。当供不应求时，元。当供不应求时，短缺数不需补上。试帮助该公司决策，如何使短缺数不需补上。试

32、帮助该公司决策，如何使6个月的总利润达到最大。个月的总利润达到最大。 月月份份123456需需求求500 600 300 400 500 80062)(1500)(30max654321654321ppppppyyyyyyZ )( 5)(1000654321654321ppppppppppppdddddd 66543211000)(2000 xxxxxxx 解：设解：设x xi i表示第表示第i i个月的工人数量，个月的工人数量，y yi i表示第表示第i i个个月生产产品的数量。月生产产品的数量。 p pi i表示第表示第i i个月初新雇工个月初新雇工人数量，人数量，d di i表示第表示第

33、i i个月初解雇工人数量。个月初解雇工人数量。 ppppi i表示第表示第i i个月月末的库存量，个月月末的库存量， ddddi i表示第表示第i i个月个月的短缺量。的短缺量。 031001001001001001001008005004003006005000; 465432166554433221165665455434432332122101106656554544343323221211010所有变量所有变量yyyyyyxyxyxyxyxyxyyppddppyppddppyppddppyppddppyppddppyppddppppdpxxdpxxdpxxdpxxdpxxdpxxx64

34、 1.17 1.17 童心玩具厂下一年度的现金流童心玩具厂下一年度的现金流( (万万元元) )如如下下表所示，表中负号表示该月现金流出表所示，表中负号表示该月现金流出大于流人，为此该厂需借款。借款有两种方式：大于流人，为此该厂需借款。借款有两种方式：一是于上一年末借一年期贷款，一次得全部贷一是于上一年末借一年期贷款，一次得全部贷款额，从款额，从1 1月底起每月还息月底起每月还息1 1，于，于1212月归还本月归还本金和最后一次利息；二是得到短期贷款，每月金和最后一次利息；二是得到短期贷款，每月初获得，于月底归还，月息初获得，于月底归还，月息1.51.5。当该厂有。当该厂有多余现金时，可短期存款

35、，月初存人，月末取多余现金时，可短期存款，月初存人，月末取出，月息出，月息0.40.4。问该厂应如何进行存贷款操。问该厂应如何进行存贷款操作，既能弥补可能出现的负现金流，又可使年作，既能弥补可能出现的负现金流，又可使年末现金总量为最大末现金总量为最大? ?月份月份123456789101112现金流现金流-12-10-8 -10 -45-7-2 1512-74565 045015. 101. 0004. 17015. 101. 0004. 112015. 101. 0004. 115015. 101. 0004. 12015. 101. 0004. 17015. 101. 0004. 1501

36、5. 101. 0004. 14015. 101. 0004. 110015. 101. 0004. 18015. 101. 0004. 110015. 101. 0004. 11212121111111110101010999988887777666655554444333322221111所有变量所有变量zyyxzzyyxzzyyxzzyyxzzyyxzzyyxzzyyxzzyyxzzyyxzzyyxzzyyxzzyxxyxzw 1212015. 101. 0004. 1max解：设解：设x x表示第表示第1 1个月初长期借款数额，个月初长期借款数额，y yi i表示第表示第i i个月初个月初短期借款数额，短期借款数额，z zi i表示第表示第i i个月初短期存款数额。个月初短期存款数额。 1.181.18 05090601203 . 14 . 1004. 112025. 1004. 1150004. 1100321313322231121所有变量所有变量xxxxxyyxyyxyyxxzzw min解：设解：设z z表示表示20022002年末筹得的资金数，年末筹得的资金数，x xi i表示购买第表示购买第i i种种债劵的金额，债劵的金额，y yi i表示第表示第i i年初短期存款数额。年初短期存款数额。