[理学]《运筹学》ppt课件第一章

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,绪论,Operations 汉语翻译：,作业运营,工作,操作,Operations Research,(简写：OR)：,日本运用学,港台作业研究,中国大陆运筹学（既有运用，也有策划之意）,Operational Research原来名称，意为军事行动研究历史渊源,1,绪论1,绪论,早期运筹思想：田忌赛马,丁渭修宫,沈括运粮,Erlang 1917 排队论,Harris 1920 存储论,康脱洛维奇 1939 LP,2,绪论2,绪论,军事运筹学阶段：,兰德公司（RAND）,德军空袭 防空系统 Blackett,运输船编队,空袭逃避,深水炸弹,轰炸机编队,3,绪论3,绪论,运筹学在中国：50年代中期,华罗庚,:,推广 优选法、统筹法,中国邮递员问题、运输问题,4,绪论4,运筹学的应用,生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”),库存管理(合理物资库存量，停车场大小，设备容量),运输问题,财政、会计(预算，贷款，成本分析，投资，证券管理),人事(人员分配，人才评价，工资和奖金的确定),设备管理(维修计划，设备更新),城市管理(救火车，警车等的分布点的设置),市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划),5,运筹学的应用生产计划制定(合理下料，配料，“生产计划、库存、,运筹学的学科体系,规划论：线性规划、非线性规划|、整数规划、目标规划、动态规划,图论与网络,存储论,排队论,决策论,对策论,计算机仿真,6,运筹学的学科体系规划论：线性规划、非线性规划|、整数规划、目,Yinyu Ye,Professor of Management Science and Engineering,and, by courtesy, Electrical Engineering,Director, Industrial Affiliates Program, MS&E,Department of Management Science and Engineering,Huang Engineering Center 308,475 Via Ortega,School of Engineering,Stanford University, CA 94305-4121,Stanford,7,Yinyu Ye Stanford7,姓名: 袁亚湘,性别: 男,籍贯: 湖南省资兴市,出生年月: 1960年1月,职称: 研究员,专业: 计算数学、应用数学、运筹学,研究方向: 最优化计算方法,所在单位: 中国科学院数学与系统科学研究院,计算数学与科学工程计算研究所,8,姓名: 袁亚湘 8,本科,1978年3月 - 1982年2月: 湘潭大学数学系, 获学士.,研究生,1982年3月 - 1982年11月: 中国科学院研究生院(导师: 冯康).,博士 研究生,1983年1月 - 1986年5月: 英国剑桥大学应用数学与理论物理系(导师: M.J.D. Powell), 获博士.,9,本科9,张,树,中,June 1991: Ph.D., Tinbergen Institute, Erasmus University.,June 1984: B.Sc., Mathematics Department, Fudan University.,1999 - 2001: Department of Systems Engineering & Engineering Management,The Chinese University of Hong Kong.,J.F.Sturm: SeDuMi (-2002?),10,张10,第一章线性规划与单纯形法,1 线性规划问题及其数学模型,1.1 问题的提出,eg.,1,生产计划问题,问：产品、各生产多少件，,使利润最大？,11,第一章线性规划与单纯形法1 线性规划问题及其数学模型,eg.,2,污水处理问题,环保要求河水含污低于2，河水可自身净化20%。,问：化工厂1、2每天各处理多少污水，使总费用最少？,分析：,化工厂1处理污水,x,1,万,m,3,化工厂2处理污水,x,2,万,m,3,。,min,z,=,1000x,1,+,800x,2,(2,-,x,1,)/500,2/1000,(1,-,0.2)(2,-,x,1,),+,1.4,-,x,2,/(500,+,200),2/1000,x,1,2,x,2,1.4,x,1,，x,2,0,这里,min z:,表示求,z,的最小值。,200万,m,3,500万,m,3,2万,m,3,1.4万,m,3,化工厂1,化工厂2,1000元/万,m,3,800元/万,m,3,12,eg.2污水处理问题 分析：200万m3500万m32,线性规划的数学模型：,max,(min),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,13,线性规划的数学模型：13,说明：,(1),决策变量：,x,1,，x,2,，x,n 。,一组,决策变量表示为问题的一个方案；,(2),目标函数：,max(min),z,z,为,决策变量的线性函数;,(3),约束条件,一组线性不等式。,c,j,为价值系数,b,i,为资源，,a,ij,为技术系数(,i,=1,m;,j,=1,n),.,14,说明： (1)决策变量：x1，x2，xn 。14,1.2 图解法,eg.,3用图解法求,eg.,1。,max,z,=,2x,1,+,3x,2,1x,1,+,2x,2,8 ,4x,1,16 ,4x,2,12,x,1,，x,2,0,解：,(1)建立,x,1,-,x,2,坐标；,x,2,x,1,(2)约束条件的几何表示；,Q,1,Q,2,Q,3,Q,4,(3)目标函数的几何表示；,*,z,=,2x,1,+,3x,2,o,4,3,15,1.2 图解法 解：x2x1 (2)约束条件的几何,首先取z,=,0，然后，使z逐,渐增大，直至找到最优解所对,应的点。,*,可见，在,Q,2,点,z,取到最大值。,因此，,Q,2,点所对应的解为最优解。,Q,2,点坐标为(4，2)。,即:,x,1,=,4，x,2,=,2,由此求得最优解：,x,1,*,=,4 x,2,*,=,2,最大值：,max,z,=,z,*,=,2x,1,+,3x,2,=,14(,元),x,2,x,1,Q,1,Q,2,(4,2),Q,3,Q,4,*,4,3,16,首先取z = 0，然后，使z逐* 可见，在Q2点z取到,讨论：,(1)唯一最优解,max,z,=,z,*,时，解唯一，如上例。,(2)无穷多最优解,eg.,4,对,eg.,1，,若目标函数,z,=,2x,1,+,4x,2,，,此时表示,目标函数的直线与表示,条件的直线平行，,最优点在线段,Q,3,Q,2,上。,即存在无穷多最优解。,x,2,x,1,Q,1,Q,2,(4,2),Q,3,(2,3),Q,4,o,4,3,*,17,讨论： (2)无穷多最优解x2x1Q1 Q,(3)无界解,eg.,5,max,z,=,2x,1,+,3x,2,4x,1,16,x,1,，x,2,0,则x,2,，z,。,即存在无界解。,在实际问题中，可能,是缺少约束条件。,o,2,2,4,18,(3)无界解o22418,(4)无可行解,eg.,6,max,z,=,2x,1,+,3x,2,2x,1,+,4x,2,8,x,1,+,x,2,1,x,1,，x,2,0,无公共部分，无可行域。,即无可行解。,在实际问题中，可能是关系错。,1,1,2,4,x,1,x,2,19,(4)无可行解1124x1x219,1.3 线性规划的标准型,1、标准型,max,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,20,1.3 线性规划的标准型20,用向量表示,21,用向量表示21,用矩阵描述为：,max,z,=,CX,AX,=,b,X 0,其中: X,=,(x,1,x,2,x,n,),T,C,=,(c,1,c,2,c,n,),b,=,(b,1,b,2,b,m,),T,22,用矩阵描述为：22,2、标准型的化法,(1)minmax min z,=,cx,=,-max(-z), max(-z),=,-min z,=,-cx,令z,=,-z 则max z,=,-cx,(2),不等式(，),对于,“,”情况：在“”左边加上一个松弛变量（非负）,，,变为等式；,对于“”情况：在“”左边减去一个剩余变量（非负），变为等式。,注意：松弛变量、剩余变量在目标函数中的价值系数为0。,(3)无约束变量,令,x,k,=,x,k,-,x,k,”,，x,k,x,k,”,0，,代入即可。,23,2、标准型的化法 (2)不等式(，) (3)无约束变,eg.,7将下述问题化为标准型,min z,=,-x,1,+2x,2,-3x,3,x,1,+ x,2,+ x,3,7,x,1,- x,2,+ x,3,2,-3x,1,+ x,2,+2x,3,=,5,x,1,x,2,0，x,3,无约束,解：令,x,3,=,x,3,-x,3,”,，x,3,x,3,”,0；,式加上一个松弛变量,x,4,；,式减去一个剩余变量,x,5,；,令,z,=,-z,max z,=,x,1,-,2x,2,+,3(x,3,-,x,3,”,),+,0x,4,+,0x,5,x,1,+,x,2,+ (x,3,-,x,3,”,),+,x,4,=,7,x,1,-,x,2,+ (x,3,-,x,3,”,),-,x,5,=,2,-3x,1,+,x,2,+,2(x,3,-,x,3,”,),=,5,x,1,x,2,x,3,x,3,”,x,4,x,5,0,24,eg.7将下述问题化为标准型解：令x3 = x3-x3,1.4 线性规划解的概念,设线性规划为,max,z,=,CX,AX,=,b,X,0,A为m,n矩阵, n,m, Rank,A,=,m (A为行满秩矩阵）,1、可行解：满足条件,、,的,X；,2、最优解：满足,条件,的可行解；,3、基：取,B,为,A,中的,m,m,子矩阵，,Rank,B,=,m，,则称,B,为线性规,划问题的一个基。,取,B,=,(p,1,p,2,p,m,) p,j,=,(a,1j,a,2j,a,mj,),T,则称,x,1,x,2,x,m,为基变量，其它为非基变量。,25,1.4 线性规划解的概念 1、可行解：满足条件、的X,4、基解：取B,=,(p,1,p,2,p,m,),a,11,a,1m,x,1,a,1m+1,a,1n,x,m+1,b,1, +, ,=,a,m1,a,mm,x,m,a,mm+1,a,mn,x,n,b,m,基 基变量,非基 非基变量,令 x,m+1,=,=,x,n,=,0 (非基变量为0),则 BX,B,=,b,26,4、基解：取B = (p1,p2,pm)26,5、基可行解,满足,式要求的基解。,如右图所示，各边交点,O,Q,1,Q,2,Q,3,Q,4,均为基可行解,；,而其延长线的交点Q,5,为,基解，但不是基可行解。,O(0,0),Q,1,(4,0),Q,2,(4,2),Q,4,(0,3),Q,3,(2,3),Q,5,(4,3),6、可行基,基可行解对应的,B,为可行基。,可行解,基可行解,非可行解,基解,27,5、基可行解O(0,0)Q1(4,0)Q2(4,2)Q4(0,2 线性规划问题的几何意义,2.1 基本概念,1、凸集：设K为E,n,(n维欧式空间)的一点集，X,(1),K，X,(2),K。,若X,(1),+(1-)X,(2),K，则称K为凸集。（0,1）,非凸集,X,(1),X,(1),X,(2),X,(2),凸集,X,(1),X,(2),X,(2),X,(1),28,2 线性规划问题的几何意义非凸集X(1)X(1)X(2,2、顶点：X,K，X,(1),K，X,(2),K (任意两点)。若X不能用X,(1),+(1-)X,(2),表示，则称X为K的一个顶点。(0,1),注：顶点所对应的解是基可行解。,3、凸组合：设X,(i),E,n,，若存在0,i,1，i,=,1,2,k，,使 ,则称X为X,(i),(i=1,2,k)的凸组合。,2.2 基本定理,1、定理1 若线性规划存在可行域，则:,可行域,D,=,X|AX,=,b,X,0,为凸集。,29,2、顶点：XK，X(1)K，X(2)K (任意两点,证明：,设 X,(1),=(,x,1,(1),x,2,(1),x,n,(1),),T,D；,X,(2),=(,x,1,(2),x,2,(2),x,n,(2),),T,D； (X,(1),X,(2),),有 AX,(1),=,b， AX,(2),=,b,令 X,=,X,(1),+,(1,-,)X,(2),(0,0 1,0,X,0， 即D为凸集,2、定理2 线性规划的基可行解对应于可行域的顶点。,3、定理3 若线性规划有解，则一定存在基可行解为最优解。,30,证明： 2、定理2 线性规划的基可行解对应于可行域的顶,3 单纯形法,基本思路：,从可行域的一个顶点到另一个顶点迭代求最优解。,3.1 初始基可行解的确定,1、,松弛基（松弛变量对应的,B）,eg.,8,max,z,=,x,1,+,3x,2,x,1,+,2x,2,3,2x,1,+,3x,2,4,x,1,x,2,0,max,z,=,x,1,+,3x,2,+,0x,3,+,0x,4,x,1,+,2x,2,+,x,3,=,3,2x,1,+,3x,2,+,x,4,=,4,x,1,x,2,x,3,x,4,0,化标准型,取,x,3,、x,4,为基变量,令非基变量,x,1,= x,2,=0,初始基可行解：,X,(0),=,(0 0 3 4),T,31,3 单纯形法3.1 初始基可行解的确定max z =,2、观察法,eg.,9,max,z,=,x,1,+,3x,2,+,2x,3,+,x,4,x,1,+,2x,2,+,3x,3,=,3,3x,2,+,x,3,+,x,4,=,4,x,1,x,2,x,3,x,4,0,选,X,B,=,(x,1,x,4,),T,令,x,2,=,x,3,=,0,则 初始基可行解：,X,(0),=,(3 0 0 4),T,32,2、观察法 32,3、人工基,eg.,10,max,z,=,x,1,+,2x,2,+,3x,3,x,1,+,3x,2,+,2x,3,=,3,2x,1,+,x,2,+,x,3,=,4,x,1,x,2,x,3,0,分析：,A,=,1 3 2,2 1 1,找不到单位矩阵基,引入人工变量为初始基变量（2个）,33,3、人工基 分析：33,3.2 最优性的检验与解的判别,34,3.2 最优性的检验与解的判别34,则,35,则35,解的判别：,1. 若 ，则此时的基可行解为最优解；,2. 若存在某个非基变量 的检验数 ，且 ，则该线性规划问题具有无界解（或称无最优解）；,3. 若所有 ，又，对于某个非基变量 有 ，则该线性规划问题具有无穷多最优解。,36,36,3.3 基变换,37,3.3 基变换37,3.4 旋转运算（消元运算）,a,1k,0,a,l-1k,0,p,k,=,（a,lk,） （1）,a,l+1k,0,a,mk,0,得到基可行解，重复3.23.4，,求出最优解。,38,3.4 旋转运算（消元运算）38,3.5 单纯形表,展开如下：,a,11,x,1,+,a,12,x,2,+,+,a,1n,x,n,+,x,n+1,=,b,1,-,c,n+1,a,21,x,1,+,a,22,x,2,+,+,a,2n,x,n,+,x,n+2,=,b,2,-,c,n+2, ,a,m1,x,1,+,a,m2,x,2,+,+,a,mn,x,n,+ x,n+m,=,b,m,-,c,n+m,c,1,x,1,+,c,2,x,2,+,+,c,n,x,n,+,c,n+1,x,n+1,+,+,c,n+m,x,n+m,-,z,=,0,1,x,1,+,2,x,2,+,+,n,x,n,+ 0,x,n+1,+,+ 0,x,n+m,-,z,= Z,0,39,3.5 单纯形表39,建立单纯形表,eg.,11,用单纯形法求解,max,z,=,x,1,+,3x,2,x,1,+,2x,2,8,4x,1,16,4x,2,12,x,1,x,2,0,40,建立单纯形表 eg.11用单纯形法求解40,解：标准化，建立单纯形表,引入松弛变量,x,3,，x,4,，x,5,为初始基变量,max,z,=,x,1,+,3x,2,+,0x,3,+,0x,4,+,0x,5,x,1,+,2x,2,+,x,3,=,8,4x,1,+,x,4,=,16,4x,2,+,x,5,=,12,x,1,x,2,x,3,x,4,x,5,0,此时的解：,x,(0),=,(0,0,8,16,12),T,z,(0),=,0,41,解：标准化，建立单纯形表此时的解：41,解的判别,1,=,1,2,=,3,0,x,(0),非最优解,基变换,max,1,2,=,3,=,2,x,2,入基,min8/2,-,12/4,=,12/4 x,5,出基,42,解的判别 1=1 2=3 0基变换,此时的解：,x,(1),=,(0,3,2,16,0),T,z,(1),=,9,x,(1),非最优,x,1,入基 x,3,出基,此时的解：,x,(2),=,(2,3,0,8,0),T,z,(2),=,11,x,(2),为最优解,即： 最优解：,x,*,=,(2 3 0 8 0),T,最大值：,z,*,=,11,43,此时的解： 即： 最优解：x* = (2 3 0 8 0,X,(0),=(0 0 8 16 12),T,O(0,0),X,(1),=(0 3 2 16 0),T,Q,4,(0,3),X,(2),=(2 3 0 8 0),T,Q,3,(2,3),x,2,x,1,Q,1,Q,2,(4,2),Q,3,(2,3),Q,4,*,O(0,0),44,x2x1Q1Q2(4,2)Q3(2,3)Q4*O(0,4 单纯形法的进一步讨论,4.1 人工变量法,1、大M法（M为很大的正数）,法则：对于max问题，人工变量在目标函数中的价值系数为-M；,对于min问题，人工变量在目标函数中的价值系数为M。,eg.,12,min,z,=,x,1,+,5,x,2,+,0,x,3,+0x,4,2x,1,+,3x,2,+,x,3,=,6,2x,1,+,x,2, x,4,= 1,x,1,x,2,x,3,x,4,0,解：min,z,=,x,1,+,5,x,2,+,0,x,3,+,0,x,4,+,Mx,5,：x,5,为人工变量,2x,1,+,3x,2,+,x,3,=,6,2x,1,+,x,2,x,4,+,x,5,= 1,x,1,x,2,x,3,x,4,x,5,0,列单纯形表求解。,45,4 单纯形法的进一步讨论45,min,z,=,x,1,+,5,x,2,+,0,x,3,+,0,x,4,+,Mx,5,2x,1,+,3x,2,+,x,3,=,6,2x,1,+,x,2,x,4,+,x,5,= 1,x,1,x,2,x,3,x,4,x,5,0,对于min问题，若 min,j,0中，选下标小的非基变量入基；,对相同的最小比值，选下标小的基变量出基。,第二章,j,与,i,的计算同,max,问题,。,54,当计算中出现最小比值相同的情况时，可按Bland规则来计算,习题,P45，1.4分别用图解法和单纯形法求解下列线性规划,并指出单纯形法迭代的每一步相当于图形上的哪一个顶点？,55,习题55,