北京理工大学：《运筹学》课程电子教案（PPT教学课件）第三章 线性规划问题的对偶与灵敏度分析

111 11 问题的偶导园截分析 11 1111 制作:北京理工大学吴祈宗等

运筹学课件 第三章 线性规划问题的对偶与灵敏度分析 制作：北京理工大学 吴祈宗等

第三章 线性规划问题的对偶与 灵敏度分析 本章内容重点 线性规划的对偶冋题概念、 理论及经济意义 线性规划的对偶单纯形法 线性规划的灵敏度分析

2 第三章 线性规划问题的对偶与 灵敏度分析 线性规划的对偶问题概念、 理论及经济意义 线性规划的对偶单纯形法 线性规划的灵敏度分析 本章内容重点

1。线性规划划偶问题 对偶原理 对偶问题定义- 线性规划 问题写出其对偶问题。要掌握在 对称形式和非对称情况下由原后 题写出对偶问题的方法。 对偶定理- 只需了解原冋 题与对偶问题解的关系,证明从

3 1.线性规划对偶问题 对偶原理 对偶问题定义—— 线性规划 问题写出其对偶问题，要掌握在 对称形式和非对称情况下由原问 题写出对偶问题的方法。 对偶定理—— 只需了解原问 题与对偶问题解的关系，证明从 略

1.线性规物对偶向题 1.对偶问题 若第二章例2.1问题的设备都用于 外协加工,工厂收取加工费。试问:设 备A、B、C每工时各如何收费才最有 竞争力? 设,y,巧分别为每工时设备 小BC的收取费用

4 1.对偶问题： 若第二章例2.1问题的设备都用于 外协加工，工厂收取加工费。试问：设 备 A、B、C 每工时各如何收费才最有 竞争力？ 设 y1 ，y2 ，y3 分别为每工时设备 A、B、C 的收取费用。 1.线性规划对偶问题

性规圳原问题 例2.1:某工厂拥有A、BC三种类型的 设备,生产甲、乙两种产品。每件产品在 生产中要占用的设备机时数。每件产品 可以获得的利润以及三种设备可利用的时 数如下表所示。求获最大利润的方案 产品甲产品乙设备能力 设备A 3 65 设备B 40 设备C 0 75 利润/(元/件) 1500 2500

5 线性规划原问题 例2.1:某工厂拥有A、B、C三种类型的 设备，生产甲、乙两种产品。每件产品在 生产中需要占用的设备机时数，每件产品 可以获得的利润以及三种设备可利用的时 数如下表所示。求获最大利润的方案。 产品甲 产品乙 设备能力 （h） 设备A 3 2 65 设备B 2 1 40 设备C 0 3 75 利润/（元/件） 1500 2500

1线性规划对偶门题 Maxz=1500x1+2500x2 s.t.3x1+2x≤65 2x1+x≤40原问题 3x2≤75 x1,x2>0 Minf=651+40y2+75y3 s.t.3n1+2y2>1500 (不少于甲产品的利润) 2n+y2+313>2500对偶题 (不少于乙产品的利润) ,y2,y3>0

6 Max z = 1500x1 + 2500x2 s.t. 3x1 + 2x2 ≤ 65 2x1 + x2 ≤ 40 原问题 3x2 ≤ 75 x1 ,x2 ≥ 0 Min f = 65y1+ 40y2 + 75y3 s.t. 3y1+2y2 ≥1500 （不少于甲产品的利润） 2y1+y2+3y3 ≥2500 对偶问题 （不少于乙产品的利润） y1, y2 , y3 ≥ 0 1.线性规划对偶问题

角.能性规划对码问题 2、对偶定义 对称形式: 互为对偶 N(LP) Max z=cTx(DP)Min f=bTy . Ax J C 0 0 Max -- Min-->

7 2、对偶定义 对称形式： 互为对偶 (LP) Max z = c T x (DP) Min f = b T y s.t. Ax ≤ b s.t. AT y ≥ c x ≥ 0 y ≥ 0 “Max -- ≤ ” “Min-- ≥” 1.线性规划对偶问题

L.线性规划偶问题 一对对称形式的对偶规判之间具有 下面的对应关系。 (1)若一个模型为目标求“极大”, 约束为“小于等于”的不等式,则它的 对偶模型为目标求“极小”,约東是 乌“大于于”的不香式。 即“max,≤ 和“min, ”相对应

8 一对对称形式的对偶规划之间具有 下面的对应关系。 (1)若一个模型为目标求“极大” ， 约束为“小于等于”的不等式，则它的 对偶模型为目标求“极小” ，约束是 “大于等于”的不等式。即“max，≤” 和“min，≥”相对应。 1.线性规划对偶问题

L.线性规划偶问题 (2)从约束系数矩阵看:一个模型中 为A,则另一个模型中为小。一个模型 是m约束,n个变量,则它的对偶模型 为n个约束,Ⅲ个变量。 (3)从数据b(的位置看:在两个规 划模型中,b和C的位置对换。 (4)两个规划模型中的变量皆非负

9 (2)从约束系数矩阵看：一个模型中 为Ａ，则另一个模型中为A T 。一个模型 是m个约束，n个变量，则它的对偶模型 为n个约束，m个变量。 (3)从数据b、C的位置看：在两个规 划模型中，b和C的位置对换。 (4)两个规划模型中的变量皆非负。 1.线性规划对偶问题

L.线性规划对偶题 非对称形式的对偶规划 般称不具有对称形式的一对线性规划为 非对称形式的对偶规划。 对于非对称形式的规划.可以按照下面 的对应关系直接给出其对偶规划 (1)将模型统一为“max,≤”或“min, ”的形式,对于其中的等式约束按下面 (2)、(3)中的方法处理 (2)若原规划的某个约束条件为等式约束 则在对偶规划中与此约束对应的那个变量取值 没有非负限制

10 非对称形式的对偶规划 一般称不具有对称形式的一对线性规划为 非对称形式的对偶规划。 对于非对称形式的规划，可以按照下面 的对应关系直接给出其对偶规划。 （1）将模型统一为“max，≤”或“min， ≥” 的形式，对于其中的等式约束按下面 （2）、（3）中的方法处理； （2）若原规划的某个约束条件为等式约束， 则在对偶规划中与此约束对应的那个变量取值 没有非负限制； 1.线性规划对偶问题 1 x2 x3 xj  0 1 y11 a23 1 b2 y21 a23 2 b 3 y31 a23 3 b 4 y41 a23 4 b y j  0 1 c2 c3 c 1 x2 x3 xj  0 1 y11 a23 1 b2 y21 a23 2 b 3 y31 a23 3 b 4 y41 a23 4 b y j  0 1 c2 c3 c 1 x2 x3 xj  0 1 y11 a23 1 b2 y21 a23 2 b 3 y31 a23 3 b 4 y41 a23 4 b y j  0 1 c2 c3 c