《教学课件PPT修正单纯形法.ppt》由会员分享,可在线阅读,更多相关《教学课件PPT修正单纯形法.ppt(19页珍藏版)》请在三一办公上搜索。
1、第九讲 修正单纯形法(1),大约在1954年,Dantzig和他的同事就发现了更有效的单纯形法。我们知道,在单纯(扩展)表格中,共有3组元素,分别与矢量组“a1,an”,“b”及“e1em”相对应,如果说前面讲的习惯用的一般单纯形表格法可只采用左边两组的话,那么,修正单纯形法在运算迭代中只应用右边两组,下面就具体阐述该种方法。仍假设:AX=b,X0,CTX=min(1)且A、b、C已知,属非退化情形,计算过程,将始终用到A,B,C这些原始数据,故需保存。每一个阶段仍用单纯形表格迭代,只用右边两组,即m+1列,每个表格与当前基础解集相对应(j1,jm):,第九讲 修正单纯形法(2),其中:ti0
2、给出当前基础解 uij给出当前基础阵之逆 z0给出当前基础解费用 yi给出当前基础阵之联立方程解YTM=(3),第九讲 修正单纯形法(3),(5),其中 当前基础解的目标系数。,表格的起步可根据两阶段法的第1阶段之初始基础解表格开始,即:ti0=bi,uij=ij,z0=bi,yi=1(4)第1阶段结束后,第2阶段开始的表格需加以修改,唯一修改处是最末一行,这是由于目标函数发生了变化z0和yi计算公式为:,第九讲 修正单纯形法(4),(6),如果zj cj,则令j=s,并作为支点列。如果zj cj,则去试探其它非基础列j,假若所有非基础列j的zj cj,则已达到最优解,其最优解值为:,下面来阐
3、述表格的迭代过程。在一般单纯形表格法中,每次检验元素zjcj全部算出,然后寻找支点列,而在修正单纯形表格中,不需一次计算全部检验元素,而是逐个计算。设j属非基础集,则:,第九讲 修正单纯形法(5),(7),其最小费用为z0和最优对偶解为yT。否则,计算zj(按6式),找出zj cj,并令j=s,然后处理如下:首先,计算单纯形表的支点列s:,(8),第九讲 修正单纯形法(6),如果所有tis0,则最优解不存在,最优目标无限,即,,(9),费用,若存在tis0,可求出支点行:,(10),第九讲 修正单纯形法(7),求出支点行后,就可进行修正单纯形表格的转换,其表格转换元素的计算只需计算后面m+1列
4、,即:新行r=(原行r)/trs(11)新行i(i r)=(原行i)i(原行r)(12)其中:,最后,用as取代旧表格Vr中表示的基矢量。,第九讲 修正单纯形法(8),例1-23 已知线性规划为:,解 1)应用阶段1,求出初始基础可行解构成新规划:A X=b,X 0,CTX=min,第九讲 修正单纯形法(9),令人工变量作为第1个基础可行解之基础变量,其对应的表格为:,第九讲 修正单纯形法(10),检验非基础变量a1,a2,a3能否进基,可按任何次序检验。先检验a1:,第九讲 修正单纯形法(11),min5/1,13/4=13/4 r=2。支点元素为t21,进行变换使(t1)列中:t21=1,
5、t11=0,z1 c1=0,得:,将(t1)临时放入表格中,以便求出支点行,,第九讲 修正单纯形法(12),当前表格对应的基础矢量为e1和a1。再次校验非基础矢量,看是否可进入基础矢量,任意选择a3检验。,第九讲 修正单纯形法(13),将(t3)加入修正单纯形表格中,并求出支点行r。,第九讲 修正单纯形法(14),即e1离开基,a3进基,将表格变换得:,从表中看出,故阶段1结束,得出初始基础可行解为x3=7/6,x1=3/2,x2=0。,第九讲 修正单纯形法(15),2)现进行阶段2,阶段2的第1个表格可借用阶段1的最后表格,仅仅将最后一行加以修改。此时:A,B,C恢复到原问题数值,这时CT=
6、(7,1,1)。其初始表格为:,其中,,第九讲 修正单纯形法(16),现判断非基矢量a2是否应进入基础解集。,第九讲 修正单纯形法(17),即支点行r=1,a3离开,支点元素t12=1/2。将a2加入表格并转换,将a2对应的t2列变为t12=1,t22=0,z2c2=0得出新表格为:,第九讲 修正单纯形法(18),目前基础矢量为a2和a1。再检验非基矢量a3:,故已得最优解:x2=7/3,x1=1/3y1=-31/3,y2=13/3,且z=14/3,第九讲 修正单纯形法(19),与此相应的有另一种方法对偶单纯型法,它的迭代原则是:在保证“优化”前提下,寻找原问题可行解,即在保证对偶可行解基础上,逐步找出原规划可行解。这些概念体现在表格上,即使每一步表格的检验行的元素(zjcj)都0,而表格的b列元素可能0。迭代的原则就是逐步将B列元素全变为0的值(求得最优解)或证明无可行解。对偶单纯形的迭代思路与前述单纯形法一样,此处不再赘述,感兴趣者,可参阅有关书籍。,