运筹学线性规划对偶问题课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《运筹学线性规划对偶问题课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 线性规划 对偶 问题 课件
- 资源描述:
-
1、第三章第三章 线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析 n线性规划的对偶问题线性规划的对偶问题 n对偶问题的基本性质对偶问题的基本性质n影子价格影子价格n对偶单纯形法对偶单纯形法n灵敏度分析灵敏度分析第1页,共18页。第二节第二节 对偶问题的基本性质对偶问题的基本性质为了便于讨论,下面不妨总是假设:为了便于讨论,下面不妨总是假设:0XbAXCX.max :tsZ原问题0YCYAbY.min :tsW对偶问题第2页,共18页。原线性规划问题的矩阵表达式加上松弛变量后为:原线性规划问题的矩阵表达式加上松弛变量后为:一、一、单纯形法的矩阵描述单纯形法的矩阵描述上式中上式中XsXs
2、为松弛变量,为松弛变量,I为为m mm m单位矩阵。单位矩阵。0,00maxsssXXbIXAXXCXz),(21mnnnsxxxX0,0,.000 21212211222222121111212111212211mnnnnmmnnmnmmnnnnnnmnnnnnxxxxxxbxxaxaxabxxaxaxabxxaxaxatsxxxxcxcxczMax第3页,共18页。Cjc1c2cn000CBXBbx1x2xnxn+1xn+2xn+m0 xn+1b1a11a12a1n1000 xn+2b2a21a22a2n0100 xn+mbmam1am2amn001cj-zjc1c2cn000非基变量非基
3、变量基变量基变量XB XNXS0 XS bB NICj-zjCB CN0 单纯形法计算时,总选取单纯形法计算时,总选取I I为为初始基初始基,对应基变量为对应基变量为XsXs。设迭代若干步后,基变量为设迭代若干步后,基变量为X XB B,在初始单纯形表中的在初始单纯形表中的系数矩阵为系数矩阵为B B。B B将在初始单纯形表中单独列出,而将在初始单纯形表中单独列出,而A A中去掉若干列中去掉若干列后剩下的列组成矩阵后剩下的列组成矩阵N N,这样初始单纯形表可列成如下形式。这样初始单纯形表可列成如下形式。第4页,共18页。非基变量非基变量基变量基变量XB XNXS0 XS bB NICj-zjCB
4、 CN0 当迭代若干步后,基变量为当迭代若干步后,基变量为X XB B时时,则该步的单纯形表中由则该步的单纯形表中由X XB B系数组成的矩阵为系数组成的矩阵为I I。又因单纯形法的迭代是对约束增广矩阵进行的行的又因单纯形法的迭代是对约束增广矩阵进行的行的初等变换初等变换,对应对应X XS的系数矩阵在新表中的系数矩阵在新表中应为应为B B-1-1。故当基变量为故当基变量为X XB B时,新的单纯形表具有如下形式。时,新的单纯形表具有如下形式。基变量基变量非基变量非基变量XBXN XSCB XB B B-1-1 bIB B-1-1 N B B-1-1 Cj-zj0CN-CB B B-1-1 N
5、-CB B B-1-1 第5页,共18页。当迭代后基变量为当迭代后基变量为XB时时,其在初始单纯形表中的系数矩阵为其在初始单纯形表中的系数矩阵为B B,则有:则有:(1 1)对应初始单纯形表中的单位矩阵对应初始单纯形表中的单位矩阵I I,迭代后的单纯形表中为迭代后的单纯形表中为B B-1-1(2)初始单纯形表中基变量初始单纯形表中基变量Xs=bXs=b,迭代后的表中迭代后的表中 XB=B B-1-1 b(3)初始单纯形表中约束系数矩阵为初始单纯形表中约束系数矩阵为 ,迭代后的表中约迭代后的表中约束系数矩阵为束系数矩阵为(B B-1-1 左乘左乘):INBIA,1111111,BNBIIBNBB
6、BIBAB非基变量非基变量基变量基变量XB XNXS0 XS bB NICj-zjCB CN0基变量基变量非基变量非基变量XBXN XSCB XB B B-1-1 bIB B-1-1 N B B-1-1 Cj-zj0CN-CB B B-1-1 N -CB B B-1-1(4)若初始矩阵中变量若初始矩阵中变量Xj的系数向量为的系数向量为Pj,迭代后为,迭代后为 ,则有,则有:jPjjPBP1第6页,共18页。(5)当当B B为最优基时为最优基时,应有,应有:01NBCCBN01BCB这时从检验数行看出,若取其相反数恰好是其对偶问题的一个可行解。这时从检验数行看出,若取其相反数恰好是其对偶问题的一
7、个可行解。将这个解代入对偶问题的目标函数值,有将这个解代入对偶问题的目标函数值,有:因因XB的检验数可写为的检验数可写为:zbBCbYwB11BCYB0YCYA则有则有称为称为单纯形乘子单纯形乘子,若令若令1BCB基变量基变量非基变量非基变量XBXN XSCB XB B B-1-1 bIB B-1-1 N B B-1-1 Cj-zj0CN-CB B B-1-1 N -CB B B-1-1 XN的检验数的检验数 XS的检验数的检验数 0ICCBBXB的检验数的检验数 01ABCCB所以所以XA的检验数的检验数 第7页,共18页。例例1 1 两个互为对偶的线性规划问题,两者分别加上两个互为对偶的线
展开阅读全文