1-3-单纯形法完成课件.ppt

1、 3.53.5人工变量及其处理方法人工变量及其处理方法 引用人工变量是用单纯形法求解线性规划问题时解决可行解问题的常用方法。人工变量法的基本思路是若原线性规划问题的系数矩阵中没有单位向量，则在每个约束方程中加入一个人工变量便可在系数矩阵中形成一个单位向量。由于单位矩阵可以作为基阵，因此可选加入的人工变量为基变量。然后，再通过基变换，使得基变量中不含非零的人工变量。如果在最终的单纯形表中还存在非零的人工变量，这表示无可行解。对于如下线性规划问题0,0,11112212111111mnnnmnmnmnnnnxxxxbxaxabxaxabxaxannxcxcxcz.max2211首先分别对每个约束方

2、程中加入一个人工变量 这样我们就可选 为基变量，令非基变 =0便可以得到一个初始基可行解 nnxcxcxcz.max22110,0,1111222121111111mnnnmmnnmnmnnnnnnxxxxbxxaxabxxaxabxxaxamnx1xnx1xX(0)=(0，0，0b1，b2bm)T3.5.13.5.1约束方程为约束方程为“=”=”或或“=”=”的情形（的情形（加人工变量）人工变量法（确定初始可行基）：0,0,1111222121111111mnnnmmnnmnmnnnnnnxxxxbxxaxabxxaxabxxaxa原约束方程：AX=b加入人工变量：xn+1，xn+m人工变量

3、是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解。标准型：标准型：max z=3 3x1-x2-x3 s.t.01 23 2 411 2 513153214321x,xxxxxxxxxxx其中第其中第2、3个约束方程中无明显基变量，分别加上人工变个约束方程中无明显基变量，分别加上人工变x6,x7,01 23 2411 2 71731653214321x,xxxxxxxxxxxxx 这时，初始基和初始基可行解很明显。X(0)=(0，0，0，11，0，3，1)T不满足

4、原来的约束条件。如何使得可从X(0)开始，经迭代逐步得到x6=0，x7=0 的基可行解，从而求得问题的最优解，有两种方法：3.5.2 3.5.2 大大M M法（又称惩罚法）法（又称惩罚法）由于人工变量对目标函数有很大的负影响，只要人工变量取值大于0，目标函数值就不可能是最优。单纯形法的寻优机制会自动将人工变量赶到基外，从而可以找到原问题的一个可行基。这种方法我们通常称其为大M法，又称惩罚法。原理：当目标函数为max z，对应的人工变量目标系数为M;当目标函数为min z，对应的人工变量目标系数为+M,其中 M 为充分大的正数。根据最优检验数判别定理进行基的转换，使得人工变量逐渐换出基底，再寻求

5、原问题的最优解。解解 先化标准型例3.12 用单纯形法求解线性规划问题313maxxxz12312323123421.39,0 xxxxxxstxxx x x76543100003maxxxxxxxz123412352312345421.39,0 xxxxxxxxstxxx x x x x然后，再添加人工变量，将原线性规划问题变为例2.12用单纯形法求解的过程见下表76543100003maxxxxxxxz1234123562371234567421.39,0 xxxxxxxxxstxxxx x x x x x x3.5.3 两阶段法两阶段法 原理：当目标函数为max Z，对应的人工变量目标系

6、数为-1;当目标函数为min Z，对应的人工变量目标系数为+1。第一阶段 将原目标系数暂时取零值。根据最优检验数判别定理进行基的转换，使得人工变量逐渐换出基底。第二阶段 再去掉人工变量对应的列，恢复原线性规划问题的目标系数，寻原问题的最优解。第第一一阶阶段段的的单单纯纯形形表表如如下下：第二阶段运算:3.5.4 3.5.4 线性规划问题解的讨论一、无可行解一、无可行解 max z=2xmax z=2x1 1+4x+4x2 2 x x1 1+x+x2 2 1010 2x 2x1 1+x+x2 2 4040 x x1 1,x,x2 2 0 0 x1x2CBXBbX3 0-1 0 0 0 0 -1

7、x1 x2 x3 x4 x540 2 1 0 -1 110 1 1 1 0 0cj1040/2x1 x5 0-1 20 0 -1 -2 -1 110 1 1 1 0 0 cj-zj0 -1 -2 -1 0cj-zj2 1 0 -1 0 Z0=-40Z1=-20两阶段法两阶段法例:max z=3xmax z=3x1 1+4x+4x2 2 x x1 1+x+x2 2 4040 2x 2x1 1+x+x2 2 6060 x x1 1-x-x2 2 =0=0 x x1 1,x,x2 2 0 0 x1x2 0 x3 40 1 1 1 0 0 0 x4 60 2 1 0 1 -1 -M x5 0 1 -1

