线性规划与单纯形法.ppt

1,运筹学,线性规划与单纯形法,2,运 筹 学,教师：赵玮 电话：,3,引言,数学要求 课程的地位与作用 运筹学概要,4,5,线性规划(LP),问题与建模 二维线性规划图解法 计算机解法 极小化下的求解与大M法 灵敏度分析 对偶规划 LP求解步骤与OR软件包操 建模与案例分析,6,线性规划(LP),问题与建模 二维线性规划图解法 计算机解法 极小化下的求解与大M法 灵敏度分析 对偶规划 LP求解步骤与OR软件包操 建模与案例分析,例1、例2，基本概念 模型的基本化,7,线性规划(LP),问题与建模 二维线性规划图解法 计算机解法 极小化下的求解与大M法 灵敏度分析 对偶规划 LP求解步骤与OR软件包操 建模与案例分析,基本原理 图解法步骤 最优解的几种类型,8,线性规划(LP),问题与建模 二维线性规划图解法 计算机解法 极小化下的求解与大M法 灵敏度分析 对偶规划 LP求解步骤与OR软件包操 建模与案例分析,图解法的启示与求解思路 需待解决的理论问题 基本概念与基本理论 算法（单纯形法）与求解 退化与循环,9,线性规划(LP),问题与建模 二维线性规划图解法 计算机解法 极小化下的求解与大M法 灵敏度分析 对偶规划 LP求解步骤与OR软件包操 建模与案例分析,图解法的启示与求解思路 需待解决的理论问题 基本概念与基本理论 算法（单纯形法）与求解 退化与循环,三种元素算法的比较 单纯形法求解思路 最优解的搜索 迭代过程与检验数 迭代与基变换 单纯形表计算 单纯形表基变换的进一步认识,10,线性规划(LP),问题与建模 二维线性规划图解法 计算机解法 极小化下的求解与大M法 灵敏度分析 对偶规划 LP求解步骤与OR软件包操 建模与案例分析,图解法的灵敏度分析 计算机解法的灵敏度分析,11,线性规划(LP),问题与建模 二维线性规划图解法 计算机解法 极小化下的求解与大M法 灵敏度分析 对偶规划 LP求解步骤与OR软件包操 建模与案例分析,对偶规划及其经济含义 对偶规划基本理论 对偶单纯形法 算法比较 影子价格,12,2. 线性整数规划,基本概念 定义 研究概况 分支定界法的理论与算法 基本思想 算法与判别准则,13,线性规划,人力资源分配的问题 例1. 某昼夜服务的工交公交线路每天各时间段内所需司机和乘务人员数如下：,14,xi： 实际安排司乘人员数 设司机和乘务人员分别在各时间段一 开始时上班，并连续工作八小时，问该公 交线路怎样安排司机和乘务人员，既能满 足工作需要，又配备最少司机和乘务员？ 解：设xi表示第i班次时开始上班的司 机和乘务人员数，这样可以知道在第i班 工作的人数应包括第i-1班次时开始上班的 人员数和第班次时开始上班的人员数，例 如有x1 +x270。又要求这六个班次时开 始上班的所有人员最少，既要求x1 +x2 +x3+x4 +x5 +x6最小，这样建立如下的数 学模型：,15,目标函数：min z = (x1 +x2 +x3+x4 +x5 +x6) 约束条件：,16,生产计划决策,例2. 某工厂在计划内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A,B两种原材料的消耗，以及资源的限制，如下表所示。,17,可以用x1和x2的线性函数形式来表示工 厂所要求的最大利润的目标： max z=50x1+100x2 其中max为最大化的符号（最小化符号为 min)；50和100分别为单位产品、的利 润。上式称为目标函数。同样也可以用x1和x2 的线性不等式来表示问题的一些约束条件。 对于台时数方面的限制可以表示为： x1+x2300. 同样，原材料的限量可以表示为 2x1+2x2400 x2250,18,暂不考虑市场需求。该工厂每生产一单位 产品可获利50元，每生产一单位产品可获 利100元，问工厂应分别生产多少个产品和 产品才能使工厂获利最多？ 这个问题可以用以下的数学模型来加以描 述。工厂目前要决策的问题是生产多少个产 品和产品，把这个要决策的问题用变量x1、 x2来表示，则称x1和x2为决策变量，即决策变 量x1=生产产品的数量，决策变量x2 =生产 产品的数量。,19,除了上述约束外，显然还应该有x10， x20， 因为产品、产品的产量是不能取负值的。综上 所述，就得到了例1的数学模型如下： 目标函数：max z=50x1+100x2 满足约束条件：,20,问题与建模,模型：对真实系统的结构与行为用图、解析式或方程来描述的合称为模型。 预测模型 评价模型 优化模型 仿真模型,21,例1. 生产计划决策,max z=50x1+100x2 xj生产产品j的数量,22,例2. 人力资源分配问题决策,min z = (x1 +x2 +x3+x4 +x5 +x6) xj：第j个班次司乘人员数,23,LP四要素 s.t ：subject约束条件 z称为目标函数 xj称为决策变量 max或min成为优化准则 LP def1： 若目标函数z为决策变量xj的线性函数，约束条件亦为决策变量xj的线性不等式（或等式），则该数学表达式（模型）称为线性规划。若目标与约束中至少有一为非线性时，则该模型称为非线性模型（NLP）。,24,模型的标准化,标准化LP模型的特点 目标函数仅限与极大化（或极小化） 所有约束条件均由等式表示 所有决策变量限于取非负值 每一约束不等式（或等式）之右端均为非负值,25,n：决策变量个数 m：约束方程个数,26,模型的标准化,约束方程的标准化（增加变量个数换取求解难度）,27,28,模型的标准化,def2：满足所有约束条件的解x称为LP的可行解，使目标函数z取得最大（小）的可行解x*称为LP的最优解，此时对应的目标函数值z (x *)称为LP的最优值。 例1的解,29,例1 （标准化模型）,模型的标准化,30,模型的标准化,例2 （标准化模型）,31,二维LP图解法,(利用解析式与平面区域对应关系求解) 基本原理 图解法步骤 最优解的几种类型,32,基本原理,33,def3：满足LP中所有约束条件（不等式或等式约束）的点必在这些约束条件所对应区域所围成的公共区域D内，则称此公共区域D为LP的可行域。 例1,34,当目标函数z取z1，z2，z3时， 直线 有相同的斜率和不同的截距，这一族平行直线称为等值线族；目标函数按优化准则递增（或递减）的方向称为等值线族的法线方向。 z=x1+x2=300称为等值线，因直线上的点（0，300），（300，0），（150，150），（100，200）等均具有相等的目标函数值300。,35,图解法步骤,在平面x1ox2上求出LP的可行域 利用目标函数作等值线族 求出等值线的法线方向 等值线沿法线方向（max准则递增方向，min准则递减方向）移动，并使目标函数z到（max, min)时，其与可行域D相交之点即为最优解,36,最优解的几种类型,唯一解 无穷多解 无界解 无最优解,37,例1. 唯一解,max z=50x1+100x2,38,例2. 无穷多解,max z=50x1+50x2,39,例3.无界解,max z=x1+x2,40,例4. 无最优解,max z=50x1+50x2,350,41,计算机算法 (图解法只对n3有效),图解法的启示与计算机求解思路 需待解决的理论问题 基本概念与理论 算法与求解 退化与循环,42,图解法的启示与计算机求解思路,最优解 在可行域D内（或边界） 最优解 在D的顶点或边界达到 求解思路设想：首先搜索D的顶点，然后通过顶点对应的目标值的比较来求解最优解,43,计算机求解,寻找Ax=b,非基变量=0之解（基本解）,寻找max z=Cx ，Ax=b ，x0之解（最优解）,寻找Ax=b, 非基变量=0， x0之解 （基本可行解）,图解法（n3）,可行点（D内点）,顶点,目标函数值比较,？,44,def4：在 之LP中，若rank (A) = mn， 则A（或对A作初等行变换）中必有m个线性武官的列向量，他们够成满秩矩阵B ( |B| 0 )，使有A=( B, N )（或( N, B )或其它），称B为A的一个基，此中N为A中除B外的子阵，相应的决策变量亦有x=( xB, xN )T，此中称xB中各分量为基变量， xN中各分量为非基变量，B中各列称为基向量，N中各列称为非基向量。 满足方程Ax=b，且取非基变量为0时的解称为LP基本解，满足非负条件（x 0）的基本解称为基本可行解，对应的基B称为可行基，满足 的解称为可行解。,45,例1.,求A的基，基向量，非基向量，LP的基变量，非基变量，基本解，基本可行解，最优解，,46,47,四种解的相互关系,最优解,基本可行解,基本解,可行解,后述定理,def4,def4,为基本解，但非可行解（x 0）,为可行解，但非基本解xN = 0,?,?,48,搜索算法思路,最优解,基本可行解,基本解（在计算机上易于求得）,满足x0,逐个比较 目标函数值,49,需待解决的理论问题,什么条件下LP的可行域非空？可行域D有何特性？ （Th1) 可行域D是否有顶点？顶点有多少个？顶点的数学含义？ （Th2) 是否一定能保证最优解在顶点（D内）上达到？ （Th3)， 顶点是什么概念？ 基本可行解是否存在？如何判断？ （Th4) 基本可行解是否唯一对应D的一个顶点？ （Th5) 如何求基本可行解？ （Th6),50,基本概念与理论,def5：设D为Rn中一点集，若对 则称D为凸集。 几何意义：凸集D内的任两点联线上的点仍在D内（含边界） def6：设D为Rn中一点集， 则称z为凸集D的顶点。 几何意义：凸集D的任何顶点都不可能在D内任两点的联线上。,51,52,Th1： 若rank (A) = mn，则LP的可行域 非空且为凸集,基本概念与理论,53,Th2：在LP中，若可行域D为非空凸集时，则D中至少有一个顶点，且顶点个数为有限。 Th3：在LP中，若可行域D为非空凸集且有界时，则LP最优解必在D的顶点上达到。 Th4：在LP中，若有可行解（即D非空），则LP至少有一基本可行解。 Th5：x是LP的基本可行解 x是LP可行域D的顶点 Th1Th5解决了上述问题（1）（5）,基本概念与理论,54,需待解决的理论问题,什么条件下LP的可行域非空？可行域D有何特性？ （Th1) 可行域D是否有顶点？顶点有多少个？顶点的数学含义？ （Th2) 是否一定能保证最优解在顶点（D内）上达到？ （Th3)， 顶点是什么概念？ 基本可行解是否存在？如何判断？ （Th4) 基本可行解是否唯一对应D的一个顶点？ （Th5) 如何求基本可行解？ （Th6),55,基本概念与理论,Th6：见后（基本可行解是否为最优解的判别法则，及无最优解的判别）。 Th7：求解过程中基本可行解迭代准则 Th8：最优解的线性组合 Th9：无穷多组解的判断,56,算法与求解,三种主流算法的比较 单纯形法求解思路 最优解的搜索思路 迭代过程与检验数 迭代与基变换 单纯形表计算 基变换的进一步认识,57,三种主流算法的比较,？,58,非主流算法：修正单纯形法，阶段法，M法，对偈单纯形法（均为单纯形发法变型），随机搜索法等。 1 算法复杂性定义：在输入规模均为L的所有可能问题中，在最坏的情况下，算法需要执行的基本运算总次数f (L)，称为该算法的计算时间复杂性，简称复杂性。,耗费时间多少,仅考虑算法执行的基本运算次数（指+、大小比较、转移指令）,满足精度要求下,排除计算机性能因素,消除LP规模因素,评价算法好坏,59,单纯形法求解思路,计算机 求解思路,?,显然,Th1,Th4,Th6,Th5,Th2,60,最优解的搜索思路,A,. . .,. . .,解的迭代,解的迭代,61,最优解的搜索思路,枚举所有的顶点作比较是不可行的，因为若 ，则D可能有 个可能顶点（基本解）。 m阶子阵,62,为使计算机能自动变更顶点，注意到两个相邻顶点对应的可行基仅有一个列向量不同的特点（可以证明，高等几何），故在已得到一个顶点（对应一个基本可行解或一个可行解）后，只需变更一个列向量，使其仍为一个基本可行解（顶点）即可。,最优解的搜索思路,63,最优解的搜索思路,若 ，则一顶点的相邻顶点有n个，究竟哪一个相邻顶点作为迭代的首选？ 这种迭代过程（由一个顶点到另一个顶点）应保证有以下不等式才能是有效的算法： ，故需研究判断 的算法。 应寻找这种迭代的终止规则（称为最优性准则）。,64,迭代过程与检验数,命题：若 ，任取A的m阶子阵，设 则目标函数 必可由非基变量 描述。,65,证：rank (A)=mn，对应于基B，Ax=b总可经过初等行变换，转换成下式：,66,67,68,迭代过程与检验数,def7：若B为A的可行基，则LP的目标函数z(x)可用非基变量 来描述如（*）式，则称此中非基变量 前之系数 为检验数（ ）,69,迭代过程与检验数,Th6：设有LP （1）若 为LP对应于可行基B的基本可行解，且对于 ， 则 为LP的最优解，并有最优值 。 （2）若 ，使 ，且对应PK 0（即 ），则LP无最优解。,70,证明： （1） （2）略,71,迭代与基变换,def 8：在LP求解过程中，由一个可行基 转换成另一个可行基 (j=0,1,l-1)的过程称为基变换，为使每次作基变换时，对应的D中的一个顶点 转换成另一相邻顶点 ，这只需在可行基Bj中仅改变一个列向量(基向量)即可，则该改变的列向量基向量对应的基变量称为出基向量，与此同时，应将A中另一非基变量转为基变量，此非基变量称为入基变量，经如此变换后，则可由一个可行基 转变成一个新的可行基 ，一般入基向量应为主元为1的单位向量。 以下定理保证经上述的基变换后，对应的新的基本可行解将不劣于原基本可行解，但如何使基变换（或迭代）的效率更高，至今仍未解决此问题。,72,73,无最优解,有无穷多个最优解,定主列K，取为入基变量 定主行，取为出基变量,END,Y,Y Th6,N,Y Th9,Th7,74,75,Th7：满足上述条件的出入基准则所得的新基本可行解 ，必含有 ，此中 为未经迭代前的基本可行解。,76,单纯形表计算,77,单纯形表计算,例1.(唯一最优解),78,79,初始单纯形表见上表，需从A中选取初始基B0，一般取B0=I，若无，可经初等行变换获得，或引入人工变量（大M）。 。 。 。 在迭代过程中，迭代前后的两个可行基有m-1个相同的列向量，只有一个列向量不同，这样的基称为相邻基，几何上可证明在非退化的情况下，代表可行域D上的两个相邻顶点。本例有,80,。,81,。 各次迭代之入、出基变量与主元素,82,例4 .,单纯形表计算,无有界最优解,Y,N,83,解：图解法已得 ，现用单纯形法求解。,基变量,84,Th8： 证：,85,86,87,i+1,迭代数,88,89,90,基变换的进一步认识,A,B1,B2,B3,BL,B0,91,基变换的进一步认识,。,92,详见下例1之单纯形表，其中,93,94,。 。 。,95,96,综合作业,设计与开发一个LP软件包应解决哪些问题？对解决这些问题你有何设想,97,退化与循环,def9：设 为LP的基本可行解，若x B的所有基变量分量都取正值，即x B 0，则称 是非退化的，若 中有一个或多个基变量分量取0，则称 为退化的，若LP的每一个基本可行解都是非退化的，则称LP为非退化的。,98,退化与循环,当采用单纯形法求解时，若在迭代过程中出现了退化的基本可行解，则继续迭代下去可能产生如下三种结果： 退化是暂时的，最终得到非退化的最优解（如例5）。 最后得到退化的最优解。 产生循环（Cycling）,目标函数得不到改善，永远得不到最优解（如例6）。,99,退化与循环,Th10：若LP是非退化的，则经过有限步单纯形迭代后，或者能判定LP没有最优解，或者能够求得最优解。 即使基本可行解是非退化的，但在确定出基变量时，若有两个（或两个以上）比值（对应不同行）相等时，当采用min准则选出基变量时，仍有可能使新的基本可行基成为退化解，如i=0时，xB0=(2,4,3)T为非退化解，出现min比值=min2/1,4/2,3/1 =2/1或4/2，此时可选s1或s2 作出基变量。由上表当选s1为出基变量时，经基变换由i=1之表知有xB0=(2,0，1)T，显然此为退化解。,100,退化与循环,。 由上表知此时虽经多次迭代，但目标函数无改进，但由于未产生循环现象，经4次迭代后得最优解：,101,退化与循环,例6 则由于退化基本可行解而出现了循环现象，可证明例6之LP有最优解，但经过6次迭代有 目标函数未得到改进而未能求得最优解。,102,退化与循环,例5,103,无改进,104,例6. (P97，E.beale给出的循环例） 本例与教材（P97）变量对应表,105,循环,106,B1,B2,B3,B4,B5,B6,B0,B0=,A(6)=A(0)，b(6)=b(0),107,退化与循环,为避免循环可用 摄动法（由A. Charnes于1952年提出） 也可用布兰德（R. G. Bland）提出的反循环法（1976年） 或Dantzig（1954年）提出的字典法来解决。,108,Bland法则如下：当所有变量均按x1, x2,xn排序时， 若有若干个检验数均为正时，可选其中下标最小的非基变量作为入基变量，即取k = min j |j 0为入基变量之下标，xK为入基变量。 若有若干个比值同时达到极小时，可选其中下标最小的基变量为出基变量，即取 为出 基变量下标。,109,极小化准则与大M法,例7. (P85),110,解1,111,极小化准则与大M法,人工变量引入的准则： 人工变量的引入应不影响约束条件，也不影响目标函数的求解 为构成基B=I，A中缺K个单位向量就引入K个人工变量（上例缺2个） 人工变量引入后，为不影响约束方程应使 的最优解中人工变量为非基变量（即取 ） 由于人工变量的引入为构成基I=B，故第0次迭代时 已成为基变量，因此在 以后的迭代过程中应尽可能将 从基变量中替换出来而成为非基变量，从而保证基本可行解分量 。,112,极小化准则与大M法,将目标函数设计成下型： 即能满足上述要求。这是由于只要 迭代过程中，若基变量含有一个人工变量，则上述设计的目标函数z(x)就不可能达到极大化（max），因此只要不出现退化现象， 在经有限次迭代后总可将引入的人工变量一个一个地替换出来，而成为非基变量。因而有 如此的 ，其最优解与LP最优解相同（ ）。,113,极小化准则与大M法,M 1故不必考虑其具体数值。本方法称为大M法来源与此。 若 在某一次迭代中，仍然为基变量，则目标函数 （此时 为基本可行解之一分量应满足非负条件 ），从而使此基本可行解不可能是最优解。,114,极小化准则与大M法,若采用大M法始终无法将人工变量从基变量替换出来，此时有两种情形： 所有检验数已有 ，此时应认为无解。 上述最优性条件仍未具备，需始终迭代下去，或改用其它方法。,115,例7. 解2,116,117,118,为使b0，同时又可形成基B0=I，可在原增广矩阵（A0：b0）基础上作初等行变换以形成人工基B0=I。 。,119,此经一次迭代即可得最优解 将约束方程变形成下述，虽然保证有一个B0=I，但约束方程右端的b(i)0非负条件被破坏，从而使用单纯形法时，获得的可行解虽然是基本解，但非基本可行解。 易知此非基本可行解，故采用单纯形法无效。,120,例8. (P88，无最优解例） 解：引入松弛变量s1，s2，剩余变量s3，人工变量a1，可得上述标准型。,121,122,当M0，经二次迭代后，已有 ，按照一般原理下有下述的x(2)=(30,6,0,0,4)T应为最优解，并迭代终止。 . 虽然有z(x0)z(x1)z(x2)目标值早增大，但根据大M法原理应将人工变量以基变量xB中替换出来，而i=2时，由上表知a1仍为基变量，故此时应认为无最优解,123,事实上由图解法知该问题无可行解。或将,124,灵敏度分析,图解法下的灵敏度分析 定义：研究LP问题中目标函数系数C与约束条件中系数矩阵A与常数向量b的变化（局部或全部变动）对LP的最优解 与最优值 的影响程度分析的问题称为LP的灵敏度分析。 由于C，b，A通常表述产品需求，原材料价格，未来的商品售价及企业的加工能力、资源消耗，故在数学建模时的估计有可能出现误差，且未来的环境亦是不确定的，有可能出现变化，因此有必要对应用问题的解作灵敏度分析。,125,图解法下的灵敏度分析 灵敏度分析通常讨论如下内容： C，b，A变动（局部或全部）后LP最优解是否仍存在？若存在的话，最优解有多大程度的变化？ C，b，A在什么范围内变动时能保证LP的原最优解不变？ 若C，b，A的变动超出上述范围后，如何利用LP的原最优解 来求解变动后的 最优解。 这些C，b，A的变动，在出现情况下对决策者有利？在什么情况下对决策者不利？此称为对偶价格研究对象（C的变动对目标最优解的影响）。,126,各种问题求解 问题建模 求解算法（理论、算法步骤、计算复杂性） 解的存在性、唯一性、可靠性（误差分析、灵敏度分析）,127,估计有误差 未来环境变动,数值解,精确解,灵敏度分析,误差分析,数值解,估计正确,128,LPa（LP原规划）,max z=50x1+100x2,129,LPb（C的变动对LP最优解的影响）,max z=60x1+50x2,130,LPc（b1的变动对LP最优解的影响）,max z=50x1+100x2,131,LPd（b2的变动对LP最优解的影响）,max z=50x1+100x2,132,命题：在例1 的优化模型中，A，b不变，讨论C变动的如下问题： 欲使LP的最优解不变，仍为 ，C1与C2应满足什么条件？ 当C2=100 不变，欲使LP 的最优解不变，仍为 ，C1应满足什