第二章单纯形法ppt课件.ppt

《第二章单纯形法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章单纯形法§2-1线性规划问题的几何意义一、线性规划问题的解（对于标准型LP问题）1、可行解：满足约束条件(2)和(3)的解称为可行解。2、基及基变量：设矩阵A的秩为m（n≥m）,则A中任何一组m个线性无关的列向量构成的子矩阵,称为该问题的一个基(basis),基中的这些列向量对应的变量称为基变量(basicvariable)线性代数线性相关性判断定理：设r个n维向量构成矩阵A，那么这r个向量线性无关的充分必要条件是A中存在不等于0的r阶子式5、最优解：若基本可行解又是最优解（也称基本最优解），这个基就称为最优基（o

2、ptimalbasis）。3、基本解：对于基,令非基变量为零,求得满足（2）的唯一解，称为基对应的线性规划的基本解（basicsolution）。4、基本可行解：满足（3）的基本解称为基本可行解（basicfeasiblesolution）；基可行解的非零分量个数

3、化解二、凸集及凸集的顶点1、凸集2、极点设X1,X2∈Ｋ，若两点连线上任意一点αX1＋（１-α）X２∈Ｋ,且０≤α≤１，则称Ｋ为凸集．设Ｋ为凸集，X∈Ｋ，若Ｘ不能用两点X1,X2∈Ｋ的线性组合表示为αX1＋（１-α）X２∈Ｋ,且０＜α＜１，则称Ｘ为Ｋ的极点或顶点．（X不是K中任何线段的内点）三、线性规划问题的基本定理定理1:若线性规划问题存在可行域（满足约束条件），则可行域是凸集。证明:假设X1和X2分别是线性规划问题的可行解,则存在:AX1=b;AX2=b现有X=αX1+(1-α)X2;AX=A[αX1+(1-α)X2

4、]=AαX1+AX2-AαX2=α×b+b-α×b=b,故X也是一可行解.定理2:线性规划问题可行解是基本可行解的充要条件是的X的非零分量对应的系数列向量线性无关。（证明从略:基解概念）。定理4:线性规划问题若有可行解,必有基本可行解；即线性规划问题的可行域非空，则必有极点。定理3:线性规划问题的基本可行解对应可行域的极点。定理5:线性规划问题若有最优解,则一定会在可行域的极点上达到。（不是说只有极点最优，其他点不能达到最优）综上所述,我们在理论上得到线性规划问题结论如下：线性规划问题的可行域是一凸集（包括有界凸集和无界

5、凸集）;线性规划问题的每个基本可行解对应着可行域的一个极点（顶点）;若线性规划问题有最优解,必在可行域的某极点上得到。由此可见,我们只需在基本可行解中寻求最优解。如何有效地寻求最优解,这就是下节要介绍的单纯形法。§2-2线性规划问题典式1、线性规划问题原式机会成本检验数线性规划问题的典式：线性规划问题的典式展开式：IIIIIIIVc1c2…cmcm+1cm+2…cnCBXBbx1x2…xmxm+1xm+2…xnc1x1b1'10…0a1,m+1a1,m+2…a1nc2x2b2'01…0a2,m+1a2,m+2…a2n……

6、………………………cmxmbm'00…1am,m+1am,m+2…amnOBJ=CBb’c1c2…cmzm+1zm+2…zn00…0cm+1-zm+1cm+2-zm+2…cn-zn表格形式典式§2-3单纯形法一、单纯形法的基本思路和步骤思路：如果线性规划问题存在最优解，一定有一个基本可行解是最优解。因此单纯形法迭代的基本思路是：先找出一个基本可行解，判断其是否为最优解，如为否，则转换到相邻的基本可行解，并使目标函数值不断增大，一直找到最优解为止。基本步骤：始1、初始基本可行解的确定对目标函数为(MAX≤)形式的线性规划背

7、景模型，通过标准化，每一个约束方程引入一个松弛变量，松弛变量为基变量，其他变量为非基变量，得到一个初始基本可行解。化为标准型：松弛变量标准型约束方程的系数矩阵为:nm阶方阵令xj=0,则xsi=bi，推出X=(0,0,0…０,b1,b2…bm)为线性规划问题的初始基可行解2、最优解检验（根据线性规划问题的典式）机会成本检验数解的判断：当所有σj≤０时，表示目标函数已经达到最优，若存在一个非基变量的检验数等于0，则该线性规划问题有多重最优解；σj＞0，则表示没有达到最优，若对应该列所有aij≤０时，则线性规划问题为无界解3

8、、基可行解的改进（求更优的基可行解）（1）确定换入变量(最大检验数规则)：从cjzj>0中找最大者，选中者称为入变量，xj对应的第j*列称为主列；（2）确定换出变量（最小比例原则）：设第i*行使最小，则第i*行对应的基变量称为出变量，第i*行称为主行；最小比例原则地解释：设原问题基可行解为X1,X2,…Xm,非基