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

第三章线性规划问题的对偶与灵敏度分析第一页，共二十八页，2022年，8月28日线性规划的对偶问题第三章线性规划问题的对偶与灵敏度分析1对偶单纯形法

2灵敏度分析

3第二页，共二十八页，2022年，8月28日某企业可生产A、B两种产品，需消耗煤、电、油三种资源。有关数据如下表所示：试拟订使总收入最大的生产方案。AB资源限量煤电油9445310360200300单位产品价格7123.1对偶问题的提出第三页，共二十八页，2022年，8月28日AB资源限量煤电油9445310360200300单位产品价格712假若有另一家厂商提出要购买其煤、电、油全部资源，并希望花费尽量少，试建立购买者的线性规划模型。

第四页，共二十八页，2022年，8月28日原问题与对偶问题的对应关系对称形式：原问题：

对偶问题：

第五页，共二十八页，2022年，8月28日原问题对偶问题目标max型目标min型有n个变量有n个约束有m个约束有m个变量目标函数系数约束条件右端常数约束条件右端常数目标函数系数约束系数矩阵约束系数矩阵的转置原问题与对偶问题的对应关系(一)第六页，共二十八页，2022年，8月28日课堂练习请写出下述线性规划的对偶问题：MaxZ=2x1+3x2s.t.x1+x2

≤350

x1≤1252x1+x2≤600x1,x2≥0第七页，共二十八页，2022年，8月28日非对称形式－不具备对称形式的一对线性规划称为非对称形式的对偶规划：例：s.t

第八页，共二十八页，2022年，8月28日原问题对偶问题第j个变量无限制第j个约束为等式约束第i个约束为等式约束第i个变量无限制原问题与对偶问题的对应关系(二)第九页，共二十八页，2022年，8月28日原问题对偶问题目标max型目标min型有n个变量有n个约束有m个约束有m个变量目标函数系数约束条件右端常数约束条件右端常数目标函数系数约束系数矩阵约束系数矩阵的转置原问题对偶问题第j个变量无限制第j个约束为等式约束第i个约束为等式约束第i个变量无限制关系(一)关系(二)第十页，共二十八页，2022年，8月28日课堂练习请写出下述线性规划的对偶问题：MaxZ=4x1+5x2+2x3s.t.3x1+2x2+x3

≤204x1-

3x2

+3x3

≥

10x1+x2

+2x3=5x1,x3≥0第十一页，共二十八页，2022年，8月28日对偶问题的经济解释－资源的影子价格

某工厂在计划期内安排Ⅰ、Ⅱ两种产品，生产单位产品所需资源A、B、C如下表所示，并且该工厂每生产一单位产品Ⅰ可获利50元，每生产一单位产品Ⅱ可获利100元，问工厂应分别生产多少产品和Ⅱ产品，才能使工厂获利最多？

ⅠⅡ资源限量资源A11300资源B21400资源C01250第十二页，共二十八页，2022年，8月28日

ⅠⅡ资源限量资源A11300资源B21400资源C01250假如有另外一个工厂要求购买该厂的资源A、B、C，那么应该如何确定合理的价格呢？第十三页，共二十八页，2022年，8月28日影子价格的经济含义影子价格是对现有资源实现最大效益时的一种估价；影子价格表明资源增加对总效益产生的影响；第十四页，共二十八页，2022年，8月28日3.2对偶单纯形法－单纯形法回顾请用单纯形法求解下述线性规划问题：MaxZ=2x1+x2s.t.3x1+5x2

≤156x1

+

2x2

≤

24x1,x2≥0第十五页，共二十八页，2022年，8月28日对偶单纯形法适用条件（1）线性规划问题初始单纯形表的b列中至少有一个基变量取值为负（2）在同一个表格的检验数行中，全部检验数非正第十六页，共二十八页，2022年，8月28日步骤例：请用对偶单纯形法求解下述线性规划问题Minf=3x1+2x2s.t.3x1+x2

≥34x1

+

3x2

≥

6

x1

+

3x2

≥

2x1,x2≥0第十七页，共二十八页，2022年，8月28日课堂练习请用对偶单纯形法求解下述线性规划问题Minf=x1+x2s.t.2x1+x2

≥4

x1

+

7x2

≥

7x1,x2≥0第十八页，共二十八页，2022年，8月28日课堂练习MinZ=3x1+2x2+

x3+4x4

s.t.2x1+4x2+5x3+x4

≥03x1-x2

+7x3-2x4

≥

25x1+2x2

+x3

+6x4

≥15x1~4≥0请用对偶单纯形法求解下述线性规划问题第十九页，共二十八页，2022年，8月28日3.3灵敏度分析已知某企业计划生产3种产品A、B、C，其资源消耗与利润如下表所示：

ABC资源限量资源甲11112资源乙12220利润586请问，该企业应该如何安排生产，才能使获利最大？第二十页，共二十八页，2022年，8月28日3.3灵敏度分析背景：线性规划模型的cj

、

bi

、

aij等系数是估计值：cj－市场条件；

bi－资源投入量；aij－工艺条件；第二十一页，共二十八页，2022年，8月28日任务：－系数在什么范围内变化时，最优解（基）保持不变；－若系数的变化使最优解发生变化，如何最简便的求得新的最优解；第二十二页，共二十八页，2022年，8月28日目标函数系数cj的灵敏度分析－在保证最优解的基变量不变的情况下，分析cj允许的变动范围cj

非基变量对应的目标函数系数变化，不影响其它检验数；基变量对应的目标函数系数变化，影响所有非基变量检验数；第二十三页，共二十八页，2022年，8月28日约束条件右端项

bi

的灵敏度分析－分析bi允许的变动范围bi

设XB=B1b是最优解，则有XB=B1b0；bi的变化不会影响检验数；bi

的变化量bi

可能导致原最优解变为非可行解；第二十四页，共二十八页，2022年，8月28日增加新变量的灵敏度分析

ABC资源限量资源甲11112资源乙12220利润586若新开发产品D，该产品需要消耗资源甲3个单位，乙2个单位，利润10元，请问，投产D是否有利？第二十五页，共二十八页，2022年，8月28日增加新约束的灵敏度分析

ABC资源限量资源甲11112资源乙12220利润586若电力供应紧张，最多供应13个单位，而生产A、B、C每单位需要电力分别为2、1、3个单位，问该企业的生产方案是否需要改变？第二十六页，共二十八页，2022年，8月28日已知LP问题：

MaxZ=3x1+6x2s.t.-x1+2x2

≤12

x1

+

2x2

≤

7x1,x2≥0(1)分别对c1，c