《基础解及基础可行解.ppt》由会员分享，可在线阅读，更多相关《基础解及基础可行解.ppt（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 1 11/21/20231/21/2023第四讲第三讲（上）基础解及基础可行解（1）一、基础解定义 令X 满足，AX=b，若X 0，则X 必有非零分量x，x，于是必存的方程式：(1)其中a，a，为与x，x，对应的A阵列矢量，如果列矢量a，a，之间线性独立，则称X为基础解。Operations Research Operations Res
2、earch Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 2 21/21/20231/21/2023第四讲 基础解及基础可行解（2）线性独立的定义（或判断准则）为：若方程中的矢量系数，必须全为零才能使方程满足，则称矢量a，a，之间线性独立。即，任何一个矢量都不能由其它矢量的线性组合所构成的一组矢量必线性独立。例如：中，则知a1，a2，a3之间线性相关（即线性不独立），因为任何一个矢量都可由其它两个矢量所组成。但是这三个矢量中，两两之间线性无关（独立）。Opera
3、tions Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 3 31/21/20231/21/2023第四讲 基础解及基础可行解（3）若存在多个不同的非零基础解，则它们之间组合系数之和为1的线性组合也必是方程解，即方程必存在无穷多个解。二、基础可行解定义o满足等式约束AX=b及自变量限制X0的解称为可行解，既是可行解又是基础解解的解称为基础可行解。即基础解与可行解之交集称为基础可行解。o基础可行解是可行域的
4、顶点，它是可行解的一部分。基础可行解在线性规划的求解中具有特殊重要性，下面将阐述并证明关于它的重要定理。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 4 41/21/20231/21/2023第四讲 基础解及基础可行解（4）三、定理对于下述标准线性规划1、如果存在可行解，则必存在基础可行解。2、如果存在最优解，则必存在基础最优解。定理1证明：设，规划已有一个可行解X，且具有正分量x，
5、x，（如果无正分量，则X本身即为落在原点的基础可行解），如果正分量x，x，对应的A阵列矢量a，a，线性独立，则X即为基础可行解，如果不独立，则在下述方程：Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 5 51/21/20231/21/2023第四讲 基础解及基础可行解（5）中(3)至少有一项i0，不失一般性，令0且0（否则等式两边乘以-1）。设(4)其中，x，x，0则用(4)式(3)
6、式得(5)Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 6 61/21/20231/21/2023第四讲 基础解及基础可行解（6）如果，足够小，则仍可使（5）式左边系数0，0，即仍可使新的X为可行解。选取于是新的正分量少了第项，即X正分量比原来至少少了一项。然后再检验新的X正分量所对应的A阵矢量是否线性独立，若是，则该新解X即为基础可行解。否则，按照上述方法又可使新解X的正分量减少，
7、直至找到基础可行解为止。定理2证明（略）Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 7 71/21/20231/21/2023第四讲第三讲（下）单纯形概念单纯形概念 1基本假设：非退化阵2单纯形算法Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSch
8、ool of Economics&Managementpage page 8 81/21/20231/21/2023第四讲1 基本假设：非退化阵（1）在推导单纯形算法时，在理论上作出非退化假设。标准规划形式：其中，A为m行n列，m0(否则该方程乘以-1)为了求出这个原规划的第1个基础可行解，可据此构造一个新规划：Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 14141/21/2023
9、1/21/2023第四讲2 单纯形算法（3）则这个新规划的第1个基础可行解可立即得到：xj=0(j=1,n)zi=bi(i=1,m)(4)新规划具有m个方程，m+n个未知量，其矩阵表达式为Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 15151/21/20231/21/2023第四讲2 单纯形算法（4）由于新规划的构成本身可提供第1个基础可行解，于是便可采用第2阶段法去寻求新规划的最
10、优解。其寻优结果有2种可能性：min=0,则新规划最优解（X*，Z*）的X*必是原规划的1个基础可行解。min0，则说明原规划无可行解。例1-5原规划为：(6)则新规划为：(7)新规划最优解为：z1=3，x1=0，x2=0。z10。故原规划无可行解。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 16161/21/20231/21/2023第四讲2 单纯形算法（5）2进行第2阶段寻找最
11、优解1在叙述寻优步骤前，首先引入非退化定理（略）。非退化定理 阶段2的进行步骤令X是非退化阵A的标准线性基础可行解，则可由此导出最优解X*。设在规划：AX=b，X0，CTX=min中，B是可行解中取正值分量的角标j之集合。即：B=j：xj0Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 17171/21/20231/21/2023第四讲2 单纯形算法（6）显然，如果A阵具有m行且B含m
12、项，则称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列）组成的基础阵Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 18181/21/20231/21/2023
13、第四讲2 单纯形算法（7）对于一般情况：，可求解m个方程式。定义矢量Y：YTaj=cj(j B)应用矩阵M，可改写如下：YTM=其中，有m个分量cj(j B)，唯一解为：YT=(12)此时，有2种可能性：1)若式(12)所得解Y是该规划的对偶可行解，则X必是原问题的最优解。从而Y亦是对偶问题最优解，即X满足：Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 19191/21/20231/
14、21/2023第四讲2 单纯形算法（8）如何判断平衡解Y是对偶可行解呢？这很容易，即判断下式是否成立：其中，jB时，等式已成立，只需判断其余(nm)个非基础列是否满足即可。若全满足，达最优，否则，未达最优，属下述第2)种情况。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 20201/21/20231/21/2023第四讲2 单纯形算法（9）2）若有一些非基础列js得出，YTascs,
15、这说明解Y不是对偶可行解。因而需把目前的非基础列as引入基础列中，以便压缩目标费用。首先，把as表达为现有基础列的组合：根据基础矩阵可写成：Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 21211/21/20231/21/2023第四讲2 单纯形算法（10）用乘(13)式并加到 若是正数且很小，则所有(m+1)个系数可全为正，于是得出新的原问题可行解，新费用为：Operations
16、Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 22221/21/20231/21/2023第四讲2 单纯形算法（11）其旧费用减新费用之差为（zscs）其中，定义要注意，必须为正，因为它是as的系数。根据式(16)看出，新费用减少的条件是：zscs0(17)该条件即为：yTascs。证明：(18)而证毕Operations Research Operations Research Prof.Wang Pr
17、of.Wang School of Economics&ManagementSchool of Economics&Managementpage page 23231/21/20231/21/2023第四讲2 单纯形算法（12）由此看出，当平衡解YT不能使所有j满足时，就说明该解的费用仍可减少，故不是最优解，并且从前面推导中看出，可以求得一个新解使其费用减少，其新费用减少值为（zscs）。想使费用尽量小，则必须使尽量大且保持解可行，即使：(19)对于(19)式之求解，可出现2种情况：(i)在(19)式中若所有tj0,则可取无限大值仍为可行解，故目标函数可无穷小，即不存在最优解或无界。Opera
18、tions Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 24241/21/20231/21/2023第四讲2 单纯形算法（13）(ii)至少有一个tj0，则可选取为下面有限值：(20)该*是此次获得最小目标值的可行解。设*是在j=p中达到，即*=xp/tp，则在（15）式中ap的系数变为0，在非退化假设下，这是唯一一个变为0的系数，选定*后，式（15）即可变为：(21)Operations Resear
19、ch Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 25251/21/20231/21/2023第四讲2 单纯形算法（14）非退化定理意味着，这个方程组定义了一个新的基础解：B=s+Bp(22)即，B中增加s，且去掉P。于是，（21）式可重写为：(23)新系数是m个正数：Operations Research Operations Research Prof.Wang Prof.Wang School of Economi
20、cs&ManagementSchool of Economics&Managementpage page 26261/21/20231/21/2023第四讲2 单纯形算法（15）非退化假设意味着，所有m个系数xj为正，且m个列矢量aj线性无关（jB），因此，对于(ii)状态，可计算出一个新的基础可行解X，且费用降低为*（zscs）。然后以新解X作为旧解，重复上述阶段2步骤，最后结果必在有限步内完成。因为进行中只有下述几种可能：出现情况1)，即有对偶解，则说明获得最优解，停止。出现情况2)中的(i)，不存在最优解，则停止。出现情况2)中的(ii)，可求出新解X以代替旧解X，并 重复阶段2步骤。O
21、perations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 27271/21/20231/21/2023第四讲2 单纯形算法（16）这个循环步骤是有限的，因为矩阵A的秩和m列子集数目有限（即AX=b）具有有限数目的基础解）。设用上述方法获得一系列基础解为X1，X2，则其费用必递减为CTX1CTX2，由于X1,X2,，不同，故迭代次数有限，由于非退化假设，死循环亦是不可能的.实际上，即使对于退化问题，死循环也很少出现。