《《最优化方法》第三讲 对偶规划与灵敏度分析课件》由会员分享，可在线阅读，更多相关《《最优化方法》第三讲 对偶规划与灵敏度分析课件（56页珍藏版）》请在金锄头文库上搜索。
1、2020/10/14,最优化方法,1,第三讲 对偶规划与灵敏度分析,对偶线性规划的概念 对偶问题的基本性质 对偶最优解的经济解释影子价格 对偶单纯形法 灵敏度分析,2020/10/14,最优化方法,2,对偶原理,对偶问题概念： 任何一个线性规划问题都有一个与之相对应 的线性规划问题，如果前者称为原始问题，后者 就称为“对偶”问题。 对偶问题是对原问题从另一角度进行的描述 其最优解与原问题的最优解有着密切的联系，在 求得一个线性规划最优解的同时也就得到对偶线 性规划的最优解，反之亦然。 对偶理论就是研究线性规划及其对偶问题的 理论，是线性规划理论的重要内容之一。,2020/10/14,最优化方法
2、,3,1.对偶问题的提出 例1、某工厂生产甲,乙两种产品，这两种产品需要在A,B,C三种不同设备上加工。每种甲、乙产品在不同设备上加工所需的台时，它们销售后所能获得的利润，以及这三种设备在计划期内能提供的有限台时数见下表。试问如何安排生产计划，即甲,乙两种产品各生产多少吨，可使该厂所获得利润达到最大。,对偶线性规划的概念,2020/10/14,最优化方法,4,用图解法或单纯形法可求得最优解 (元) 即在计划期内甲产品生产4/3 吨，乙产品生产8吨，可以使总利润达到最大，为 元。,假设计划期内甲乙两种产品各生产x1 x2 吨，,2020/10/14,最优化方法,5,例1 现在从另一个角度来考虑该
3、工厂的生产问题: 假设该厂的决策者打算不再自己生产甲,乙产品，而是把各种设备的有限台时数租让给其他工厂使用，这时工厂的决策者应该如何确定各种设备的租价。 设 y1 y2 y3 分别为设备A，B，C每台时的租价， 约束条件：把设备租出去所获得的租金不应低于利用这些设备自行生产所获得的利润,目标函数：所获租金总额最小,2020/10/14,最优化方法,6,由此可得两个对称的线性规划：,矩阵形式：,2020/10/14,最优化方法,7,对偶问题的定义,2020/10/14,最优化方法,8,对偶的定义的图解,原始问题 min z=CX s.t.AXb X 0,对偶问题 max W=bTY s.t. A
4、TYC Y 0,min,b,A,C,C,AT,bT,max,m,n,m,n,2020/10/14,最优化方法,9,对偶问题的特点 （1）目标函数在一个问题中是求最大值在另一问题中则为求最小值 （2）一个问题中目标函数的系数是另一个问题中约束条件的右端项 （3）一个问题中的约束条件个数等于另一个问题中的变量数 （4）原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵,2020/10/14,最优化方法,10,由于任何一个等式约束都可以用两个不等式约束等价地表示，所以标准形线性规划问题可等价表示为：,考虑一个标准形式的线性规划问题,线性规划问题标准型的对偶问题,它的对偶规划为：,2020/10
5、/14,最优化方法,11,对偶线性规划的求法,从任何一个线性规划出发，都可以求出相应的对偶规划，在实际求解过程中，通常不通过求标准型，而是利用如下原始对偶表：,2020/10/14,最优化方法,12,解： 原问题目标最大，对偶问题目标最小。 设对于原问题4个约束条件的对偶变量分别为 y1 y2 y3 y4 ; 由4个约束条件的类型，可知4个对偶变量分别为0，0，0和无约束； 原问题有3个决策变量x1 x2 x3 ，因此对偶规划有3个约束条件，由3个决策变量的符号，可知对偶规划3个约束条件的类型分别为，=。 由此可得上述问题的对偶规划DP.,例2 写出下列线性规划的对偶问题,2020/10/14
6、,最优化方法,13,练习：写出对偶规划。,2020/10/14,最优化方法,14,2020/10/14,最优化方法,15,2020/10/14,最优化方法,16,1：对偶问题的对偶是原问题。 证明：,对偶问题的基本性质,2020/10/14,最优化方法,17,对偶定理,弱对偶性（可行解的目标函数值之间的关系） 设X、Y分别是原始问题和对偶问题的可行解 f=CTX YTAX YTb=z,2020/10/14,最优化方法,18,最优性,无界性,如果原问题（对偶问题）具有无界解， 则其对偶问题（原问题）无可行解。,2020/10/14,最优化方法,19,推论1：若原问题有一个对应于基的最优解，那么此
7、时的单纯形乘子Y=CBB-1是对偶问题的一个最优解。 根据这个推论我们可以在原问题的最优单纯形表中直接找到对偶问题的最优解，即剩余变量检验数的相反数CBB-1（松弛变量的检验数）,强对偶性 如果原问题有最优解，那么对偶问题也有最优解，而且目标函数 值相等。,2020/10/14,最优化方法,20,在线性规划问题的最优解中，,如果对应某一约束条件的对偶变量值为非零，,则该约束条件取严格等式；,反之如果约束条件取严格不等式，,互补松弛性,则其对应的对偶变量一定为零。,即,2020/10/14,最优化方法,21,利用单纯形表求例1原问题的最优解，并由最优单纯形表推出对偶问题的最优解。,解：原问题线性
8、规划模型为,引入松弛变量x3 x4 x5，化为标准形得:,2020/10/14,最优化方法,22,1 0 -2/3 0 1/3,4/3,x1,-32,0 0 1/3 1 -2/3,3/4,X4,0,4/2,1 0 0 2 -1,4,x1,-32,4/3,0 0 1 3 -2,4,X3,0,8/4/5,1 4/5 0 1/5 0,8,x1,-32,12/8/5,0 8/5 1 -3/5 0,12,X3,0,40/5,5 4 0 1 0,40,x4,0,36/3,3 4 1 0 0,36,X3,0,0 0 7/6 0 19/6,Z,0 1 3/4 0 -1/4,8,x2,-30,0 0 0 -7/
9、2 11/2,-278,Z,0 1 0 -9/4 5/4,5,x2,-30,0 -22/5 0 32/5 0,-256,Z,4/4/5,0 4/5 0 -9/5 1,4,x5,0,-32 - 30 0 0 0,0,Z,76/9,9 8 0 0 1,76,x5,0,x1 x2 x3 x4 x5,b,XB,CB,-32 - 30 0 0 0,C,2020/10/14,最优化方法,23,由最优表可知，原问题最优解：,同时不难得到原问题的最优基：,由强对偶定理的推论可得此时的单纯形乘子,为对偶问题的最优解,即松弛变量的检验数。,2020/10/14,最优化方法,24,原问题和对偶问题是紧密关联的，它们
10、不但有相同的数据集合，相同的最优目标函数值，而且在求得一个线性规划的最优解的同时，也同步得到对偶线性规划的最优解。对偶理论深刻地指示了原问题和对偶问题的内在联系，由对偶问题引伸出来的对偶解还有着重要的经济意义，是研究经济学的重要概念和工具之一。,原问题的检验数对应对偶问题的一个基本解,2020/10/14,最优化方法,25,由强对偶定理可知，如果原问题有最优解，那么对偶问题也有最优解，而且它们的目标函数值相等，即有： 其中是线性规划原问题约束条件的右端数据向量，它代表各种资源的拥有量。 为对偶问题最优解，它代表在资源最优利用条件下对各种单位资源的估价，称为影子价格(shadow price)。
11、,对偶最优解的经济解释影子价格,2020/10/14,最优化方法,26,在资源最优利用的条件下， 设备A每增加一个单位台时， 可以使总利润增加7/6元。,例,对偶最优解 其中为设备A的影子价格，,2020/10/14,最优化方法,27,对偶解的经济含义: 资源的单位改变量引起目标函数的增加量。影子价格是对偶解的一个形象的名称，它既表明了对偶解是对系统内部资源的一种客观估价，又表明它是一种虚拟的价格，而不是真实的价格。 影子价格的大小客观地反映了资源在系统内的稀缺程度。如果第 i 种资源在系统内供大于求，即在达到最优解时，该资源并没有用完，该资源的影子价格为0。它表明，增加该资源的供应不会引起系
12、统目标值的增加。 资源的影子价格越高，说明资源在系统内越稀缺，而增加该资源的供应量对系统目标函数值的贡献也越大。 企业管理者可以根据各种资源在企业内影子价格的大小决定企业的经营策略。,2020/10/14,最优化方法,28,对偶单纯形法是求解线性规划的另一基本方法。 由于它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。 不能简单理解为是求解对偶问题的单纯形法。,由对偶理论可以知道，对于一个线性规划问题，我们能够通过求解它的对偶问题来找到它的最优解。,对偶单纯形法,2020/10/14,最优化方法,29,求解思路：在迭代过程中，始终保持对偶问题解的可行性，而原问题的解由不可行
13、向可行性转化，一旦原问题的解也满足可行性条件，也就达到了最优值。 对偶单纯形法并不需要把原问题转化为对偶问题，而是利用原问题与对偶问题的数据相同，只是所处的位置不同这一特点，直接在反映原问题的单纯形表上进行运算。 对偶单纯形法不要求向量 , 处理带剩余变量的一些问题很方便。,2020/10/14,最优化方法,30,（2）确定换出变量 根据 ，确定基变量 xl 作为换出变量。检验 xl 所在行各元素 若所有alj 0, 则无可行解，停止计算。否则转入()，,（3）确定换入变量 按最小比值原则，若 确定非基变量 xk 为换入变量。 （4）以alk 为主元进行旋转变换，得新的单纯形表，重复 （2）-
14、（4），直到求得最优解。,（1）根据原始线性规划，列出初始单纯形表，检查b列数字和检验行元素，若b列数字全部非负，检验数全部非负，则已经求得最优解，停止计算。若b列中至少有一个负分量，检验数全部非正，则转入（2）,计算步骤（对于极大化目标函数问题）,2020/10/14,最优化方法,31,例 用对偶单纯形法求解 解：先化为标准型 对偶单纯形允许约束方程右端为负， 因此可将方程2，3两端同乘-1， 可得含单位矩阵的标准型：,2020/10/14,最优化方法,32,据此列出初始单纯形表，并施行对偶单纯形法迭代步骤如下：,-5/4,-7/4,0,0,0,-16,-W,-1/4,1/4,0,1,0,2
15、,x2,-2,-1/4,-3/4,0,0,1,4,x1,-3,5/4,3/4,1,0,0,4,x3,0,-2/3,0,0,0,-7/3,-20/3,-W,-1/3,0,0,1,1/3,10/3,x2,-2,1/3,1,0,0,-4/3,-16/3,x4,0,1,0,1,0,1,8,x3,0,0,0,0,-2,-3,0,-W,1,0,0,-3,-1,-10,x5,0,0,1,0,1,-1,-2,x4,0,0,0,1,3,2,18,x3,0,x5,x4,x3,x2,x1,b,XB,CB,0,0,0,-2,-3,C,可得最优解,2020/10/14,最优化方法,33,单纯形法和对偶单纯形法步骤,是,是,是,是,否,否,否,否,所有,所有,得到 最优解,计算,计算,典式对应原规划的基本解是可行的,典式对应原规划的基本解的检验数,所有,所有,计算,计算,以为中心元素进行迭代,以为中心元素进行迭代,停,没有最优解,没有最优解,单纯形法,对偶单纯形法,2020/10/14,最优化方法,34,单纯形法是在基本可行解中寻找满足最优性条件（简约价值系数非负）的最优解 对偶单纯形法则是在所有满足最优性条件（简约价值系数非负）的最优解中寻找满足可行的最优解,单纯
