运筹学对偶理论.pptx

第第第第3 3章章章章 线性规划对偶理论线性规划对偶理论线性规划对偶理论线性规划对偶理论及其应用及其应用及其应用及其应用 例例1 穗羊公司的例子穗羊公司的例子III每周可使用量每周可使用量A（千克）（千克）125B（吨）（吨）214C（百工时）（百工时）439单位产品利润（万元）单位产品利润（万元）323.1 线性规划的对偶问题线性规划的对偶问题穗家公司由于订单较多，希望收购穗羊公司的各种穗家公司由于订单较多，希望收购穗羊公司的各种资源以扩大自己的生产能力，那么穗羊公司的资源资源以扩大自己的生产能力，那么穗羊公司的资源该如何定价呢？该如何定价呢？生产计划问题（生产计划问题（LP1）资源定价问题（资源定价问题（LP2）原料原料A原料原料B工时工时CY1Y2Y3产品产品1产品产品2原料原料A原料原料B工时工时C产品产品1产品产品2方程对变量，变量对方程方程对变量，变量对方程 min w=5y1+4y2+9y3 y1+2 y2+4y332 y1+y2+3y32y1,y2,y3 03.1.2 规范形式线性规划的对偶问题规范形式线性规划的对偶问题原问题（LP1）对偶问题（LP2）原问题（LP1）对偶问题（LP2）目标目标max型型 目标目标min型型 有有n个变量（非负）个变量（非负）有有n个约束（大于等于）个约束（大于等于）有有m个约束个约束（小于等于）（小于等于）有有m个变量（非负）个变量（非负）价值价值系数系数 资源系数资源系数 资源资源系数系数 价值价值系数系数 技术系数矩阵技术系数矩阵 技术系数矩阵的转置技术系数矩阵的转置(AB)=AB(AB)=BA(A)=A 矩阵转置 3.1.3 非规范形式线性规划的对偶问题非规范形式线性规划的对偶问题1 变量取值范围不符合非负要求的情况变量取值范围不符合非负要求的情况将其约束方程第二行将其约束方程第二行左右同乘左右同乘-1：令令 解解:令令2 约束方程不是约束方程不是“”的情况的情况 解：约束方程第二解：约束方程第二行左右同乘行左右同乘1：其对偶规划为：其对偶规划为：令 得到原问题的对偶问题为：解解:约束方程第二行的等约束方程第二行的等式拆为两个不等式式拆为两个不等式:其对偶规划为：其对偶规划为：令 得到原问题的对偶问题为：3.1.4 总结总结方程对变量，变量对方程；方程对变量，变量对方程；正常对正常，不正常对不正常；正常对正常，不正常对不正常；变量正常是非负，方程正常看目标变量正常是非负，方程正常看目标(max ，min)。max=7y1+4y2-2y3 2y1+y2 -y3 3 y1 +3y3 2-4y1+2y2 -6 y1 -y2-y3 0 3y1 +y3 1 y10,y20,y3无约束无约束 =min z=3x1+2x2-6x3+x5 2x1+x2-4x3+x4+3x57 x1+2x3-x4 4 -x1+3x2 -x4+x5=-2 x1,x2,x30;x4 0;x5无约束无约束例例 求解下面线性规划的对偶规划求解下面线性规划的对偶规划LP2:min w=5y1+4y2+9y3 y1+2 y2+4y33 st.2 y1+y2+3y32 y1,y2,y3 0 x1+2x2 5 2x1+x2 4 4x1+3x2 9 x1,x2 0LP1:max z=3x1+2x2st.对偶变量对偶变量y1y2y3对偶变量对偶变量x1x2 x x1 1+2x2+x3 =52x1+x2 +x4 =44x1+3x2 +x5=9 x1,x2,x3,x4,x50 y1+2y2+4y3 y4 =32y1+y2+3y3 y5=2 y1,y2,y3,y4,y5 0原原问题变量问题变量原问题松弛变量原问题松弛变量CBXBx1x2x3x4x5b032x3x1x20100011005/23/2-2-3/2-1/213/23/21-j j0001/21/213/2原问题松弛变量原问题松弛变量原原问题变量问题变量x3 x4x5x1x2对偶问题剩余变量对偶问题剩余变量对偶问题变量对偶问题变量y4 y5y1y2y3对偶问题变量对偶问题变量对偶问题剩余变量对偶问题剩余变量CBXBy1y2y3y4y5b49y2y3-5/415/21001-1/41/21/4-3/21/21/2j j3/2003/2113/232000CBXBx1x2x3x4x5b000 x3x4x5124213100010001549320000030 x3x1x50103/21/21100-1/21/2-200132101/20-3/206032x3x1x20100011005/23/2-2-3/2-1/213/23/21000-1/2-1/213/2max z=CX+0XS st.AX+I XS=b (I式式)X,XS0I 式式经过若干迭代，经过若干迭代，基矩阵为基矩阵为B，则则上式上式等价与等价与：max z=CBXB+CNXN+0XS st.BXB+NXN+I XS=b XB,XN,XS0max z=CX st.AX b X0LP:max Z=CB B-1b+（CN-CB B-1N）XN-CB B-1XS st.XB+B-1N XN+B-1XS=B-1b XB，XN，XS 0 单纯形算法的矩阵表示单纯形算法的矩阵表示基基解解 XB XN XSXSb B N I j CB CN 0基基解解 XB XN XSXBB-1b I B-1N B-1 j 0 CN-CB B 1N -CB B-1初始单纯形表初始单纯形表基为基为B时单纯形表时单纯形表单纯形算法的矩阵表示单纯形算法的矩阵表示Cj23 500bCBXBx1x2 x3x4x50 x42/3 1/3 4/31011/60 x52/3 4/3 10/30110/3j j23 50000 CN-CBB-1N-CBB-1CBB-1bCB CN 00例例:max z=2x1+3x2+5x3 2/3 x1+1/3 x2+4/3x311/6 st.2/3 x1+4/3x2+10/3x310/3 x1,x2,x3 0BINB-1NIB-1Cj23 50 0bCBXBx1x2 x3x4 x52x11 0 12-1/223x20 1 2-1 13/2j j00 -3-1 -217/2初初始始表表最最终终表表3max z=2x1+3x2+5x3 2/3 x1+1/3 x2+4/3x3+x4=11/6 st.2/3 x1+4/3x2+10/3x3+x5=10/3 x1,x2,x3，x4,x5 0基基解解 XB XN XSXBB-1b I B-1N B-1 j 0 CN-CB B 1N -CB B-1基为基为B时单纯形表时单纯形表若若B为最优基，则为最优基，则 CB CBB 1B =0CN CBB 1N 0 -CBB-1 0则则 AY C Y0=Yb=CBB1 b=z*令令 Y=CBB1，Y =S S =CBB1YS=C CBB1AC CBB 1A 0-CBB 10例：下表为例：下表为“max，”型线性规划问题加入松弛变量后型线性规划问题加入松弛变量后的最优解单纯形表的最优解单纯形表BV.x1x2x3x4x5bx1100105x500-1/21/211x2011/2-1/20200-3/2-1/20（1 1）问题中有几个约束方程、几个决策变量、几个）问题中有几个约束方程、几个决策变量、几个松弛变量？松弛变量？（2 2）此线性规划问题的最优解）此线性规划问题的最优解x*=?x*=?（3 3）对偶问题的最优解）对偶问题的最优解y*=?y*=?3.2 对偶规划的基本性质对偶规划的基本性质3.2.1 对称性定理对称性定理：线性规划的对偶问题的对偶问题：线性规划的对偶问题的对偶问题是原问题是原问题证明：证明：对偶的定义对偶的定义对偶的定义对偶的定义max z=CXs.t.AXb X 0min w=bYs.t.AYCY 0min z=-CXs.t.-AX-bX 0max w=-bYs.t.-AY-CY 0以下定理以下定理3.2.2-3.2.5，假定原问题是，假定原问题是(3.1)，对，对偶问题是偶问题是(3.2)。3.2.2 弱对偶性定理弱对偶性定理：如果：如果X、Y分别是原问题和对分别是原问题和对偶问题的一个可行解，则其对应的原问题的目偶问题的一个可行解，则其对应的原问题的目标函数值不大于对偶问题的目标函数值，也即标函数值不大于对偶问题的目标函数值，也即证明：因为证明：因为X、Y分别是原问题（分别是原问题（3.1）与对偶问题）与对偶问题（3.2）的可行解，故：）的可行解，故：所以所以推论一推论一：原问题任一可行解的目标函数值是其：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值一可行解的目标函数值是其原问题目标函数值的上界。的上界。推论二推论二：如果原问题存在无界解，则对偶问题：如果原问题存在无界解，则对偶问题一定无可行解；反之，如果对偶问题存在无界一定无可行解；反之，如果对偶问题存在无界解，原问题也一定不存在可行解。解，原问题也一定不存在可行解。(若其中一若其中一个问题为无界解，则另一个问题无可行解个问题为无界解，则另一个问题无可行解)注意，该推论的逆定理并不成立。注意，该推论的逆定理并不成立。3.2.3 最优性定理最优性定理:如果如果 是原问题的可行解，是原问题的可行解，是是其对偶问题的可行解，且有其对偶问题的可行解，且有 ，则：，则：是原问题和对偶问题的最优解。是原问题和对偶问题的最优解。证明证明:假设假设X*,Y*分别是原问题与对偶问题的最分别是原问题与对偶问题的最优解，则显然它们也是各自的可行解。优解，则显然它们也是各自的可行解。而根据最优解的定义，而根据最优解的定义，由弱对偶性定理得：由弱对偶性定理得：所以所以 因而因而 是也原问题的最优解是也原问题的最优解 同理，可证同理，可证 也是其对偶问题的最优解。也是其对偶问题的最优解。3.2.4 强对偶性定理（对偶定理）强对偶性定理（对偶定理）如果原问题存在最优解如果原问题存在最优解X*，则其对偶问题一定具，则其对偶问题一定具有最优解有最优解Y*，且，且则则Y*=0,且且AY*C所以由最优性定理知所以由最优性定理知Y*为对偶问题的最优解。为对偶问题的最优解。如果原问题存在最优解，假设其对应的基是如果原问题存在最优解，假设其对应的基是B，即，即 令令所以所以Y*满足对偶问题的约束条件满足对偶问题的约束条件,是其可行解是其可行解 又因为又因为 CX*=CBB1 b=(Y*)b=b Y*3.2.5 互补松弛定理互补松弛定理线性规划问题的最优解中，线性规划问题的最优解中，线性规划问题的最优解中，线性规划问题的最优解中，yi xSi=0 xj ySj=0yi0,分为两种情况：分为两种情况：yi0，变量比较松；，变量比较松；yi=0，变量比较紧；，变量比较紧；互补松弛定理的解释互补松弛定理的解释约束方程约束方程 分为两种情况：分为两种情况：,约束条件比较松；约束条件比较松；,约束条件比较紧约束条件比较紧变量同其对偶问题的约束方程之间至多只能够有一个取松弛的情况，当其中一个取松弛的情况时，另外一个比较紧，即取严格等号。例例3.6 已知下面的已知下面的LP1和和LP2为一组对偶规划，且已知为一组对偶规划，且已知LP1的最优解为的最优解为X=（1.5，1）T。试运用互补松弛定理。试运用互补松弛定理求出对偶问题的最优解求出对偶问题的最优解Y。解：由解：由X=（1.5，1），得），得联立求解得：联立求解得：生产计划问题（生产计划问题（LP1）资源定价问题（资源定价问题（LP2）max z=3x1+2x2 x1+2x2 5 2x1+x2 4 4x1+3x2 9 x1,x2 0st.y1+2 y2+4y33 st.2 y1+y2+3y32 y1,y2,y3 0 min w=5y1+4y2+9y3 3.3 影子价格和灵敏度分析影子价格和灵敏度分析 3.3.1 影子价格影子价格 对偶变量的经济含义就是资源的定价，然而对偶变量的经济含义就是资源的定价，然而这种价格同市场价格不同，我们称之为影子价格。这种价格同市场价格不同，我们称之为影子价格。它反映了资源对于企业的紧缺程度、利润贡献程它反映了资源对于企业的紧缺程度、利润贡献程度等，并不能反映资源的生产成本，以及在外部度等，并不能反映资源的生产成本，以及在外部市场的紧缺程度。市场的紧缺程度。1 1、影子价格是边际利润、影子价格是边际利润如果某种资源有剩余，则增加资源不会增加利润；如果某种资源有剩余，则增加资源不会增加利润；如果某种资源影子价格大于如果某种资源影子价格大于0 0，则资源一定没有剩余。，则资源一定没有剩余。说明资源增加说明资源增加1 1个单位，企业总利润可以增加个单位，企业总利润可以增加y yi i单位。单位。所以如果资源的市场价格低于所以如果资源的市场价格低于y yi i，就要买进。，就要买进。互补松弛定理互补松弛定理y1y2ym2、影子价格是影子价格是产品的机会成本产品的机会成本(Opportunity Cost)机会成本机会成本 表示减少一件产品所节省的资源可以增加的利润表示减少一件产品所节省的资源可以增加的利润减少一件产品可以节省的资源减少一件产品可以节省的资源0 xxxxbxaxaxaxabxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211+=LLLLLLLLLLLLLLLLL增加单位资源可以增加的利润增加单位资源可以增加的利润如果该产品机会成本大于利润，则该产品不生产。如果该产品机会成本大于利润，则该产品不生产。对于原有产品，如果生产的，则其机会成本等于对于原有产品，如果生产的，则其机会成本等于利润。利润。对于原有产品对于原有产品j j，其机会成本为，其机会成本为 在利润最大化的生产计划中在利润最大化的生产计划中（1）影子价格大于）影子价格大于0的资源没有剩余；的资源没有剩余；（2）有剩余的资源影子价格等于）有剩余的资源影子价格等于0；（3）安排生产的产品机会成本等于利润；）安排生产的产品机会成本等于利润；（4）机会成本大于利润的产品不安排生产。）机会成本大于利润的产品不安排生产。总结3.3.2 灵敏度分析灵敏度分析1、目标函数系数、目标函数系数cj变化变化例例 3.7 C由由(3.2)变为变为(3,1)，请问最优生产计划如何变化？，请问最优生产计划如何变化？32000CBXBx1x2x3x4x5b000 x3x4x512421310001000154932000032000CBXBx1x2x3x4x5b032x3x1x20100011005/23/2-2-3/2-1/213/23/21000-1/2-1/211114 5初初始始表表最最优优表表z解：由原最优单纯形表得：解：由原最优单纯形表得：31000CBXBx1x2x3x4x5b031x3x1x20100011005/23/2-2-3/2-1/213/23/21000-5/21/211/2所以原最优解不是新问题的最优解所以原最优解不是新问题的最优解单纯形迭代得：单纯形迭代得：31000bCBxBx1x2x3x4x50 x30 3/21 -1/2033x11 1/20 1/2020 x50 10 -21 1 0 -1/20-3/206所以得到新的最优生产计划为产品所以得到新的最优生产计划为产品I生产生产2件，件，产品产品II不生产，此时总利润上升为不生产，此时总利润上升为6万元。万元。例例3.8 假设产品假设产品II的价格不变，请问产品的价格不变，请问产品I的利润在什的利润在什么范围内波动时，最优生产计划不变？么范围内波动时，最优生产计划不变？欲使最优生产计划不变，须欲使最优生产计划不变，须解：假设解：假设c1由由3变为变为 ，则，则32000bCBxBx1x2x3x4x50 x30 0 1 5/2-3/23/23x11 0 0 3/2-1/23/22x20 1 0 -2 1 1 0 0 0 -1/2-1/213/2所以所以,当当-1/3,1,即即c1 8/3,4时时,最优生产计划不变最优生产计划不变最优解保持不变的最优解保持不变的C变化范围变化范围2、约束条件右端向量约束条件右端向量b的变化的变化 例例3.8 b由由(5 4 9)T变为变为(5 5 9)T，最优生产计划如何变化？，最优生产计划如何变化？32000CBXBx1x2x3x4x5b000 x3x4x512421310001000154932000032000CBXBx1x2x3x4x5b032x3x1x20100011005/23/2-2-3/2-1/213/23/21000-1/2-1/213/25b1 b2 b3 z初初始始表表最最优优表表解：解：显然显然X=(3,-1,4,0,0)T不是基可行解不是基可行解XB带入原最终单纯形表得：带入原最终单纯形表得：32000bCBxBx1x2x3x4x50 x30 0 1 5/2-3/24(1)3x11 0 0 3/2-1/23(2)2x20 1 0 -2 1 -1 (3)0 0 0 -1/2-1/27(4)l因为因为x2=-10，所以令其，所以令其岀岀基。基。minbi/bi0=brl检验数所在行除以出基变量所在行，商最小的列对应的元检验数所在行除以出基变量所在行，商最小的列对应的元素作为主元素素作为主元素min /arj ,arj0 。这里。这里正数和零不能作正数和零不能作为主元素为主元素。l本题中第三行只有本题中第三行只有a34=-20，所以选为主元素，进行对偶，所以选为主元素，进行对偶迭代迭代l迭代的目标：迭代的目标：右端向量划为非负右端向量划为非负把基变量所在列划成单位矩阵把基变量所在列划成单位矩阵基变量检验数化为零。基变量检验数化为零。因因x2=-10 扩大第一种资源或第二种资源的量扩大第一种资源或第二种资源的量 1/2 -1/2 0 b1 b1/2-4xB=B-1b=-1/8 3/8 0 8 =-b1/8+3 0 1 -2 1 8 b1-8 解得解得 b1 8，24所以第一种资源最大扩大所以第一种资源最大扩大24-12=12单位单位此时此时z*=CBXB=(1 2 0)(8 0 16)T=8 求求b1的变化范围的变化范围 同理同理 b2 4，10，第二种资源最大扩大，第二种资源最大扩大10-8=2单位单位此时此时z*=CBXB=(1 2 0)(1 9/4 0)T=11/2 要使最优基不变，需满足要使最优基不变，需满足：Cjc11000bCBXBx1x2x3x4x51x20 1 1/2-1/202c1x11 0 -1/83/803/20 x50 0 1-21 4j j00-1/4-1/40（6）求使最优基不变的）求使最优基不变的c1,c2的取值范围。的取值范围。解解:求求c1的变化范围的变化范围 3=c3-cBP3=0-(1 C1 0)(1/2 -1/8 1)T0 4=c4-cBP4=0-(1 C1 0)(-1/2 3/8 -2)T 0 4/3 c1 4同理同理 1/2 c1 3/2 3.3 试运用对偶理论试运用对偶理论证明证明下面的线性规划问题存在无界解。下面的线性规划问题存在无界解。证明证明:首先写出其对偶问题首先写出其对偶问题 x1+2x2 5 2x1+x2 4 4x1+3x2 9 x1,x2 0min w=7y1+5y2st.2y1+4y2 3-3y1 -y2 2 4y1+2y2 3 y1,y2 0由第二个约束条件，显然无可行解由第二个约束条件，显然无可行解而而x=(0,0,0)T是原问题的一个解是原问题的一个解,即原问题存在可行解即原问题存在可行解所以原问题存在无界解所以原问题存在无界解3.4 设有如下线性规划问题：设有如下线性规划问题：（1）写出其对偶问题；）写出其对偶问题；（2）利用对偶问题的性质证明原问题目标函数值）利用对偶问题的性质证明原问题目标函数值z6。