运筹学第二章线性规划第二讲标准型与单纯形法.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是约

2、束方程的个数，n是决策变量的个数，一般情况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

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

4、Standard form of LP,2.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

5、(A)=2，2阶子矩阵有C52=10个，其中第1列与第3列构成的2阶矩阵不是一个基，基矩阵只有9个，即,当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为基向量(basic vector)，其余列向量称为非基向量;,基向量对应的变量称为基变量(basic variable)， 非基向量对应的变量称为非基变量 ；,在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基变量，x2、x3、x5是非基变量。基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。,2.4 基本概念 Basic Concepts,可行解(feasible solution)

6、: 满足式(2.2)及(2.3)的解X=（x1, x2 , xn)T 称为可行解；,基本可行解(basic feasible solution): 若基本解是可行解 则称为是基本可行解（也称基可行解）。,基本解(basic solution) : 对某一确定的基B，令非基变量 等于零，利用式(2.2)解出基变量，则这组解称为基 的 基本解。,最优解(optimal solution): 满足式(1.1)的可行解称为最优 解，即使得目标函数达到最大值的可行解就是最优解；,非可行解(infeasible solution) 无界解 (unbounded solution),2.4 基本概念 Bas

7、ic Concepts,显然，只要基本解中的基变量的解满足式(2.3)的非负要求，那么这个基本解就是基本可行解。,在上例中，对来说，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, 不是可行解，因此

8、也不是基本可行解。,可行基: 基可行解对应的基称为可行基； 最优基: 基本最优解对应的基称为最优基； 如上述B3就是最优基，最优基肯定是可行基。,2.4 基本概念 Basic Concepts,基本最优解: 最优解是基本解称为基本最优解。例如 满足式(2.1)(2.3)是最优解, 又是B3的基本解, 因此它是基本最优解。,注：当最优解惟一时，最优解亦是基本最优解， 当最优解不惟一时，则最优解不一定是基本最优解。,基本最优解、最优解、基本可行解、基本解、可行解的关系:,基本最优解,基本可行解,可行解,最 优 解,基本解,2.4 基本概念 Basic Concepts,凸集(Convex set)

9、: 设 K 是 n 维空间 Rn 的一个点集，对 任意两点 时，则称K为凸集。,就是以X(1)、X(2)为端点的线段方程, 点X的位置由的值确定, 当=0时, X=X(2), 当=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 基本概念 Basi

10、c Concepts,【定理2.1】 若线性规划可行解集 K 非空, 则 K 是凸集。,【定理2.2】 线性规划的可行解集合 K 的点 X 是极点的充要条件为 X 是基本可行解。,【定理2.3】 若线性规划有最优解, 则最优值一定可以在可行解集合的某个极点上达到, 最优解就是极点的坐标向量。,注：定理2.2刻划了可行解集的极点与基本可行解的对应关系，极点是基本可行解，反之，基本可行解一定是极点，但它们并非一一对应，有可能两个或几个基本可行解对应于同一极点(退化基本可行解时)。,线性规划的基本定理,2.4 基本概念 Basic Concepts,定理2.3描述了最优解在可行解集中的位置，它也表明

11、若线性规划问题有最优解，则必有基本最优解，且若最优解惟一，则最优解只能在某一极点上达到；若具有多重最优解，则最优解是某些极点的凸组合，从而最优解是可行解集的极点或界点，不可能是可行解集的内点。,若线性规划的可行解集非空且有界，则一定有最优解；若可行解集无界，则线性规划可能有最优解，也可能没有最优解；若线性规划具有无界解，则可行域一定无界。,定理2.2及2.3还给了我们一个启示，寻求最优解可不在无限个可行解中去找，而是去有限个基本可行解中去找。下一节将介绍一种有效地寻找最优解的方法。,2.4 基本概念 Basic Concepts,2.5 单纯形法 Simplex Method,单纯形计算方法(

12、Simplex Method)是先求出一个初始基可行解并判断它是否最优，若不是最优，再换一个基可行解并判断，直到得出最优解或判断出问题无最优解。它是一种逐步逼近最优解的迭代方法。,当系数矩阵A中可以观察得到一个可行基时(通常是一个单位矩阵或m个线性无关的单位向量组成的矩阵)，则可以通过解线性方程组求得基本可行解。,2.5 单纯形法 Simplex Method,2.5.1 普通单纯形法,【例3】 用单纯形法求下列线性规划的最优解,【解】化为标准型:,2.5 单纯形法 Simplex Method,系数矩阵A及可行基B1,r(B1)=2, B1是一个初始基, x3、x4为基变量, x1、x2为非

13、基变量, 令x1=0、x2=0, 由约束方程知x3=40、x4=30得到初始基本可行解,X(1)=(0, 0, 40, 30)T,2.5 单纯形法 Simplex Method,上述基本可行解是不是最优解？,我们可在目标函数中把基变量用非基变量来表示，则可根据非基变量的系数来判断目标函数有没有达到最优值，把判别线性规划问题是否达到最优解的数称为检验数，记作j ( j=1,2,n)。,本例中1=3,2=4,3=0,4=0。,最优解判断标准: 当所有检验数j0(j=1，n)时，基本可行解为最优解。,注：当目标函数中有基变量xi 时，利用约束条件将目标函数中的 xi 消去即可求出检验数。,2.5 单

14、纯形法 Simplex Method,检验数: 目标函数用非基变量表达时的变量系数。,典则形式(典式): (1)约束方程组中基变量的系数矩阵是的单位矩阵，移项后基变量可由非基变量表出； (2)目标函数中不含有基变量，只含非基变量(因为基变量可由非基变量表出)。,通常我们把典式中的相关数据列在一张表上，显得比较直观、简洁。若初始基可行解不是最优解，我们也可直接在表上进行作业，换到下一个基可行解，把这样的表叫做单纯形表。,2.5 单纯形法 Simplex Method,如何通过观察第一个基本可行解并能判断是否为最优解，关键看模型是不是典则形式（简称典式）：,进基列,出基行,bi /ai2，ai20

15、,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 单纯形法 Simplex Method,30,18,单纯形法的计算步骤：,1. 找一个初始可行基，写出对应的典式，列出初始单纯形表,其中基变量的检验数必为零；,2. 判断： (a)若j( j，n)，则得到最优解； (b)若存在某个k0且aik(i=1，2,m)，则线性 规划具有无界解； (c)若存在k0且aik (i=1,m)不全非正，则进行换基；,1.5 单纯形法 S

16、implex Method,3. 换基： (a)选进基变量：设k=max j | j 0, 选第k列所对应的变量xk为进基变量。,第个比值最小，选最小比值对应行的基变量为出基变量，若有相同最小比值，则任选一个aLk为主元素。,(c)求新的基可行解：用初等行变换方法将aLk化为, 第 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,下一节：基本概念,