对偶理论与灵敏度分析

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 问题的对偶问题： ...