第三次课大M法对偶

1、 在实际问题中有些模型并不含有单位矩阵，为在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初始基可行解，在约束条件的了得到一组基向量和初始基可行解，在约束条件的等式左端等式左端加一组虚拟变量，得到一组基变量加一组虚拟变量，得到一组基变量。这种。这种人为加的变量称为人为加的变量称为人工变量人工变量，构成的可行基称为，构成的可行基称为人人工基工基，用大，用大M法或两阶段法求解，这种用人工变量法或两阶段法求解，这种用人工变量作桥梁的求解方法称为作桥梁的求解方法称为人工变量法。人工变量法。1.5.2 大大M和两阶段单纯形法和两阶段单纯形法1.5 单纯形法单纯形法 Simplex Method

2、. .,0 SSmaxZCXAXIXbstX X1.1.大大M法法2.2.两阶段法两阶段法1.5 单纯形法单纯形法 Simplex Method. .0 maxZCXAXbs tX. .0 maxZCXAXbs tX. .,0 SSmaxZCXAXIXbs tX X对于线性规划问题的标准形式：对于线性规划问题的标准形式：njxbxaxaxabxaxaxabxaxaxajmnmnmmnnnn, 2 , 1, 022112222212111212111max Z=c1x1+c2x2+cnxn1.5 单纯形法单纯形法 Simplex Method一、一、 大大M 单纯形法单纯形法1 1、思想：、思想

3、： 由于系数矩阵由于系数矩阵A中中不包含不包含mm 维单位子矩阵维单位子矩阵，我们，我们在每个约束中人为的加入一个变量，将约束化为在每个约束中人为的加入一个变量，将约束化为1.5 单纯形法单纯形法 Simplex Methodmnnnjxbxxaxaxabxxaxaxabxxaxaxajmmnnmnmmnnnnnn, 1, 2 , 1, 02211222222121111212111 新约束要与原约束等价当且仅当所有的人工变新约束要与原约束等价当且仅当所有的人工变量取值为零，为确保引入人工变量后新的线性规划量取值为零，为确保引入人工变量后新的线性规划问题与原线性规划问题求解一致，我们在新的线性

4、问题与原线性规划问题求解一致，我们在新的线性规划目标函数中设规划目标函数中设人工变量的系数为人工变量的系数为- -M（M00为一为一充分大的数），其作用为罚因子充分大的数），其作用为罚因子，这样只要人工变，这样只要人工变量是基变量且取值大于量是基变量且取值大于0,0,目标函数就不可能达到最目标函数就不可能达到最大值，因此原问题只要有可行解，新的线性规划问大值，因此原问题只要有可行解，新的线性规划问题的最优解中人工变量的取值一定为题的最优解中人工变量的取值一定为0 0， 这种方这种方法称为法称为大大M单纯形单纯形法（简称大法（简称大M法）。法）。1.5 单纯形法单纯形法 Simplex Meth

5、od大大M法法中加入人工变量后新的线性规划问题为中加入人工变量后新的线性规划问题为1.5 单纯形法单纯形法 Simplex Methodmax Z=c1x1+c2x2+cnxn Mxn+1 Mxn+mmnnnjxbxxaxaxabxxaxaxabxxaxaxajmmnnmnmmnnnnnn, 1, 2 , 1, 022112222221211112121112 2、应用举例：、应用举例：【例【例6】用大】用大M法解下列线性规划法解下列线性规划012210243423max321321321321321xxxxxxxxxxxxxxxZ、1.5 单纯形法单纯形法 Simplex Method【解】

6、首先将数学模型化为标准形式【解】首先将数学模型化为标准形式12312312345123max324342102210,1,2,5jZxxxxxxxxxxxxjxxx 式中式中x4，x5为松弛变量，为松弛变量，x5可作为可作为一个基变量，第一、三约束中分一个基变量，第一、三约束中分别加入人工变量别加入人工变量x6、x7，目标函，目标函数中加入数中加入Mx6Mx7一项，得到一项，得到人工变量单纯形法数学模型人工变量单纯形法数学模型12345146767231231235max324342102210,1,2,7jZxxxxxMMxxxxxxxxxxxxxxjxx +0 +0 1.5 单纯形法单纯形

7、法 Simplex Method12312312345123max324342102210,1,2,5jZxxxxxxxxxxxxjxxx cj32-100-M-MiCBXBbx1x2x3x4x5x6x7-Mx64 431 10104/10 x5101 12010010/2-Mx712-2100011/1j2M-3-M-2-2M+1M000-Mx63 650 1013/50 x58 3300108/3-1x312 21000-j6M-5-5M0M002x23/5 6/510- 1/500 x531/5 3/5003/51-1x311/5-2/501-2/50-j-500002x21301120

