第章+对偶问题和灵敏度分析.pptVIP

灵敏度分析与对偶 王广民 中国地质大学 经济管理学院 wgm97@163.com 一、线性规划的对偶问题 2、对称形式的原始对偶问题 对称形式 LP与DP之间的关系： 3、对称形式的对偶规则 给每个原始约束条件定义一个非负对偶变量yi(i=1,2,…,m)； 使原问题的目标函数系数 cj 变为其对偶问题约束条件的右端常数； 使原问题约束条件的右端常数 bi 变为其对偶问题目标函数的系数； 将原问题约束条件的系数矩阵转置，得到其对偶问题约束条件的系数矩阵； 改变约束问题不等号的方向，即将“≤”改为“≥”； 原问题为“max”型，对偶问题为“min”型。 4、一般的线性规划问题的对偶问题 混合型问题的对偶规则： 原问题为“max”，对偶问题为“min”； 原问题中目标函数系数 ci 变为其对偶问题约束条件的右端常数； 原问题约束条件的右端常数 bi 变为其对偶问题目标函数的系数； 原问题约束条件的系数矩阵转置，即为其对偶问题的系数矩阵； 原问题的变量个数n等于其对偶问题的约束条件个数n，原问题 约束条件的个数m等于其对偶问题变量的个数m； 在求极大值的原问题中，“≤”，“≥”和“=”的约束条件分别对应其对偶变量“≥0”，“≤0”和“无符号限制”； 在求极大值的原问题中，变量“≥0”，“≤0”和“无符号限制”分别对应其对偶约束条件的“≥”，“≤”和“=”约束. 对偶规则表 二、对偶原理 紧约束与松约束 四、对偶单纯形法 对偶规划可以用线性规划的单纯形法求解。 由对偶原理可见，原问题与对偶问题之间有紧密联系，因此我们能够通过求解原问题来找出对偶问题的解，反之依然。 互补松弛条件就可以解决由原问题的最优解直接求出对偶问题的最优解。 对偶单纯形法是求解线性规划的另一个基本方法，它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。 先回顾一下单纯形算法：它是从线性规划的一个基可行解迭代到另一个基可行解的过程，在迭代过程中，保持基解的可行性，逐步消除基解的检验数的非负性，即 为了求解线性规划，我们也可以从线性规划的一个基解迭代到另一个基解，在迭代过程中，保持基解的检验数的非正性，逐步消除基解的不可行性，即 对偶单纯法计算框图 设正则基 的典式为： 对偶单纯形表 对偶单纯形法的迭代方式与原单纯形法基本一致.所不同的是：先定换出变量，再定换入变量，决定主元并作基变换得到一个新的正则解X(1),从而完成一次迭代.算法的后半部分与原单纯形法完全一致. (2)再选进基变量:假定xk为进基变量, 我们分析一下xk 应满足什么条件,才能使迭代后得到的解仍为问题(P)的正则解. (1)先选出基变量:若 则取与 相对应的基变量 xr 为出基变量. 因为 ,而换基运算的第一步是用主元 去除第r 行中的各元素,为了使变换后 为正数,所以主元 必须从第r 行的负元素中选取,即 . 设主元处在第 k 列,于是换基运算后,各检验数变为 因为要求迭代后得到的解仍为正则解,于是 又因为 于是当 时,不等式(1)自然成立; 由此 则取与之相对应的非基变量 为换入变量。 否则,当 时,要使不等式(1)成立,必须 又因为 于是当 时,不等式(1)自然成立; 最后证明对应于新的正则解X(1),对偶问题(D)的目标函数值将得到改善. 这样,上述求极大值问题(P)的迭代过程,实质上是在对对偶问题(D)求极小值,所以目标函数越小就越接近最优解.直到得到对偶问题(D)的最小值,相应地也就求出了原问题(P)的最大值. 出基变量 与进基变量 xk 确定以后,以 为主元进行换基运算(方法与原单纯形法相同)即可得新的正则解X(1) . 这是因为 ,故 和原始单纯形法一样,若对偶问题是非退化的(即对偶问题的每一个基可行解都是非退化的,或者说,对于原问题的每一个正则解，都有 ,则每迭代一次,目标函数都将严格减小,从而一定能在有限次迭代后得到原问题的最优解,或者判定它无解. 容易证明:若 ,且所有的 ,则原问题(P)无解(自己证明). 用对偶单纯形法求解线性规划问题时．当约束条件为“＞”时