《单纯型表格算法课件》由会员分享，可在线阅读，更多相关《单纯型表格算法课件（38页珍藏版）》请在金锄头文库上搜索。
1、第四讲 单纯型表格算法,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列a
2、j(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列即为： a3a
3、1=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=MU U=M1。因此扩充表格中的uij是当前基础阵之
4、逆阵。,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）,设在上述基础解的基础上，将非基矢
5、量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
6、 新基础解表格与原表格的关系（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 新
7、基础解表格与原表格的关系（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）,对于扩充表格右
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 非支点
9、行(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
10、 如何选择支点列 （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才行，这和在第五节所得 结论一致。即可
11、得出下述结论： 从式（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；
12、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
13、 其中，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=
14、(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。说