8、3x131/31015/31-1x319/30002/30-j152/300525/3012345146767231231235max324342102210,1,2,7jZxxxxxMMxxxxxxxxxxxxxxjxx +0+0 最优解最优解X(31/3，13，19/3，0，0)T；最优值；最优值Z152/31.5 单纯形法单纯形法 Simplex Method注意：注意： (1)M是一个很大的抽象的数，不需要给出具体的数是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；值，可以理解为它能大于给定的任何一个确定数值；(2)人工变量是帮助我们寻求原问题的可

9、行基人工变量是帮助我们寻求原问题的可行基，人工变，人工变量从模型中推出后，说明原问题有可行解，但不量从模型中推出后，说明原问题有可行解，但不能肯定有最优解。能肯定有最优解。 新的线性规划问题的最优解中人工变量取值必为新的线性规划问题的最优解中人工变量取值必为0 0，否则原，否则原问题无可行解问题无可行解，在得到新问题的最优解后，去掉人工变量便得到，在得到新问题的最优解后，去掉人工变量便得到原问题的最优解，相应的在新问题的最终单纯形表中去掉人工变原问题的最优解，相应的在新问题的最终单纯形表中去掉人工变量那一块即为原问题的最优单纯形表。量那一块即为原问题的最优单纯形表。注注: : (1) 迭代过程

10、中人工变量一旦出基就不会再进基，所以当迭代过程中人工变量一旦出基就不会再进基，所以当某个人工变量出基后，其对应的列可不再计算，以减少计算量；某个人工变量出基后，其对应的列可不再计算，以减少计算量；(2)在加入人工变量时，实际上不一定每个约束都加入人工变量，在加入人工变量时，实际上不一定每个约束都加入人工变量，例如某约束是例如某约束是“”型，则在加入松弛变量后，该松弛变量可作型，则在加入松弛变量后，该松弛变量可作为基变量；为基变量；1.5 单纯形法单纯形法 Simplex Method解解 的的 判判 断断唯一最优解的判断唯一最优解的判断：最优表中所有非基变量的检验最优表中所有非基变量的检验数非

11、零数非零,则线性规划具有唯一最优解。则线性规划具有唯一最优解。 多重最优解的判断多重最优解的判断: 最优表中存在非基变量的检验最优表中存在非基变量的检验数为零数为零,则线性规划具有多重最优解。则线性规划具有多重最优解。 无界解的判断无界解的判断: 某个某个k0且且aik(i=1，2,m)，则，则线性规划具有无界解。线性规划具有无界解。1.5 单纯形法单纯形法 Simplex Method无可行解的判断：无可行解的判断：当用大当用大M单纯形法计算得到最优解单纯形法计算得到最优解并且存在非零人工变量时，则表明原线性规划无可行并且存在非零人工变量时，则表明原线性规划无可行解。解。设有线性规划设有线性

