第三章线性规划问题的对偶与灵敏度分析优秀课件.ppt

《第三章线性规划问题的对偶与灵敏度分析优秀课件.ppt》由会员分享，可在线阅读，更多相关《第三章线性规划问题的对偶与灵敏度分析优秀课件.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章线性性规划划问题的的对偶偶与灵与灵敏度分析敏度分析第1页，本讲稿共28页线性规划的对偶问题线性规划的对偶问题第三章第三章 线性性规划划问题的的对偶偶与灵与灵敏度分析敏度分析1对偶单纯形法对偶单纯形法 2灵敏度分析灵敏度分析 3第2页，本讲稿共28页v某企业可生产A、B两种产品，需消耗煤、电、油三种资源。有关数据如下表所示：v试拟订使总收入最大的生产方案。A B资源限量资源限量煤煤电电油油9 44 5 3 10360200300单位产品价格单位产品价格 7 123.1对偶问题的提出对偶问题的提出第3页，本讲稿共28页A B资源限量资源限量煤煤电电油油9 44 5 3 10360200

2、300单位产品价格单位产品价格 7 12 假若有另一家厂商提出要购买其煤、电、油全部资源，并希望花费尽量少，试建立购买者的线性规划模型。第4页，本讲稿共28页原问题与对偶问题的对应关系原问题与对偶问题的对应关系v对称形式：对称形式：原问题：对偶问题：第5页，本讲稿共28页原问题原问题对偶问题对偶问题目标max 型目标min 型有n 个变量有n 个约束有m 个约束有m 个变量目标函数系数约束条件右端常数约束条件右端常数目标函数系数约束系数矩阵约束系数矩阵的转置原问题与对偶问题的对应关系原问题与对偶问题的对应关系(一一)第6页，本讲稿共28页课堂练习课堂练习v请写出下述线性规划的对偶问题：请写出下

3、述线性规划的对偶问题：Max Z=2x1+3 x2 s.t.x1+x2 350 x1 125 2x1+x2 600 x1 ,x2 0第7页，本讲稿共28页v非对称形式不具备对称形式的一对线性规划非对称形式不具备对称形式的一对线性规划称为非对称形式的对偶规划称为非对称形式的对偶规划：例：例：s.t 第8页，本讲稿共28页原问题原问题对偶问题对偶问题第j 个变量无限制第j 个约束为等式约束第i个约束为等式约束第i个变量无限制原问题与对偶问题的对应关系原问题与对偶问题的对应关系(二二)第9页，本讲稿共28页原问题原问题对偶问题对偶问题目标max 型目标min 型有n 个变量有n 个约束有m 个约束有

4、m 个变量目标函数系数约束条件右端常数约束条件右端常数目标函数系数约束系数矩阵约束系数矩阵的转置原问题原问题对偶问题对偶问题第j 个变量无限制第j 个约束为等式约束第i个约束为等式约束第i个变量无限制关系关系(一一)关系关系(二二)第10页，本讲稿共28页课堂练习课堂练习v请写出下述线性规划的对偶问题：请写出下述线性规划的对偶问题：Max Z=4x1+5 x2+2 x3 s.t.3x1+2x2+x3 20 4x1-3x2+3x3 10 x1+x2+2x3=5 x1 ,x3 0第11页，本讲稿共28页对偶问题的经济解释资源的影子价格对偶问题的经济解释资源的影子价格 v某工厂在计划期内安排、两种产

5、品，生产单位产品所需资源A、B、C如下表所示，并且该工厂每生产一单位产品可获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少 产品和产品，才能使工厂获利最多？资源限量资源A11300资源B21400资源C01250第12页，本讲稿共28页 资源限量资源A11300资源B21400资源C01250 假如有另外一个工厂要求购买该厂的资源A、B、C，那么应该如何确定合理的价格呢？第13页，本讲稿共28页影子价格的经济含义影子价格的经济含义v影子价格是对现有资源实现最大效益时的一种影子价格是对现有资源实现最大效益时的一种估价；估价；v影子价格表明资源增加对总效益产生的影响；第14页，本讲

