《[数学]第四章 线性规划的对偶问题》由会员分享，可在线阅读，更多相关《[数学]第四章 线性规划的对偶问题（99页珍藏版）》请在金锄头文库上搜索。
1、第四章 线性规划的对偶问题4.1 对称的对偶规划在线性规划早期发展中,对偶问题是一项重要的发现。早在1928著名数学家John.Von.Neumann在研究对策理论时就已经有原始和对偶的思想。对偶理论有着重要的应用。首先是在原始和对偶两个线性规划中求解任一规划时，会自动地给出另一个规划的最优解。当对偶问题比原问题有较少分量时，求解对偶问题比求解原始问题方便得多。对偶理论另一个应用是Lemke，1954提出的对偶单纯形法。对偶理论对影子价值的分析在经济理论上有着重要作用。,一 对偶问题的提出:例:某厂生产A.B.C三种畅销产品,每台产品需四种资源,具体数据表：,问怎样安排生产,效益最大？,设决策
2、变量 得出模型:,现在工厂考虑不进行生产而把全部可利用的资源都让给其它企业单位,但又希望给这些资源订一个合理价格,既使别的单位愿意买,又使工厂能得到生产这些产品时可以得到的最大效益.,这就需建立另一个线性规划模型,设 代表销售这四种资 源的价格，买方希望总售价尽可能低,即：,原来生产产品A每台需用的资源按现在的单价计算,每台收益为:,易见,后一个问题的数据完全由另一问题数据确定.对每一个线性规划问题都伴随有另一个线性规划问题,即：,都伴随一个对偶规划(LD)。,定义1:对应着每一个(LP),都存在着线性规划问题(LD),其中 是m维行向量,称(LP)为原始线性规划，称(LD)为(LP)的对偶线
3、性规划。,因此得到的线性规划问题模型如下:,下面进一步探讨(LP)与(LD)之间的关系：,其对偶问题:(LD),(LP),用下表表示二者之间关系,更为清楚:,对偶线性规划问题一定要有一对线性规划问题，没有一个“对偶”的线性规划问题，也就无所谓“原始线性规划问题”如果没有原始线性规划问题，也就无所谓对偶线性规划问题了。,线性规划的对偶关系具有“对合”性质,什么是对合性质呢?,可见，（LP）与（LP）是同一类型的问题，依照定义1，又可写出（LP）的对偶线性规划。记为（LD）（LD）,（LD） 又可等价地写成：,既（LD）就是前面的（LP） 这表明，对于一个给定的（LP）可以根据对偶规则写出（LD）
4、；而对于新问题（LD），又可根据对偶规则写出其对偶。而此对偶又刚好回到原问题本身。即（LP）的对偶是（LD） ，（LD）的对偶是（LP）。,这就是线性规划对偶关系的“对合”性质。 这样我们可以把一个相互对偶的线性规则中任何一个称为原问题，而把另一个称为对偶问题，称它们互为对偶。 下面我们举例说明怎样由一个规则写出其对偶问题。,解：因目标函数最小化，故先把约束条件都写成“ ”形式：,由于这是个（LD）问题。故其对偶是（LP）问题。,对偶函数目标系数由给出的（LD）约束右端列向量（-7，14，3) 可得，对偶的约束方程右端常数，向量由（LD）的目标函数 系数向量（5，-6，7，1）可得，从而写出（
5、LP）问题：,所以把它们称为一对对称的对偶规划。 下面来讨论它们的关系。,二 （LP）、（LD）的对偶定理定理1 对于（LP）的任意可行解x 及（LD）的任意可行解 u 有 c x u b 。证： 因 x 、u满足： A x b , x0 （1） u Ac u0 （2）用u左乘（1），x右乘（2）的：c xu Axu b 故c xu b 。,由于（LP） 与（LD） 形式上是等价的,定理1 给出了（LP）（LD）这对互为对偶的线性规问题目标函数的一个界限。若（LP）有可行解x，则（LD）的目标值u b就有了下界c x；反之，若（LD）有可行解u，则（LP）的目标值c x就有了上界u b。推论：
6、 若（LP）有无界解，则（LD）无可行解。若（LD）有无界解，则（LP）无可行解。证： 只证前面，后面一样，反证法。若（LP）有无界解，而（LD）有可行解u0，而根据定理一，对（LP）的任何可行解x，c xu0 b这与（LP）目标函数无上界矛盾。注： 这个推论的逆不一定成立。即一对对偶问题中有一个无可行解，不能判定另一个有无 界解。,例： （LP）,（LD）,上面（LP）无可行解，而（LD）并没有无界解，而是无可行解。,定理2：,证明：,证明：,推论2,这样（LP）就化成了等价的（*）问题。 由于假定（LP）有最优解，则（*）亦有最优解。,有,定理4,证明：,证毕,由此可得如下松紧关系：,对偶
7、松紧关系又称为互补松弛条件。 下面通过一个例子说明对偶松弛关系：,例,（LP）,引进松弛变量 ，（LP）化为：,得（LP）的最优解,又,可见，用单纯形法迭代的到（LP)最优解时，对偶(LD)的 最优解 可以直接从（LD)的最优单纯形到表上得到。在问题的松弛变量 （y1，y2)的检验数就是对偶(LD)的最优解。这个结果对一般情形也成立。下面予以证明。,用单纯形求解。得到一个判别数全非负的最优基本解。对应松弛变量yi的判别数 又 yi在目标函数中系数 pn+i为第i分量为1的m维单位列向量。(i=1m)且,一对相互对偶的线性规划（LP）（LD）之间解的可能构形有 哪些？这可用对偶定理来回答，因为（
8、LP）（LD）都单独分 别有三种可能：,综合以上对偶定理知：（LP）（LD）之间只可能有下面三种情形：（1） 两者都有最优解。（2） 两者都没有可行解。（3） 一个问题有无界解，另一个问题没有可行解。其他情形都不可能出现了，因为，一个问题有最优解，另一个问题有无界解，或一个问题有最优解，另一个问题无可行解，将与定理3矛盾。如果两个问题都有无界解，将与推论1矛盾。,4.2 非对称及混合型对偶规划,一 （SLP）的对偶规划：,在单纯形法中，我们总是先将（LP）问题化为（SLP）求解，因此，有必要研究（SLP）的对偶规划问题。,先将（SLP）：,改写成（LP）,再根据（LP）的对偶定义写出其对偶规划
9、：,(LD),这就是(SLP)的对偶线性规划，这一线性规划问题还可进 一步简化。引进m维行向量u ：,那么u就不一定有非负约束了。于是将上面（LD)写成：,（SLD),u无限制,(LP)（亦即(SLP) 的对偶是(LD)亦即(SLD) 。而 (LP)与(LD)是对称对偶规划，具有对合性。即(LD)也就是(SLD) 的对偶是(LP)(亦即(SLP)）。故知: (SLP)与(SLD)这对对偶 规划也具有对合性质的。,二 (SLP)、(SLD)的对偶定理： 下面我们考察前面已证明的关于(LP) (LD)的一些定理，考 虑是否对(SLP) (SLD)也成立。 定理1 对(SLP)的任意可行解x，(SL
10、D)的任意可行解u 。有：,证明：,推论1：若(SLP)有无界解，则(SLD)无可行解；若(SLD) 有无界解，则(SLP)无可行解。其逆不成立。,定理3：若(SLP),(SLD)中一个有最优解，则另一个也有 最优解，并且两者的目标函数值相等。,推论2：若x*，u*分别是(SLP),(SLD)的可行解，且cx*=u*b。 则x*,u*分别是(SLP),(SLD)的最优解。 （这些结论的证明与(LP),(LD)类似结论证明一样）,定理2：对偶(SLP),(SLD)有最优解 两者同时有可行解。,根据第一节的定理3知，(LP)即(SLP)有最优解。 故得证。,并且目标值 根据上面的推论2即可知： 因
11、此我们证明了若(SLP)有最优解，则(SLD)必有最优解。 反之，若(SLD)有最优解u*,则,是(SLD)的最优解。,我们由上面定理证明过程可见：若B*是(SLP)的最优基，那 么单纯乘子 就是(SLD)的最优解。因此我们定义： 定义2：对于(SLP)的一个基B，若单纯到乘子 为对偶(SLD)的可行解，则称B为对偶可行基。若 为对偶(SLD)的最优解，则称B为对偶最优基。 上面定理3的证明表明：(SLP)的最优基B*必是对偶最优 基。这个结论在后面的对偶单纯形法迭代中将是十分重要。,定理4：(SLP),(SLD)的可行解x*，u*分别是最优解,我们下面再细看一下这里的松弛条件：,从而得出如下
12、的松紧关系： （1）若(SLP)有最优解x*，使得对指标j满足x*j0，则称j对 （SLD)是松的。对(SLD)的 一切最优解u*就必有u*pj=cj 称j对(SLD)是紧的。 （2）若(SLD)有最优解u*,使前对指标j满足u*pjcj.则称j对 (SLD)是松的。对(SLP)的一切最优解x*就必有xj*=0，称j对 (SLP) 是紧的。从上述对偶定理知：(SLP)，(SLD)这一对对偶规划的解之间也有下面三种情形： （1） 两者都有最优解。 （2） 两者都没有可行解。 （3） 其中一个有无界解，而另一个无可行解。除此之外，不能再有其他的形式了。其理由与4.1一样。,上面我们已经讨论过了对称
13、及非对称型对偶规划。但实际问 题中会出现两种情形共存的问题，即所谓混合型的对称规划问题。定义:对于一个线形规划问题,若它的约束包括两个部分,一部分的约束是方程式 ，另一部分约束是不等式 (或 ) ,其变量也分两类, 其一类有非负限制,另一类没有限制，称这种类型的问题为混合型问题。考虑混合型问题：,(I),三 混合型对偶线形规划,.,根据上面求混合型对偶规划过程，我们总结出混合型对偶 的特点如下： （对偶表）：,例：写出下面线性规划的对偶规划：,（1）,（2）,注意：（1）写出的对偶问题，其系数矩阵必须是原问题的系数矩阵的转置。（2）写出对偶的前一步，问题统一化形式是必须的，否则容易出错。,例2
14、 用对偶定理证明，下面两个问题不能同 时成立： （1）,(2),证明：构造一对对偶线性规划问题：,(LD),（LP),（LP),故（1）成立时，（2）不可能也成立。 反之，若（2）成立时，同样不可能有（1）成立。,若 有解。即(SLP)有可行解。而对此(SLP),其 任意可行解也是最优解。根据对偶定理3，知(SLD)也有最 优解u， 反之，若 且对满足 的任意u，有 表明（SLD)有可行解，且目标值有下界。因而此(SLD) 有最优解。根据对偶定理3，即可知：(SLP)也有最优解x， 满足：,例5：利用对偶定理证明Farkas引理：有解 有解，且对满足 的任意 u必有 。其中A是 矩阵，b是m维
15、列向量。 证明：构造一对对偶规划向量如下：,（LP),(SLP),(LD),SLD),从而,反之，若存在u，使c表成（*）式。则（LP)有可行解。即 （SLP)有可行解。又已设(LD)有可行解。即(SLP)有可行解 根据对偶定理2 。即知：(SLD),(SLP) 均有最优解。从而 （LD)有最优解。 设上面A1Am是A的行向量。,我们将原来的一对（LP),(LD)等价的化为如上所示的一对 (SLP),(SLD)。这样(LD)有最优解等价与(SLD)有最优解。 有根据对偶定理3（SLD)有最优解等价于（SLP)有最优解。 而（SLP)有最优解等价与(LP)有最优解。 因此，若（LD)有最优解等价于(LP)有最优解u。从而,
