线性规划的对偶

第四章线性规划的对偶理论一、 填空题线性规划问题具有对偶性，即对于任何一个求最大值的线性规划问题，都有一个求最小值/极小值的线性规划问题与之对应，反之亦然。在一对对偶问题中，原问题的约束条件的右端常数是对偶问题的目标函数系数。如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为等式_。.对偶问题的对偶问题是原嶂_。.若原问题可行，但目标函数无界，则对偶问题不可行。若某种资源的影子价格等于k。在其他条件不变的情况下（假设原问题的最佳基不变），当该种资源增加3个单位时。相应的目标函数值将增加3k。线性规划问题的最优基为B，基变量的目标系数为C，则其对偶问题的最优解丫*=_0号1。若X•和Y•分别是线性规划的原问题和对偶问题的最优解，则有CX•二Y*b。若X、Y分别是线性规划的原问题和对偶问题的可行解，则有CXWYb。若X•和Y•分别是线性规划的原问题和对偶问题的最优解，则有CX*=Y±b。设线性规划的原问题为maxZ=CX，AxWb，XN0，则其对偶问题为min=Yb_ _。影子价格实际上是与原问题各约束条件相联系的对偶变量的数量表现。线性规划的原问题的约束条件系数矩阵为A，则其对偶问题的约束条件系数矩阵为AL。在对偶单纯形法迭代中，若某«<0，且所有的aij^0（j=1，2，„n），则原问题_无解。二、 单选题 1 1J线性规划原问题的目标函数为求极小值型，若其某个变量小于等于0，则其对偶问题约束条件为A形式。业.亨”B.“W”C，">”D.“=”设x、r分别是标准形式的原问题与对偶问题的可行解，则4。A.CX>yb B.CX=ybC.CX<yb D.CX^yb对偶单纯形法的迭代是从_△_开始的。A.正则解 B.最优解 C.可行解D.基本解如果z。是某标准型线性规划问题的最优目标函数值，则其对偶问题的最优目标函数值w*A。A.W*=Z*B.W*#Z* C.W*WZ* D.W*NZ*如果某种资源的影子价格大于其市场价格，则说明堕A.该资源过剩B.该资源稀缺C.企业应尽快处理该资源D.企业应充分利用该资源，开僻新的生产途径三、 多选题1.在一对对偶问题中，可能存在的情况是ABC。A•一个问题有可行解，另一个问题无可行解 B.两个问题都有可行解两个问题都无可行解 D.一个问题无界，另一个问题可行下列说法错误的是『。A.任何线性规划问题都有一个与之对应的对偶问题B.对偶问题无可行解时，其原问题的目标函数无界。C.若原问题为maxZ=CX，AXWb，XN0，则对偶问题为minW=Yb，YANC，Y甘。D.若原问题有可行解，但目标函数无界，其对偶问题无可行解。如线性规划的原问题为求极大值型，则下列关于原问题与对偶问题的关系中正确的是BCDE。A原问题的约束条件“N”，对应的对偶变量“N0”B原问题的约束条件为“=”，对应的对偶变量为自由变量C.原问题的变量“N0”，对应的对偶约束“N”D.原问题的变量“WO”对应的对偶约束“W”E.原问题的变量无符号限制，对应的对偶约束“=”一对互为对偶的问题存在最优解，则在其最优点处有BDA.若某个变量取值为0，则对应的对偶约束为严格的不等式B.若某个变量取值为正，则相应的对偶约束必为等式C.若某个约束为等式，则相应的对偶变取值为正D.若某个约束为严格的不等式，则相应的对偶变量取值为0E.若某个约束为等式，则相应的对偶变量取值为0下列有关对偶单纯形法的说法正确的是ABCD。A.在迭代过程中应先选出基变量，再选进基变量B.当迭代中得到的解满足原始可行性条件时，即得到最优解C.初始单纯形表中填列的是一个正则解D.初始解不需要满足可行性E.初始解必须是可行的。根据对偶理论，在求解线性规划的原问题时，可以得到以下结论ACD。A.对偶问题的解B.市场上的稀缺情况C.影子价格D.资源的购销决策E.资源的市场价格7.在下列线性规划问题中，皿采用求其对偶问题的方法，单纯形迭代的步骤一般会减少。A.maxZ=2xtA.maxZ=2xt+4x2+X3+gX】+3x2+右<82xi+x2W6X2+X3+z<6X】+X2+X3<9七20。=1,2,3,4)B.maxZ=X]+x2，_X[+X2+X3W2s.M-2xi+X2-X3W1、xi,x2,x3^0C.maxZ—3x]+2x2，一X[+2x2<43x]+2x2<14s.trsX]-X2W3%,x2^0tninZ=3xt+2x2+x3Xi+X2+X3W6Xi一x324S，^x2-x3>3X],x2,x3^0maxZ=4xi+10x2

