胡运权《运筹学教程》习题答案(第一章)[1].pdf 9页

'2011/03/21第一章习题解答第一章习题解答minZ=2x+3x1.1用图解法求解下列线性规划问题。并指出问12⎧4x1+6x2≥6题具有惟一最优解、无穷多最优解、无界解还是无可(1)⎪行解。st.⎨2x1+2x2≥4⎪x,x≥0⎩12minZ=2x+3xmaxZ=3x+2x1212无穷多最优解，⎧4x1+6x2≥6⎧2x1+x2≤2(1)⎪(2)⎪1st.⎨2x1+2x2≥4st.⎨3x1+4x2≥12x1=1,x2=,Z=3是一个最优解3⎪x,x≥0⎪x,x≥0⎩12⎩12maxZ=3x+2x12maxZ=x1+x2maxZ=5x1+6x2⎧2x1+x2≤2⎧6x1+10x2≤120⎧2x1−x2≥2(2)st.⎪⎨3x+4x≥12(3)⎪(4)⎪12st.⎨5≤x1≤10st.⎨−2x1+3x2≤2⎪x,x≥0⎩12⎪5≤x≤8⎪x,x≥0⎩2⎩12该问题无解第一章习题解答第一章习题解答maxZ=x+x1.2将下述线性规划问题化成标准形式。12⎧6x1+10x2≤120minZ=−3x+4x−2x+5x(3)⎪1234st.⎨5≤x1≤10⎧4x1−x2+2x3−x4=−2⎪5≤x≤8⎪⎩2(1)⎪x1+x2−x3+2x4≤14st⎨.唯一最优解，x1=10,x2=6,Z=16⎪−2x1+3x2+x3−x4≥2⎪x,x,x≥0,x无约束maxZ=5x+6x⎩123412⎧2x1−x2≥2minZ=2x−2x+3x(4)⎪123st.⎨−2x1+3x2≤2⎧−x1+x2+x3=4⎪x,x≥0(2)st⎪−2x+x−x≤6⎩12⎨123该问题有无界解⎪x≤0,x≥0,x无约束⎩123第一章习题解答第一章习题解答minZ=−3x+4x−2x+5x1234minZ=2x−2x+3x123⎧4x1−x2+2x3−x4=−2⎧−x+x+x=4⎪123(1)⎪x1+x2−x3+2x4≤14(2)st⎪−2x+x−x≤6st⎨.⎨123⎪−2x1+3x2+x3−x4≥2⎪x≤0,x≥0,x无约束⎩123⎪,,0,无约束⎩x1x2x3≥x4无约束maxZ=2x+2x−3x+3x123132maxZ=3x−4x+2x−5x+5x1234142⎧−x1+x2+x31−x32=4⎧−4x1+x2−2x3+x41−x42=2st⎪2x+x−x+x+x=6⎪⎨1231324⎪x1+x2−x3+2x41−2x42+x5=14⎪x,x,x,x,x≥0st⎨⎩1231324−2x+3x+x−x+x−x=2⎪12341426⎪x,x,x,x,x,x≥0⎩123414261 2011/03/21第一章习题解答第一章习题解答maxZ=3x+x+2x1.3对下述线性规划问题找出所有基解，指出哪123⎧12x1+3x2+6x3+3x4=9些是基可行解，并确定最优解。⎪(1)⎪8x1+x2−4x3+2x5=10st⎨maxZ=3x1+x2+2x3⎪3x1−x6=0⎧12x1+3x2+6x3+3x4=9⎪x≥0（,j=1,?,6）⎩j⎪(1)⎪8x1+x2−4x3+2x5=10st⎨基可行解3x−x=0⎪16⎪x≥0（,j=1,?,6）x1x2x3x4x5x6Z⎩j03003.503minZ=5x−2x+3x+2x1234⎧x+2x+3x+4x=7001.508031234(2)⎪st⎨2x1+2x2+x3+2x4=30003500⎪x≥0,(j=1,?4)⎩j0.7500022.252.25第一章习题解答第一章习题解答minZ=5x−2x+3x+2x1.4分别用图解法和单纯形法求解下述线性规划1234⎧x+2x+3x+4x=7问题，并对照指出单纯形表中的各基可行解对应图解1234(2)⎪法中可行域的哪一顶点。st⎨2x1+2x2+x3+2x4=3⎪x≥0,(j=1,?4)maxZ=10x1+5x2⎩j⎧3x1+4x2≤9(1)⎪st.⎨5x1+2x2≤8基可行解⎪x,x≥0⎩12x1x2x3x4Z00.5205001152/5011/5043/5第一章习题解答第一章习题解答maxZ=2x+x12l.5上题(1)中，若目标函数变为maxZ=cx+dx，⎧3x1+5x2≤1512(2)⎪讨论c,d的值如何变化，使该问题可行域的每个顶点依st.⎨6x1+2x2≤24次使目标函数达到最优。⎪x,x≥0⎩12解：得到最终单纯形表如下：Cj→cd00CB基bx1x2x3x4dx23/2015/14-3/4cx1110-2/1410/35σj00-5/14d+2/14c3/14d-10/14c2 2011/03/21第一章习题解答第一章习题解答当c/d在3/10到5/2之间时最优解为图中的A点；当l.6考虑下述线性规划问题：c/d大于5/2且c大于等于0时最优解为图中的B点；当c/d小于3/10且d大于0时最优解为图中的C点；当c/d大于maxZ=c1x1+c2x25/2且c小于等于0时或当c/d小于3/10且d小于0时最优解⎧a11x1+a12x2≤b1为图中的原点。⎪st.⎨a21x1+a22x2≤b2⎪x,x≥0⎩12式中，1≤c≤3,4≤c≤6,-1≤a≤3,2≤a≤5,1211128≤b≤12,2≤a≤5,4≤a≤6,10≤b≤14,试确定121222目标函数最优值的下界和上界。第一章习题解答第一章习题解答解：上界对应的模型如下（c,b取大，a取小）解：下界对应的模型如下（c,b取小，a取大）maxZ=x+4xmaxZ=3x+6x1212⎧−1x1+2x2≤12⎧3x1+5x2≤8⎪st.⎪4x+6x≤10st.⎨2x1+4x2≤14⎨12⎪x,x≥0⎪x,x≥0⎩12⎩12最优值（上界）为：21最优值（下界）为：6.4第一章习题解答第一章习题解答l.7分别用单纯形法中的大M法和两阶段法求解下列线性规划问题，并指出属哪—类解。minZ=2x1+3x2+x3⎧x1+4x2+2x3≥8maxZ=3x−x+2x(2)⎪123st.⎨3x+2x≥612⎧x1+x2+x3≥6⎪x,x0⎪⎩12≥(1)⎪−2x1+x3≥2st⎨该题是无穷多最优解。2x−x=0⎪2394⎪x≥0（,j=1,?,3）最优解之一：x=,x=,x=0,Z=6⎩j12355该题是无界解。3 2011/03/21第一章习题解答第一章习题解答maxZ=4x+x12maxZ=10x+15x+12x⎧3x+x=312312⎪⎧5x1+3x2+x3≤9(3)⎪4x1+3x2−x3=6⎪st⎨(4)⎪−5x1+6x2+15x3≤15⎪x1+2x2+x4=4st⎨2x+x+x≥5⎪x≥0（,j=1,?,4）⎪123⎩j⎪x≥0（,j=1,?,3）⎩j该题是唯一最优解：该题无可行解。2917x=,x=,x=1,x=0,Z=1234555第一章习题解答第一章习题解答1.8已知某线性规划问题的初始单纯形表和用单1.9若X(1)、X(2)均为某线性规划问题的最优解，纯形法迭代后得到下面表格，试求括弧中未知数a∼l值。证明在这两点连线上的所有点也是该问题的最优解。项目XXXXXT12345maxZ=CXX46(b)(c)(d)10设X(1)和X(2)满足：⎧AX=b⎨X51-13(e)01⎩X≥0C－Za-1200jj对于任何00为某一常数，分别讨论五种饲料可供选用，各种饲料每kg营养成分含量及单下列情况时最优解的变化。价如下表所示。(1)目标函数变为maxZ＝λCX；饲料蛋白质(g)矿物质(g)维生素(mg)价格（元/kg）(2)目标函数变为maxZ＝(C+λ)X；1310.50.2(3)目标函数变为maxZ＝C/λ*X，约束条件变为AX＝λb。220.51.00.7解:(1)最优解不变;310.20.20.4(2)C为常数时最优解不变，否则可能发生变化。46220.3(3)最优解变为:X/λ。5180.50.80.8第一章习题解答第一章习题解答要求确定既满足动物生长的营养需要，又使费用1.14某医院护士值班班次、每班工作时间及各最省的选用饲料的方案。(建立这个问题的线性规划班所需护士数如下页表格所示。模型，不求解)班次工作时间所需护士数（人）设x表示第i种饲料数量,i=1,2,3,4,5i16006:00∼100010:0060minZ=0.2x+0.7x+0.4x+0.3x+0.8x12345210:00∼14:0070⎧3x1+2x2+x3+6x4+18x5≥700314:00∼18:0060⎪⎪x1+0.5x2+0.2x3+2x4+0.5x5≥30418:00∼22:0050⎨0.5x+x+0.2x+2x+0.8x≥100⎪12345522:00∼2:0020⎪x≥0,i=1,2,3,4,5⎩i62:00∼6:00305 2011/03/21第一章习题解答第一章习题解答(1)若护士上班后连续工作8h，该医院最少需多少名护士，以满足轮班需要；设x表示第i班开始上班的护士人数,i=1,2,3,4,5，6i(2)若除22：00上班的护士连续工作8h外(取消第6minZ=x+x+x+x+x+x123456班)，其他班次护士由医院排定上1-4班的其中两个班，x+x≥6016则该医院又需多少名护士满足轮班需要。x+x≥7012解:第5班一定要30个人，x+x≥6023x+x≥5034x+x≥2045x+x≥3056x≥0,i=1,2,3,4,5,6,且为整数i第一章习题解答第一章习题解答设x表示第i班开始上班的护士人数,i=1,2,3,4iminZ=x1+x2+x3+x4+301.15—艘货轮分前、中、后三个舱位，它们的⎧yx+yx+yx+yx≥60,第一班约束容积与最大允许载重量见后面的表格。现有3种货物待111212313414⎪运，已知有关数据列于后面的表格。y=1,y+y+y+y=2⎪1111121314⎪yx+yx+yx+yx≥70,第二班约束又为了航运安全，前、中、后舱的实际载重量大121222323424⎪体保持各舱最大允许载重量的比例关系。具体要求：⎪y22=1,y21+y22+y23+y24=2前、后舱分别与中舱之间载重量比例的偏差不超过15⎪⎨y13x1+y23x2+y33x3+y43x4≥60,第三班约束％，前、后舱之间不超过10％。问该货轮应装载A，B，⎪y33=1,y31+y32+y33+y34=2C各多少件运费收入才最大?试建立这个问题的线性规⎪⎪yx+yx+yx+yx≥50,第四班约束划模型。141242343444⎪y=1,y+y+y+y=2⎪4441424344⎪x≥0,,y是0−1变量i,j=1,2,3,4⎩iij第一章习题解答第一章习题解答项目前舱中舱后舱MAX=1000（X(1,1)+X(1,2)+X(1,3)）最大允许载重量（t）200030001500+700（X(2,1)+X(2,2)+X(2,3)）容积（m3）400054001500+600（X(3,1)+X(3,2)+X(3,3)）SUBJECTTO数量每件体积每件重量运价X(i,j)表示第商品i在舱j的装载量，i,j=1,2,3商品（件）(m3/件)(t/件)（元/件）商品数量约束：1]X(1,1)+X(1,2)+X(1,3)<=600A60010810002]X(2,1)+X(2,2)+X(2,3)<=1000B1000567003]X(3,1)+X(3,2)+X(3,3)<=800C800756006 2011/03/21第一章习题解答第一章习题解答重量比例偏差约束：商品容积约束：10]8X(1,1)+6X(2,1)+5X(3,1)<=2/3（1+0.15）8X(1,2)+6X(2,2)+5X(3,2)4]10X(1,1)+5X(2,1)+7X(3,1)<=400011]8X(1,1)+6X(2,1)+5X(3,1)>=2/3（1-0.15）5]10X(1,2)+5X(2,2)+7X(3,2)<=54008X(1,2)+6X(2,2)+5X(3,2)6]10X(13)+5X(23)+7X(33)<=10X(1,3)+5X(2,3)+7X(3,3)<=150012]8X(1,3)+6X(2,3)+5X(3,3)<=1/2（1+0.15）最大载重量约束：8X(1,2)+6X(2,2)+5X(3,2)7]8X(1,1)+6X(2,1)+5X(3,1)<=200013]8X(1,3)+6X(2,3)+5X(3,3)>=1/2（1-0.15）8X(1,2)+6X(2,2)+5X(3,2)8]8X(1,2)+6X(2,2)+5X(3,2)<=300014]8X(1,3)+6X(2,3)+5X(3,3)<=3/4（1+0.1）9]8X(1,3)+6X(2,3)+5X(3,3)<=15008X(1,1)+6X(2,1)+5X(3,1)15]8X(1,3)+6X(2,3)+5X(3,3)>=3/4（1-0.1）8X(1,1)+6X(2,1)+5X(3,1)第一章习题解答第一章习题解答周次1.16某厂生产I，Ⅱ两种食品，现有50名熟练工人，123456678每名熟练工人每h可生产食品110kg或食品Ⅱ6kg。由于需求量将不断增长(见下页表格)，该厂计划到第8周末前培食品训出50名新工人，组织两班生产。已知一名工人每周工Ⅰ101012121616162020作40h，一名熟练工人用2周时间可培训出不多于3名新工人(培训期间熟练工人和被培训人员均不参加生产)。熟Ⅱ6727.2848.410810.81212121212练工人每周工资360元，新工人培训期间工资每周120元，新工人培训结束后工作每周工资240元，且生产效率同熟设x(i)，y(i)表示从事两个产品生产的人数，xx(i)，练工人。培训过渡期，工厂将安排部分熟练工人加班，yy(i)表示从事生产两个产品的加班小时数，f1(i),f2(i)加班1h另加付12元。又生产食品不能满足订货需求，推表示两个产品推迟交货的数量，r1(i),r2(i)表示两个产迟交货的赔偿费分别为：食品I为0.50元／(kg·周)；食品的需求数量，w(i),n(i)分别表示开始从事培训工作的人品Ⅱ为0.60元／(kg·周)。工厂应如何全面安排，使各项数和新接受培训的工人人数。费用总和最小，试建立线性规划模型。第一章习题解答第一章习题解答MIN=400∑X(i)+10∑XX(i)=116000∑360X(i)+∑360Y(i)+∑360W(i)240∑y(i)+6∑yy(i)=79200400*x(1)+10*xx(1)+f1(1)=10000;+∑12XX(i)+∑12yy(i)400*(x(1)+x(2))+10*(xx(1)+xx(2))+0.5∑f1(i)+0.6∑f2(i)+f1(2)=20000;+(120+120)∑n(i)@for(a(i)|i#ge#3#and#i#le#s:+240∑(7-i)n(i)400*x(1)+400*x(2)+10*xx(1)+10*xx(2)n(i)=nx(i)+ny(i)+@sum(a(j)|j#le#i#and#j#gt#2:N(8)=0400*(x(j)+nx(j-2))+10*xx(j))+f1(i)-3W(i)+N(i)<=0=@sum(a(j)|j#le#i:r1(j)));XX(i)<=1000f1(s)=0;YY(i)<=10007 2011/03/21第一章习题解答第一章习题解答240*y(1)+6*yy(1)+f2(1)=6000;x(1)+y(1)+w(1)=50;240*(y(1)+y(2))+6*(yy(1)+yy(2))x(2)+y(2)+w(1)+w(2)=50;+f2(2)=13200;@for(a(i)|i#gt#2:@for(a(i)|i#ge#3#and#i#le#s:x(i)+y(i)+w(i-1)+w(i)=50);240*y(1)+240*y(2)+6*yy(1)+6*yy(2)@sum(a(i)|i#le#s:n(i))=50;+@sum(a(j)|j#le#i#and#j#gt#2:@for(a(i):@gin(x(i)));240*(y(j)+ny(j-2))+6*yy(j))+f2(i)@for(a(i):@gin(y(i)));=@sum(a(j)|j#le#i:r2(j)));@for(a(i):@gin(w(i)));f2(s)=0;@for(a(i):@gin(n(i)));第一章习题解答第一章习题解答1-17时代服装公司生产—款新的时装，据预测今max=30(y1+y2+y3+y4+y5+y6)后6个月的需求量如下表所示。每件时装用工2h和10元-1500(p1+p2+p3+p4+p5+p6)原材料费，售价40元。该公司1月初有4名工人，每人-1000(d1+d2+d3+d4+d5+d6)每月可工作200h，月薪2000元。该公司可于任何—个-5(pp1+pp2+pp3+pp4+pp5+pp6)月初新雇工人，但每雇1人需—次性额外支出1500元，也可辞退工人，但每辞退1人需补偿1000元。如当月生-2000(x1+x2+x3+x4+x5+x6)产数超过需求，可留到后面月份销售，但需付库存费-1000x6;每件每月5元。当供不应求时，短缺数不需补上。试帮x0=4;x表示工人人数，y表示产品产量，助该公司决策，如何使6个月的总利润达到最大。p表示新工人人数d表示辞退工人人数月份123456p1-d1=x1-x0;p2-d2=x2-x1;p3-d3=x3-x2;p4-d4=x4-x3;需求500600300400500800p5-d5=x5-x4;p6-d6=x6-x5;第一章习题解答第一章习题解答pp0=0;pp表示库存量,dd表示缺损额1.18童心玩具厂下一年度的现金流(万元)如下表所示，表中负号表示该月现金流出大于流人，为此pp1-dd1=y1+pp0-500;pp2-dd2=y2+pp1-600;该厂需借款。借款有两种方式：一是于上一年末借一pp3-dd3=y3+pp2-300;pp4-dd4=y4+pp3-400;年期贷款，一次得全部贷款额，从1月底起每月还息1pp5-dd5=y5+pp4-500;pp6-dd6=y6+pp5-800;％，于12月归还本金和最后一次利息；二是得到短期生产能力约束：贷款，每月初获得，于月底归还，月息151.5％。当该厂y1<=100*x1;y2<=100*x2;y3<=100*x3;有多余现金时，可短期存款，月初存人，月末取出，月息0.4％。问该厂应如何进行存贷款操作，既能弥补y4<=100*x4;y5<=100*x5;y6<=100*x6;可能出现的负现金流，又可使年末现金总量为最大?总产量约束：y1+y2+y3+y4+y5+y6<=3100;@gin(y1);@gin(y2);@gin(y3);@gin(y4);月份123456789101112@gin(y5);@gin(y6);@gin(x1);@gin(x2);现金流-12-10-8-10-45-7-21512-745@gin(x3);@gin(x4);@gin(x5);@gin(x6);8 2011/03/21第一章习题解答MAX=1.004Z(12)-1.01y-1.015W(12)SUBJECTTO1]Y-Z(1)+W(1)=122]-.01Y+1.004Z(1)-.1015W(1)-Z(2)+W(2)=103]-.01Y+1.004Z(2)-.1015W(2)-Z(3)+W(3)=84]-.01Y+1.004Z(()3)-.1015W(()3)-Z(()()4)+W(4)=105]-.01Y+1.004Z(4)-.1015W(4)-Z(5)+W(5)=46]-.01Y+1.004Z(5)-1.015W(5)-Z(6)+W(6)=-57]-.01Y+1.004Z(6)-1.015W(6)-Z(7)+W(7)=78]-.01Y+1.004Z(7)-1.015W(7)-Z(8)+W(8)=29]-.01Y+1.004Z(8)-1.015W(8)-Z(9)+W(9)=-1510]-.01Y+1.004Z(9)-1.015W(9)-Z(10)+W(10)=-1211]-.01Y+1.004Z(10)-1.015W(10)-Z(11)+W(11)=712]-.01Y+1.004Z(11)-1.015W(11)-Z(12)+W(12)=-459'