第二章单纯形法原理+表格形式和人工变量法.ppt

《第二章单纯形法原理+表格形式和人工变量法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、单纯形法一、单纯形原理*可行域的极点对应LP问题的基可行解*LP的最优解一定可以在基可行解中找到1、思路2、举例步骤：1、化标准型（SLP）2、找初始基可行解3、判断4、换基迭代*换基：找一个非基变量作为换入变量，同时确定一个基变量为换出变量。*依据原则：1)新的基可行解能使目标值增加；2)新的基仍然是可行基。(1)确定换入变量：变量下标最小的（勃兰特法则）变量对应的价值系数最大的(2)确定换出变量*迭代（求新的基可行解）主元素5、判断→代入目标函数得6、确定进基变量和出基变量7、换基迭代8、判断代入目标函数：最优解：二、表格形式的单纯形法1、表的结构及含义2、计算步骤1)化标准型，

2、建立初始单纯形表;2)计算非基变量的检验系数，若所有检验系数都小于等于零，则已得到最优解。否则转一步;4)换基迭代，求出新的基可行解，转步骤二;10500003410520198cj5300bcBxBx1x2x3x405x3x1c011/5de012aδjb-1fgZ=10求出a,b,c,d,e,f,g的值。1、z=10=0×2+5×a→a=22、c=0,d=1,b=0,f=0;3、g=0-(05)(1/51)’=-54、3-(05)(0e)’=-1→e=4/5小结：单纯形法的前提条件是SLP存在一个初始的单位基矩阵。三、人工变量法1、思路——人为构造一个单位矩阵人工变量人工变量cj

3、3-250-M-MbθcBxbx1x2x3x4x5x6-M-Mx5x623410221201737/43/2δj3+3M-2+4M5+4M6M↑00→x5x4-M0-3-2101-21111/2101/23/2δj3-3M–2-2M5+M00-3M↑→13…53x3x102/516/52/51/514/502/5-1/52/511/52/5δj0-32/50-36/5–7/5-M–11/5-M*若基变量中有非零的人工变量，则该LP无可行解。