第三章 对偶单纯形法ppt课件

1、运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外对偶理论与灵敏度分析对偶理论与灵敏度分析第二章第二章 对偶理论与灵敏度分析对偶理论与灵敏度分析第一节对偶问题的提出第一节对偶问题的提出第二节线性规划的对偶理论第二节线性规划的对偶理论第三节对偶问题的经济解释第三节对偶问题的经济解释第四节对偶单纯形法第四节对偶单纯形法【例【例2-12-1】某家电厂利用现有资源生产两种】某家电厂利用现有资源生产两种产品，有关数据如下表：产品，有关数据如下表：设备设备A A设备设备B B调试工序调试工序利润元）利润元）061252111515时时2424时时 5 5 时时产品产品产品产品D D第一节

2、第一节 对偶问题的提出对偶问题的提出如何安排生产，如何安排生产，使获利最多？使获利最多？厂厂家家设设 产量产量 产量产量1x2x 0, 5 2426 155 2max 212121221xxxxxxxs.t.xxz 设：设备A 元时 设备B 元时 调试工序 元时1y2y3y承租承租 付出的代价最小，付出的代价最小， 且对方能接受。且对方能接受。出让代价应不低于出让代价应不低于用同等数量的资源用同等数量的资源自己生产的利润。自己生产的利润。设备设备A设备设备B调试工序调试工序利润元）利润元）0612521115时时24时时 5 时时D厂家能接受的条件：厂家能接受的条件：32152415minyy

3、yw出让代价应不低于出让代价应不低于用同等数量的资源用同等数量的资源自己生产的利润。自己生产的利润。1252632132yyyyy收购方的意愿：收购方的意愿：厂厂家家0, 5 2426 155 2max212121221xxxxxxxs.t.xxz0,y 125 26.32132132yyyyyyyts32152415minyyyw对对偶偶问问题题原原问问题题承承租租厂厂家家一对对偶问题一对对偶问题第二节第二节 线性规划的对偶理论线性规划的对偶理论一原问题与对偶问题的关系一原问题与对偶问题的关系二对偶问题的基本性质二对偶问题的基本性质一一原问题与对偶问题的关系原问题与对偶问题的关系1对称式的对

4、偶对称式的对偶“”不等式约束条件的原问题与不等式约束条件的原问题与“”不等式约束条件的对偶问不等式约束条件的对偶问题，称为对称式的一对对偶问题。题，称为对称式的一对对偶问题。原问题：原问题：max z=c1x1+c2x2+cnxn a11 a12 a1n am1 am2 amn x1xn b1bm x1，x2，xn0对偶问题：对偶问题：min =b1y1+b2y2+bmym a11 a12 a1n am1 am2 amn y1，y2，ym0 (y1,y2,ym) (c1,c2,cn)max z=CXAXbX0min =YbYA CY0 n个变量，个变量，m个约束条件个约束条件 m个变量，个变量

5、，n个约束条件个约束条件2约束条件全部为约束条件全部为“=”的对偶的对偶max z=CXAXbX0原问题：原问题：max z=CXAXbX0AXb等价等价max z=CXAXbX0AXbmax z=CXX0AAXbbmin =(Y1,Y2)Y1,Y20AACbb(Y1,Y2)其中其中 Y1=(y1, y2, ym)， Y2=(ym+1, ym+2, y2m)等等价价等价等价min =YbY为无约束为无约束YA Cmin =(Y1Y2)bY1,Y20(Y1 Y2)A C令令Y=(Y1 Y2)对偶问题对偶问题对偶对偶问题问题3约束条件为约束条件为“”的对偶的对偶max z=CXAXbX0原问题：原

6、问题：max z=CXAX bX0min =Y1 ( b)Y1(A) CY10min =YbYA CY0等价等价对对偶偶问问题题令令Y= Y1对偶对偶问题问题4变量变量0的对偶的对偶max z=CXAXbX0原问题：原问题：令令X= X1max z=C (X1)A (X1) bX10max z=(C) X1(A )X1 bX10等等价价min =Y bY (A) CY0min =Y bY A CY0对对偶偶问问题题对偶对偶问题问题等等价价5变量无约束的对偶变量无约束的对偶max z=CXAXbX无约束无约束原问题：原问题：令令X=X1 X2 X1， X20max z=CX1CX2X1,X20A