12、规划0maxXbAXCXZ其中矩阵其中矩阵Amn 且且 r(A)=m,12( ,)nCc ccTmbbbb),(21X0理解为理解为X大于等于零的向量，即大于等于零的向量，即xj0( j=1,2,n)。TnxxxX),(211.5.3 计算公式计算公式1.5 单纯形法单纯形法 Simplex Method不妨假设不妨假设A(P1, P2, ,Pn)中前中前m个列向量构成一个可个列向量构成一个可行基，记为行基，记为B=(P1, P2 , ,Pm)。矩阵。矩阵A中后中后nm列构成列构成的矩阵记为的矩阵记为N(Pm+1, ,Pn), 则则A可以写成分块矩阵可以写成分块矩阵A=(B，N)。对于基对于基

13、B，基变量为，基变量为XB=(x1, x2 , , xm )T, 非基变量为非基变量为XN=(xm+1, xm+2, xn)T。 则则X可表示成可表示成 , 同理将同理将C 写成分块矩阵写成分块矩阵C=(CB，CN)，NBXXX CB=(C1,C2,Cm), CN=(Cm+1Cm+2，cn), 则则 AX=b 可写成可写成bNXBXXXNBNBNB)( ，1.5 单纯形法单纯形法 Simplex Method因为因为r(B)=m(或或|B|0)所以所以B -1存在，因此可有存在，因此可有 NNBNBNXBbBNXbBXNXbBX111)(令非基变量令非基变量XN=0，XB=B1b，由，由B是可

14、行基的假设，是可行基的假设，则得到基本可行解则得到基本可行解X=(B1b，0)T消去目标函数中的基变量，于是目标函数可写成消去目标函数中的基变量，于是目标函数可写成 NNBBNBNBXCXCXXCCZ),(1111()()BNNNBNBNCB bB NXC XC B bCC B N X1.5 单纯形法单纯形法 Simplex Method将将B化为化为E(E为为m阶单位矩阵阶单位矩阵), 即求基本可行解。即求基本可行解。用用B1左乘表中第二行左乘表中第二行,得到得到CBCNXBXNbCB XBE B-1NB-1bj0CBB-1N- -CNZ=CBB1bCBCNXBXNbBNb1.5 单纯形法单

15、纯形法 Simplex Method对于如下形式的线性规划问题：对于如下形式的线性规划问题：0maxXbAXCXZ引入松弛变量引入松弛变量 化为标准形如下：化为标准形如下：TmnnnsxxxX),(210, 00maxsssXXbEXAXXCXZ1.5 单纯形法单纯形法 Simplex Method 记记 则上述标准形式为则上述标准形式为,0,CCEAAXXXs0maxXbXAXCZ由于由于 对应的系数矩阵为单位阵，故容易确定初始基变量为对应的系数矩阵为单位阵，故容易确定初始基变量为 ， 得到如下初始单纯形表得到如下初始单纯形表:sXsXCX0Xs CB XsAEb-C001.5 单纯形法单纯

16、形法 Simplex Method CX0Xsb CB XBB-1A B-1B-1bjCB B-1A-CCB B-1CB B-1 b而对于而对于一般的基一般的基B为为 的子矩阵，的子矩阵，A1111111(),0BBBBB AB A BC CB ACCBA EC CB ACB1.5 单纯形法单纯形法 Simplex Method1.6 线性规划的对偶模型线性规划的对偶模型 Dual Model of LP 【例【例1】 某企业计划生产甲乙两种产品，生产单位产品所需设备某企业计划生产甲乙两种产品，生产单位产品所需设备A、B、C台时及产品的单位利润如下表：台时及产品的单位利润如下表： 建立总收益最

17、大的数学模型。建立总收益最大的数学模型。 1.6 线性规划的对偶模型线性规划的对偶模型 Dual model of LP产品产品车间（车间（资源）资源）单耗（工时单耗（工时/件）件）生产能力生产能力甲甲乙乙工时工时/天天x1x2A108B0212C3436利润（百元利润（百元/件）件）35一、引例一、引例【解】设【解】设x1，x2分别为产品分别为产品 甲、甲、乙的产量，则线性规划数学模乙的产量，则线性规划数学模型为：型为： 现在我们从另一个角度来考虑这个问题。假如有另外一个工厂现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备要求租用该厂的设备A、B、C，那么该厂的厂长应

18、该如何来确，那么该厂的厂长应该如何来确定合理的租金呢？定合理的租金呢？产品产品车间车间（资源）资源）单耗（工单耗（工时时/件）件）生产生产能力能力甲甲乙乙工时工时/天天x1x2A108B0212C3436利润（百利润（百元元/件）件）35 0,364368.53max21212121xxxxxxtsxxz123yyy1333yy23245yy123min81236Wyyy但对于租用者来说，他要求在满足上述要求的前提下，也就是在但对于租用者来说，他要求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越

19、好即即 这样我们得到了该问题的数学模型：这样我们得到了该问题的数学模型：123min81236Wyyy 设设 分别为设备分别为设备A、B、C的每台时的租金。为了叙的每台时的租金。为了叙述便，这里把租金定义为扣除成本后的利润。作为出租者来说，述便，这里把租金定义为扣除成本后的利润。作为出租者来说，把生产单位甲产品所需各设备的台时各总租金不应低于原利润把生产单位甲产品所需各设备的台时各总租金不应低于原利润3百元，即百元，即 ，否则就不出租还是用于生产甲，否则就不出租还是用于生产甲产品以获利产品以获利3百元；百元；3,21,yyy1333yy同样把生产一单位乙产品所需各设备的台时的总租金也不应当低同

20、样把生产一单位乙产品所需各设备的台时的总租金也不应当低于原利润于原利润5百元，百元， 即即，否则这些设备台时就不出租，还是用于生产乙产品以获利，否则这些设备台时就不出租，还是用于生产乙产品以获利5百元。百元。23245yy 收益优化模型为收益优化模型为0,54233. .36128min3213231321yyyyyyyt syyyw1.6 线性规划的对偶模型线性规划的对偶模型 Dual model of LP123132312381236332450 minwyyyyys.t.yyy ,y ,y1212121235821234360max zxxxxs.t.xxx , x 互为对偶模型互为对

21、偶模型12345610,1,0,20,042yyyyyyw 最最优优解解：1234546400max42xxxxxz 最优解：最优解：，收益优化模型为收益优化模型为生产利润的优化模型生产利润的优化模型max. .TzC XAXbs tXO min.TTwb YA YCs tYO 从上面可知租金：从上面可知租金：A A设备为设备为0 0元，元，B B设备为设备为1/21/2百元，百元，C C设备为设备为1 1百元。百元。这样把工厂的所有设备出租可共得租金这样把工厂的所有设备出租可共得租金4242百元。对出租者来说这百元。对出租者来说这租金是出租者租金是出租者愿出租设备的最小费用愿出租设备的最小费

22、用，因为这是目标函数的最小值。，因为这是目标函数的最小值。 12345610,1,0,0,02yyyyyy二、资源的影子价格二、资源的影子价格1.6 线性规划的对偶模型线性规划的对偶模型 Dual model of LP*YbWCXZT 由由于于是是变变化化的的，则则假假设设mbbb,211、 y*i的数学含义的数学含义mmbZybZybZy *2*21*1,*22*11*mmybybybZ 所以所以 可以理解为当第可以理解为当第i资源变化资源变化1个单位时，原问题个单位时，原问题的最优目标函数值（即利润）的变化量的最优目标函数值（即利润）的变化量.*iy1x2x)0 , 0(O)0 , 8(

23、A)6 , 4(C)6 , 0(D364321 xx81 x62 x)3 , 8(B(3,5)最优解最优解(4,6)Z=4212121212max358212. .3436,0 zxxxxs txxx x当两种产品的产量分别为当两种产品的产量分别为x1=4, x2 =6=6时，第一种资源还剩时，第一种资源还剩4 4；第二种资源用完；第三种资源用完第二种资源用完；第三种资源用完. .Z=43(13/3,6)2132 xZ=85/2(30/3,13/2)资源的影子价格：资源的影子价格：y1=0, y2=1/2, y3=1.*12310,12 yyy资源的影子价格：资源的影子价格：根据影子价格的含义

24、，表明：根据影子价格的含义，表明：2b变化变化1个单位，则个单位，则 变化变化0.5；*Z1b变化变化1个单位，则个单位，则 没有变化；没有变化；*Z3b变化变化1个单位，则个单位，则 变化变化1；*Z (1)对偶问题的最优解对偶问题的最优解买主的最低出价。买主的最低出价。 (2)原问题资源的影子价格原问题资源的影子价格当该资源增加当该资源增加1单位时引起单位时引起的总收入的增量的总收入的增量卖主的内控价格。卖主的内控价格。 (3)代表在资源最优利用条件下对单位第代表在资源最优利用条件下对单位第i种资源的估价，种资源的估价，这种估价不是资源的市场价格，而是根据资源在最优生产配置这种估价不是资源

25、的市场价格，而是根据资源在最优生产配置中作出的贡献而作的估价，为区别起见，称为影子价格中作出的贡献而作的估价，为区别起见，称为影子价格（shadow price)。 资源影子价格资源影子价格资源市场价格资源市场价格 资源的市场价格是已知数，相对比较稳定，而它的影子价资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。产品结构等情况发生变化，资源的影子价格也随之改变。即：市场价格由市场确定；影子价格由生产企业确定。即：市场价格由市场确定；影子

