第十四章 线性划的对偶问题.doc

第十四章 线性规划的对偶问题 14.1 对称的对偶规划 在线性规划早期发展中,对问题是一项重要的发现.早在1928著名数学家John.Von.Neumann在研究对策理论时就已经有原始和对偶的思想. 对偶理论有着重要的应用.首先是在原始,对偶两个线性规划中求解任一规划时,含自动地给出另一个规划的最优解.当对偶问题比原问题有较少分量时,求解对偶问题比求解原始问题方便的多. 对偶理论另一个应用是Lemke,1954提出的对偶域形法。另外,对偶理论还应用于通用的运转问题模型上，对偶理论对影子价值的分析在经济理论上有着重要作用. 14.1.1对偶问题的提出: 例14.1.1:某厂生产A.B.C三种畅销产品,每台产品需四种资源,具体数据表 表14.1.1 资源 产品 甲 乙 丙 丁 每台收益 A 3 2 1 1 2000 B 4 1 3 2 4000 C 2 2 3 4 3000 资源服务 600 400 300 200 问怎样安排生产,效益最大! 设决策变量得出模型: 现在工厂考虑不进行生产而把全部可利用的资源都让给其它企业单位,但又希望给这些资源订一个合理价格,既使别的单位愿意买,又使工厂能得到生产这些产品时可以得到的最大效益. 这就需建立另一个线性规划模型,设代表销售这四种资源总售价尽可能低,即 原来生产产品A每台需用的资源按现在的单价计算,每台收益为: 为了使工厂效益不减少,就要求订时,使这个效益额不低于原来生产一台产品A可以得到的效益,因此满足约束: 对B,C产品可列出类似约束. 因此得到的线性规划问题模型如下: 易见,后一个问题的数据完全由另一问题数据确定.对每一个线性规划问题都伴随有另一个线性规划问题,一般地。对每个(LP) 都伴随一个对偶规划(LP)。 定义14.1.1个(LP),都存在着线性规划问题(LD) 其中是m维向量,称(LP)为原始线性规划.称(LD)为(LP)的对偶线性规划. 下面进一步探讨(LP)与(LD)之间的关系： (LP) 其对偶问题: (LD) 用下表示二者之间关系,更为清楚: 表14.1.2 对偶线性规划问题一定要有一对线性规划问题，没有一个“对偶”的线性规划问题，也就无所谓“原始线性规划问题”如果没有原始线性规划问题，也就无所谓对偶线性规划问题了. 线性规划的对偶关系具有“对合”性质,什么是对合性质呢? 因而问题可写成（10） 可见，（LP） 与（LP）是同一类型的问题，依照定义1，又可写出（LP）的对角线形状态。记为（LP） （LP） （LP）’ 又可等价地写成： 既（LD）’就是前面的（LP），而（LD）’等价于前面的（LD）这表面，对于一个给定的（LP）可以根据对偶规则写出（LD）；而对于新问题（LD），又可根据对偶规则写出其对偶。而此对偶又刚好回到原问题本身。即（LP）的对偶是（LD） ，（LD）的对偶是（LP）。 这就是线形规则对偶关系的“对合”性质。这样我们可以把一个相互对偶的线性规则中任何一个称为原问题，而把另一个称为对偶问题，称它们互为对偶。 下面我们举例说明怎样由一个规则写出其对偶问题。 例14.1.2：写出：min s.t 的对偶规划 解：因目标函数最小化故先把约束条件都写成“ ”形式： 由于这是个（LD）问题。故其对偶是（LP）问题。目标函数极大化，约束不等式，用“”号，因（LD）中三个“”不等式，故引入三个变量分别与之对应。因原角中有四个变量，因此对偶问题中有四个约束不等式。 对偶函数目标系数由给出的（LD）约束右端列向量（-7，14，3)转置而成，对偶的约束方程右端常数，向量由（LD）的目标函数系数向量（5，-6，7，1）转置而得，从而写出（LP）问题： Max （LP） （s.t） 由于（LP） 与（LD）形式上是等价的。所以把它们称为一对对称的对偶规划。 下面来补充它们的关系。 14.1.2（LP）、（LD）的对偶定理 定理14.1.1 对于（LP）的任意可行解x ,及（LD）的任意可行解u有cx ≤ub 证：因 x 、u满足： （14.1.1） （14.1.2） 用u左乘（1），x右乘（2）的：c x≤u Ax≤u b 故c x≤u b . 定理1 给出了（LP）（LD）这对互为对偶的线性规问题目标函数的一个界限。若（LP）有可行解x，则（LD）的目标值ub就有了下界cx；反之，若（LD）有可行解u，则（LP）的目标值cx就有了上界ub。 推论：若（LP）有无界