第二章对偶理论10

1第二章LP的对偶理论(dualtheory)§1对偶问题的提出§2原问题与对偶问题§3对偶问题的基本性质§4对偶问题的经济意义——影子价格§5对偶单纯形法§6灵敏度分析§7参数线性规划2§1对偶问题的提出一、对偶问题的提出在理论上和实践上，对偶理论都是LP中一个十分重要和有趣的概念。支持对偶理论的基本思想是，每一个LP问题都存在一个与其对偶的问题，原问题与对偶问题对一个实际问题从不同角度提出来，并进行描述，组成一对互为对偶的LP问题。在求出一个问题解的时候，也同时可以得到另一个问题的解。下面通过一个例子看一下对偶问题的经济意义。3美佳公司计划制造甲乙两种产品。已知各制造一件产品时分别占用设备A,B的台时，每天可用于这两种产品的能力，各售出一件时的获利能力如下表。问该公司应制造两种产品各多少件，获取的利润最大？项目甲乙每天可用能力设备A1517设备B6224利润214MAXZ=2X1+X2满足条件：X1+5X2176X1+2X224X1≥0,X2≥0列出线性规划模型为：5现从另一个角度提出问题：假定东方公司想把美佳公司（的资源)收买过来，它至少应付出多大代价（底线），才能使美佳公司愿意放弃生产活动，出让自己的资源？显然，该企业愿意出让的条件是，出让的价格不应低于同等数量资源由自己组织生产活动时获取的利润。分析：设y1,y2分别表示单位时间（h）设备A、设备B的出让代价，则从东方公司来看，希望用最小的代价把全部资源收买过来，故有：minw=17y1+24y2因生产一件甲产品需两种设备分别为1、6小时，盈利2元，生产一件乙产品需两种设备分别为5、1小时，盈利1元。从美佳公司来看，出让资源获得的利润应不少于自己组织生产获得的利润。因此有：y1+6y225y1+2y216要使收买成功，双方的要求都必须满足，于是得到出让资源问题的线性规划数学模型：minw=17y1+24y2y1+6y225y1+2y21y10,y20于是我们得到两个线性规划：7原问题：LP1:maxZ=2X1+X2X1+5X2176X1+2X224X10,X20对偶问题：LP2：minw=17y1+24y2y1+6y225y1+2y21y10,y20我们把LP2称为LP1的对偶问题；若把LP2看成原问题，则LP1就是LP2的对偶问题。比较两者，看有什么规律？81）目标函数的目标互为相反(max,min)；2）目标函数的系数是另一个约束条件右端的向量；3）约束系数矩阵是另一个的约束系数矩阵的转置；4）约束方程的个数与另一个的变量的个数相等；5）约束条件在一个问题中为“≤”，在另一个问题中为“”。9二、对偶问题的一般提法（对称形式下对偶问题的一般提法）看书P41原问题：m种资源bi(i=1…m)生产n种产品xj(j=1…n)，获利分别为cj(j=1…n)元，aij为工艺系数，则原问题为Maxz=∑cjxj∑aijxj≤bi(i=1…m)xj≥0(j=1…n)对偶问题：设将上述资源出售定价为yi（i=1…m），使获得收益不低于原企业生产产品出售获得的收益，则应满足Minw=∑biyi∑aijyi≥cj(j=1…n)yi≥0(i=1…m)10三、LP的对偶问题也可以从数学的角度引出来（了解）检验数为B=CB-CBB-1B(1)N=CN-CBB-1N(2)-Y=CBB-1(1)(2)合到一起，检验数一般形式为：=C-CBB-1A令Y=CBB-1，称为单纯形乘子当所有j0时，YACY0又Z=CX=CBb’=CBB-1b=Yb=W,所以：minw=Ybst.YACY011从例子看到，原问题为求max，对偶问题为求min，因为：（1）对偶问题的可行解（Y=CBB-1）满足原问题的最优化条件（0）；（2）因此对原问题来说，只有最优解（X＊=B-1b）才是其对偶问题的可行解。（3）也即原问题的最优解目标函数值是它的对偶问题可行解目标函数值最小的一个。(注意对偶问题求min)(Z＊=CX=CBb／=CBB-1b=Yb=W)（4）由此可知，原问题目标函数的最大值对应于对偶问题的目标函数的最小值。CX＊Yb（具体见第三节基本性质）12一、对偶关系（对称形式）§2原问题与对偶问题原问题对偶问题maxz=CXminw=Ybst.AXbst.YACX0Y0看书上表2.1，验证对应关系对称性：LP的原问题与对偶问题之间存在对称关系，即LP对偶问题的对偶是原问题结论：LP对偶问题与原问题互为对偶。看例2，通过例子得出结论第一步，化为对称形式下的原问题形式；第二步，根据对应关系写出其对偶问题；第三步，做一变换，得到原问题。13二、非对称形式原问题与对偶问题之间的关系看例3，是一个最小化问题第一步，化为对称形式下的对偶问题形式（min，≥，变量非负）；第二步，引入对偶变量（根据原问题约束条件符号来设的），根据对应关系写出其对偶问题；第三步，变换为一般形式。设原问题的三个约束条件的对偶变量分别为y1、y2、y3(每一个约束条件对应一个对偶变量)由此，对于非对称形式原问题与对偶问题之间的关系可用下表反映：14原问题（或对偶问题）对偶问题（或原问题）目标函数maxz目标函数minw资源系数价值系数价值系数资源系数变量原变量个数为n个第j个xj变量0第j个xj变量0,第j个xj变量无约束行约束个数为n个第j个约束取第j个约束取第j个约束取=约束条件约束条件行约束个数为m个第i个约束取第i个约束取第i个约束取=对偶变量m个第i个变量yi0第i个变量yi0第i个变量yi无约束变量约束条件系数矩阵AA′15例：给出下列线性规划的对偶问题：MAXZ=X1+2X2+X3X1+X2–X32y1X1–X2+X3=1y2st.2X1+X2+X32y3X10,X20,X3无约束16例：给出下列线性规划的对偶问题：MAXZ=X1+2X2+X3X1+X2–X32y1X1–X2+X3=1y2st.2X1+X2+X32y3X10,X20,X3无约束其对偶问题为：minw=2y1+y2+2y3y1+y2+2y31X1st.y1-y2+y32X2-y1+y2+y3=1X3y10,y2无约束，y3017例：给出下列线性规划的对偶问题：minZ=2X1+8X2-4X3X1+3X2–3X330y1-X1+5X2+4X3=80y2st.4X1+2X2-4X350y3X10,X20,X3无约束18例：给出下列线性规划的对偶问题：minZ=2X1+8X2-4X3X1+3X2–3X330y1-X1+5X2+4X3=80y2st.4X1+2X2-4X350y3X10,X20,X3无约束其对偶问题为：MAXw=30y1+80y2+50y3y1-y2+4y32x1st.3y1+5y2+2y38x2-3y1+4y2-4y3=-4x3y10,y2无约束，y3019先相同，后相反；先相反，后相同最大化问题找其对偶问题，约束条件与其对偶变量的符号相同，而其变量的符号与其对应约束条件的符号相反；最小化问题找其对偶问题，约束条件与其对偶变量的符号相反，而其变量的符号与其对应约束条件的符号相同。20§3对偶问题的基本性质原问题对偶问题maxz=CXminw=Ybst.AXbst.YACX0Y0可行解XY本节讨论先假定原LP与对偶问题为对称形式的线性规划问题，然后说明对偶问题的基本性质在非对称形式（一般形式）时也适用。性质是就对称形式提出的，可行平行的推广到一般形式的问题中去，只不过叙述上也要有相应的变动。211、弱对偶性：CX≤YbX，Y是可行解（证明用到了上面两个约束条件）性质含义：极大化问题的任一可行解的目标函数值，不大于对偶问题的任一可行解的目标函数值。也即：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。22已知线性规划问题:maxZ=4x1+7x2+2x3s.t.应用对偶理论证明该问题最优解的目标函数值不大于25.0,,10332102321321321xxxxxxxxx232、最优性：当原问题与对偶问题均有可行解X、Y，且当CX=Yb时，则X、Y分别是原问题与对偶问题的最优解。（由性质1证明）（隐含：两者都存在可行解，则均存在最优解）24已知线性规划问题：MAXZ=3x1+2x2-x1+2x2≤43x1+2x2≤14x1–x2≤3x1，x2≥0（1）写出对偶问题；（2）利用对偶问题性质证明原问题和对偶问题都存在最优解。253、无界性：如果原问题（对偶问题）有无界解，则对偶问题（原问题）无可行解。即原问题有可行解且目标函数值无界（可达正无穷），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界（可达负无穷），则其原问题无可行解。（性质1，CX≤Yb，Yb≥CX）如果原问题无可行解时，对偶问题无可行解或具有无界解对偶问题无可行解时，原问题无可行解或具有无界解（原问题有可行解，对偶问题无可行解，则原问题有无界解）26已知线性规划问题:maxZ=x1+x2s.t.试应用对偶理论证明上述线性规划问题无最优解。（无界解属于无最优解）0,,122321321321xxxxxxxxx27已知线性规划问题maxZ=x1-x2+x3x1-x3≥4x1–x2+2x3≥3x1x2x3≥0试应用对偶理论证明上述线性规划问题无最优解.（无界解属于无最优解）284、强对偶性（对偶定理）：若原问题有最优解，则对偶问题也一定有最优解，且目标函数值相等。证明：Z=CX=CBb／=CBB-1b=Yb=W根据性质2，Y是对偶问题最优解29小结：1、原问题有可行解，则对偶问题：有可行解，则两者均具有最优解；无可行解，则原问题具有无界解。2、原问题无可行解，则对偶问题可以无可行解或者无界解。3、原问题无界解，对偶问题无可行解。（无界性）4、原问题有最优解，对偶问题有最优解，且CX=Yb。（对偶定理）305、互补松弛性：变量为“0”时，其对应约束条件为“=”；约束条件为“”时，其对应对偶变量为“0”（线性规划问题的约束条件与对偶变量一一对应）(一个问题的约束条件和另一个问题的变量对应，一个问题的变量和另一个问题的约束条件对应)已知线性规划问题minZ=8X1+6X2+3X3+6X4STX1+2X2+X4≥33X1+X2+X3+X4≥6X3+X4≥2X1+X3≥2Xj≥0j=1,2,3,4已知原问题最优解为：X=（1,1,2,0）T试利用对偶性质求对偶问题的最优解。31例:已知下列线性规划问题的对偶问题的最优解为(6/5,1/5),求该线性规划问题的最优解.MAXZ=X1+2X2+3X3+4X4X1+2X2+2X3+3X420Y12X1+X2+3X3+2X420Y2X1,X2,X3,X4≥032解:其对偶问题为:MINW=20Y1+20Y2+5Y3Y1+2Y2≥11)X12Y1+Y2≥22)X22Y1+3Y2≥33)X33Y1+2Y2≥44)X4Y1≥0,Y2≥033将解代入到对偶问题的四个约束条件可得1*1.2+2*0.21;2*1.2+0.21;2*1.23*0.2=3;3*1.2+2*0.2=4那么由互补松驰性得，x1=0;x2=0。再由y1,y20得，原问题的两个约束条件均取等号，这样联立方程从而:原问题的约束变为:2X3+3X4=203X3+2X4=20解此方程得:X3=X4=4于是原问题的最优解为:(0,0,4,4)目标函数值z=28.34已知线性规划问题minW=2X1+3X2+5X3+2X4+3X5STX1+X2+2X3+X4+3X5≥42X1－X2+3X3+X4+X5≥3Xj≥0j=1,2,3,4,5已知对偶问题最优解为：Y1=4/5Y2=3/5Z=5试利用对偶性质求原问题的最优解。35解：由互补松弛定理可得方程：3X1+X5=42X1+X5=3解此方程组可得：X1=1，X5=1所以原问题的