7、X1 AX2 bmax z=(C, C)X1,X20bX1X2(A, A)X1X2等等价价min =YbY0Y(A , A) (C, C)对对偶偶min =YbYACY0 YA Cmin =YbYA CY0min =YbYACY0YA C等价等价等等价价等等价价对偶对偶问题问题6原问题与对偶问题的关系表原问题与对偶问题的关系表原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 max zn个变量个变量变量变量0变量变量0变量无约束变量无约束目标函数目标函数 min n个约束条件个约束条件约束约束约束约束约束约束=m个约束条件个约束条件约束约束约束约

8、束约束约束=约束条件右端项约束条件右端项目标函数变量系数目标函数变量系数m个变量个变量变量变量0变量变量 0变量无约束变量无约束 目标函数变量系数目标函数变量系数约束条件右端项约束条件右端项【例【例2-2】试求下述线性】试求下述线性规划问题的对偶问题规划问题的对偶问题123123123123max5124210 238,0zxxxxxxs.t.xxxx x x（P与(D)的关系对应表： 原(对偶)问题 对偶(原)问题目标函数max目标函数min目标函数系数约束方程常数列约束方程常数列 目标函数系数变量个数n约束方程个数n约束方程个数m变量个数m约束方程变量00=无符号约束变量0约束方程0无符号

9、约束=系数矩阵AA系数矩阵解解 ： 1212121212min10825212. .340,yyyyyys tyyyy无约束（P与(D)的关系对应表： 原(对偶)问题 对偶(原)问题目标函数max目标函数min目标函数系数约束方程常数列约束方程常数列 目标函数系数变量个数n约束方程个数n约束方程个数m变量个数m约束方程变量00=无符号约束变量0约束方程0无符号约束=系数矩阵AA系数矩阵123412341342341234min2353522460,0,zxxxxxxxxxxxxxxxx xx无 约 束【例【例2-3】 试求下述线性试求下述线性规划原问题的对偶问题规划原问题的对偶问题解：原问题的

10、对偶问题解：原问题的对偶问题无约束3213213213121321001523322645y,y,yyyyyyyyyyyyyyzmax【课堂练习】【课堂练习】4321532max1xxxxZ题、求下列问题的对偶问无限制432143214214321, 0, 0643247235234.xxxxxxxxxxxxxxxts4321532min2xxxxZ题、求下列问题的对偶问无限制432143214214321, 0, 0643247235234.xxxxxxxxxxxxxxxt s（P与(D)的关系对应表： 原问题 对偶问题目标函数max目标函数min目标函数系数约束方程常数列约束方程常数列 目

11、标函数系数变量个数n约束方程个数n约束方程个数m变量个数m约束方程变量00=无符号约束变量0约束方程0无符号约束=系数矩阵AA系数矩阵321645minyyyS无限制32132131321321,0,01725433322234.yyyyyyyyyyyyyyts321645maxyyyS无限制32132131321321, 0, 01725433322234.yyyyyyyyyyyyyyts构建对偶问题的规则构建对偶问题的规则原始问题的原始问题的 目标目标对偶问题对偶问题目标目标约束类型约束类型变量符号变量符号最大化最大化极小化极小化=无限制无限制最小化最小化极大化极大化=无限制无限制要求：要

12、求：1 1、将所有约束转换成等式；、将所有约束转换成等式； 2 2、将所有决策变量转换成大于等于。、将所有决策变量转换成大于等于。回想：原问题与对偶问题的关系表回想：原问题与对偶问题的关系表原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 max zn个变量个变量变量变量0变量变量0变量无约束变量无约束目标函数目标函数 min n个约束条件个约束条件约束约束约束约束约束约束=m个约束条件个约束条件约束约束约束约束约束约束=约束条件右端项约束条件右端项目标函数变量系数目标函数变量系数m个变量个变量变量变量0变量变量 0变量无约束变量无约束 目标函数

