第二章 线性规划的对偶理论.doc

第二章 线性规划的对偶理论随着线性规划应用的逐步深入，人们发现线性规划有一个有趣的特性，就是每一个线性规划问题都存在另一个与之配对、两者有密切联系的线性规划问题.称其中一个为原问题，则另一个被称为对偶问题，这个特性称为线性规划的对偶性，这不仅仅是数学上具有的理论问题，由对偶问题引伸出来的对偶解有着重要的经济意义，也是经济学中重要的概念与工具之一. 对偶理论充分显示出线性规划理论逻辑上的严谨性与结构上的对称性，它是线性规划理论的重要成果.1 对偶问题的提出一、对偶问题的实例在第一章的例1.1中，讨论了某工厂资源的合理利用问题，建立了LP问题模型： s.t. 65 40 75 （2.1） 0已知最优解为：.现从另一个角度考虑这个问题.假定该厂的决策者考虑自己不生产甲、乙两种产品，而把原拟用于生产这两种产品的资源A,B,C全部出售给外单位，则应如何确定这三种资源的价格.显然，该厂的决策者要考虑两个原则：第一，每种资源所收回的费用应不低于自己生产时可获得的利润；第二，定价不能太高，要对方容易接受.设分别表示三种资源出售的价格，则由第一个原则，应有如下约束条件： 1500 2500 0而把原拟用于生产甲、乙产品的三种资源全部售出，总收入为： 当然，对厂方而言，w越大越好，但根据第二个原则，在保证上述条件下，应考虑使总收入即对方的总支出尽可能少才比较合理，因为只有这样，厂方不会吃亏，对方也容易接受.于是，该问题的数学模型归结为： s.t. 1500 2500 （2.2） 0这也是一个LP问题，用单纯形法解之得最优解为： 及相应的目标函数最优值 =70000. 如果称（2.1）给出的LP问题为原问题，则称（2.2）式为（2.1）式的对偶问题.二、对偶问题的形式以上从一个资源利用问题，引出了对资源的估价问题，得到了对偶规划.原问题与其对偶问题之间通常有三种不同的关系形式，以下将原问题记作（P）问题，对偶问题记作（D）问题.1、对称型对偶问题定义2.1 设原LP问题为 s.t. （2.3） 0 （）则称下列LP问题 s.t. （2.4） 0 （）为其对偶问题.其中（）称为对偶变量，并称（2.3），（2.4）为一对对称型对偶问题.如果用矩阵形式来表示模型（2.3），（2.4），则可更清楚地看出两者之间的对称性. （P） s.t. b （2.5） x0 （D） s.t. c （2.6） y0其中是一行向量.即（P）问题求极大化，（D）问题求极小化；（P）的约束为“”，（D）的约束为“”；（P）的价值系数c，在（D）中成为约束右端项；（P）的约束右端项b，在（D）中恰好价值系数；在（P）中，约束方程左端为Ax，而在（D）中，约束方程左端为yA，决策变量x、对偶变量y都是非负的.例2.1 写出（P）问题 s.t. 2 3 5 0 （ j = 1,2,3）的（D）问题.解：首先将问题化为式（2.3）的形式： s.t. 2 3 5 0 （ j = 1,2,3）再根据定义2.1，写出其（D）问题： s.t. 2 3 4 0 （i = 1,2,3）2、非对称型对偶问题如果原问题是LP问题的标准形式，则其对偶问题形式是怎样呢？记（P）问题为 s.t. =b （2.7） x0为了利用对称型（D）问题的结论，先将问题（2.7）等价地化为： s.t. b b x0再引入对偶向量（u,v），其中为对应于第一组不等式约束b的对偶变量，为对应于第二组不等式约束b的对偶变量，按对称型的结论，可写出其（D）问题为： s.t. c u,v0即 s.t. c u,v0令 为m维行向量，则以上模型又可写成： s.t. c （2.8） y无符号限制将问题（2.7）与问题（2.8）称为一对非对称型的对偶问题.要注意的是：（P）问题（2.7）中约束为等式，则其（D）问题（2.8）中对偶变量无符号限制.例2.2 写出（P）问题 s.t. 0 （ j = 1,2,3）的（D）问题.解：由式（2.8）知其（D）问题为 s.t. 3 1 2 无符号限制3、混合型对偶问题考虑更一般的LP问题: s.t. （2.9） 0，无符号限制其中为矩阵，为维列向量，为维行向量，为维列向量，i = 1,2,3；j = 1,2，且，.为利用非对称型（D）问题的结论，令，引入松弛变量 ，其中分别为 维列向量. 将问题（2.9）化为标准形式： s.t. 0再按式（2.8）写出它的（D）问题为 s.t. 0， 0即 s.t. = （2.10） 0，无符号限制，0表2-1原问题对偶问题目标函数max目标函数min约束条件m个m个00无符号限制变量变量n个00无符号限制n个约束条件目标函数的系数约束条件右端常数系数矩阵A约束条件右端常数目标函数的系数系数矩阵AT将问题（2.9）与问题（2.10）称为一对混合型对偶问题.从以上三种形式的对偶关系中，可以总结（P）问题与（D）问题相关数据之间的联系，即对偶规则见表2-1.显然，有了对偶规则表2-1，则上述任一形式的问题的对偶问题都可以直接利用表2-1得到.例2.3 写出（P）问题 s.t. 5 4 0，0，无符号限制的（D）问题.解：根据对偶规划表2-1，可直接写出上述（P）问题的（D）问题. s.t. 2 3 5 0，0，无符号限制2 对偶问题的基本性质这一节给出对偶问题的一些性质，为叙述方便，仅在对称形式下即对（P）问题：（D）问题： s.t. Ax b s.t.yA c x 0 y 0讨论.对其它形式的对偶问题也有类似结论，请读者给出并加以证明.一、对偶规划的若干问题定理2.1（对称性定理） 对偶问题的对偶是原问题.证明： 先将（D）问题化成原问题形式 s.t. 0 由定义2.1设为它的对偶变量，写出它的对偶问题. s.t. 0即 s.t. b 0这就是（P）问题. 证毕.根据对称性定理，在一对对偶问题中，可以把其中任何一个称为原问题，则另一个称为其对偶问题.定理2.2（弱对偶定理） 设和分别是（P）问题和（D）问题的可行解，则必有.证明： 因为是（P）问题的可行解，故必有 b，0 （2.11）又是（D）问题的可行解，于是有 c，0 （2.12）用左乘不等式（2.11）两边，得 用右乘不等式（2.12）两边，得 从而有 证毕.推论2.1 如果和分别是（P）问题和（D）问题的可行解，且=，则、分别是（P）问题和（D）问题的最优解.证明： 由定理2.2知，对于（P）问题的任意一个可行解x，必有 但=，故对（P）问题的所有可行，有 由定义知，为（P）问题的最优解.同理可证，是（D）问题的最优解. 证毕.推论2.2 在一对对偶问题中，如果其中一个问题可行，但目标函数无界，则为另一个问题不可行.证明： 用反证法.设（P）问题可行，但目标函数无界，而（D）问题可行，即存在可行解，则由定理2知对（P）问题的任一可行解x有 即 （P）问题的目标函数有上界，与条件矛盾. 证毕.注意推论2.2的逆命题不一定成立，当（P）问题（D）问题）无可行解时，其（D）问题（P）问题）或具有无界解或无可行解.推论2.3 如果一对对偶问题都有可行解，则它们都有最优解.证明： 设、分别是（P）问题与（D）问题的可行解，对（P）问题的任一可行解x，由定理2.2知，必有，即对于求极大值（P）问题，目标函数值有上界，故必有最优解，同理，对（D）问题的任一可行解y有，即对于求极小值的（D）问题，目标函数值有下界，故必有最优解. 证毕.定理2.3（对偶定理） 如果（P）问题（D）问题）有最优解，那么（D）问题（P）问题）也有最优解，且目标函数值相等.证明： 先证明当（P）问题有最优解时，（D）问题也有最优解.设 是（P）问题的最优解，它对应的基矩阵为B，引入松弛变量，将（P）问题化为标准形式 s.t. 0显然，该问题也有最优解 由第一章定理1.7（最优性判别定理）必有检验数 0令，则有0，即 0.这表明是（D）问题的可行解，对应的目标函数值为： 又因为是（P）问题的最优解，其目标函数的值为 所以有 .则由推论2.1知（D）问题有最优解，且两者的目标函数的最优值相等.同理可证，当（D）问题有最优解时，（P）问题也有最优解且目标函数相等. 证毕.推论2.4（单纯形乘子定理） 如果（P）问题有最优解，最优基为B，则就是（D）问题的一个最优解.证明： 由定理2.3的证明过程，已得到此推论的结论.推论2.5 对于对称形式的（P）问题，如果有最优解，则在其最优单纯形表中，松弛变量的检验数的负值即为（D）问题的一个最优解.证明： 当（P）问题取得最优解时，有已知 ，如果记 则 式 由推论2.4可知，是（D）问题的一个最优解. 证毕.在矩阵形式的最优单纯形表上更能清楚地得到推论2.5的结论.设松弛变量为初始可行基对应的基变量，B为最优基，表2-2表示（P）问题的初始单纯形表，表2-3表示（P）问题的最优单纯形表.表2-2 表2-3cobcoboBNIbI检验数oo检验数o在表2-3中，还可以看到在约束方程的系数矩阵中，松弛变量对应的mm子矩阵中，记录了最优基矩阵B的逆矩阵，它在灵敏度分析中是很有用的.综上所述，（P）问题与（D）问题的解之间只有以下三种可能的关系：（1）两个问题都有可行解，从而都有最优解，分别设为，则必有；（2）一个问题为无界解，另一个问题必无可行解；（3）两个问题都无可行解.定理2.4（互补松弛定理） 设和分别是（P）问题和（D）问题的可行解，则它们分别是（P）、（D）问题的最优解的充要条件是：；同时成立.证明： 必要性 设、分别是（P）问题和（D）问题的最优解.则 b，0； c， 0；，所以由 推出=，于是 ，充分性 由，得 =又、分别是（P）问题和（D）问题的可行解，所以、分别是（P）问题和（D）问题的最优解. 证毕.因为，0，b，由，有 ，i = 1,2, m由0，c，有 ，j = 1,2, n即一个规划的某个约束成立严格不等式（约束条件为松），对应的对偶规划中变量取0（变量是紧），当某个变量不为0时（变量是松），对应的对偶规划中约束成立等式（约束条件是紧）.二、对偶规划的求解对偶规划作为一个线性规划，自然可以用前面介绍的单纯形法求解. 但是，由本节关于对偶规划的若干定理的讨论，可以看到原问题及其对偶问题之间有着紧密的联系，那么，能否通过求解原问题找出对偶问题的解，或者相反，在此介绍两种求对偶最优解的方法.1、利用原问题的最优单纯形表求对偶最优解的方法由推论2.4已得到是（D）问题的一个最优解，又由推论2.5在对称形式的（P）问题，如果有最优解，则在其最优单纯形表中，松弛变量的检验数的负值即为（D）问题的一个最优解，见表2-3，所以，对对称形式的对偶问题，当用单纯形法求得（P）问题的最优解的同时，得到了（D）问题的最优解.例2.4 求如下LP问题 s.t. 100 100 0的对偶问题的最优解.解: 对偶问题为 s.t. 4 3 7 0 表2-4c43700bcBxBx1x2x3x4x53x2-3/4103/4-1/2257x35/401-1/41/225检验数-5/200-1/2-2-250对原问题引入松弛变量，将原问题化为标准形式，由单纯形法求解得最优单纯形表（表2-4）.则原问题的最优解为： 其相应的目标函数最优值 由推论2.5，在表2-4中可得，对偶问题的最优解为： 其相应的目标函数最优值 .如果（P）问题为： s.t. x0此时矩阵A中没有现成的单位矩阵I，但可以通过引进人工变量，使之出现单位矩阵，再用大M法或两阶段法求解（结果保留所有人工变量位置），那么，这时如何从最优单纯形表中，求得对偶规划的解？设 I为初始可行基，对应的基变量在目标函数中的系数向量为，B为最优基，参考 表2-3,在最优单纯形表中,对应的检验数为,因此.例2.5 （第一章例1.10）已知（P）问题 s.t. 11 3 0试求其（D）问题的最优解.解：该问题的（D）问题为 s.t. 3 -1 -1 0，0，无符号限制对（P）问题，在第一章例1.10中，引进松弛变量，人工变量，用大M法已解得（见表1.9），.在表1-9 的检验数行中，可以看到初始基变量对应的检验数为 ，而在原问题的目标函数中相应的系数分别为0,-M,-M，故（D）问题的最优解为： ； ； ，即对偶问题的最优解为： 其相应的目标函数最优值 .2、利用互补松弛定理求对偶最优解.通过例子来介绍此方法.例2.6 已知（P）问题 s.t. 2 3 5 2 3 0试求其（D）问题的最优解.解：该问题的（D）问题为 s.t. 4 3 0由于（P）问题只含两个决策变量，故可用图解法求解，得最优解为： 其相应的目标函数最优值 .将代入约束条件，知第2、3、4个约束条件成立严格不等式，由互补松弛定理，对偶规划最优解中相应的变量有 ，又因为不为0，在对偶规划中对应的约束条件为紧，因此，得到，解得，故（D）问题的最优解为： 其相应的目标函数最优值 .注意：从前面的讨论可知，原问题与对偶问题是对称的，即互为对偶问题. 求解一个有m个约束条件n个变量的LP问题，可以转化为求解一个有n个约束条件m个变量的对偶问题. 因此在求解一个LP问题时，往往需要先考虑一下，究竟是解它的原问题还是解它的对偶问题比较省事，一般来说，求解一个LP问题的计算量，是同这个问题所包含约束条件的个数有密切关系的，如果约束条件的个数愈多，则基可行解中基变量的个数也随之增多，相应地迭代变换的计算量也愈大，根据经验，单纯形法的迭代次数大约是约束条件个数的11.5倍，因此，当m n时，则用其对偶问题求解较好. 但当m=2时，对偶问题可用图解法求解，可简化求解过程.例2.7 求解LP问题 s.t. 2 0 0，0解： 对偶规划为 s.t. 2 4 -3 -1 0，0用图解法解之，得：，.将代入约束条件，第3、4个条件成立严格不等式，所以，又因为0，所以原规划第二个约束条件为等式约束，即： 此时，原规划最优解不唯一，由上述不等式组得： ， 所以，原规划有两个最优基可行解., 原规划的最优解为：，其中01，相应的目标函数最优值 .3 对偶问题的经济解释影子价格一、影子价格的概念考虑一对对称的对偶问题. （P） s.t. Ax b（D） s.t.yA c x 0 y 0从上节对偶问题的基本性质可知，当（P）问题求得最优解时，其（D）问题也得到最优解，且有 （2.13）代表第i种资源的拥有量；对偶变量的意义代表在资源最优利用条件下对单位第i种资源的估价.这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，称之为影子价格.资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数.由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变.不同企业，即使是相同的资源，其影子价格也不一定相同，就是同一个企业，在不同的生产周期，资源的影子价格也不完全一样.在（2.13）式中对z求的偏导数，得，这说明的值相当于在资源得到 表2-5 产品资源甲乙资源限制A1390B2180C1145单位产值54最优利用的生产条件下，每增加一个单位时目标函数z的增量，所以，影子价格是一种边际价格.例2.8 某工厂经理对该厂生产的两种产品甲、乙，用线性规划来确定最优的产量方案.产品的单位产值，对三种资源的单位消耗及资源的现有数量如表2-5.用单纯形法解这个LP问题，得初始及最优单纯形表（表2-6）.表2-6c54000b初始表013100900021110010018045检验数540000最优表05401000110021-1-5-12253510检验数000-1-3-215这说明最优生产方案为甲产品生产35件，乙产品生产10件，总产值达到最大为215.由上节讨论，在最优单纯形表中，不难得到对偶解，即影子价格：资源A的影子价格；资源B的影子价格；资源C的影子价格.资源A的影子价格为零，说明增加这种资源不会增加总的产值，如在表2-6的初始表中的90改为91，则最优单纯形表为表2-7，这说明资源A的增加不改变产品生产方案，也不增加总的产值.如果资源C增加一个单位从45改为46，最优单纯形表为表2-7（）.表2-7c54000b初始表00012-526001001101-1-123510检验数000-1-3-215最优表05401000110021-1-5-12203412检验数000-1-3-218这说明增加一个单位的资源C以后，最优生产方案为甲产品生产34件，乙产品生产12件，总产值由原来215件增加到218，增加了3个单位，即为该资源的影子价格格或边际价格.由上节，对偶问题的互补松弛定理中有时，；当时，有，这表明生产过程中，如果某种资源未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕.二、影子价格在经营管理中的应用影子价格在经营管理中的用处很多，可提供以下几个方面的信息.1、影子价格说明增加哪一种资源对增加经济效益最有利.如例2.8中的三种资源的影子价格为（0,1,3），说明首先应考虑增加资源C，因为相比之下它能给收益带来的增加最大.2、影子价格又是一种机会成本. 企业经营决策者可以把本企业资源的影子价格与当时的市场价格进行比较，当年i种资源的影子价格高于市场价格时，则企业可以买进该种资源；而当某种资源的影子价格低于市场价格时（特别是当影子价格为零时），则企业可以卖出该种资源，以获得较大的利润.3、企业在新产品投产之前，可利用影子价格，通过分析新产品使用资源的经济效果，以决定新产品是否应该投产.如在例2.8中，企业要生产一新产品，单件消耗三种资源的数量是（2,3,2）单位，则新产品的定价一定要大于，才能增加公司的收益，如果售价低于9的话，生产是不合算的.4、利用影子价格分析现有产品价格变动时资源紧缺情况的影响，如在例2.8中，产品的售价不是（5,4），而是（5,5），则从最优单纯形表中，可计算出影子价格 这说明如果产品乙的价格增加的话，资源C将变得更紧俏了.5、利用影子价格可以帮助分析工艺改变后对资源节约的收益. 如在例2.8中，工艺过程改进后，使资源C能节约2%，则带来的经济收益将是3452%=2.7.值得指出的是，以上的分析都是在最优基不变的条件下进行的，如果最优基有变化，则应结合5灵敏度分析的方法进行分析.正是由于影子价格在经济管理中对收益能提供大量的信息，所以对偶理论中的影子价格概念正日益受到管理人员的重视.影子价格虽然被定义为一种价格，但是还应对它有更为广义的理解，影子价格是针对约束条件而言的，并不是所有的约束条件都代表了资源的约束，如在例2.8中，还可以列入一个产量约束：两种产品的数量不超过市场上的需要量，这样的约束也有个影子价格，如果这个影子价格算出来比前面几种影子价格更大，则应理解为扩大销售量能比增加资源带来更大的经济效益.4 对偶单纯形法一、对偶单纯形法的基本思路对偶单纯形法是根据对偶原理和单纯形法的原理而设计出来求解线性规划问题的一种方法（而不能简单的将它理解为是求解对偶问题的方法），前面介绍的单纯形法可称为原始单纯形法.从理论上说原始单纯形法，可以解决一切线性规划问题，但正因为它适用范围广泛，必有不足之处，如它对于某些特殊问题，虽然也可解决，但计算量较大.例如线性规划问题 化为标准形式 s.t. Axb s.t. x0 0在约束方程中出现了一个负单位矩阵，若将剩余变量取作初始基变量，则初始基，初始解0不满足可行性.因此不能将取作初始基，为了求得初始基本可行解，在第一章6中已讲述，需在约束方程左边增加一组人工变量，通过大M法或两阶段法进行计算，这就显得很不方便，且（）也没能利用上. 考察一般的标准形式的线性规划问题及其对偶问题： （P） s.t. Ax=b （D） s.t. c x0 y无符号限制设B为原问题（P）的一个基，不妨设 则 （2.14）为原问题（P）的一个基本解；且当 0 （2.15）时，则为一个基可行解，B为可行基；进一步若检验数满足 0 （2.16）则为原问题（P）的一个最优解，这时B称为最优基.以上概念都是对原问题（P）而言的，因此，我们更将条件（2.15）称为原始可行性条件；条件（2.16）称为原始最优性条件.原始单纯形法的基本思路是：从满足原始可行性条件（2.15）的一个基可行解出发，经过换基运算迭代到另一个基可行解，即总是保持解的可行性不变（满足条件（2.15），变化的只是检验数向量，它从不满足0，逐步迭代到0成立，一旦达到0，也就得到了原问题的最优解.再从对偶的观点来解释这个问题，令代入式（2.16）得c （2.17）即y是对偶问题（D）的一个可行解.条件（2.17）称为对偶可行性条件，即原始最优性条件（2.16）与对偶可行性条件（2.17）是等价的，因此，如果一个原始可行基B是原问题（P）的最优基，则就是对偶问题（D）的一个可行解，此时对应的目标函数值，等于原问题（P）的目标函数值，可知也是对偶问题（D）的最优解.定义2.2 若原问题（P）的一个基本解对应的检验数向量满足条件（2.16），即 0则称x为（P）的一个正则解.于是可知，原问题（P）的正则解x与对偶问题（D）的可行解y是一一对应的，它们由同一个基B所决定，我们称这一基为正则基.因此，我们可以设想另一条求解思路，即在迭代过程中，始终保持对偶问题解的可行性，而原问题的解由不可行逐渐向可行性转化，一旦原问题的解也满足了可行性条件，也就达到了最优解.也即在保持正则解的正则性不变条件下，在迭代过程中，使原问题解的不可行性逐步消失，一旦迭代到可行解时，即达到了最优解.这正是对偶单纯形法的思路，这个方法并不需要把原问题化为对偶问题，利用原问题与对偶问题的数据相同（只是所处位置不同）这一特点，直接在反映原问题的单纯形表上进行运算.二、对偶单纯形法的计算步骤求解如下标准形式线性规划问题： s.t. Ax = b x0对偶单纯形法的计算步骤：（1）找一个正则基B和初始正则解；将原问题化为关于基B（不妨设）的典式，列初始对偶单纯形表，见表2-8.表2-8c100010001检验数000（2）若0，则停止计算，当前的正则解，即为原问题的最优解；否则转下一步.（3）确定离（换出）基变量：令 ，（显然）则取相应的变量，为离（换出）基变量.（4）若0，（j = 1,2, n），则停止计算，原问题无可行解.否则转下一步.（5）确定进（换入）基变量；若，则取相应的变量为进（换入）基变量.（6）以为主元进行换基运算，得到新的正则解，转（2）.例2.9 用对偶单纯形法求解 s.t. 540解：先将问题化为 s.t. 0 （j = 15）其中为松弛变量，取初始正则基则问题已化为关于基B的典式，初始正则解为： 及目标函数值.列对偶单纯形表并进行迭代见表2-9，由表2-9（）可知，因为 故应取为换出基变量，又因为 故应取为换入基变量，以为主元作换基运算，得表2-9（），又由该表可知.因为 故应取为换出基变量，又因为 故应取为换入基变量，以为主元作换基运算，得表2-9()，至此，基变量的取值已全部非负，检验已全部非正，故已求得最优解表2-9序号c-15-5-1100b0-3-2*-210-50-5-1-201-4检验数-15-5-11000-53/211-1/205/20-7/2*0-1-1/21-3/2检验数-15/20-6-5/2025/2-5014/7-5/73/713/7-15102/71/7-2/73/7检验数00-27/7-10/7-15/7110/7及相应的目标函数最优值，原问题的目标函数最优值.由表2-9()还可以看出，其对偶问题的最优解为及目标函数最优值.例2.10 用对偶单纯形法求解表2-10序号c-2-4-6000b0-2*1-1100-1001220101200-21001-4检验数-2-4-60000-21-1/21/2-1/2005005/23/21/210700-2*1001-4检验数0-5-5-100-10-2101/4-1/20-1/4600011/41/215/42-401-1/200-1/22检验数00-15/2-10-5/2-20 s.t. 10 12 4 0，（j = 1,2,3）.解：先将问题化为: s.t. 0，j = 1,2,6其中为松弛变量，取初始正则基 则问题已代为关于基B的典式，初始正则解为：及目标函数值.用对偶单纯形法求解、迭代过程如表2-10.由表2-10（）可知，基变量的取值已全部非负，检验数已全部非正，故已求得最优解:及原问题目标函数最优值.从以上求解过程可以看到，对偶单纯形法有以下优点：（1）初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人工变量，因此，可以简化计算；表