基础解及基础可行解

基础解及基础可行解第1页，课件共27页，创作于2023年2月

基础解及基础可行解（2）

线性独立的定义（或判断准则）为：若方程中的矢量系数，

，…必须全为零才能使方程满足，则称矢量a，a，…之间线性独立。即，任何一个矢量都不能由其它矢量的线性组合所构成的一组矢量必线性独立。例如：

中，，，则知a1，a2，a3之间线性相关（即线性不独立），因为任何一个矢量都可由其它两个矢量所组成。但是这三个矢量中，两两之间线性无关（独立）。

第2页，课件共27页，创作于2023年2月

基础解及基础可行解（3）

若存在多个不同的非零基础解，则它们之间组合系数之和为1的线性组合也必是方程解，即方程必存在无穷多个解。二、基础可行解定义

满足等式约束AX=b及自变量限制X≥0的解称为可行解，既是可行解又是基础解解的解称为基础可行解。即基础解与可行解之交集称为基础可行解。基础可行解是可行域的顶点，它是可行解的一部分。基础可行解在线性规划的求解中具有特殊重要性，下面将阐述并证明关于它的重要定理。

第3页，课件共27页，创作于2023年2月

基础解及基础可行解（4）

三、定理对于下述标准线性规划1、如果存在可行解，则必存在基础可行解。2、如果存在最优解，则必存在基础最优解。定理1证明：设，规划已有一个可行解X，且具有正分量x，x

，…（如果无正分量，则X本身即为落在原点的基础可行解），如果正分量x，x

，…对应的A阵列矢量a，a，…线性独立，则X即为基础可行解，如果不独立，则在下述方程：第4页，课件共27页，创作于2023年2月

基础解及基础可行解（5）

中(3)至少有一项i0，不失一般性，令0且>0（否则等式两边乘以-1）。设

(4)其中，x，x

，…>0则用(4)式－λ·(3)式得

(5)第5页，课件共27页，创作于2023年2月

基础解及基础可行解（6）

如果，λ足够小，则仍可使（5）式左边系数≥0，

≥0，…即仍可使新的X为可行解。选取于是新的正分量少了第μ项，即X正分量比原来至少少了一项。

然后再检验新的X正分量所对应的A阵矢量是否线性独立，若是，则该新解X即为基础可行解。否则，按照上述方法又可使新解X的正分量减少，直至找到基础可行解为止。定理2证明（略）第6页，课件共27页，创作于2023年2月第三讲（下）单纯形概念

§1基本假设：非退化阵

§2单纯形算法

第7页，课件共27页，创作于2023年2月§1基本假设：非退化阵（1）

在推导单纯形算法时，在理论上作出非退化假设。标准规划形式：其中，A为m行n列，

m<n则作2个假设：1．A阵的秩为m，即m行线性独立。2．b(m维向量)是不少于m列的线性组合，即在

中，X至少有m个正分量。

第8页，课件共27页，创作于2023年2月§1基本假设：非退化阵（2）

第1个假设表明，AX=b总是有解，如果该假设失败，则有下述两种情况：①

不独立，或者②不合理

例如，

，显然两行成正比例，A阵秩为1。若有AX=b，b=(b1,b2)T，必有2种情况：设b2=2b1，说明不独立。

b2≠2b1，产生矛盾，不合理。

第9页，课件共27页，创作于2023年2月§1基本假设：非退化阵（3）

对于这个假设失败,可作如下处理:如行间不独立,可消去一行或几行,使之独立；如果不合理,则方程无解,不考虑。

第2个假设表明，可行解的正分量个数不少于m个，若失败，即为退化问题。例如方程

(1)第10页，课件共27页，创作于2023年2月§1基本假设：非退化阵（4）则b=可由a3=单独组合而成，即可得可行解X=。这种现象有时会给单纯形算法造成困难。其解决方法是对b加一小扰动，即令b=，这样就会使假设2成立。后面在推导单纯形算法时，都指非退化情况，除非加以特殊说明。第11页，课件共27页，创作于2023年2月§2单纯形算法（1）

单纯形算法根据寻找基础可行解的步骤可分为大M（T）法和两阶段法，这两个方法无本质区别，下面主要阐述两阶段法。两阶段法的主要步骤为两项：

找出规划的第1个基础可行解或证明无可行解；

从第1个基础可行解开始，逐步找了最优解或证明无最优解。这两项工作可在有限步数内完成。现分别叙述这两个阶段是如何完成的。1．进行第一阶段——找出第1个基础可行解（假设第2阶段已经会作。）设在规划中的约束部分第12页，课件共27页，创作于2023年2月§2单纯形算法（2）

