单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精选ppt课件,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,精选ppt课件,*,第五章 单纯形法,1,精选ppt课件,第五章 单纯形法1精选ppt课件,5.1,线性规划求解的相关概念,一、相关定理,定理1 线性规划问题的可行解集S是凸集。,定理2 线性规划问题的基本可行解X对应于可行域S的顶点。也就是说，可行域的顶点就是线性规划问题的基本可行解。,定理3 若线性规划问题有最优解，它一定在其可行域的顶点上达到。,2,精选ppt课件,5.1 线性规划求解的相关概念 一、相关定理2精选ppt课,二、基本概念,单纯形法的基本思路：单纯形法也可以说是一种找凸集极点的计算方法，但它并不是要求去计算所有的极点，而是从凸集的一个初始解出发，沿凸集的边缘逐个验算所遇到的极点，直到找到使目标函数最优的极点为止。,初始可行解:第一个找到的可行域的顶点。,三、单纯形法试算程序框图,（,见图51,）,3,精选ppt课件,二、基本概念单纯形法的基本思路：单纯形法也可以说是一种找凸集,开 始,转变为标准型增加额外变量(松弛、剩余、人工变量),建立初始,单纯形表,最优,停,找出“换入”“换出”变量,修正单纯形表,是,否,图51,4,精选ppt课件,开 始转变为标准型增加额外变量(松弛、剩余、人工变量)建,5.2,线性规划模型的变换,一、线性规划模型标准型的特点,目标函数是求极大值或极小值；,所有的变量都是非负的；,除变量的非负约束外，其余的约束条件都是等式约束；,每个约束方程右边的常数都是非负的。,除变量的非负约束,等式约束,思考:若右边的常数不是非负怎么办?,5,精选ppt课件,5.2 线性规划模型的变换 一、线性规划模型标准型的特点,二、线性规划模型的变换,根据线性规划模型约束条件的不同，将其划分为三种类型：,1,.“”类型的约束条件的变换,变换的方法：在不等式中增加一个额外的变量，称为松弛变量，以S表示之。松弛变量在约束方程中的系数为1，在目标函数中的系数为0，所以它的引入并不影响目标函数值。,松弛变量即表示作为决策限制条件的某种有限资源未被利用的部分。,6,精选ppt课件,二、线性规划模型的变换 根据线性规划模型约束条件的不同,2,“”类型的约束条件的变换,变换的方法：引入剩入变量及人工变量，以S和A表示。,剩余变量在约束方程中的系数为-1，在目标函数中的系数为0，人工变量在约束方程中的系数为1，在目标函数中的系数为是一任意大正数，以M表示之。在求最大值的目标函数中，M取负号；在求最小值的目标函数中，M取正号。,剩余变量一般用来表示决策要求的某一最低标准超过要求的量，人工变量仅为了单纯形法在运算上方便，无其它特殊意义。,7,精选ppt课件,2“”类型的约束条件的变换变换的方法：引入剩入变量及人工,3,“=”类型的约束条件,变换的方法：引入人工变量，人工变量在约束方程中的系数为1，在目标函数中的系数为任意大的正数M。在求最大值的目标函数中，M取负号；在求最小值的目标函数中，M取正号。,8,精选ppt课件,3“=”类型的约束条件 变换的方法：引入人工变量，人工,三、模型变换方法归纳,约束条件类型,变 换 方 法,对于约束条件,对于目标函数,+S,+0S,-S+A,求max时，+0S-MA,求min时，+0S+MA,=,+A,求max时，-MA,求min时，+MA,表中，S为松弛变量或剩余变量，A为人工变量，M为一任意大的正数。,9,精选ppt课件,三、模型变换方法归纳 约束条件类型变 换 方 法对于约束条件,单纯形法,1.单纯形法的基本思想,从一个初始的基本可行解出发，沿着不断改进目标函数值的方向进行迭代，经过若干基本可行解，直到得出最优解。,计算顺利进行的保证条件：,最优性条件：它保证每次变动不会得到更差的解,可行性条件：它保证每次变动仍是基本可行解,可行域是不变的,10,精选ppt课件,单纯形法 1.单纯形法的基本思想 10精选ppt课件,2.单纯形法的计算步骤,将线性规划问题转化为标准型,编制初始单纯行表,判别基本可行解是否为最优,找出“换入”或“换出”变量，以便进行换基,先找出主元行与主元列：对于求极大值问题，取,Cj-Zj,为正数且最大者所在的列为主元列，取,b,i,/a,ij,为正数且最大者所在的行为主元行，主元行与主元列之交点元素称为主元素，在右上方记“*”主元素正上方对应的变量为“换入”变量，主元素左边对应的基变量为“换出”变量。,修正单纯形表,运算规则：新行主元行元素=旧行元素/主元素,其他新行元素=旧行元素-交点元素*新主元行相应元素【交点元素指该行与主元列之交点元素】,对新基本可行解进行判别，是否达到最优，是则停；否则继续上述程序,对于求最大值问题，全部判别数为零与负数时，即C,j,-Z,j,0，,得最优解,11,精选ppt课件,2.单纯形法的计算步骤将线性规划问题转化为标准型对于求最大值,线性规划模型的一般形式：,求一组变量,x,1,，x,2,，x,n,的值,使目标函数：,Z=c,1,x,1,+c,2,x,2,+c,n,x,n,的值最大或最小，并满足的约束条件：,a,11,x,1,+a,12,x,2,+a,1n,x,n,(,，=)b,1,a,21,x,1,+a,22,x,2,+a,2n,x,n,(,，=)b,2,a,m1,x,1,+a,m2,x,2,+a,mn,x,n,(,，=)b,m,x,1,，x,2,x,n,0,12,精选ppt课件,线性规划模型的一般形式：求一组变量x1，x2，xn的值,线性规划一般形的标准型：,13,精选ppt课件,线性规划一般形的标准型：13精选ppt课件,一般型的初始单纯形表：,C,j,C,1,C,2,C,n,0 0 0,x,1,x,2,x,n,S,n+1,S,n+2,S,n+m,解b,0 S,n+1,0 S,n+2,0 S,n+m,a,11,a,12,a,1n,1 0 0,a,21,a,22,a,2n,0 1,0,a,m1,a,m2,a,mn,0 0,1,b,1,b,2,b,n,机会成本行Z,j,判别数行C,j,-Z,j,目标函数,14,精选ppt课件,一般型的初始单纯形表：CjC1 C2,例1,求,max Z=7x,1,+10 x,2,满足,7x,1,+7x,2,49,10 x,1,+5x,2,50,x,1,，x,2,0,用单纯形法求解。,15,精选ppt课件,例1求max Z=7x1+10 x215精选ppt课件,例2,第2章例1中我们得线性规划模型为：,目标函数：max Z=50 x,1,+,100 x,2,满足,x,1,+,x,2,300,2x,1,+,x,2,400,x,2,250,x,1,，x,2,0,用单纯形法求解。,16,精选ppt课件,例2 第2章例1中我们得线性规划模型为：16精选ppt课件,本题模型的标准型为：,求max Z=50 x,1,+100 x,2,+0S,3,+0S,4,+0S,5,满足 x,1,+x,2,+S,3,=300,2x,1,+x,2,+S,4,=400,x,2,+S,5,=250,x,1,，,x,2,，,S,3,，,S,4,，,S,5,0,17,精选ppt课件,本题模型的标准型为：求max Z=50 x1+100 x2+0,C,j,50100000,x,1,x,2,S,3,S,4,S,5,解,0,S,3,0,S,4,0,S,5,1 1 1 0 0,2 1 0 1 0,0,1,*,0,0,1,300,400,250,Z,j,C,j,-Z,j,0 0 0 0 0,50 100 0 0 0,0,0 S,3,0 S,4,100,x,2,1,*,0 1 0 -1,2 0 0 1 -1,0 1 0 0 1,50,150,250,Z,j,C,j,-Z,j,0 100 0 0 100,50 0 0 0 -100,25000,18,精选ppt课件,Cj 501000000 S31,C,j,50100 0 0 0,x,1,x,2,S,3,S,4,S,5,解,50 x,1,0 S,4,100,x,2,1 0 1 0 -1,0 0 -2 1 1,0 1 0 0 1,50,50,250,Z,j,C,j,-Z,j,50 100 50 0 50,0 0 -50 0 -50,27500,此时，C,j,-Z,j,0 则此时为最优解。,即：x,1,=50,x,2,=250,S,3,=0S,4,=50,S,5,=0,Z=27500,19,精选ppt课件,Cj 50100 0 0 050 x,3.人工变量法,用单纯形法求最小值问题，与求最大值问题类似，其区别在于判别数为零或者正值，即,Cj-Zj0时得到最优解，在决定“换入”及“换出”变量时，取Cj-Zj为负且绝对值最大者为主元列，其余步骤同求最大值问题。,这种求线性规划的方法，称为“人工变量法”或称为“大M”法，这就是当一个 线性规划问题在增加了松弛变量后 仍不能提供基本可行解时，需要采用“人工变量”来获得一个初始的基本可行解。,20,精选ppt课件,3.人工变量法用单纯形法求最小值问题，与求最大值问题类似，其,例3,求线性规划：min Z=2x,1,+3x,2,满足,2x,1,+x,2,4,-x,1,+x,2,2,x,1,x,2,0,21,精选ppt课件,例3求线性规划：min Z=2x1+3x221精选ppt,单纯形法的步骤归纳如下：,根据线性规划模型的特点，将问题改写成标准型,以各变量为列，各约束方程的系数为行，全部决策变量为0，松弛变量或人工变量为基变量，建立初始单纯形表,计算机会成本行,Zj及判别数行Cj-Zj，检验问题是已达最优，是则停，否则进行下一步,找出主元素，确定“换出”及“换入”变量,进行换基及迭代运算，修正单纯形表,重返第3步,22,精选ppt课件,单纯形法的步骤归纳如下：根据线性规划模型的特点，将问题改写成,单纯形法的经济信息,例：设某制药厂生产A和B两种药品，在已有条件下。药品A的生产能力为5吨/月,药品B生产能力为4吨/月，设每吨药品A耗电0.5万度，每吨药品B耗电1万度，电力部门供电能力为每月5万度，若药品A价格为每吨4千元，药品B的价格为每吨1千元，问每月应如何分配电力资源，使产值最大？,本题解题过程,23,精选ppt课件,单纯形法的经济信息例：设某制药厂生产A和B两种药品，在已有条,由题：,Cj列表示每一个基变量对目标函数的贡献,初始表最右端bi列，表示的是各松弛变量的最大值，即相应资源的约束条件的上限,初始表提供的基本可行解为,x,1,=x,2,=0 不生产A、B,S,3,=5 闲置的药品A的生产能力,S,4,=4 闲置的药品B的生产能力,S,5,=5 闲置的电力资源,24,精选ppt课件,由题：Cj列表示每一个基变量对目标函数的贡献24精选ppt课,例2：,某医院营养室专门为病员制作甲、乙、丙三种营养食品，其中每种食品都要包含两种主要营养素A、B，具体数据如下表，而且A营养素的供应量为12千克，B营养素的供应量为20千克，试问该营养室每天制作甲、乙、丙三种食品各多少份才能使其利润最高？,甲,乙,丙,A,1,1,1,B,1,3,2,利润（元/份）,5,8,6,25,精选ppt课件,例2：某医院营养室专门为病员制作甲、乙、丙三种营养,对偶规划,线性规划是研究资源最优利用的途径，所谓最优利用包含两方面的含意：,1.在一定的资源条件下完成最多的任务或做出最大的贡献,2.完成给定的任务，使用的资源最小,对于一个求极大值问题必存在一个求极小值的问题与其对应，而且两者包含相同的数据，称前一个问题为原问题，则后一个问题便是原问题的对偶问题。反之，若称后一问题为原问题，则前一个问题是对偶问题。,26,精选ppt课件,对偶规划线性规划是研究资源最优利用的途径，所谓最优利用包含两,对偶规划的定义,例2：某人某月营养成分的最低需求量，不同食品的营养成分含量及其单件如表所示，问某人每月怎样购买这些食