1 / 8 对偶单纯形法与单纯形法对比分析1.教学目标:通过对偶单纯形法的学习,加深对对偶问题的理解2.教学内容:1)对偶单纯形法的思想来源2)对偶单纯形法原理3.教学进程:1)讲述对偶单纯形法解法的来源:所谓对偶单纯形法,就是将单纯形法应用于对偶问题的计算,该方法是由美国数学家 C.莱姆基于 1954 年提出的,它并不是求解对偶问题解的方法,而是利用对偶理论求解原问题的解的方法。2)为什么要引入对偶单纯形法:单纯形法是解线性规划的主要方法,对偶单纯形法则提高了求解线性规划问题的效率,因为它具有以下优点:(1)初始基解可以是非可行解, 当检验数都为负值时 , 就可以进行基的变换 , 不需加入人工变量 , 从而简化计算;(2)对于变量多于约束条件的线性规划问题, 用对偶单纯形法可以减少计算量,在灵敏度分析及求解整数规划的割平面法中, 有时适宜用对偶规划单纯形法。由对偶问题的基本性质可以知道,线性规划的原问题及其对偶问题之间存在一组互补的基解, 其中原问题的松弛变量对应对偶问题的变量,对偶问题的剩余变量对应原问题的变量;这些互相对应的变量如果在一个问题的解中是基变量,则在另一问题的解中是非基变量; 将这对互补的基解分别代入原问题和对偶问题的目标函数有 z=w。据此可知,用单纯形法求解线性规划问题时,在得到原问题的一个基可行解的同时, 在检验数行得到对偶问题的一个基解,并且将两个解分别代入各自的目标函数时其值相等。我们知道,单纯形法计算的基本思路是保持原问题为可行解(这时一般其对偶问题为非可行解)的基础上,通过迭代,增大目标函数,当其对偶问题的解也为可行解时, 就达到了目标函数的最优值。 那么对偶单纯形法的基本思想可以理解为保持对偶问题为可行解 (这时一般原问题为非可行解) 的基础上,通过迭代,减小目标函数, 当原问题也达到可行解时, 即达到了目标函数的最优值。其实对偶单纯形法本质上就是单纯形法, 只不过在运用时需要将单纯形表旋转一下而已。一. 单纯形法和对偶单纯性法单纯形法是求解线性规划的主要方法, 单纯形表则是单纯形法和对偶单纯形法的运算工具。设线性规划问题为Max njjj xcZ12 / 8 ),....,1(0),...,1(..1njmitsxbxajnjijij⑴将其化为标准形式,得Max Z= CXs.t. 0, XXssXbAX⑵其中),(CCNBC,)0,...,0,0(0C N,),(NBA,XXNBX,则其对应的线性约束转换为011XBXBXsNB,XBXBBXsNBb111,代入目标函数得XBCXBCCBCSBN...