《清华大学胡运权《运筹学习题集》第二版》由会员分享，可在线阅读，更多相关《清华大学胡运权《运筹学习题集》第二版（51页珍藏版）》请在金锄头文库上搜索。
1、1,同样适合 第三版黄皮版,运筹学教程（第二版） 习题解答,安徽大学管理学院 洪 文,3,第一章习题解答,1.1 用图解法求解下列线性规划问题。并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。,4,第一章习题解答,5,第一章习题解答,6,第一章习题解答,1.2 将下述线性规划问题化成标准形式。,7,第一章习题解答,8,第一章习题解答,9,第一章习题解答,1.3 对下述线性规划问题找出所有基解，指出哪些是基可行解，并确定最优解。,10,第一章习题解答,11,第一章习题解答,12,第一章习题解答,1.4 分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图
2、解法中可行域的哪一顶点。,13,第一章习题解答,14,第一章习题解答,l.5 上题(1)中，若目标函数变为max Z = cx1 + dx2，讨论c,d的值如何变化，使该问题可行域的每个顶点依次使目标函数达到最优。 解：得到最终单纯形表如下：,15,第一章习题解答,当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时最优解为图中的原点。,16,第一章习题解答,式中，1c13, 4c26, -1a113, 2a125, 8b
3、112, 2a215, 4a226, 10b214,试确定目标函数最优值的下界和上界。,l.6 考虑下述线性规划问题：,17,第一章习题解答,最优值（上界）为：21,解：上界对应的模型如下（c,b取大，a取小）,18,第一章习题解答,最优值（下界）为：6.4,解：下界对应的模型如下（ c,b取小，a取大）,19,第一章习题解答,l.7 分别用单纯形法中的大M法和两阶段法求解下列线性规划问题，并指出属哪类解。,20,第一章习题解答,21,第一章习题解答,22,第一章习题解答,23,第一章习题解答,1.8 已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到下面表格，试求括弧中未知数al值。,b
4、=2, c=4, d=-2, g=1, h=0, f=3, i=5, e=2, l=0, a=3, j=5, k= -1.5,24,第一章习题解答,1.9 若X(1)、X(2)均为某线性规划问题的最优解，证明在这两点连线上的所有点也是该问题的最优解。,25,第一章习题解答,1.10 线性规划问题max ZCX,AXb，X0，设X0为问题的最优解。若目标函数中用C*代替C后，问题的最优解变为X*，求证 (C*-C)(X*-X0)0,26,第一章习题解答,1.11 考虑线性规划问题,模型中，为参数，要求： (1)组成两个新的约束(i)(i)+(ii)，(ii)(ii)一2(i)，根据(i)，(ii
5、)以x1,x2为基变量，列出初始单纯形表；,27,第一章习题解答,28,第一章习题解答,(2)在表中，假定0，则为何值时，x1, x2为问题的最优基变量； 解： 如果=0，则当3a 4时，x1, x2为问题的最优基变量； (3)在表中，假定3，则为何值时，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)目标函数变为m
6、ax ZC/*X，约束条件变为AXb。 解: (1)最优解不变; (2)C为常数时最优解不变，否则可能发生变化。 (3)最优解变为:X/ 。,30,第一章习题解答,1.13 某饲养场饲养动物出售，设每头动物每天至少需700g蛋白质、30g矿物质、100mg维生素。现有五种饲料可供选用，各种饲料每kg营养成分含量及单价如下表所示。,31,第一章习题解答,要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。(建立这个问题的线性规划模型，不求解),32,第一章习题解答,1.14 某医院护士值班班次、每班工作时间及各班所需护士数如下页表格所示。,33,第一章习题解答,(1)若护士上班后连续
7、工作8h，该医院最少需多少名护士，以满足轮班需要；,34,第一章习题解答,(2)若除22：00上班的护士连续工作8h外(取消第6班)，其他班次护士由医院排定上1-4班的其中两个班，则该医院又需多少名护士满足轮班需要。 解:第5班一定要30个人，,35,第一章习题解答,36,第一章习题解答,1.15 艘货轮分前、中、后三个舱位，它们的容积与最大允许载重量见后面的表格。现有3种货物待运，已知有关数据列于后面的表格。 又为了航运安全，前、中、后舱的实际载重量大体保持各舱最大允许载重量的比例关系。具体要求：前、后舱分别与中舱之间载重量比例的偏差不超过15，前、后舱之间不超过10。问该货轮应装载A，B，
8、C各多少件运费收入才最大?试建立这个问题的线性规划模型。,37,第一章习题解答,38,第一章习题解答,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,第一章习题解答,商品容积约束： 4 10X
9、(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,1)=2/3（1-0.15） 8X(1,2)+6X(2,2)+5X(3,2) 12 8X(1,
10、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。由于需求量将不断增长(见下页表格)，该厂计划到第8周末前培训出50名新工人，组织两班生产。已知一名工人每周工作40h，一名熟练工人用2周时间可培训出不多于3名新工人(培训期间熟练工人和被培训人员均不参加生产)。熟练工人每周工资360元，新工人
11、培训期间工资每周120元，新工人培训结束后工作每周工资240元，且生产效率同熟练工人。培训过渡期，工厂将安排部分熟练工人加班，加班1h另加付12元。又生产食品不能满足订货需求，推迟交货的赔偿费分别为：食品I为0.50元(kg周)；食品为0.60元(kg周)。工厂应如何全面安排，使各项费用总和最小，试建立线性规划模型。,42,第一章习题解答,设x(i)，y(i)表示从事两个产品生产的人数，xx(i)，yy(i)表示从事生产两个产品的加班小时数，f1(i),f2(i)表示两个产品推迟交货的数量，r1(i),r2(i)表示两个产品的需求数量，w(i),n(i)分别表示开始从事培训工作的人数和新接受培
12、训的工人人数。,43,第一章习题解答,MIN= 360X(i)+360Y(i)+360W(i) +12XX(i)+12yy(i) +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
13、) +f1(2)=20000; for(a(i)|i#ge#3#and#i#le#s: 400*x(1)+400*x(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*
14、y(2)+6*yy(1)+6*yy(2) +sum(a(j)|j#le#i#and#j#gt#2: 240*(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
15、(i):gin(n(i);,47,第一章习题解答,1-17 时代服装公司生产款新的时装，据预测今后6个月的需求量如下表所示。每件时装用工2h和10元原材料费，售价40元。该公司1月初有4名工人，每人每月可工作200h，月薪2000元。该公司可于任何个月初新雇工人，但每雇1人需次性额外支出1500元，也可辞退工人，但每辞退1人需补偿1000元。如当月生产数超过需求，可留到后面月份销售，但需付库存费每件每月5元。当供不应求时，短缺数不需补上。试帮助该公司决策，如何使6个月的总利润达到最大。,48,第一章习题解答,max = 30(y1+y2+y3+y4+y5+y6) -1500(p1+p2+p3+
16、p4+p5+p6) -1000(d1+d2+d3+d4+d5+d6) -5(pp1+pp2+pp3+pp4+pp5+pp6) -2000(x1+x2+x3+x4+x5+x6) -1000x6; x0=4; x表示工人人数，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-
