第2章 线性规划的对偶理论与灵敏度分析2.1

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

1、第2章线性规划的对偶理论与灵敏度分析§2.1线性规划的对偶问题随着线性规划应用的逐步深入，人们发现一个线性规划问题往往伴随者与之配对的、两者有密切联系的另一个线性规划问题。将其中一个称为原问题，另一个称为对偶问题。自从对偶理论提出以来，已经有了相当深入的研究。对偶理论深刻揭示了原问题与其对偶问题的内在的联系，由对偶理论引伸出来的对偶解有着重要的经济意义，是经济学中重要的概念。对偶理论充分显示出线性规划理论逻辑上的严谨性与结构上的对称性，它是线性规划理论的重要成果。2.1.1对偶线性规划问题例2.1.1某家具厂木器车间加工木门与木窗两种产品，加工木门收入

2、为56元/扇，加工木窗收入为30元/扇。加工一扇木门需要木工4小时，油漆工2小时；加工一扇木窗需要木工3小时，油漆工1小时。该家具厂每天可用木工总工时120小时，油漆工总工时50小时。问该家具厂应如何安排加工任务才能使每天收益最大？即该车间每天加工木门15扇、木窗20扇使收入最大，收入可达1440元。（2.1.1）现在从另一个角度来考虑该车间的加工问题。假若有一个个体经营者，手中有一批木器家具生产订单，由于人手不足不能加工出来，他想利用该车间的木工和油漆工来完成他的订单。他要考虑付给木工和油漆工每个工时的报酬，使得该车间能够愿意替他加工这批订单，又使自

3、己支付的工时费最少。器车间能够接受，木工4小时、油漆工2小时能加工一扇木门，创造收入56元，小时可以加工一扇木窗，创造收入30元，支付的工时费不低于30元，即必须设分别表示支付每个木工工时和每个油漆工工时的价格，为了使木支付的工时费不低于56元，即必须满足；木工3小时、油漆工1满足同时，该个体经营者的目标为每日所支付的工时费最少。因此所建立的线性规划问题数学模型为：将线性规划模型（2.1.2）称为（2.1.1）的对偶线性规划问题，两者之有着紧密的联系。它们都是使用了木器加工车间的数据，只是这些数据在模型中所处的位置不同，反映所要表达的含义也不相同。（2

4、.1.1）是反映追求木器车间收入最大的数学模型，（2.1.2）是寻求个体经营者支给木器车间工时费最少的数学模型。一般地，给定线性规划问题：（2.1.2）用LINGO求得（2.1.2）的最优解为：（LP）（2.1.3）称线性规划问题（DLP）（2.1.4）为（2.1.3）的对偶线性规划问题。或者对线性规划问题（LP）（2.1.5）称线性规划问题（DLP）（2.1.6）为（2.1.5）的对偶线性规划问题。其中证明对于线性规划问题（2.1.6）改写求目标函数最大化且不等式约束条件两边同乘以（-1）不等式反向，则（2.1.7）即（2.1.8）定理2.1.1（对

5、称定理）对偶问题的对偶问题是原问题。（2.1.8）式的对偶线性规划问题是（2.1.9）将（2.1.9）式改写成求目标函数最大化且不等式约束条件两边同乘以（-1）不等式反向，则（2.1.10）（2.1.10）就是模型（2.1.5）。因此，（2.1.5）是（2.1.6）的对偶线性规划问题。所以，（2.1.5）与（2.1.6）是一对互为对偶的线性规划问题。（2.1.9）2.1.2对偶表与对偶原理表2.1.1对偶表…约束条件…≤…≤……………………≤约束条件≥≥…≥…从横行上看表示问题（LP），从纵列上看表示问题（DLP）。为了直观表达一对互为对偶的线性规划问

6、题（LP）与（DLP），通常用对偶表（表2.1.1）表示。以上是对称形式的线性规划问题，若不符合以上对称形式，则有非对称形式的对偶问题的结论：无非负限制；如果线性规划问题偶线性规划问题（DLP）中的第k个变量定理2.1.2如果线性规划问题（LP）中第k个约束条件是等式，那么它的对个约束条件是等式。反之，亦然。的第（LP）中第个变量无非负限制，那么它的对偶线性规划问题（DLP）中证明假设原问题（LP）为（2.1.11）（2.1.12）由对称形式的对偶关系可知，（2.1.12）式的对偶线性规划问题为（2.1.13）将（2.1.13）式整理，得（2.1.14

7、）（2.1.15）(2.1.15)中与(2.1.11)的等式约束相对应的变量无非负限制，(2.1.15)中与(2.1.11)的无非负限制的变量相对应的为等式约束。因此，线性规划问题与其对偶问题的对偶关系如表2.1.2所示。表2.1.2线性规划问题与其对偶问题之间的关系原问题对偶问题目标函数形式max目标函数形式min变量n个变量约束条件n个约束无非负限制约束=约束条件m个约束条件变量m个变量约束约束约束=无非负限制约束条件右端常数项目标函数系数目标函数系数约束条件右端常数项约束方程（不等式）组系数矩阵A约束方程（不等式）组系数矩阵例2.1.2写出下述线

8、性规划问题的对偶线性规划问题（2.1.16）解首先将线性规划问题（2.1.16）写成标准形式：