《[理学]《运筹学》清华大学课件第一章》由会员分享，可在线阅读，更多相关《[理学]《运筹学》清华大学课件第一章（55页珍藏版）》请在金锄头文库上搜索。
1、1,绪论,Operations 汉语翻译：作业运营工作操作 Operations Research (简写：OR)： 日本运用学 港台作业研究 中国大陆运筹学（既有运用，也有策划之意） Operational Research原来名称，意为军事行动研究历史渊源,2,绪论,早期运筹思想：田忌赛马丁渭修宫沈括运粮Erlang 1917 排队论Harris 1920 存储论康脱洛维奇 1939 LP,3,绪论,军事运筹学阶段：兰德公司（RAND）德军空袭 防空系统 Blackett运输船编队空袭逃避深水炸弹 轰炸机编队,4,绪论,运筹学在中国：50年代中期华罗庚: 推广 优选法、统筹法 中国邮递员问
2、题、运输问题,5,运筹学的应用,生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”) 库存管理(合理物资库存量，停车场大小，设备容量) 运输问题 财政、会计(预算，贷款，成本分析，投资，证券管理) 人事(人员分配，人才评价，工资和奖金的确定) 设备管理(维修计划，设备更新) 城市管理(救火车，警车等的分布点的设置) 市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划),6,运筹学的学科体系,规划论：线性规划、非线性规划|、整数规划、目标规划、动态规划 图论与网络 存储论 排队论 决策论 对策论 计算机仿真,7,Yinyu Ye,Professor of Manageme
3、nt 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,8,姓名: 袁亚湘 性别: 男 籍贯: 湖南省资兴市
4、出生年月: 1960年1月 职称: 研究员 专业: 计算数学、应用数学、运筹学 研究方向: 最优化计算方法 所在单位: 中国科学院数学与系统科学研究院 计算数学与科学工程计算研究所,9,本科 1978年3月 - 1982年2月: 湘潭大学数学系, 获学士. 研究生 1982年3月 - 1982年11月: 中国科学院研究生院(导师: 冯康). 博士 研究生 1983年1月 - 1986年5月: 英国剑桥大学应用数学与理论物理系(导师: M.J.D. Powell), 获博士.,10,张 树 中,June 1991: Ph.D., Tinbergen Institute, Erasmus Univ
5、ersity. 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?),11,第一章 线性规划与单纯形法,1 线性规划问题及其数学模型 1.1 问题的提出eg.1 生产计划问题 问：产品、各生产多少件，使利润最大？,12,eg.2污水处理问题环保要求河水含污低于2
6、，河水可自身净化20%。问：化工厂1、2每天各处理多少污水，使总费用最少？,分析：化工厂1处理污水x1万m3,化工厂2处理污水x2万m3。 min z = 1000x1 + 800x2(2 - x1)/500 2/1000(1 - 0.2)(2 - x1) + 1.4 - x2/(500 + 200) 2/1000x1 2x2 1.4x1，x2 0这里min z:表示求z的最小值。,13,线性规划的数学模型：max (min)z = c1x1 + c2x2 + + cnxna11x1 + a12x2 + + a1nxn (=, ) b1a21x1 + a22x2 + + a2nxn (=, )
7、 b2 am1x1 + am2x2 + + amnxn (=, ) bmx1，x2，xn 0,14,说明：,(1)决策变量：x1，x2，xn 。一组决策变量表示为问题的一个方案；(2)目标函数：max(min)zz为决策变量的线性函数;(3)约束条件一组线性不等式。 cj为价值系数, bi为资源， aij为技术系数(i=1,m;j=1,n) .,15,1.2 图解法eg.3用图解法求eg.1。max z = 2x1 + 3x21x1 + 2x2 8 4x1 16 4x2 12 x1，x2 0,解：(1)建立x1 - x2坐标；,(2)约束条件的几何表示；,(3)目标函数的几何表示；,z = 2
8、x1 + 3x2 ,o,4,3,16,首先取z = 0，然后，使z逐 渐增大，直至找到最优解所对 应的点。,可见，在Q2点z取到最大值。因此， Q2点所对应的解为最优解。Q2点坐标为(4，2)。即: x1 = 4，x2 = 2 由此求得最优解：x1* = 4 x2* = 2最大值：max z = z* = 2x1 + 3x2 = 14(元),4,3,17,讨论：(1)唯一最优解 max z = z*时，解唯一，如上例。,(2)无穷多最优解eg.4对eg.1，若目标函数z = 2x1 + 4x2，此时表示目标函数的直线与表示条件的直线平行，最优点在线段Q3Q2上。即存在无穷多最优解。,18,(3
9、)无界解eg.5max z = 2x1 + 3x24x1 16 x1，x2 0则x2 ，z 。即存在无界解。在实际问题中，可能是缺少约束条件。,19,(4)无可行解eg.6max z = 2x1 + 3x22x1 + 4x2 8x1 + x2 1x1，x2 0无公共部分，无可行域。即无可行解。在实际问题中，可能是关系错。,20,1.3 线性规划的标准型1、标准型max z = c1x1 + c2x2 + + cnxna11x1 + a12x2 + + a1nxn = b1a21x1 + a22x2 + + a2nxn = b2 am1x1 + am2x2 + + amnxn = bmx1，x2
10、，xn 0,21,用向量表示,22,用矩阵描述为：max z = CXAX = bX 0其中: X = (x1,x2,xn)TC = (c1,c2,cn)b = (b1,b2,bm)T,23,2、标准型的化法(1)minmax min z = cx = -max(-z) max(-z) = -min z = -cx令z = -z 则max z = -cx,(2)不等式(，)对于“”情况：在“”左边加上一个松弛变量（非负），变为等式；对于“”情况：在“”左边减去一个剩余变量（非负），变为等式。注意：松弛变量、剩余变量在目标函数中的价值系数为0。,(3)无约束变量令xk = xk - xk”，xk
11、,xk” 0，代入即可。,24,eg.7将下述问题化为标准型min z = -x1+2x2-3x3x1+ x2+ x3 7 x1- x2+ x3 2 -3x1+ x2+2x3 = 5 x1,x2 0，x3无约束,解：令x3 = x3-x3”，x3,x3” 0；式加上一个松弛变量x4；式减去一个剩余变量x5；令z = -zmax z = x1- 2x2 + 3(x3 - x3”) + 0x4 + 0x5x1 + x2 + (x3 - x3”) + x4 = 7x1 - x2 + (x3 - x3”) - x5 = 2-3x1 + x2 + 2(x3 - x3”) = 5x1,x2,x3,x3”,
12、x4,x5 0,25,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 = (p1,p2,pm) pj = (a1j,a2j,amj)T则称x1,x2,xm为基变量，其它为非基变量。,26,4、基解：取B = (p1,p2,pm)a11,a1m x1 a1m+1,a1n xm+1 b1 + = am1,amm xm amm+1,amn xn
13、 bm 基 基变量 非基 非基变量 令 xm+1 = = xn = 0 (非基变量为0)则 BXB = b,27,5、基可行解满足式要求的基解。如右图所示，各边交点O,Q1,Q2,Q3,Q4 均为基可行解；而其延长线的交点Q5为 基解，但不是基可行解。,O(0,0),Q1(4,0),Q2(4,2),Q4(0,3),Q3(2,3),Q5(4,3),6、可行基基可行解对应的B为可行基。,28,2 线性规划问题的几何意义 2.1 基本概念1、凸集：设K为En(n维欧式空间)的一点集，X(1)K，X(2)K。 若X(1)+(1-)X(2)K，则称K为凸集。（01）,29,2、顶点：XK，X(1)K，X(2)K (任意两点)。若X不能用X(1)+(1-)X(2)表示，则称X为K的一个顶点。(01)注：顶点所对应的解是基可行解。3、凸组合：设X(i)En，若存在0i 0 X 0， 即D为凸集,2、定理2 线性规划的基可行解对应于可行域的顶点。,3、定理3 若线性规划有解，则一定存在基可行解为最优解。,31,3 单纯形法基本思路：从可行域的一个顶点到另一个顶点迭代求最优解。,3.1 初始基可行解的确定1、松弛基（松弛变量对应的B）eg.8max z = x1 + 3x2x1 + 2x2 32x1 + 3x2 4x1,x2 0,
