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

《第二章 线性规划的对偶理论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章线性规划的对偶理论随着线性规划应用的逐步深入，人们发现线性规划有一个有趣的特性，就是每一个线性规划问题都存在另一个与之配对、两者有密切联系的线性规划问题.称其中一个为原问题，则另一个被称为对偶问题，这个特性称为线性规划的对偶性，这不仅仅是数学上具有的理论问题，由对偶问题引伸出来的对偶解有着重要的经济意义，也是经济学中重要的概念与工具之一.对偶理论充分显示出线性规划理论逻辑上的严谨性与结构上的对称性，它是线性规划理论的重要成果.§1对偶问题的提出一、对偶问题的实例在第一章的例1.1中，讨论了某工厂资源的合理利用问题，建立了LP问题模型：s.t.≤65≤40≤75（2.1）≥0已知

2、最优解为：.现从另一个角度考虑这个问题.假定该厂的决策者考虑自己不生产甲、乙两种产品，而把原拟用于生产这两种产品的资源A,B,C全部出售给外单位，则应如何确定这三种资源的价格.显然，该厂的决策者要考虑两个原则：第一，每种资源所收回的费用应不低于自己生产时可获得的利润；第二，定价不能太高，要对方容易接受.设分别表示三种资源出售的价格，则由第一个原则，应有如下约束条件：≥1500≥2500≥0而把原拟用于生产甲、乙产品的三种资源全部售出，总收入为：当然，对厂方而言，w越大越好，但根据第二个原则，在保证上述条件下，应考虑使总收入即对方的总支出尽可能少才比较合理，因为只有这样，厂方不会吃亏，

3、对方也容易接受.于是，该问题的数学模型归结为：s.t.≥1500≥2500（2.2）≥0这也是一个LP问题，用单纯形法解之得最优解为：及相应的目标函数最优值=70000.如果称（2.1）给出的LP问题为原问题，则称（2.2）式为（2.1）式的对偶问题.32二、对偶问题的形式以上从一个资源利用问题，引出了对资源的估价问题，得到了对偶规划.原问题与其对偶问题之间通常有三种不同的关系形式，以下将原问题记作（P）问题，对偶问题记作（D）问题.1、对称型对偶问题定义2.1设原LP问题为s.t.≤≤（2.3）………………≤≥0（）则称下列LP问题s.t.≤≤（2.4）………………≤≥0（）为其对

4、偶问题.其中（）称为对偶变量，并称（2.3），（2.4）为一对对称型对偶问题.如果用矩阵形式来表示模型（2.3），（2.4），则可更清楚地看出两者之间的对称性.（P）s.t.≤b（2.5）x≥0（D）s.t.≤c（2.6）y≥0其中是一行向量.即（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）的（

5、D）问题.32解：首先将问题化为式（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）x≥0为了利用对称型（D）问题的结论，先将问题（2.7）等价地化为：s.t.≤b≤－bx≥0再引入对偶向量（u,v），其中为对应于第一组不等式约束≤b的对偶变量，为对应于第二组不等式约束≤－b的对偶变量，按对称型的结论，可写出其（D）问题为：s.t.≥cu,v≥0即s.t.≥cu,v≥0令为m维行

6、向量，则以上模型又可写成：s.t.≥c（2.8）y无符号限制将问题（2.7）与问题（2.8）称为一对非对称型的对偶问题.要注意的是：（P）问题（2.7）中约束为等式，则其（D）问题（2.8）中对偶变量无符号限制.32例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

7、.9）化为标准形式：s.t.≥0再按式（2.8）写出它的（D）问题为s.t.≥≥≥－≥0，≥0即s.t.≥=（2.10）≥0，无符号限制，≤032表2-1原问题对偶问题目标函数max目标函数min约束条件m个≤≥＝m个≥0≤0无符号限制变量变量n个≥0≤0无符号限制n个≥≤＝约束条件目标函数的系数约束条件右端常数系数矩阵A约束条件右端常数目标函数的系数系数矩阵AT将问题（2.9）与问题（2.10）称为一对混合型对偶问题.从以上三种形式的对偶关系中，可以总结