基础解及基础可行解.ppt

《基础解及基础可行解.ppt》由会员分享，可在线阅读，更多相关《基础解及基础可行解.ppt（27页珍藏版）》请在装配图网上搜索。

1、第三讲 （上） 基础解及基础可行解 （1）,一、基础解定义 令X 满足，AX=b，若X 0，则X 必有非零分量x，x ， 于是必存的方程式： (1) 其中a，a，为与x，x ，对应的A阵列矢量，如果列矢 量a，a，之间线性独立，则称X为基础解。,基础解及基础可行解 （2）,线性独立的定义（或判断准则）为：若方程 中的矢量系数， ，必须全为零才能使方程满足，则称 矢量a，a，之间线性独立。 即，任何一个矢量都不能由其它矢量的线性组合所构成的一 组矢量必线性独立。 例如： 中， ， ， 则知a1，a2，a3之间线性相关（即线性不独立），因为任何一 个矢量都可由其它两个矢量所组成。但是这三个矢量中，

2、两 两之间线性无关（独立）。,基础解及基础可行解 （3）,若存在多个不同的非零基础解，则它们之间组合系数之和为1 的线性组合也必是方程解，即方程必存在无穷多个解。 二、基础可行解定义 满足等式约束AX=b及自变量限制X0的解称为可行解，既是可行解又是基础解解的解称为基础可行解。即基础解与可行解之交集称为基础可行解。 基础可行解是可行域的顶点，它是可行解的一部分。基础可行解在线性规划的求解中具有特殊重要性，下面将阐述并证明关于它的重要定理。,基础解及基础可行解 （4）,三、定理 对于下述标准线性规划 1、如果存在可行解，则必存在基础可行解。 2、如果存在最优解，则必存在基础最优解。 定理1证明：

3、设，规划已有一个可行解X，且具有正分量x， x ，（如果无正分量，则X本身即为落在原点的基础可行 解），如果正分量x，x ，对应的A阵列矢量a，a，线 性独立，则X即为基础可行解，如果不独立，则在下述方程：,基础解及基础可行解 （5）,中 (3) 至少有一项i0，不失一般性，令0且0（否则等式两 边乘以-1）。设 (4) 其中，x，x ，0 则用(4)式 (3)式得 (5),基础解及基础可行解 （6）,如果，足够小，则仍可使（5）式左边系数 0， 0， 即仍可使新的X为可行解。 选取 于是新的正分量少了第项，即X正分量比原来至少少了一项。 然后再检验新的X正分量所对应的A阵矢量是否线性独立，若

4、 是，则该新解X即为基础可行解。否则，按照上述方法又可使 新解X的正分量减少，直至找到基础可行解为止。 定理2证明（略）,第三讲（下） 单纯形概念,1 基本假设：非退化阵 2 单纯形算法,1 基本假设：非退化阵（1）,在推导单纯形算法时，在理论上作出非退化假设。 标准规划形式： 其中，A为m行n列， mn 则作2个假设： 1A阵的秩为m，即m行线性独立。 2b(m维向量)是不少于m列的线性组合，即在 中，X至少有m个正分量。,1 基本假设：非退化阵（2）,第1个假设表明，AX=b总是有解，如果该假设失败，则有下 述两种情况： 不独立，或者 不合理 例如， ，显然两行成正比例，A阵秩为1。 若有

5、AX=b，b=(b1,b2)T，必有2种情况： 设b2=2b1，说明不独立。 b22b1，产生矛盾，不合理。,1 基本假设：非退化阵（3）,对于这个假设失败,可作如下处理:如行间不独立,可消去一 行或几行,使之独立；如果不合理,则方程无解,不考虑。 第2个假设表明，可行解的正分量个数不少于m个，若失败， 即为退化问题。例如方程 (1),1 基本假设：非退化阵（4）,则b= 可由a3= 单独组合而成，即可得可行解X= 。 这种现象有时会给单纯形算法造成困难。 其解决方法是对b加一小扰动，即令b = ， 这样就会使假设2成立。 后面在推导单纯形算法时，都指非退化情况，除非加以特殊说明。,2 单纯形

6、算法（1）,单纯形算法根据寻找基础可行解的步骤可分为大M（T）法和 两阶段法，这两个方法无本质区别，下面主要阐述两阶段法。 两阶段法的主要步骤为两项： 找出规划的第1个基础可行解或证明无可行解； 从第1个基础可行解开始，逐步找了最优解或证明无最优解。 这两项工作可在有限步数内完成。现分别叙述这两个阶段是如 何完成的。 1进行第一阶段找出第1个基础可行解（假设第2阶段已经会作。）设在规划中的约束部分,2 单纯形算法（2）,(2) 其中，bi0(否则该方程乘以-1) 为了求出这个原规划的第1个基础可行解，可据此构造一个新规 划：,2 单纯形算法（3）,则这个新规划的第1个基础可行解可立即得到： x

