单纯形法原理表格形式和人工变量法精选PPT.ppt

单纯形法原理表格形式和人工变量法第1页，此课件共19页哦2、举例第2页，此课件共19页哦步骤：1、化标准型（SLP）第3页，此课件共19页哦2、找初始基可行解3、判断第4页，此课件共19页哦4、换基迭代*换基：找一个非基变量作为换入变量，同时 确定一个基变量为换出变量。*依据原则：1)新的基可行解能使目标值增加；2)新的基仍然是可行基。(1)确定换入变量：变量下标最小的（勃兰特法则）变量对应的价值系数最大的第5页，此课件共19页哦(2)确定换出变量第6页，此课件共19页哦*迭代（求新的基可行解）主元素第7页，此课件共19页哦5、判断代入目标函数得第8页，此课件共19页哦6、确定进基变量和出基变量第9页，此课件共19页哦7、换基迭代第10页，此课件共19页哦8、判断代入目标函数：最优解：第11页，此课件共19页哦二、表格形式的单纯形法 1、表的结构及含义第12页，此课件共19页哦 2、计算步骤1)化标准型，建立初始单纯形表;2)计算非基变量的检验系数，若所有检验系数都小于等于零，则已得到最优解。否则转 一步;4)换基迭代，求出新的基可行解，转步骤二;第13页，此课件共19页哦 10 5 0 0 0 0 3 4 1 0 5 2 0 1 9 8第14页，此课件共19页哦cj 5 3 0 0 bcBxB x1 x2 x3 x4 0 5x3x1 c 0 1 1/5 d e 0 1 2 a j b -1 f gZ=10 求出a,b,c,d,e,f,g的值。第15页，此课件共19页哦1、z=10=02+5aa=2 2、c=0,d=1,b=0,f=0;3、g=0-(0 5)(1/5 1)=-54、3-(0 5)(0 e)=-1e=4/5小结：单纯形法的前提条件是SLP存在一个初始的单位基矩阵。第16页，此课件共19页哦三、人工变量法1、思路人为构造一个单位矩阵第17页，此课件共19页哦cj3 -2 5 0 -M -Mb cBxbx1 x2 x3 x4 x5 x6-M-Mx5x61 2 3 4 1 02 2 1 2 0 1 737/43/2j3+3M-2+4M 5+4M 6M 0 0 x5x4-M 0-3 -2 1 0 1 -2 1 1 1 1/2 1 0 1/2 3/2 j3-3M 2-2M 5+M 0 0 -3M13 5 3 x3 x10 2/5 1 6/5 2/5 1/51 4/5 0 2/5 -1/5 2/511/52/5 j0 -32/5 0 -36/5 7/5-M 11/5-M第18页，此课件共19页哦*若基变量中有非零的人工变量，则该LP无可行解。第19页，此课件共19页哦