(2)其中，bi>0(否则该方程乘以-1)为了求出这个原规划的第1个基础可行解，可据此构造一个新规划：第13页，课件共27页，创作于2023年2月§2单纯形算法（3）

则这个新规划的第1个基础可行解可立即得到：

xj=0(j=1,…,n)

zi=bi(i=1,…,m)(4)新规划具有m个方程，m+n个未知量，其矩阵表达式为第14页，课件共27页，创作于2023年2月§2单纯形算法（4）

由于新规划的构成本身可提供第1个基础可行解，于是便可采用第2阶段法去寻求新规划的最优解。其寻优结果有2种可能性：①min=0,则新规划最优解（X*，Z*）的X*必是原规划的1个基础可行解。②min>0，则说明原规划无可行解。[例1-5]原规划为：

(6)

则新规划为：

(7)

新规划最优解为：z1=3，x1=0，x2=0。∵z1>0。故原规划无可行解。第15页，课件共27页，创作于2023年2月§2单纯形算法（5）

2．进行第2阶段——寻找最优解1．在叙述寻优步骤前，首先引入非退化定理（略）。

①

非退化定理②阶段2的进行步骤令X是非退化阵A的标准线性基础可行解，则可由此导出最优解X*。设在规划：AX=b，X>0，CTX=min中，B是可行解中取正值分量的角标j之集合。即：B={j：xj>0}第16页，课件共27页，创作于2023年2月§2单纯形算法（6）

显然，如果A阵具有m行且B含m项，则称B是基础解集，∣B∣=m。因此，基础解X依赖于基础解集B中的j所对应的列aj，又称基础列，这m个基础列组成m×n矩阵，这是一个可逆阵。[例1-7]给出约束条件阵为：

若给定基础可行解XT=[1,0,1],则x1>0，x3>0,其基础解集B={1,3}，B有2项，∣B∣=2。则解X依赖于两列（1，3列）组成的基础阵第17页，课件共27页，创作于2023年2月§2单纯形算法（7）

对于一般情况：，可求解m个方程式。定义矢量Y：YTaj=cj

(j

B)应用矩阵M，可改写如下：YTM=其中，有m个分量cj

(j

B)，唯一解为：YT=(12)此时，有2种可能性：1)若式(12)所得解Y是该规划的对偶可行解，则X必是原问题的最优解。从而Y亦是对偶问题最优解，即X满足：

第18页，课件共27页，创作于2023年2月§2单纯形算法（8）

如何判断平衡解Y是对偶可行解呢？这很容易，即判断下式是否成立：其中，jB时，等式已成立，只需判断其余(n－m)个非基础列是否满足即可。若全满足，达最优，否则，未达最优，属下述第2)种情况。

第19页，课件共27页，创作于2023年2月§2单纯形算法（9）

2）若有一些非基础列j＝s得出，YTas>cs,这说明解Y不是对偶可行解。因而需把目前的非基础列as引入基础列中，以便压缩目标费用。首先，把as表达为现有基础列的组合：根据基础矩阵可写成：

第20页，课件共27页，创作于2023年2月§2单纯形算法（10）

用乘(13)式并加到

若是正数且很小，则所有(m+1)个系数可全为正，于是得出新的原问题可行解，新费用为：第21页，课件共27页，创作于2023年2月§2单纯形算法（11）

其旧费用减新费用之差为（zs－cs）其中，定义

要注意，必须为正，因为它是as的系数。根据式(16)看出，新费用减少的条件是：

zs－cs>0(17)该条件即为：yTas>cs。证明：

(18)

而

证毕第22页，课件共27页，创作于2023年2月§2单纯形算法（12）

由此看出，当平衡解YT不能使所有j满足时，就说明该解的费用仍可减少，故不是最优解，并且从前面推导中看出，可以求得一个新解使其费用减少，其新费用减少值为（zs－cs）。想使费用尽量小，则必须使尽量大且保持解可行，即使：

(19)对于(19)式之求解，可出现2种情况：(i)在(19)式中若所有tj≤0,则可取无限大值仍为可行解，故目标函数可无穷小，即不存在最优解或无界。

第23页，课件共27页，创作于2023年2月§2单纯形算法（13）(ii)至少有一个tj>0，则可选取为下面有限值：

(20)

该*是此次获得最小目标值的可行解。

设*是在j=p中达到，即*=xp/tp，则在（15）式中ap的系数变为0，在非退化假设下，这是唯一一个变为0的系数，选定*后，式（15）即可变为：

(21)

第24页，课件共27页，创作于2023年2月§2单纯形算法（14）非退化定理意味着，这个方程组定义了一个新的基础解：B’={s}+B{p}(22)即，B中增加s，且去掉P。于是，（21）式可重写为