7、j=0 (j=1,n) zi=bi (i=1,m) (4) 新规划具有m个方程，m+n个未知量，其矩阵表达式为,2 单纯形算法（4）,由于新规划的构成本身可提供第1个基础可行解，于是便可采用 第2阶段法去寻求新规划的最优解。其寻优结果有2种可能性： min =0,则新规划最优解（X*，Z*）的X*必是原规划的1个 基础可行解。 min 0，则说明原规划无可行解。 例1-5原规划为： (6) 则新规划为： (7) 新规划最优解为：z1=3，x1=0，x2=0。 z10。故原规划无可行解。,2 单纯形算法（5）,2进行第2阶段寻找最优解 1在叙述寻优步骤前，首先引入非退化定理（略）。 非退化定理

8、阶段2的进行步骤 令X是非退化阵A的标准线性基础可行解，则可由此导出最优 解X* 。 设在规划：AX=b，X0，CTX=min中，B是可行解中取正值分 量的角标j之集合。 即： B=j：xj0,2 单纯形算法（6）,显然，如果A阵具有m行且B含m项，则称B是基础解集， B=m。因此，基础解X依赖于基础解集B中的j所对应的列aj， 又称基础列，这m个基础列组成mn矩阵，这是一个可逆阵。 例1-7 给出约束条件阵为： 若给定基础可行解XT=1,0,1,则x10，x30,其基础解集 B=1,3，B有2项，B=2。则解X依赖于两列（1，3列） 组成的基础阵,2 单纯形算法（7）,对于一般情况： ，可求

9、解m个方程式。 定义矢量Y：YTaj=cj (j B) 应用矩阵M，可改写如下：YTM = 其中， 有m个分量cj (j B)，唯一解为：YT= (12) 此时，有2种可能性： 1) 若式(12)所得解Y是该规划的对偶可行解，则X必是原问题的 最优解。从而Y亦是对偶问题最优解，即X满足：,2 单纯形算法（8）,如何判断平衡解Y是对偶可行解呢？ 这很容易，即判断下式是否成立： 其中，jB时，等式已成立，只需判断其余(nm)个非基础列 是否满足即可。若全满足，达最优，否则，未达最优，属下述 第2)种情况。,2 单纯形算法（9）,2）若有一些非基础列js得出，YTascs,这说明解Y不是对偶可 行解

10、。因而需把目前的非基础列as引入基础列中，以便压缩 目标费用。 首先，把as表达为现有基础列的组合： 根据基础矩阵可写成：,2 单纯形算法（10）,用乘(13)式并加到 若是正数且很小，则所有(m+1) 个系数可全为正，于是得出 新的原问题可行解，新费用为：,2 单纯形算法（11）,其旧费用减新费用之差为（zscs） 其中，定义 要注意，必须为正，因为它是as的系数。根据式(16)看出， 新费用减少的条件是： zscs 0 (17) 该条件即为：yTascs。 证明： (18) 而,证毕,2 单纯形算法（12）,由此看出，当平衡解YT不能使所有j满足 时，就 说明该解的费用仍可减少，故不是最优

11、解，并且从前面推导 中看出，可以求得一个新解使其费用减少，其新费用减少值 为（zscs）。想使费用尽量小，则必须使尽量大且保持解 可行，即使： (19) 对于(19)式之求解，可出现2种情况： (i) 在(19)式中若所有tj0,则可取无限大值仍为可行解， 故目标函数可无穷小，即不存在最优解或无界。,2 单纯形算法（13）,(ii) 至少有一个tj0，则可选取为下面有限值： (20) 该*是此次获得最小目标值的可行解。 设*是在j=p中达到，即*=xp/tp，则在（15）式中ap的系数变 为0，在非退化假设下，这是唯一一个变为0的系数，选定* 后，式（15）即可变为： (21),2 单纯形算法

12、（14）,非退化定理意味着，这个方程组定义了一个新的基础解： B=s+Bp (22) 即，B中增加s，且去掉P。 于是，（21）式可重写为： (23) 新系数是m个正数：,2 单纯形算法（15）,非退化假设意味着，所有m个系数xj为正，且m个列矢量aj线 性无关（jB），因此，对于(ii)状态，可计算出一个新的 基础可行解X，且费用降低为*（zscs）。然后以新解X作 为旧解，重复上述阶段2步骤，最后结果必在有限步内完成。 因为进行中只有下述几种可能： 出现情况1)，即有对偶解，则说明获得最优解，停止。 出现情况2)中的(i)，不存在最优解，则停止。 出现情况2)中的(ii)，可求出新解X以代替旧解X，并 重复阶段2步骤。,2 单纯形算法（16）,这个循环步骤是有限的，因为矩阵A的秩和m列子集数目有限 （即AX=b）具有有限数目的基础解）。 设用上述方法获得一系列基础解为X1，X2，则其费用必 递减为CTX1 CTX2，由于X1, X2,，不同，故迭代次数有 限，由于非退化假设，死循环亦是不可能的.实际上，即使对 于退化问题，死循环也很少出现。,