26、价格由生产企业确定。2、 y*i的经济学含义的经济学含义(4)资源的影子价格实际上又是一种机会成本。资源的影子价格实际上又是一种机会成本。 在完全市场经济条件下在完全市场经济条件下,当：当： 资源的市场价格资源的市场价格影子价格，应卖出这种资源影子价格，应卖出这种资源 随着资源的买进卖出，它的影子价格也将随之发生变化，随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。一直到影子价格与市场价格保持同等水平时，才处于平衡状态。3 3、影子价格的作用、影子价格的作用（1 1）调节生产规模）调节生产规模: :例如，目标函数例如，目标函数Z Z表示

27、利润（或产值），表示利润（或产值），当第当第i i种资源的影子价格大于零（或高于市场价格）时种资源的影子价格大于零（或高于市场价格）时, ,表示表示有利可图，企业应购进该资源扩大生产规模，当影子价格等有利可图，企业应购进该资源扩大生产规模，当影子价格等于零（或低于市场价格），企业不能增加收益，这时应将资于零（或低于市场价格），企业不能增加收益，这时应将资源卖掉或出让，缩小生产规模源卖掉或出让，缩小生产规模 (2)(2)影子价格是企业生产过程中资源的一种隐含的潜在价值，表影子价格是企业生产过程中资源的一种隐含的潜在价值，表明单位资源的贡献，是企业内部根据资源对生产的贡献而作的明单位资源的贡献，是

