第三章 对偶理论和灵敏度分析.ppt

第三章对偶理论和灵敏度分析
第三章对偶理论和灵敏度分析
第1节线性规划的对偶问题
第2节对偶问题的基本性质
第3节影子价格
第4节对偶单纯形法
第5节灵敏度分析
第1节线性规划的对偶问题
一、对偶的含义
对同一事物(问题)从不同的角度(立场)观察,有两种对立的表述。
例如:“平面中矩形的面积与周长的关系”有两种表述:周长一定,面积最大的矩形是正方形;面积一定,周长最短的矩形是正方形。
第1节线性规划的对偶问题
例1:某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品,已知生产单位产品所需的设备台时及A、B两种原材料的消耗,如下表所示。该工厂每生产一件产品Ⅰ可获利2元,每生产一件产品Ⅱ可获利3元,问应如何安排计划使该工厂获利最多?
产品
资源
产品Ⅰ
产品Ⅱ
现有条件
设备
1台时/件
2台时/件
8台时
原材料A
4kg/件
0
16kg
原材料B
0
4kg/件
12kg
另一个角度
灵敏度分析
第1节线性规划的对偶问题
例1:
解:设计划期内产品Ⅰ、Ⅱ的产量分别为x1、x2
max z =2x1+3x2
x1+2x2≤8
4x1≤16
4x2≤12
x1,x2≥0
求解对偶问题
图解法确定影子价格
第1节线性规划的对偶问题
从另一个角度考虑例1。
假设该工厂的决策者决定不生产产品Ⅰ、Ⅱ,而将其所有资源(设备和原材料)出租或外售,问应给每种资源如何定价,使该工厂的收入最合理?
第1节线性规划的对偶问题
解:设出租单位设备台时的租金为y1,出让单位原材料A,B的售价为y2,y3
minω=8y1+16y2+12y3
y1+4y2≥2
2y1+4y3≥3
y1,y2 ,y3≥0
第1节线性规划的对偶问题
max z =2x1+3x2 minω=8y1+16y2+12y3
x1+2x2≤8 y1+4y2≥2
4x1≤16 2y1+4y3≥3
4x2≤12 y1,y2,y3≥0
x1,x2≥0
第1节线性规划的对偶问题
对于一般产品组合问题的线性规划问题,从另一角度提出问题:
假定有另一公司欲将该公司所拥有的资源收买过来,至少应付出多少代价,才能使该公司愿意放弃生产活动,出让资源?
第1节线性规划的对偶问题
解:设用yi代表收买该公司一单位i种资源时付给的代价