《运筹学》课程教学资源（PPT课件讲稿）第三章 对偶理论及灵敏度分析

第三章对偶理论及灵敏度分析 3.1.1线性规划对偶问题 3.1.2对偶问题的基本性质 3.1.3影子价格 3.1.4对偶单纯形法 3.2.1灵敏度问题及其图解法 3.2.2灵敏度分析 3.2.3参数线性规划

第三章 对偶理论及灵敏度分析 3.1.1 线性规划对偶问题 3.1.2 对偶问题的基本性质 3.1.3 影子价格 3.1.4 对偶单纯形法 3.2.1 灵敏度问题及其图解法 3.2.2 灵敏度分析 3.2.3 参数线性规划

3.L.1线性觊划的对偶题 一、对偶问题的提出 二、原问题与对偶问题的教学模型 原问题与对偶问题的对应关亲 返回

返回 继续 3.1.1 线性规划的对偶问题 ◼一、对偶问题的提出 ◼二、原问题与对偶问题的数学模型 ◼三、原问题与对偶问题的对应关系

爱家的 、对偶问题的提出 实例:某家电厂家利用现有资源生产两种 产品,有关数据如下表: 产品产品Ⅱ D 上页 设备A 15时 下页 设备B 6 24时 调试工序1 5211 5时 回 利润(元)2 通观图

返回 上页 下页 对 偶 问 题 实例：某家电厂家利用现有资源生产两种 产品， 有关数据如下表： 设备A 设备B 调试工序 利润（元） 0 6 1 2 5 2 1 1 15时 24时 5时 产品Ⅰ 产品Ⅱ D 一、对偶问题的提出

2测测紧 设I产量X1 如何安排生产, Ⅱ产量—x2 使获利最多? 超maxz=2x1+x2 s. t 5x2<15 上页 2 6x1+2x2≤24 下页 x1+x2≤5 回 x1,x2≥0 冢

返回 上页 下页 对 偶 问 题 如何安排生产， 使获利最多？ 厂 家 设 Ⅰ产量––––– Ⅱ产量––––– x1 x2 , 0 5 6 2 24 5 15 max 2 1 2 1 2 1 2 2 1 2  +  +   = + x x x x x x s.t. x z x x

设:议音 设备B 元时 调试工序 元y时 付出的代价最小 且对方能接受 上页 下页 /出让代价应不低于 返回 用同等数量的资源 自己生产的利润。 烈

返回 上页 下页 对 偶 问 题 设：设备A —— 元／时 设备B –––– 元／时 调试工序 –––– 元／时 y1 y 2 y 3 收 购 付出的代价最小， 且对方能接受。 出让代价应不低于 用同等数量的资源 自己生产的利润

y2+y3≥2单位产品工出租 6 ∠收入不低于2元 5y+212+y≥1单位产品工出租 收入不低于1元 收购方的意愿: minw=151+24y2+5y 上页 下页 回

返回 上页 下页 对 偶 问 题 设备A 设备B 调试工序 利润（元） 0 6 1 2 5 2 1 1 15时 24时 5时 Ⅰ Ⅱ D ◼ 厂家能接受的条件： ◼ 收购方的意愿： min 15 1 24 2 5 3 w = y + y + y 单位产品Ⅰ出租 收入不低于2元 单位产品Ⅱ出租 收入不低于1元 出让代价应不低于 用同等数量的资源 5 自己生产的利润。 2 1 6 2 1 2 3 2 3 + +  +  y y y y y

max z=2xu+x2 s t 5x2<15 原 6x+2x2≤24/ 问 x2≤5 题 0 对对偶问题 上页 min w 们2+5 下页 st x:+y≥2对 偶 回 y+2y2+y2≥ 收 购 y1,y2,y3≥0 1额

返回 上页 下页对偶问题 厂家 , 0 5 6 2 24 5 15 max 21 2 1 2 1 2 2 1 2  +  +  = + x x x x x x s.t. x z x x y , , 0 5 2 1 . 6 2 1 2 3 1 2 3 2 3 + +  +  y y y y y s t y y min 15 1 24 2 5 3 w = y + y + y 对偶问题 原问题收购 厂家 一对对偶问题

题原问题 对偶问题 max Z=CX min w=yb 题,.AX≤b→1.Y≥C X≥0 Y≥0 13个约 2个约束 上页 般 束 3个变量 窥2个变 下页 =(c1,c2)Y=0,y2,y3) 回 bI A=(a,) X= 6=l b2 b3 通观图

返回 上页 下页对偶问题  =   =  0 min AX b X 0 . . max z CX Y s.t. YA C w Yb st ( , ) 1 2 C = c c   = 21 xx A = (aij) X Y = (y1,y 2,y3 )  = 321 bbb b 3个约 束2个变 量 2个约束 3个变量 原问题 对偶问题 一般规律

将点都都就其它形式该 的对偶 离1.max<>mn 题2.限定向量b个变量。 4.maxz的LP约束 的 下页 LP是“”的约束。 回 5.变量都是非负限制

返回 上页 下页 对 偶 问 题 特点： 1． 2．限定向量b 价值向量C （资源向量） 3．一个约束 一个变量。 4． 的LP约束“ ” 的 LP是“ ”的约束。 5．变量都是非负限制。   max min max z   min z 其它形式 的对偶 ?

的线的 =、原问题与对偶问题的数学模型 1.对称形式的对偶 当原问题对偶问题只含有不等式约束时, 称为对称形式的对偶。 情形 上页 下页 原问题 对偶问题 max Z=CX min w=yb 回 AX≤b→1s.t.YA≥C st X≥0 Y≥0

返回 上页 下页 对 偶 问 题 二、原问题与对偶问题的数学模型 ◼ 1．对称形式的对偶 当原问题对偶问题只含有不等式约束时， 称为对称形式的对偶。       =    =            0 min AX b X 0 . . max z CX Y s.t. YA C w Yb st 原问题 对偶问题 情形一：