物流管理运筹学教案.

运筹于帷幄之中，决胜于千里之外运筹学A1交通运输与物流学院冯勋省[e-mail]绪论历史，性质，应用运筹学的工作步骤运筹学在解决大量实际问题的过程中形成了自己的工作步骤。（1）提出和形成问题。即弄清问题的目标，可能的约束，问题的可控变量以及有关参数，搜集有关资料;（2）建立模型。即把问题中可控变量，参数和目标与约束之间的关系用一定的模型表示出来;（3）求解。用各种手段（主要是数学方法，也可用其他方法）将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要可由求决策者提出；绪论历史，性质，应用运筹学的工作步骤（4）解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题；（5）解的控制。通过控制解的变化过程决定是否要作一定的改变；（6）解的实施。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清解的用法，在实施中可能产生的问题和修改。绪论历史，性质，应用运筹学的模型运筹学在解决问题时，按研究对象不同可构造各种不同的模型。模型是研究者对客观现实经过思维抽象后用文字、图表、符号、关系以及实体模样描述所认识到的客观对象。模型的有关参数和关系式是较容易改变的，这样是有助于问题的分析和研究。利用模型可以进行一定预测、灵敏度分析等。模型的三种基本形式：（1）形象模型，（2）模拟模型，（3）符号或数学模型。构造模型是一种创造性劳动，成功的模型往往是科学和艺术的结晶，构造模型的方法和思路通常有以下几种：绪论历史，性质，应用直接分析法按研究者对问题内在机理的认识直接构造出模型。运筹学中已有不少现存的模型，如线性规划模型、投入产出模型、排队模型、存储模型、决策和对策模型等等。这些模型都有很好的求解方法及求解软件，但用这些现成的模型研究问题时，应注意不能生搬硬套。类比法有些问题可以用不同方法构造出模型；而这些模型的结构性质是类同的，这就可以互相类比。如物理学中的机械系统、气体动力学系统、水力学系统、热力学系统及电路系统之间就有不少彼此类同的现象。甚至有些经济、社会系统也可以用物理系统来类比。在分析有些经济、社会问题时，不同国家之间也可以找出某些类比的现象。绪论历史，性质，应用数据分析法对有些问题的机理尚未了解清楚，若能搜集到与此问题密切有关的大量数据，或通过某些试验获得大量数据，这就可以用统计分析法建摸。试验分析法有些问题的机理不清，又不能作大量试验来获得数据，这时只能通过做局部试验的数据加上分析来构造模型。想定（构想）法当有些问题的机理不清，又缺少数据，又不能作试验来获得数据时，例如有些社会、经济、军事问题，人们只能在已有的知识、经验和某些研究的基础上，对于将来可能发生的情况给出逻辑上合理的设想和描述。然后用已有的方法构造模型，并不断修正完善，直至比较满意为止。绪论历史，性质，应用运筹学的主要应用二次大战后运筹学的应用迅速转向了民用，下面对某些重要领域给于简述。1、市场销售------广告预算和媒介选择、竞争性定价、新品开发、销售计划的制订。（美）杜邦公司在五十年代起就非常重视将运筹学用于如何做好广告工作、产品定价、新品引入。2、生产计划------从总体确定生产、存储和劳动力的配合等计划适应波动的需求计划。巴基斯坦一重型制造厂用线性规划安排生产计划，节省10%的生产费用。3、运输问题------涉及空运、水运、公路、铁路运输、管道运输等。公路网的设计和分析，市内公共汽车路线的选择和行车时刻表的安排，出租车的调度等。绪论历史，性质，应用4、人事管理------需求估计，教育和培训，人员分配（各种指派问题），合理利用，人才评价等。5、设备维修，更新和可靠性等。6、计算机和信息系统------内存分配研究，网络设计分析等。7、城市管理------紧急服务系统的设计和运用，区域布局规划，管道网络设计等。（美）曾用排队论确定纽约市紧急电话站的值班人数，（加）设计城市警车配置和负责范围、指挥接警后的行走路线等。8、对策研究------价格竞争，中央与地方政府投资分配博弈，工会与雇主间的博弈。第一部分线性规划及单纯形法线性规划LinearProgramming（LP）引言解决有限资源在有竞争的使用方向中如何进行最佳分配。线性规划是运筹学的一个重要分支，也是运筹学中应用最广泛的方法之一。自1947年旦茨基（G.B.Dantzig）提出了一般线性规划问题求解的方法——单纯形法（simplexmethod）之后，线性规划已被广泛应用于解决经济管理和工业生产中遇到的实际问题。调查表明，在世界500家最大的企业中，有85%的企业都曾使用过线性规划解决经营管理中遇到的复杂问题。线性规划的使用为应用者节约了数以亿万计的资金。线性规划LinearProgramming（LP）本章中我们将讨论什么是线性规划问题，线性规划问题的数学表示，基本理论、概念和求解方法。线性规划问题是什么样的一类问题呢？请看案例------线性规划LinearProgramming（LP）线性规划LinearProgramming（LP）产品车间可用工时市场限制甲乙在A加工时数216114108无≤7在B加工时数单位产品利润引例：有甲、乙两种产品，都要在车间A和车间B加工，资料如下：问：如何组织生产才能使利润最大？建立数学模型，即将问题用数学语言描述，利用初等代数列出解应用题的方程式或方程组，就是建立简单数学模型的过程。第一步：确定决策变量在复杂的线性规划问题中是成功建立数学模型的关键。第一步：确定决策变量很容易设定：X1=产品甲的产量，X2=产品乙的产量。建立线性规划问题数学模型步骤：针对引例一建立数学模型：线性规划LinearProgramming（LP）线性规划LinearProgramming（LP）第二步：确定目标函数就是将所要追求的目标列成函数形式。第三步：确定约束条件方程将限制条件列成代数方程式既是约束条件方程；另外，决策变量为正数也为约束条件。第二步：确定目标函数很容易知道利润为：Z=6X1+4X2但要求解利润最大，所以写成：MAXZ=6X1+4X2第三步：确定约束条件方程2X1+X2≤10X1+X2≤8X2≤7Xj≥0，对一切j线性规划LinearProgramming（LP）基本概念通常建立LP模型有以下几个步骤：1.确定决策变量：决策变量是模型要确定的未知变量，也是模型最重要的参数，是决策者解决实际问题的控制变量。2.确定目标函数：目标函数决定线性规划问题的优化方向，是模型的重要组成部分。实际问题的目标可表示为决策变量的一个线性函数，并根据实际问题的优化方向求其最大化（max）或最小化（min）。3.确定约束方程：一个正确的线性规划模型应能通过约束方程来描述和反映一系列客观条件或环境的限制，这些限制通过一系列线性等式或不等式方程组来描述。4.变量取值限制：一般情况下，决策变量取正值（非负值）。因此，模型中应有变量的非负约束即Xj≥0，但也存在例外。线性规划LinearProgramming（LP）基本概念线性规划的一般形式:max（或min）z=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn（≤=≥）b1a21x1+a22x2+…+a2nxn（≤=≥）b2s.t.………………am1x1+am2x2+…+amnxn（≤=≥）bmxj≥0（j=1，2…n）线性规划LinearProgramming（LP）基本概念线性规划问题的标准形式1、目标函数极大化——“max”2、等式约束条件——“=”3、变量非负——“xj≥0”maxz=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2s.t.……………am1x1+am2x2+…+amnxn=bmxj≥0（j=1，2…n）线性规划LinearProgramming（LP）基本概念化标准形式的一般步骤1、目标函数极小化“极大化”2、约束条件的右端项bi≤0“bi≥0”3、约束条件为不等式≤或≥“=”4、取值无约束（自由）变量“非负变量”5、取值非正变量“非负变量”线性规划LinearProgramming（LP）基本概念线性规划问题的求解解：（图解）如何求解一般的线性规划呢？下面我们分析一下简单的情况——只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。线性规划LinearProgramming（LP）基本概念例1maxz=2x1+x25x2≤15s.t.6x1+2x2≤24x1+x2≤5x1，x2≥0线性规划LinearProgramming（LP）基本概念maxz=2x1+x25x2≤15s.t.6x1+2x2≤24x1+x2≤5x1，x2≥0线性规划LinearProgramming（LP）基本概念例maxZ=2X1+X2X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0线性规划LinearProgramming（LP）基本概念maxZ=2X1+X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)4=2X1+X220=2X1+X217.2=2X1+X211=2X1+X2Lo：0=2X1+X2（7.6，2）DmaxZminZ此点是唯一最优解，且最优目标函数值maxZ=17.2可行域线性规划LinearProgramming（LP）基本概念maxZ=3X1+5.7X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)（7.6，2）DL0：0=3X1+5.7X2maxZminZ（3.8，4）34.2=3X1+5.7X2绿色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值maxZ=34.2是唯一的。可行域线性规划LinearProgramming（LP）基本概念minZ=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)DL0：0=5X1+4X2maxZminZ8=5X1+4X243=5X1+4X2（0，2）可行域此点是唯一最优解线性规划LinearProgramming（LP）基本概念图解法的启示1.线性规划问题解的可能情况a.唯一最优解b.无穷多最优解c.无可行解d.没有有界最优解(无界解)2.若线性规划问题的可行域非空，则可行域是一个凸集；3.若线性规划问题的最优解存在，则一定可以在可行域的凸集的某个顶点上达到。线性规划LinearProgramming（LP）单纯形法单纯形方法是G.B.Danzig于1947年首先发明的。近50年来，一直是求解线性规划的最有效的方法之一，被广泛应用于各种线性规划问题的求解。本节讨论单纯形法的基本概念、原理及算法。线性规划LinearProgramming（LP）单纯形法给定线性规划问题（标准形式）maxz=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2s.t.……………am1x1+am2x2+…+amnxn=bmxj≥0（j=1，2…n）线性规划LinearProgramming（LP）单纯形法一、线性规划问题的解的概念可行解最优解基基解（基本解）基可行解可行基线性规划LinearProgramming（LP）单纯形法二、凸集及其顶点凸集顶点（极点）凸集凹集线性规划LinearProgramming（LP）12345678线性规划LinearProgramming（LP）单纯形法三、线性规划基本定理基本定理1线性规划所有可行解组成的集合S