28、企业内部根据资源对生产的贡献而作的估计，贡献越大价格越高，是资源效率的一种评价，与市场价估计，贡献越大价格越高，是资源效率的一种评价，与市场价格是不同的两个概念。同一种资源在不同的企业、生产不同的格是不同的两个概念。同一种资源在不同的企业、生产不同的产品或在不同时期影子价格都不一样。例如，某种钢板市场价产品或在不同时期影子价格都不一样。例如，某种钢板市场价格是每吨格是每吨80008000元，一个企业用来生产汽车，另一个企业用来生元，一个企业用来生产汽车，另一个企业用来生产空调外壳，每吨钢板的产值是不一样的。而资源的市场价是产空调外壳，每吨钢板的产值是不一样的。而资源的市场价是已知的，是商品价值

29、的货币表现。已知的，是商品价值的货币表现。 （3 3）告诉管理者增加何种资源对企业更有利）告诉管理者增加何种资源对企业更有利 （5 5）为新产品定价提供依据）为新产品定价提供依据(4)(4)了解生产要素对产出贡献的分解。通过影子价格分了解生产要素对产出贡献的分解。通过影子价格分析每种资源获得多少产出。例如，企业获得析每种资源获得多少产出。例如，企业获得100100万元的万元的利润，生产过程中产品的直接消耗的资源有材料甲、材利润，生产过程中产品的直接消耗的资源有材料甲、材料乙，这些资源各产生多少利润，由影子价格可以大致料乙，这些资源各产生多少利润，由影子价格可以大致估计出来估计出来。 11221

30、1112211211222221122.01,2,.max., nnnnnnmmmnnmjZc xc xc xa xa xa xba xa xa xbs ta xaxaxbxjn 1P112211121211121222221122min.01,2,.,mmmmmmnnmnmniwb yb yb ya ya yayca ya yaycs ta yayaycyim 1D称作互为对偶的线性规划问题，其中一个称为原问题，另一个称称作互为对偶的线性规划问题，其中一个称为原问题，另一个称为它的对偶问题。用矩阵形式分别写为为它的对偶问题。用矩阵形式分别写为 max. .TzC XAXbs tXO min.

31、TTwb YA YCs tYO 三、对偶模型三、对偶模型1. 1. 规范（对称）形式的的对偶规范（对称）形式的的对偶 max型型min型型式号式号右端右端目标目标 式号式号min w目标目标右端右端 max z12ncccnx2x1x从横行上看表示原线性规划问题（从横行上看表示原线性规划问题（ ）1P从纵列上看表示对偶线性规划问题（从纵列上看表示对偶线性规划问题（ )1D 0 0 0111212122212nnmmmnaaaaaaaaa12mbbb12000 myyy1. 1. 规范（对称）形式的的对偶问题的对偶表：规范（对称）形式的的对偶问题的对偶表：解：对偶关系表解：对偶关系表 Max型型

32、 min型型例例1 1试建立下述试建立下述LP问题的对偶关系表，并写出其对偶问题问题的对偶关系表，并写出其对偶问题 max Z =2x1+3x2 s.t. x1+ 2x28 4x1 16 4x2 12 x1 ,x2 0 对偶对偶min W =8y1+16y2+12y3 s.t. y1+4y2 2 2y1 +4y3 3 y1 ,y2,y3 0yyy123xx1200zw12840160412230001242yy13243yy123min81612wyyy解：对偶关系表解：对偶关系表 Max型型 min型型wxxxxxxxxs txxxxxx 12123123123123min34334748.

33、 .1,0例例2 2 写出下列写出下列LPLP问题的对偶问题问题的对偶问题zyyyyyyyyys tyyyyyy 123123123123123max7834334. . 40,0对偶对偶340000321 xxxyyy123zw3-34741181-1110002.2.非对称非对称LPLP问题的对偶问题问题的对偶问题例例3 3 写出下列写出下列LPLP问题的对偶问题问题的对偶问题解：用解：用x2= -x2, x3=x3-x3代入上述代入上述LP问题，并将其问题，并将其化为第一类对称形式化为第一类对称形式max Z = x1+2x2+x3 x1+x2-x3 2 s.t. x1 -x2+x3 =

