运筹学第二章线性规划第二讲标准型与单纯形法.ppt

《运筹学第二章线性规划第二讲标准型与单纯形法.ppt》由会员分享，可在线阅读，更多相关《运筹学第二章线性规划第二讲标准型与单纯形法.ppt（36页珍藏版）》请在三一办公上搜索。

1、,2.3 线性规划的标准型Standard form of LP,在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。,2.3 线性规划的标准型Standard form of LP,线性规划问题的标准型为:1目标函数求最大值（或求最小值）2约束条件都为等式方程3变量xj非负4常数bi非负,max(或min)Z=c1x1+c2x2+cnxn,2.3 线性规划的标准型Standard form of LP,或写成下列形式：,或用矩阵形式,2.3 线性规划的标准型Standard form of LP,通常X记为：,称为约束方程的系数矩阵，m是约束方程的个数，n是决

2、策变量的个数，一般情况mn，且r()m。,其中:,2.3 线性规划的标准型Standard form of LP,一般形式线性规划模型的标准化准则:（前提 bi 0）,5.xj0,令xj=xj,xj 0,【例1】将下列线性规划化为标准型,【分析】()因为x3无符号要求，即x3 可取正值也可取负值，标准型中要求变量非负，所以令,2.3 线性规划的标准型Standard form of LP,(3)第二个约束条件是“”号，在“”号左端减去剩余变量(surplus variable)x5，x50，也称松驰变量；,2.3 线性规划的标准型Standard form of LP,(2)第一个约束条件是“

3、”号，在“”号左端加入松驰变量(slack variable)x4，x40,化为等式；,(4)第三个约束条件是“”号且常数项为负数，因此在“”左边加入松驰变量x6，x60，同时两边乘以1。,(5)目标函数是最小值，为了化为求最大值，令Z=Z,得到 max Z=Z，即当Z达到最小值时Z达到最大值。,综合起来得到下列标准型,2.3 线性规划的标准型Standard form of LP,当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束,将其化为两个不等式,再加入松驰变量化为等式。,2.3 线性规划的标准型Standard form of LP,2.4 线性规划的有关概

4、念Basic Concepts of LP,设线性规划的标准型 max Z=CX(2.1)AX=b(2.2)X 0(2.3)式中A 是mn矩阵，mn并且r(A)=m，显然A中至少有一个mm子矩阵B，使得r(B)=m。,2.4 基本概念Basic Concepts,基(basis)：A中 mm子矩阵 B 并且有r(B)=m，则称B是线性规划的一个基(或基矩阵basis matrix)。,【例2】线性规划,求所有基矩阵。,【解】约束方程的系数矩阵为25矩阵,2.4 基本概念Basic Concepts,容易看出r(A)=2，2阶子矩阵有C52=10个，其中第1列与第3列构成的2阶矩阵不是一个基，基

5、矩阵只有9个，即,当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为基向量(basic vector)，其余列向量称为非基向量;,基向量对应的变量称为基变量(basic variable)，非基向量对应的变量称为非基变量；,在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基变量，x2、x3、x5是非基变量。基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。,2.4 基本概念Basic Concepts,可行解(feasible solution):满足式(2.2)及(2.3)的解X=（x1,x2,xn)T 称为可行解；,基本可行解(ba

6、sic feasible solution):若基本解是可行解 则称为是基本可行解（也称基可行解）。,基本解(basic solution):对某一确定的基B，令非基变量 等于零，利用式(2.2)解出基变量，则这组解称为基 的基本解。,最优解(optimal solution):满足式(1.1)的可行解称为最优 解，即使得目标函数达到最大值的可行解就是最优解；,非可行解(infeasible solution)无界解(unbounded solution),2.4 基本概念Basic Concepts,显然，只要基本解中的基变量的解满足式(2.3)的非负要求，那么这个基本解就是基本可行解。,在

7、上例中，对来说，x1,x2是基变量，x3,x4，x5是非基变量，令x3=x4=x5=0，则式(2.2)为,因|B1|，由克莱姆法则知，x1、x2有惟一解x12/5,x2=1,从而基本解为,2.4 基本概念Basic Concepts,对B2来说，x1,x4,为基变量，令非变量x2,x3,x5为零，由式(2.2)得，x4=4，则基本解为,反之，可行解不一定是基本可行解，如满足式(2.2)(2.3)，但不是任何基矩阵的基本解。,在 中x10,不是可行解，因此也不是基本可行解。,可行基:基可行解对应的基称为可行基；最优基:基本最优解对应的基称为最优基；如上述B3就是最优基，最优基肯定是可行基。,2.

8、4 基本概念Basic Concepts,基本最优解:最优解是基本解称为基本最优解。例如 满足式(2.1)(2.3)是最优解,又是B3的基本解,因此它是基本最优解。,注：当最优解惟一时，最优解亦是基本最优解，当最优解不惟一时，则最优解不一定是基本最优解。,基本最优解、最优解、基本可行解、基本解、可行解的关系:,基本最优解,基本可行解,可行解,最 优 解,基本解,2.4 基本概念Basic Concepts,凸集(Convex set):设 K 是 n 维空间 Rn 的一个点集，对任意两点 时，则称K为凸集。,就是以X(1)、X(2)为端点的线段方程,点X的位置由的值确定,当=0时,X=X(2)

