运筹学大作业哈工大

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

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

3、，是其对偶问题的最优解。性质三：无界性。如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）无可行解。性质四：强对偶性。如果原问题有最优解，则其对偶问题也一定有最优解。性质五：互补松弛型。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。性质六：线性规划的原问题及其对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函

4、数有z=w.b.对偶单纯形法（参考书p64页）设某标准形式的线性规划问题，对偶单纯形表中必须有-0（j=1.n),但(i=1.m)的值不一定为正，当对i=1.m，都有0时，表中原问题和对偶问题均为最优解，否则通过变换一个基变量，找出原问题的一个目标函数值较小的相邻的基解。3）为什么要引入对偶单纯形法从理论上说原始单纯形法可以解决一切线性规划问题，然而实际问题中，由于考虑问题的角度不同，变量设置的不同，便产生了原问题及其对偶问题，对偶问题是原问题从另外一个角度考虑的结果。用对偶单纯形法求解线性规划问题时，当约束条件为“”时，不必引入人工变量，使计算简化。例如，有一线性规划问题：min =12+1

5、6+15 约束条件 将问题改写为求目标函数极大化，化为标准形式有max=-12-16-15+0+0约束条件若用对偶单纯形法，则直接按右边的标准型列出单纯形表求解即可，计算简单。4)例题详解 用对偶单纯形法求解线性规划问题min=15+24+5 先将问题改为第一步 15 24 5 0 0 -2 -1 0 -1 1 0-5 -2 -1 0 1 j 015 24 5 0 0建立初始单纯形表，表中检验行的值全部0，即对其对偶问题而言是一基本可行解。根据原问题和对偶问题之间的对称关系，这时单纯形表中原基变量列数字相当于对偶问题解的非基变量的检验数第二步 由于对偶问题的求解是使目标函数达到最小值所以最优判

6、别准则是当所有检验数大于等于零时为最优（也即这时原问题是可行解）如果不满足这个条件，找出绝对值最大的负检验数，其对应的原问题的基变量即为对偶问题的换入变量。第三步 确定换出变量：=min(-)/=min-24/-6,-5/-1=4因此选作为换入变量。第四步 用换入变量替换对偶问题中的换出变量得到一个新的单纯形表。表中数字计算同用单纯形法时完全一样。新表中对偶问题仍保持基本可行解，原问题基变量列数字相当于对偶问题的检验数。第五步：重复第二四步，一直到找出最优解为止。 15 24 5 0 0 y1 y2 y3 y4 y5 y4 -2 0 -1 1 0 y5 -1 -5 -2 -1 0 1 0 15

7、 24 5 0 0 y2 1/3 0 1 1/6 -1/6 0 y5 -1/3 -5 0 -1/3 1 -8 15 0 1 4 0 y2 1/4 -5/4 1 0 -1/4 1/4 y3 1/2 15/2 0 1 1/2 -3/2 -17/2 15/2 0 0 7/2 3/2此时达到最优, 最优为例题讲解结束，我们可以通过例题的详细求解过程得到对偶单纯形法的算法步骤如下：（参考书第64页） 1、 确定换出基的变量： 对小于零的，令=min，其对应变量为换出基的变量。2、 确定换入基的变量：（1）为使迭代后的表中第r行基变量为正值，因而只有对应<0（j=m+1，n）的非基变量才可以考虑作为

8、换入基的变量；（2）为使迭代后表中对偶问题的解仍为可行解，令=min|<0=为换入基的变量。 设迭代后表中的检验数为 则=（-）-=此时一定有0，下面分两点说明：a. 对0，因（-）0，故0,又因主元素<0,故有0，因此0b. 对<0,因>0,故同样03、 用换入变量替换换出变量，得到一个新的基， 检查是否所有0。如果是，则找到了问题最优解，否则回到第一步重复计算。4、 原问题无可行解的情况：对<0,而对所有j=1.n,有0。因为这种情况下，把表中第r行的约束方程列出有+.+=，因0,又<0,故不可能存在0的解，故原问题无可行解，这时对偶问题的目标函数值无界

9、。4、 总结1） 对比分析单纯形法和对偶单纯形法单纯形法对偶单纯形法原理保证原问题是可行解的情况下向对偶问题可行的方向迭代保证对偶问题是可行解的情况下向原问题可行的方向迭代前提条件所有>=0所有j>=0最优性检验所有j>=0所有>=0迭代原则最大：检验数最大的非基变量为换入变量最小：的最小的为换出变量最小：最小的对应的那个非基变量为换入变量最小：数字最小（负数）对应的那个基变量为换出变量2) 对偶单纯形法优缺点对偶单纯形法的优点：(1) 运用对偶单纯形法时,初始解可以是非可行解,只要检验数全部非正数就可以进行基变换.因此不需要引进人工变量,这样可以简化计算.(2) 应用

10、对偶问题与原问题的关系,对变量较少而约束较多的线性规划问题 ,应用对偶问题与原问题的关系,先变换成对偶问题,再用对偶单纯形法求解,可以减少计算工作量.(3) 灵敏度分析中有时需要用到对偶单纯形法,可使问题的处理简化.2. 对偶单纯形法的缺点：对于大多数线性规划问题而言很难找到一个初始正则基, 对于大多数线性规划问题而言很难找到一个初始正则基,即很难满足使 所有的检验数小于等于零(对偶可行性),因而此法很少单独使用.5、 对偶单纯形法算法流程图开始 结束原问题无可行解进行枢轴运算，列出新的单纯形表1. 用非基变量xs代替基变量xr；2. 对主元行（第r行），令br/ars br，arj/ars arj3. 对主元列（第s列），令1 ars，0 其他元素4. 表中其他列元素aij-arjais/ars aij bi-b