运筹学对偶单纯形法.ppt
《运筹学对偶单纯形法.ppt》由会员分享,可在线阅读,更多相关《运筹学对偶单纯形法.ppt(13页珍藏版)》请在三一文库上搜索。
1、6 对偶单纯形法,在原来的单纯形表中进行迭代时,前提要求右端项b 0(基可行解),迭代过程中在b列中得到的是原问题的基可行解,在检验数行得到的是对偶问题的基解。当检验数行也是对偶问题的基可行解时,原问题与对偶问题都得到最优解。,对偶单纯形法原理:根据对偶问题的对称性,保持对偶问题的解是基可行解,即cj-CBB-1Pj 0,同时取消对解答列元素非负的限制,在原问题非可行解的基础上, 通过逐步迭代达到基可行解,这样就得到了最优解。,其优点是原问题的初始解不一定要求是基可行解,可从非可行解开始迭代。简言之,不必引进人工变量寻找基底。,方法:设原问题 max z = CX AX = b X 0,设B是
2、一个基,令B=(P1 ,P2 , ,Pm),它对应的变量为 XB = ( x1 ,x2 , ,xm),当非基变量都为零时,可以得到XB = B-1b。若在B-1b中至少有一个负分量,设(B-1b)i 0, 并且在单纯形表的检验数行中的检验数都为非正,即对偶问题保持可行解,它的各分量是,1、对应基变量x1,x2, ,xm的检验数是 i = ci zi = ci - CB B-1Pi = 0,i = 1 ,2 , ,m 2、对应非基变量xm+1, ,xn的检验数是 j = cj zj = cj - CB B-1Pj 0,j = m+1 , ,n,每次迭代时,将基变量中的负分量xl取出(换出变量),
3、 去替换非基变量中的xk,要求在所有检验数仍保持非正(对偶问题可行性)的前提下,进行基变换。从原问题来看,经过每次迭代, 原问题由非可行解往可行解更靠近,当原问题得到可行解时,便得到了最优解(原问题、对偶问题)。,注意: 1. 对偶单纯形法不是解对偶问题的单纯形法,而是应用对偶原理求解原问题最优解的一种方法。当然,当求解得到原问题的最优解的同时,也就得到对偶问题的最优解。,2.在具体计算中,不另外构造单纯形表格,而是在原始问题的单纯形表格基础上进行对偶处理。,对偶单纯形法的计算步骤:,(1) 根据线性规划问题,列出初始单纯形表,检查b列的数值,若都为非负,并且检验数都为非正,则已得到最优解。停
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 对偶 单纯
链接地址:https://www.31doc.com/p-2096815.html