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

第第2章章 线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析 2.1 线性规划的对偶问题线性规划的对偶问题 随着线性规划应用的逐步深入，人们发现一个线性规划问题往往伴随者与之配对的、两者有密切联系的另一个线性规划问题。将其中一个称为原问题，另一个称为对偶问题。自从对偶理论提出以来，已经有了相当深入的研究。对偶理论深刻揭示了原问题与其对偶问题的内在的联系，由对偶理论引伸出来的对偶解有着重要的经济意义，是经济学中重要的概念。对偶理论充分显示出线性规划理论逻辑上的严谨性与结构上的对称性，它是线性规划理论的重要成果。2.1.1 对偶线性规划问题对偶线性规划问题 例例2.1.1 某家具厂木器车间加工木门与木窗两种产品，加工木门收某家具厂木器车间加工木门与木窗两种产品，加工木门收入为入为56元元/扇，加工木窗收入为扇，加工木窗收入为30元元/扇。加工一扇木门需要木工扇。加工一扇木门需要木工4小时，油漆工小时，油漆工2小时；加工一扇木窗需要木工小时；加工一扇木窗需要木工3小时，油漆工小时，油漆工1小时。小时。该家具厂每天可用木工总工时该家具厂每天可用木工总工时120小时，油漆工总工时小时，油漆工总工时50小时。问小时。问该家具厂应如何安排加工任务才能使每天收益最大？该家具厂应如何安排加工任务才能使每天收益最大？即该车间每天加工木门即该车间每天加工木门1515扇、木窗扇、木窗2020扇使收入最大，收入可达扇使收入最大，收入可达14401440元。元。（2.1.1）现在从另一个角度来考虑该车间的加工问题。假若有一个个体经营者，手中有一批木器家具生产订单，由于人手不足不能加工出来，他想利用该车间的木工和油漆工来完成他的订单。他要考虑付给木工和油漆工每个工时的报酬，使得该车间能够愿意替他加工这批订单，又使自己支付的工时费最少。器车间能够接受，木工4小时、油漆工2小时能加工一扇木门，创造收入56元，小时可以加工一扇木窗，创造收入30元，支付的工时费不低于30元，即必须设分别表示支付每个木工工时和每个油漆工工时的价格，为了使木支付的工时费不低于56元，即必须满足 ；木工3小时、油漆工1满足 同时，该个体经营者的目标为每日所支付的工时费 最少。因此所建立的线性规划问题数学模型为：将线性规划模型（2.1.2）称为（2.1.1）的对偶线性规划问题，两者之有着紧密的联系。它们都是使用了木器加工车间的数据，只是这些数据在模型中所处的位置不同，反映所要表达的含义也不相同。（2.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（对称定理）对偶问题的对偶问题是原问题。（对称定理）对偶问题的对偶问题是原问题。（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）。为了直观表达一对互为对偶的线性规划问题（为了直观表达一对互为对偶的线性规划问题（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）（2.1.15）(2.1.15)中与中与(2.1.11)的等式约束相对应的变量无非负限制，的等式约束相对应的变量无非负限制，(2.1.15)中与中与(2.1.11)的无非负限制的变量相对应的为等式约束。的无非负限制的变量相对应的为等式约束。因此，线性规划问题与其对偶问题的对偶关系如表因此，线性规划问题与其对偶问题的对偶关系如表2.1.2所示。所示。表表2.1.2 2.1.2 线性规划问题与其对偶问题之间的关系线性规划问题与其对偶问题之间的关系原问题对偶问题目标函数形式max目标函数形式min变量n个变量 约束条件 n个约束无非负限制 约束=约束条件m个约束条件变量m个变量 约束 约束约束=无非负限制约束条件右端常数项 目标函数系数 目标函数系数 约束条件右端常数项约束方程（不等式）组系数矩阵 A约束方程（不等式）组系数矩阵 例例2.1.2 写出下述线性规划问题的对偶线性规划问题写出下述线性规划问题的对偶线性规划问题（2.1.16）解解 首先将线性规划问题（2.1.16）写成标准形式：（2.1.17）由定理2.1.2，得其对偶线性规划问题为：（2.1.18）对于更一般的线性规划问题，可以按照表2.1.2的对应关系给出其对偶线性规划问题，兹不赘述。作业P111（1）练习用LINGO求解线性规划问题