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

《第三章 对偶理论及灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章对偶理论及灵敏度分析1灵敏度问题及其图解法灵敏度问题灵敏度分析——图解法灵敏度问题背景：线性规划问题中，都是常数，但这些系数是估计值和预测值。市场的变化值变化；工艺的变化值变化；资源的变化值变化。问题：当这些系数中的一个或多个发生变化时，原最优解会怎样变化？当这些系数在什么范围内变化时，原最优解仍保持不变？若最优解发生变化，如何用最简单的方法找到现行的最优解？研究内容：研究线性规划中，的变化对最优解的影响。研究方法：图解法对偶理论分析仅适用于含2个变量的线性规划问题在单纯形表中进行分析MaxZ=50x1+1

2、00x2x1+x23002x1+x2400x2250x1、x20线性规划模型灵敏度分析——图解法分析价值系数c的改变产生的影响x2400—300—200—100—0

3、

4、

5、

6、100200300400x1x2=250x1+x2=3002x1+x2=400ABCDE最优解(50,250)灵敏度分析——图解法Z=27500灵敏度分析—图解法目标函数的系数50x1+100x2=Z100x2=-50x1+Zx2=-+50x1Z100100400—300—200—100—0

7、

8、

9、

10、100200300400x1x2=25

11、0x1+x2=3002x1+x2=400ABCDE灵敏度分析—图解法目标函数的系数50x1+100x2=Z100x2=-50x1+Zx2=-+50x1Z100100400—300—200—100—0

12、

13、

14、

15、100200300400x1x2=250x1+x2=3002x1+x2=400ABCDE若c1增加（c2不变）新的最优解灵敏度分析—图解法目标函数的系数50x1+100x2=Z100x2=-50x1+Zx2=-+50x1Z100100400—300—200—100—0

16、

17、

18、

19、100200300400x1x2=2

20、50x1+x2=3002x1+x2=400ABCDE若c1减少（c2不变）新的最优解灵敏度分析—图解法最优解不变的范围（设c1改变c2固定）

21、

22、

23、

24、100200300400x1x2=250x1+x2=3002x1+x2=400ABCDE（斜率为-1）（斜率为0）分析资源系数b的改变产生的影响MaxZ=50x1+100x2x1+x23102x1+x2400x2250x1、x20400—300—200—100—0

25、

26、

27、

28、100200300400x1x2=250x1+x2=3102x1+x2=400ABCDE最

29、优解(60,250)Z=28000增加10个单位的第一种资源，能让利润增加28000-27500=500个单位，也就是增加一个单位的第一种资源，利润增加50个单位。我们称第一种资源的对偶价格为50.像这样在约束条件常数项中增加一个单位而使最优目标函数值得到改进的数量称之为这个约束条件的对偶价格。在一定范围内，当约束条件右边常数增加1个单位时（1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）；（2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏）；（3）若约束条件的对偶价格等于0，则

30、最优目标函数值不变。返回继续2线性规划的对偶问题一、对偶问题的提出二、原问题与对偶问题的数学模型三、原问题与对偶问题的对应关系实例：某家电厂家利用现有资源生产两种产品，有关数据如下表：设备A设备B调试工序利润（元）0612521115时24时5时产品Ⅰ产品ⅡD一、对偶问题的提出如何安排生产，使获利最多？厂家设Ⅰ产量–––––Ⅱ产量–––––设：设备A——元／时设备B––––元／时调试工序––––元／时收购付出的代价最小，且对方能接受。出让代价应不低于用同等数量的资源自己生产的利润。设备A设备B调试工序利润（元）0

31、612521115时24时5时ⅠⅡD厂家能接受的条件：收购方的意愿：单位产品Ⅰ出租收入不低于2元单位产品Ⅱ出租收入不低于1元出让代价应不低于用同等数量的资源自己生产的利润。厂家对偶问题原问题收购厂家3个约束2个变量2个约束3个变量原问题对偶问题一般规律特点：1．2．限定向量b价值向量C（资源向量）3．一个约束一个变量。4．的LP约束“”的LP是“”的约束。5．变量都是非负限制。其它形式的对偶?二、原问题与对偶问题的数学模型1．对称形式的对偶当原问题对偶问题只含有不等式约束时，称为对称形式的对偶。原问题对偶问题情形

32、一：原问题对偶问题化为标准对称型情形二：证明对偶2、非对称形式的对偶若原问题的约束条件是等式，则原问题对偶问题推导:原问题根据对称形式的对偶模型,可直接写出上述问题的对偶问题:令，得对偶问题为：证毕。三、原问题与对偶问题的对应关系原问题（或对偶问题）对偶问题（或原问题）例:对偶问题为四、对偶定理（强对偶性）：——若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们