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

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

1、单纯形法原理表格形式和人工变量法第一页，讲稿共十九页哦2、举例第二页，讲稿共十九页哦步骤：1、化标准型（SLP）第三页，讲稿共十九页哦2、找初始基可行解3、判断第四页，讲稿共十九页哦4、换基迭代*换基：找一个非基变量作为换入变量，同时 确定一个基变量为换出变量。*依据原则：1)新的基可行解能使目标值增加；2)新的基仍然是可行基。(1)确定换入变量：变量下标最小的（勃兰特法则）变量对应的价值系数最大的第五页，讲稿共十九页哦(2)确定换出变量第六页，讲稿共十九页哦*迭代（求新的基可行解）主元素第七页，讲稿共十九页哦5、判断代入目标函数得第八页，讲稿共十九页哦6、确定进基变量和出基变量第九页，讲稿共

2、十九页哦7、换基迭代第十页，讲稿共十九页哦8、判断代入目标函数：最优解：第十一页，讲稿共十九页哦二、表格形式的单纯形法 1、表的结构及含义第十二页，讲稿共十九页哦 2、计算步骤1)化标准型，建立初始单纯形表;2)计算非基变量的检验系数，若所有检验系数都小于等于零，则已得到最优解。否则转 一步;4)换基迭代，求出新的基可行解，转步骤二;第十三页，讲稿共十九页哦 10 5 0 0 0 0 3 4 1 0 5 2 0 1 9 8第十四页，讲稿共十九页哦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 求

3、出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)=-54、3-(0 5)(0 e)=-1e=4/5小结：单纯形法的前提条件是SLP存在一个初始的单位基矩阵。第十六页，讲稿共十九页哦三、人工变量法1、思路人为构造一个单位矩阵人工变量人工变量第十七页，讲稿共十九页哦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第十八页，讲稿共十九页哦*若基变量中有非零的人工变量，则该LP无可行解。第十九页，讲稿共十九页哦