3xi+6x2<5

xt+3x2<2S.X-—,2xi+5x2<4g,x2^0四、 名词、简答题1、 对偶可行基：凡满足条件＜5=C-CbB-iAW0的基B称为对偶可行基。2、 .对称的对偶问题：设原始线性规划问题为maxZ=CXs.tJAXWbLX河称线性规划问题minW=Yb s.tgYANCLYN0 为其对偶问题。又称它们为一对对称的对偶问题。3、 影子价格：对偶变量匕表示与原问题的第i个约束条件相对应的资源的影子价格，在数量上表现为，当该约束条件的右端常数增加一个单位时（假设原问题的最优解不变），原问题目标函数最优值增加的数量。4、 影子价格在经济管理中的作用。（1）指出企业内部挖潜的方向；（2）为资源的购销决策提供依据；（3）分析现有产品价格变动时资源紧缺情况的影响；（4）分析资源节约所带来的收益；（5）决定某项新产品是否应投产。5、 线性规划对偶问题可以采用哪些方法求解？（1）用单纯形法解对偶问题；（2）由原问题的最优单纯形表得到；（3）由原问题的最优解利用互补松弛定理求得；（4）由Y*=CbB-i求得，其中B为原问题的最优基6、 一对对偶问题可能出现的情形：1.原问题和对偶问题都有最优解，且二者相等；2.一个问题具有无界解，则另一个问题具有无可行解；3.原问题和对偶问题都无可行解。五、 写出下列线性规划问题的对偶问题1.minZ=2X]+2xj4x33.minZ=SZx.+3xi-5xj^2-说Zx.+3xi-5xj^2-说+7xj<3出—+电*5x47xi+风-3为=-4力、=2=1,2,JT",m)国+4跖+6mj^5-—■ s.F=b(j=1»2,i«l•,•n)lx】,xt+Xj^0也「电却心无符号限制.Xij20(i=1,2，…,m,j=l,2,•••：!)2.0.13x2=21^-询中3却+&IB"*'吧1:%嘤‘也+3>：*aW3■5・L11'-W■+7光*占以』2|CIEHWPT-4为4-,方+7无+北点-电，十为=-IS~Ji5s3W4%=1无符皓BISI,丸球03.maiW=四+U=1叱+匕a$,t：上匕滞号糠{i=1,2产，丽=六、已知线性规划问题maxZ=4xi+7x?+2x3Xi+2x2+X3V10t+3x2+maxZ=4xi+7x?+2x3Xi+2x2+X3V10t+3x2+3x3W10x2,x3>0应用对偶理论证明该问题最优解的目标函数值不大于25证明三版向跋对佰MIJtH为LfnijiW=10^3+10^.'3皿+**m42^.*6争噫,vii-j^tMQ叫脱察可带对儡问Jttjj的一HI行解 Y={1/2,相斑的日稀谢澈为市窗对他理说可待Z'-W<W-七、已知线性规划问题maxZ=2Xi+x2+5x3+6x4]2xi+X3+、V8s.r2xj+2x2+X3+2g<12^>00=1,2,3,4)其对偶问题的最优解为Y「=4,厂=1,试应用对偶问题的性质求原问题的最优解。r*>'心=mf国察*心心侦。^¥祐冬F电秘/尊s/je、寇7-54I■弋蜻攻岐晶n.祢|顿.彖!■怎氟>*■■■- n七、用对偶单纯形法求解下列线性规划问题:1.minZ=X]+X2]2xi+x?24s.XXi+7乂227Ixj,x2^02.minZ=3x】+2x2+x3X]+X2+X3<6xl-x324x2一x3N4、X1,x2,x3^0八、已知线性规划问题maxZ=2xi+4x2+X3+gxt+3x2+g<82xi+<6s.HX2+X3+X4M6X[+X2+X3<9x,20(j=l,2,3,4)

⑴写出其对偶问题 (2)已知原问题最优解为X*=(2,2,4,0)T试根据对偶理论，直接求出对偶问题的最优解。