运筹学作业及答案.pdf

运筹学作业目录运筹学作业.1第一章 线性规划及单纯形法.3第二章线性规划的对偶理论与灵敏度分析.24第三章运输问题.53第四章目标规划.63第五章整数规划.73第六章非线性规划.85第七章动态规划.94第八章图与网络分析.97第九章网络计划.99第一章线性规划及单纯形法1.1分别用图解法和单纯形法求下列线性规划问题,指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解；当具有限最优解时，指出单纯形表中 的各基可行解对应图解法中可行域的哪一顶点。(1)min z=2xi+3x2(2)max z=3xi+4xi+6x2 62xi+x2 2s.t.4s.t.12Xi,X20Xi,X20(3)max z=10 xi+5-3xi+4%2 9s.t.5xi+2%2 0(4)max z=5xi+6x22xi-%2 2 2s.t.0解：图解法:当X2图解法:该问题无可行解。图解法：单纯形法:在上述问题的约束条件中分别加入松弛变量43，14，化为标准型:max z=lQx1+5x2+Ox3+0 x43x1+4x2+x3=9s.tJ5再+2x2+x4=8 xpx2,x3,x4 0由线性规划问题的标准型可列出单纯初始形表逐步迭代，计算结果如下表所 示：G105009iCBXbbXlX2X3X40X39341030X4852018/5CjZ105000X321/5014/51-3/53/210Xl8/512/501/54CjZ010-25X23/2015/14-3/1410Xl110-1/72/7Cj00-5/14-25/14单纯形表的计算结果表明：X*=,1,O,O)T,Z*=10 x|+5xl=20 单纯形表迭代的第一步得X()=(0,0,9,8儿 表示图中原点0(0,0)单纯形表迭代的第二步得X=(|,0,g,0)。表示图中C点 单纯形表迭代的第三步得X=(L,0,0尸，表示图中与点2图解法：当=%-工2经过点(2,2)时，z取得唯一最优解。6 61.2将下述线性规划问题化成标准形式。(1)min z=-3xx+4x2-2x3+5x4S.tJ4X x 2+2&-%=2 xx+x2-x3+2x4 2、再，2，%3 2 0，X4无约束解：上述问题中令z二z,=其中整0,2 0,则该问题的标准形式为max 2=3为-4x2+2x3-5x4-5%/s.t.s4%+2%3+%=2X+%-&+2%2%+/=14 2%+3x2+&-%4 4%4-4=2(2)min z=2xr-2x2+3x3X+%2+七=4s.t.-2芯+x2-x3 6xr 0,%3无约束解：上述问题中令z，=z,=-xvx3=x3-&：其中七听0,且 2 0,则该问题的标准形式为max z=21i+2x2-%+x3 nX+x?+%_ x3 n 4s.tJ 2x1+x2-x3 f+x3 n+x4=6X；x2,X3%3,x4 01.3对下述线性规划问题找出所有基解,(1)max z=3%+5x2指出哪些是基可行解，并确定最优解。(2)min z=5%-2x2+3x3+2x4S.t.sx1+x3=42x2+x4=123x1+2x2+x5=180 j=l,5S.t.s为+2x2+3x3+4x4=72为+2x2+x3+2x4=3x70(j=l,4)解：(1)该线性规划问题的全部基解见下表中的，打者为基可行解，注*者为最优解，z*=36o序号X1X2X3X4X5Z可行？2620036*4306027q4600-642X094-6045X0640630N004121804001261260-212018X(2)该线性规划问题的标准形式为：max z=5玉+2x2 3巧一2x4x1+2x2+3x3+4x4=7s.tJ 2xr+2x2+x3+2x4=3x.0(，=L,4)其全部基解见下表中的，打者为基可行解，注*者为最优解，/=5o序号X1X2X3X4Zz可行？0011-5*q0-1/202-5X0-1/220-5*-1/30011/6-2X2/5011/50-43/57-411/20031X1.4题L1(3)中，若目标函数变为maxz=cii+d%2，讨论c,d的值如何变化，使该问题可行域的每个顶点依次使目标函数达到最优。c z Z C解：由目标函数maxz=oq+d%2可得：工2二一二再+：=如+：，其中左二一二。a a a a当-士 V左VO时，可行域的顶点A使目标函数达到最优；45 3当二时，可行域的顶点B使目标函数达到最优；2 4当7心一9时可行域的顶点C使目标函数达到最优;当c=O,dVO或cVO,d=O时，最优解为。点。1.6分别用单纯形法中的大M法和两阶段法求解下列线性规划问题，并指出属哪一类解。(1)min z=2为+3x2+x3$+4x2+2x3 8s.t.6x1,x2,x3 0(2)max z=10%+15%+12x3S.tJ5%+3x2+x39-5xr+6x2+15%5x1.x2,x3 0(1)解:大M法：在上述线性规划问题的约束条件中减去剩余变量“也，再分别加上人工变量*6、*7，何1min z=2占+3x2+工+0 x4+0 x5+Mx6+Mx1s.t.0其中M是一个任意大的正数，据此可列出初始单纯形表如下:Cj23100MM9iCbXbbXix2x3x4x5x6x7MX681：42-10102MX763200-1013Cj-Zj2-4M3-6M1-2MMM003X221/411/2-/401/408MX72：5/20-11/2-1-1/214/5CZi5 5“0M 3 1“-MM3 3M 04 224 22 43X29/5013/5-3/101/103/10-1/102Xi4/510-2/51/5-2/5-1/52/5ClZj0001/21/2M-l/2M-l/2由单纯形表的计算结果得：最优解X*二目,0,0,0,0,o1,4 Q目标函数最优值z*=2x+3x=7X存在非基变量检验数q=0，故该线性规划问题有无穷多最优解。两阶段法：先在上述线性规划问题的约束条件中减去剩余变量4号再分别加上人工变量%6，%7,得第一阶段的数学模型min w=x6+x7%+4x2+2x3-x4+x6=8s.tJ 3X1+2x2-x5+x7=6据此可列出单纯初始形表如下:Cj00000119iCbXbbXix2x3x4x5x6x71X681：42-101021X763200-1013Cj-Zj-4-6-211000X221/411/2-1/401/4081X72：5/20-11/2-1-1/214/55120110-2220X29/5013/5-3/101/103/10-1/100Xi4/510-2/51/5-2/5-1/52/5Cj-Zj0000011第一阶段求得的最优解X*0,0,0,0,目标函数的最优值w*=0,因人工变量4=%7=。，所以g,|,ooooo是原线性规划问题的基可行解。于是可以进行第二阶段计算，将第一阶段的最终表中的人工变量取消，并填入原问题的 目标函数的系数，如下表：Cj231009iCbXbbXix2x3x4x532X2X19/54/501103/5-2/5-3/10 1/51/10-2/5Cj0001/21/2由表中计算可知，原线性规戈U问题的最优解x*=q,(oo,o,o,o,目标函数的 最优值z*=2x+3x|=7,由于存在非基变量检验数4=0,故该线性规划问题 有无穷多最优解。(2)解：大M法：在上述线性规划问题的约束条件中加上松弛变量4%5,减去剩余变量%再加上 人工变量年得max z=10+15+12x3+0 x4+0 x5+0 x6-Mx7s.tJ5*+3元2+元3+=9-5%+6元2+15思+元5=152玉+%2+4 一元6+元7=5、%,元2，工3，14，元5，16，X7 20其中M是一个任意大的正数，据此可列出单纯形表如下:Cj101512000-M9iCBXbbXix2x3x4x5X6x70 x49：53110009/50 x515-56150100-Mx7521100-115/2。厂Zj10+2M15+M12+M00-M010Xi9/513/51/51/500090 x524091611003/2-Mx77/50-1/53/5-2/50-117/3IZj09-丝 53 1O+-M52M 50-M0由单纯性表的最终表可以看出，所有非基变量检验数丐0,且存在人工变量10X13/2139/8003/16-1/800012X33/209/1611/161/1600-MX71/20-43/800-7/16-3/80-11Cj-Zj027 43-M8 80021 7-M8 165 3,-M8 80-M0故原线性规划问题无可行解。两阶段法:在上述线性规划问题的约束条件中加上松弛变量减去剩余变量小再 加上人工变量.得第一阶段的数学模型min w=x7s.t.5%+3x2+%+/=9 一5%+6x2+15x3+x5=152xr+x2+x3-x6+x7=5据此可列出单纯初始形表如下:Cj00000019iCbXbbXix2x3x4x5x6X70X49：53110009/50X515-561501001X7521100-115/2Cj-Zj-2-1-1001010Xi9/513/51/51/500090X524091611003/21X77/50-1/53/5-2/50-117/3Cj-Zj0-1/53/5-2/50100Xi3/2139/8003/16-1/80000X33/209/1611/161/16001X71/20-43/800-7/16-3/80-11Cj-Zj0438007/163/8010第一阶段求得最优解x*=13,o弓0,0,0，g），因人工变量X7=g=0，且非基变量检验数 0,所以原线性规划问题无可行解。1.5考虑下述线性规划问题：max z=。1玉+c2x2auxr+ai2x2 b、s.t.6z21xx+a22x2 0式中,193,4。26,1即3,2%25,8412,24214,44226,10214,试确定目标函数最优值的下界和上界。解：（1）上界对应的模型如下（c,b取大，a取小）max z=3xx+6x2 s.t.lxx+2x2 12 25+4x2 O最优值（上界）为：21；（2）下界对应的模型如下（c,b取小，a取大）max z=jq+4x23天+5x2 8s.t.v 4玉+6x2 O最优值（下界）为：6.4o1.7 已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到表L21,试 求括弧中未知数/的值。表 1-21项目X1X2X3x4X5X46(b)(c)(d)10X51-13(e)01CZj(a)-1200X1(f)(g)2-11/20X54(h)(i)11/21Cj-Zj0-7(J)(k)(1)解：abcdefgh ijk 1324-22310 5-5-3/2 01.8 若X,X均为某线性规划问题的最优解，证明在这两点连线上的所有点也 是该问题的最优解。证明：设不口 茜足：maxz=CTX AX=b O对于任何Ova vl,两点连线上的点才满足：X=aX+(1-a)*也是可行解，且 CTX=CTaXm+Cr(l-6i)X(2)=CTaXw-aCTX(2)+CrX(2)=C=(2)所以X也是最优解。1.9考虑线性规划问题max z-axx+2x2+x3-4x4为十12-x4=4+2夕S.t.0(ii)模型中圆分为参数，要求:组成两个新的约束=+(ii),(ii)=(ii)-2，根据式，和式(ii),以%1，42为基变量，列出初始单纯形表;(i)&+鼻-%4=3+2夕解：夕Cj_a21-4CB基bXlX2X3X4aXl3+20101-12X2l-p01-10Cj-Zj003-aa-4在表中，假定4=。,则。为何值时，/，2为问题的最优基；解：如果=0,则当3VaV4时，%,%为问题的最优基变量。在表中，假定。=3,则尸为何值时，为问题的最优基。解：如果。=3,则当-14/时，%,%为问题的最优基变量。1.10试述线性规划模型中“线性”二字的含义，并用实例说明什么情况下线性 的假设将被违背。答：线性的含义：一是严格的比例性，如生产某产品对资源的消耗量和可获取 的利润，同其生产数量严格成比例；二是可叠加性，如生产多种产品时，可获 取的总利润使各项产品的利润之和，对某项资源的消耗量应等于各产品对该资 源的消耗量之和；三是可分性，即模型中的变量可以取值为小数、分数或某一 实数；四是确定性，指模型中的参数5,此,b均为确定的常数。很多实际问题往往不符合上述条件，例如每件产品售价3元，但成批购买 就可以得到折扣优惠。1.11 判断下列说法是否正确，为什么？含n个变量m个约束的标准型的线性规划问题，基解数恰好为C/个；答：错误。基本解的个数二基的个数4c：线性规划问题的可行解如为最优解，则该可行解一定为基可行解；答：错误。当有唯一最优解时，最优解是可行域顶点，对应基本可行解；当有无穷多最优解时，除了其中的可行域顶点对应基本可行解外，其余最优解不 是基本可行解。如线性规划问题存在可行域，则可行域一定包含坐标的原点；答：错误。如果约束条件中有一个约束所对应的区域不包含坐标的原点，则 即使有可行域，也不包含坐标的原点。(4)单纯形法迭代计算中，必须选取同最大检验数%0对应的变量作为换入 基的变量。答：错误。若此时最大检验数%0,可是Pj0为某一常数，分别讨论下列情况时最优解的变化。(1)目标函数变为max z=4CX；(2)目标函数变为maxz=(C+X)X；(3)目标函数变为maxz=X,约束条件变为AX=助。A解：最优解不变；C为常数时最优解不变，否则可能发生变化；最优解变为:X/入。1.13某饲养场饲养动物出售，设每头动物每天至少需要700g蛋白质、30g矿物 质、1001ng维生素。现有五种饲料可供选用，各种饲料每kg营养成分含量及单 价如表1-22所示。表 1-22饲料蛋白质/g矿物质/g维生素/mg价格/(元/kg)1310.50.2220.51.00.7310.20.20.446220.35180.50.80.8要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。解：设七表示第，种饲料数量，;123,4,5min 2=0.2内+0.7x2+0.4x3+0.3x4+0.8x53xt+2x2+x3+6x4+1 8x5 700jq+0.5x2+0.2x3+2x4+0.5x5 300.5%+x2+0.2x3+2x4+0.8X5 100 xt 0,/=1,2,3,4,5最优解为 =刍=。，Z=39.74,x5 25.64,2=32.44（兀）1.14辽源街邮局从周一到周日每天所需的职员人数如下表1-23所示。职员分 别安排在周内某一天开始上班，并连续工作5天，休息2天。表1-23 人周-二四五六日所需人数17131519141611要求确定：该邮局至少应配备多少职员，才能满足值班需要；因从周一开始上班的，双休日都能休息；周二或周日开始上班的，双休日 内只能有一天得到休息；其他时间开始上班的，两个双休日都得不到休息，很 不合理。因此邮局准备对每周上班的起始日进行轮换（但从起始日开始连续上5 天班的规定不变），问如何安排轮换，才能做到在一个星期内每名职工享受到同 等的双休日的休假天数；该邮局职员中有一名领班，一名副领班。为便于领导，规定领班于每周一、三、四、五、六上班，副领班于一、二、三、五、日这5天上班。据此试重新 对上述要求和建模和求解。解：（1）设x#=l,2,7）表示星期一至星期天开始上班的人数，则建立如下 的数学模型。目标函数:min z=%+/+&+/+/+4约束条件：st 19%+马+%+/+%214 x5+xx+x2+x3+x4 16 x6+x2+x3+x4+x5 11 x7+x3+x4+x5+x6 17 xpx2,x3,x4,x5,x6,x7 0解得最优解为 X*=(7,4,2,8,0,2,0),z*=23则该邮局至少应配备23名职员，才能满足值班需要。对这23名职工分别编号，。，以23周为一个周期，这23名 职工上班安排见下表。此时只需在每天人数中减去领班和副领班两人即可，重现建模如下:每周上班 时间起止周职工职工职工职工职工周一周五1-72816 2217 2323,1-6周二周六81191223,1-31-4710周三周日12 1313 144556H12周四卜周14 2115 2261371413 20周五下周二22 2323,114 1515 1621-22min z=X+x2+x3+x4+x5+x6+a:7s.t.15 xx+x2+x5+x6+x1 12 X1+%2+%3+4+%7-13X1+12+%3+%+%7 2 18X1+12+X3+Z+%5 2 1212+%3+%4+%5+%6 2 16%3+/+毛+%+10、%1，%3，%4，15，%6，%7。1.15 一艘货轮分前、中、后三个舱位，它们的容积与最大允许载重量如表-24 所示。现有三种货物待运，已知有关数据列于表l-25o又为了舱运安全，前、中、后舱的实际载重量大体积保持各舱最大允许载 重量的比例关系。具体要求：前、后舱分别与中舱之间载重量比例的偏差不超 过15%,前、后舱之间不超过10%。问该货轮应装载A、B、C各多少件运费收入 为最大？试建立这个问题的线性规划模型。表 1-24项目前舱中舱后舱最大允许载重量/t200030001500容积/HP400054001500表 1-25商品数量/件每件体积4m3/件）每件重量/（小牛）运价/（元/件）A6001081000B100056700C80075600解：用i=l,2,3表示A、B、C三种货物，j=l,2,3表示前、中、后三个舱,用x(i,j)表示货物i在舱j的装载量。max z=lOOO(XlJ)+x(l,2)+x(l,3)+700(x(2,l)+x(2,2)+x(2,3)+600(x(3,l)+x(3,2)+x(3,3)商品数量约束：1)x(l51)+x(l,2)+x(l,3)6002)x(2,1)+x(2,2)+x(2,3)10003)x(3,1)+x(3,2)+x(3,3)800商品容积约束：4)10 x(1,1)+5x(2,1)+7x(3,1)40005)10 x(l,2)+5x(2,2)+7x(3,2)54006)10 x(1,3)+5x(2,3)+7x(3,3)1500最大载重量约束：7)8x(l,l)+6x(2,1)+5x(3,1)20008)8x(l,2)+6x(2,2)+5x(3,2)30009)8x(l,3)+6x(2,3)+5x(3,3)1500重量比例偏差约束：10)8x(l,l)+6x(2,1)+5x(3,l)1(l-0.15)(8x(l,2)+6x(2,1)+5x(3,2)12)8x(L 3)+6x(2,3)+5x(3,3)1-(1-0.15)(8x(l,2)+6x(2,1)+5x(3,2)314)8x(l,3)+6x(2,3)+5x(3,3)-(l-0.1)(8x(l,l)+6x(2,1)+5x(3,1)41.16长城通信公司拟对新推出的一款手机收费套餐服务进行调查，以便进一步 设计改进。调查对象设定为商界人士及大学生，要求：总共调查600人，其 中大学生不少于250人；方式分电话调查和问卷调查，其中问卷调查人数不 少于30%；对大学生电话调查80%以上应安排在周六或周日，对商界人士电话 调查80%以上应安排在周一至周五；问卷调查时间不限。已知有关调查费用如 表1-26所示，问该公司应如何安排调查，使总的费用为最省。元/人次表 1-26调查对象电话调查问卷调查周一至周五周六、日大学生3.02.55.0商界人士3.53.05.0解：设/，/为周一至周五对大学生和商界人士电话调查人数，/，元22为双休日对上述 人员电话调查人数，%，%23分别为问卷调查人数，则数学模型为minz=3.0再 1+2.5 再2+5.0 x13+3.5x21+3.0 x22+5.0 x23s.tJ再 1+X12+再 3+X21+X22+X23=600Xn+xi2+xi3-250 x13+x23 180-0.8无X 2-0.8、%21+412最优解=0,x12=350,x13=0,x21=58,x22=11,x23=180,z*=20141.17生产存储问题。某厂签订了 5种产品（i=L，5）上半年的交货合同。已知各产品在第j月（j=l,，6）的合同交货量为，该月售价s,、成本价%及生产1件时所需工时加。该厂第j月的正常生产工时为j但必要时可加班生产，第j月允许的最多加 班工时不超过t，并且加班时间内生产出来的产品每件成本增加额外费用Ci/元。若生产出来的产品当月不交货，每件库存1个月交存储费Pi元。试为该厂 设计一个保证完成合同交货，又使上半年预期盈利总额为最大的生产计划安排。解：设.为，种产品/月正常时间生产数，%.为加班时间生产数，模型为5 6 5 6 jmaxz=0）%.+（s厂c厂q，勺 化（%+/，左）i=l j=l c=l j=l k=l5E%u=t,6）C=15 u=t S.tJ m%+/）之2（万 L,6）k=l k=lXij-01.18 宏银公司承诺为某建设项目从2003年起的4年中每年年初分别提供以下 数额贷款：2003年一100万元，2004年一150万元，2005年一120万元，2006 年一110万元。以上贷款资金均需于2002年年底前筹集齐。但为了充分发挥这 笔资金的作用，在满足每年贷款额情况下，可将多余资金分别用于下列投资项 目：于2003年年初购买A种债券,期限3年,到期后本息合计为投资额的140%,但限购60万元；于2003年年初购买B种债券,期限2年,到期后本息合计为投资额的125%,且限购90万元；于2004年年初购买C种债券，期限2年,到期后本息合计为投资额的130%,但限购50万元；（4）于每年年初将任意数额的资金存放于银行，年息4%,于每年年底取出。求宏银公司应如何运用好这笔筹集到的资金，使2002年年底需筹集到的资金数 额为最少。解：用（为第1,2,3年年初，/=1,2,3,4分别为A,B,C,D四类投资数）min 2=480+(xn+xn+x13+%区)+(x21+x22+jc23+4)+(&i+32+33+x34)xH+(1+140%)110 xn 120 x12 1103 V 50(xn+x12+x13+x14)(1+4%)100区1+2+%23+%24)Q+4%)150(X31+X32+冗33+x34)(l+4%)1201.19 红豆服装厂新推出一款时装，据经验和市场调查，预测今后6个月对该款时装的需求 为：1 月一3000 件，2 月一3600 件，3 月一4000 件，4 月一4600 件，5 月一4800 件，6 月一 5000件。生产每件需熟练工人工作4h,耗用原材料150元，售价为240元/件。该厂1月初 有熟练工80人，每人每月工作160h。为适应生产需要，该厂可招收新工人培训，但培训一 名新工人需占用熟练工人50h用于指导操作，培训期为一个月，结束后即可上岗。熟练工人 每月工资2000元，新工人培训期间给予生活补贴800元，转正后工资与生产效率同熟练工 人。又熟练工人（含转正一个月后的新工人）每月初有2%因各种原因离职。已知该厂年初 已加工出400件该款时装作为库存，要求6月末存库1000件。又每月生产出来时装如不在 当月交货，库存费用为每件每月10元。试为该厂设计一个满足各月及6月末库存要求，又 使16月总收入为最大的劳动力安排方案。解：设该厂每月初拥有熟练工人数不=,6）,每月招收培训的新工人数为小 该厂月末库存为。一月初库存为却凡为各月对时装的需求数，则数学模型为6maxz=f（每月销售收入-熟练工人工资-培训工人补助-原材料费-库存费）i=lS.tJIt_1+40 xt-n.5ytRt/,=17+40为+4041+12.5%4%1=0.9弭+%”20解得z*=875122元，各月有关数字如下:ti23456Xt8082.47106.62130.93128.32125.75yt4.0725.8026.45000it559.3400637.38970.021000第二章线性规划的对偶理论与灵敏度分析2.1 写出下列线性规划问题的对偶问题，并以对偶问题为原问题，再写出对偶的 对偶问题。(1)min z=2七+2x2+4x3x1+3x2+4x3 22x1+x2+3x3 3s.t J项+4x2+3x3=5项，工2之。，尤3无约束解：对偶问题：max vp=2必+3y2+5X、+2t2+丁3 423必+丁2+4、3 0,y2 22ml+m2+3m3 3s.t J+4m2+3m3=5人，加230,人无约束(2)max z=5xr+6x2+3x3xr+2x2+2x3=5Xy+5%2 3s.tJ4项+7%+3/0,x3 0解：对偶问题:minw=5%+3为+8%&_%+4%=52%+5y2+7%2 6S.t.52%-3y2+3%K 3%无约束，0对偶的对偶问题:max v=5ml+6m2+3m3阴+2m2+2/=0mx+5m2 3m3 0S.t.4ml+7m2+3m3 0,m3 0(i=l,m,j=L，九）m n解：对偶问题:maxw=+Z”/匕+根，T j=l+(i=l,m,j=l,n)1%无限制，i=l,n+mm n对偶的对偶问题：minv=E2六1nZ%=q（i=L，加）六1ms.qz/a o=l)i=lXtj 0(z=1,，以 j=l,，九）n(4)max z=Z cjxjj=inSa.x.0%.无约束 J(，=1,m)(1=+1,g+2,m)(/=1,，/v)(/=+1,)解:对偶问题：min w=Ay+%+bmymmi=l=c.i=lj无约束(J=L2,%)(/=+L/+2,n)(i=L 四)。=叫+1,m)对偶的对偶问题:max 2=汇c.x.j=inj=ins.t.0勺无约束(，=1,m1V(，=叫+1,叫+2,(/=1,，勺 v)。=勺+1,),加)2.2判断下列说法是否正确，并说明为什么。如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解；答：错误。如果原问题是无界解，则对偶问题无可行解。如果线性规划的对偶问题无可行解，则原问题也一定无可行解；答：错误。如果对偶问题无可行解，也可能是因为原问题是无界解。在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问 题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值；答：错误。如果原问题是求极小，则结论相反。任何线性规划问题具有唯一的对偶问题。答：正确。2.5已知某求极大线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如表2-30所示，求表中各括号内未知数(a)的值。Cj 一322000CB基bXlX2X3X4X5X60X4(b)1111000X515(a)120100X6202(c)1001CrZj3220000X45/400(d)(1)-1/4-1/43Xl25/410(e)03/4(i)2X25/201(f)0(h)1/2Cj%0(k)(g)0-5/4(j)解：1=1,k=0,a=2,c=3,h=-l/2,b=10,e=5/4,f=-l/2,d=l/4,g=-3/4,i=-l/4,j=-l/4.2.6给出线性规划问题min z=21+3x2+5x3+6x4%+2x2+3x3+x4 2S.t.(J=L,4)写出其对偶问题；用图解法求解对偶问题；利用的结果及根据对偶问 题性质写出原问题最优解。解：其对偶问题为：min w=2M 3y2S.tJM 2%-2 2 M+为 2-3 3M-h 2-5 M+3y2 N-6 J ，2。图解法求解:求得最优解为x=一|,%=*=（3）根据互补松弛型性质可以得到最优解X*=（7/5,0,1/5,0）2.7 给出线性规划问题max z=3项+2x2+5x3项+2x2+x3 5003xa+2占 460s.tJ项+4x2 0写出其对偶问题；利用对偶问题性质证明原问题目标函数值zV1360 o解：其对偶问题为：min w=500%+460%+420y33%+为 2 32y1+4y3 2s.tJ 3+2%*J，%，%2。易得x=o,%=，%=（是对偶问题的一个可行解，带入目标函数得 坟=1360，故原问题的目标函数值zV1360。2.8 已知线性规划问题max z=玉+/一%+/+巧2S.t.0试根据对偶问题性质证明上述线性规划问题目标函数值无界。解：%=2,%=%3=0是原问题的一个可行解，原问题的对偶问题为：min w=2y1+y2-yi-2y2l(1)%+y2l(2)s.tJ%-%2。(3)(4)由于和是矛盾约束，故对偶问题无可行解。所以原问题目标函数值无界。2.9给出线性规划问题max z=2xr+4x2+x3+x4玉+3x2+x4 82xr+x2 6s.t.x2+x3+x4 6+x2+x3 0(，=L,4)要求：写出其对偶问题；已知原问题最优解为X*=(224,0),试根据对偶理论，直接求出对偶问题的最优解。解：其对偶问题为：min w=8yl+6y2+6y3+9y4s.tJ%+2%+%之23M+y2+y3+y4 1%+%2 1M+%21 yj0(j=l,4)已知原问题最优解为X*=(2,2,4,0),带入原问题，第4个约束不等式成立，故为二。又由于石,元2，天大于。，上面对偶问题前3个约束取等号，故4 3得到最优解：y*=2.10已知线性规划问题A和B如下:问题A几max 2=Z cjxjj=iS.t.vn工。3=。j=inj=lnZ二4 j=iXj 0(/=1,问题B影子价格X乃%,n）max 2=cjxj 影子价格/=inH5aijXj=5bl 义J=1vl 1,jL7a2JXJ=b2%st,j=i 3 3n=4+34%y=iXj 0(j=l,n)试分别写出凡同y（，=1,2,3）间的关系式。解：571=-1，572=523=）；3+-）；1.2.11用对偶单纯形法求解下列线性规划问题。(1)minz=4xt+12x2+18x3(2)min z=5%+2x2+4x3x1+3x3 3s.tJ 2x2+2x3 5s.tJxvx2,x3 03%i+/+2%2 46为+3x2+5x3 10 xpx2,x3 0解：先将问题改写为:max z 二4为一2-18x3+0 x4+Ox5S.t.s一再3=+44 32%2 2思+二 一5再,工2，工3，工4，/5-0列出单纯形表，用对偶单纯形法求解步骤进行计算过程如下:Cj 一-4-12-1800Cb 基 bX1X2X3X4X50 x4-3-10-3100 x5-50-2-201Cj-Zj-4-12-18000 x4-3-10-310-12 x2 5/201101/2Cj-Zj-40-60-6-18 x3 11/301-1/30-12 X2 3/2-1/3101/3-1/2Cj-Zj-200-2-6由上表可得原问题最优解为x*=（o1,1）,代入目标函数得z=36o 先将问题改写为：.maxz=-5%i-212-4x3+0 x4+0 x5S.tJ3xy-%2思+%二 一46%34 5思+/二10 再，42，43，44，元5-0列出单纯形表，用对偶单纯形法求解步骤进行计算过程如下:Cj 一-5-2-400CB基bXlX2X3X4X50X4-4-3-1-2100X5-10-6-3-501Cj-Zj-5-2-4000X4-2/3-10-1/311/3-2X210/3215/301/3c/j-10-2/302/3-5Xl2/3101/3-1-1/3-2X2201124/3CjZ00-1/3-11/322由上表可得原问题最优解为X*=(g,2,0),代入目标函数得Z 二，2.12考虑如下线性规划问题:min 2=60X1+40 x2+80 x3s.tJ31i+2x2+x3 24玉+x2+3x3 421i+2x2+2x3 3x2,x3 0要求：写出其对偶问题；用对偶单纯形法求解原问题；用单纯形法求解 其对偶问题；对比与中每步计算得到的结果。解：其对偶问题为：max w=2y+4y2+3y3 3yl+4y2+2y3 60 2%+为+2%40s.t.y1+3y2+2y3 80，之先将问题改写为max z=60%1 40%一 8。%+。4+。15+。6S.t.-3%22-%+14=-24X x2 3%+七=4_2X 22 2%+/=-3%1，%2，%3，%4，15，46 N0列出单纯形表，用对偶单纯形法求解步骤进行计算过程如下:Cj 一-60-40-80000CB基bX1X2X3X4X5X60X4-2-3-2-11000X5-4-4-1-30100X6-3-2-2-2001CjZ-60-40-800000X411/6005/311/3-5/6-60X15/6102/301/31/6-40X22/3011/30-1/3-2/3CjZ00-80/30-20/3-50/3s 9 230由上表可得原问题最优解为x*=（）,4,0）,代入目标函数得z二一厂。6 3 j用单纯形法求解其对偶问题：Cj 一243000CB基bX1X2X3X4X5X60X4603421000X5402120100X680132001CjZ2430004X220/31/3101/3-1/303X350/35/601-1/62/300X680/3-5/300-2/3-1/31CjZ-11/600-5/6-2/30由上表可得对偶问题最优解为X*=(0,3，学，代如目标函数W二7。2.13已知线性规划问题：max z=2xr-x2+x3+x2+x3 6s.tJ-xr+2x2 0先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。目标函数变为max z=2%+3%2+%3；约束右端项由4变为4;增添一个新的约束条件-X+2%22。解：先用单纯形法计算如下：Cj 一2-1100CB基bXlX2X3X4X50X46111100X54-12001Cj-Zj2-11000Xl611110-1X51003111Cj-Zj0-3-1-20由上表可得最优解为再=6,%2=。，%3=。，2*=12（1）当目标函数变为1112乂2=2玉+3%2+%3时，反映到最终单纯形表上 如下表所示：因变量X2的检验数大于零，故需继续用单纯形法迭代计算得下表:Cj 一23100Cb 基 bXlX42 x；6111100 x5 1003-111CrZj01-1-20Cj 一23100Cb 基 bXlX4X52 x2 8/3102/32/3-1/33 x2 10/3011/31/31/3*000-3-1由上表可得最优解变为x=|,=$3=0，z*W一一 nn_3|4-因有 AZ?二,W BrW _0 J 1 1。-3_将其反映到最终单纯形表中如下表所示：Cj 一23100Cb 基 bX1X42 3111100 x5 703-111CrZj01-1-20由表可得最优解为X=3,=。，%3=。*=6先将原问题的最优解玉=6,%=0,%3=。带入新增约束条件一%+2%2 中，因-6+2x0=-6W2故原问题最优解发生改变。给新增约束条件中加入松弛变量并规范化得：玉+%6 -2以X6为基变量，将上式反映到最终单纯形表中得下表：因上表中XI列不是单位向量，故需进行变换，得下表:Cj 一2-11000Cb 基 bX1X2X3X4X5X62 xi 61111000 x5 100311100 x6-210-2001CrZj0-3-1-200Cj 一2-11000Cb 基 bX1X2X3X4X5X62 xi 61111000 X5 100311100 x6-80-1-3-101Cj-Zj0-3-1-200因上表中对偶问题为可行解，原问题为非可行解，故用对偶单纯性法迭代计算 得下表：Cj 一2-11000CB基bX1X2X3X4X5X62X110/312/302/301/30X522/308/302/311/30X38/301/311/30-1/3C