纯形法原理表格形式和人工变量法.ppt

单纯形法,一、单纯形原理,*可行域的极点对应LP问题的基可行解*LP的最优解一定可以在基可行解中找到,1、思路,2、举例,步骤：,1、化标准型（SLP）,2、找初始基可行解,3、判断,4、换基迭代,*换基：找一个非基变量作为换入变量，同时 确定一个基变量为换出变量。,*依据原则：,1)新的基可行解能使目标值增加；,2)新的基仍然是可行基。,(1)确定换入变量：,变量下标最小的（勃兰特法则）变量对应的价值系数最大的,(2)确定换出变量,*迭代（求新的基可行解）,主元素,5、判断,代入目标函数得,6、确定进基变量和出基变量,7、换基迭代,8、判断,代入目标函数：,最优解：,二、表格形式的单纯形法,1、表的结构及含义,2、计算步骤,1)化标准型，建立初始单纯形表;,2)计算非基变量的检验系数，若所有检验系数都小于等于零，则已得到最优解。否则转 一步;,4)换基迭代，求出新的基可行解，转步骤二;,求出a,b,c,d,e,f,g的值。,1、z=10=02+5aa=2,2、c=0,d=1,b=0,f=0;,3、g=0-(0 5)(1/5 1)=-5,4、3-(0 5)(0 e)=-1e=4/5,小结：单纯形法的前提条件是SLP存在一个初始的单位基矩阵。,三、人工变量法,1、思路人为构造一个单位矩阵,人工变量,人工变量,x5x4,-M,0,-3-2 1 0 1-2 1,1 1 1/2 1 0 1/2 3/2,j,3-3M 2-2M 5+M 0 0-3M,13,*若基变量中有非零的人工变量，,则该LP无可行解。,