34、 1 2x1+x2+x3 2 x10, x20 ,x3无约束无约束 max Z = x12x2 +x3 x3 x1 x2 x3+x3 2 x1+x2+x3 x3 1s.t. x1 x2 x3+x3 1 2x1+x2 x3+x3 2 x1, x2, x3, x3 0 x1 -x2+x3 1x1 -x2+x3 1x1 -x2+x3 1-x1 +x2-x3 - 1-2x1-x2-x3 -2上述第一类对称形式上述第一类对称形式LP问题的对偶问题为：问题的对偶问题为：则上述问则上述问题变为：题变为：min W =2y1+y2 y32y4 y1+y2 y32y4 1 y1+y2 y3 +y4 -2 s.t

35、. y1+y2 y3y4 1 y1 y2+y3 +y4 -1 y1, y2, y3, y4 0 min W =2u1+u2+2u3 u1+u2+2u3 1 s.t. u1 u2+ u3 2 u1+u2+ u3 =1 u10, u30 ,u2无约束无约束 令令 u1= y1 u2=y2y3 u3=y4max Z = x12x2 +x3 x3 x1 x2 x3+x3 2 x1+x2+x3 x3 1s.t. x1 x2 x3+x3 1 2x1+x2 x3+x3 2 x1, x2, x3, x3 0 -y1+y2 -y3 -y4 1y1-y2+y3 -y4 2(D)min W =2u1+u2+2u3

36、u1+u2+2u3 1 s.t. u1 -u2+ u3 2 -u1+u2+ u3 =1 u10, u30 ,u2无约束无约束 (L)max Z = x1+2x2+x3 x1+x2-x3 2 s.t. x1 -x2+x3 = 1 2x1+x2+x3 2 x10, x20 ,x3无约束无约束 对偶关系：对偶关系：一个问题第一个问题第i个变量的约束情况决定另一问题个变量的约束情况决定另一问题第第i个约束不等式的方向，反之亦然。个约束不等式的方向，反之亦然。正常的对正常的，不正常的对不正常的正常的对正常的，不正常的对不正常的 原问题约束条件是等式对应于对偶问题决策变量无原问题约束条件是等式对应于对偶问

37、题决策变量无约束，反之亦然约束，反之亦然 max型型min型型式号式号右端右端目标目标 . . 式号式号min w目标目标右端右端 max znc2c1c1200 yy12bbnx2x1x从横行上看表示原线性规划问题（从横行上看表示原线性规划问题（ ）1P从纵列上看表示对偶线性规划问题（从纵列上看表示对偶线性规划问题（ )1D 0 0 00 =无约束无约束111212122212nnmmmnaaaaaaaaa非对称非对称LPLP问题的对偶问题的对偶表：问题的对偶问题的对偶表：0 iijjybyb无约束无约束解：对偶关系表解：对偶关系表 Max型型 min型型bicj对偶对偶例例4：试写出下述：

38、试写出下述LP问题的对偶问题问题的对偶问题 0, 0, 0426323.23max321321321321xxxxxxxxxtsxxxz1212121212min6433221.32, wyyyyyys tyyy y 无约束yy12 xxx 123000zw无约束无约束无约束无约束32-3 61-21 43-1-2=解：对偶关系表解：对偶关系表 Max型型 min型型yyy123zw0=对偶对偶0无约束无约束例例5.写出下述写出下述LP问题的对偶问题：问题的对偶问题： 11-121-11= 1211 21211231231231231232 2 1. .2 20,0, maxZxxxxxxxx

39、xs txxxxxx 无约束123123123123123min22212. .1,0 wyyyyyyyyys tyyyyyy0 无约束12300 xxx无约束无约束例例6.写出下述写出下述LP问题的对偶关系表，问题的对偶关系表，并写出其对偶问题：并写出其对偶问题： 解：对偶关系表解：对偶关系表 Max型型 min型型xxx 12300自自由由yy12zw1212121212max7365236. .7,0 zyyyyyys tyyyy无约束123123123132min56727.633,0, wxxxxxxs txxxx xx 无约束无约束无约束012-1=-76-313 5 -6 7=对

40、偶对偶jmaxzxxxxxxs.txxx( j, ) 1212121212322122841641201 2（）对偶对偶iminwyyyyyyys.tyyyy(i, , , ) 12341231241281612242224301 2 3 4j)minwxxxxxxxxxxs.txxxxxx( j, , ) 123451234512345267554132205801 25对偶对偶imaxzyyyyyyyys.tyyyyy(i, ) 1212121212122085146135721501 2练习练习 写出下述写出下述LP问题的对偶问题：问题的对偶问题： (3)max Z = x1+2x2+x

