《怎样把事情做到最好运筹学课件》由会员分享，可在线阅读，更多相关《怎样把事情做到最好运筹学课件（70页珍藏版）》请在金锄头文库上搜索。
1、OR1,1,OPERATIONS RESEARCH 运筹学,怎样把事情做到最好 郝英奇,OR1,2,第一章 绪论,1.1题解 Operations 汉语翻译 工作、操作、行动、手术、运算 Operations Research 日本运用学 港台作业研究 中国大陆运筹学 Operational Research原来名称，意为军事行动研究历史渊源,OR1,3,绪论,1.2 运筹学的历史 早期运筹思想：田忌赛马 丁渭修宫 沈括运粮 Erlang 1917 排队论 Harris 1920 存储论 Levinson 1930 零售贸易 康脱洛维奇 1939 LP,OR1,4,绪论,1.2运筹学的历史 军
2、事运筹学阶段 德军空袭 防空系统 Blackett 运输船编队 空袭逃避 深水炸弹 轰炸机编队,OR1,5,绪论,1.2运筹学的历史 管理运筹学阶段 战后人员三分:军队、大学、企业 大学：课程、专业、硕士、博士 企业：美国钢铁联合公司 英国国家煤炭局 运筹学在中国：50年代中期引入 华罗庚推广 优选法、统筹法 中国邮递员问题、运输问题,OR1,6,1.3学科性质,应用学科 Morse&Kimball定义：运筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的科学方法。 Churchman定义：运筹学是应用科学的方法、技术和工具，来处理一个系统运行中的问题，使系统控制得到最优的解决
3、方法。 中国定义：运筹学是应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。,OR1,7,1.4定性与定量,例：店主进货 两者都是常用的决策方法 定性是基础，定量是工具，定量为定服务。 定性有主观性也有有效性，定量有科学性也有局限性。管理科学的发展，定量越来越多。但定量不可替代定性。,OR1,8,1.5运筹学的模型,模型：真实事物的模仿，主要因素、相互关系、系统结构。 形象模型：如地球仪、沙盘、风洞 模拟模型：建港口，模拟船只到达。学生模拟企业管理系统运行。 数学模型：用符号或数学工具描述现实系统。V=F（xi,y
4、j,uk) G(xi,yj,uk)0,OR1,9,1.6运筹学的学科体系,规划论：线性规划、非线性规划|、整数规划、目标规划、动态规划 图论与网络 存储论 排队论 决策论 对策论 计算机仿真,OR1,10,1.7运筹学的工作步骤,确定问题 搜集数据建立模型 检验模型 求解模型 结果分析 结果实施,OR1,11,1.8运筹学与计算机,计算机为运筹学提供解题工具。 本书有现成的程序可以利用 要学会解题的思路与方法，建立模型很重要。,OR1,12,第二章 线性规划与单纯形法,2.1 LP(linear programming)的基本概念 LP是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经
5、济效益的优化方法。 LP有一组有待决策的变量， 一个线性的目标函数， 一组线性的约束条件。,OR1,13,2.1.1 LP的数学模型 例题1生产计划问题,某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：,OR1,14,例题1建模,问题：如何安排生产计划，使得获利最多？ 步骤： 1、确定决策变量：设生产A产品x1kg,B产品x2kg 2、确定目标函数：maxZ=70X1+120X2 3、确定约束条件：人力约束 9X1+4X2360 设备约束 4X1+5X2 200 原材料约束3X1+10X2 300 非负性约束X10 X20,OR1,15,例题2配方问
6、题,养海狸鼠 饲料中营养要求：VA每天至少700克，VB每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表：,OR1,16,例题2建模,设抓取饲料I x1kg;饲料II x2kg;饲料III x3kg 目标函数：最省钱 minZ=2x1+7x2+4x3+9x4+5x5 约束条件：3x2+2x2+x3+6x4+18x5 700 营养要求： x1+0.5x2+0.2x3+2x4+0.5x5 30 0.5x1+x2+0.2x3+2x4+0.8x5 =200 用量要求： x1 50,x2 60,x3 50,x4 70,x5 40 非负性要求：x1 0,x2 0,x3 0,x4
7、 0,x5 0,OR1,17,例题3：人员安排问题,医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计：,OR1,18,例题3建模,目标函数：min Z=x1+x2+x3+x4+x5+x6 约束条件： x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30 非负性约束：xj 0,j=1,2,6,OR1,19,归纳：线性规划的一般模式,目标函数：max(min)Z=c1x1+c2x2+c3x3+cnxn 约束条件：a11x1+a12x2+a13x3+a1nxn (= )b1 a21x1+a22x2+a23x3+a2nxn (= )b2 am
8、1x1+am2x2+am3x3+amnxn (= )bn 非负性约束：x1 0,x2 0,xn 0,OR1,20,2.1.2线性规划图解法,由中学知识可知：y=ax+b是一条直线，同理：Z=70x1+120x2x2=70/120x1-Z/120也是一条直线，以Z为参数的一族等值线。 9x1+4x2 360 x1 360/9-4/9x2 是直线 x1=360/9-4/9x2 下方的半平面。所有半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。,OR1,21,例1图示,.,90 80 60 40 20,0 20 40 60 80 100,x1,x2,9x1+4x
9、2 360,4x1+5x2 200,3x1+10x2 300,A,B,C,D,E,F,G,H,I,Z=70x1+120x2,OR1,22,概念,概念： 1、可行解：满足所有约束条件的解。 2、可行域：即可行解的集合。所有约束条件的交集，也就是各半平面的公共部分。满足所有约束条件的解的集合，称为可行域。 3、基解：约束条件的交点称为基解（直观） 4、基可行解：基解当中的可行解。 5、凸集：集合内任意两点的连线上的点均属于这个集合。如：实心球、三角形,OR1,23,结论,可行域是个凸集 可行域有有限个顶点 最优值在可行域的顶点上达到 无穷多解的情形 无界解情形 无解情形,OR1,24,2.1.3线
10、性规划的标准型,代数式maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm xj 0 j=1,2,n,OR1,25,线性规划的标准型,和式：maxZ=cjxj aijxj=bi i=1,2,m xj 0 j=1,2,n,j=1,n,n,j=1,OR1,26,线性规划的标准型,向量式：maxZ=CX pjxj=bi i=1,2,m xj 0 j=1,2,n C=(c1,c2,c3,cn) X=(X1,X2,X3,Xn) T,n,j=1,OR1,27,线性规划的标准型,矩阵式： maxZ
11、=CX AX=b X 0 其中： b=(b1,b2,bm)T a11 a12 .a1n A= a21 a22 a2n am1 am2 amn,OR1,28,标准型的特征,目标函数极大化 约束条件为等式 决策变量非负,OR1,29,非标准型转化为标准型,目标函数极小化转为极大化： minZ=max(Z) ，一个数的极小化等价于其相反数的极大化。 不等式约束的转化： aijxjbi 加入松弛变量 aijxjbi 减去剩余变量 非正变量：即xk 0 则令xk = xk 自由变量：即xk无约束，令xk= xkx”k,OR1,30,非标准型转化举例之一,maxZ=70X1+120X2 maxZ=70X1
12、+120X2 9X1+4X2360 9X1+4X2+X3=360 4X1+5X2 200 4X1+5X2 +x4=200 3X1+10X2 300 3X1+10X2+x5 =300 X10 X20 Xj0 j=1,2,5,OR1,31,非标准型转化举例之二,minZ=x1+2x2-3x3 maxZ=x12x2+3(x3x”3) x1+x2+x3 9 x1+x2+x3 x”3 + x4=9 -x1-2x2+x3 2 x12x2+x3 x”3 - x5= 2 3x1+x2-3x3=5 3x1+x23(x3 x”3 )=5 x1 0 x2 0 x3无约束 x1 0 x2 0 x3 0 x”3 0 x
13、40 x50,OR1,32,2.1.4基可行解,基的概念：如前所述LP标准型 和式：maxZ= cjxj aijxj=bi xj 0 j=1,2,n 矩阵式：maxZ=CX AX=b X 0 约束方程的系数矩阵A的秩为m，且mn。设A=B+N ，B是A中mm阶非奇异子矩阵，则称B是LP的一个基，即：B是A中m个线性无关向量组。,n,j=1,n,j=1,OR1,33,基解的概念,不失一般性,设B是A的前m列,即B=(p1,p2,pm）,其相对应的变量XB=(x1,x2,xm)T,称为基变量；其余变量XN=(Xm+1,Xn)T称为非基变量。令所有非基变量等于零,则X=（x1,x2,xm,0,0)T
14、称为基解 。,OR1,34,基可行解的概念,基可行解：基解可正可负，负则不可行（违背非负性约束条件），称满足所有约束条件的基解为基可行解。 退化的基可行解：若某个基变量取值为零，则称之为退化的基可行解。 基解的数目：最多Cmn=n!/m!(n-m)!,OR1,35,例题6 基可行解说明,maxZ=70X1+120X2 P1 P2 P3 P4 P5 9X1+4X2+X3=360 9 4 1 0 0 4X1+5X2 +x4=200 A= 4 5 0 1 0 3X1+10X2+x5 =300 3 10 0 0 1 Xj0 j=1,2,5 这里m=3,n=5。 Cmn=10,OR1,36,例题6 基可
15、行解说明,基（p3,p4,p5） ，令非基变量x1,x2=0，则基变量x3=360, x4=200, x5=300, 可行解 基（p2,p4,p5）,令非基变量x1=0,x3=0基变量x2=90,x4=250,x5=600. 非可行解 基（ p2,p3,p4 ），令非基变量x1,x5=0，则基变量x2=30, x3=240, x4=50,可行解（P21图）,OR1,37,2.2单纯形法,2.2.1初始基可行解的确定 从系数矩阵中找到一个可行基B，不妨设B由A的前m列组成，即B=(P1,P2,Pm)。进行等价变换约束方程两端分别左乘B1 得 X1+ +a1m+1xm+1+a1nxn=b1 x2+ +a