8、 0 0 1 0 x3 40 0 2 1 0 0 x4 60 0 3 0 1 3 x1 0 1 -1 0 0 3+M 4-M 0 0 0 zj-cj 0 0 0 -7/3 zj-cj 0 x3 0 0 0 1 -1/3 4 x2 20 0 1 0 1/3 3 x1 20 1 0 0 1/3 cj 3 4 0 0 -M CB XB b x5 x1 x2 x3 x4 0 7 0 0 zj-cj 0 0 -3.5 0 zj-cj 4 x2 20 0 1 1/2 0 0 x4 0 0 0-3/2 1 3 x1 20 1 0 1/2 0 例 max z=3xmax z=3x1 1+5x+5x2 2 3x

9、 3x1 1+5x+5x2 2 1515 2x 2x1 1+x+x2 2 5 5 2 2x x1 1+2x+2x2 2 1111 x x1 1,x,x2 2 0 0。CBXBbx3 000 3 5 0 0 0 x1 x2 x3 x4 x5 5 2 1 0 1 015 3 5 1 0 035 11/2x2 x4x5 5003 3/5 1 1/5 0 02 7/5 0 -1/5 1 0 5 4/5 0 -2/5 0 1 cj-zj 0 0 -1 0 0cj-zj3 5 0 0 0 Z0=011 2 2 0 0 1Z1=15x1x2四、无（有）界解 max z=xmax z=x1 1+x+x2 2

10、-2x -2x1 1+x+x2 2 4 4 x x1 1-x-x2 2 2 2 -3 -3x x1 1+x+x2 2 3 3 x x1 1,x,x2 2 0 0练习：写出单纯形表练习：写出单纯形表,分析检验数分析检验数 与系数关系并画图验证。与系数关系并画图验证。线性规划解除有唯一最优解的情况外，还有如下几种情况人工人工变量变量不能不能从基从基底中底中换出换出基可行基可行解中非解中非零元素零元素个数小个数小于基变于基变量数量数检验数检验数中零的中零的个数多个数多于基变于基变量的个量的个数数检验数大检验数大于零，但于零，但对应列元对应列元素小于等素小于等于零，无于零，无换出变量换出变量唯一最优解

11、唯一最优解 否 否否 是是是添加松弛变量添加松弛变量、人工变人工变量量 列出初始单纯形表列出初始单纯形表计算非基变量计算非基变量各列的检验数各列的检验数j所有所有j 0基变量中基变量中有非零的有非零的人工变量人工变量某非基某非基变量检变量检验数为验数为零零无可行解无可行解无穷多最优解无穷多最优解对任一对任一j 0有有aik0无界解无界解令令k=maxjx xk k为换入变量为换入变量对 所 有对 所 有 ai k 0 计 算计 算i i=bi/aik令令l=min=mini i 第第l l个基变量个基变量为换出变为换出变量，量，alk为主元素为主元素 迭代运算迭代运算.用非基变量用非基变量xk

12、替换换出变量替换换出变量 .对主元素行对主元素行(第第l行行)令令 bl/alkbl;alj/alkajl对主元素列对主元素列(第第k列列)令令1aalklk;0;0其它元其它元素表中其它行列元素素表中其它行列元素令令 aij-ali/alkaikaaijij b bi i-b-bl l/a/alklka aikikbbi i j-alj/alk k j否对目标函数求极大值标准型线性规划对目标函数求极大值标准型线性规划问题，单纯形法计算步骤的框图：问题，单纯形法计算步骤的框图：练习 下表中给出某线性规划问题计算过程中的一个单纯形表，目标函数为Max Z=28x4+x5+2x6,约束条件为，表中x1,x2,x3为松弛变量，表中解的目标函数值为Z=14（1）求ag的值；（2）判断给出的解是否为最优解；x1x2x3x4x5x6 x6 a x2 5 x4 0 3 6 00de-14/3 2 f00115/20100 cj-zjbc00-1g练习 下表是某求极大值线性规划问题的初始表及迭代后的表，x4,x5为松弛变量，求表中的al的值及各下表mt的值x1x2x3x4x5 xm 6 xn 1b-1c3de1001 cj-zja 1-200 xs f xt 4gh 2i-1101 cj-zj07jkl课后作业 P45 1.5（1）（2）大M法 （3）（4）两阶段法 作业要求上交