下载文档原格式
OPERATIONS RESEARCH运筹学Ⅰ——怎样把事情做到最好第一章绪论♦1.1题解Operations 汉语翻译工作、操作、行动、手术、运算Operations Research日本——运用学港台——作业研究中国大陆——运筹学Operational Research原来名称，意为军事行动研究——历史渊源绪论♦1.2 运筹学的历史早期运筹思想：田忌赛马丁渭修宫沈括运粮Erlang 1917 排队论Harris 1920 存储论Levinson 1930 零售贸易康脱洛维奇1939 LP绪论♦1.2运筹学的历史军事运筹学阶段德军空袭防空系统Blackett运输船编队空袭逃避深水炸弹轰炸机编队绪论♦1.2运筹学的历史管理运筹学阶段战后人员三分:军队、大学、企业大学：课程、专业、硕士、博士企业：美国钢铁联合公司英国国家煤炭局运筹学在中国：50年代中期引入华罗庚推广优选法、统筹法中国邮递员问题、运输问题1.3学科性质▪应用学科▪Morse&Kimball定义：运筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的科学方法。
▪Churchman定义：运筹学是应用科学的方法、技术和工具，来处理一个系统运行中的问题，使系统控制得到最优的解决方法。
▪中国定义：运筹学是应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。
1.4定性与定量♦例：店主进货♦两者都是常用的决策方法♦定性是基础，定量是工具，定量为定性服务。
♦定性有主观性也有有效性，定量有科学性也有局限性。
管理科学的发展，定量越来越多。
但定量不可替代定性。
1.5运筹学的模型♦模型：真实事物的模仿，主要因素、相互关系、系统结构。
♦形象模型：如地球仪、沙盘、风洞♦模拟模型：建港口，模拟船只到达。
学生模拟企业管理系统运行。
♦数学模型：用符号或数学工具描述现实系统。
《管理运筹学》1、运筹学的工作步骤(1)提出和形成问题．(2)建立模型．(3)求解．(4)解的检验．(5)解的控制．(6)解的实施.2、运筹学模型三种基本形式：(1)形象模型(2)模拟模型(3)符号或数学模型构模的五种方法和思路： (1)直接分析法 (如线性规划)(2)类比法（手机的普及与电视机的普及）(3)数据分析法（如汽车销售量预测模型）(4)试验分析法（销售量与价格之间的关系模型）(5)想定(构想)法（销售与心理）3、如何将线性规划问题的一般形式化为标准形式：1.如果问题是求目标函数的最小值，求min f＝∑Cjxj则可先将目标函数乘（-1），化为求极大值问题，即求 max Z=－f=－∑Cjxj2.如果有某个bk≤0，则可将该等式两边均乘以(－1)，使右端常数项bk=－bk≥03.如果第k个约束条件是∑akjxj≤bk,引入松弛变量sk≥0 , 将它写成∑akjxj+sk＝bk如果第l个约束条件是∑aljxj≥bl则引入剩余变量(也可称为松弛变量)sl≥0，将它写成∑aljxj—sl=bl 且使松弛变量和剩余变量在目标函数中的系数为零。
4.如果对某个变量xj没有非负限制(这种变量称为自由变量或无约束变量)，则引进两个非负变量xj′，xj″，令xj＝xj′－xj″代人目标函数和约束条件中，可将它化为对全部变量都有非负限制的问题。
4、①目标函数为变量的线性函数，约束条件也为变量的线性等式或不等式的模型称之为线性规划。
②如果目标函数是变量的非线性函数，或约束条件中含有变量非线性的等式或不等式的数学模型则称之为非线性规划。
③满足所有约束条件的解称为该线性规划的可行解。
④把使得目标函数值最大(即利润最大)的可行解称为该线性规划的最优解,此目标函数值称为最优目标函数值，简称最优值5、图解法的启示1．最优解：如果某一个线性规划问题有最优解，则一定有一个可行域的顶点对应一个最优解。
（一般为封闭可行域凸集）2．无穷多个最优解：若将上例中的目标函数变为求maxZ=50x1+50x2则代表目标函数的直线平移到最优位置后将和直线x1+x2=300重合。
第一章绪论一运筹学的发展历史1学科起源：二战期间英美等国军事部门集中多学科人员，研究提高武器系统效能，如反空袭雷达控制系统，使雷达和高炮相配合。
诺将物理学家布莱克特（Blackett）领导研究小组“Operational Research”，多学科构成（布莱克特马戏团）。
战争结束后专家转移到企业和院校——学科形成。
2我国古代的运筹思想：齐王赛马——齐王“上中下”，田忌“下上中”丁渭修皇宫——北宋真宗宰相丁渭（澶chan州之盟的主和派），主持皇宫失火后的修复。
宫前大街取土、引汴河运料、完工后回填废土。
3我国近代以来：50年代开始钱学森、许志国等引进运筹学理论，华罗庚教授回国后从事优选法和统筹法研究推广（烧茶壶的故事）4翻译：来自汉高祖“夫运筹帷幄之中,决胜千里之外,吾不如子房;填国家,抚百姓,给饷馈,不绝粮道,吾不如萧何;连百万之众,战必胜,攻必取,吾不如韩信。
”台湾地区直译为“运作研究”。
二运筹学的特点运筹学存在多种定义，如“依照给定目标和条件，从众多方案中选择最优方案的最优化技术”，学科特点：最优化、定量化1 多种专家的协作2 科学的方法：从实际情况出发，通过假设的模型打到一个符合实际的结论3 目的在于解决实际问题。
4 需要系统的信息资料5 需要建立模型——运筹学的核心问题就是通过合适的模型分析系统的未来情况6 对于复杂问题，需要计算机三运筹学的模型运筹学的主要特点是通过模型来描述和分析所认定范围内的系统状态。
分析过程包括：1 系统分析和问题描述。
认定问题的实质——社会经济问题复杂性、不可重复性，不同于具有可控性的物理模型（提高企业效益：开发市场？增加设备？加强研发？）。
明确系统的主要目标（利润最大化、市场占有率最大化、销售收入最大化？GDP增长、可持续协调增长？）、找出系统主要变量和参数、变化范围、相互关系及其对目标的影响。
分析问题的可行性：技术可行性—有无现成的运筹学方法？经济可行性—研究的成本和预期的效果，考虑运筹决策的时间和代价，要对研究问题的深度和广度作出一定限制操作可行性—研究人员的配备2 建立数学模型——要尽可能简单；要能完整的描述所研究的系统。
运筹学课程讲义第一部分线性规划第一章线性规划的基本性质1.1 线性规划的数学模型一、线性规划问题的特点胜利家具厂生产桌子和椅子两种家具。
桌子售价50 元/个，椅子售价30 元/个。
生产桌子和椅子需木工和油漆工两种工种。
生产一个桌子需要木工4 小时，油漆工2小时。
生产一个椅子需要木工3 小时，油漆工1 小时。
该厂每月可用木工工时为120 小时，油漆工工时为50 小时。
问该厂如何组织生产才能使每月的销售收入最大？max z 50x1 30x24x1 3x2 1202x1 x2 50x1,x2 0 例：某工厂生产某一种型号的机床。
每台机床上需要 2.9m、2.1m、1.5m的轴，分别为1根、2根和1根。
这些轴需用同一种圆钢制作，圆钢的长度为74m。
如果要生产100台机床，问应如何安排下料，才能用料最省？二、数学模型的标准型1. 繁写形式2. 缩写形式3. 向量形式4. 矩阵形式若原模型中变量 x j 有上下界，如何化为非负变量？三、 任一模型如何化为标准型？1. 若原模型要求目标函数实现最大化，如何将其化为最小化问题？2. 若原模型中约束条件为不等式，如何化为等式？3. 若原模型中变量 x k 是自由变量，如何化为非负变量？1. 2 图解法该法简单直观，平面作图适于求解二维问题。
使用该法求解线性规划问题时，不必把原模型化为标准型。
一、 图解法步骤1. 由全部约束条件作图求出可行域2. 作出一条目标函数的等值线3. 平移目标函数等值线，作图求解最优点，再算出最优值 max z 5x 1 6x 2 7x 3x 1 5x 23x 3 15 5x 1 6x 210x 3 20 x 1 x 2 x 3 5x 1 0,x 2 0,x 3无约束令 x 1' x 1,x 3 x 3' x 3'',x 3' ,x 3'' 0, Z 1Z ' 1 1 min z ' 5x 1' 6x 2 7x 3' 7x 3'' 0x 5 Mx 6 1 x 1' 5x 2 1 11 3x 3' 3x 3'' x 4 x 6 15 1 5x 1' 6x 2 10x 3' 10x 3'' x 5 20 1 x ' x 1 ' II '' 54.Mx 7 x 1, x 2 , x 3, x 3, x 4 , x 5 ,x 6, x 7 0从图解法看线性规划问题解的几种情况1. 有唯一最优解2. 有无穷多组最优解3. 无可行解4. 无有限最优解（无界解）min z 6x1 4x?2x〔X2 13 最优解（1,0），最优值33x14x2 22x1, x20直观结论：1）线性规划问题的可行域为凸集，特殊情况下为无界域（但有有限个顶点）或空集；2）线性规划问题若有最优解，一定可以在其可行域的顶点上得到。
运筹学讲义《管理运筹学》1、运筹学的工作步骤(1)提出和形成问题．(2)建立模型．(3)求解．(4)解的检验．(5)解的控制．(6)解的实施.2、运筹学模型三种基本形式：(1)形象模型(2)模拟模型(3)符号或数学模型构模的五种方法和思路： (1)直接分析法 (如线性规划)(2)类比法（手机的普及与电视机的普及）(3)数据分析法（如汽车销售量预测模型）(4)试验分析法（销售量与价格之间的关系模型）(5)想定(构想)法（销售与心理）3、如何将线性规划问题的一般形式化为标准形式：1.如果问题是求目标函数的最小值，求min f＝∑Cjxj则可先将目标函数乘（-1），化为求极大值问题，即求 max Z=－f=－∑Cjxj2.如果有某个bk≤0，则可将该等式两边均乘以(－1)，使右端常数项bk=－bk≥03.如果第k个约束条件是∑akjxj≤bk,引入松弛变量sk≥0 , 将它写成∑akjxj+sk＝bk如果第l个约束条件是∑aljxj≥bl则引入剩余变量(也可称为松弛变量)sl≥0，将它写成∑aljxj—sl=bl 且使松弛变量和剩余变量在目标函数中的系数为零。
4.如果对某个变量xj没有非负限制(这种变量称为自由变量或无约束变量)，则引进两个非负变量xj′，xj″，令xj＝xj′－xj″代人目标函数和约束条件中，可将它化为对全部变量都有非负限制的问题。
4、①目标函数为变量的线性函数，约束条件也为变量的线性等式或不等式的模型称之为线性规划。
②如果目标函数是变量的非线性函数，或约束条件中含有变量非线性的等式或不等式的数学模型则称之为非线性规划。
③满足所有约束条件的解称为该线性规划的可行解。
④把使得目标函数值最大(即利润最大)的可行解称为该线性规划的最优解,此目标函数值称为最优目标函数值，简称最优值5、图解法的启示1．最优解：如果某一个线性规划问题有最优解，则一定有一个可行域的顶点对应一个最优解。
（一般为封闭可行域凸集）2．无穷多个最优解：若将上例中的目标函数变为求maxZ=50x1+50x2则代表目标函数的直线平移到最优位置后将和直线x1+x2=300重合。
第六讲排队论X/Y/ZX处填写表示相继到达间隔时间的分布;Y处填写表示服务时间的分布;Z处填写并列的服务台的数目c.c=1 单服务台，c>1 多服务台表示相继到达间隔时间和服务时间的各种分布的符号: M —负指数分布 D —确定型Ek —k 阶爱尔朗分布GI — 一般相互独立的时间间隔的分布 G — 一般服务时间的分布 X/Y/Z/A/B/CA 处填写系统容量限制N ；N=c 损失制，N=∞等待制系统，N>c 混合制系统B 处填写顾客源数m （有限、无限）；C 处填写服务规则（FCFS/LCFS/SIRO/PR ）。
约定：FCFS Z Y X /////∞∞如略去后三项，即指1、平均到达率(λ)：单位时间内平均到达的顾客数。
平均到达间隔 (1/λ)2、平均服务率(μ)：单位时间内平均服务的顾客数。
平均服务时间(1/μ)3、队长(Ls)：排队系统中顾客的平均数。
4、队列长(Lq)： 指系统中排队等候服务的顾客数。
Ls=Lq+正被服务的顾客数5、逗留时间(Ws)：指一个顾客在系统中的停留时间。
6、等待时间(Wq)：指一个顾客在系统中排队等待的时间。
Ws=Wq+服务时间7、系统的状态：描述系统中的顾客数损失制、服务台个数c系统容量N系统容量无限0,1,2,...,N0,1,2,...0,1,2,...,c8、系统的状态概率[Pn ( t )] ：指t 时刻、系统状态为n 的概率9、稳定状态（统计平衡状态）：lim Pn (t )→PnP n =P {N =n }稳态 系统中有n 个顾客概率 P 1稳态 系统中有1个顾客概率 P 0稳态 所有服务台全部空闲概率模型P n (t)的计算（在时刻t 系统中有n 个顾客的概率）在时刻在时刻×O×O离去到达n n n n××O Onn +1n -1n(A)(B)(C)(D)t +Δt 顾客数在区间（t , t +Δt ）t顾客数情况λΔt μΔtλΔtP n (t )P n (t )P n+1(t )P n-1(t )1-λΔt 1-λΔt μΔt1-μΔt1-μΔtP n (t +Δt )=P n (t )(1-λΔt )(1-μΔt )+P n +1(t )(1-λΔt )μΔt++P n-1(t)λΔt(1- μΔt) +P n (t)λΔt μΔt n ≥1整理得：P n (t +Δt )=P n (t )(1-λΔt -μΔt )+P n +1(t )μΔt +P n -1(t )λΔt +o(Δt ) [P n (t +Δt )-P n (t )]/Δt =λP n -1(t )+μP n +1(t )-(λ+μ)P n (t ) 令ΔtdP n (t )/d t =λP n -1(t )+μP n +1(t )–(λ+μ)P n (t )( n ≥1) (1) 考虑P 0(t )的情况：在时刻在时刻×O O离去到达000××O010(A)(B)(C)t +Δt 顾客数在区间（t , t +Δt ）t 顾客数情况μΔt P 0(t )P 1(t )1-λΔt 1-λΔt 1P 0(t )λΔtμΔtP 0(t +Δt )=P 0(t )(1-λΔt )+P 1(t )(1-λΔt )μΔt+ P 0(t )λΔt μΔt 令ΔtdP 0(t )/d t =-λP 0(t )+μP 1(t ) （2）令dP n (t )/d t =0，由(1)和(2)得到-λP 0+μP 1=0 (3)λP n -1+μP n +1-(λ+μ)P n =0 (4)1 =P P 0λμ由(3)式得λ, 012==nn P P n （），，，0μ通过求解可得令n =1，由(4)式得220P P λμ=（）200001n n P P P P λλμμ∞=⎛⎫⎛⎫=+++= ⎪ ⎪⎝⎭⎝⎭∑1λρμ=<（令）2001111P ()P ρρρ+++==-01(1),1n n P P n ρρρ=-=-≥011n n P P P ρ∞==-==∑忙λλ…...0P 1λP n -1+μP n +1 =(λ+μ)P n对状态0对状态n (n ≥1)系统状态转移速度图（1）系统中平均顾客数（L s ）01230123S n n L nP P P P P ∞===⋅+⋅+⋅+⋅∑=-+++23(1)(23)ρρρρS ⎫=+++⎪⇒⎬=+++⎪⎭S 232342323ρρρρρρρ-=+++=-S 23(1)1ρρρρρρ/11/s L ρλμλρλμμλ===---记230(1)1(1)2(1)3(1)ρρρρρρρ=⋅-+⋅-+⋅-+⋅-+（2）队列中等待的平均顾客数（L q ）∞==⋅+⋅+⋅+=-∑1231012(1)q nn L P P P n P∞∞===-=--=-=-∑∑011(1)n n s s n n nP P L P L λρρμλ（3）顾客逗留时间的期望值（W s ）李泰勒（Little ）证明了在很宽的条件下，排队系统数量指标之间有以下的关系式： W s =L s /λe=⋅=--11s W λμλλμλ（4）队列中顾客等待时间（W q ）李泰勒证明了在很宽的条件下，排队系统数量指标之间有以下的关系式==-=-=--111qq s e L W W ρλμμλμμλ()1 ,111/0≥-=-=<=n ρρP ρP n n μλρ(1) 队长（L s ）指在系统中的顾客数(2) 排队长（L q ）指系统中排队等候服务的顾客数L q =L s -正被服务的顾客数λμλ-=s LλμλρρL L s q -=-=(3) 逗留时间（W s ）指一个顾客在系统中的停留时间(4) 等待时间（W q ）指一个顾客在系统中排队等待的时间W q =W s -服务时间λμW E W s -==1][λμρμW W s q -=-=1（5）顾客在系统中逗留的时间W （随机变量），在M/M/1情形下，它服从参数为μ-λ的负指数分布，即()()()() ()1 ()() ()1() ()()1w w wwF w e f w e w P W w F w e w P W w F w e μλμλμλμλμλ--------=-=->=-=≤==-分布函数密度函数顾客在系统中逗留时间超过的概率是顾客在系统中逗留时间不超过的概率是（12年，第二题，15分）某修理店只有一个修理工，来修理的顾客到达过程为泊松流，平均4人/小时；修理时间服从负指数分布，平均每人服务时间为6分钟。
请计算： 1）修理店空闲的概率； 2）店内恰有3个顾客的概率； 3）在店内的平均顾客数；4）每位顾客在店内的平均逗留时间； 5）等待服务的平均顾客数； 6）每位顾客平均等待服务的时间； 7）必须在店内消耗10分钟以上的概率。
解：由已知条件知4/10/λμ==人小时，人小时 ，因此40.410λρμ===0P 10.6ρ=-=33P (1)0.0384ρρ=-=42L 1043s λμλ===--111W 1046s μλ===--0.444L 10415q ρλμλ⨯===--0.41W 10415s ρμλ===--1）修理店空闲的概率2）店内恰有3个顾客的概率3）在店内的平均顾客数4）每位顾客在店内的平均逗留时间5）等待服务的平均顾客数6）每位顾客平均等待服务的时间7）必须在店内消耗10分钟以上的概率()11P(W>)6w e e μλ---==（08年，第五题，15分）顾客按泊松分布到达某单人理发店，平均间隔20分钟。
理发时间为负指数分布，平均每人15分钟。
设该系统符合M/M/1模型，求： a ）顾客不必等待的概率； b ）顾客在店内平均等待时间；c ）若顾客在店内耗时超过1.25小时，则雇人帮忙，问平均到达率达到多少以上需雇人帮忙。
解：由已知条件知3/4/λμ==人小时，人小时，因此30.754λρμ===a ）顾客不必等待的概率0P 10.25ρ=-=；b ）顾客在店内平均等待时间q 0.75W 0.7543ρμλ=--==小时；c ）若顾客在店内耗时超过1.25小时，即s W 1.25=，因此111.25, 3.24λμλλ=--==，平均到达率达到32/.人小时以上需雇人帮忙。
M/M/1/N/∞模型（混合制系统）假定系统最大容量为N，单服务台情形排队等待的顾客最多为N-1λλμλλμN+1个状态μ10111()n n nN NP PP P PP Pλμλλμμλ+--=+=+=P n 的计算2000001NNn n P P P P P ρρρ==+++=∑1 =P P 0λμ通过求解可得, 10nn P P n Nλμ=≤≤（）2011N P ()ρρρ+++=10111N ()P ρρ+-⋅=-n1 n N N n N P P ++-=≠--=≤-0111111ρρρρρρ解得：ρ（队长++=+==-≠--∑N Nn N n N nP 1s 11L , 111ρρρρ）(1) ==-=--∑Nn s o n n P L P q 1L 11 （）（）(2) 队列长有效到达率λe =λ(1-P N ) 系统不满时顾客以λ的速度进入系统1W 1q q q s e N L L W P λλμ===--（）(4) 顾客等待时间0W 1sss e L L P λμ==-（）(3) 顾客逗留时间λe = μ(1-P 0)顾客源为有限的情形（M/M/1/∞/m ）mλλμμ机器故障问题：设共有m台机器，机器故障停机表示到达，待修机器形成队列，修理工是服务员。
+--=+-+=-+≤≤-=10111(1)[()],11n n nm mP m PP m n P m n P n mP PμλμλλμμλM/M/c 规定各服务台工作相互独立且平均分配服务率相同，即⎧μ1=μ2=…=μc=μ整个服务机构的平均服务率为cμ,(n≥c)nμ,(n <c)⎨⎩μ…...cμn≤c n>cλλλλ()(c)μλμλλμμλλμ+-+-=++=+≤<+=+≥101111(1)(),1(),n n nn n nP Pn P P n P n cc P P c P n如有侵权请联系告知删除，感谢你们的配合！。
