《纯型表格算法》PPT课件.ppt

第四讲 单纯型表格算法,1 与基础解对应的单纯型表格 2 新基础解表格与原表格的关系3 如何选择支点行4 如何选择支点列,5 举例分析,1 与基础解对应的单纯型表格（1）,关于单纯形法概念，以前已讲过，本章讲具体计算步骤。该计算方法在计算机上计算。令A为mn矩阵，mn,行线性独立，即秩为m。非退化线性规划的标准形式为：AX=b，X0，CTX=min(1)如果b是A的不少于m列的线性组合，则称非退化形式。设从 阶段2开始计算，即设已获得初始可行解X（这需阶段1，而 寻找第1个初始可行解亦需用到阶段2算法）。,1 与基础解对应的单纯型表格（2）,设已有一个基础可行解X，只依赖于m列aj(j=1,m)，则有 xj0，jB，B=j1，jm(2)令矢量 Vi=aji(i=1,2,m)(3)则，V1，V2，Vm即是当前基础矩阵M的列矢量。现把A阵每一列都用基础列表达：aj=t1jV1+t2jV2+tmjVm(j=1,2,n)(4)同样，b可写成：b=t10V1+t20V2+tm0Vm(5)这样，便可给出一个单纯形表格(tij)，i=1,m；j=1,2,n,0(6),1 与基础解对应的单纯型表格（3）,例1-18 A=b=令当前基础矢量是第3列和第1列。即V1=a3，V2=a1，则表格为：,1 与基础解对应的单纯型表格（4）,第2列即为：a3a1=a2(8)最后1列为：a3+2a1=b(9)这就给出基础解分量 x3=1，x1=2，x2=0 扩充单纯形表格：前述表格中的元素仅是把A阵矢量和b表达为基础矢量线性组合时的系数，为方便，现又增加uij，其含义是把m个单位矢量e1(1,0,0,)，e2(0,1,0,)，em(0,0,1)表达成基本矢量的线性组合，即：ej=(j=1,2,m)(10),1 与基础解对应的单纯型表格（5）,于是，扩充的单纯形表格如下：因为单位矢量ej(j=1,m)构成一个标准单位矩阵I，而Vi是基础矩阵M的列，根据式(10)知，I=MUU=M1。因此扩充表格中的uij是当前基础阵之逆阵。,1 与基础解对应的单纯型表格（6）,同样式(4)和(5)也可写成矩阵的形式：A，b=MT(13)其中，T=tij(i=1,m，j=1,n,0)，于是扩充表格可写成：T；U=M1A，b；I(14)例1-19 例1-18的基础矩阵为：M=a3，a1=,1 与基础解对应的单纯型表格（7）,因此，U=M1=uij则扩充表格为：(15),1 与基础解对应的单纯型表格（8）,表格中，第一部分为A阵所有列关于当前基础列之表达式。第二部分为当前基础解的正分量。第三部分为当前基础阵之逆阵。,2 新基础解表格与原表格的关系（1）,设在上述基础解的基础上，将非基矢量as引进基础解集，即asB集；而令原基础解集B中的Vr处原基矢量离开。这两种情况表达形式示于表1-3和表1-4表1-3 原表格（用当前基础解表达矢量）,2 新基础解表格与原表格的关系（2）,表1-4 新表格（用新基础解表达矢量）,2 新基础解表格与原表格的关系（3）,其中原表格是已经给出的与当前基础矢量相对应的单纯形表格，新基础解是由原非基矢量as代入Vr所致。其新解所对应的表格形式如表1-4所示，那么新表中各个元素如何根据原表1-3求出呢？现在就对该问题进行推导。因为当前基础解和新基础解都假定是可行的非退化解，因此两表中：ti00，ti00(i=1,2,m)(16),2 新基础解表格与原表格的关系（4）,则，当前基础可行解满足：AX=(17)因此，ti0就是X的正分量根据当前基础解来表达as：as=t1sV1+trsVr+tmsVm(18)由于基础矢量V1,Vr,Vm线性无关，因此trs0；,2 新基础解表格与原表格的关系（5）,否则，从式(18)中说明，as可由Vi(i=1,m,ir)线性组合，这说明新基础解不是线性无关的矢量构成，与假设矛盾。于是，Vr可根据式(18)表达为：Vr=(19)从假设知，新基础解基础矢量为：(V1)=V1,(Vr)=as,(Vm)=Vm(20)为获得新表格，系数tij应满足：,2 新基础解表格与原表格的关系（6）,aj=t1j(V1)+trj(Vr)+tmj(Vm)这表明 aj=trjas+(21)(式中，表示，下同)这唯一地定义了新表格中的系数。而根据当前基础解，存在：aj=trjVr+(22),2 新基础解表格与原表格的关系（7）,现在，把Vr用式(19)代入，则式(22)变为：aj=(23)将aj的两个表达式(21)和(23)的矢量系数加以比较，便可得出下述关系：当i=r时,trj=trj/trs(24)当ir时，tij=tij(tis/trs)trj(25),2 新基础解表格与原表格的关系（8）,对于扩充表格右边系数uij的表达更没问题。可把单位矢量ej作为扩充矩阵A，I的列，就像阶段法1做的那样，可设：e1=an+1，e2=an+2，em=an+m(26)于是，我们可定义：uij=ti,，n+j(i,j=1,2,m)(27)在式(24)和(25)中，用n+j代替j可得当i=r时，urj=urj/trs(28)当ir时，uij=uij(tis/trs)urj(29),2 新基础解表格与原表格的关系（9）,上述公式的含义如下：如果用as代替Vr而形成新基础可行解，则称原表中的r行为支点行原表中的s列为支点列trs为支点元素支点行(r)：新表r行原表r行/trs非支点行(i):新表i行=原表i行i（原表r行）,2 新基础解表格与原表格的关系（10）,从上所述，如果知道原表格的支点行和支点列，那么，新的表格便可应孕而生。于是如何选择支点行和支点列便是单纯形表格的关键问题，下面就分别阐述这两个问题。,3 如何选择支点行,选择支点行即是假设支点列已选定（即已知道应引进的非基础矢量），应令哪一个基础矢量离开的问题。支点行的选择原则是新解可行，即新表格中的ti0（i=1,m）0(对于非退化)。即，若r行被选中，则必须满足：tr0/trs=minti0/tis：tis0，i=1,m这就是r行被中的充分必要条件，对于非退化情况，r行能被唯一确定。,4 如何选择支点列（1）,在选择支点行之前，必须首先选择支点列，其原则是，新矢量进入基础解使费用尽量小，即最优性选择。旧费用为：CTX=(32)表明基础矢量Vi的单位费用。如果决定选支点列s，那么新的解的费用是多少呢？根据：as=0(33)及=AX=b(34),4 如何选择支点列（2）,将(33)式乘以再加(34)式得：as+(35)于是，得出一组新解，其新解的费用为：cs+(36)而=旧费用，令(37)故 新费用=旧费用（zscs）(38),4 如何选择支点列（3）,即，要使费用减少，只有zscs 0才行，这和在第五节所得结论一致。即可得出下述结论：从式（35）看出，若所有tis0,则当时，X（）永远可行，若此时，zscs 0,则最优目标值无界，即可无穷小。若zscs 0且至少有一个tis0，则s列是被选中之一，若有若干列的zscs 0,则通常选择最大的zscs 作为支点列，然后根据前面讲的选择支点行标准选取支点元素并构成新的表格。,4 如何选择支点列（4）,当选中s列作为支点列时，其新费用减少值为*（zscs）,其中，*是新基础解中as的系数。（as=(vr)）,我们有：*=tr0=tr0/trs如果，旧费用为z0,新费用为z0，则有 z0=z0 tr0(39)对于原扩充表格：T；U=M1A，b；I，显然缺少一些信息，即检验数信息，现可把它放在表格最后一行：z1c1，,zncn，z0；y1，ym(40),4 如何选择支点列（5）,这一行称为判断行或检验行。该行各元素含义如下：前n个元素之表达式为 zjcj=(j=1,n)(41)如果aj是当前基础解集，则：zjcj=0如果aj不是当前基础解集，则：元素z0是当前费用，(42),4 如何选择支点列（6）,最后m个元素定义为：(j=1,m)(43)其中uij=U是基础阵M之逆阵，则YT含义为：因此，YT是方程解，在最后阶段，当所有zjcj0时，YT将是下述对偶问题最优解：YTACT,YTb=max其中，YT将满足：YTaj=zjcj。,4 如何选择支点列（7）,加进判断行后，表格变为：(44)判断行之计算：新判断行=旧判断行-0乘支点行 0=（zscs）/trs(45)证明从略。,5 举例（1）,至此，单纯形表格法的基本步骤已推导完毕，下面举例来说明单纯形表格的应用。例1-21 已知线性规划为：AX=b，X0，CTX=min其中：A=，b=，CT=7，1，1(46)例1-21应用阶段1，求出式(46)的初始基础可行解。解为了求初始基础可行解，要引进人工变量并构成新规划：AX=b，X0，CTX=min,5 举例（2）,其中，A=，（X)T=(x1，x2，x3，s1，s2)b=(C)T=(0 0 0 1 1)现在变成求新规划最优解问题，显然，此规划的第1个基础可行解为：s1=5,s2=13,X=0,其相应表格为：(47),5 举例（3）,初始表格判断的计算很简单：，例如z1c1=(1,4)c1=50=5从判断行看出，最大的判断元素为z3c3=9。故a3应进入基础解，支点列s=3（当然a1，a2进入也行），然后选支点行：故支点元素为t13=3,于是用公式可计算出第2个表格。,5 举例（4）,(48),从表格（48）看出，max（zjcj）=z1c1=2,故令a1进入基础解集，然后选支点行r：,5 举例（5）,支点元素为t21=2。经变换，得出下述表格(49)：,(49),5 举例（6）,判断行zjcj全部0，故达最优，且z0=0。说明原问题存在可行解，且第1个基础可行解即为新规划的最优解：x2=0,x3=7/6,x1=3/2。于是阶段1结束。例1-22 求解（46）式的最优解。即进行阶段2。解将例1-21求得的新规划最优表格转换为原规划的初始单纯形表格。转换原则是：1）表的上面m行基本不变，新表右半部uij与原表人工变量矢量所对应的tij一致。2）表的判断行，需按照原规划的目标系数重算。,5 举例（7）,计算的初始单纯形表格如表格(50)：比较(49)与(50)，看出：把e1，e2列移往右边,(50),5 举例（8）,判断行不同，因阶段1时的新规划费用系数为CT=（0 0 0 1 1），而原规划为CT=7 1 1。初始解的基础矢量为a3，a1，=(1 7)。例：z2c2=1+71=3 z0=1+7=35/3y1=1+(-1)7=,5 举例（9）,从表格（50）看出：z2c2=3为唯一正值，选s=2。选支点行：trs=V1=a2(代替a3)最后表格：,5 举例（10）,则知，所有zjcj0(j=1，2，3)，已达最优。最优基础可行解：x2=，x1=min cost=CTX=z0=最优对偶分量：y1=,y2=检查条件：AX=b,X0,YTACT,CTX=YTb。全部符合条件。,