2对偶理论与灵敏度分析.ppt

1、1,第 2章线性规划的对偶理论,要求： 了解LP对偶问题的实际背景 了解对偶问题的建立规则与基本性质 掌握对偶最优解的计算及其经济解释 掌握LP的灵敏度分析 理解计算机输出的影子价格与灵敏度分析的内容,2,1 对偶问题,对偶问题的提出 例1：生产A、B两产品的情况如下表。现在销路不畅，可以将所有资源出租或外卖，问我们的价格底线是什么？,换个角度审视生产计划问题,3,对偶模型,设每个工时收费y1元，设备每台时收费用y2元，单位原材料收费y3元。 （用于生产第i种产品的资源转让收益不小于生产该种产品时获得的利润又最富有竞争力（资源的总价格最低） ） Min w=360y1+200y2+300y3

2、9y1+4y2+3y3 70 s.t. 4y1+5y2+10y3 120 y1，y2，y3 0,4,原问题与对偶问题之比较,原问题： 对偶问题： Max z=70 x1+120 x2 Min w=360y1+200y2+300y3 9x1+4x2360 9y1+4y2+3y3 70 4x1+5x2 200 4y1+5y2+10y3 120 3x1+10 x2 300 y1 0, y2 0, y3 0 x10 x20,s.t.,s.t.,5,对偶规则,原问题一般模型： 对偶问题一般模型： Max z=CX min w=bY AX b AYC X 0 Y 0,s.t.,s.t.,6,对偶规则,原问

3、题有m个约束条件，对偶问题有m个变量 原问题有n个变量，对偶问题有n个约束条件 原问题的价值系数对应对偶问题的右端项 原问题的右端项对应对偶问题的价值系数 原问题的系数矩阵转置后为对偶问题系数矩阵 原问题的约束条件与对偶问题方向相反 原问题与对偶问题优化方向相反,7,对偶规则,.,8,对偶规则简捷记法,原问题标准则对偶问题标准 原问题不标准则对偶问题不标准 例题2 max w=7y1+4y2-2y3 min z=3x1+2x2-6x3+x5 2y1+ y2- y3 3 2x1+x2-4x3+x4+3x5 7 y1 +3y3 2 x1+ 2x3 -x4 4 -4y1+ 2y2 -6 -x1+3x

4、2 -x4+ x5 =-2 y1 -y2 -y3 0 x1，x2，x3 0; 3y1 +y3=1 x4 0; x5无约束 y1 0，y2 0， y3 无约束,9,3对偶问题的基本性质,对称性：对偶问题的对偶问题是原问题 弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值,均有可行解，分别为 和 ，则C b。,10,无界性：原问题无界，对偶问题无可行解 对偶定理（强对偶性）：若一个问题有最优解，则另一问题也有最优解，且最优目标函数值相等。若原问题最优基为B，则其对偶问题最优解Y*=CBB-1,3对偶问题的基本性质（续）,证,11,主对偶定理：若原始问题和对偶问

5、题两者均可行，则两者均有最优解，且此时目标函数值相同。,互补松弛性：将原问题和对偶问题的最优解分别带入各自的线性规划模型中时，存在如下关系：,12,互补松弛性：将原问题和对偶问题的基最优解分别带入各自的线性规划模型中时，存在如下关系：,3对偶问题的基本性质（续）,13,4对偶最优解的经济解释影子价格,z = w=CX=Yb Z/ b=(Yb)=Y z =Yb= yibi的意义：Y是检验数的相反数。在Y确定的前提下，每增加一个单位的i种资源，对目标函数的贡献。 影子价格所含有的信息： 1、资源紧缺状况 2、确定资源转让基价 3、取得紧缺资源的代价 参见：P61,14,39/5,0,1,0,-2/

6、5,240,5/2,0,0,1,-1/2,34,0,0,50,0,-12, ,例1的求解,15, ,0,0,1,-78/5,29/5,84,0,1,0,-3/25,4/25,24,0,0,0,-68/5,-26/5,换基迭代,x3,x1,x2,16,例1中的影子价格：y1= 0，第一种资源过剩；y2=13.6，设备台时最紧张，每增加一个台时， 利润增加13.6元；y3=5.2 当市场价格低于影子价格时，可以买进这种资源，扩大生产；当市场价格高于影子价格时，宁愿卖出这种资源，更为划算。 当影子价格为零时，说明该资源不紧缺。若再增加这种资源也不会带来任何经济效益。,4影子价格约束条件所付出的代价,

7、17,5 对偶单纯形法,单纯形法：初始可行基（对应一个初始基本可行解）迭代另一个可行基（对应另一个基本可行解），直至所有检验数0为止。 即 在保持原始可行的前提下(b列保持0)， 通过逐步迭代实现对偶可行(实现检验数行0)。,对偶单纯形法： （换个角度考虑LP求解过程）保持对偶可行的前提下（检验数行保持0） ，通过逐步迭代实现原始可行（实现b列0，从非可行解变成可行解）。,18,习题1.7(b), ,-3/2,-1,0,-1/2,0,19, ,有无穷多最优解，最优值为7,0,5/3,1,-1/2,1/6,3,0,0,0,-1/2,-1/2,x3,x1,20,6 灵敏度分析,什麽是灵敏度分析？

8、研究线性规划模型某些参数或限制量的变化对最优解的影响及其程度的分析过程称为灵敏度分析（或优化后分析）。 灵敏度分析的内容： 目标函数的系数变化对最优解的影响 约束方程右端系数变化对最优解的影响 约束方程组系数矩阵变化对最优解的影响,21,5 灵敏度分析（续）,为什么要进行灵敏度分析？ 灵敏度分析的两把尺子： =CN-CBB-1N 0； xB= B-1b 0 价值系数的灵敏度分析 Cj变化到什么程度可以保持最优解不变？用 （参看P66） 例题6： C1=2, C2=3,22,s.t.,最优表,模型,23,由,得,（注意基变量的顺序）,即当,对C1,时，最优解不变。,24,由,得,即当,对C2,时

9、，最优解不变。,25,灵敏度分析（续）,右端项的灵敏度分析： bi变化到什么程度可以保持最优基不变？用尺子 xB= B-1b 0 例7：在最优表中读出（思考：B =?）,26,由,得,即当,类似可得b2、b3的变化范围,对b1,时，最优基不变。,27,系数阵A的元素发生变化,增加1个新变量：相当于系数阵A增加1列 如开发出一种新产品，已知其有关工艺参数（或消耗的资源量）和单位产品利润，设该种产品的产量为xk，则ck和Pk已知，需要进行“是否投产”的决策。 先算检验数k =Ck-CBB-1Pk 若算出的k 0 有利可图，将P6左乘B-1，加入到末表之中，继续迭代，直到求得最优解。,28,0,4,1,0,4,1,1, ,29,0,1,1/2,-1/4,0,0,2,0,0,-1/2,-1/4,-2/5,0,故新的最优解为x1=3，x2=2，x6=1，z*=16,30,增加1个约束条件：相当于系数阵A增加1行,首先将原最优解代入新增约束检查是否满足？是，则说明新增约束不影响最优解。否则再作下面的讨论： 将新增约束标准化，添加到原最优表格中（相当于约束矩阵新增1行）； 进行规格化处理用矩阵的行变换将当前基变成单位阵； 用适当方法（通常是对偶单纯形法）进行迭代求出新的最优解。,系数矩阵