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

《单纯形法原理表格形式和人工变量法PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《单纯形法原理表格形式和人工变量法PPT讲稿.ppt（19页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、单纯形法原理表格形式和人工变量法第1页，共19页，编辑于2022年，星期五2、举例第2页，共19页，编辑于2022年，星期五步骤：1、化标准型（SLP）第3页，共19页，编辑于2022年，星期五2、找初始基可行解3、判断第4页，共19页，编辑于2022年，星期五4、换基迭代*换基：找一个非基变量作为换入变量，同时 确定一个基变量为换出变量。*依据原则：1)新的基可行解能使目标值增加；2)新的基仍然是可行基。(1)确定换入变量：变量下标最小的（勃兰特法则）变量对应的价值系数最大的第5页，共19页，编辑于2022年，星期五(2)确定换出变量第6页，共19页，编辑于2022年，星期五*迭代（求新的基

2、可行解）主元素第7页，共19页，编辑于2022年，星期五5、判断代入目标函数得第8页，共19页，编辑于2022年，星期五6、确定进基变量和出基变量第9页，共19页，编辑于2022年，星期五7、换基迭代第10页，共19页，编辑于2022年，星期五8、判断代入目标函数：最优解：第11页，共19页，编辑于2022年，星期五二、表格形式的单纯形法 1、表的结构及含义第12页，共19页，编辑于2022年，星期五 2、计算步骤1)化标准型，建立初始单纯形表;2)计算非基变量的检验系数，若所有检验系数都小于等于零，则已得到最优解。否则转 一步;4)换基迭代，求出新的基可行解，转步骤二;第13页，共19页，编

3、辑于2022年，星期五 10 5 0 0 0 0 3 4 1 0 5 2 0 1 9 8第14页，共19页，编辑于2022年，星期五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页，编辑于2022年，星期五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页，编辑于2

4、022年，星期五三、人工变量法1、思路人为构造一个单位矩阵第17页，共19页，编辑于2022年，星期五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页，编辑于2022年，星期五*若基变量中有非零的人工变量，则该LP无可行解。第19页，共19页，编辑于2022年，星期五