运筹学(一)

运筹学（O.R.)郑州大学管理工程学院：冯小玲教材胡运权主编，运筹学教程（第四版），清华大学出版社，2012。课程说明课程说明参考书（1）胡运权主编，运筹学习题集（第四版），清华大学出版社，2010（2）钱颂迪等，运筹学（第三版），清华大学出版社，2005课程说明先修课程微积分、线性代数、概率论学习方式课堂听课、课下习题、软件学习主要授课内容：绪论线性规划及单纯形法线性规划的对偶理论与灵敏度分析运输问题目标规划整数规划动态规划图与网络分析绪论一、运筹学的起源与发展二、运筹学研究的基本特点与基本方法三、运筹学研究的主要分支四、运筹学在企业管理中的应用一、运筹学的起源与发展1.什么是运筹学英文：OperationalResearch(英国)OperationsResearch(美国)（直译为“作业研究”、“运用研究”）中文：运筹学（来源于“夫运筹帷幄之中，决胜于千里之外”）运筹学是在实行管理的领域，运用数学方法，对需要进行管理的问题统筹规划，作出决策的一门应用科学(P.M.Morse与G.E.Kimball)；运筹学是用数学方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优化可行方案（《中国大百科全书》）；运筹学是应用分析、试验、量化的方法，对经济管理系统中人、财、物等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理（《中国企业管理百科全书》）。2.运筹学的发展历史（1）二战以前：萌芽齐王-田忌赛马、丁渭修皇宫等。（2）二战期间：产生1938年，英国某雷达站负责人罗伊提出整个防空作战系统运行的研究，并用到了operationalresearch来描述此研究。1940年，英国军事部门成立了第一个由一些数学家、物理学家和工程专家等组成的OR小组，负责研究一些武器有效使用的问题。1942年，美国也成立了由17人组成的OR小组，研究反潜艇策略等问题。（3）二战后：推广与发展战时从事运筹学研究的许多专家转到了经济部门、民用企业、大学或研究所，继续从事决策的数量方法的研究，运筹学作为一门学科逐步形成并得以迅速发展。运筹学发展到今天，已成为分支学科众多的一个繁荣昌盛的大家族。随着电子计算机的发展和使用，运筹学处理复杂性问题的能力大大加强，成为解决实际问题的有力工具，广泛地应用于企业管理、交通运输、公共服务等领域。二、运筹学研究的基本特征与基本方法1.运筹学研究的基本特征（1）系统性特征运筹学用系统的观点来分析一个组织（或系统），它着眼于整个系统而不是一个局部，通过协调各组成部分之间的关系和利害冲突，使整个系统达到最优状态。（2）综合性特征运筹学是一门交叉学科，具有综合性，它的起源就是由不同学术背景的专家共同解决实际问题。它充分利用了数学、计算机科学、统计学及其它科学的成就，这决定了运筹学内容的跨学科性和综合性。（3）模型方法的应用运筹学研究建立在科学的研究方法之上，它研究的第一步就是根据实际问题和管理要求建立必要的数学或模拟模型。然后对模型进行求解、分析和检验。因此学习运筹学要掌握的重要技巧就是对运筹学模型的表达、运算和分析的能力。2.运筹学研究的基本方法（1）分析和表述问题；（2）建立模型；（3）求解模型；（4）测试模型；（5）对模型进行必要的修正；（6）建立对解的有效控制；（7）方案的实施。三、运筹学研究的主要分支线性规划（linearprogramming)非线性规划动态规划图论与网络分析存贮论排队论对策论决策论四、运筹学在企业管理中的应用生产计划。使用运筹学方法从总体上确定适应需求的生产、储存和劳动力安排等计划，以谋求最大的利润或最小的成本。库存管理。存储论应用于多种物资库存量的管理，确定某些设备的合理的能力或容量以及适当的库存方式和库存量运输问题。用运筹学中运输问题的方法，可以确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择。人事管理。可以用运筹学方法对人员的需求和获得情况进行预测；确定合适需要的人员编制；用指派问题对人员合理分配；用层次分析法等方法来确定一个人才评价体系等。市场营销。可把运筹学方法用于广告预算和媒体的选择、竞争性的定价、新产品的开发、销售计划的制定等方面。财务和会计。可以用运筹学方法进行预测、贷款、成本分析、定价、证券管理、现金管理。第一章线性规划与单纯形法主要内容：第一节线性规划问题及其数学模型第二节图解法第三节单纯形法原理第四节单纯形法计算步骤第五节单纯形法的进一步讨论第六节线性规划在经济管理中的应用例子第一节线性规划问题及其数学模型一、线性规划问题举例例1（生产计划问题）：美佳公司计划制造Ⅰ，Ⅱ两种家电产品。已知各制造一件时分别占用的设备A,B的台时、调试时间、调试工序及每天可用于这两种家电的能力、各售出一件的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润为最大。表1-1项目ⅠⅡ每天可用能力设备A（h)0515设备B（h)6224调试工序（h)115利润（元）21设x1,x2分别代表Ⅰ，Ⅱ两种家电的生产量，此问题的数学模型为：目标函数约束条件212maxxxz0,52426155.2121212xxxxxxxst例2（仓库租借问题）：某公司在下一年度的1—4月的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于表1-2.仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3.租借仓库的合同每月月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签订一份合同，也可签若干份租用面积和租用期限不同的合同，试确定该公司签订租借合同的最优策略，目的使所付租借费最小。合同租借期限1个月2个月3个月4个月租借费（元/100m2)2800450060007300表1-2月份1234所需仓库面积（100m2)15102012表1-3设xij公司在第i（i=1,2,3,4)个月初签订租借期为j（j=1,2,3,4)个月的合同的仓库面积，此问题的数学模型为：142313322212413121117300)(6000)(4500)(2800minxxxxxxxxxxz)4,,1;4,,1(015201015.4132231432312322141323222114131214131211jixxxxxxxxxxxxxxxxxxxxxstij二、线性规划问题的数学模型线性规划问题数学模型的三个组成要素1.决策变量:是决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。2.目标函数:指问题要达到的目的要求，表示为决策变量的函数。3.约束条件:指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。nnxcxcxcz2211min)max(或n:变量个数m：约束个数cj:价值系数bi:资源拥有量aij:工艺系数线性规划问题数学模型的一般表示形式：该模型的简化表示：njjjxcz1min)max(或),,1(0),,1((.1njxmibxastjnjijij），或该模型的向量表示：);,,,(..min)max(212121211mmjjjjnnnjjjbbbaaaxxxcccxtszbPXC0XbPCX；；其中，），（或或该模型的矩阵表示：..min)max(212222111211mnmmnnaaaaaaaaaAXAXtsz其中，），（或或0bCX三、线性规划问题的标准形式为了使线性规划问题的解法标准，就要把一般形式化为标准形式。标准形式如下：njjjxcz1max),,1(0),,1(.1njxmibxastjnjijij标准形式特点：4.决策变量取值非负。1.目标函数为求极大值；2.约束条件全为等式；3.约束条件右端常数项bi全为非负值；把非标准形式转化为标准形式的方法：（1）目标函数为min型，即等价于求，令，即化为：；（2）约束条件的右端项bi为负值，则该行左右两端同时乘以（-1），同时不等号也要反向；（3）第i个约束为型，在不等式左边增加一个非负的变量，称为松弛变量；同时该变量在目标函数中的系数为0；njjjxcz1min)max(zzznjjjxcz1max（4）第i个约束为型，在不等式左边减去一个非负的变量，称为剩余变量；同时令该变量在目标函数中的系数为0；（5）若，令（6）若无约束，令，其中，xxxxxx0,xx0x例3：将下述线性规划模型化为标准形式：32132minxxxz取值无约束321321321321,0,0632442392.xxxxxxxxxxxxst54332100332maxxxxxxxz0,,,,,63324422392.54332133215332143321xxxxxxxxxxxxxxxxxxxxst标准形式化为：和剩余变量同时引入松弛变量，，其中解：令,0,,,543333311xxxxxxxxxzz第二节图解法一、图解法的步骤1.画出直角平面坐标系；2.图示约束条件，找出可行域；3.图示目标函数；4.最优解的确定。212maxxxz0,52426155.2121212xxxxxxxst242621xx32x521xx2x1xo4Q3Q1Q2Q最优解在Q2处获得，此时x1=3.5,x2=1.5,目标函数值为8.5例4：用图解法求解以下线性规划问题二、由图解法得到的启示（2）无穷多最优解（若上例中目标函数变为maxz=3x1+x2)；242621xx32x521xx2x1xo4Q3Q2Q1Q(3)无界解（若去掉例子中第2、3个约束）；32x2x1xo1.求解线性规划问题时，解的情况有四种类型。（1）惟一最优解（如上例）；(4)无可行解。62;22121xxxx目标函数为maxz=3x1+x2，约束条件为2x1xo2.若线性规划问题的可行域存在，则可行域一定是个凸集。3.线性规划问题的最优解若存在，则最优解或最优解之一一定是可行域的凸集的某个顶点。4.解题思路是，先找凸集的任一顶点，计算其目标函数值。比较其相邻顶点函数值，若更优，则逐点转移，直到找到最优解。第三节单纯形法原理可行解：满足约束条件的解称为可行解，可行解的集合称为可行域。最优解：使目标函数达到最大值的可行解。基：约束方程组的一个满秩子矩阵称为规划问题的一个基，基中的每一个列向量称为基向量，与基向量对应的变量称为基变量，其他变量称为非基变量。基解：在约束方程组中，令所有非基变量为0，可以解出基变量的唯一解，这组解与非基变量的0共同构成基解。基可行解：满足变量非负的基解称为基可行解可行基：对应于基可行解的基称为可行基一、线性规划问题的解212maxxxz0,52426155.2121212xxxxxxxst543210002maxxxxxxz0,,,,52426155.5432152142132xxxxxxxxxxxxxst化为标准形式O是5241500x3,x4,x5⑨Q4是218030x2,x4,x5⑧P3否-70-45120x2,x3,x5⑦P4否020-1050x2,x3,x4⑥Q1是