[理学]Chapter02线性规划的对偶理论.ppt

黑龙江大学数学科学学院 信息与计算数学系 All rights reserved,第2章 线性规划的对偶理论,2011年3月,2,2019/4/14,1 对偶问题的提出,设备租赁问题 假定有四海机器厂想扩大生产规模想租赁常山机器厂的三种设备，常山方面应如何决定出租价格呢？ 设常山机器厂对三种设备的出租定价分别为y1,y2,y3元/小时。 常山机器厂的考虑： 不能比自己组织生产获利少(约束条件)； 四海机器厂的考虑： 租金尽可能少(目标函数),3,2019/4/14,租赁问题形成的新规划模型,写出原问题和新问题的约束矩阵，右端项和目标函数系数,问题：原问题的约束矩阵等和对偶问题的之间有什么关系？,4,2019/4/14,1 原问题和对偶问题之间的关系,原问题和对偶问题A, b 和 c 的对应关系： A AT, bT c , cT b ; 原问题是极大化问题，对偶问题是极小化问题； 原问题 vs. 对偶问题：约束条件个数 = 决策变量个数，反之依然； 原问题的约束为“”号，对偶问题的约束为“”号。,5,2019/4/14,对称形式的对偶规划,定义2.1 原问题 (LP) 的对偶问题为（DP） 其中 y = (y1,y2,ym)T 为对偶问题的决策变量，称(LP)为标准形式原问题。 注：在对偶理论中，一般不再要求x和 b 非负。,例2.1 求下述问题的对偶问题。,标准原问题,问题：请某位同学上黑板写下对偶问题 (4)？,6,2019/4/14,对偶问题的对偶问题为原问题,定理2.1 对偶问题 (DP) 的对偶问题为（LP）,证明思路：将对偶问题转化为标准形式原问题，即 “max + 约束” 形式，再用定义求解。,7,2019/4/14,两个推论 非标准原问题的对偶问题,难点记住：对偶问题约束的符号取决于原问题的变量符号； 对偶问题的变量符号取决于原问题的约束符号。,8,2019/4/14,约束为“”的原问题的对偶问题,9,2019/4/14,混合形式原问题的对偶问题(书中P56例2),设对偶问题的决策变量为 y = (y1,y2,y3)T， 对偶问题目标函数，约束矩阵，右端项容易写出；关键是约束符号和变量符号问题。 第1约束：min + x1 0, 如果x10, 对偶问题约束该取“”，此处相反取 “”； 第2约束取“=”；第3约束为 min + x3 0，约束取“”； 对偶问题第1变量y1: 由 min+第1约束“” 决定，y1 0 ;变量y2: 由 min+第2约束“” 决定，y2 0 ; 原问题第3个等式决定了变量y3取值无限制。,10,2019/4/14,3 对偶问题的基本性质(书P58),始终规定 原问题 (LP) 对偶问题为（DP） 其中 A为m n 阶约束矩阵，x和y 分别为原问题和对偶问题的决策变量。,11,2019/4/14,强对偶定理(书P58，性质3,性质4),原问题 (LP) 对偶问题为（DP） 其中 A为m n 阶约束矩阵，x和y 分别为原问题和对偶问题的决策变量。,12,2019/4/14,互补松紧定理(书P59，性质5),原问题 (LP) 对偶问题为（DP） 其中 A为m n 阶约束矩阵，x和y 分别为原问题和对偶问题的决策变量。,13,2019/4/14,松紧定理的应用,14,2019/4/14,基解互补原理(书P59，性质6),原问题 (LP) 对偶问题为（DP） 其中 A为m n 阶约束矩阵，x和y 分别为原问题和对偶问题的决策变量。,推论2.4 (LP)和(DP)存在一对互补的（最优）基解： 原问题的剩余变量对应对偶问题的变量，对偶问题的松弛变量对应原问题的变量 原问题解的基变量（非基变量）对应对偶问题的非基变量（基变量) 互补的基解对应原问题和对偶问题的目标函数值相同 推论2.4的应用 如果原问题不方便求解，求其对偶问题最优解，利用对偶问题最终单纯形表的检验数行获得原问题最优解。,15,2019/4/14,基解互补应用的例子(书P60.例3),问题1：原问题和对偶问题哪个更容易求解？为什么？ 问题2：不容易求解的问题用什么方法求解？,16,2019/4/14,两个问题最终单纯形表(注意对应关系),问题3：这个最优解在原最终单纯形表中的什么位置？,问题4：这里的B和B1分别是什么？,17,2019/4/14,4 影子价格,bi : 第i种资源的拥有量； yi : 第i种资源的单位估价，不是市场价格，是生产贡献估价，称为影子价格(shadow price)；影子价格是边际价格。,18,2019/4/14,影子价格的经济学含义,影子价格和资源利用的关系 (1) 若Ai x 0, 则Ai x = bi ; 结论：资源消耗完毕，影子价格大于零；未充分利用，影子价格为0,单纯法中检验数的含义：,各个变量的含义 cj : 第j种产品的产值； aijyi : 生产单位产品消耗各种该资源的影子价格的总和，即产品的隐含成本； 检验数的含义(三种情况) 影子价格的应用(书P63),19,2019/4/14,5 对偶单纯形法,单纯形法的思想： 保持原问题是可行解，在目标函数值不减的条件下迭代求解，直至检验数满足最优性标准。 原问题 vs. 对偶问题: 根据基解互补原理，原问题检验数非正时，其对偶问题达到可行解，此时相应解为两个问题的最优解。 对偶单纯形法的基本思想： 保持对偶问题为可行解(检验数非正，此时原问题解未必可行)的基础上，迭代求解(目标函数值不增)，当原问题解变为可行解时，即达到最优。,20,2019/4/14,对偶单纯形算法的例子(书P65.例5),化标准形式： (1) 目标函数最大化？ (2) 约束的处理？（要求获得初始单位阵基）,对偶单纯形算法的要求：保持对偶问题可行(min + cj 0)。,21,2019/4/14,对偶单纯形算法主元的确定,先确定离基变量 br = minbi | bi 0, 则对应xr离基。 再确定进基变量 = min(cjzj)/arj | arj 0 = (cszs)/ars ,则xs进基。 在中，的选择保证了对偶问题一定是可行的。 见黑板论证。,22,2019/4/14,6 灵敏度分析,什么是灵敏度分析？ 对(LP)问题，aij,bi,cj都是可变的。灵敏度分析研究的是：当这些参数中的一个或几个发生变化时，问题的最优解会有什么变化；或者这些参数在多大范围内变化时，问题的最优解不变。,I = B1B,B1N,B1b,B= 0,N= cN cBB1N,cBB1b,23,2019/4/14,6.1 c 变化的灵敏度分析,某个非基变量xj对应的cj发生变化，cjcj： 只有检验数j发生变化，重新计算检验数j : 如果j 0,则原问题的最优解和最优值不变。 如果j 0,则xj进基继续迭代。 如果某个基变量xi系数ci发生变化, cici ： 所有检验数都发生变化，目标函数值也会改变；此时需重新计算所有检验数，依情况考虑是否继续迭代。 检验数 j =cj cBB1pj ci aij 目标函数值 z = z + ci bi 对和的分析见黑板。,24,2019/4/14,例6.1(c的灵敏度分析),考虑如下问题： (1) 把c1= 1改为 c1 = 4，求新问题最优解； (2) c2在什么范围内变化时，原问题最优解仍是新问题的最优解？,25,2019/4/14,例6.1 分析和求解,（1）x1是非基变量，只有1发生变化， c1 =1, c1 =4, c1=5， 1 = 1+5 = 2 0 ,需要继续迭代求解,(2) x2是基变量，系数由2变为c2 ， c2=c2-2,据(6.1) 2 = 2= 0 1 = 1 c2 1 = 1c2 3 = 3 c2 1 = 1c2 4 = 4 c2 1 = c2 所有j 0，得c21 最优解不变，最优值呢？,问题：新问题的最优解和最优值什么？,26,2019/4/14,6.2 b 变化的灵敏度分析,若右端项b变为b,此时xB= B1b和 z=cBB1b都有改变： 如果B1b 0，最优基不变，重新计算最优解和最优值即可。 如果B1b 0，说明B1b中有负的分量，当前解不是不行的，但是对偶可行的(为什么？)，修改右端列，代以B1b，利用对偶单纯形法继续求解。,27,2019/4/14,例6.2 b的灵敏度分析,问题：请问最优基B是什么？ B1是什么？( 5 ),28,2019/4/14,例 6.2 分析和求解,(1) B1已知，重新计算xB= B1b即可： B1b = (1,4,4)T 0, 现行解仍是可行解，又对偶可行的，故当前基解为最优解， x*=(1,0,4), z* = 15. 问题：最优解和最优值分别是什么？,(2) 计算 B1b = (-1,5,2)T ，b10,但是所有检验数非正，利用对偶单纯形法继续求解即可。 x*=(0,0,3/2)T, z* = 6.,29,2019/4/14,6.3 A 变化的灵敏度分析,原约束矩阵A中pj元素aij发生变化: 非基列pj发生变化，重新计算j =cj cBB1pj (1) 若j 0,则原问题最优解和最有值不变； (2) 若j 0,则xj进基继续迭代。 基列pi发生变化，变为pi (1) 若pi 和原基中其余各列线性无关不易判断，此时可在原最优表中增加一列pn+1 = B1pi ,令cn+1= ci, 原ci = M充分小，在原最优表基础上继续迭代计算不作为大纲要求。 (2) 若pi 和原基中其余各列线性相关，一般需要重新计算不作为大纲要求。 增加一个变量的分析(书P69) 类似和的分析，最优表中先增加一列pn+1 = B1pn+1,再重新计算检验数，根据检验数的符号决定是否继续迭代。,30,2019/4/14,例6.3 增加一列的灵敏度分析（书P70 例8）,在第一章的例子中(本幻灯片第二页)，若增加一个变量，比如x6, c6 =4, p6=(2,4,5)T,分析最优解的变化最优解如右所示。,分析和求解： (1) B已知，计算B1p6 增加到最优表中； (2) 计算检验数c6-z6，决定是否继续迭代。,31,2019/4/14,6.4 增加约束的灵敏度分析,设原问题约束为Ax=b，x0, A为mn矩阵，秩(A)=m . 现增加一个约束条件 x bm+1, 为n维行向量，此时： 若原问题最优解x*满足新的约束条件，那么x*也是新问题的最优解证明略。 若x* bm+1,说明x*不是新问题的可行解，需要重新构造新基B(见黑板),这种情况下， x*是对偶可行的，可利用对偶单纯形法求解(约束写成BxB+ NxN+xn+1 = bm+1)： 结论1：新约束添加消元后，原变量检验数j(1jn)不变， n+1=0 结论2：消元后bm+1 位置变为： bm+1 BB1b 0,故可以利用对偶单纯形法处理。 新基B的确定，结论1和结论2见黑板推导。,32,2019/4/14,例6.4 增加一个约束的灵敏度分析（书P71 例9）,在第一章的例子中(本幻灯片第二页)，若增加一个约束条件3x1+2x214,分析最优解的变化。,分析和求解： (1)原最优解x*=(3,3)T, 不满足新约束； (2)新约束化为等式加入到最终单纯形表中; (3)把新约束的B部分消元为0，检验数部分不必重新计算。,33,2019/4/14,例6.4 续，b40，用对偶单纯法求解,新问题最优解：x*=(8/3,3)T, z*=43/3,34,2019/4/14,7 参数线性规划,灵敏度分析研究的内容 参数aij,bi,cj离散变化时，最优解和最优值的变化情况 最优解或最优基不变的情况下，参数aij,bi,cj的变化区间 参数线性规划的研究内容和要求 研究内容：引进新参数，把原参数写成与的线性和的形式，即bibi+di 以及cjcj+dj ,研究当连续变化时, 问题的最优(解)值z=z()和之间的关系。 要求： z=z() 是的线性函数，因此一般要求b和c不能同时含参数，一般也不研究A的变化问题：为什么这样要求？。 z=z()一般为 +的分段线性函数。 参数线性规划和灵敏度