1 §2 对偶与灵敏度分析 一、本章学时数:6 学时 其中讲授学时:5 学时,课堂练习学时:1 学时。 二、本章主要内容: 1 .对偶问题的提出及原问题与对偶问题转化; 2 .对偶问题的基本性质; 3 .影子价格; 4 .对偶单纯形法; 5 .灵敏度分析。 三、本章重点、难点: 1 .对偶问题的提出及原问题与对偶问题转化; 2 .对偶问题的基本性质; 3 . 灵敏度分析。 2 §2.1 LP 的对偶问题 无论从理论和实践角度,对偶理论是 LP 中的一个最重要和有趣的概念,支持对偶理论的基本思想是:每一个 LP 问题都存在一个与其对偶的问题,在求解一个问题解的时候,也同时给出了另一问题的解。 一、问题的提出 例 2.1:设某工厂生产两种产品甲乙,生产过程需要 4 种设备 ABCD 进行加工,每件产品加工所需机时数,每件产品的利润值及每种设备的可利用机时如下表: 1.问:充分利用设备时,应怎样安排甲乙产品的生产数量,利润才能最大? 2.问:如有另外一家公司想租用该厂设备加工生产,那么,这家公司应至少对每台设备的机时价格为多少时,才能使该厂愿意出租设备? 解:1.设甲乙产品各生产1x 2x 件 LP1:0,16482122232211212121xxxxxxxxxMaxZ 2.设每台设备的机时最低价分别为:1y ,2y ,3y ,4y 设备 产品 A 1y B 2y C 3y D 4y 利润 甲1x 2 1 4 0 2 乙2x 2 2 0 4 3 总机时 12 8 16 12 3 LP2:4,3,2,1,0342224212168124213214321iyyyyyyyyyyyMinZi 二、原问题和对偶问题之间的关系: 1.对称形式下的原问题与对偶问题 对称形式下原问题的一般式: 矩阵形式: njxbxaxaxabxaxaxabxaxaxaxcxcxcMaxZjmnmnmmnnnnnn.......21,0.............................221122222121112121112211 0XbAXCXMax 若用iy 代表第 i种资源的估价,则其对偶问题的一般式为: mjycyayayacyayayacyayayaybybybMinZjnmmnnnmmnmmmm.......21,0.............................221122222112112211112211 0YCYAYbMinTT 2.非对称形式下原问题与对偶问题: 方法一:将非对称形式转化为对称形式,求出对偶问题,然后再还原。 例 2.2 写出下列 LP 问题的对偶问题: ...