41、3 x1+x2-x3 2 s.t. x1 -x2+x3 = 1 2x1+x2+x3 2 x10, x20 ,x3无约束无约束 (D)min W =2y1+y2+2y3 y1+y2+2y3 1 s.t. y1 -y2+ y3 2 -y1+y2+ y3 =1 y10, y30 ,y2无约束无约束 对偶对偶0, 01553232.23min3132121321321xxxxxxxxxxtsxxxw 无约束无约束32131321321321, 0, 0132533252maxyyyyyyyyyyyyyyz(4)对偶对偶1.7对偶性质对偶性质Dual property 0maxXbAXCXZ对偶问题是对

42、偶问题是(记为记为DP)：0minYCYAYbw这里这里A是是mn矩阵矩阵, X是是n1列向量列向量, Y是是1m行向量。行向量。【性质性质1】 对称性对称性: 对偶问题的对偶是原问题。对偶问题的对偶是原问题。 设原问题是设原问题是(记为记为LP)： 1.7 对偶性质对偶性质Dual property一、一、 对偶性质对偶性质【性质性质2】 弱对偶性弱对偶性: 设设X*、Y*分别为分别为LP(max)与与 DP(min)的可行解，则的可行解，则 bYCX*【性质性质3】最优准则定理最优准则定理: 设设X*与与Y*分别是分别是(LP)与与(DP)的可行解，则的可行解，则X*、Y*是是(LP)与与

43、(DP)的最优解当且仅当的最优解当且仅当C X*= Y*b .【性质性质4】对偶性：对偶性：若互为对偶的两个问题其中一个有若互为对偶的两个问题其中一个有最优解，则另一个也有最优解，且最优值相同。最优解，则另一个也有最优解，且最优值相同。1.7 对偶性质对偶性质Dual property*(max)(min)LPDPCXY b在用单纯形法求解在用单纯形法求解LPLP问题（问题（LPLP）的最优单纯形表中松）的最优单纯形表中松弛变量的检验数的数就是其对偶问题（弛变量的检验数的数就是其对偶问题（DPDP）的最优解）的最优解 Cj CB CN 0CBXB XB XN XS b CB E B-1N B-

44、1 B-1b 0CBB-1N CN 0 CBB-1MaxZ=CB(B-1b)minW = (CBB-1)b*1.用单纯形法只要做用单纯形法只要做LP或或LD一个问题，即可同时得一个问题，即可同时得LP及及LD的最优解。的最优解。*2若若LP目标函数无界（无最优解），则目标函数无界（无最优解），则LD也无可行解。也无可行解。j 0maxXbAXCXZ0minYCYAYbw1.7 对偶性质对偶性质Dual property【性质性质5】LP(max)的检验数对应于的检验数对应于DP(min)的一组基的一组基本解。本解。 其中第其中第j个决策变量个决策变量 的检验数对应于的检验数对应于(DP)中第中

45、第j个松弛变量个松弛变量 的解，第的解，第i个松弛变量个松弛变量 的的检验数对应于第检验数对应于第i个对偶变量个对偶变量 的解。反之，的解。反之，(DP)的的检验数对应于检验数对应于(LP)的一组基本解。的一组基本解。jSyiSxiyjxT（B） 3 5000基基解解比值比值08101000120 201003634001检验行检验行0-3-50005x4x3x2x1xjc543xxx12 36min,6240810100560101/20012300-21检验行检验行30-3005/208 12min,413040012/3-1/3560101/2034100-2/31/3检验行检验行420