9、,当=1时X=X(1)。,凸组合(Convex combination):设是Rn中的点，若存在 使得 成立，称X为 的凸组合。,2.4 基本概念Basic Concepts,极点(Extreme point):设K是凸集，若X不能用K中两个不同的点 的凸组合表示为,则称X是K的一个极点或顶点。,X是凸集K的极点，即X不可能是K中某一线段的内点，只能是K中某一线段的端点。,O,2.4 基本概念Basic Concepts,【定理2.1】若线性规划可行解集 K 非空,则 K 是凸集。,【定理2.2】线性规划的可行解集合 K 的点 X 是极点的充要条件为 X 是基本可行解。,【定理2.3】若线性规

10、划有最优解,则最优值一定可以在可行解集合的某个极点上达到,最优解就是极点的坐标向量。,注：定理2.2刻划了可行解集的极点与基本可行解的对应关系，极点是基本可行解，反之，基本可行解一定是极点，但它们并非一一对应，有可能两个或几个基本可行解对应于同一极点(退化基本可行解时)。,线性规划的基本定理,2.4 基本概念Basic Concepts,定理2.3描述了最优解在可行解集中的位置，它也表明若线性规划问题有最优解，则必有基本最优解，且若最优解惟一，则最优解只能在某一极点上达到；若具有多重最优解，则最优解是某些极点的凸组合，从而最优解是可行解集的极点或界点，不可能是可行解集的内点。,若线性规划的可行

11、解集非空且有界，则一定有最优解；若可行解集无界，则线性规划可能有最优解，也可能没有最优解；若线性规划具有无界解，则可行域一定无界。,定理2.2及2.3还给了我们一个启示，寻求最优解可不在无限个可行解中去找，而是去有限个基本可行解中去找。下一节将介绍一种有效地寻找最优解的方法。,2.4 基本概念Basic Concepts,2.5 单纯形法Simplex Method,单纯形计算方法(Simplex Method)是先求出一个初始基可行解并判断它是否最优，若不是最优，再换一个基可行解并判断，直到得出最优解或判断出问题无最优解。它是一种逐步逼近最优解的迭代方法。,当系数矩阵A中可以观察得到一个可行

12、基时(通常是一个单位矩阵或m个线性无关的单位向量组成的矩阵)，则可以通过解线性方程组求得基本可行解。,2.5 单纯形法 Simplex Method,2.5.1 普通单纯形法,【例3】用单纯形法求下列线性规划的最优解,【解】化为标准型:,2.5 单纯形法 Simplex Method,系数矩阵A及可行基B1,r(B1)=2,B1是一个初始基,x3、x4为基变量,x1、x2为非基变量,令x1=0、x2=0,由约束方程知x3=40、x4=30得到初始基本可行解,X(1)=(0,0,40,30)T,2.5 单纯形法 Simplex Method,上述基本可行解是不是最优解？,我们可在目标函数中把基变

13、量用非基变量来表示，则可根据非基变量的系数来判断目标函数有没有达到最优值，把判别线性规划问题是否达到最优解的数称为检验数，记作j(j=1,2,n)。,本例中1=3,2=4,3=0,4=0。,最优解判断标准:当所有检验数j0(j=1，n)时，基本可行解为最优解。,注：当目标函数中有基变量xi 时，利用约束条件将目标函数中的 xi 消去即可求出检验数。,2.5 单纯形法 Simplex Method,检验数:目标函数用非基变量表达时的变量系数。,典则形式(典式):(1)约束方程组中基变量的系数矩阵是的单位矩阵，移项后基变量可由非基变量表出；(2)目标函数中不含有基变量，只含非基变量(因为基变量可由

14、非基变量表出)。,通常我们把典式中的相关数据列在一张表上，显得比较直观、简洁。若初始基可行解不是最优解，我们也可直接在表上进行作业，换到下一个基可行解，把这样的表叫做单纯形表。,2.5 单纯形法 Simplex Method,如何通过观察第一个基本可行解并能判断是否为最优解，关键看模型是不是典则形式（简称典式）：,进基列,出基行,bi/ai2，ai20,i,表2.5,基变量,1,10,0,0,1/3,0,1/3,10,5/3,1,-1/3,40,5/3,0,-4/3,30,1,0,3/5,-1/5,18,0,1,-1/5,2/5,4,0,0,-1,-1,将3化为1,2.5 单纯形法 Simpl

15、ex Method,30,18,单纯形法的计算步骤：,1.找一个初始可行基，写出对应的典式，列出初始单纯形表,其中基变量的检验数必为零；,2.判断：(a)若j(j，n)，则得到最优解；(b)若存在某个k0且aik(i=1，2,m)，则线性规划具有无界解；(c)若存在k0且aik(i=1,m)不全非正，则进行换基；,1.5 单纯形法 Simplex Method,3.换基：(a)选进基变量：设k=max j|j 0,选第k列所对应的变量xk为进基变量。,第个比值最小，选最小比值对应行的基变量为出基变量，若有相同最小比值，则任选一个aLk为主元素。,(c)求新的基可行解：用初等行变换方法将aLk化

16、为,第 k 列其它元素化为零（包括检验数行）得到新的可行基及基本可行解，再判断是否得到最优解。,(b)选出基变量：求最小比值,1.5 单纯形法 Simplex Method,【例4】用单纯形法求解,【解】将数学模型化为标准型：,1.5 单纯形法 Simplex Method,表1.6,1/3,1,5,0,1,20,3,0,17,1,3,75,1/3,0,9,0,2,20,25,60,1,0,17/3,1/3,1,25,0,1,28/9,1/9,2/3,35/3,0,0,98/9,1/9,7/3,最优解X=(25，35/3，0，0，0)T，最优值 Z=145/3,1.5 单纯形法 Simplex Method,作业：教材P3435 T 8(1)，11(1),1.3 线性规划的标准型Standard form of LP,下一节：基本概念,