运筹学第一章ppt课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,OR1,1,第一章 线性规划与单纯形法,重点与难点：,1,、线性规划的概念和模型，线性规划问题的标准型，线性规划问题的标准化；,2,、线性规划问题解的概念，图解法,(,解的几何表示,),，基本可行解的几何意义，线性规划求解思路,(,单纯形法思想,),；,3,、单纯形法的一般描述，表格单纯形法，一般线性规划问题的处理，单纯形迭代过程中的注意事项；,4,、线性规划建模，决策变量，约束不等式、等式，目标函数，变量的非负限制。,OR1,2,第一章 线性规划与单纯形法,1.1 LP(linear programming),的基本概念,LP,是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。,LP,有一组有待决策的变量，（决策变量）,一个线性的目标函数，,一组线性的约束条件,。,OR1,3,1.1.1,LP,的数学模型 例题,1,：生产计划问题,某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：问题：如何安排生产计划，使得获利最多？,产品,A,产品,B,资源限量,劳动力,设 备,原材料,9,4,3,4,5,10,360,200,300,利润,元,/kg,70,120,OR1,4,例题,1,建模,步骤：,1,、确定决策变量：设生产,A,产品,x,1,kg,B,产品,x,2,kg,2,、确定目标函数：,maxZ=70X,1,+120X,2,3,、确定约束条件：人力约束,9X,1,+4X,2,360,设备约束,4X,1,+5X,2,200,原材料约束,3X,1,+10X,2,300,非负性约束,X,1,0,X,2,0,综上所述，该问题的数学模型表示为：,OR1,5,例题,2,：人员安排问题,医院护士,24,小时值班，每次值班,8,小时。不同时段需要的护士人数不等。据统计：,序号,时段,最少人数,安排人数,1,0610,60,X,1,2,1014,70,X,2,3,1418,60,X,3,4,1822,50,X,4,5,2202,20,X,5,6,0206,30,x,6,请问该医院至少需要多少名护士？,OR1,6,例题,2,建模,目标函数：,min Z=x,1,+x,2,+x,3,+x,4,+x,5,+x,6,约束条件：,x,1,+x,2,70,x,2,+x,3,60,x,3,+x,4,50,x,4,+x,5,20,x,5,+x,6,30,非负性约束：,x,j,0,j,=1,2,6,OR1,7,例题,3,：,运输问题,三个加工棉花的加工厂，并且有三个仓库供应棉花，各供应点到各工厂的单位运费以及各点的供应量与需求量分别如下表所示：,问如何运输才能使总的运费最小？,仓库 工厂,B,1,B,2,B,3,库存,A,1,2,1,3,50,A,2,2,2,4,30,A,3,3,4,2,10,需求,40,15,35,OR1,8,例题,3,建模,设,X,ij,为第,i,个仓库运到底,j,座工厂的运输量。,目标函数：总运费最省：,minZ=2x,11,+x,12,+3x,13,+2x,21,+2x,22,+4x,23,+3x,31,+4x,32,+2x,33,约束条件：,供给要求：,x,11,+x,12,+x,13,50,需求要求：,x,11,+x,21,+x,31,=40,x,21,+x,22,+x,23,30,x,12,+x,22,+x,32,=15,x,31,+x,32,+x,33,10,x,13,+x,23,+x,33,=35,非负要求：,X,ij,0,OR1,9,例题,4,：连续投资问题（书,P42,页）,某投资者有资金,10,万元，考虑在今后,5,年内给下列,4,个项目进行投资，已知：,项目,A,：从第一年到第四年每年年初需要投资，并于次年末回收本利,115,。,项目,B,：第三年初需投资，到第五年末能回收本利,125,。但规定投资额不超过,4,万元。,项目,C,：第二年初需要投资，到第五年末能回收本利,140,，但规定最大投资额不超过,3,万元。,项目,D,：,5,年内每年初可购买公债，于当年末归还，并加利息,6,。,问该投资者应如何安排他的资金，确定给这些项目每年的投资额，使到第五年末能拥有的资金本利总额为最大,？,OR1,10,建模,解：记,x,iA,x,iB,x,iC,x,iD,(i=1,2,3,4,5),分别表示第,i,年年初给项目,A,B,C,D,的投资额，它们都是决策变量，为了便于书写数学模型，我们列表如下：,OR1,11,例题,5,：合理下料问题,将长,8m,的圆钢，截取成长,2.5m,的毛坯,100,根、长,1.3m,的毛坯,200,根，问应该怎样选择下料方式，才能既满足需要，又使总的用料最少,?,各种搭配方案如下：,长度根数方案,甲 乙 丙 丁,需要根数,2.5,米,3 2 1 0,100,1.3,米,0 2 4 6,200,料头,0.5 0.4 0.3 0.2,OR1,12,例题,5,建模,设,X,j,表示采用第,j,种方案下料的根数。,目标函数：,minZ=x,1,+x,2,+x,3,+x,4,约束条件：,3x,1,+2x,2,+x,3,100,2x,2,+4x,3,+6x,4,200,x,j,0,且为整数,(j=1,2,3,4),OR1,13,课堂练习：营养配餐问题,养海狸鼠 饲料中营养要求：,V,A,每天至少,700,克，,V,B,每天至少,30,克，,V,C,每天刚好,200,克。现有五种饲料，搭配使用，饲料成分如下表,:,OR1,14,建 模,设抓取饲料,I,x,1,kg;,饲料,II,x,2,kg;,饲料,III,x,3,kg,目标函数：最省钱,m,inZ=2x,1,+7x,2,+4x,3,+9x,4,+5x,5,约束条件：,3x,2,+2x,2,+x,3,+6x,4,+18x,5,700,营养要求：,x,1,+0.5x,2,+0.2x,3,+2x,4,+0.5x,5,30,0.5x,1,+x,2,+0.2x,3,+2x,4,+0.8x,5,=200,用量要求：,x,1,50,x,2,60,x,3,50,x,4,70,x,5,40,非负性要求：,x,1,0,x,2,0,x,3,0,x,4,0,x,5,0,OR1,15,总 结,从以上,5,个例子可以看出，它们都属于优化问题，它们的共同特征：,1,、每个问题都用一组决策变量表示某一方案；这组决策变量的值就代表一个具体方案，一般这些变量取值是非负的。,2,、存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。,3,、都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。,满足以上三个条件的数学模型称为线性规划的数学模型。,OR1,16,线性规划模型的一般模式,目标函数：,max(min)Z=c,1,x,1,+c,2,x,2,+c,3,x,3,+c,n,x,n,约束条件：,a,11,x,1,+a,12,x,2,+a,13,x,3,+a,1n,x,n,(=)b,1,a,21,x,1,+a,22,x,2,+a,23,x,3,+a,2n,x,n,(=)b,2,a,m1,x,1,+a,m2,x,2,+a,m3,x,3,+a,mn,x,n,(=)b,m,非负性约束：,x,1,0,x,2,0,x,n,0,.,OR1,17,线性规划的标准型,代数式,maxZ=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,j,0,j,=1,2,n,OR1,18,线性规划的标准型,和式：,maxZ=,c,j,x,j,a,ij,x,j,=b,i,i=1,2,m,x,j,0,j,=1,2,n,j=1,n,n,j=1,OR1,19,线性规划的标准型,向量式：,maxZ=CX,p,j,x,j,=b,i,i,=,1,2,m,x,j,0,j,=,1,2,n,C=(,c,1,c,2,c,3,c,n,),X=(,X,1,X,2,X,3,X,n,),T,n,j=1,OR1,20,线性规划的标准型,矩阵式：,maxZ=CX AX=b X,0,其中：,b=(b,1,b,2,b,m,),T,a,11,a,12,.,a,1n,A=,a,21,a,22,a,2n,a,m1,a,m2,a,mn,OR1,21,标准型的特征,目标函数极大化（也有的版本选择极小化）,约束条件为等式,决策变量非负,OR1,22,非标准型转化为标准型,目标函数极小化转为极大化：,minZ=,max(,Z),，一个数的极小化等价于其相反数的极大化。,不等式约束的转化：,a,ij,x,j,bi,加入,松弛,变量,a,ij,x,j,bi,减去,剩余,变量,非正变量：即,x,k,0,则令,x,k,=,x,k,自由变量：即,x,k,无约束，令,x,k=,x,k,x”,k,OR1,23,非标准型转化举例,minZ=,x,1,+2,x,2,-3,x,3,maxZ,=x,1,2,x,2,+,3,(,x,3,x”,3,),x,1,+,x,2,+,x,3,9,x,1,+,x,2,+,x,3,x”,3,+,x,4=,9,-,x,1,-2,x,2,+,x,3,2,x,1,2,x,2,+,x,3,x”,3,-,x,5=,2,3,x,1,+,x,2,-3,x,3,=5,3,x,1,+,x,2,3(,x,3,x”,3,),=5,x,1,0,x,2,0,x,3,无约束,x,1,0,x,2,0,x,3,0,x”,3,0,x,4,0,x,5,0,OR1,24,课堂练习：将下列非标准型化为标准型,1,、,minZ=x,1,-2x,2,+3x,3,2,，,maxZ=x,1,+x,2,s.t.x,1,+x,2,+x,3,7 s.t.x,1,-x,2,0,x,1,-x,2,+x,3,2 3x,1,-x,2,-3,-3x,1,+x,2,+2x,3,=-5 x,1,x,2,0,x,1,x,2,0,x,3,无约束。,OR1,25,1.1.2,线性规划问题的图解法,一、图解法的步骤,1,、在平面上建立直角坐标系；,2,、图示约束条件，找出可行域；,3,、图示目标函数，即为一直线；,4,、将目标函数直线沿其法线方向其最优化方向平移，直至与可行域第一次相切为止，这个切点就是最优点。,二、几种可能结局：,1,、有唯一最优解，,2,、有无穷多个最优解，,3,、无界解，,4,、无解。,OR1,26,线性规划图解法例题,（唯一最优解）,maxZ=70X,1,+120X,2,s.t.9X,1,+4X,2,360,4X,1,+5X,2,200,3X,1,+10X,2,300,X,1,0,X,2,0,OR1,27,线性规划图解法例题,（无穷多最优解）,OR1,28,线性规划图解法例题,（无界解）,OR1,29,线性规划图解法例题,（无解）,OR1,30,利用图解法的常识,1,、若存在唯一最优解，则此最优解在可行域的顶点上取得。,2,、若存在无穷多最优解，则最优解在可行域的边界上取得。,3,、若可行域为空集，则没有可行解，也就没有最优解。,4,、若可行域无界，目标函数取值可以增大到无穷大，称这种情况为无界解或无最优解。,5,、若有可行解，则可能有最优解，也可能无最优解（最优解无界）。,OR1,31,1.1.3,解的概念,概念：,1,、可行解：满足所有约束条件的解。,2,、可行域：即可行解的集合。所有约束条件的交集，也就是各半平面的公共部分。满足所有约束条件的解的集合，称为可行域。,3,、凸集：集合内任意两点的连线上的点均属于这个集合。如：实心球、三角形。线性规划的可行域是凸集。,OR1,32,基的概念,基,：如前所述,LP,标准型,和式：,maxZ=,c,j,x,j,a,ij,x,j,=b,i,x,j,0,j,=,1,2,n,矩阵式：,maxZ=CX AX=b X,0,约束方程的系数矩阵,A,的,秩,为,m,，且,m,0,=,b,L,/,a,Lk,确定,X,L,为出基变量。,4,、以,a,Lk,为枢轴元素进行迭代，回到第二步。,OR1,46,解的判别定理,(P,24,),1,、最优解的判别定理：若,X,(0),为对应于基,B,的一个基可行解，且对于一切非基变量，有 ，则,X,*,为最优解。称 为检验数。,2,、无穷多最优解的判别定理：若,X,(0),为对应于基,B,的一个基可行解，且对于一切非基变量，有 ，又存在某个非基变量的检验数为,0,，则称该,LP,问题有无穷多最优解。,OR1,47,解的判别定理,3,、,无界解的判别：若,X,(0),为对应于基,B,的一个基可行解，有某个正检验数的非基变量对应的列向量其分量均为非正，则该问题无界,。,OR1,48,1.3,单纯形法的进一步探讨,2.3.1,极小化,LP,的解法。,2.3.2,人工变量法之一：大,M,法。,2.3.3,人工变量法之二：两阶段法。,OR1,49,1.3.1,极小化,LP,问题的解法,方法一：将最小化问题化为最大化问题，再对该最大化问题进行求解。,方法二：最小化问题直接求解：检验数的判别由所有,j(c,j,-z,j,),0,即为最优，变为所有,j,0,则为最优。,(,选择最小的负的,j,所对应的变量为进基变量。其余同最大化求解方法。,),OR1,50,极小化问题的直接解法,例：求解线性规划问题：,OR1,51,解：该规划的基变量为,x,1,x,3,x,6,。直接按最小问题单纯形法的求解过程如下,：,c,j,1,-1,1,0,-3,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,x,6,1,0,0,2,1,2,0,1,0,-2,-1,1,0,2,3,0,0,1,5,6,8,x,1,x,3,x,6,1,1,0,z,11,1,3,1,-3,2,0,0,-4,0,3,-5,0,3,8/3,x,1,x,3,x,5,1,1,-3,1,0,0,2,-1/3,2/3,0,1,0,-2,-,5/3,1/3,0,0,1,0,-2/3,1/3,5,2/3,8/3,5/2,0,0,-2/3,0,14/3,0,5/3,x,2,x,3,x,5,1/6,-1/3,1,0,0,0,1,0,-1,-2,1,0,0,1,0,-2/3,1/3,5/2,3/2,1,0,0,4,0,5/3,4,-1,1,-3,OR1,52,1.3.2,人工变量法之一：大,M,法,首先看下面例题：,OR1,53,大,M,法,对于这种无初始可行基的问题可以大,M,法求解。方法：化为标准型的同时，将,以及,的约束条件中，加入人工变量（虚拟变量），将目标函数中，虚拟变量的系数定为,M,。,注：当目标函数为最大化时，虚拟变量的系数为,M,当目标函数为最小化时，虚拟变量的系数为,+M,。,(,目的是迫使人工变量为,0,）,该问题的解法同,LP,问题的一般解法。例同上。解法见书,P33,。,OR1,54,解法,解,:,在上述问题的约束条件中加入松弛变量，剩余变量，人工变量，得到：,OR1,55,用单纯形表计算：,c,j,-3,1,1,0,0,M,M,x,1,x,2,x,3,x,4,x,5,x,6,x,7,c,B,X,B,b,1,-4,-2,-2,1,0,1,2,1,1,0,0,0,-1,0,0,1,0,0,0,1,x,4,x,6,x,7,0,M,M,11,3,1,-3+6M,1-M,1-3M,0,M,0,0,11,3/2,1,x,4,x,6,x,3,0,M,1,3,0,-2,-2,1,0,0,0,1,1,0,0,0,-1,0,0,1,0,-1,-2,1,10,1,1,-1,1-M,0,0,M,0,3M-1,1,x,1,x,2,x,3,-3,1,1,1,0,0,0,1,0,0,0,1,1/3,0,2/3,-2/3,-1,-4/3,2/3,1,4/3,-5/3,-2,-7/3,4,1,9,2,0,0,0,1/3,1/3,M-1/3,M-2/3,OR1,56,人工变量法,:,两阶段法,大,M,法如果在计算机上运作，,M,就只能用很大的数来代替，这样可能会出现错误。故介绍两阶段法。,方法：第一阶段：不考虑原问题是否存在基可行解；原线性规划问题加入人工变量，并构造,仅含人工变量的要求最小化的目标函数。约束条件不变。,（,注：不管原问题是求最大化还是求最小化，第一阶段的目标函数都为人工变量之和的最小化,。）,OR1,57,例题,1,OR1,58,例题,2,OR1,59,第二阶段,用单纯形法求解上述模型，若得到 ，说明所有的人工变量都为,0,。至此，可以去掉人工变量，进入第二阶段；若得到 ，说明仍有人工变量没有降至,0,，表示原问题无可行解，应停止计算。,第二阶段：将第一阶段计算得到的最终表，除出人工变量。将目标函数行的系数，换原问题的目标函数系数，作为第二阶段计算的初始解。,OR1,60,解法举例：例,2,解：用两阶段法求解如下：,第一阶段，用单纯形法求解下列线性规划问题：,OR1,61,计算过程如下：,c,j,0,0,0,-1,-1,x,1,x,2,x,3,x,4,x,5,3,1,2,-2,-3,1,1,0,0,1,x,4,x,5,6,4,-1,-1,z,j,-4,0,-10,2,-1,-1,4,0,-2,0,0,2,4,x,1,x,5,1,0,2/3,-8/3,-1,2,1/3,-1/3,0,1,2,2,0,-1,-2,0,-8/3,2,-4/3,0,1,x,1,x,3,0,0,1,0,-2/3,-3/4,0,1,1/6,-1/6,1/2,3,1,0,0,0,0,-1,-1,c,B,X,B,b,OR1,62,由上表可知，辅助问题的最优解为：,X,*,=(3,0,1,0,0),T,=0,故可得原问题的一个初始基可行解：,X,*,=(3,0,1),T,阶段,2,：求解原问题：将目标函数换回，并且删去人工变量，得到第二阶段的问题。由表上作业法求解,。,OR1,63,c,j,3,-1,-2,c,B,X,B,b,x,1,x,2,x,3,x,1,x,3,3,1,1,0,-2/3,-4/3,0,1,3,2,7,0,-5/3,0,