运筹学大作业 哈工大.pdf

《运筹学大作业 哈工大.pdf》由会员分享，可在线阅读，更多相关《运筹学大作业 哈工大.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课程名称：对偶单纯形法课程名称：对偶单纯形法一、教学目标教学目标在对偶单纯形法的学习过程中，理解和掌握对偶问题；综合运用线性规划和对偶原理知识对对偶单纯形法与单纯形法进行对比分析，了解单纯形法和对偶单纯形法的相同点和不同点，总结出各自的适用范围；掌握对偶单纯形法的求解过程；并能运用对偶单纯形法独立解决一些运筹学问题。二、教学内容二、教学内容1)对偶单纯形法的思想来源(5min)2)对偶单纯形法原理(5min)3)总结对偶单纯形法的优点及适用情况(5min)4)对偶单纯形法的求解过程(10min)5)对偶单纯形法例题(15min)6)对比分析单纯形法和对偶单纯形法(10min)三、教学进程：三、

2、教学进程：1）讲述对偶单纯形法思想的来源：1954 年美国数学家 C.莱姆基提出对偶单纯形法（Dual Simplex Method）。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。2）讲述对偶单纯形法的原理A.对偶问题的基本性质依照书第 58 页，我们先介绍一下对偶问题的六个基本性质：性质一：弱对偶性性质二：最优性。如果nx（j=1.n)原问题的可行解

3、，y是其对偶问题可jj行解，且有c x=by，则xj是原问题的最优解，yj1jjmi1iij是其对偶问题的最优解。性质三：无界性。如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）无可行解。性质四：强对偶性。如果原问题有最优解，则其对偶问题也一定有最优解。性质五：互补松弛型。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。性质六：线性规划的原问题及其对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解

4、中是基变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有 z=w.B.对偶单纯形法（参考书 p64 页）设某标准形式的线性规划问题，对偶单纯形表中必须有cj-zj0（j=1.n),但bi(i=1.m)的值不一定为正，当对 i=1.m，都有bi0 时，表中原问题和对偶问题均为最优解，否则通过变换一个基变量，找出原问题的一个目标函数值较小的相邻的基解。3）为什么要引入对偶单纯形法从理论上说原始单纯形法可以解决一切线性规划问题，然而实际问题中，由于考虑问题的角度不同，变量设置的不同，便产生了原问题及其对偶问题，对偶问题是原问题从另外一个角度考虑的结果。用对偶单纯

5、形法求解线性规划问题时，当约束条件为“”时，不必引入人工变量，使计算简化。例如，有一线性规划问题：min=12y+16y12+15y32y4y 221约束条件2y15y3 3(i 1,2,3)0yi将问题改写为求目标函数极大化，化为标准形式有max=-12y-16y-15y+0y+0y123452y4yy 2124约束条件25yy 335y1若用对偶单纯形法，则直接按右边的标准型列出单纯形表求解即可，计算简单。4)4)例题详解例题详解用对偶单纯形法求解线性规划问题min=15y+24y+5y12363 2y3y25y12y2y31y1,y2,y3 0先将问题改为min 15y24y5y0y0y

6、123456yyy 23425y12y2y3y51 0(i 1,2,3,4,5)yi第一步 15 24 5 0 0yyyyy12345y -24 06 -1 1 0-5 -2 -1 0 115 24 5 0 0y -15j 0建立初始单纯形表，表中检验行的值全部0，即对其对偶问题而言是一基本可行解。根据原问题和对偶问题之间的对称关系，这时单纯形表中原基变量列数字相当于对偶问题解的非基变量的检验数第二步 由于对偶问题的求解是使目标函数达到最小值所以最优判别准则是当所有检验数大于等于零时为最优（也即这时原问题是可行解）如果不满足这个条件，找出绝对值最大的负检验数，其对应的原问题的基变量xl即为对偶

