运筹学：线性规划对偶理论、与灵敏度分析

第 二 章 线性规划对偶理论 与灵敏度分析教学时数： 学时 教学时数：12学时 教学目的与要求： 教学目的与要求：理解线性规划对偶问题理论与影 价格概念,掌握对偶单纯形法及灵敏度分析技巧 子 价格概念 掌握对偶单纯形法及灵敏度分析技巧 教学内容： 教学内容： 1.线性规划对偶问题及相关理论 线性规划对偶问题及相关理论 2.影子价格 影子价格 3.对偶单纯形法 对偶单纯形法 4.灵敏度分析及参数规划 灵敏度分析及参数规划 教学重点： 教学重点：影子价格及灵敏度分析 教学难点： 教学难点：对偶理论

第二章 讲授内容和知识第一节 线性规划的对偶问题 第二节 第三节 第四节 第五节 第六节 对偶问题的基本性质 影子价格 对偶单纯形法 灵敏度分析 参数线性规划(简介)

第 一 节 线性规划的对偶问题一、对偶问题的提出 对称形式的原始-对偶关系 二、对称形式的原始 对偶关系 三、非对称形式的原始-对偶问题 非对称形式的原始 对偶问题 四、原始-对偶关系一览表 原始 对偶关系一览表

一、对偶问题的提出生产计划问题。 例2.1.1 生产计划问题。 某企业生产A、 、 三种畅销产品 三种畅销产品， 某企业生产 、B、C三种畅销产品，每一件产品所需要的资 源和收益列于表中： 源和收益列于表中： 表 1资源甲 资源乙 资源丙 资源丁每件收益( 每件收益(元)

产品 A 产品 B 产品 C 资源限量

3 4 2 600

2 1 2 400

1 3 3 300

1 2 4 200

2000 4000 3000

问：如何安排生产，可以使总利润最大？ 如何安排生产，可以使总利润最大？ 解：利用第一章的知识，设三种产品的生产量分别为x1, 利用第一章的知识，设三种产品的生产量分别为 x2和 x3 ,可以建立线性规划模型如下 可以建立线性规划模型如下:

max z = 2000 x1+4000 x2 +3000 x3 y1 3 x1+4 x2 +2 x3 ≤ 600 2x1+ x2 + 2 x3 ≤ 400 x1+3 x2 +3 x3 ≤ 300 x1+2 x2 +4 x3 ≤ 200 x 1, x 2 , x 3 ≥ 0 假如企业不进行生产， 假如企业不进行生产，而是把全部可利用的资源转 让给其他企业。此时， 让给其他企业。此时，企业必须考虑一个合适的资 源价格，使得： 有企业愿意接受转让 有企业愿意接受转让； 企业自身 源价格，使得：1.有企业愿意接受转让；2.企业自身 没有经济损失。 没有经济损失。 设四种资源的价格确定为 y1, y2 , y3 , y4 。

y2 y3 y4

则有企业愿意接受转让的条件是极小化资源总价， 则有企业愿意接受转让的条件是极小化资源总价，即 w =600 y1+ 400 y2 + 300 y3 + 200 y4 而企业自身没有经济损失的要求可做如下思考： 而企业自身没有经济损失的要求可做如下思考：生 产一件产品，比如A,需要四种资源的量分别为3, 产一件产品，

比如 ，需要四种资源的量分别为 ， 2,1,1个单位。由于要把生产 产品的这些资源卖 个单位。 , , 个单位 由于要把生产A 出去，所以， 出去，所以，单件总卖值不应比企业自己生产时的 收益( 收益(2000)低，即， ) 3 y1 + 2 y2 + y3 + y4 ≥2000 对产品B: 对产品 ：4 y1 + y2 + 3 y3 + 2 y4 ≥ 4000 对产品C 对产品 ：2 y1 + 2 y2 +3 y3 +4 y4 ≥3000

max z = 2000 x1+4000 x2 +3000 x3 3 x1+4 x2 +2 x3 ≤ 600 2x1+ x2 + 2 x3 ≤ 400 x1+3 x2 +3 x3 ≤ 300 x1+2 x2 +4 x3 ≤ 200 x1 ≥0, x2 ≥ 0,x3 ≥0

原 问 题

min w = 600 y1+ 400 y2 + 300 y3 + 200 y4 3 y1 + 2 y2 + y3 + y4 ≥2000 对 偶 4 y1 + y2 + 3 y3 + 2 y4 ≥ 4000 问 2 y1 + 2 y2 +3 y3 +4 y4 ≥3000 题 y1 , y2 , y3 , y4 ≥0

两个线性规划问题的比较中，可以初步发现： 两个线性规划问题的比较中，可以初步发现： (1)原问题的目标函数求极大， 原问题的目标函数求极大， 原问题的目标函数求极大 对偶问题的目标函数求极小； 对偶问题的目标函数求极小； (2)原问题目标函数中的系数 原问题目标函数中的系数 在对偶问题中变为约束条件的右端常数项； 在对偶问题中变为约束条件的右端常数项； (3)约束条件的不等式方向改变了； 约束条件的不等式方向改变了； 约束条件的不等式方向改变了 (4)约束方程的系数矩阵发生了转置； 约束方程的系数矩阵发生了转置； 约束方程的系数矩阵发生了转置 (5)原问题约束数目与对偶问题的变量数相等。 原问题约束数目与对偶问题的变量数相等。 原问题约束数目与对偶问题的变量数相等

二、对称形式的原始-对偶关系 对称形式的原始 对偶关系对称形式的条件： 对称形式的条件： (1)变量全部具有非负约束； )变量全部具有非负约束； (2)目标函数求极大值时，约束不等式符号全部 )目标函数求极大值时， 为≤;目标函数为求极小值时，约束不等式的符号 ；目标函数为求极小值时， 全部为≥。 全部为 。 max z =c1x1+ c2x2 +… + cnxn a11x1+ a12x2 + … + a1nxn ≤ b1 a21x1+ a22x2 + … + a2nxn ≤ b2 st. …… am1x1+ am2x2 + … + amnxn ≤ bm x1, x2 , …,xn ≥0 对偶问题的一般形式为： 对偶问题的一般形式为： (2-1)

max z =c1x1+ c2x2 +… + cnxn a11x1+ a12x2 + … + a1nxn ≤ b1 a21x1+ a22x2 + … + a2nxn ≤ b2 …… am1x1+ am2x2 + … + amnxn ≤ bm x1, x2 , …,xn ≥0 min w = b1y1+ b2y2 +… + bmym a11y1+ a21y2 + … + am1ym ≥ c1 a12y1+ a22y2 + … + am2ym ≥ c2 …… a1ny1+ a2ny2 + … + amnym ≥ cn y1 , y2 , …, ym ≥0

原问题： 原问题： max z = C X AX ≤ b X ≥0 Y=(y1,y2,…,ym) 对偶问题： 对偶问题： min w = Y b YA≥C Y≥0

yi y1 y2 : ym

xj x1 a11 a21 : am1

x2 a12 a22

… … …

xn 原始约束 对 …… 此处隐藏：2918字，全部文档内容请下载后查看。喜欢就下载吧 ……