13、变量系数目标函数变量系数约束条件右端项约束条件右端项二二对偶问题的基本性质对偶问题的基本性质1对称性：对偶问题的对偶问题是原问题。对称性：对偶问题的对偶问题是原问题。2弱对偶性：若弱对偶性：若X(0)是原问题的可行解，是原问题的可行解， Y(0)是是对偶问题的可行解，则存在对偶问题的可行解，则存在CX(0) Y(0) b。3无界性：若原问题无界解，无界性：若原问题无界解， 则其对偶问题无可则其对偶问题无可行解行解 。4最优性：若最优性：若X(0)是原问题的可行解，是原问题的可行解， Y(0)是对是对偶问题的可行解，且偶问题的可行解，且C X(0) = Y(0) b ，则，则X(0)，Y(0)是

14、最优解。是最优解。5对偶定理：若原问题有最优解，对偶定理：若原问题有最优解， 那么对偶问题那么对偶问题也有最优解；且目标函数值相等。也有最优解；且目标函数值相等。6互补松弛性：若互补松弛性：若X(0)是原问题的可行解，是原问题的可行解， Y(0)是对是对偶问题的可行解，则偶问题的可行解，则YsX(0)=0和和Y(0)Xs=0 当且仅当当且仅当X(0)，Y(0)是最优解。是最优解。其中其中Xs和和Ys分别为原问题和对偶问题的松弛变量的可分别为原问题和对偶问题的松弛变量的可行解行解.【例【例2-4】已知线性规划问题】已知线性规划问题min w=2x1+3x2+5x3+2x4+3x5x1+x2+2x

15、3+x4+3x542x1-x2+3x3+x4+x53 xj0，j=1，2，5已知其对偶问题的最优解为已知其对偶问题的最优解为y1*=4/5，y2*=3/5；z=5。试用对偶理论找出原问题的最优解。试用对偶理论找出原问题的最优解 。【例【例2-4】已知线性规划问题】已知线性规划问题 解：先写出它的对偶问题解：先写出它的对偶问题max z=4y1+3y2y1+2y22 y1-y23 2y1+3y25 y1+y22 3y1+y23 y1，y20【例【例2-42-4】已知线性规划问题】已知线性规划问题 将将y1y1* * =4/5,y2 =4/5,y2* * =3/5 =3/5的值代入约束条件，的值代

16、入约束条件，得得=1/53，=17/55，=7/52 它们为严格不等式；由互补松弛性得它们为严格不等式；由互补松弛性得 x2*=x3*=x4*=0。因因y1，y20；原问题的两个约束条件应取等式；原问题的两个约束条件应取等式，故有，故有 x1*+3x5*=4，2x1*+x5*=3求解后得到求解后得到x1*=1,x5*=1；故原问题的最优解为；故原问题的最优解为 X*=(1，0，0，0，1)T；w*=51、原始问题是利润最大化的生产计划问题、原始问题是利润最大化的生产计划问题0. .max212122112222221211112121112211mnnnnmmnnmnmmnnnnnnnnxxx

17、xxxbxxaxaxabxxaxaxabxxaxaxat sxcxcxcz单位产品的利润元单位产品的利润元/件）件）产品产量件）产品产量件）总利润元）总利润元）资源限量吨）资源限量吨）单位产品消耗的资源吨单位产品消耗的资源吨/件）件）剩余的资源吨）剩余的资源吨）消耗的资源吨）消耗的资源吨）第三节第三节 对偶问题的经济解释对偶问题的经济解释2、对偶问题、对偶问题0. .min212122112222221121112211112211nmmmmnnmmmnnnmmmmmmmmyyyyyycyyayayacyyayayacyyayayat sybybybw资源限量吨）资源限量吨）资源价格元资源价格

