《线性规划对偶理论.ppt》由会员分享，可在线阅读，更多相关《线性规划对偶理论.ppt（67页珍藏版）》请在三一文库上搜索。
1、线性规划问题具有对偶性,即任何一个线性规划问题,都存在另一个线性规划问题问题与之对应.如果把其中一个问题叫做原问题,则另外一个就叫做它的对偶问题.并称这两个相互联系的问题为一对对偶问题.研究对偶问题之间的关系及其性质,就是线性规划的对偶理论(DualityTheory).,第2章 线性规划的对偶理论,1 对偶问题的提出2 原问题与对偶问题3 对偶问题的基本性质4 影子价格5 对偶单纯形法6 灵敏度分析7 参数线性规划,常山机器厂用A、B、C三种设备生产I、II两种产品。问该企业应安排生产使总的利润收入为最大。,例1 生产计划问题,2-1 对偶问题的提出,模型,s.t.,现有四海机器厂, 为扩大
2、生产想租常山机器厂的设备, 问常山机器厂分别以每小时什么价格才愿意出租自己的设备呢?,设设备A, B, C每小时的出租价格分别为y1, y2,和y3元,出租条件: 租金收入生产的获利。,四海机器厂接受条件: 租金要低,LP1,LP2,原问题,对偶问题,矩阵形式,2-2 原问题与对偶问题,对应关系：,(1),(2),变量的个数,约束条件个数,=,(3),(原)约束条件,(4),右端项,目标函数的系数,(对偶)约束条件,对偶问题(求极小),右端项,目标函数max,目标函数min,目标函数中变量的系数,约束条件右端项,约束条件右端项,目标函数中变量的系数,例2,写出下列线性规划的对偶问题,写出下列线
3、性规划的对偶问题,2-3 对偶问题的基本性质,弱对偶性；强对偶性；最优性; 无界性; 互补松弛性,说明,在下面的讨论中, 假定线性规划原问题和对偶问题分别如下,原问题,对偶问题,掌握原问题和其对偶问题解之间的关系,1. 弱对偶性,是其对偶问题的可行解，则恒有,若,是原问题的可行解，,证明：,原问题,对偶问题,2.最优性,问题的可行解，且有,若,是原问题的可行解，,提示,则,是原问题的最优解，,是其对偶问题的最优解。,设,是原问题的最优解，,是其对偶问题的最优解。,是其对偶,3.无界性,若原问题(对偶问题)具有无界解, 则其对偶问题(原问题)无可行解.,说明,逆命题不成立。,即原问题(对偶问题)
4、无可行解，则其对偶问题(原问题)或无可行解或具有无界解,反证法结合弱对偶性,4. 强对偶性(对偶定理),若原问题有最优解, 则其对偶问题,且有,证明：,将原问题化成标准形式,用单纯形法求得最优解，则有,即,即,故,是对偶问题的可行解,又因,由性质2即可证得。,也一定有最优解,5. 互补松弛性,在线性规划问题的最优解中, 如果对应某一约束条件的对偶变量值为非零, 则该约束条件取严格等式;反之如果约束条件取严格不等式, 则该对应的对偶变量一定为零。,即：,如果,则,如果,则,证明：,由弱对偶性知，,由最优性知,从而,因此,6. 互补的基解,线性规划的原问题及其对偶问题之间存在一对互补的基解, 其中
5、原问题的松弛变量对应对偶问题的变量, 对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量, 则在另一问题的解中是非基变量；将这对互补的基解分别代入对偶问题的目标函数有z=w.,说明：,原问题的检验数,恰好是对偶问题的基解.,例3.,s.t.,原问题,对偶问题,标准形式,最终单纯形表,原问题变量,原问题变量,原问题松弛变量,原问题松弛变量,对偶问题变量,对偶问题剩余变量,对偶问题变量,对偶问题剩余变量,说明：,1)只需求解其中一个问题, 从最优解的单纯形表中同时得到另一个问题的最优解.,2)单纯形法迭代的每一步中, 原问题及对偶问题解的关系,可行解,非可行解,可行
6、解,非可行解,最优,z zmax,z zmax,2-4 影子价格,在单纯形法的每步迭代中有目标函数,表示第i种资源的拥有量,表示对一个单位第i种资源的估价, 非市场价格.,影子价格,说明：,1)供求关系影响市场价格; 资源的利用影响影子价格.,2) 影子价格是一种边际价格.,在给定的生产条件下, bi每增加1个单位时目标函数的增量,3) 影子价格又是一种机会成本.,若,市场价格 影子价格,买进该资源,市场价格 影子价格,卖出该资源,若,市场价格影子价格,4) 互补松弛性的实际意义,如果,则,如果,则,在生产中, 若某资源未充分利用时, 影子价格为0；当影子价格不为0时, 表明该资源在生产中已耗
7、费完毕.,5) 检验数的经济意义,: 表示第j种产品的产值,表示生产一个单位该种产品所消耗各项资源的影子价格的总和, 即产品的隐含成本.,若,产值 隐含成本,产值 隐含成本,若,可安排生产该产品,不安排生产该产品,2-5 对偶单纯形法,单纯形法计算的基本思想：,保持原问题为可行解的基础上, 通过迭代增大目标函数, 当对偶问题的解也为可行解时, 就达到了目标函数的最优解.,即,从满足,的基解入手，,寻找满足,的基解。,对偶单纯形法的基本思想：,保持对偶问题为可行解的基础上, 通过迭代减小目标函数, 当原问题的解也为可行解时, 就达到了目标函数的最优解.,的条件下寻找满足,的基解。,从满足,的基解
8、入手，,即,在保持,的条件下,在保持,cj -zj,cj zj,cn -zn,对偶单纯形法的初始单纯形表：,在上表中必须有,cj zj 0 ( j= 1,n ),但,的值不一定为正.,对偶单纯形法的计算步骤：,(1) 确定出基变量.,对应的变量xr作为出基变量.,(2) 确定入基变量.,xs作为入基变量.,ars称为主元素,(3) 用入基变量替换出基变量得到新基, 进行初等变换, 再检验是否 , 若是, 则找到了问题的最优解, 否则, 回到第一步在重复计算.,说明：,原问题无可行解, 对偶问题的目标函数值无界.,例4：用对偶单纯形法求解线性规划问题,解：,化成标准形式,列出单纯形表, 并用对偶
9、单纯形法求解, , ,说明：,1) 在利用对偶单纯形法时, 要保证初始单纯形表中对偶问题应是基可行解, 这一点对大多数线性规划很难实现, 因此对偶单纯形法一般不单独使用.,2) 使用对偶单纯形法的条件,概况改变价值向量改变右端向量增加变量增加约束条件,2-6 灵敏度分析,1. 灵敏度分析的含义,概况,是指对系统或事物因周围条件变化显示出来的敏感度的分析.,2. 灵敏度分析研究的问题,当一个或多个参数发生变化时, 最优解会有什么变化; 或这些参数在一个多大范围内变化时, 问题的最优解不变.,3. 如何解决,1) 用单纯表法从头计算(此法既麻烦又没有必要),2) 把参数的变化直接反映到单纯形表中，
10、再继续处理。,灵敏度分析的步骤,1) 将参数的改变计算反映在最终单纯形表上,2) 检查原问题是否仍为可行解,4) 按右表所列情况得出结论和决定继续计算的步骤,3) 检查对偶问题是否仍为可行解,6-1 价值系数cj发生变化(仅影响检验数),单纯形表,s.t.,例 已知下述线性规划的最终单纯形表为,(1) 若c由(2, 3)变成(3, 2), 最优解是否发生变化?,(2) 若目标函数为,问 分别在什么范围内变化时，问题的最优解不变？,当 在什么范围内变化时，问题的最优解不变？,例 已知下述线性规划的最终单纯形表为,(1) 若c由(2, 3)变成(3, 2), 最优解是否发生变化?,解：,将c的变化
11、反映到最终单纯形表中,3 2,3,2,- 3/2, ,最优解是(4,2,0,0,5), 最优值16,1/ 5,(2) 若目标函数为,问 分别在什么范围内变化时, 问题的最优解不变？,解：,当,即,最优解不变.,时,类似可讨论，当,最优解不变.,(3) 若目标函数为,问 在什么范围内变化时, 问题的最优解不变？,解：,当,即,最优解不变.,时,o,6-2 分析bi的变化范围,bi的变化引起基变量的取值发生变化，有可能发生1、3两种情况,s.t.,例 已知下述线性规划的最终单纯形表为,(1) 若b由(12,16,15)变成(15,12,20), 最优基是否发生变化?,(2) 若b变成 ，分别分析
12、在什么范围内变化时, 问题的最优基不变。,(3) 当 在什么范围内变化时, 问题的最优基不变。,解：,(1) 若b由(12,16,15)变成(15,12,20), 最优基是否发生变化?,则新规划的最初单纯形表为, ,最优基发生变化，,最优值为18,最优解为,解：,当,问题的最优基不变,(2) 若 ，分别分析 在什么范围内变化时, 问题的最优基不变。,即,类似可求得当,问题的最优基不变,解：,当,即,问题的最优基不变,(3) 若 ，分析 在什么范围内变化时, 问题的最优基不变。,6-3 增加新变量(增加新产品),分析步骤：,(1)计算,(2)计算,(3)若,，只需将,原最优解不变,的值反映到最终
13、单纯形表中，,和,，则按单纯形法继续迭代计算。,若,s.t.,例 已知下述线性规划的最终单纯形表为,若增加一个变量x6 , 有c6=4, P6=(2,4,5)T, 分析问题最优解的变化.,解：,或,构造新表, ,利用单纯形法继续迭代,6-4 增加约束条件(增加工序),分析步骤：,先将原问题的最优解变量取值代入新增的约束条件，若满足，说明新增约束未起到限制作用，原最优解不变.否则，将新增约束直接反映到最终表中，在进行分析.,s.t.,例 已知下述线性规划的最终单纯形表为,若增加一个约束条件 , 分析问题最优解的变化.,解：,原问题的最优解为(3,3,0,4,0)，而33+2 3=1514,构造新
14、表,将新增的约束条件加上松弛变量后的方程直接反映到最终单纯形表中，得,取P1、P4、P2、P6列组成单位阵,对上表进行初等行变化得到对应的单纯形表,对偶单纯形法, ,最优解,最优值,x1=8/3, x2=3,z*=43/3,s.t.,练习 已知下述线性规划的最终单纯形表为,(1)若增加一个约束条件 , 分析问题最优解的变化.,(2)若增加一个约束条件 , 分析问题最优解的变化.,s.t.,练习 已知下述线性规划的最终单纯形表为,(1)若增加约束条件 , 分析问题最优解的变化.,解：,原问题的最优解为(3,3,0,4,0)，,故(3,3,0,4,0)还是新规划的最优解,而33+2 3=1514,
15、对上表进行初等行变化得到对应的单纯形表,s.t.,练习 已知下述线性规划的最终单纯形表为,(2)若增加一个约束条件 , 分析问题最优解的变化.,解：,原问题的最优解为(3,3,0,4,0)，而33+2 3=1516,将新增的约束条件减去剩余变量后的方程直接反映到最终单纯形表中,构造新表,取P1、P4、P2、P6列组成单位阵,构造初始单纯形表,对偶单纯形法, ,2-7 参数线性规划,灵敏度分析：,研究使问题的最优解或最优基保持不变时的参数值变化范围.,参数线性规划：,研究当参数值连续变化时, 问题的最优解如何随参数值的变化而变化.,例 求解下述参数线性规划问题,s.t.,解：,当=0求解得最终单
16、纯表为,将参数的变化反映到最终单纯形表中，得,当,即,时，最优基为,P1, P4, P2,当0，利用单纯形法继续迭代, , ,当1时, 50，利用单纯形法继续迭代, ,例 求解下述参数线性规划问题,s.t.,解：,当=0求解得最终单纯表为,将参数的变化反映到最终单纯形表中,当,即,时，最优基不变, , ,课后习题选讲,2-1 写出下列线性规划问题的对偶问题,2-2 判断下列说法是否正确，为什么？,如果线性规划的原问题存在可行解, 则其对偶问题也一定存在可行解;(b) 如果线性规划的对偶问题无可行解, 则原问题也一定无可行解;(c)在互为对偶的一对原问题与对偶问题中, 不管原问题是求极大还是极小
17、, 原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值;(d)任何线性规划问题具有唯一的对偶问题。,无界性,无可行解或无界解,2-3 应用对偶理论证明下述线性规划问题为无界解。,对偶问题,原问题,约束(1)(2)相加推出矛盾,无可行解,因为对偶问题无可行解，所以原问题无可行解或无界解,而(0,0,0)是原问题的可行解，所以原问题无界解,2-4 已知线性规划问题：,对偶问题,要求: (a)写出其对偶问题； (b)已知原问题最优解为 根据对偶理论, 直接求出对偶问题的最优解.,由互补松弛性得,由目标函数相等得,2-5 已知线性规划问题A和B如下：,问题A,问题B,对偶变量,对偶变量,试分别写出yi同 间的关系式,对偶变量,对偶变量,对偶问题,对偶问题,2-11 已知线性规划问题：,解:(a),由,得,由,得,