7、问题的换入变量。第三步 确定换出变量：=min(2c-z)/ajjrj=min-24/-6,-5/-1=4因此选y作为换入变量。第四步用换入变量替换对偶问题中的换出变量得到一个新的单纯形表。表中数字计算同用单纯形法时完全一样。新表中对偶问题仍保持基本可行解，原问题基变量列数字相当于对偶问题的检验数。第五步：重复第二四步，一直到找出最优解为止。Y4 -2 Y5 -1cj 0 Y2 1/3 Y5 -1/3cj -8 Y2 1/4 Y3 1/2cj -17/2此时达到最优,最优为 15 Y1 0 24 Y26 5 Y3 -1 -1 0 Y4 1 0 0 -1/6 -1/3 4 -1/4 1/2 7/

8、2 0 Y5 0 1 0 0 1 0 1/4 -3/2 3/2 -5 -2 15 0 -5 15 24 5 1 1/6 0 023 1 0 1 0 -5/4 1 15/2 0 15/2 0172例题讲解结束，我们可以通过例题的详细求解过程得到对偶单纯形法的算法步骤如下：骤如下：（参考书第（参考书第 6464 页）页）1、确定换出基的变量：对小于零的bi，令br=minbi，其对应变量2、确定换入基的变量：（1）为使迭代后的表中第 r 行基变量为正值，因而只有对应arj0（j=m+1，n）的非基变量才可以考虑作为换入基的变量；（2）为使迭代后表中对偶问题的解仍为可行解，令x为换出基的变量。rcz

9、=mina|ajjrjrjcz0=asrssx为换入基的变量。s设迭代后表中的检验数为(cjzj)则(cjzj)=（czj-j）-a()=czczczaaaarjjjssssrjrsrjrs此时一定有(cjzj)0，下面分两点说明：zca.对arj0，因（cj-zj）0，故ajrjjzc0,又因主元素ars0,故有asrss0，因此(cjzj)0zczcb.对arj0,故同样(cz)0aajjssjjrjrs3、用换入变量替换换出变量，得到一个新的基，检查是否所有bi0。如果是，则找到了问题最优解，否则回到第一步重复计算。4、原问题无可行解的情况：对br0,而对所有 j=1.n,有程列出有ar

10、j0。因为这种情况下，把表中第 r 行的约束方x+arr,m1xm1+.+ar,nx=b，因anrrj0,又br=0前提条件最优性检验迭代原则所有bi=0所有j=0所有bi=0最大：检验数最大的非基变量为换入变量cz最小：ajrjj最小的对应b最小：a出变量i的那个非基变量为换入的最小的为换变量ikbi数字最小最小：（负数）对应的那个基变量为换出变量2)2)对偶单纯形法优缺点对偶单纯形法优缺点对偶单纯形法的优点：(1)运用对偶单纯形法时,初始解可以是非可行解,只要检验数全部非正数就可以进行基变换.因此不需要引进人工变量,这样可以简化计算.(2)应用对偶问题与原问题的关系,对变量较少而约束较多的

11、线性规划问题 ,应用对偶问题与原问题的关系,先变换成对偶问题,再用对偶单纯形法求解,可以减少计算工作量.(3)灵敏度分析中有时需要用到对偶单纯形法,可使问题的处理简化.2.对偶单纯形法的缺点：对于大多数线性规划问题而言很难找到一个初始正则基,对于大多数线性规划问题而言很难找到一个初始正则基,即很难满足使 所有的检验数小于等于零(对偶可行性),因而此法很少单独使用.五、对偶单纯形法算法流程图五、对偶单纯形法算法流程图开始将原问题化为标准型，计算非基变量检验数，列出初始单纯形表检验基变量对应的 b 是否0是是找到最优解结束确定换出基的变量，若bj0，令 br=minbj,其对应变量为换出基的变量对于 br这一行，ari是否均非负原问题无可行解确定换入基的变量，=min（cj-zj）/ari=(cs-zs)/ars,xs为换入基的变量。结束进行枢轴运算，列出新的单纯形表1.用非基变量 xs代替基变量 xr；2.对主元行（第 r 行），令 br/arsbr，arj/arsarj3.对主元列（第 s 列），令 1ars，0其他元素4.表中其他列元素 aij-arjais/arsaijbi-brais/arsbi