18、元/吨）吨）总利润元）总利润元）对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为称为m种资源的影子价格种资源的影子价格Shadow Price）原始和对偶问题都取得最优解时，最大利润原始和对偶问题都取得最优解时，最大利润 max z=min w3、资源影子价格的性质、资源影子价格的性质从对偶定理可知，当达到最优解时，原问题和对偶问题的目标从对偶定理可知，当达到最优解时，原问题和对偶问题的目标函数值相等，即函数值相等，即z=CX(0)=Y(0)b=CBB-1b .也即也即z=CX(0)=Y(0)b=CBB-1b =y1(0)b1+ y2(0

19、) b2 + +ym(0) bm 其中其中 X(0),Y(0)分别是原问题和对偶问题的最优解。分别是原问题和对偶问题的最优解。现在考虑在最优解处，常数项现在考虑在最优解处，常数项bi的微小变动对目标函数值的影响的微小变动对目标函数值的影响(不改变原来的最优基不改变原来的最优基).求求z对对bi的偏导数，可得：的偏导数，可得：y 1 ( 0 ) zb1, y2(0) zb2, ym(0) zbm, 这说明，若原问题的某一约束条件的右端常数项这说明，若原问题的某一约束条件的右端常数项bi增加一个单增加一个单位，则由此引起的最优目标函值的增加量，就等于该约束条件位，则由此引起的最优目标函值的增加量，

20、就等于该约束条件相对应的对偶变量的最优值。相对应的对偶变量的最优值。最优变量最优变量yi(0) 的值，就相当于对单位第的值，就相当于对单位第I种资源在实现最大利润种资源在实现最大利润时的一种估价。这种估价是针对具体企业具体产品而存在的一时的一种估价。这种估价是针对具体企业具体产品而存在的一种特殊价格，称它为种特殊价格，称它为“影子价格影子价格”。【例【例1-31-3】 求下列问题的最优解。求下列问题的最优解。0124164823221212121x ,xxxxx:xxzmax约束条件目标函数0124164223221212121x,xxxxxxxzmax影价格及其经济解释影价格及其经济解释 0

21、124164223221212121x,xxxxxxxzmax第四节第四节 对偶单纯形法对偶单纯形法6(LP)的检验数的相反数对应于的检验数的相反数对应于(DP)的一个基的一个基解，其中第解，其中第j个决策变量个决策变量xj的检验数的相反数对的检验数的相反数对应于应于(DP)中第中第j个松弛变量个松弛变量ysj的解，第的解，第i个松弛个松弛变量变量xsi的检验数的相反数对应于第的检验数的相反数对应于第i个对偶变量个对偶变量yi的解。的解。s0Ys1CN1 CB B-1N1Ys2 CB B-1Y二二对偶问题的基本性质对偶问题的基本性质【例【例2-4】线性规划】线性规划12312313123max

22、62222 44,0zxxxxxxs.t.xxx x x（1用单纯形方法求最优解；用单纯形方法求最优解；（2求每步迭代对应对偶问题的基本解。求每步迭代对应对偶问题的基本解。cj6-2100CBXBbx1x2x3x4x500 x4x5242110241001 j 6-210060 x1x513101/21/2131/2-1/201 j 01-5-306-2x1x2461001460-112 j 00-11-2-2123解：解：原问题与对偶问题解之间的对应关系指出：在单纯原问题与对偶问题解之间的对应关系指出：在单纯形表中进行迭代时，在形表中进行迭代时，在b b列中得到的是原问题的基列中得到的是原问

23、题的基可行解，而在检验数行得到的是对偶问题的基解。可行解，而在检验数行得到的是对偶问题的基解。通过逐步迭代，当在检验数行得到对偶问题的解也通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，已得到最优解。即原问题与对偶问是基可行解时，已得到最优解。即原问题与对偶问题都是最优解。题都是最优解。根据对偶问题的对称性，可以这样考虑：若保持对根据对偶问题的对称性，可以这样考虑：若保持对偶问题的解是基可行解，即偶问题的解是基可行解，即cjcjCBB-1Pj0CBB-1Pj0，而原，而原问题在非可行解的基础上，通过逐步迭代达到基可问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解。

