基础运筹学教程(第三版)- 第一章-5 单纯形法.ppt
*从而,有:显然,由于要求XB、XN均满足非负约束,所以下面讨论的均指基可行解。将B-1作用于约束方程,得:代入目标函数,得:于是,检验数变为:对应初始的具有单位矩阵的系数矩阵[AI]:*注意到B-1I=B-1,所以B-1可在各次迭代表上对照初始单位阵I的位置读出。0由于每次迭代只置换一个变量,因此前后两个基阵只改变一列,而前一基阵恒是单位阵,故后一基阵求逆只须将换入变量的对应列向量化为单位向量即可。至此,完成了单纯形法的矩阵描述,从而为下面讨论对偶问题与灵敏度分析提供了理论基础。CICACj→-CBB-1bB-1bbCI-CBB-1ICA-CBB-1A-zB-1IB-1AXBCBXIXAXBCB先取初始单位阵I作为初始基阵B,得初始单纯形表:其中,检验数行可简写为:σ=(CA-CIA0)再选某一基阵B进行迭代,将B-1作用于约束方程,得:B-1AXA+B-1IXI=B-1b,于是有迭代单纯形表:B-1CI-CBB-1CICACj→-CIbbbCI-CBI-1ICA-CII-1A-zIAXICIXIXAXBCB0*-1/21/20122x262-11008x32-1-28-100-4-z0-3/21/20-4-24-z-1/21/44481[1/2]00x501601/412x26001x400268Cj→01216b0268-z31124x502014[8]x40θix5x3x2x1XBCB-1-1/21/8-16420120-z--11/200x50401/8[1/2]1x18通过例子来理解B=?B-1=?B-1=?直接从最初的单纯行表到最后的单纯行表**第一章线性规划*§1-3单纯形法一.线性规划的基本定义二.线性规划解之间的关系三.线性规划解的性质四.单纯形法引例五.单纯形法(SM)原理六.单纯形法的表算七.单纯形法的进一步讨论1.人工变量法2.多最优解的情况八.单纯形法的矩阵描述*1.人工变量法对于标准的线性规划问题:其中,约束方程组的系数矩阵中不含有m阶的单位矩阵,即:其约束方程可以表示为:*引入m个人工变量xn+I,i=1,2,…,m,这m个人工变量便可以构成m阶的单位矩阵,取这m个人工变量为初始基变量,便可得到新的约束方程组:*上式最通常的表示为:其中xn+1,xn+2,…,xn+m即为引入的人工变量。引入人工变量之后,该约束方程组便可得到一个m×m阶的单位矩阵,符合用单纯形法进行计算的初始格式,因此,在引入人工变量后,就很容易进行求解了。*但是,我们必须注意:人工变量是不存在的量,只是为了计算的方便而引入的,因此,在计算的结果中必须要剔除人工变量,所得到的解才是原问题的最优解。如果所得的最优解中,每个人工变量都是0,那么自然就可以剔除所增加的人工变量,得到原规划问题的最优解;如果至少有一个人工变量的取值是大于0的,说明什么?出现这种情况,则说明:原线性规划无可行解。*我们介绍两种特殊的方法来避免人工变量取正值的情况。(1)大M法基本思想:在有最优解的线性规划问题中,由于人工变量在最优解中的取值必须为0,所以,通过引入一个无穷大的正数M来将原目标函数进行修正。这个无穷大的正数M通常称为罚因子。*具体做法是:考虑如下新的线性规划问题:如果最优解中含有正的人工变量,由上式的结构特点可知:目标函数不可能实现最大化。这时,原线性规划问题无可行解。取无穷大正数M作为罚因子的作用就是迫使所有的人工变量都为0。这样,新的线性规划问题就和原来的线性规划问题完全等价。*例用大M法求解例2中的环保线性规划问题。解:由例2得该问题的数学模型为:*引进剩余变量,松弛变量,人工变量,以及无穷大正数M,得新线性规划模型为:*用单纯形表表示为:Cj→-1000-8000000-M-MΘiCBXBbx1x2