第二章对偶理论与灵敏度分析.ppt
《第二章对偶理论与灵敏度分析.ppt》由会员分享,可在线阅读,更多相关《第二章对偶理论与灵敏度分析.ppt(123页珍藏版)》请在三一文库上搜索。
1、第二章 对偶理论与灵敏度分析,1线性规划的对偶问题 2对偶问题的基本性质 3影子价格 4对偶单纯形法 5灵敏度分析,1线性规划的对偶问题,1.1 对偶问题的提出 1.2 对称形式下对偶问题的一般形式 1.3 非对称形式的原对偶问题关系 1.4 对偶问题的定义 1.5 对偶关系对应表,例1:美佳公司利用该公司资源生产两种家电产品。,1.1 对偶问题的提出,1线性规划的对偶问题,现从另一角度提出问题。假定有另一公司想把美佳公司的资源收买过来,它至少应付出多大代价,才能使美佳公司愿意放弃生产活动,出让自己的资源? 显然美佳公司愿出让自己资源的条件是,出让代价应不低于用同等数量资源由自己组织生产活动时
2、获取的盈利。 设分别用yl,y2和y3代表单位时间(h)设备A、设备B和调试工序的出让代价。因美佳公司用6小时设备A和l小时调试可生产一件家电I,盈利2元;用5小时设备A,2小时设备B及1小时调试可生产一件家电II,盈利1元。,1线性规划的对偶问题,由此y1,y2,y3的取值应满足:,该公司希望用最小代价把美佳公司的全部资源收买过来。,因此,线性规划模型为:,1线性规划的对偶问题,1线性规划的对偶问题,原问题:设x1 , x2 为产品1,2的产量,maxZ= 2X1 +3x2,1线性规划的对偶问题,对偶问题:设 y1 , y2 , y3 , y4分别为A, B, C, D设备的单价,1线性规划
3、的对偶问题,对称的含义:满足下列条件的线性规划问题称为具有对称形式:其变量均具有非负约束,其约束条件当目标函数求极大时均取“”号,当目标函数求极小时均取“”号。 对称形式下线性规划原问题的一般形式为:,max Z=c1x1+ c2x2+cnxn,1.2 对称形式下对偶问题的一般形式,1线性规划的对偶问题,用yi(i1,m)代表第i种资源的估价,则其对偶问题的一般形式为:,min w=b1y1+ b2y2+bmym,1线性规划的对偶问题,用矩阵形式表示,原问题为:,其对偶问题为:,1线性规划的对偶问题,原问题与对偶问题的对应关系,1线性规划的对偶问题,1.3 非对称形式的原对偶问题关系,1线性规
4、划的对偶问题,例2 写出下述线性规划问题的对偶问题,无约束,1.3 非对称形式的原对偶问题关系,1线性规划的对偶问题,写出其对偶问题为:,可变换成具有如下对称形式的线性规划问题,1.3 非对称形式的原对偶问题关系,1线性规划的对偶问题,进行整理为:,无约束,例3 写出下述线性规划问题的对偶问题,1.3 非对称形式的原对偶问题关系,1线性规划的对偶问题,解:原问题可化为,则对偶问题:,1线性规划的对偶问题,令 y1 = y1 -y1 “,1线性规划的对偶问题,1.4 对偶的关系,原始问题 max z=CTX s.t. AX b X 0,对偶问题 min y=bTW s.t. ATW C W 0,
5、1线性规划的对偶问题,1.5 对偶关系对应表,1线性规划的对偶问题,2对偶问题的基本性质,单纯形法计算的矩阵描述 一、对称性 二、弱对偶性 三、无界性 四、可行解是最优解的性质 五、对偶定理 六、松紧定理,用矩阵形式表示,原问题为:,其对偶问题为:,min y=bY s.t. AY C Y 0,max z=CX s.t. AX b X 0,2对偶问题的基本性质,单纯形法计算的矩阵描述,对称形式线性规划问题的矩阵表达式加上松弛变量后为:,上式中XS为松弛变量,I 为mm单位矩阵,通过迭代后: X=XB + XN,相应地: C=CB + CN,系数矩阵 : A= B + N,2对偶问题的基本性质,
6、参1-105,迭代后新的单纯形表为:,初始单纯形表:,2对偶问题的基本性质,迭代后新的单纯形表为:,初始单纯形表:,C- CBB-1A,2对偶问题的基本性质,可以看出:,(1)对应初始单纯形表中的单位矩阵I,迭代后的单纯形表中为B-1 ; (2)初始单纯形表中基变量Xsb,迭代后的表中 XB=B1b ; (3)初始单纯形表中约束系数矩阵为A,I B,N,I ,迭代后的表中约束系数矩阵为B-1A,B-1IB-1B,B-1N,B-1I I,B-1N,B-1 ; (4)若初始矩阵中变量Xi的系数向量为Pj,迭代后为Pj,则有Pj=B-1Pj 。,2对偶问题的基本性质,当B为最优基时,因xB的检验数可
7、写为 CB- CBI=0,CBB-1称为单纯形乘子,若令Y= CBB-1 ,则,所以,CN- CBB-1N 0 -CBB-1 0,C- CBB-1A 0 -CBB-1 0,2对偶问题的基本性质,看出这时检验数行,若取其相反数恰好是其对偶问题的一个可行解。 将这个解代入对偶问题的目标函数值,有:,当原问题为最优解时,这时对偶问题为可行解,且两者具有相同的目标函数值,对偶问题的解也为最优解。,w=Yb= CBB-1b=z,2对偶问题的基本性质,例4,maxZ=2x1+ x2+0x3 +0x4+0x5,min w=15y1+ 24y2+ 5y3 +0y4+0y5,2对偶问题的基本性质,最终单纯形表:
8、,2对偶问题的基本性质,一 . 对称性 : 对偶问题的对偶是原问题,2对偶问题的基本性质,对 偶,2对偶问题的基本性质,若x是原问题的可行解,y是对偶问题的可行解。则有 cxyb,二. 弱对偶性,2对偶问题的基本性质,推论(2): 若原问题(对偶问题)为无界解,则其对偶问题(原问题)无可行解。,推论(1): 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界,反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。,注 : 其逆不成立。,推论(3)若原问题有可行解而其对偶问题无可行解,则原问题目标函数值无界,反之对偶问题有可行解而其原问题无可行解,则对偶问题的目标函数值无界。,2对
9、偶问题的基本性质,设x是原问题的可行解,y是对偶问题的可行解. 当 cx= yb 时 x, y 是最优解。,三 . 最优性,2对偶问题的基本性质,四 . 强对偶性(对偶定理),若原问题及其对偶问题均具有可行解,则两者均具有最优解且它们最优解的目标函数值相等。,证明: 由弱对偶定理推论1,可知两者都有最优解。 由前面公式可知,当原问题有最优解时,对偶问题有可行解,且目标函数值相等。 由最优性知,两者均为最优解。,2对偶问题的基本性质,五. 互补松弛性(松紧定理),在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值为非零,则该约束条件取严格等式;反之如果约束条件取严格不等式,则其对应的对偶
10、变量一定为零。,y1 y2 y3,2对偶问题的基本性质,即:,2对偶问题的基本性质,证明:,几个练习,2对偶问题的基本性质,2对偶问题的基本性质,1 )说明原问题和对偶问题都有最优解. 2 )求原问题和对偶问题的最优目标函数值的一个上界和下界.,2对偶问题的基本性质,2对偶问题的基本性质,2对偶问题的基本性质,2对偶问题的基本性质,2对偶问题的基本性质,2对偶问题的基本性质,2对偶问题的基本性质,3影子价格,式中bi是线性规划原问题约束条件的右端项,它代表第i种资源的拥有量;对偶变量yi*的意义代表在资源最优利用条件下对单位第i仲资源的估价。这种估价不是资源的市场价格,而是根据资源在生产中作出
11、的贡献而作的估价,为区别起见,称为影子价格(shadow price)。,关于影子价格的几点说明,1影子价格是未知数,有赖于资源的利用情况。,2影子价格是一种边际价格。,这说明影子价格的值相当于在资源得到最优利用的生产条件下,b每增加一个单位时目标函数Z的增量。,3影子价格,例1,A B C,15/2 0 0,资源,剩余,0 1/4 1/2,影子价格,3影子价格,所以第2种资源的影子价格为0.25,第3种资源的影子价格为0.5。,3影子价格,3资源的影子价格实际上又是一种机会成本。 在纯市场经济条件下,可以根据影子价格与市场价格的关系确定资源的买进或卖出。,4生产过程中如果某种资源末得到充分利
12、用时,该种资源的影子价格为零;又当资源的影子价格不为零时,表明该种资源在生产中已耗费完毕。,3影子价格,5单纯形表中各个检验数的经济意义,6对线性规划问题的求解是确定资源的最优分配方案,而对于对偶问题的求解则是确定对资源的恰当估价。,当产品产值大于隐含成本时,表明生产该项产品有利,可在计划中安排,否则这些资源来生产别的产品更为有利,就不在计划中安排。这就是单纯形表中各个检验数的经济意义。,3影子价格,4对偶单纯形法,单纯形法的思路:找一个基可行解,在保持解可行的前提下,让检验数全为非正。,对偶单纯形法的基本思路:先找出一个对偶问题的可行基,并保持对偶问题为可行解条件下,如不存在XB o,通过变
13、换到一个相邻的目标函数值较小的基本解(因对偶问题是求目标函数极小化),并循环进行,一直到原问题也为可行解(即XB o),这时对偶问题与原问题均为可行解。 在迭代过程中保持原问题的检验数为非正,逐步替换负基变量,从而得到最优解。,4对偶单纯形法,对偶单纯形法的计算步骤:,1. 列出初始单纯形表,且检验数非正。,4对偶单纯形法,4.以ars为主元素,进行迭代变换。 可以证明,按照上述方法进行迭代变换以后,检验数仍保持为非正,即对偶问题仍可行。,5 . 返 2,直到B 0为止。,原始单纯形法 按列选主元 对偶单纯形法 按行选主元,对于对偶问题有可行解,而原问题无可行解的判断。 判断准则是:对 ,而对
14、所有j=1,n,有 。,4对偶单纯形法,例5:用对偶单纯形法求解下列问题,4对偶单纯形法,4对偶单纯形法,4对偶单纯形法,4对偶单纯形法,已获得最优解: (x1, x2, x3, x4, x5, x6)=(5, 7, 6, 0, 0, 0) min z=35 对偶问题的最优解为: (w1, w2, w3, w4, w5, w6)=(-1, 5, 7, 0, 0, 0) max y=35,4对偶单纯形法,从以上计算可以看出,用对偶单纯形法求解线性规划问题时,当约束条件为“”时,不必引进人工变量,使计算简化。但在初始单纯形表中其对偶问题应是基可行解这点,对多数线性规划问题很难实现。因此对偶单纯形法
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 对偶 理论 灵敏度 分析
链接地址:https://www.31doc.com/p-3151217.html