24、其优点是原问题的初行解，这样也得到了最优解。其优点是原问题的初始解不一定是基可行解，可从非基可行解开始迭代。始解不一定是基可行解，可从非基可行解开始迭代。 设原问题为设原问题为 max z=CX AX=b X0又设又设B是一个基。不失一般性，令是一个基。不失一般性，令B=(P1，P2，Pm)，它对应的变量为，它对应的变量为 XB=(x1，x2，,xm)。当非。当非基变量都为零时，可以得到基变量都为零时，可以得到XB=B-1b。若在。若在B-1b中中至少有一个负分量，设至少有一个负分量，设(B-1b)i0，并且在单纯形表，并且在单纯形表的检验数行中的检验数都为非正，即对偶问题保持的检验数行中的检

25、验数都为非正，即对偶问题保持可行解。可行解。每次迭代是将基变量中的负分量每次迭代是将基变量中的负分量xl取出，去替换非取出，去替换非基变量中的基变量中的xk，经基变换，所有检验数仍保持非正。，经基变换，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近。当原问题得到可行解时，便得到了往可行解靠近。当原问题得到可行解时，便得到了最优解。最优解。2对偶单纯形法的计算步骤对偶单纯形法的计算步骤列出初始单纯形表列出初始单纯形表最优性检验最优性检验 根据线性规划问题，确定一个对偶可行根据线性规划问题，确定一个对偶可行的基解，列出初始

26、单纯形表。的基解，列出初始单纯形表。 检查检查b列的数，若都为非负，则已得到最优解。列的数，若都为非负，则已得到最优解。停止计算。若停止计算。若b列的数中，还有分量为负数，则进行下一步计列的数中，还有分量为负数，则进行下一步计算。算。确定换出变量确定换出变量 按按min (B-1b)i | (B-1b)i0，则无可行解，停止计算。，则无可行解，停止计算。 假设假设 有有alj 0 ( j=1,2, n) ,则计算则计算 ck zkmincj zj alj| alj alk确定确定xk为换入为换入 变量，且保持得到的对偶问题的解是基可行解。变量，且保持得到的对偶问题的解是基可行解。迭代运算迭代运

27、算 以以alk为主元素，对单纯形表进行迭代运算，得到为主元素，对单纯形表进行迭代运算，得到新单纯表。新单纯表。 反复反复【例【例2-5】用对偶单纯形法求解】用对偶单纯形法求解 x1+2x2 +x3 3 2 x1x2 +3x3 4 min =2 x1+3x2 +4x3 x1,x2 ,x30 x1 2x2 x3+ x4 =3 2 x1+x2 3x3 +x5=4 max z=2 x1 3x2 4x3 x1,x2 ,x3 x4 ,x5 0解：解：cj23400CBXBbx1x2x3x4x500 x4x5341221131001 j 2340014/3其中其中x4,x5为松弛变量为松弛变量cj23400

28、CBXBbx1x2x3x4x502x4x112015/21/21/23/2101/21/2 j 041018/52cj23400CBXBbx1x2x3x4x532x2x12/511/501101/57/52/51/51/52/5 j 009/5 8/5 1/5原最优原最优 X*=(11/5,2/5,0,0,0)T，对偶最优，对偶最优 Y*=(8/5,1/5)从以上求解过程可以看到对偶单纯形法有以下优点：从以上求解过程可以看到对偶单纯形法有以下优点：(1) 初始解可以是非可行解，当检验数都为负数时就可以初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，因此可以简

29、化进行基的变换，这时不需要加入人工变量，因此可以简化计算。计算。(2) 当变量多于约束条件，对这样的线性规划问题用对偶当变量多于约束条件，对这样的线性规划问题用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。然后用对偶单纯形法求解。(3) 在灵敏度分析及求解整数规划的割平面法中，有时需在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法，这样可使问题的处理简化。对偶单纯要用对偶单纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是，对大多数线性规划问题，很难找到形法的局限性主要是，对大多数线性规划问题，很难找到一个对偶问题初始可行基，因而这种方法在求解线性规划一个对偶问题初始可行基，因而这种方法在求解线性规划问题时很少单独应用。问题时很少单独应用。对偶单纯形法的计算步骤对偶单纯形法的计算步骤min）列出初始单纯形表列出初