运筹学教程第一章

1、1同样适合 第三版黄皮版运筹学教程（第三版）运筹学教程（第三版）习题解答习题解答3第一章习题解答第一章习题解答 1.1 用图解法求解下列线性规划问用图解法求解下列线性规划问题。并指出问题具有惟一最优解、无穷题。并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。多最优解、无界解还是无可行解。 0,422664.32min)1 (21212121xxxxxxstxxZ0,124322.23max)2(21212121xxxxxxstxxZ85105120106.max)3(212121xxxxstxxZ0,23222.65max)4(21212121xxxxxxstxxZ4第一章习题解答

2、第一章习题解答是一个最优解无穷多最优解，3,31, 10,422664.32min)1 (2121212121ZxxxxxxxxstxxZ该问题无解0,124322.23max)2(21212121xxxxxxstxxZ5第一章习题解答第一章习题解答16, 6,1085105120106.max)3(21212121ZxxxxxxstxxZ唯一最优解，该问题有无界解0,23222.65max)4(21212121xxxxxxstxxZ6第一章习题解答第一章习题解答 1.2 将下述线性规划问题化成标准形式。将下述线性规划问题化成标准形式。 ., 0,2321422245243min) 1 (43

3、214321432143214321无约束xxxxxxxxxxxxxxxxstxxxxZ无约束321321321321,0,0624322min)2(xxxxxxxxxstxxxZ7第一章习题解答第一章习题解答., 0,2321422245243min) 1 (43214321432143214321无约束xxxxxxxxxxxxxxxxstxxxxZ0,232142222455243max64241321642413215424132142413214241321xxxxxxxxxxxxxxxxxxxxxxxstxxxxxZ8第一章习题解答第一章习题解答无约束321321321321,0,0

4、624322min)2(xxxxxxxxxstxxxZ0,6243322max43231214323121323121323121xxxxxxxxxxxxxxstxxxxZ9第一章习题解答第一章习题解答 1.3 对下述线性规划问题找出所有基解，对下述线性规划问题找出所有基解，指出哪些是基可行解，并确定最优解。指出哪些是基可行解，并确定最优解。 ）（6 , 1,0031024893631223max)1 (6153214321321jxxxxxxxxxxxstxxxZj)4, 1( ,0322274322325min)2(432143214321jxxxxxxxxxstxxxxZj10第一章习题

5、解答第一章习题解答）（6 , 1,0031024893631223max)1 (6153214321321jxxxxxxxxxxxstxxxZj基可行解x1x2x3x4x5x6Z03003.503001.5080300035000.7500022.252.2511第一章习题解答第一章习题解答)4, 1( ,0322274322325min)2(432143214321jxxxxxxxxxstxxxxZj基可行解x1x2x3x4Z00.5205001152/5011/5043/512第一章习题解答第一章习题解答 1.4 分别用图解法和单纯形法求解分别用图解法和单纯形法求解下述线性规划问题，并对照

6、指出单纯形下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域表中的各基可行解对应图解法中可行域的哪一顶点。的哪一顶点。 0,825943.510max)1 (21212121xxxxxxstxxZ 13第一章习题解答第一章习题解答0,24261553.2max)2(21212121xxxxxxstxxZ 14第一章习题解答第一章习题解答 l.5 上题上题(1)中，若目标函数变为中，若目标函数变为max Z = cx1 + dx2，讨论，讨论c,d的值如何变化，使该问题的值如何变化，使该问题可行域的每个顶点依次使目标函数达到最优。可行域的每个顶点依次使目标函数达到最优。 解：得

7、到最终单纯形表如下：解：得到最终单纯形表如下： Cjcd00CB基bx1x2x3x4dx23/2015/14-3/4cx1110-2/1410/35j00-5/14d+2/14c3/14d-10/14c15第一章习题解答第一章习题解答 当当c/d在在3/10到到5/2之间时最优解为图中之间时最优解为图中的的A点；当点；当c/d大于大于5/2且且c大于等于大于等于0时最优解时最优解为图中的为图中的B点；当点；当c/d小于小于3/10且且d大于大于0时最优时最优解为图中的解为图中的C点；当点；当c/d大于大于5/2且且c小于等于小于等于0时或当时或当c/d小于小于3/10且且d小于小于0时最优解为

8、图中时最优解为图中的原点。的原点。 16第一章习题解答第一章习题解答 式中，式中，1c13, 4c26, -1c13, 4c26, -1a113, 2a125, 8b112, 1a113, 2a125, 8b112, 2a215, 4a226, 10b214,2a215, 4a226, 10b214,试确试确定目标函数最优值的下界和上界。定目标函数最优值的下界和上界。 0,.max21222212112121112211xxbxaxabxaxastxcxcZ l.6 考虑下述线性规划问题：考虑下述线性规划问题： 17第一章习题解答第一章习题解答 最优值（上界）为：最优值（上界）为：21 21

9、0,14421221.63max21212121xxxxxxstxxZ 解：上界对应的模型如下（解：上界对应的模型如下（c,b取大，取大，a取小）取小） 18第一章习题解答第一章习题解答 最优值（下界）为：最优值（下界）为：6.46.40,1064853.4max21212121xxxxxxstxxZ 解：下界对应的模型如下（解：下界对应的模型如下（ c,b取小，取小，a取大）取大）19第一章习题解答第一章习题解答 l.7 分别用单纯形法中的大分别用单纯形法中的大M法和两法和两阶段法求解下列线性规划问题，并指出阶段法求解下列线性规划问题，并指出属哪属哪类解。类解。 该题是无界解。）（3 , 1

10、, 00222623max) 1 (3231321321jxxxxxxxxstxxxZj20第一章习题解答第一章习题解答6, 0,54,590,623824.32min)2(3212121321321ZxxxxxxxxxxstxxxZ最优解之一：该题是无穷多最优解。21第一章习题解答第一章习题解答517, 0, 1,59,524 , 1, 042634334max) 3(43214213212121ZxxxxjxxxxxxxxxstxxZj该题是唯一最优解：）（22第一章习题解答第一章习题解答该题无可行解。）（3 , 1, 052151565935121510max)4(32132132132

11、1jxxxxxxxxxxstxxxZj23第一章习题解答第一章习题解答 1.8 已知某线性规划问题的初始单已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到下面表纯形表和用单纯形法迭代后得到下面表格，试求括弧中未知数格，试求括弧中未知数a l值。值。 项 目X1X2X3X4X5X46(b)(c)(d)10X51-13(e)01CjZja-1200X1(f)(g)2-11/20X54(h)(i)1 1/21CjZj0-7jk(l) b=2, c=4, d=-2, g=1, h=0, f=3, i=5, e=2, l=0, a=3, j=5, k= -1.524第一章习题解答第一章习题解答 1

12、.9 若若X(1)、X(2)均为某线性规划问题均为某线性规划问题的最优解，证明在这两点连线上的所有点也的最优解，证明在这两点连线上的所有点也是该问题的最优解。是该问题的最优解。 也是最优解。所以也是可行解，且满足：两点连线上的点对于任何满足：和设XXCXCXaCaXCXaCaXCXCXaaXXXaXbAXXCZXXTTTTTTTT,)1 ()1 (, 100max)2()2()2()1()2()1()2()1()2()1(25第一章习题解答第一章习题解答 1.10 线性规划问题线性规划问题max ZCX,AXb，X0，设，设X0为问题的最优解。若目为问题的最优解。若目标函数中用标函数中用C*代

13、替代替C后，问题的最优解后，问题的最优解变为变为X*，求证，求证(C*-C)(X*-X0)00)()()(; 0max; 0max0*00*0*00XXCXXCXXCCXCXCXCZXCXCXCXZX的最优解，故是的最优解，故是26第一章习题解答第一章习题解答 1.11 考虑线性规划问题考虑线性规划问题0,)(75232)(24.42min432143214214321xxxxiixxxxixxxstxxxxZ 模型中模型中，为参数，要求：为参数，要求： (1) (1)组成两个新的约束组成两个新的约束(i)(i)(i)+(ii)(i)+(ii)，(ii)(ii)(ii)(ii)一一2(i)2(

14、i)，根据，根据(i)(i)，(ii)(ii)以以x1,x2x1,x2为基变量，为基变量，列出初始单纯形表；列出初始单纯形表；27第一章习题解答第一章习题解答1)(23)(32431xxiixxxiCja21-4CB 基bx1x2x3x4ax13+2011-12x21- 10-10j003-aa-428第一章习题解答第一章习题解答 (2)在表中，假定在表中，假定0，则，则为何值为何值时，时，x1, x2为问题的最优基变量；为问题的最优基变量； 解：解： 如果如果=0，则当，则当3a 4时，时，x1, x2为为问题的最优基变量；问题的最优基变量； (3)在表中，假定在表中，假定3，则，则为何值时

15、，为何值时，x1, x2为问题的最优基。为问题的最优基。 解：解： 如果如果a=3，则当，则当-1 1时，时，x1, x2为为问题的最优基变量。问题的最优基变量。29第一章习题解答第一章习题解答 1.12 线性规划问题线性规划问题max ZCX，AXb，X0，如，如X*是该问题的最优解，是该问题的最优解，又又0为某一常数，分别讨论下列情况时为某一常数，分别讨论下列情况时最优解的变化。最优解的变化。 (1)目标函数变为目标函数变为max ZCX； (2)目标函数变为目标函数变为max Z(C+)X； (3)目标函数变为目标函数变为max ZC/*X，约束，约束条件变为条件变为AXb。 解解:(1

16、)最优解不变最优解不变; (2)C为常数时最优解不变，否则可为常数时最优解不变，否则可能发生变化。能发生变化。 (3)最优解变为最优解变为:X/ 。30第一章习题解答第一章习题解答 1.13 某饲养场饲养动物出售，设每某饲养场饲养动物出售，设每头动物每天至少需头动物每天至少需700g蛋白质、蛋白质、30g矿矿物质、物质、100mg维生素。现有五种饲料可维生素。现有五种饲料可供选用，各种饲料每供选用，各种饲料每kg营养成分含量及营养成分含量及单价如下表所示。单价如下表所示。饲料饲料 蛋白质蛋白质(g)(g)矿物质矿物质(g)(g)维生素维生素(mg)(mg) 价格（元价格（元/kg/kg）131

17、0.50.2220.51.00.7310.20.20.446220.35180.50.80.831第一章习题解答第一章习题解答 要求确定既满足动物生长的营养需要，要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。又使费用最省的选用饲料的方案。( (建立这个建立这个问题的线性规划模型，不求解问题的线性规划模型，不求解) )5 , 4 , 3 , 2 , 1, 01008 . 022 . 05 . 0305 . 022 . 05 . 0700186238 . 03 . 04 . 07 . 02 . 0min5 , 4 , 3 , 2 , 1,54321543215432154321i

18、xxxxxxxxxxxxxxxxxxxxxZiixii种饲料数量表示第设32第一章习题解答第一章习题解答 1.14 某医院护士值班班次、每班工某医院护士值班班次、每班工作时间及各班所需护士数如下页表格所作时间及各班所需护士数如下页表格所示。示。班次班次工作时间工作时间所需护士数所需护士数（人）（人）1 16:00 6:00 10:0010:0060602 210:0010:0014:14:000070703 314:0014:0018:18:000060604 418:0018:0022:22:0000505033第一章习题解答第一章习题解答 (1)若护士上班后连续工作若护士上班后连续工作8h

19、，该医，该医院最少需多少名护士，以满足轮班需要；院最少需多少名护士，以满足轮班需要； 且为整数，班开始上班的护士人数表示第设, 6 , 5 , 4 , 3 , 2 , 1, 0302050607060min65 , 4 , 3 , 2 , 1,655443322161654321ixxxxxxxxxxxxxxxxxxxZiixii34第一章习题解答第一章习题解答 (2)若除若除22：00上班的护士连续工作上班的护士连续工作8h外外(取消第取消第6班班)，其他班次护士由医院，其他班次护士由医院排定上排定上1-4班的其中两个班，则该医院又班的其中两个班，则该医院又需多少名护士满足轮班需要。需多少名

20、护士满足轮班需要。 解解:第第5班一定要班一定要30个人，个人， 35第一章习题解答第一章习题解答4 , 3 , 2 , 1,10, , 02, 1,502, 1,602, 1,702, 1,6030min4 , 3 , 2 , 1,44434241444443342241143433323133443333223113242322212244233222211214131211114413312211114321jiyxyyyyyxyxyxyxyyyyyyxyxyxyxyyyyyyxyxyxyxyyyyyyxyxyxyxyxxxxZiixijii变量是第四班约束第三班约束第二班约束第一班约束

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

22、间不超过10。问该货。问该货轮应装载轮应装载A，B，C各多少件运费收入才各多少件运费收入才最大最大?试建立这个问题的线性规划模型。试建立这个问题的线性规划模型。37第一章习题解答第一章习题解答商品商品数量数量（件）（件）每件体每件体积积(m3/(m3/件件) )每件重每件重量量(t/(t/件件) )运价运价（元（元/ /件）件）A A60060010108 810001000B B100010005 56 6700700C C8008007 75 5600600项目项目前舱前舱中舱中舱后舱后舱最大允许载重量最大允许载重量（t t）200020003000300015001500容积（容积（m3

23、m3）40004000540054001500150038第一章习题解答第一章习题解答 MAX= 1000（X(1,1)+X(1,2)+X(1,3)） +700 （X(2,1)+X(2,2)+X(2,3)） +600 （X(3,1)+X(3,2)+X(3,3)） SUBJECT TO X(i,j)表示第商品表示第商品i在舱在舱j的装载量，的装载量，i,j=1,2,3 商品数量约束：商品数量约束： 1 X(1,1)+X(1,2)+X(1,3) = 600 2 X(2,1)+X(2,2)+X(2,3) = 1000 3 X(3,1)+X(3,2)+X(3,3) = 800 39第一章习题解答第一章

24、习题解答 商品容积约束：商品容积约束： 4 10X(1,1)+5X(2,1)+7X(3,1) = 4000 5 10X(1,2)+5X(2,2)+7X(3,2) = 5400 6 10X(1,3)+5X(2,3)+7X(3,3) = 1500 最大载重量约束：最大载重量约束： 7 8 X(1,1)+6X(2,1)+5X(3,1) = 2000 8 8 X(1,2)+6X(2,2)+5X(3,2) = 3000 9 8 X(1,3)+6X(2,3)+5X(3,3) = 1500 40第一章习题解答第一章习题解答重量比例偏差约束：重量比例偏差约束： 10 8X(1,1)+6X(2,1)+5X(3,

25、1)=2/3（1-0.15） 8X(1,2)+6X(2,2)+5X(3,2) 12 8X(1,3)+6X(2,3)+5X(3,3)=1/2（1-0.15） 8X(1,2)+6X(2,2)+5X(3,2) 14 8X(1,3)+6X(2,3)+5X(3,3)=3/4（1-0.1） 8X(1,1)+6X(2,1)+5X(3,1) 41第一章习题解答第一章习题解答 1.16 某厂生产某厂生产I，两种食品，现有两种食品，现有50名熟练工人，每名熟练工人每名熟练工人，每名熟练工人每h可生产可生产食品食品110kg或食品或食品6kg。由于需求量将不。由于需求量将不断增长断增长(见下页表格见下页表格)，该厂

26、计划到第，该厂计划到第8周末周末前培训出前培训出50名新工人，组织两班生产。已名新工人，组织两班生产。已知一名工人每周工作知一名工人每周工作40h，一名熟练工人，一名熟练工人用用2周时间可培训出不多于周时间可培训出不多于3名新工人名新工人(培训培训期间熟练工人和被培训人员均不参加生产期间熟练工人和被培训人员均不参加生产)。熟练工人每周工资熟练工人每周工资360元，新工人培训期间元，新工人培训期间工资每周工资每周120元，新工人培训结束后工作每元，新工人培训结束后工作每周工资周工资240元，且生产效率同熟练工人。培元，且生产效率同熟练工人。培训过渡期，工厂将安排部分熟练工人加班，训过渡期，工厂将

27、安排部分熟练工人加班，加班加班1h另加付另加付12元。又生产食品不能满足元。又生产食品不能满足订货需求，推迟交货的赔偿费分别为：食订货需求，推迟交货的赔偿费分别为：食品品I为为0.50元元(kg周周)；食品；食品为为0.60元元(kg周周)。工厂应如何全面安排，使各项费。工厂应如何全面安排，使各项费用总和最小，试建立线性规划模型。用总和最小，试建立线性规划模型。42第一章习题解答第一章习题解答周次周次食品食品1 12 23 34 45 56 66 67 78 8101010101212121216161616161620202020 6 67.27.2 8.48.410.10.8 812121

28、212121212121212 设设x(i)，y(i)表示从事两个产品生产的人数，表示从事两个产品生产的人数，xx(i)，yy(i)表示从事生产两个产品的加班小时数，表示从事生产两个产品的加班小时数，f1(i),f2(i)表示两个产品推迟交货的数量，表示两个产品推迟交货的数量，r1(i),r2(i)表示两个产表示两个产品的需求数量，品的需求数量，w(i),n(i)分别表示开始从事培训工作的人分别表示开始从事培训工作的人数和新接受培训的工人人数。数和新接受培训的工人人数。43第一章习题解答第一章习题解答 MIN= 360X(i)+360Y(i)+360W(i) +12XX(i)+12yy(i)

29、+0.5f1(i)+0.6f2(i) +(120+120)n(i) +240(7-i)n(i) n(i)=nx(i)+ny(i) N(8)=0 - 3 W(i) + N(i) = 0 XX(i) = 1000 YY(i) = 1000 44第一章习题解答第一章习题解答 400X(i)+10XX(i)=116000 240y(i)+6 yy(i)= 79200 400*x(1)+10*xx(1)+f1(1)=10000; 400*(x(1)+x(2)+10*(xx(1)+xx(2) +f1(2)=20000; for(a(i)|i#ge#3#and#i#le#s: 400*x(1)+400*x(

30、2)+10*xx(1)+10*xx(2) +sum(a(j)|j#le#i#and#j#gt#2: 400*(x(j)+nx(j-2)+10*xx(j)+f1(i) =sum(a(j)|j#le#i:r1(j); f1(s)=0;45第一章习题解答第一章习题解答 240*y(1)+6*yy(1)+f2(1)=6000; 240*(y(1)+y(2)+6*(yy(1)+yy(2) +f2(2)=13200; for(a(i)|i#ge#3#and#i#le#s: 240*y(1)+240*y(2)+6*yy(1)+6*yy(2) +sum(a(j)|j#le#i#and#j#gt#2: 240*

31、(y(j)+ny(j-2)+6*yy(j)+f2(i) =sum(a(j)|j#le#i:r2(j); f2(s)=0;46第一章习题解答第一章习题解答 x(1)+y(1)+w(1)=50; x(2)+y(2)+w(1)+w(2)=50; for(a(i)|i#gt#2: x(i)+y(i)+w(i-1)+w(i)=50); sum(a(i)|i#le#s:n(i)=50; for(a(i):gin(x(i); for(a(i):gin(y(i); for(a(i):gin(w(i); for(a(i):gin(n(i);47第一章习题解答第一章习题解答 1-17 时代服装公司生产时代服装公司

32、生产款新的时款新的时装，据预测今后装，据预测今后6个月的需求量如下表所个月的需求量如下表所示。每件时装用工示。每件时装用工2h和和10元原材料费，元原材料费，售价售价40元。该公司元。该公司1月初有月初有4名工人，每名工人，每人每月可工作人每月可工作200h，月薪，月薪2000元。该公元。该公司可于任何司可于任何个月初新雇工人，但每雇个月初新雇工人，但每雇1人需人需次性额外支出次性额外支出1500元，也可辞退元，也可辞退工人，但每辞退工人，但每辞退1人需补偿人需补偿1000元。如元。如当月生产数超过需求，可留到后面月份当月生产数超过需求，可留到后面月份销售，但需付库存费每件每月销售，但需付库存

33、费每件每月5元。当供元。当供不应求时，短缺数不需补上。试帮助该不应求时，短缺数不需补上。试帮助该公司决策，如何使公司决策，如何使6个月的总利润达到最个月的总利润达到最大。大。 月月份份123456需需求求500 600 300 400 500 80048第一章习题解答第一章习题解答 max = 30(y1+y2+y3+y4+y5+y6) -1500(p1+p2+p3+p4+p5+p6) -1000(d1+d2+d3+d4+d5+d6) -5(pp1+pp2+pp3+pp4+pp5+pp6) -2000(x1+x2+x3+x4+x5+x6) -1000 x6;x0=4; x表示工人人数，表示工人

34、人数，y表示产表示产品产量，品产量， p表示新工人人数表示新工人人数 d表示辞退工表示辞退工人人数人人数p1-d1=x1-x0; p2-d2=x2-x1;p3-d3=x3-x2; p4-d4=x4-x3;p5-d5=x5-x4; p6-d6=x6-x5; 49第一章习题解答第一章习题解答pp0=0;pp表示库存量表示库存量,dd表示缺损额表示缺损额 pp1-dd1=y1+pp0-500; pp2-dd2=y2+pp1-600;pp3-dd3=y3+pp2-300; pp4-dd4=y4+pp3-400;pp5-dd5=y5+pp4-500; pp6-dd6=y6+pp5-800;生产能力约束：生产能力约束： y1=100*x1; y2=100*x2; y3=100*x3; y4=100*x4; y5=100*x5; y6=100*x6;总产量约束：总产量约束：y1+y2+y3+y4+y5+y6=3100;