1、LOGO2.1 线性规划的对偶模型 Dual Model of LP2.2 对偶性质 Dual property 2.3 对偶单纯形法 Dual Simplex Method2.4 灵敏度与参数分析 Sensitivity and ParametricAnalysis2.1.1 引例【 例 2 1】 某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表： 建立总利润最大的数学模型。 产 品资 源 A B C 资 源限量 9 8 6 500 5 4 7 450 8 3 2 300 7 6 4 550单 件 产 品利润100 80 702.1 线性规划的对偶模型2 第 2章 对偶理论【
2、 解 】 设 x1， x2， x3分别为产品 A， B， C的产量，则现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产品，要将现有的资源转让或出租给其它企业，那么资源的转让价格应是多少才合理？合理的价格应是对方用最少的资金购买本企业的全部资源，而本企业所获得的利润不应低于自己用于生产时所获得的利润。2.1.1 引 例（ LP）3 第 2章 对偶理论设 y1， y2， y3， y4分别表示四种资源的单位增值价格售价成本增值总增值最低可表示为min w=500y1+450y2+300y3+550y4 企业生产一件产品 A用了四种资源的数量分别是 9， 5， 8和 7个单位，利润是 100
3、，企业出售这些数量的资源所得的利润（增值）不能少于 100，即同理，对产品 B和 C有另有2.1.1 引 例yi0,i=1, ,4 4 第 2章 对偶理论这是一个线性规划数学模型，称这一线性规划问题是前面生产计划模型 ( )的 对偶线性规划问题 或 对偶问题 （ Dual Poblem, DP） 。生产计划的线性规划问题称为原始线性规划问题 或 原始问题 。2.1.1 引 例（ ）（ DP）5 第 2章 对偶理论观察以上两个线性规划模型的对应关系原始问题 对偶问题2.1.1 引 例原始问题的 C,A,b分别转置后就是对偶问题的资源限量 (b)，消耗系数 (A)及利益系数 (C)原始问题和对偶问
4、题是互为对偶的两个线性规划问题，已知一个问题就可以写出另一个问题 。 6 第 2章 对偶理论xjyix1 x2 x3 原始约 束 min y1 9 8 6 500y2 5 4 7 450y3 8 3 2 300y4 7 6 4 550对 偶 约束 max 100 80 70对 偶 表2.1.1 引 例7 第 2章 对偶理论规范形式（ Canonical Form）的定义：目标函数求 极大值 时，所有约束条件 为 号 ， 变量非负 ；目标函数求 极小值 时，所有约束条件 为 号 ， 变量非负 。2.1.2 线性规划的规范形式8 第 2章 对偶理论XB XN XS bXB B N E bC CB CN 0 0XB XN XS bXB E B 1N B 1 B 1b 0 CN CBB 1N CBB 1 CBB 1b表 2 2表 2 32.1.2 线性规划的规范形式9 第 2章 对偶理论2.1.3 对偶模型u 每个线性规划问题都有一个与之相伴的对偶问题 。u 已知一个问题就可写出另一个问题。l 当原始问题是规范形式，其对偶问题很容易写出；l 如果给出的问题不是规范形式， 可以先化成规范形式再写对偶问题。也可直接按表 2-4中的对应关系写出非规范形式的对偶问题。10 第 2章 对偶理论
