第三章线性规划问题的对偶与灵敏度分析精选文档.ppt

第三章第三章线性性规划划问题的的对偶偶与灵与灵敏度分析敏度分析本讲稿第一页，共二十八页线性规划的对偶问题线性规划的对偶问题第三章第三章 线性性规划划问题的的对偶偶与灵与灵敏度分析敏度分析1对偶单纯形法对偶单纯形法 2灵敏度分析灵敏度分析 3本讲稿第二页，共二十八页v某企业可生产A、B两种产品，需消耗煤、电、油三种资源。有关数据如下表所示：v试拟订使总收入最大的生产方案。A B资源限量资源限量煤煤电电油油9 44 5 3 10360200300单位产品价格单位产品价格 7 123.1对偶问题的提出对偶问题的提出本讲稿第三页，共二十八页A B资源限量资源限量煤煤电电油油9 44 5 3 10360200300单位产品价格单位产品价格 7 12 假若有另一家厂商提出要购买其煤、电、油全部资源，并希望花费尽量少，试建立购买者的线性规划模型。本讲稿第四页，共二十八页原问题与对偶问题的对应关系原问题与对偶问题的对应关系v对称形式：对称形式：原问题：对偶问题：本讲稿第五页，共二十八页原问题原问题对偶问题对偶问题目标max 型目标min 型有n 个变量有n 个约束有m 个约束有m 个变量目标函数系数约束条件右端常数约束条件右端常数目标函数系数约束系数矩阵约束系数矩阵的转置原问题与对偶问题的对应关系原问题与对偶问题的对应关系(一一)本讲稿第六页，共二十八页课堂练习课堂练习v请写出下述线性规划的对偶问题：请写出下述线性规划的对偶问题：Max Z=2x1+3 x2 s.t.x1+x2 350 x1 125 2x1+x2 600 x1 ,x2 0本讲稿第七页，共二十八页v非对称形式不具备对称形式的一对线性规划非对称形式不具备对称形式的一对线性规划称为非对称形式的对偶规划称为非对称形式的对偶规划：例：例：s.t 本讲稿第八页，共二十八页原问题原问题对偶问题对偶问题第j 个变量无限制第j 个约束为等式约束第i个约束为等式约束第i个变量无限制原问题与对偶问题的对应关系原问题与对偶问题的对应关系(二二)本讲稿第九页，共二十八页原问题原问题对偶问题对偶问题目标max 型目标min 型有n 个变量有n 个约束有m 个约束有m 个变量目标函数系数约束条件右端常数约束条件右端常数目标函数系数约束系数矩阵约束系数矩阵的转置原问题原问题对偶问题对偶问题第j 个变量无限制第j 个约束为等式约束第i个约束为等式约束第i个变量无限制关系关系(一一)关系关系(二二)本讲稿第十页，共二十八页课堂练习课堂练习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本讲稿第十一页，共二十八页对偶问题的经济解释资源的影子价格对偶问题的经济解释资源的影子价格 v某工厂在计划期内安排、两种产品，生产单位产品所需资源A、B、C如下表所示，并且该工厂每生产一单位产品可获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少 产品和产品，才能使工厂获利最多？资源限量资源A11300资源B21400资源C01250本讲稿第十二页，共二十八页 资源限量资源A11300资源B21400资源C01250 假如有另外一个工厂要求购买该厂的资源A、B、C，那么应该如何确定合理的价格呢？本讲稿第十三页，共二十八页影子价格的经济含义影子价格的经济含义v影子价格是对现有资源实现最大效益时的一种影子价格是对现有资源实现最大效益时的一种估价；估价；v影子价格表明资源增加对总效益产生的影响；影子价格表明资源增加对总效益产生的影响；本讲稿第十四页，共二十八页3.2对偶单纯形法单纯形法回顾对偶单纯形法单纯形法回顾请用单纯形法求解下述线性规划问题：请用单纯形法求解下述线性规划问题：Max Z=2x1+x2 s.t.3x1+5x2 15 6x1+2x2 24 x1 ,x2 0本讲稿第十五页，共二十八页对偶单纯形法对偶单纯形法v适用条件（1）线性规划问题初始单纯形表的b列中至少有一个基变量取值为负（2）在同一个表格的检验数行中，全部检验数非正本讲稿第十六页，共二十八页步骤步骤v例：例：请用对偶单纯形法求解下述线性规划问题请用对偶单纯形法求解下述线性规划问题 Min f=3x1+2x2 s.t.3x1+x2 3 4x1+3x2 6 x1+3x2 2 x1 ,x2 0本讲稿第十七页，共二十八页课堂练习课堂练习v请用对偶单纯形法求解下述线性规划问题请用对偶单纯形法求解下述线性规划问题 Min f=x1+x2 s.t.2x1+x2 4 x1+7x2 7 x1 ,x2 0本讲稿第十八页，共二十八页课堂练习课堂练习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请用对偶单纯形法求解下述线性规划问题请用对偶单纯形法求解下述线性规划问题本讲稿第十九页，共二十八页3.3灵敏度分析灵敏度分析v已知某企业计划生产3种产品A、B、C，其资源消耗与利润如下表所示：ABC资源限量资源甲11112资源乙12220利润586v请问，该企业应该如何安排生产，才能使获利最大？本讲稿第二十页，共二十八页3.3灵敏度分析灵敏度分析v背景：背景：线性规划模型的cj、bi、aij 等系数是估计值：cj 市场条件；bi 资源投入量；aij 工艺条件；本讲稿第二十一页，共二十八页v任务：系数在什么范围内变化时，最优解（基）保持不变；若系数的变化使最优解发生变化，如何最简便的求得新的最优解；本讲稿第二十二页，共二十八页v目标函数系数目标函数系数 cj 的灵敏度分析的灵敏度分析在保证最优解的基变量不变的情况下，分析cj允许的变动范围cj 非基变量对应的目标函数系数变化，不影响其它检验数；基变量对应的目标函数系数变化，影响所有非基变量检验数；本讲稿第二十三页，共二十八页v约束条件右端项约束条件右端项 bi 的灵敏度分析的灵敏度分析分析bi允许的变动范围bi 设 XB=B1b 是最优解，则有XB=B1b0；bi的变化不会影响检验数；bi 的变化量 bi 可能导致原最优解变为非可行解；本讲稿第二十四页，共二十八页v增加新变量的灵敏度分析增加新变量的灵敏度分析 ABC资源限量资源甲11112资源乙12220利润586v若新开发产品D，该产品需要消耗资源甲3个单位，乙2个单位，利润10元，请问，投产D是否有利？本讲稿第二十五页，共二十八页v增加新约束的灵敏度分析增加新约束的灵敏度分析 ABC资源限量资源甲11112资源乙12220利润586 若电力供应紧张，最多供应13个单位，而生产A、B、C每单位需要电力分别为2、1、3个单位，问该企业的生产方案是否需要改变？本讲稿第二十六页，共二十八页已知已知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，求新的最优解。课堂练习课堂练习本讲稿第二十七页，共二十八页本讲稿第二十八页，共二十八页