线性规划的对偶理论第一部分

一、对偶问题的提出1、

对偶思想举例：某工厂拥有一定生产原材料时，该工厂考虑是自己进行产品生产所赚的利润大还是将其原材料直接出售给其它工厂时所以赚取的利润大的问题。

第二章

线性规划的对偶理论线性规划的对偶理论部分共23页，您现在浏览的是第1页!

2、

换个角度审视生产计划问题例：（章例2）要求制定一个生产计划方案，在劳动力和原材料可能供应的范围内，使得产品的总利润最大。线性规划的对偶理论部分共23页，您现在浏览的是第2页!

它的对偶问题就是一个价格系统，使在平衡了劳动力和原材料的直接成本后，所确定的价格系统最具有竞争力：（用于生产第i种产品的资源转让收益不小于生产该种产品时获得的利润）

对偶变量的经济意义可以解释为对工时及原材料的单位定价；线性规划的对偶理论部分共23页，您现在浏览的是第3页!

若工厂自己不生产产品A、B和C，将现有的工时及原材料转而接受外来加工时，那么上述的价格系统能保证不亏本又最富有竞争力（包工及原材料的总价格最低）

当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值是相等的：

Zmax=Wmin线性规划的对偶理论部分共23页，您现在浏览的是第4页!则定义其对偶问题为这两个式子之间的变换关系称为“对称形式的对偶关系”。

线性规划的对偶理论部分共23页，您现在浏览的是第5页!（2）对称形式的对偶关系的矩阵描述（D）（L）

（3）怎样从原始问题写出其对偶问题？

按照定义；记忆法则：“上、下”交换，“左、右”换位，不等式变号，“极大”变“极小”线性规划的对偶理论部分共23页，您现在浏览的是第6页!（1）原问题对偶问题（特点：对偶变量符号不限，系数阵转置）(特点：等式约束)线性规划的对偶理论部分共23页，您现在浏览的是第7页!

原问题（或对偶问题）

对偶问题（或原问题）

目标函数MaxZ目标函数MinW变量数：n个变量≥0变量≤0变量无约束

约束条件数：n个约束条件≥约束条件≤

约束条件=

约束条件：m个约束条件≤约束条件≥约束条件=

变量数：m个变量≥0变量≤0无约束线性规划的对偶理论部分共23页，您现在浏览的是第8页!下面的答案哪一个是正确的？为什么？

（原问题是极小化问题，因此应从原始对偶表的右边往左边查！）√

×

线性规划的对偶理论部分共23页，您现在浏览的是第9页!性质1

弱对偶性——如果是原问题的可行解，其对偶问题的可行解，则恒有：（L）

和（D）

均有可行解，分别为和，则C≤b。证明思路：由（L）

左乘，得由（D）

右乘，得线性规划的对偶理论部分共23页，您现在浏览的是第10页!性质2

最优性

若、分别为对称形式对偶线性规划的可行解，且两者目标函数的相应值相等，即则，分别为原始问题和对偶问题的最优解。线性规划的对偶理论部分共23页，您现在浏览的是第11页!性质4

强对偶性(或称对偶定理)

如果原问题有最优解，则其对偶问题也一定具有最优解，且有线性规划的对偶理论部分共23页，您现在浏览的是第12页!性质6

线性规划的原问题及其对偶问题之间存在一对互补的基解，其中原问题的松驰变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基解变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有：线性规划的对偶理论部分共23页，您现在浏览的是第13页!二、原问题和对偶问题的关系1、对称形式的对偶关系（1）定义：若原问题是

线性规划的对偶理论部分共23页，您现在浏览的是第14页!原问题与对偶问题的对比：若原问题对偶问题线性规划的对偶理论部分共23页，您现在浏览的是第15页!例

写出下面线性规划的对偶问题：

2、非对称形式的对偶关系：线性规划的对偶理论部分共23页，您现在浏览的是第16页!（2）怎样写出非对称形式的对偶问题？把一个等式约束写成两个不等式约束，再根据对称形式的对偶关系定义写出；按照原始-对偶表直接写出；（3）原始-对偶表线性规划的对偶理论部分共23页，您现在浏览的是第17页!课堂练习：写出下面线性规划的对偶规划：线性规划的对偶理论部分共23页，您现在浏览的是第18页!三、对偶定理对偶定理是揭示原始问题的解与对偶问题的解之间重要关系的

一系列性质。对称性——对偶问题的对偶是原问题。线性规划的对偶理论部分共23页，您现在浏览的是第19页!

•关于“界”的结果；•极小化问题有下界——推论1

极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。•极大化问题有上界——推论2

极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。线性规划的对偶理论部分共23页，您现在浏览的是第20页!性质3

无界性

如果原问题（对偶问题）具有无界解，则对偶问题（原问题）无可行解。

注意：这个性质逆不成立。因为当原问题（对偶问题）无可行解时，其对偶问题（原问题）或无可行解或具有无界解。线性规划的对偶理论部分共23页，您现在浏览的是第21页!性质5

互补松弛性