资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第九讲,修正单纯形法（,1,）,大约在,1954,年，,Dantzig,和他的同事就发现了更有效的单,纯形法。,我们知道，在单纯,(,扩展,),表格中，共有,3,组元素，分别,与矢量组“,a,1,，,，,a,n,”,，“,b,”,及“,e,1,e,m,”,相对应，如果说,前面讲的习惯用的一般单纯形表格法可只采用左边两组,的话，那么，修正单纯形法在运算迭代中只应用右边两,组，下面就具体阐述该种方法。,仍假设：,AX,=,b,，,X,0,，,C,T,X,=min (1),且,A,、,b,、,C,已知，属非退化情形，计算过程，将始终,用到,A,，,B,，,C,这些原始数据，故需保存。每一个阶段仍,用单纯形表格迭代，只用右边两组，即,m,+1,列，每个表,格与当前基础解集相对应（,j,1,，,，,j,m,）：,第九讲,修正单纯形法（,2,）,t,10,t,m,0,u,11,u,1,m,u,m,1,u,mm,z,0,y,1,y,m,(2),其中：,t,i,0,给出当前基础解,u,ij,给出当前基础阵之逆,z,0,给出当前基础解费用,y,i,给出当前基础阵之联立方程解,Y,T,M,=,(3),第九讲,修正单纯形法（,3,）,(5),其中,当前基础解的目标系数。,表格的起步可根据两阶段法的第,1,阶段之初始基础解表格开始，即：,t,i,0,=,b,i,，,u,ij,=,ij,，,z,0,=,b,i,，,y,i,=1 (4),第,1,阶段结束后，第,2,阶段开始的表格需加以修改，唯一修改处是最末一行，这是由于目标函数发生了变化,z,0,和,y,i,计算公式为：,第九讲,修正单纯形法（,4,）,(6),如果,z,j,c,j,，则令,j,=,s,，并作为支点列。,如果,z,j,c,j,，则去试探其它非基础列,j,，假若所有非基础,列,j,的,z,j,c,j,，则已达到最优解，其最优解值为：,下面来阐述表格的迭代过程。在一般单纯形表格法中，每次检验元素,z,j,c,j,全部算出，然后寻找支点列，而在修正单纯形表格中，不需一次计算全部检验元素，而是逐个计算。设,j,属非基础集，则：,第九讲,修正单纯形法（,5,）,(7),其最小费用为,z,0,和最优对偶解为,y,T,。,否则，计算,z,j,(,按,6,式,),，找出,z,j,c,j,，并令,j,=,s,，然后处理如下：,首先，计算单纯形表的支点列,s,：,(8),第九讲,修正单纯形法（,6,）,如果所有,t,is,0,，则最优解不存在，最优目标无限，即，,(9),费用,若存在,t,is,0,可求出支点行：,(10),第九讲,修正单纯形法（,7,）,求出支点行后，就可进行修正单纯形表格的转换，其表格转换元素的计算只需计算后面,m,+1,列，即：,新行,r,= (,原行,r,)/,t,rs,(11),新行,i,(,i,r,) = (,原行,i,),i,(,原行,r,) (12),其中：,最后，用,a,s,取代旧表格,V,r,中表示的基矢量。,第九讲,修正单纯形法（,8,）,例,1-23,已知线性规划为：,解, 1,）应用阶段,1,，求出初始基础可行解,构成新规划：,A,X, =,b,，,X,0,C,T,X,=min,第九讲,修正单纯形法（,9,）,令人工变量作为第,1,个基础可行解之基础变量，其对应的表格为：,e,1,e,2,b,e,1,e,2,5 1 0,13 0 1,18 1 1,第九讲,修正单纯形法（,10,）,检验非基础变量,a,1,，,a,2,，,a,3,能否进基，可按任何次序检验。先检验,a,1,：,第九讲,修正单纯形法（,11,）,e,1,e,2,a,1,b,e,1,e,2,1 5 1 0,4 13 0 1,5 18 1 1,min5/1,，,13/4 = 13/4,r,= 2,。,支点元素为,t,21,，,进行变换使,(t,1,),列中：,t,21,=1,，,t,11,=0,，,z,1,c,1,= 0,，得：,将,(,t,1,),临时放入表格中，以便求出支点行，,第九讲,修正单纯形法（,12,）,当前表格对应的基础矢量为,e,1,和,a,1,。,再次校验非基础矢量，看是否可进入基础矢量，任意选择,a,3,检验,。,e,1,a,1,a,1,b,e,1,e,2,0 7/4 1 -1/4,1 13/4 0 1/4,0 7/4 1 -1/4,第九讲,修正单纯形法（,13,）,将,(,t,3,),加入修正单纯形表格中，并求出支点行,r,。,e,1,a,1,a,3,b,e,1,e,2,3/2 7/4 1 -1/4,3/2 13/4 0 1/4,3/2 7/4 1 -1/4,第九讲,修正单纯形法（,14,）,即,e,1,离开基，,a,3,进基，将表格变换得：,a,3,a,1,a,3,b,e,1,e,2,1 7/6 2/3 -1/6,0 3/2 -1 1/2,0 0 0 0,从表中看出，,故阶段,1,结束，得出初始基础可行解为,x,3,=7/6,，,x,1,=3/2,，,x,2,=0,。,第九讲,修正单纯形法（,15,）,2,）现进行阶段,2,，阶段,2,的第,1,个表格可借用阶段,1,的最后表格，仅仅将最后一行加以修改。此时：,A,，,B,，,C,恢复到原问题数值，这时,C,T,=(7,，,1,，,1),。其初始表格为：,a,3,a,1,b,e,1,e,2,7/6 2/3 -1/6,3/2 -1 1/2,35/3 -19/3 10/3,其中，,第九讲,修正单纯形法（,16,）,现判断非基矢量,a,2,是否应进入基础解集。,第九讲,修正单纯形法（,17,）,即支点行,r,= 1,，,a,3,离开，支点元素,t,12,=1/2,。,将,a,2,加入表格并转换,a,2,b,e,1,e,2,1/2 7/6 2/3 -1/6,1/2 3/2 -1 1/2,3 35/3 -19/3 10/3,将,a,2,对应的,t,2,列变为,t,12,=1,，,t,22,=0,，,z,2,c,2,=0,得出新表格为：,第九讲,修正单纯形法（,18,）,目前基础矢量为,a,2,和,a,1,。再检验非基矢量,a,3,：,a,2,b,e,1,e,2,1 7/3 4/3 -1/3,0 1/3 -5/3 2/3,0 14/3 -31/3 13/3,a,2,a,1,故已得最优解 ：,x,2,= 7/3,，,x,1,= 1/3,y,1,= -31/3,，,y,2,= 13/3,， 且,z,= 14/3,第九讲,修正单纯形法（,19,）,与此相应的有另一种方法,对偶单纯型法，它的迭代原则是：在保证“优化”前提下，寻找原问题可行解，即在保证对偶可行解基础上，逐步找出原规划可行解。这些概念体现在表格上，即使每一步表格的检验行的元素,(,z,j,c,j,),都,0,，而表格的,b,列元素可能,0,。迭代的原则就是逐步将,B,列元素全变为,0,的值（求得最优解）或证明无可行解。,对偶单纯形的迭代思路与前述单纯形法一样，此处不再赘述，感兴趣者，可参阅有关书籍。,
展开阅读全文