46、001/21xxx321对应的基本可行解：对应的基本可行解： 1234546400max42xxxxxz，523xxx )5 , 2 , 1(036431228.53max521423121jxxxxxxxxtsxxzjy4 ， y5， y1 y2 ， y3 12/2= 6 36/4=98/1=812/3=4 加上松弛变量加上松弛变量 和人工变量和人工变量 ，把此问题化成标准型，把此问题化成标准型如下：如下：45,yyy6iwyyyyyMyyyys tyyyyyi 1234561342356max()812360033. .2450,1,6123132312381236332450 minwy

47、yyyys.t.yyy ,y ,ycj-8-12-3600-MiCBXBby1y2y3y4y5y6-8y13103- 1003/3-My650240-115/4j0-2M+12-4M+128M0-36y311/301- 1/300-My61-4/3204/3-11j4/3M-4-2M+1204/3M+12M0-36 y311/301- 1/30-12y21/2-2/3102/3-1/2 jZ=4240046iwyyyyyMyyyys tyyyyyi 1234561342356max()812360033. .2450,1,6x3 x4 x5 x1 x2 12312123123min300400

48、250250.100,0wyyyyys t yyyy y y 121212212max501003002400. .250,0Zxxxxxxs txx x 收益优化模型为收益优化模型为 生产利润的优化模型生产利润的优化模型-36 y311/301- 1/30-12y21/2-2/3102/3-1/2 jZ=4240046x3 x4 x5 x1 x2 cj-8-12-3600-MiCBXBby1y2y3y4y5y6-8y13103- 1003/3-My650240-115/4j0-2M+12-4M+128M01.8 对偶单纯形法对偶单纯形法Dual Simplex Method1.8 对偶单纯形

49、法对偶单纯形法Dual Simplex Methodmax( )0ZCXAXbPX设线性规划问题为：设线性规划问题为：原始单纯形法的思想原始单纯形法的思想： 从满足可行性条件的一个基可行解从满足可行性条件的一个基可行解(即基即基B满足满足 )出发，经过换基运算迭代到另一个基可行解，出发，经过换基运算迭代到另一个基可行解，直到找到满足最优性条件直到找到满足最优性条件( )的基可行解，的基可行解，这就是原问题的最优解。这就是原问题的最优解。10B b10BC B AC若上表为最优单纯形表，则下列两个式子同时成立：若上表为最优单纯形表，则下列两个式子同时成立：1(1)0B b(可行性条件，又叫对偶最

50、优性条件)1(2)0()BC B AC最优性条件,又叫对偶可行性条件问题：可否从满足条件问题：可否从满足条件(2)的基出发去找原问题的最优解？的基出发去找原问题的最优解？对偶单纯形法思想对偶单纯形法思想： 从满足条件从满足条件(2) 的基的基(一般称为一般称为正则基正则基)B出发，经出发，经过换基运算到另一个正则基，即一直保证条件过换基运算到另一个正则基，即一直保证条件(2)成立，成立，直到找到一个满足条件直到找到一个满足条件(1)的正则基。的正则基。CBB1bCBB1A - - C检验数检验数 B- -1 1bB- -1A XBXb1.8 对偶单纯形法对偶单纯形法Dual Simplex M

51、ethod【例【例1】123123123123min43543,0zxxxxxxxxxx x x先将约束不等式化为等式，再两边同乘以先将约束不等式化为等式，再两边同乘以(1)，得到，得到x4、x5 为基变量，用对偶单纯形法，迭代过程如表为基变量，用对偶单纯形法，迭代过程如表2-7所示。所示。1.8 对偶单纯形法对偶单纯形法Dual Simplex Method【解法【解法1】用对偶单纯形法求解】用对偶单纯形法求解/imax Zxxxxxxxxxxxx,i, 123123412354354301512312312312453min43543,0zxxxxxxxxxx x xxxCj-4-1-30

52、0CB XBbx1x2x 3x 4x 5表表 0(1) 0 x 4x55 3-1-1-11-141001检验数检验数-Z=041300表表2-7最优解：最优解：X(4，1，0， 0，0)T；Z=17表表 -1(2) 0 x2x55-8 1-21013-1101-Z=-5 30210表表 -1(3) -4 x2x11401105/2-3/2-1/2-1/21/2-1/2-Z=-170013/25/23/21.8 对偶单纯形法对偶单纯形法Dual Simplex Method1231234123543543015 /imax Zxxxxxxxxxxxx,i,对偶解：对偶解：Y(5/2，3/2，0,

53、 0, 13/2 )T；W=17【例【例1】求解】求解123123123123min43543,0zxxxxxxxxxx x x【解法【解法2】 大大M法法x6、x7为人工变量，用单纯形法，迭代过程如表所示。为人工变量，用单纯形法，迭代过程如表所示。1.8 对偶单纯形法对偶单纯形法Dual Simplex Method123671234612357max()435430,1,5iZxxxMxMxxxxxxxxxxxxi Cj-4-1-300-M -MCB XBbx1x2x 3x 4x 5x 6 x7表表 -M(1) -Mx 6x75 3111-1 1-4-100-11 0 0 14-2M13M

54、+3MM0 0表表 -M(2) -4x6x123012-15-4-101-1 1 00-2M+319-5MM-M+4 0表表 -3(3) -4 x3x12/523/5012/53/510-1/5-4/51/51/5-98/ 50-13/5019/51/51.8 对偶单纯形法对偶单纯形法Dual Simplex Method表表 -1(4) -4 x2x11401105/2-3/2-1/2-1/21/21/2-Z=-170013/25/23/2最优解：最优解：X(4，1，0, 0, 0)T；Z=17123671234612357max()435430,1,5iZxxxMxMxxxxxxxxxxxxi 对偶解：对偶解：Y(5/2，3/2，0, 0, 13/2 )T；W=17【例【例1】解法】解法3123123123123min43543,0zxxxxxxxxxx x xy3，y4、x5 为基变量，用单纯形法，迭代过程如表所示。为基变量，用单纯形