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

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

1、单纯形法原理表格形式和人工变量法第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、确定

2、进基变量和出基变量第9 页，本讲稿共19 页7、换基迭代第10 页，本讲稿共19 页8、判断代入目标函数：最优解：第1 1 页，本讲稿共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 bcB xB x1 x2 x3 x4 0 5x3x1 c 0 1 1

3、/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 页cj 3-2 5 0-M-Mb cB xb x1 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 j 3-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 页