《运筹学》第二章 对偶问题

1第2章线性规划的对偶理论•2.1对偶问题的提出•2.2原问题与对偶问题的关系•2.3对偶问题的性质•2.4影子价格•2.5对偶单纯形法•2.6灵敏度分析•2.7参数线性规划2对偶：Duality对偶问题：DualProblem对偶线性规划：DualLinearProgramming对偶理论：DualTheory32.1对偶问题的提出例：某企业计划生产甲、乙两种产品，该两种产品均需要A、B、C、D四种不同的材料，按工艺资料规定，生产一单位甲乙产品需要各种材料数量及单位产品利润如表中所示。问:如何安排产品的生产计划,才能使企业获利最大?设备产品ABCD单位利润甲产品乙产品2212400423现有材料数量12816124解：设企业生产甲产品为X1件，乙产品为X2件，则maxz=2X1+3X2s.t.2X1+2X212X1+2X284X1164X212X10,X205如果另外一企业想将上述企业拥有的资源收买过来，至少应付出多少代价，才能使第一个企业愿意放弃生产活动，出售资源？我出让资源的代价不应低于我自己组织生产时的产值!我要用最小的代价购买资源!注:关键是确定转让价格6设备产品ABCD单位利润甲产品乙产品2212400423现有材料数量1281612设第i种资源单位增值价（售价＝成本＋增值），为yi,（i=1,2,3,4）,则有minw=12y1+8y2+16y3+12y4s.t.2y1+y2+4y3+0y422y1+2y2+0y3+4y43yi0,(i=1,2,3,4)71.最大生产利润模型设企业生产甲产品为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)y1y2y3y4注：考虑角度不同，模型中的系数有对应关系。8对偶问题：minw=b1y1+b2y2+┈+bmyma11y1+a21y2+┈+am1ymc1a12y1+a22y2+┈+am2ymc2·························a1ny1+a2ny2+┈+amnymcnyi0，(i=1,2,···,m)2.2原问题与对偶问题的关系原问题：maxz=c1x1+c2x2+┈+cnxna11x1+a12x2+┈+a1nxnb1a21x1+a22x2+┈+a2nxnb2·······················am1x1+am2x2+┈+amnxnbmxj0，j=1,2,┈,n一般形式：目标函数系数:C=[c1c2…cn]系数矩阵:A=[aij]m×n约束右端项:b=b1b2:bm目标函数系数:b’系数矩阵:A’约束右端项:C’9（1）maxz=CXs.tAXbX0典式模型的对偶结构的矩阵表示minw=Ybs.tYACY0对偶问题原问题Y=(y1,…,ym)10(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其它模型的对偶结构的矩阵表示11（3）maxz=CXs.t.AXbX0变形设X=-X´maxz=(-C)X´s.t.(-A)X´bX´0minw=Ybs.t.YACY0minw=Ybs.t.Y(-A)-CY0对偶变量Y12原问题与对偶问题的对应关系用矩阵形式表示：（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013原问题(对偶问题)对偶问题(原问题)目标函数系数约束右端项约束右端项目标函数系数约束条件系数列向量A约束条件系数行向量A’变量个数约束条件个数maxmin变量xj:第j个约束方程:xj0xj无约束=xj0第i各约束方程:变量yi:yi0=yi无约束yi0原问题与对偶问题的对应关系表14无约束4321432142143214321,0,,0643247235234532maxxxxxxxxxxxxxxxxxxxxZ无约束32132131321321321,0,01725433322234645minyyyyyyyyyyyyyyyyyW•例写出下列线性规划问题的对偶问题.解：原问题的对偶问题为对偶问题的对偶还是原问题1512312312123123123max4324353242346310,0,无约束Zxxxxxxxxxxxxxxxxx•练习写出下列线性规划问题的对偶问题.162.3对偶问题的基本性质原问题对偶问题Maxz=CXMinw=Ybs.t.AXbs.t.YACX0Y0(1)弱对偶性(2)最优性(3)强对偶性(或称对偶定理)(4)互补松弛性(5)单纯形表上的对应关系17(1)弱对偶性：若X0是原问题可行解，Y0是对偶问题可行解，则CX0Y0b证明：∵Y00，AX0b，∴Y0AX0Y0b，而Y0AC，∴CX0Y0AX0，∴CX0Y0AX0Y0b由弱对偶性，可得以下结论：(1)原问题(对偶问题)任一可行解的目标函数值是其对偶问题(原问题)目标函数值的下(上)界；(2)若原问题(或对偶问题)具有无界解，则对偶问题(或原问题)无可行解。其逆定理不成立，即如果原问题（对偶问题）无可行解，那么对偶问题（或原问题）无可行解，或者有可行解（此时有无界解）。证明：由性质1，CX0Y0b，当CX0∞时，则不可能存在Y0，使得CX0Y0b。(3)若原问题(对偶问题)有可行解而其对偶问题(原问题)无可行解，则原问题(对偶问题)具有无界解。19(2)最优性：若X0是原问题可行解，Y0是对偶问题可行解，且CX0=Y0b，则X0是原问题最优解，Y0是对偶问题最优解。证明：设X*是原问题最优解，Y*是对偶问题最优解，则CX0CX*Y*bY0b但CX0=Y0b，∴CX0=CX*=Y*b=Y0b即X0是原问题最优解，Y0是对偶问题最优解。20(3)强对偶性（对偶定理）：若原(对偶)问题有最优解,则对偶(原)问题一定有最优解，且有zmax=wmin.证：由=C-CBB-1A0，s=0-CBB-1I0，令CBB-1=Y*，得Y*AC，-Y*=-CBB-10，Y*0，因此，Y*是对偶问题的可行解，又CX*=CB(B-1b)=CBB-1b=Y*b，∴由性质2，Y*是对偶问题的最优解。21一组互为对偶的线性规划问题的解之间只有下列三种情况:(1)两个规划问题都有可行解(此时,两个规划问题都有最优解,且最优值相等);(2)两个规划问题都不可行;(3)一个规划问题不可行,另一个规划问题有可行解,且具有无界解。22（4）互补松弛性：在线性规划问题的最优解中，n若yi*0,则aijxj*=bi；j=1n若aijxj*bi,则yi*=0j=1(4)’互补松弛性：在线性规划问题的最优解中，m若xj*0,则aijyi*=cj；i=1m若aijyi*cj,则xj*=0i=123nnmm证：∵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=1nnn24性质(4)的应用:已知原问题(对偶问题)的最优解,求对偶问题(原问题)的最优解.25例已知线性规划的最优解是X＊=(6,2,0)’,求其对偶问题的最优解Y＊.3,2,1,0162210243max321321321jxxxxxxxxxxzj26解：写出原问题的对偶问题，即0,1422321610min2121212121yyyyyyyyyyw因为X＊=(6,2,0)’,所以y1+2y2=32y1+2y2=4解得y1=1,y2=1。所以对偶问题的最优解为Y*=(1,1),最优值为w=26.27例已知线性规划maxz=2x1+x2+5x3+6x42x1+x3+x4≤82x1+2x2+x3+2x4≤12xj≥0,j=1,2,3,4,其对偶问题的最优解是y1*=4,y2*=1，求原问题的最优解X＊.28解：写出原问题的对偶问题，即因为y1*=4,y2*=1，所以2x1+x3+x4=82x1+2x2+x3+2x4=12又因为2y1*+2y2*＞22y2*＞1所以x1*=0,x2*=0。求得原问题的最优解为X*=(0,0,4,4),最优值为z=44.minw=8y1+12y22y1+2y2≥22y2≥1y1+y2≥5y1+2y2≥6y1,y2≥0,j=1,2,3,4,29（5）单纯形表中的对应关系原问题对偶问题maxz=2x1+3x2minw=12y1+8y2+16y3+12y4s.t2x1+2x212s.t2y1+y2+4y3+0y42x1+2x282y1+2y2+0y3+4y434x116yi0,i=1,2,3,44x212x10,x20cj→230000CBXBbx1x2x3x4x5x60x302x140x643x22001-1-0.25010000.250000-20.510100.5-0.1250cj-zj000-1.5-0.1250-y1-y2-y3-y4-y5-y6用单纯形法对原问题求解30原问题对偶问题maxz=2x1+3x2minw=12y1+8y2+16y3+12y4s.t2x1+2x212s.t2y1+y2+4y3+0y42x1+2x282y1+2y2+0y3+4y434x116yi0,i=1,2,3,44x212x10,x20-y1-y2-y3-y4Cj→x1x2x3x4XBbCB2300002283x3x1x5x20203cj-zjx5x6010000011000-21-4000100.5-0.520.25000-200.25-y5-y6用单纯形法对原问题求解312.4影子价格(Shadowprice)约束条件右侧（即资源）改变1个单位时，目标函数（即利润）的变化量，它度量了约束条件对应的那种资源的价值，经济学上称为影子价格。z=c1x1*+…+cnxn*=b1y1*+…+bmym*注：(y1*,…,ym*)=CBB-1，其中B是原问题的最优解的基变量在初始表里对应的矩阵。*32市场价格影子价格商品的价值的货币表现资源最优利用时的边际价值随着市场的供求情况和有关方针，政策的变化而变化。随着经济结构的变化而变化，同一资源在不同的经济结构中影子价格不同。它的制定含定价者的主观因素它的形成完全由经济结构的客观条件确定。它的制定是个比较复杂的过程，不存在统一的计算公式。它的计算是比较容易的。用单纯形法求得任何一种商品的市场价格都不可能为0影子价格可以为0，当资源过剩时，其影子价格为0市场价格为已知数，相对比较稳定。影子价格则有赖于资源利用情况，是未知数。因企业生产任务，产品的结构等情况发生变化，资源的影子价格也随之改变。影子价格与市场价格的比较33(1)决定买进或卖出某种资源的参考依据(2)对资源使用状况的估算（互补松弛性）(3)机会成本：j=cj-CBB-1pj=