下载文档原格式
第一章绪论一运筹学的发展历史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）线性规划问题若有最优解，一定可以在其可行域的顶点上得到。
《管理运筹学教案》PPT课件第一章：管理运筹学概述1.1 管理运筹学的定义解释管理运筹学的概念和内涵强调管理运筹学在实际管理中的应用价值1.2 管理运筹学的发展历程介绍管理运筹学的起源和发展过程提及著名学者和管理运筹学的重要成果1.3 管理运筹学的方法和工具概述管理运筹学常用的方法和工具简要介绍线性规划、整数规划、动态规划等方法1.4 管理运筹学的应用领域列举管理运筹学在不同领域的应用实例强调管理运筹学在企业经营、物流管理、生产计划等方面的应用第二章：线性规划2.1 线性规划的基本概念解释线性规划的目标函数和约束条件引入可行解、最优解等基本概念2.2 线性规划的图解法演示线性规划问题的图解法步骤提供实际例子进行图解法的应用演示2.3 线性规划的代数法介绍线性规划的代数法解题步骤使用具体例子进行代数法的应用解释2.4 线性规划的应用案例提供实际案例，展示线性规划在企业决策、资源分配等方面的应用强调线性规划在解决实际问题中的重要性第三章：整数规划3.1 整数规划的基本概念解释整数规划与线性规划的区别引入整数规划的目标函数和约束条件3.2 整数规划的解法介绍整数规划常用的解法，如分支定界法、动态规划法等使用具体例子进行整数规划解法的应用解释3.3 整数规划的应用案例提供实际案例，展示整数规划在人员排班、物流配送等方面的应用强调整数规划在解决实际问题中的重要性3.4 整数规划与线性规划的比较对比整数规划与线性规划的解法和技术强调整数规划在处理离散决策问题时的优势第四章：动态规划4.1 动态规划的基本概念解释动态规划的定义和特点引入动态规划的基本原理和基本定理4.2 动态规划的解法步骤演示动态规划的解题步骤，如最优子结构、状态转移方程等使用具体例子进行动态规划解法的应用解释4.3 动态规划的应用案例提供实际案例，展示动态规划在库存管理、项目管理等方面的应用强调动态规划在解决多阶段决策问题中的重要性4.4 动态规划与其他运筹学方法的比较对比动态规划与其他运筹学方法的特点和适用场景强调动态规划在处理具有时间序列特征的问题时的优势第五章：决策分析5.1 决策分析的基本概念解释决策分析的目的和意义引入决策问题的基本要素和决策方法5.2 确定型决策分析介绍确定型决策分析的方法和步骤使用具体例子进行确定型决策分析的应用解释5.3 不确定型决策分析介绍不确定型决策分析的方法和步骤使用具体例子进行不确定型决策分析的应用解释5.4 风险型决策分析介绍风险型决策分析的方法和步骤使用具体例子进行风险型决策分析的应用解释5.5 决策分析的应用案例提供实际案例，展示决策分析在企业战略规划、新产品开发等方面的应用强调决策分析在解决实际问题中的重要性第六章：网络计划技术6.1 网络计划技术的基本概念解释网络计划技术的定义和作用引入节点、箭线、活动等基本元素6.2 常用网络计划技术介绍常用的网络计划技术，如PERT、CPM等演示这些网络计划技术的绘制和应用方法6.3 网络计划技术的应用案例提供实际案例，展示网络计划技术在项目管理和生产调度等方面的应用强调网络计划技术在时间管理和资源分配中的重要性6.4 网络计划技术的优化介绍网络计划技术的优化方法和步骤使用具体例子进行网络计划技术优化的应用解释第七章：排队论7.1 排队论的基本概念解释排队论的定义和研究对象引入队列、服务设施、顾客等基本元素7.2 排队论的模型构建介绍排队论的模型构建方法和步骤使用具体例子进行排队论模型的应用解释7.3 排队论的应用案例提供实际案例，展示排队论在服务业、制造业等方面的应用强调排队论在解决等待问题和提高服务水平中的重要性7.4 排队论的优化策略介绍排队论的优化策略和方法使用具体例子进行排队论优化策略的应用解释第八章：存储论8.1 存储论的基本概念解释存储论的定义和研究对象引入存储成本、缺货成本、需求量等基本元素8.2 存储论的模型构建介绍存储论的模型构建方法和步骤使用具体例子进行存储论模型的应用解释8.3 存储论的应用案例提供实际案例，展示存储论在库存管理、供应链等方面的应用强调存储论在解决存货控制和降低成本中的重要性8.4 存储论的优化策略介绍存储论的优化策略和方法使用具体例子进行存储论优化策略的应用解释第九章：对偶理论9.1 对偶理论的基本概念解释对偶理论的定义和意义引入对偶问题、对偶关系等基本元素9.2 对偶理论的解法介绍对偶理论的解法方法和步骤使用具体例子进行对偶理论的应用解释9.3 对偶理论的应用案例提供实际案例，展示对偶理论在优化问题和经济学中的应用强调对偶理论在解决实际问题中的重要性9.4 对偶理论与灵敏度分析解释对偶理论与灵敏度分析的关系介绍灵敏度分析的方法和步骤第十章：总结与展望10.1 管理运筹学的重要性和局限性总结管理运筹学在实际管理中的应用价值和局限性强调管理运筹学在解决问题和创新方面的潜力10.2 管理运筹学的发展趋势展望管理运筹学未来的发展趋势和研究方向提及新兴领域和技术在管理运筹学中的应用前景10.3 提高管理运筹学能力的建议给出提高管理运筹学能力的建议和指导鼓励学习者持续学习和实践，以提升解决实际问题的能力重点解析本文教案主要介绍了管理运筹学的十个重点内容，具体如下：1. 管理运筹学的定义、发展历程、方法与工具，以及应用领域。
运筹管理精编运筹学讲义文件编码（008-TTIG-UTITD-GKBTT-PUUTI-WYTUI-M B A运筹学讲义运筹学是一门应用科学，它广泛应用现代科学技术知识、用定量分析的方法，解决实际中提出的问题，为决策者选择最优决策提供定量依据。
运筹学的核心思想是建立在优化的基础上。
例如，在线性规划中体现为两方面：（1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成（2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多运筹学解决问题的主要方法是用数学模型描述现实中提出的决策问题，用数学方法对模型进行求解，并对解的结果进行分析，为决策提供科学依据。
随着计算机及计算技术的迅猛发展，目前对运筹学的数学模型的求解已有相应的软件。
因此，在实际求解计算时常可借助于软件在计算机上进行，这样可以节省大量的人力和时间。
第一部分线性规划内容框架LP问题基本概念数学模型可行解、最优解实际问题LP问题解的概念基本解、基可行解提出基本最优解基本方法图解法原始单纯形法单纯形法大M法人工变量法对偶单纯形法两阶段法对偶理论进一步讨论灵敏度分析──参数规划*在经济管理领域内应用运输问题（转运问题）特殊的LP问题整数规划多目标LP 问题*第一部分线性规划（Linear Programming）及其应用第一章 LP问题的数学模型与求解§1 LP问题及其数学模型（一）引例1（生产计划的问题）某工厂在计划期内要安排生产Ⅰ、Ⅱ的两种产品，已知生产单位产品所需的设备台时，A、B两种原材料的消耗以及每件产品可获的利润如下表所示。
问应如何安排计划使该工厂获利最多该问题可用一句话来描述，即在有限资源的条件下，求使利润最大的生产计划方案。
解：设x1,x2分别表示在计划期内生产产品Ⅰ、Ⅱ的产量。
由于资源的限制，所以有：机器设备的限制条件：x 1+2x 2≤8 原材料A 的限制条件： 4x 1≤16 （称为资源约束条件）原材料B 的限制条件： 4x 2≤12同时，产品Ⅰ、Ⅱ的产量不能是负数，所以有 x 1≥0，x 2≥0（称为变量的非负约束）显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有许许多多。
而工厂的目标是在不超过所有资源限量的条件下，如何确定产量x 1，x 2以得到最大的利润，即使目标函数Z=2x 1+3x 2的值达到最大。
综上所述，该生产计划安排问题可用以下数学模型表示： maxz=2x 1+3x 2引例2. （营养配餐问题）假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质和800毫克钙。
如果市场上只有四种食品可供选择，它们每千克所含热量和营养成份以及市场价格如下表所示。
问如何选择才能满足营养的前提下使购买食品的费用最小解:设x j (j=1,2,3,4)为第j 种食品每天的购买量，则配餐问题数学模型为minz=10x 16x 23x 32x 4（二）LP 问题的模型上述两例所提出的问题，可归结为在变量满足线性约束条件下，求使线性目标函数值最大或最小的问题。
它们具有共同的特征。
（1）每个问题都可用一组决策变量(x 1,x 2,…x n )表示某一方案，其具体的值就代表一个具体方案。
通常可根据决策变量所代表的事物特点，可对变量的取值加以约束，如非负约束。
（2）存在一组线性等式或不等式的约束条件。
（3）都有一个用决策变量的线性函数作为决策目标（即目标函数），按问题的不同，要求目标函数实现最大化或最小化。
满足以上三个条件的数学模型称为LP 的数学模型，其一般形式为：max(或min)z=c 1x 1+c 2x 2+…+c n x n⎢⎢⎢⎢⎢⎢⎣⎡≥⋅≥=≤+++≥=≤+++≥=≤+++0),(),(),(.2122212222222*********n m n mn m m n n n n x x x b x a x a x a bx a x a x a b x a x a x a ts或紧缩形式max(或min)z=∑=nj j j x c 1⎢⎢⎣⎡≥=≥=≤∑=0),,2,1(),(1j n j ij j x m i b x a或矩阵形式 max(或min)z=cx⎢⎣⎡≥≥=≤0),(X b AX或向量形式： max(或min)z=cx⎢⎢⎢⎣⎡=≥≥=≤∑=),,2,1(0),(1n j X b x p j nj j j其中C=(c 1,c 2,…,c n )，称为价值系数向量；⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎦⎤=mn m m nn a a a a a a a a a A ,,,,,,212222111211称为技术系数矩阵（并称消耗系数矩阵） =(p 1,p 2,…,p n )⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=m b b b b 21称资源限制向量X=(x 1,x 2,…,x n )T 称为决策变量向量。
（三）LP 问题的标准型1.为了讨论LP 问题解的概念和解的性质以及对LP 问题解法方便，必须把LP 问题的一般形式化为统一的标准型：maxz=∑=nj j j x c 1；⎢⎢⎣⎡=≥==∑=),,2,1(0),,2,1(1n j x m i b x a j nj ij j 或⎢⎣⎡≥=0X b AXmaxz=cxmaxz=cx或⎢⎢⎣⎡=≥=∑=),,2,1(01n j x b x p j nj j j 标准型的特点：①目标函数是最大化类型 ②约束条件均由等式组成 ③决策变量均为非负 ④b i (i=1,2,…,n) 2.化一般形式为标准型 ①minz?max(-z)=-cx②“?”?左边+松驰变量；“?”?左边－“松驰变量” ③变量x j ?0?-x j ?0变量x j 无限制?令x j =x j ?－xj? ④b i <0?等式两边同乘以(-1)。
3.模型隐含的假设①比例性假定：决策变量变化的改变量与引起目标函数的改变量成比例；决策变量变化的改变量与引起约束方程左端值的改变量成比例。
此假定意味着每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是一个常数。
②可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其它变量的。
③连续性假定：决策变量应取连续值。
④确定性假定：所有的参数(a ij ,b i ,c j )均为确定，所以LP 问题是确定型问题，不含随机因素。
以上4个假定均由于线性函数所致。
在现实生活中，完全满足这4个假定的例子并不多见，因此在使用LP 时必须注意问题在什么程度上满足这些假定。
若不满足的程度较大时，应考虑使用其它模型和方法。
如非线性规划，整数规划或不确定型分析方法。
对LP 标准型，我们还假定r(A)=m<n 。
（四）LP 问题的解的概念 设LP 问题maxz=∑=nj j j x c 1∑===n j ijjn i b x a 1),,2,1(),,2,1(0n j x j =≥1.从代数的角度看：可行解和最优解满足约束条件和的解X=(x1,x2,…,xn)T称为可行解。
所有可行解构成可行解集，即可行域}0,{≥==xbAXSx。
而使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最优值。
求解LP问题就是求其最优解和最优值，但从代数的角度去求是困难的。
2.从LP角度看：基：设A为mxn矩阵，r(A)=m，B是A中的mxm阶非奇异子矩阵（即|B|?0），则称B是LP问题的一个基。
若B是LP问题的一个基，则B由m个线性独立的列向量组成，即B=(Pr1,Pr2,…,Prm)，其中Prj=(a1rj,a2rj,…,amrj)T，(j=1,2,…,m)称为基向理。
与其向量Prj 相对应的变量xrj称为基变量，其它变量称为非基变量。
显然，对应于每个基总有m个基变量，n－m个非基变量。
基本解与基可行解设B是LP问题的一个基，令其n－m个非基变量均为零，所得方程的解称为该LP问题的一个基本解。
显然，基B与基本解是一一对应的，基本解的个数≤C mn。
在基本解中，称满足非负条件的基本解为基可行解，对应的基称为可行基。
退化解 如果基解中非零分量的个数小于m ，则称此基本解为退化的，否则是非退化的。
最优基 如果对应于基B 的基可行解是LP 问题的最优解，则称B 为LP 问题的最优基，相应的解又称基本最优解。
问题解之间的关系如图所示 ?（五）两个变量LP 问题的图解法问题解的几何表示。
以引例为例说明maxz=2x 1+3x 2按以下顺序进行：解：（1）画出直角坐标系；（2）依次做每条约束线，标出可行域的方向，并找出它们共同的可行域；（3）任取一目标函数值作一条目标函数线（称等值线），根据目标函数（最大或最小）类型，平移该直线即将离开可行域上，则与目标函数线接触的最终点即表示最优解。
①②③可行解基本基可行解x 2 ②3一条直线上的点具有相同的值。
解的几种情况：（1）此例有唯一解Q 2，即x 1=4,x 2=2,z=14（2）有无穷多最优解（多重解），若将目标函数改为z=2x 1+4x 2则线段Q 2，Q 3上的点均为最优解。
（3（41可行域与最优解间的关系：可行域最优解空集无最优解（无可行解）有界集唯一最优解多重解无界集无有限最优解（无界解）结论：（1）LP问题的可行域是凸集（凸多边形，凸多面体，…）；（2）LP问题最优解若存在，则必可在可行域的顶点上得到；（3）LP问题的可行域的顶点个数是有限的；（4）若LP问题有两个最优解，则其连线上的点都是最优解。
因此，求解LP问题可转化为如何在可行域的顶点上求出使目标函数值达到最优的点的问题。
2.基可行解的几何意义对例1 LP问题标准化为maxZ=2x1+3x2可求得所有的基本解：x(1)=(0,0,8,16,12)T(0点),x(2)=(4,0,4,0,12)T(Q1点)x(3)=(4,2,0,0,4)T(Q2点),x(4)=(2,3,0,8,0)T(Q3点)x(5)=(0,3,2,16,0)T(Q4点),x(6)=(4,3,-2,0,0)T(C点)x(7)=(8,0,0,-16,12)T(A点),x(8)=(0,4,0,16,-4)T(B点)但A、B、C三点是非可行域上的点，即非可行解。
因此，x(1)，x(2)，x(3)，x(4)，x(5)才是基可行解，它们与可行域的顶点相对应。
于是还有结论：（5）对于标准型的LP问题，X是基可行解的充要条件是X为可行域的顶点。
（6）LP问题可行域顶点的个数=基可行解的个数≤基的个数≤C mn3.图解法只适用于两个变量（最多含三个变量）的LP问题。
4.求解LP问题方法的思考：①完全枚举法，对m、n较大时，C mn是一个很大的数，几乎不可能；②从可行域的一个顶点（基可行解）迭代到另一个顶点（基可行解）。
§2 单纯形法与计算机求解 1.解LP 问题单纯形法的基本思路：y2.单纯形法的计算步骤（表格形式） （1）建立初始单纯形表，假定B=I ，b ≥0 设maxZ=c 1x 1+c 2x 2+…+c n x n将目标函数改写为：-Z+c 1x 1+c 2x 2+…+c n x n =0把上述方程组和目标函数方程构成n+1个变量，m+1个方程的方程组，并写成增广矩阵的形式：-Z x 1 x 2 … x m x m+1 … x nb0 1 0 … 0 a 1m+1 … a 1n b 1 0 0 1 … 0 a 2m+1 … a 2n b 20 0…1a mm+1 …a mnb m-1 c 1 c 2 … c m c m+1 … c n以非基变量表示基变量形式∑=-=nj j ij i i x a b x 1代入Z 中的基变量,有令∑∑====mi mi j i i j i i a c Z b c Z 110,于是∑+=-+=nm j j j jo x c ZZ Z 1)(因此，上述的增广矩阵就可写成：Z x 1 x 2 … x m x m+1… x nb0 1 0 … 0 a 1m+1 … a 1n b 10 0 1 … 0 a 2m+1 …a 2nb 20 0 0 (1)a mm+1 …a mnb m1 0 0 …111+=+-∑m mi im i c a c …∑=mi in i a c 1－c n∑=mi i i b c 1再令∑=-=-=mi ij i j j j j a c c Z c 1σ则上述增广矩阵可写成下面表格形式：即初始单纯形表T （B ）上述初始单纯形表可确定初始可行基和初始基可行解： B=(P 1,P 2,…,P m )=I, x=(b 1,b 2,…,b m , 0……0)T 从初始单纯形表建立的过程可以看到以下事实：（1）凡LP 模型中约束条件为“≤”型，在化为标准型后必有B=I ，如果b ≥0，则模型中约束方程的各数据不改变符号照抄在表中相应的位置。
