第四章线性规划的对偶问题

第四章 线性规划的对偶问题4.1 对称的对偶规划在线性规划早期发展中 ,对偶问题是一项重要的发现。早在 1928著名数学家 John.Von.Neumann在研究对策理论时就已经有原始和对偶的思想。对偶理论有着重要的应用。首先是在原始和对偶两个线性规划中求解任一规划时，会自动地给出另一个规划的最优解。当对偶问题比原问题有较少分量时，求解对偶问题比求解原始问题方便得多。对偶理论另一个应用是 Lemke， 1954提出的对偶单纯形法。对偶理论对影子价值的分析在经济理论上有着重要作用。一 对偶问题的提出 :例 :某厂生产 A.B.C三种畅销产品 ,每台产品需四种资源 ,具体数据表：问怎样安排生产 ,效益最大？ 设决策变量 得出模型 :现在工厂考虑不进行生产而把全部可利用的资源都让给其它企业单位 ,但又希望给这些资源订一个合理价格 ,既使别的单位愿意买 ,又使工厂能得到生产这些产品时可以得到的最大效益 . 这就需建立另一个线性规划模型 ,设 代表销售这四种资源的价格，买方希望总售价尽可能低 ,即：为了使工厂效益不减少 ,就要求订 时 ,使这个效益额不低于原来生产一台产品 A可以得到的效益 ,因此满足约束 :对 B,C产品可列出类似约束 .原来生产产品 A每台需用的资源按现在的单价计算 ,每台收益为 :易见 ,后一个问题的数据完全由另一问题数据确定 .对每一个线性规划问题都伴随有另一个线性规划问题 ,即： 都伴随一个对偶规划 (LD)。定义 1:对应着每一个 (LP),都存在着线性规划问题 (LD)其中 是 m维行向量 ,称 (LP)为原始线性规划，称 (LD)为 (LP)的对 偶线性规划 。因此得到的线性规划问题模型如下 : 下面进一步探讨 (LP)与 (LD)之间的关系： 其对偶问题 :(LD)(LP)用下表表示二者之间关系 ,更为清楚 :原始约束max对偶问题minw对偶线性规划问题一定要有一对线性规划问题，没有一个 “对偶 ”的线性规划问题，也就无所谓 “原始线性规划问题 ”如果没有原始线性规划问题，也就无所谓对偶线性规划问题了。线性规划的对偶关系具有 “对合 ”性质 ,什么是对合性质呢 ?可见，（ LP） 与（ LP） 是同一类型的问题，依照定义 1，又可写出（ LP） 的对偶线性规划。记为（ LD） （ LD） （ LD） 又可等价地写成：既（ LD） 就是前面的（ LP）这表明，对于一个给定的（ LP） 可以根据对偶规则写出（ LD）； 而对于新问题（ LD）， 又可根据对偶规则写出其对偶。而此对偶又刚好回到原问题本身。即（ LP） 的对偶是（ LD） ，（ LD） 的对偶是（ LP）。这就是线性规划对偶关系的 “对合 ”性质。这样我们可以把一个相互对偶的线性规则中任何一个称为原问题，而把另一个称为对偶问题，称它们互为对偶。下面我们举例说明怎样由一个规则写出其对偶问题 。例：写出： min s.t. 的对偶规划。解：因目标函数最小化，故先把约束条件都写成 “ ”形式：由于这是个（ LD） 问题。故其对偶是（ LP） 问题。对偶函数目标系数由给出的（ LD） 约束右端列向量（ -7， 14， 3)可得，对偶的约束方程右端常数，向量由（ LD） 的目标函数 系数向量（ 5， -6， 7， 1）可得，从而写出（ LP） 问题：max (LP) (s.t.)所以把它们称为一对对称的对偶规划。下面来讨论它们的关系。二 （ 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。推论 ： 若（ LP） 有无界解，则（ LD） 无可行解。若（ LD） 有无界解，则（ LP） 无可行解。证： 只证前面，后面一样，反证法。若 （ LP） 有无界解，而（ LD） 有可行解 u0，而根据定理一，对（ LP） 的任何可行解 x， c xu0 b这与（ LP） 目标函数无上界矛盾。注 ： 这个推论的逆不一定成立。即一对对偶问题中有一个无可行解，不能判定另一个有无 界解。例： （ LP）（ LD）上面（ LP） 无可行解，而（ LD） 并没有无界解，而是无可行解。定理 2：证明：证明 ： 推论 2定理 3证明：这样（ LP） 就化成了等价的（ *）问题。由于假定（ LP） 有最优解，则（ *）亦有最优解。亦即 （ *） 其中)=1 pp Bj ,.0对应的最优基为jB -1(c ，组成的 m维 向量记为，在其中取出基变量对, cc,cc ,.00001应的分量。满足个jjsbB有定理 4证明：证毕由此可得如下松紧关系：对偶松紧关系又称为互补松弛条件 。下面通过一个例子说明对偶松弛关系：例 （ LP）引进松弛变量 ，（ LP） 化为：用单纯形法解此问题的最优单纯形表： x1 x2 x3 y1 y2 基变量 CB XB 1 1 1 0 0 X2 1 2/3 2 1 0 -1/3 2/3 X3 1 2/3 0 0 1 2/3 -1/3 F*=4/3 1 0 0 1/3 1/3 得（ LP） 的最优解 （ LP） 的对偶：（ LD）又可见，用单纯形法迭代的到（ LP)最优解时，对偶 (LD)的 最优解可以直接从（ LD)的最优单纯形到表上得到。在问题的松弛变量（ y1， y2)的检验数就是对偶 (LD)的最优解。这个结果对一般情形也成立。下面予以证明。用单纯形求解。得到一个判别数全非负的最优基本解。对应松弛变量 yi的判别数 又 yi在 目标函数中 系 数 pn+i为第 i分量为 1的 m维单位列向量。 (i=1m)且 一对相互对偶的线性规划（ LP）（ LD） 之间解的可能构形有哪些？这可用对偶定理来回答，因为（ LP）（ LD） 都单独分别有三种可能：综合以上对偶定理知：（ LP）（ LD） 之间只可能有下面三种情形：（ 1） 两者都有最优解。（ 2） 两者都没有可行解。（ 3） 一个问题有无界解，另一个问题没有可行解 。其他情形都不可能出现了，因为，一个问题有最优解，另一个问题有无界解，或一个问题有最优解，另一个问题无可行解，将与定理 3矛盾。如果两个问题都有无界解，将与推论 1矛盾。（ LP) (LD) .有最优解 .有无界解 .无可行解.4.2 非对称及混合型对偶规划一 （ SLP） 的对偶规划 ：在单纯形法中，我们总是先将（ LP） 问题化为（ SLP） 求解，因此，有必要研究（ SLP） 的对偶规划问题。先将（ SLP）： 改写成（ LP）再根据（ LP） 的对偶定义写出其对偶规划：(LD)这就是 (SLP)的对偶线性规划，这一线性规划问题还可进一步简化