6、稿共28页3.2对偶单纯形法单纯形法回顾对偶单纯形法单纯形法回顾请用单纯形法求解下述线性规划问题：请用单纯形法求解下述线性规划问题：Max Z=2x1+x2 s.t.3x1+5x2 15 6x1+2x2 24 x1 ,x2 0第15页，本讲稿共28页对偶单纯形法对偶单纯形法v适用条件（1）线性规划问题初始单纯形表的b列中至少有一个基变量取值为负（2）在同一个表格的检验数行中，全部检验数非正第16页，本讲稿共28页步骤步骤v例：例：请用对偶单纯形法求解下述线性规划问题请用对偶单纯形法求解下述线性规划问题 Min f=3x1+2x2 s.t.3x1+x2 3 4x1+3x2 6 x1+3x2 2

7、x1 ,x2 0第17页，本讲稿共28页课堂练习课堂练习v请用对偶单纯形法求解下述线性规划问题请用对偶单纯形法求解下述线性规划问题 Min f=x1+x2 s.t.2x1+x2 4 x1+7x2 7 x1 ,x2 0第18页，本讲稿共28页课堂练习课堂练习Min Z=3x1+2 x2+x3+4x4 s.t.2x1+4x2+5x3+x4 0 3x1 -x2+7x3 -2x4 2 5x1+2x2+x3+6x4 15 x14 0v请用对偶单纯形法求解下述线性规划问题请用对偶单纯形法求解下述线性规划问题第19页，本讲稿共28页3.3灵敏度分析灵敏度分析v已知某企业计划生产3种产品A、B、C，其资源消耗

8、与利润如下表所示：ABC资源限量资源甲11112资源乙12220利润586v请问，该企业应该如何安排生产，才能使获利最大？第20页，本讲稿共28页3.3灵敏度分析灵敏度分析v背景：线性规划模型的cj、bi、aij 等系数是估计值：cj 市场条件；bi 资源投入量；aij 工艺条件；第21页，本讲稿共28页v任务：系数在什么范围内变化时，最优解（基）保持不变；若系数的变化使最优解发生变化，如何最简便的求得新的最优解；第22页，本讲稿共28页v目标函数系数目标函数系数 cj 的灵敏度分析的灵敏度分析在保证最优解的基变量不变的情况下，分析cj允许的变动范围cj 非基变量对应的目标函数系数变化，不影响

9、其它检验数；基变量对应的目标函数系数变化，影响所有非基变量检验数；第23页，本讲稿共28页v约束条件右端项约束条件右端项 bi 的灵敏度分析的灵敏度分析分析bi允许的变动范围bi 设 XB=B1b 是最优解，则有XB=B1b0；bi的变化不会影响检验数；bi 的变化量 bi 可能导致原最优解变为非可行解；第24页，本讲稿共28页v增加新变量的灵敏度分析增加新变量的灵敏度分析 ABC资源限量资源甲11112资源乙12220利润586v若新开发产品D，该产品需要消耗资源甲3个单位，乙2个单位，利润10元，请问，投产D是否有利？第25页，本讲稿共28页v增加新约束的灵敏度分析增加新约束的灵敏度分析

10、ABC资源限量资源甲11112资源乙12220利润586 若电力供应紧张，最多供应13个单位，而生产A、B、C每单位需要电力分别为2、1、3个单位，问该企业的生产方案是否需要改变？第26页，本讲稿共28页已知已知LP问题：问题：Max Z=3x1+6x2 s.t.-x1+2x2 12 x1+2x2 7 x1 ,x2 0(1)分别对c1，c2进行灵敏度分析；(2)对b1进行灵敏度分析；(3)当c2=2时，求新的最优解；(4)增加变量x5，c5=5，a15=2，a25=3，对最优解是否有影响？(5)增加一个约束条件：2x1+3x2 6，求新的最优解。课堂练习课堂练习第27页，本讲稿共28页第28页，本讲稿共28页