第三章 线性规划问题的对偶与灵敏度分析

运筹学－Operation’sResearch北京理工大学珠海学院吴浩然线性规划的对偶问题第三章线性规划问题的对偶与灵敏度分析1对偶单纯形法2灵敏度分析3某企业可生产A、B两种产品，需消耗煤、电、油三种资源。有关数据如下表所示：试拟订使总收入最大的生产方案。AB资源限量煤电油9445310360200300单位产品价格7123.1对偶问题的提出AB资源限量煤电油9445310360200300单位产品价格712假若有另一家厂商提出要购买其煤、电、油全部资源，并希望花费尽量少，试建立购买者的线性规划模型。原问题与对偶问题的对应关系对称形式：0,,maxxbAxcxz0..minycyAybfTTT原问题：对偶问题：原问题对偶问题目标max型目标min型有n个变量有n个约束有m个约束有m个变量目标函数系数约束条件右端常数约束条件右端常数目标函数系数约束系数矩阵约束系数矩阵的转置原问题与对偶问题的对应关系(一)课堂练习请写出下述线性规划的对偶问题：MaxZ=2x1+3x2s.t.x1+x2≤350x1≤1252x1+x2≤600x1,x2≥0非对称形式－不具备对称形式的一对线性规划称为非对称形式的对偶规划：例：321643maxxxxz0,,20035,10046,44063232321321321xxxxxxxxxxxs.t原问题对偶问题第j个变量无限制第j个约束为等式约束第i个约束为等式约束第i个变量无限制原问题与对偶问题的对应关系(二)原问题对偶问题目标max型目标min型有n个变量有n个约束有m个约束有m个变量目标函数系数约束条件右端常数约束条件右端常数目标函数系数约束系数矩阵约束系数矩阵的转置原问题对偶问题第j个变量无限制第j个约束为等式约束第i个约束为等式约束第i个变量无限制关系(一)关系(二)课堂练习请写出下述线性规划的对偶问题：MaxZ=4x1+5x2+2x3s.t.3x1+2x2+x3≤204x1-3x2+3x3≥10x1+x2+2x3=5x1,x3≥0对偶问题的经济解释－资源的影子价格某工厂在计划期内安排Ⅰ、Ⅱ两种产品，生产单位产品所需资源A、B、C如下表所示，并且该工厂每生产一单位产品Ⅰ可获利50元，每生产一单位产品Ⅱ可获利100元，问工厂应分别生产多少产品和Ⅱ产品，才能使工厂获利最多？ⅠⅡ资源限量资源A11300资源B21400资源C01250ⅠⅡ资源限量资源A11300资源B21400资源C01250假如有另外一个工厂要求购买该厂的资源A、B、C，那么应该如何确定合理的价格呢？影子价格的经济含义影子价格是对现有资源实现最大效益时的一种估价；影子价格表明资源增加对总效益产生的影响；3.2对偶单纯形法－单纯形法回顾请用单纯形法求解下述线性规划问题：MaxZ=2x1+x2s.t.3x1+5x2≤156x1+2x2≤24x1,x2≥0对偶单纯形法适用条件（1）线性规划问题初始单纯形表的b列中至少有一个基变量取值为负（2）在同一个表格的检验数行中，全部检验数非正步骤例：请用对偶单纯形法求解下述线性规划问题Minf=3x1+2x2s.t.3x1+x2≥34x1+3x2≥6x1+3x2≥2x1,x2≥0课堂练习请用对偶单纯形法求解下述线性规划问题Minf=x1+x2s.t.2x1+x2≥4x1+7x2≥7x1,x2≥0课堂练习MinZ=3x1+2x2+x3+4x4s.t.2x1+4x2+5x3+x4≥03x1-x2+7x3-2x4≥25x1+2x2+x3+6x4≥15x1~4≥0请用对偶单纯形法求解下述线性规划问题3.3灵敏度分析已知某企业计划生产3种产品A、B、C，其资源消耗与利润如下表所示：ABC资源限量资源甲11112资源乙12220利润586请问，该企业应该如何安排生产，才能使获利最大？3.3灵敏度分析背景：线性规划模型的cj、bi、aij等系数是估计值：cj－市场条件；bi－资源投入量；aij－工艺条件；任务：－系数在什么范围内变化时，最优解（基）保持不变；－若系数的变化使最优解发生变化，如何最简便的求得新的最优解；目标函数系数cj的灵敏度分析－在保证最优解的基变量不变的情况下，分析cj允许的变动范围cj–非基变量对应的目标函数系数变化，不影响其它检验数；–基变量对应的目标函数系数变化，影响所有非基变量检验数；约束条件右端项bi的灵敏度分析－分析bi允许的变动范围bi•设XB=B1b是最优解，则有XB=B1b0；•bi的变化不会影响检验数；•bi的变化量bi可能导致原最优解变为非可行解；增加新变量的灵敏度分析ABC资源限量资源甲11112资源乙12220利润586若新开发产品D，该产品需要消耗资源甲3个单位，乙2个单位，利润10元，请问，投产D是否有利？增加新约束的灵敏度分析ABC资源限量资源甲11112资源乙12220利润586若电力供应紧张，最多供应13个单位，而生产A、B、C每单位需要电力分别为2、1、3个单位，问该企业的生产方案是否需要改变？已知LP问题：MaxZ=3x1+6x2s.t.-x1+2x2≤12x1+2x2≤7x1,x2≥0(1)分别对c1，c2进行灵敏度分析；(2)对b1进行灵敏度分析；(3)当c2=2时，求新的最优解；(4)增加变量x5，c5=5，a15=2，a25=3，对最优解是否有影响？(5)增加一个约束条件：2x1+3x2≤6，求新的最优解。课堂练习