第二章-对偶问题

2020/11/17--第2章对偶问题----1--第二章线性规划的对偶理论Duality对偶DualProblem对偶问题DualLinearProgramming对偶线性规划DualTheory对偶理论2020/11/172例甲方生产计划问题：ⅠⅡ能力设备A2212设备B4016设备C0515利润23Ⅰ，Ⅱ各生产多少,可获最大利润?乙方租借设备：甲方以何种价格将设备A、B、C租借给乙方比较合理？请为其定价。2.1问题的提出--第2章对偶问题--0,1551641222212121xxxxxx2132maxxxZ2020/11/173而就乙方而言，希望甲方的租金收入在满足约束的条件下越小越好，这样双方才可能达成协议。于是得到下述的线性规划模型：解：假设A、B、C的单位租金分别为，所以生产产品Ⅰ的资源用于出租时，租金收入应满足：24221yy类似的，生产产品Ⅱ的资源用于出租时，租金收入应满足：35231yy总的租金收入：321151612yyy321151612minyyyW242.21yyts0,,35232131yyyyy--第2章对偶问题--思路：就甲方而言，租金收入应不低于将设备用于自己生产时的利润。321,,yyy原问题的对偶问题2020/11/17--第2章对偶问题----4--例：某企业计划生产甲、乙两种产品，该两种产品均需经A、B、C、D四种不同设备加工，按工艺资料规定，在各种不同设备上的加工时间及设备加工能力、单位产品利润如表中所示。问：如何安排产品的生产计划，才能使企业获利最大?设备产品ABCD单位利润甲产品乙产品2212400423加工能力12816122020/11/17--第2章对偶问题----5--1.最大生产利润模型设企业生产甲产品为X1件，乙产品为X2件，则maxz=2X1+3X2s.t2X1+2X212X1+2X284X1164X212X10,X202.资源最低售价模型(原问题)========(对偶问题)设第i种资源价格为yi,（i=1,2,3,4,）则有minw=12y1+8y2+16y3+12y4s.t2y1+y2+4y3+0y422y1+2y2+0y3+4y43yi0,(i=1,2,3,4)y1y2y3y42020/11/17--第2章对偶问题----6--2.2原问题与对偶问题的关系一般表示式：原问题：maxz=c1X1+c2X2+┈+cnXns.ta11X1+a12X2+┈+a1nXnb1a21X1+a22X2+┈+a2nXnb2·······················am1X1+am2X2+┈+amnXnbmxj0，j=1,2,┈,n对偶问题：minw=b1y1+b2y2+┈+bmyms.ta11y1+a21y2+┈+am1ymc1a12y1+a22y2+┈+am2ymc2·························a1ny1+a2ny2+┈+amnymcnyi0，(i=1,2,···,m)1y2ymy1x2xnx2020/11/17--第2章对偶问题----7--典式模型对应对偶结构矩阵表示（1）maxz=CXs.tAXbX0minw=Ybs.tYACY0对偶问题原问题0maxXbAXCXZ0minYCYAYbWTTT123[,,...,]TYyyy123[,,...,]Yyyy这是规范形式的原问题，由此写出其对偶问题如右方所示，那么，当原问题不是规范形式时，应如何写出其对偶问题？可以先将原问题化成规范的原问题，再写出对偶问题。2020/11/17--第2章对偶问题----8--对偶模型其他结构关系（2）若模型为maxz=CXs.tAXbX0maxz=CXs.t-AX-bX0变形minw=Ybs.tYACY0Minw=Y´(-b)st.Y´(-A)CY´0令Y=-Y´对偶问题对偶变量Y2020/11/17--第2章对偶问题----9--（3）maxz=CXs.tAXbX0变形设X=-X´max=-CX´st.-AX´bX´0minw=Ybs.tYACY0则有minw=Ybs.t-YA-CY02020/11/17--第2章对偶问题----10--对偶问题典式：用矩阵形式表示：（1）maxz=CXminw=Ybs.tAXb========s.tYACX0Y0（2）maxz=CXminw=Ybs.tAXb========s.tYACX0Y0（3）maxz=CXminw=Ybs.tAXb========s.tYACX0Y011等式、无约束情况的对偶：max..0ZCXAXbstX原问题min..WYbYACstY无约束对偶问题12推导:max..0ZCXAXbstAXbXmax..0ZCXAbXstAbX原问题化为：即：13根据对称形式的对偶模型,可直接写出上述问题的对偶问题:121212min(..0,0bW(Y,Y)-bAY,Y)CstAYY14121212min..00W(YY)b(YY)ACstY,Ymin..WYbYACstY无约束令，得对偶问题为：12YYY2020/11/17--第2章对偶问题----15--原问题与对偶问题关系表原问题(对偶问题)对偶问题(原问题)目标函数系数约束右端项约束右端项目标函数系数约束条件系数列向量A约束条件系数行向量AT变量个数约束条件个数maxmin变量xj:约束方程i:xj0xj无约束=xj0约束方程:变量yi:yi0=yi无约束yi02020/11/17--第2章对偶问题----16--2.3对偶问题的基本性质Maxz=CXMinw=Ybst.AXbst.YACX0Y0(1)弱对偶性：若X0——原问题可行解，Y0——对偶问题可行解则CX0Y0b证明：∵Y00，AX0b，∴Y0AX0Y0b，而Y0AC，∴CX0Y0AX0，∴CX0Y0AX0Y0b推论1:原问题任一可行解的目标函数值是其对偶问题目标函数值的下届；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。推论2:在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；反之不成立。这也是对偶问题的无界性。2020/11/17--第2章对偶问题----17--（2）最优性：若X0——原问题可行解，Y0——对偶问题可行解，且CX0=Y0b则X0——原问题最优解，Y0——对偶问题最优解证明：设X*——原问题最优解，Y*——对偶问题最优解则CX0CX*Y*bY0b但CX0=Y0b，∴CX0=CX*=Y*b=Y0b∴X0=X*，Y0=Y*即X0——原问题最优解，Y0——对偶问题最优解证毕。若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。2020/11/17--第2章对偶问题----18--（3）无界性若原问题最优解无界，则对偶问题无可行解证：有性质1，CX0Y0b，当CX0∞时，则不可能存在Y0，使得CX0Y0b。注：逆定理不成立，即如果原问题（对偶问题）无可行解，那么对偶问题（或原问题）“解无界”不成立。2020/11/17--第2章对偶问题----19--（4）强对偶性（对偶定理）若原问题有最优解，则对偶问题一定有最优解，且有zmax=wmin证：由=C-CBB-1A0令CBB-1=Y*，得Y*AC-Y*=-CBB-10，Y*0因此，Y*是对偶问题的可行解，又CX*=CB(B-1b)=CBB-1b=Y*b∴Y*是对偶问题的最优解。还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。2020/11/17--第2章对偶问题----20--Maxz=CXst.AXbX0Maxz=CXst.AX+Xs=bX0标准形Maxz=CBXB+CNXN+0XSst.BXB+NXN+IXS=b，XB,XN,XS0改写∴B-1存在Maxz=CBXB+CNXN+0XSst.B-1BXB+B-1NXN+B-1IXS=B-1bXB,XN,XS0左乘B-1LP模型矩阵变换：|B|≠0，（XB+B-1NXN+B-1XS=B-1b）2020/11/17--第2章对偶问题----21--单纯形法的矩阵描述：XBXNXSBNIIN´B-1bb´XSXBσCBCN0CBCN0σ=C-CBB-1A´00σNσSxjcjpj0pj´σjcjXB=b´=B-1bN=B-1NσN=CN-CBB-1N0CBσS=-CBB-10σ初始表最终表A´=[BNI]2020/11/17--第2章对偶问题----22--（5）互补松弛性n若yi*0,则aijxj*=bij=1n若aijxj*bi,则yi*=0j=1nnmm证：∵cjxj*=(aijyi*)xj*=biyi*j=1j=1i=1i=1nmm∴(aijyi*)xj*-biyi*=0j=1i=1i=1mn(aijxj*-bi）yi*=0i=1j=1∴当yi*0,aijxj*-bi=0,即aijxj*=bi当aijxj*-bi0,yi*=0j=1j=1j=1nnn2020/11/17--第2章对偶问题----23--设X0和Y0分别是P问题和D问题的可行解，则它们分别是最优解的充要条件是：000ss0XYXY其中：Xs、Ys为松弛变量证明：（LP）和（LD）标准化为：max..,0sszCXAXXbstXXmin..,0sswYbYAYCstYY则有:ˆˆˆˆˆˆ()ssZCXYAYXYAXYXˆˆˆˆˆˆ()ssWYbYAXXYAXYX2020/11/17--第2章对偶问题----24--必要性：则ˆˆCXYb于是ˆˆssYXYX所以ˆˆ0,0ssYXYX充分性：若若为最优解YXˆ,ˆ所以为最优解YXˆ,ˆˆˆ0,0ssYXYX则ˆˆCXYb2020/11/17--第2章对偶问题--25该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知Y*求X*或已知X*求Y*00ssXYXY互补松弛条件由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：若Y*≠0，则Xs必为0；若X*≠0，则Ys必为0利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。•例已知线性规划123123123123min22460,0,zxxxxxxxxxxxx＝无约束其对偶问题的最优解为Y*=(0,-2)，求原问题的最优解。解:对偶问题是021264max2121212121yyyyyyyyyyw无约，＝标准化0,,0,21264max43212142132121yyyyyyyyyyyyyyw无约＝设原问题最优解为X*＝(x1，x2，x3)T,由互补松弛性定理可知，X*和Y*满足：0),)(,(0),,)(,,(5421321543TTxxyyxxxyyy将Y*带入由方程可知，y3＝y5＝0，y4＝1。∵y2=-2≠0∴x5＝0又∵y4=1≠0∴x2＝0将x2，x5分别带入原问题约束方程中，得：643131xxxx解方程组得：x1=-5,x3=-1,所以原问题的最优解为X*=(-5,0,-1)，最优值z=-12若其对偶问题的最优解为：y1﹡=4/5,y2﹡=3/5,Z﹡=5用互补松弛定理求最优解。125125