第1章线性规划及单纯形法PPT讲稿.ppt

第1章线性规划及单纯形法第1页，共65页，编辑于2022年，星期日第一章第一章 线性规划及单纯形法线性规划及单纯形法线性规划是运筹学的基础第2页，共65页，编辑于2022年，星期日第一节 一般线性规划问题的数学模型本节内容：w一、线性规划问题简介w二、线性规划问题的数学模型w三、线性规划问题的标准形式w四、线形规划模型的标准形式的转化第3页，共65页，编辑于2022年，星期日一、线性规划问题简介w线性规划能解决哪类问题？有限资源的最佳分配问题：资源分配问题；成本有限资源的最佳分配问题：资源分配问题；成本收益平衡问题；网络配送问题收益平衡问题；网络配送问题w w线性规划的广泛应用是计算机时代的产物。线性规划的广泛应用是计算机时代的产物。w w19021902年，Julius Farkas Julius Farkas 发表论文，阐述有关线性规划发表论文，阐述有关线性规划问题。问题。w1938年，英国人康德进行较详细研究。年，英国人康德进行较详细研究。w w19471947年，美国学者年，美国学者George Dantzig（丹茨格）发明（丹茨格）发明了求解线性规划的单纯形法（了求解线性规划的单纯形法（1951年发表），从而为线性规划的推广奠定了基础。有人认为，求解线性规划的单纯形算法可与求解线性方程组的高斯消元法相媲美。第4页，共65页，编辑于2022年，星期日二、线性规划问题建模举例w w资源分配问题：教材第资源分配问题：教材第6 6页例页例2 2w w企业计划生产企业计划生产I I，II II两种产品，它们分别在两种产品，它们分别在A A，B B，C C，D D四四种不同设备上加工，具体生产时间及各设备加工能力种不同设备上加工，具体生产时间及各设备加工能力如下表：如下表：w w求：企业如何安排两种产品的产量，使得总利润最大求：企业如何安排两种产品的产量，使得总利润最大设备设备A B C DA B C D单位利润单位利润产品产品1 1产品产品2 2 2 1 4 0 2 1 4 0 2 2 0 4 2 2 0 4 2 2 3 3加工能力加工能力 12 8 16 12 12 8 16 12第5页，共65页，编辑于2022年，星期日二、线性规划问题建模举例 w w解：根据题意，选择决策变量为解：根据题意，选择决策变量为x x1 1，x x2 2，分别代表，分别代表I I，II II两种产品在计划两种产品在计划期内的产量。期内的产量。w w设利润为设利润为Z Z，则，则 maxZ=2xmaxZ=2x1 1+3x+3x2 2 （1 1）w w此为企业追求的目标，故称为目标函数。此为企业追求的目标，故称为目标函数。w w根据题意，两种产品在计划期内的产量应该满足各设备的生产时间限制，根据题意，两种产品在计划期内的产量应该满足各设备的生产时间限制，则有：则有：w w w w w w （2 2）w w以上的不等式左端均为决策变量以上的不等式左端均为决策变量x x1 1，x x2 2的函数，因此称为函数约束的函数，因此称为函数约束w w两种产品的产量应为非负，即应满足以下限制条件：两种产品的产量应为非负，即应满足以下限制条件：w w w w （3 3）w w上面的称为非负性约束。上面的称为非负性约束。w w（2 2）（）（3 3）统称为约束条件。）统称为约束条件。第6页，共65页，编辑于2022年，星期日二、线性规划问题建模举例 w因此，该问题的数学模型可以归结为：在约束条件（2）（3）下，确定变量x1，x2，的数值，使目标函数（1）式的函数值Z达到最大，上述数学模型可简记为：w maxZ=2xmaxZ=2x1 1+3x+3x2 2w其中，max是maximize的缩写，s.t.是subject to（受约束于）的缩写第7页，共65页，编辑于2022年，星期日三、线性规划问题的数学模型 1.三个组成要素：三个组成要素：w决策变量：问题中的未知量，一般由研究者的决策部门加以确定，故称决策变量。w目标函数：决策目标，为决策变量的函数。w约束条件：可用资源的限制。第8页，共65页，编辑于2022年，星期日三、线性规划问题的数学模型三、线性规划问题的数学模型 小结小结1 1：建模的基本步骤：建模的基本步骤：建模的基本步骤：建模的基本步骤w w设置决策变量，它们体现解决问题的方案。设置决策变量，它们体现解决问题的方案。设置决策变量，它们体现解决问题的方案。设置决策变量，它们体现解决问题的方案。w w确定目标函数，它是决策变量的函数。确定目标函数，它是决策变量的函数。确定目标函数，它是决策变量的函数。确定目标函数，它是决策变量的函数。w确定约束条件，它们是含有决策变量的不等确定约束条件，它们是含有决策变量的不等式或等式。式或等式。w w确定决策变量的取值范围，给出优化方向。确定决策变量的取值范围，给出优化方向。确定决策变量的取值范围，给出优化方向。确定决策变量的取值范围，给出优化方向。w其中，前两条称为可行条件，最后一条称为其中，前两条称为可行条件，最后一条称为优化条件。符合这三个条件的数学模型通常优化条件。符合这三个条件的数学模型通常称为线性规划的一般型（称为线性规划的一般型（generalgeneral）。）。第9页，共65页，编辑于2022年，星期日三、线性规划问题的数学模型三、线性规划问题的数学模型 小结小结小结小结2：数学模型的共同结构：数学模型的共同结构w w存在一组决策变量，对它们可有非负要求；存在一组决策变量，对它们可有非负要求；存在一组决策变量，对它们可有非负要求；存在一组决策变量，对它们可有非负要求；w w存在一个以决策变量为自变量的目标函数，且存在一个以决策变量为自变量的目标函数，且存在一个以决策变量为自变量的目标函数，且存在一个以决策变量为自变量的目标函数，且它为线性函数；它为线性函数；它为线性函数；它为线性函数；w w存在一组约束条件，且每个条件都是由决策变量存在一组约束条件，且每个条件都是由决策变量存在一组约束条件，且每个条件都是由决策变量存在一组约束条件，且每个条件都是由决策变量构成的线性不等式或等式；构成的线性不等式或等式；构成的线性不等式或等式；构成的线性不等式或等式；w w结构要求出这样的变量组，或者说决策向量，结构要求出这样的变量组，或者说决策向量，结构要求出这样的变量组，或者说决策向量，结构要求出这样的变量组，或者说决策向量，在满足约束条件和非负约束的同时，使相应的在满足约束条件和非负约束的同时，使相应的在满足约束条件和非负约束的同时，使相应的在满足约束条件和非负约束的同时，使相应的目标函数值达到最大或者最小。简言之，在一目标函数值达到最大或者最小。简言之，在一目标函数值达到最大或者最小。简言之，在一目标函数值达到最大或者最小。简言之，在一定条件下使目标函数优化。定条件下使目标函数优化。定条件下使目标函数优化。定条件下使目标函数优化。第10页，共65页，编辑于2022年，星期日三、线性规划问题的数学模型三、线性规划问题的数学模型 2.线性规划问题的数学模型：线性规划问题的数学模型：线性规划问题的数学模型：线性规划问题的数学模型：以上模型的简写形式为：以上模型的简写形式为：以上模型的简写形式为：以上模型的简写形式为：第11页，共65页，编辑于2022年，星期日三、线性规划问题的数学模型三、线性规划问题的数学模型 其向量形式为：其向量形式为：其向量形式为：其向量形式为：其中，其中，其中，其中，其中，其中，C C常常被称为价值向量，其每个分量价值系数常常被称为价值向量，其每个分量价值系数第12页，共65页，编辑于2022年，星期日三、线性规划问题的数学模型三、线性规划问题的数学模型 模型的矩阵形式为：模型的矩阵形式为：模型的矩阵形式为：模型的矩阵形式为：其中，其中，其中，其中，A A称为约束方程组变量的称为约束方程组变量的称为约束方程组变量的称为约束方程组变量的系数矩阵，或简称约束变量的系数矩阵系数矩阵，或简称约束变量的系数矩阵系数矩阵，或简称约束变量的系数矩阵系数矩阵，或简称约束变量的系数矩阵第13页，共65页，编辑于2022年，星期日三、线性规划问题的数学模型三、线性规划问题的数学模型 课堂练习：课堂练习：课堂练习：课堂练习：1.1.1.1.一一一一食食食食品品品品厂厂厂厂生生生生产产产产饼饼饼饼干干干干：生生生生产产产产两两两两种种种种饼饼饼饼干干干干A A A A，B B B B，需需需需经经经经过过过过三三三三道道道道工工工工序序序序及及及及相相相相应应应应的的的的设设设设备备备备：搅搅搅搅拌拌拌拌机机机机、成成成成型型型型机机机机、烘烘烘烘箱箱箱箱。生生生生产产产产每每每每吨吨吨吨A A A A、B B B B产产产产品品品品各各各各需需需需要要要要在在在在三三三三种种种种设设设设备备备备上上上上时时时时间间间间如如如如表表表表所所所所示示示示。单单单单位位位位利利利利润润润润：A A A A：500500500500元元元元/吨吨吨吨，B B B B：400400400400元元元元/吨。问：如何安排生产，使总利润最大？吨。问：如何安排生产，使总利润最大？吨。问：如何安排生产，使总利润最大？吨。问：如何安排生产，使总利润最大？搅拌机搅拌机 成型机成型机 烘箱烘箱 单位利单位利润润 饼干饼干A A 饼干饼干B B 3 4 4 3 4 4 5 2 4 5 2 4 500 500 400 400加工能力加工能力 15 10 22 15 10 22 第14页，共65页，编辑于2022年，星期日w w1.1.解：设总利润为解：设总利润为z z，生产饼干，生产饼干A A、B B各为各为x x1 1、x x2 2吨吨。w w maxZ=500 xmaxZ=500 x1 1+400 x+400 x2 2第15页，共65页，编辑于2022年，星期日课堂练习：课堂练习：课堂练习：课堂练习：2.2.2.2.某某某某农农农农场场场场要要要要新新新新买买买买一一一一批批批批拖拖拖拖拉拉拉拉机机机机以以以以完完完完成成成成每每每每年年年年三三三三季季季季的的的的工工工工作作作作量量量量：春春春春种种种种330330330330公公公公顷顷顷顷、夏夏夏夏管管管管130130130130公公公公顷顷顷顷、秋秋秋秋收收收收470470470470公公公公顷顷顷顷。可可可可供供供供选选选选择择择择的的的的拖拖拖拖拉拉拉拉机机机机型型型型号号号号、单单单单台台台台投投投投资资资资额额额额及及及及工工工工作作作作能能能能力力力力如如如如下下下下表表表表所所所所示示示示。问问问问：配配配配购购购购哪哪哪哪几几几几种种种种拖拖拖拖拉拉拉拉机机机机各各各各多多多多少少少少台台台台，才才才才能能能能完完完完成成成成上上上上述述述述每每每每年年年年工工工工作量且使总投资最少？作量且使总投资最少？作量且使总投资最少？作量且使总投资最少？拖拉机型号拖拉机型号单台投资单台投资（元）（元）单台工作能力（公顷）单台工作能力（公顷）春种春种夏管夏管秋收秋收东方红东方红丰收丰收跃进跃进胜利胜利5000450044005200302932311714161841434244第16页，共65页，编辑于2022年，星期日w w2.2.解：设总投资为解：设总投资为z z，购置东方红、丰收、跃进、胜，购置东方红、丰收、跃进、胜利型号拖拉机分别为利型号拖拉机分别为x x1 1、x x2 2、x x3 3、x x4 4台台。w w minZ=5000 xminZ=5000 x1 1+4500 x+4500 x2 2+4400 x+4400 x3 3+5200 x+5200 x4 4第17页，共65页，编辑于2022年，星期日课堂练习：课堂练习：课堂练习：课堂练习：3.3.3.3.运运运运输输输输问问问问题题题题如如如如下下下下表表表表。问问问问：如如如如何何何何安安安安排排排排运运运运输输输输，使使使使总总总总运运运运费费费费最最最最少？（运输方案的确定）少？（运输方案的确定）少？（运输方案的确定）少？（运输方案的确定）销地销地 产地产地A B C D产量（吨）产量（吨）甲甲 21 25 7 152000乙乙 25 51 37 151100销地（吨）销地（吨）1700 1100 200 100第18页，共65页，编辑于2022年，星期日四、线性规划问题的标准形式线性规划问题的标准形式1.1.线性规划问题的标准形式线性规划问题的标准形式线性规划问题的标准形式线性规划问题的标准形式 矩阵形式：矩阵形式：矩阵形式：矩阵形式：第19页，共65页，编辑于2022年，星期日四、线性规划问题的标准形式线性规划问题的标准形式2.2.标准形式的特点：标准形式的特点：标准形式的特点：标准形式的特点：同时满足以下四个条件：w w目标函数为求极大值目标函数为求极大值w w约束条件全为等式约束条件全为等式w w右端常数项全为非负值右端常数项全为非负值w变量的取值全为非负值第20页，共65页，编辑于2022年，星期日四、线性规划问题的标准形式线性规划问题的标准形式3.非标准形式的标准化（四种类型）：非标准形式的标准化（四种类型）：非标准形式的标准化（四种类型）：非标准形式的标准化（四种类型）：（1 1）目标函数为求极小值）目标函数为求极小值方法：令方法：令 ，则原目标函数可以化为：，则原目标函数可以化为：第21页，共65页，编辑于2022年，星期日四、线性规划问题的标准形式线性规划问题的标准形式3.3.非标准形式的标准化（四种类型）：非标准形式的标准化（四种类型）：非标准形式的标准化（四种类型）：非标准形式的标准化（四种类型）：（2 2）约束条件为不等式。（）约束条件为不等式。（时，时，+变量，松弛变量；变量，松弛变量；时，时，-变量，剩余变量）变量，剩余变量）例如：例如：，令，令 ，则约束条件可化为：，则约束条件可化为：，令，令 ，则约束条件可化为：，则约束条件可化为：，。松弛变量和剩余变量的含义松弛变量和剩余变量的含义松弛变量和剩余变量的含义松弛变量和剩余变量的含义：分别代表未被充分利用的资源和超出的资源数，均未转化分别代表未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引入模型后它们在目标函数中的系数均为价值和利润，所以引入模型后它们在目标函数中的系数均为零。为零。第22页，共65页，编辑于2022年，星期日四、线性规划问题的标准形式线性规划问题的标准形式3.非标准形式的标准化（四种类型）：非标准形式的标准化（四种类型）：（3 3）约束条件右端项）约束条件右端项 只需将等式或不等式两端同乘-1，则等式，则等式右端项必大于零。右端项必大于零。（4 4）将变量中的非正限制或无限制转化为非负限制。）将变量中的非正限制或无限制转化为非负限制。其中，对于无限制变量的处理：同时引进两个非负其中，对于无限制变量的处理：同时引进两个非负变量，然后用它们的差代替无限制变量。变量，然后用它们的差代替无限制变量。第23页，共65页，编辑于2022年，星期日例例3 3：（：（：（：（P8P8）将下述线性规划模型化为标准形式：将下述线性规划模型化为标准形式：将下述线性规划模型化为标准形式：将下述线性规划模型化为标准形式：解：令解：令 ，并引入松弛变量并引入松弛变量 和剩余变量和剩余变量 ，按上述标准化规，按上述标准化规则将问题转化为：则将问题转化为：第24页，共65页，编辑于2022年，星期日五、常用的三类线性规划问题 w1资源分配问题：约束条件全部为资源约束（用表示的约束），即一般要求资源有限。w2成本收益平衡问题：约束条件全部为收益约束（用表示的约束），即一般要求收益要大于某个值。w3运输问题的产销平衡模型：约束条件为一定形式的确定需求的约束（用表示的约束）w4混和问题：不能归于这三类的任何线性规划的问题。第25页，共65页，编辑于2022年，星期日第二节 图解法w本节内容：一、图解法的应用范围（优缺点）二、案例讨论三、图解法解题步骤四、解的讨论五、图解法对单纯形法的启示第26页，共65页，编辑于2022年，星期日一、图解法的优缺点及适用范围：一、图解法的优缺点及适用范围：一、图解法的优缺点及适用范围：一、图解法的优缺点及适用范围：直观、简单，但只能解决两个变量的线性规划问直观、简单，但只能解决两个变量的线性规划问题。题。二、图解法举例：二、图解法举例：二、图解法举例：二、图解法举例：以教材第以教材第以教材第以教材第1010页例题为例页例题为例页例题为例页例题为例：第27页，共65页，编辑于2022年，星期日二、图解法举例：二、图解法举例：w1画约束条件的边界线画约束条件的边界线w本例只有两个变量 和 ，因此，以 和 为坐标轴作直角坐标系，根据约束条件 ，和 ，划出对应的等式对应的直线。第28页，共65页，编辑于2022年，星期日二、图解法举例：二、图解法举例：2确定问题的可行域如图（划线阴影部分）确定问题的可行域如图（划线阴影部分）w w同时满足这些约束条件的点必落在围成的阴影面积内及同时满足这些约束条件的点必落在围成的阴影面积内及该多边型的边界上（该多边型是凸的，后面会证明，若该多边型的边界上（该多边型是凸的，后面会证明，若线性规划存在可行域，则该可行域必定是凸的）。线性规划存在可行域，则该可行域必定是凸的）。2x1+2x2=12 4x1=16 4x2=12 x1+2x2=8 4Q 3Q 2Q 1Q x2 x1 O 第29页，共65页，编辑于2022年，星期日二、图解法举例：二、图解法举例：3画目标函数的等值线画目标函数的等值线 目标函数目标函数 （z z为待定值），将其改写为为待定值），将其改写为 该式代表斜率为该式代表斜率为 ，参数为，参数为 z z 的一族平行的直线，该直的一族平行的直线，该直线为一族等值线，离远点越远的，线为一族等值线，离远点越远的，值越大。值越大。第30页，共65页，编辑于2022年，星期日二、图解法举例：二、图解法举例：4最优解的确定最优解的确定w w最优解：满足约束条件且使目标函数值达到最大。最优解：满足约束条件且使目标函数值达到最大。w w用图解法求线性规划的最优解，沿等值线的法线方向向用图解法求线性规划的最优解，沿等值线的法线方向向O O点点右上方移动等值线，和可行域相切的点代表的就是最优解对右上方移动等值线，和可行域相切的点代表的就是最优解对应的点。本例中，该点为应的点。本例中，该点为 点。点。w w本例中的最优解为唯一解。本例中的最优解为唯一解。第31页，共65页，编辑于2022年，星期日三、解题步骤：解题步骤：w1画约束条件的边界线；w2.确定可行域；w3.画目标函数的一组图线；w4.最优解确定。第32页，共65页，编辑于2022年，星期日四、图解法对解的讨论图解法对解的讨论唯一解、无穷多最优解、无界解（或无最优解）、无可行唯一解、无穷多最优解、无界解（或无最优解）、无可行解。解。1.1.唯一解：唯一解：唯一解：唯一解：等值线与可行域边界相切为一点，本例等值线与可行域边界相切为一点，本例2.2.无穷多最优解无穷多最优解无穷多最优解无穷多最优解：将本例的目标函数改为：将本例的目标函数改为 ，则目标函，则目标函数的等值线正好与约束条件数的等值线正好与约束条件 平行，即在整个线段平行，即在整个线段 上相切，此时的最优解对应上相切，此时的最优解对应 上所有的点。即该线性规划上所有的点。即该线性规划问题有无穷多最优解。问题有无穷多最优解。第33页，共65页，编辑于2022年，星期日四、图解法对解的讨论图解法对解的讨论3 3.无界解无界解无界解无界解：约束条件只保留（：约束条件只保留（1.7d1.7d）和（）和（1.7f1.7f），则因为变量取），则因为变量取值可以无限大，所以目标函数可以无限大，此种情况称为值可以无限大，所以目标函数可以无限大，此种情况称为无界解和无最优解（原因是建立实际问题的数学模型时遗无界解和无最优解（原因是建立实际问题的数学模型时遗漏了某些必要的资源约束）。漏了某些必要的资源约束）。第34页，共65页，编辑于2022年，星期日四、图解法对解的讨论图解法对解的讨论4 4.无可行解：无可行解：无可行解：无可行解：（线性规划问题无可行域）（线性规划问题无可行域）例：例：线性规划问题解的状况示意图：线性规划问题解的状况示意图：第35页，共65页，编辑于2022年，星期日练习：练习：w w案例：伟恩德玻璃制品公司产品，组合问题案例：伟恩德玻璃制品公司产品，组合问题w w背景资料：伟恩德公司生产高质量的玻璃制品，包括具背景资料：伟恩德公司生产高质量的玻璃制品，包括具有手艺和最精细工艺特性的窗和玻璃门。尽管这些产品有手艺和最精细工艺特性的窗和玻璃门。尽管这些产品昂贵，但它们是为最具辨别眼光的客户提供的行业中最昂贵，但它们是为最具辨别眼光的客户提供的行业中最高可得质量的产品。高可得质量的产品。w w公司有三个工厂：工厂公司有三个工厂：工厂1 1：生产铝框和硬制件：生产铝框和硬制件w w 工厂工厂2 2：生产木框：生产木框w w 工厂工厂3 3：生产玻璃和组装窗和门：生产玻璃和组装窗和门w w 由于某些产品销售量的下降，高层管理部门决定调整公司由于某些产品销售量的下降，高层管理部门决定调整公司的产品线。现在研发部门设计出了两种新产品：的产品线。现在研发部门设计出了两种新产品：8 8英尺的铝框英尺的铝框玻璃门；玻璃门；4 4英尺英尺66英尺的双把木框窗英尺的双把木框窗w w现在管理部门要考虑的问题：现在管理部门要考虑的问题：w w公司是否应该生产这两个新产品？公司是否应该生产这两个新产品？w w如果生产，两个新产品的产品生产组合如何？如果生产，两个新产品的产品生产组合如何？第36页，共65页，编辑于2022年，星期日练习：练习：门门门门 窗窗窗窗 约束（每周可得时约束（每周可得时约束（每周可得时约束（每周可得时间）间）间）间）工厂工厂工厂工厂1 1 1 1小时小时 0 0 4 4小时小时 工厂工厂工厂工厂2 2 0 0 2 2小时小时 1212小时小时 工厂工厂工厂工厂3 3 3 3小时小时 2 2小时小时 1818小时小时 利润利润利润利润 300300美元美元/每件每件 500500美元美元/每件每件 第37页，共65页，编辑于2022年，星期日练习：练习：w解：经分析，给出该问题的数学模型为：第38页，共65页，编辑于2022年，星期日练习：练习：用图解法进行求解：用图解法进行求解：划出约束条件的边值线，确定可行域（如下图）：划出约束条件的边值线，确定可行域（如下图）：第39页，共65页，编辑于2022年，星期日练习：练习：w w目目标标函函数数的的斜斜率率：，与与约约束束条条件件 对对应应的的斜斜率率不不同同（约约束束条条件件斜斜率率为为 ），根根据据图图示示的的约约束束条条件件的的可可行行域域，该该问问题题应应该该存存在在唯唯一一最最优优解解，画画出出目目标标函函数数等值线分析得，最优解为（等值线分析得，最优解为（2 2，6 6）。第40页，共65页，编辑于2022年，星期日图解法对单纯形法的启示：图解法对单纯形法的启示：(引出单引出单纯形法的解题思路纯形法的解题思路)w w求线性规划时，解的情况有：唯一最优解、无求线性规划时，解的情况有：唯一最优解、无求线性规划时，解的情况有：唯一最优解、无求线性规划时，解的情况有：唯一最优解、无穷最优解、无界解、无可行解。穷最优解、无界解、无可行解。穷最优解、无界解、无可行解。穷最优解、无界解、无可行解。w w若线性规划问题的最优解存在，则可行域一定若线性规划问题的最优解存在，则可行域一定若线性规划问题的最优解存在，则可行域一定若线性规划问题的最优解存在，则可行域一定是一个凸集。是一个凸集。是一个凸集。是一个凸集。w w若最优解存在，则最优解或最优解之一（无穷多时）若最优解存在，则最优解或最优解之一（无穷多时）若最优解存在，则最优解或最优解之一（无穷多时）若最优解存在，则最优解或最优解之一（无穷多时）一定能在可行域的某个顶点上找到。一定能在可行域的某个顶点上找到。一定能在可行域的某个顶点上找到。一定能在可行域的某个顶点上找到。w w解题思路：现找凸集任一顶点，计算在顶点处解题思路：现找凸集任一顶点，计算在顶点处解题思路：现找凸集任一顶点，计算在顶点处解题思路：现找凸集任一顶点，计算在顶点处的目标函数值。的目标函数值。的目标函数值。的目标函数值。第41页，共65页，编辑于2022年，星期日第三节第三节 单纯形法原理单纯形法原理w本节内容：一、线性规划问题的解（基本概念）一、线性规划问题的解（基本概念）二、凸集、顶点、相关定理二、凸集、顶点、相关定理 三、单纯形法迭代原理三、单纯形法迭代原理第42页，共65页，编辑于2022年，星期日一、线性规划问题的解（基本概念）一、线性规划问题的解（基本概念）w w可行域：可行域：可行域：可行域：满足约束条件的解叫可行解。所有可行解的集合，满足约束条件的解叫可行解。所有可行解的集合，构成线性规划问题的可行域。构成线性规划问题的可行域。w w最优解：最优解：最优解：最优解：使目标函数达到最大值的可行解称为最优解。使目标函数达到最大值的可行解称为最优解。(使目使目标函数得到极值的可行解，称为线性规划问题的最优解标函数得到极值的可行解，称为线性规划问题的最优解)w w基：基：基：基：设约束方程组的系数矩阵设约束方程组的系数矩阵A A为为 阶矩阵，设阶矩阵，设 ，其秩为，其秩为 ，是是 中的一个中的一个mmmm阶的满秩子矩阵，阶的满秩子矩阵，则称为线性规划问题的一个基。则称为线性规划问题的一个基。w w设设 w w则则 中的每一个列向量中的每一个列向量 称为基向量。称为基向量。w w基变量：基变量：基变量：基变量：与基向量对应的变量。与基向量对应的变量。w w非基变量：非基变量：非基变量：非基变量：线性规划中除基变量以外的变量线性规划中除基变量以外的变量。第43页，共65页，编辑于2022年，星期日一、线性规划问题的解（基本概念）一、线性规划问题的解（基本概念）基解：基解：令所有非基变量为0，解出的解。基可行解：基可行解：满足变量非负约束条件的基解称为基可行解。例：求出下列线性规划问题的基解和基可行解第44页，共65页，编辑于2022年，星期日二、凸集、顶点、相关定理二、凸集、顶点、相关定理w w凸集：凸集：凸集：凸集：对任何对任何 ，有，有 ，w w则则 称为凸集。称为凸集。w w凸集的例子：（此处可以判断出现）凸集的例子：（此处可以判断出现）凸集的例子：（此处可以判断出现）凸集的例子：（此处可以判断出现）w w非凸集的例子：非凸集的例子：非凸集的例子：非凸集的例子：w w 顶点：顶点：顶点：顶点：设设 为凸集，若为凸集，若 ，且对任何，且对任何 ，不存，不存在在 ，则称，则称 为为 的顶点。的顶点。w w 第45页，共65页，编辑于2022年，星期日二、凸集、顶点、相关定理二、凸集、顶点、相关定理w w定理定理定理定理1 1若线性规划问题存在可行解，则问题的可行域是凸集。w w定理定理定理定理2 2：线性规划问题的基可行解对应线性规划线性规划问题的基可行解对应线性规划问题可行域（凸集）的顶点。问题可行域（凸集）的顶点。w w定理定理定理定理3 3：若线性规划问题有最优解，则一定存在一个基可行解为最优解。第46页，共65页，编辑于2022年，星期日三、单纯形法迭代原理三、单纯形法迭代原理w w（根据定理（根据定理3 3，若线性规划问题存在最优解，一，若线性规划问题存在最优解，一定有一个基可行解是最优解）定有一个基可行解是最优解）w单纯形法的基本思路：单纯形法的基本思路：先找出一个基可行解，判断其是否为最优解，如为否，则转换到相邻的基可行解，并使目标函数值不断增大，一直找到最优解为止。第47页，共65页，编辑于2022年，星期日三、单纯形法迭代原理三、单纯形法迭代原理w w单纯形法的原理：单纯形法的原理：单纯形法的原理：单纯形法的原理：1.1.确定初始基可行解：确定初始基可行解：确定初始基可行解：确定初始基可行解：在约束条件的变量的系数矩阵找到一个单位矩阵，从而确定一在约束条件的变量的系数矩阵找到一个单位矩阵，从而确定一个基可行解。个基可行解。2.2.从一个基可行解转换为相邻的基可行解从一个基可行解转换为相邻的基可行解从一个基可行解转换为相邻的基可行解从一个基可行解转换为相邻的基可行解 3.3.最优性检验和解的判断最优性检验和解的判断最优性检验和解的判断最优性检验和解的判断w wA.A.最优解的判断标准最优解的判断标准最优解的判断标准最优解的判断标准 设设 为对应于基为对应于基B B的一个基可的一个基可 行解，行解，（，（），且对于一），且对于一 切切 ，有，有 ，则，则 为最优解，为最优解，为检验数。为检验数。第48页，共65页，编辑于2022年，星期日三、单纯形法迭代原理三、单纯形法迭代原理w wB.B.无穷多最优解判断标准无穷多最优解判断标准无穷多最优解判断标准无穷多最优解判断标准 设设 为对应于基为对应于基B B的一个基可行解，的一个基可行解，且对于一切且对于一切 ，有，有 又存在某个非基变量又存在某个非基变量的检验数的检验数 ，则线性规划问题有无穷多最优解。，则线性规划问题有无穷多最优解。w wC.C.无界解的判别标准无界解的判别标准无界解的判别标准无界解的判别标准 若若 ，且，且 （意味着（意味着 ），则对任意的），则对任意的 ，均有，均有 成立，因而成立，因而 取值无限制可取值无限制可 无限增大，因为，无限增大，因为，所以所以 也可也可 无限增大，这表明线性规划有无界解。无限增大，这表明线性规划有无界解。第49页，共65页，编辑于2022年，星期日第四节第四节 单纯形法的计算步骤单纯形法的计算步骤 一、单纯形表中的一些变量一、单纯形表中的一些变量w：各变量在目标函数中的系数值w：各基变量在目标函数中的系数值w：（）基变量w：非基变量w：检验数 第50页，共65页，编辑于2022年，星期日二、单纯形法的基本计算流程二、单纯形法的基本计算流程w w1.1.列单纯形表列单纯形表列单纯形表列单纯形表w w2.2.最优性检验最优性检验最优性检验最优性检验 最优，停止计算最优，停止计算 无最优解，停止计算 否则，确定新的基变量，修正单纯形表，再进行否则，确定新的基变量，修正单纯形表，再进行最优性检验，直至满足停止的条件。最优性检验，直至满足停止的条件。第51页，共65页，编辑于2022年，星期日三、单纯形法的具体步骤三、单纯形法的具体步骤1 1、把、把LPLP问题化为标准形问题化为标准形2 2、从系数阵中找出或构造一个、从系数阵中找出或构造一个m m阶排列矩阵作为初始可行基阶排列矩阵作为初始可行基，建立初始单纯形表。，建立初始单纯形表。3 3、若所有检验数、若所有检验数 ，就得到一个最优基本解，停止计算，就得到一个最优基本解，停止计算，否则转否则转4 4。4 4、在所有的、在所有的 中，只要有一个中，只要有一个 对应的系数列向量对应的系数列向量 （即一切的（即一切的 ），则该），则该LPLP问题为无界解，问题为无界解，停止计算，否则转停止计算，否则转5 5 第52页，共65页，编辑于2022年，星期日三、单纯形法的具体步骤三、单纯形法的具体步骤5 5、确定确定进基、出基进基、出基进基、出基进基、出基变量变量 进基变量的确定：进基变量的确定：进基变量的确定：进基变量的确定：在所有的在所有的 中找出一个最大的，中找出一个最大的，确定进基变量，确定进基变量 和和 主列主列 出基变量的确定：出基变量的确定：出基变量的确定：出基变量的确定：再按最小比值原则，再按最小比值原则，确定，确定 主元素主元素 和出基变量和出基变量 。第53页，共65页，编辑于2022年，星期日三、单纯形法的具体步骤三、单纯形法的具体步骤6 6、以以以以 为为为为主主主主元元元元素素素素，对对对对当当当当前前前前表表表表格格格格进进进进行行行行一一一一次次次次换换换换基基基基计计计计算算算算，得得得得到到到到一一一一个个个个新新新新单单单单纯纯纯纯形形形形表表表表（新新新新单单单单纯纯纯纯形形形形表表表表的的的的变变变变化化化化原原原原则则则则为为为为将将将将新新新新的的的的进进进进基基基基变变变变量量量量的的的的系系系系数数数数化化化化成成成成单单单单位位位位向向向向量量量量，检检检检验验验验数数数数化化化化为为为为零零零零，所用的方法为高斯消元法），返回所用的方法为高斯消元法），返回所用的方法为高斯消元法），返回所用的方法为高斯消元法），返回3 3。第54页，共65页，编辑于2022年，星期日三、单纯形法的具体步骤三、单纯形法的具体步骤 例：用单纯形求解线性规划问题例：用单纯形求解线性规划问题例：用单纯形求解线性规划问题例：用单纯形求解线性规划问题 maxZ=2xmaxZ=2x1 1+3x+3x2 2第55页，共65页，编辑于2022年，星期日四、最优解的讨论四、最优解的讨论 1.1.当所有的检验数小于等于零时，表明现有顶点（基当所有的检验数小于等于零时，表明现有顶点（基当所有的检验数小于等于零时，表明现有顶点（基当所有的检验数小于等于零时，表明现有顶点（基可行解）的目标函数值比起相邻各顶点的目标函数值可行解）的目标函数值比起相邻各顶点的目标函数值可行解）的目标函数值比起相邻各顶点的目标函数值可行解）的目标函数值比起相邻各顶点的目标函数值都大，现有顶点对应的基可行解为最优解。都大，现有顶点对应的基可行解为最优解。都大，现有顶点对应的基可行解为最优解。都大，现有顶点对应的基可行解为最优解。2.2.当所有的检验数小于等于零，对某一非基变量有检验数当所有的检验数小于等于零，对某一非基变量有检验数当所有的检验数小于等于零，对某一非基变量有检验数当所有的检验数小于等于零，对某一非基变量有检验数等于零，有无穷多最优解。等于零，有无穷多最优解。等于零，有无穷多最优解。等于零，有无穷多最优解。第56页，共65页，编辑于2022年，星期日第五节第五节 单纯形法的进一步讨论单纯形法的进一步讨论 一、人工变量法（大一、人工变量法（大MM法）法）法）法）w w适用范围：适用范围：适用范围：适用范围：当约束条件为等式或当约束条件为等式或 时，很难找到单位矩时，很难找到单位矩阵作为基，就需要添加人工变量。阵作为基，就需要添加人工变量。w w大大大大M法的基本思想：法的基本思想：法的基本思想：法的基本思想：考察化为标准型的线性规划模考察化为标准型的线性规划模型，若约束条件对应的系数矩阵中无单位矩阵，则添型，若约束条件对应的系数矩阵中无单位矩阵，则添加人工变量，构成单位矩阵，引入的人工变量的价值加人工变量，构成单位矩阵，引入的人工变量的价值系数为一个大的负数系数为一个大的负数-M-M，使得目标函数达到最大时，使得目标函数达到最大时，人工变量取值应该为人工变量取值应该为0 0，从而保证引入人工变量到约，从而保证引入人工变量到约束条件的等式中，等式仍然成立，最终的最优解中束条件的等式中，等式仍然成立，最终的最优解中非非0 0项不包含人工变量项不包含人工变量。第57页，共65页，编辑于2022年，星期日一、人工变量法（大一、人工变量法（大M法）法）例例6 用单纯形法求解线性规划问题：用单纯形法求解线性规划问题：第58页，共65页，编辑于2022年，星期日一、人工变量法（大一、人工变量法（大M法）法）例例例例6 6 解：解：解：解：将此问题化为标准形式，即在约束条件中添加松弛变将此问题化为标准形式，即在约束条件中添加松弛变量和剩余变量得：量和剩余变量得：化为标准形式的线性规划模型中，其约束条件的系数化为标准形式的线性规划模型中，其约束条件的系数矩阵为：矩阵为：找不到单位矩阵。找不到单位矩阵。第59页，共65页，编辑于2022年，星期日一、人工变量法（大一、人工变量法（大M法）法）例例例例6 6 解：因此，添加两列单位向量解：因此，添加两列单位向量解：因此，添加两列单位向量