《管理运筹学》复习提纲.doc

1、管理运筹学复习提纲第一章 绪论（P1-P9)1.决策过程（解决问题的过程）（1）认清问题。（2）找出一些可供选择的方案。（3）确定目标或评估方案的标准。（4）评估各个方案：解的检验、灵敏性分析等。（5）选出一个最优的方案：决策。（6）执行此方案：回到实践中。（7）进行后评估：考察问题是否得到圆满解决。其中：（1）（2）（3）形成问题。（4）（5）分析问题：定性分析与定量分析，构成决策2. 运筹学的分支：线性规划、整数线性规划、动态规划、图与网络模型、存储论、排队论、排序与统筹方法、决策分析、对策论、预测、目标规划，此外，还有多目标规划、随机规划、模糊规划等。3. 运筹学在工商管理中的应用1）生

2、产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等，追求利润最大化和成本最小化。2）库存管理：多种物资库存量的管理，某些设备的库存方式、库存量等的确定。3）运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等。4）人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等。5）市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等。6）财务和会计：预测、贷款、成本分析、定价、证券管理、现金管理等。此外，还有设备维修、更新，项目选择、评价，工程优化设计与管理等。3. 学习管理运筹学必须使用相应的计算机软件，必须注重学以致

3、用的原则。第二章 线性规划的图解法(P10-P26)1.一些典型的线性规划在管理上的应用合理利用线材问题：如何在保证生产的条件下，下料最少；配料问题：在原料供应量的限制下如何获取最大利润；投资问题：从投资项目中选取方案，使投资回报最大；产品生产计划：合理利用人力、物力、财力等，使获利最大；劳动力安排：用最少的劳动力来满足工作的需要；运输问题：如何制定调运方案，使总运费最小。2.线性规划的组成目标函数：max f 或 min f ；约束条件：s.t. (subject to)，满足于；决策变量：用符号来表示可控制的因素。3.建模过程（1）理解要解决的问题，明确在什么条件下，要追求什么目标。（2）

4、定义决策变量（x1 ，x2 ，xn），每一组值表示一个方案。（3）用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标。（4）用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件。一般形式目标函数：max（min）z = c1 x1 + c2 x2 + + cn xn约束条件：s.t. a11 x1 + a12 x2 + + a1n xn （=, ）b1a21 x1 + a22 x2 + + a2n xn （=, ）b2am1 x1 + am2 x2 + + amn xn （=, ）bmx1 ，x2 ， ，xn 0对于只包含两个决策变量的线性规划问题，可以在平面直角坐标系上

5、作图表示线性规划问题的有关概念，并求解。下面通过例 1 详细介绍图解法的解题过程取各约束条件的公共部分（如图 2-1（f）所示）。目标函数 z = 50x1 + 100x2，当 z 取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到 B 点时，z 在可行域内实现了最大化。A、B、C、D、E是可行域的顶点，有限个约束条件其可行域的顶点也是有限的。线性规划的标准化内容之一引入松弛变量（资源的剩余量）例 1 中引入 s1，s2，s3，模型变化为：4.重要结论如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；无穷多个最优解。若将例

6、1 中的目标函数变为 max z=50x1+50x2，则线段 BC 上的所有点都代表了最优解；无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；无可行解。若在例 1 的数学模型中再增加一个约束条件 4x1+3x21200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。5.线性规划的标准化6.线性规划的标准形式有四个特点：目标最大化；约束为等式；决策变量均非负；右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过变换，将其转化为标准形式。7.为了使约束由不等式成为等式而引进的变量 s，当不等式为“小于等

7、于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量或剩余变量。8.9.灵敏度分析：在建立数学模型和求得最优解之后，研究线性规划的一个或多个参数（系数）ci , aij , bj 变化时，对最优解产生的影响。一、目标函数中的系数 ci 的灵敏度分析二、约束条件中常数项 bj 的灵敏度分析当约束条件中常数项 bj 变化时，线性规划的可行域发生变化，可能引起最优解的变化。A.考虑例 1 的情况：假设设备台时增加 10 个台时，即 b1 变化为 310，这时可行域扩大，最优解为 x2 = 250 和

8、 x1 + x2 = 310 的交点 x1 = 60，x2 = 250。变化后的总利润 变化前的总利润 = 增加的利润(50 60+ 100 250) (50 50+100 250) = 500，500 / 10 = 50（元）说明在一定范围内每增加（或减少）1 个台时的设备能力就可增加（或减少）50 元利润，这称为该约束条件的对偶价格。B.假设原料 A 增加 10 千克，即 b2 变化为 410，这时可行域扩大，但最优解仍为 x2 = 250 和 x1 + x2 = 300 的交点 x1 = 50，x2 = 250。此变化对总利润无影响，该约束条件的对偶价格为 0。解释：原最优解没有把原料

9、A 用尽，有 50 千克的剩余，因此增加 10千克只增加了库存，而不会增加利润。在一定范围内，当约束条件中常数项增加 1 个单位时，（1）若约束条件的对偶价格大于 0，则其最优目标函数值得到改善（变好）；（2）若约束条件的对偶价格小于 0，则其最优目标函数值受到影响（变坏）；（3）若约束条件的对偶价格等于 0，则其最优目标函数值不变。课本重点习题：P23-26 习题1 2 6 8第三章 线性规划问题的计算机求解(P27-P38)1. 随书软件为“管理运筹学”2.5 版（Windows 版），是“管理运筹学”2.0 版（Windows 版）的升级版。它包括：线性规划、运输2. 问题、整数规划（0

10、-1 整数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法，共 15 个子模块。3. “管理运筹学”软件的输出信息分析当有多个系数变化时，需要进一步讨论。百分之一百法则：对于所有变化的目标函数决策系数（约束条件右端常数值），当其所有允许增加的百分比与允许减少的百分比之和不超过100%时，最优解不变（对偶价格不变，最优解仍是原来几个线性方程的解）。在使用百分之一百法则进行灵敏度分析时，要注意以下几方面。（1）当允许增加量（允许减少量）为无穷大时，则对任意增加量（减少量），其允许增加（减少）

11、百分比均看作零。（2）百分之一百法则是充分条件，但非必要条件；也就是说超过 100%，最优解或对偶价格并不一定变化。（3）百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变化的情况。这种情况下，只能重新求解。在松弛/剩余变量栏中，约束条件 2 的值为 125，它表示对原料 A 的最低需求，即对 A 的剩余变量值为 125；同理可知约束条件 1 的剩余变量值为 0；约束条件 3 的松弛变量值为 0。在对偶价格栏中，约束条件 3 的对偶价格为 1 万元，也就是说如果把加工时数从 600 小时增加到 601 小时，则总成本将得到改进，由 800万元减少到 799 万元。也可知约束条

12、件 1 的对偶条件为-4 万元，也就是说如果把购进原料 A 和 B 的总量下限从 350t 增加到 351t，那么总成本将增加，由 800 万元增加到 804 万元。当然如果减少对原料 A和 B 的总量的下限，那么总成本将得到改进。在常数项范围一栏中，知道当约束条件 1 的常数项在 300 到 475 范围内变化，且其他约束条件不变时，约束条件 1 的对偶价格不变，仍为-4；当约束条件 2 的常数项在负无穷到 250 范围内变化，且其他约束条件的常数项不变时，约束条件 2 的对偶价格不变，仍为 0；当约束条件 3 的常数项在 475 到 700 范围内变化，且其他约束条件的常数项不变时，约束条

13、件 3 的对偶价格不变，仍为 1。3.注意（1）当约束条件中的常数项增加一个单位时，最优目标函数值增加的数量称为影子价格。在求目标函数最大值时，当约束条件中的常数项增加一个单位时，目标函数值增加的数量就为改进的数量，此时影子价格等于对偶价格；在求目标函数最小值时，改进的数量就是减少的数量，此时影子价格即为负的对偶价格。（2） 管理运筹学”软件可以解决含有 100 个变量 50 个约束方程的线性规划问题，可以解决工商管理中大量的问题。如果想要解决更大的线性规划问题，可以使用由芝加哥大学的 L.E.Schrage 开发的 LINDO 计算机软件包的微型计算机版本 LINDO/PC。课本重点习题：P

14、34-38 习题1 2 3 4第四章 线性规划在工商管理中的应用(P39-P66)包括：人力资源分配的问题 生产计划的问题 套裁下料问题 配料问题 投资问题1人力资源分配问题例 1某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如表 4-1 所示。设司机和乘务人员分别在各时间段一开始时上班，并连续工作 8h，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又使配备最少司机和乘务人员的人数最少？例 2一家中型的百货商场对售货员的需求经过统计分析如表 4-2 所示。为了保证售货员充分休息，要求售货员每周工作五天，休息两天，并要求休息的两天是连续的。问应该如何安排售货员的休息日期，既满足

15、工作需要，又使配备的售货员的人数最少？2 生产计划的问题例 3某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，这三种产品都需要经过铸造、机加工和装配三道工序。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表 4-3 所示。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和外包协作各应多少件？解：设 x1，x2，x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5 分别为由外包协作铸造再由本公司进行机械加工和装配的甲、乙两种产品的件数。每件产品的利润如下：可得到

16、 xi （i = 1,2,3,4,5）的利润分别为 15 元、10 元、7 元、13 元、9 元。*该公司的最大利润为 29 400 元*最优的生产计划为全部由自己生产的产品甲 1 600 件，铸造工序外包而其余工序自行生产的产品乙 600 件。例 4永久机械厂生产、三种产品，均要经过 A、B 两道工序加工。设有两种规格的设备 A1、A2 能完成 A 工序；有三种规格的设备 B1、B2、B3 能完成 B 工序。产品可在 A、B 的任何规格的设备上加工；产品可在工序 A 的任何一种规格的设备上加工，但对 B 工序，只能在 B1 设备上加工；产品只能在 A2 与 B2 设备上加工。数据如表 4-4

17、 所示。问：为使该厂获得最大利润，应如何制定产品加工方案？解：设 xijk 表示第 i 种产品，在第 j 种工序上的第 k 种设备上加工的数量。建立如下的数学模型。目标函数为计算利润最大化，利润的计算公式为：利润 = （销售单价 原料单价） 产品件数之和 （每台时的设备费用 设备实际使用的总台时数）之和。这样得到目标函数：max (1.250.25) (x111+x112) + (20.35) (x211+x212) + (2.800.5) x312 300/6 000(5x111+10x211) -321/10 000 (7x112+9x212+12x312)-250/4 000(6x121

18、+8x221)-783/7 000(4x122+11x322)-200/4 000(7x123).经整理可得：max0.75x111+0.775 3x112+1.15x211+1.361 1x212+1.914 8x312-0.375x121-0.5x221-0.447 4x122-1.230 4x322-0.35x123*该厂的最大利润为 1 146.600 5 元。4 套裁下料问 题例 5.某工厂要做 100 套钢架，每套用长为 2.9 m，2.1 m，1.5 m 的圆钢各一根。已知原料每根长 7.4 m，问：应如何下料，可使所用原料最省？解：共可设计下列 8 种下料方案，如表 4-5 所

19、示。设 x1, x2, x3, x4, x5, x6 , x7 , x8 分别为上面 8 种方案下料的原材料根数。这样我们建立如下的数学模型。用管理运筹学软件计算得出最优下料方案：按方案 1 下料 30 根；按方案 2 下料 10 根；按方案 4 下料 50 根。即：x1=30; x2=10； x3=0；x4=50； x5=0；x6= x7= x8=0只需 90 根原材料就可制造出 100 套钢架。注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。若可能的下料方案

20、太多，可以先设计出较好的几个下料方案。首先要求每个方案下料后的料头较短；其次方案总体能裁下所有各种规格的圆钢，且不同方案有着不同的各种所需圆钢的比。这样套裁即使不是最优解，也是次优解，也能满足要求并达到省料目的。如我们用前 5 种下料方案供套裁用，进行建模求解，也可得到上述最优解。5 配 料 问 题例 6某工厂要用三种原料1、2、3 混合调配出三种不同规格的产品甲、乙、丙，数据如表4-6 和表 4-7 所示。问：该厂应如何安排生产，使利润最大？解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学模型时，要考虑：对于甲：x11，x12，x13；对于乙：x21，x2

21、2，x23；对于丙：x31，x32，x33；对于原料 1：x11，x21，x31；对于原料 2：x12，x22，x32；对于原料 3：x13，x23，x33；目标函数：利润最大，利润 = 收入 原料支出约束条件：规格要求 4 个；供应量限制 3 个。利润=总收入-总成本=甲、乙、丙三种产品的销售单价 产品数量甲、乙、丙使用的原料单价 原料数量。故有：目标函数：约束条件：从表 4-6 中可知x110.5（x11+x12+x13）x120.25（x11+x12+x13）x210.25（x21+x22+x23）x220.5（x21+x22+x23）从表 4-7 中可知，生产甲、乙、丙的原材料不能超过

22、原材料的供应限额，故有x11+x21+x31100x12+x22+x32100x13+x23+x3360通过整理，得到以下模型：目标函数：max z = -15x11+25x12+15x13-30x21+10x22-40x31-10x33约束条件：线性规划的计算机解为 x11 = 100，x12 = 50，x13 = 50，其余的 xij = 0，也就是说每天只生产产品甲 200 kg，分别需要用第 1 种原料 100 kg，第 2 种原料 50 kg，第 3 种原料 50 kg。6 投 资 问 题例 9 某部门现有资金 200 万元，今后五年内考虑给以下的项目投资。项目 A：从第一年到第五年

23、每年年初都可投资，当年末能收回本利 110%；项目 B：从第一年到第四年每年年初都可投资，次年末能收回本利 125%，但规定每年最大投资额不能超过 30 万元；项目 C：第三年年初需要投资，第五年末能收回本利 140%，但规定最大投资额不能超过 80 万元；项目 D：第二年年初需要投资，第五年末能收回本利 155%，但规定最大投资额不能超过 100 万元。据测定每次投资 1 万元的风险指数如右表 4-10 所示：问：（1）应如何确定这些项目每年的投资额，使得第五年年末拥有资金的本利金额最大？ （2）应如何确定这些项目每年的投资额，使得第五年年末拥有资金的本利在 330万元的基础上总的风险系数最

24、小？ 所设变量与问题相同，目标函数为风险最小，有min f =x11+x21+x31+x41+x51+3(x12+x22+x32+x42)+4x33+5.5x24在问题的约束条件中加上“第五年末拥有资金本利在 330 万元”的条件，于是模型如下。min f = (x11+x21+x31+x41+x51) +3 (x12+x22+x32+x42) +4x33+5.5x24s. t. x11+ x12 = 200x21 + x22+ x24 = 1.1x11；x31 + x32+ x33 = 1.1x21+ 1.25x12；x41 + x42 = 1.1x31+ 1.25x22；x51 = 1.1

25、x41+ 1.25x32；xi2 30 ( i =1，2，3，4 )，x33 80，x24 1001.1x51 + 1.25x42+ 1.4x33+ 1.55x24330xij 0（i= 1，2，3，4，5；j = 1、2、3、4）运用“管理运筹学”软件求得此问题的解为：x5A=33.5，x4B=30，x3C=80，x2D=100，x1A=170，x1B=30，x2A=57，x2B=30，x3A=0，x3B=20.2，x4A=7.5。课本重点习题：P57-61 习题1 3 4 5 6第七章 运输问题(P126-P162)1 运 输 模 型例 1. 某公司从两个产地 A1、A2 将物品运往三个销

26、地 B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如表 7-1 所示，问：应如何调运可使总运输费用最小？一般运输问题的线性规划模型：产销平衡A1、A2、Am 表示某物资的 m 个产地；B1、B2、Bn 表示某物质的 n 个销地；si 表示产地Ai 的产量；dj 表示销地 Bj 的销量；cij 表示把物资从产地 Ai 运往销地 Bj 的单位运价。设 xij 为从产地 Ai 运往销地 Bj 的运输量，得到下列一般运输量问题的模型：变化：（1）有时目标函数求最大。如求利润最大或营业额最大等。（2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约

27、束)。（3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。2 运输问题的计算机求解例 2. 某公司从两个产地 A1、A2 将物品运往三个销地 B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表 7-3 所示，问：应如何调运可使总运输费用最小？解：增加一个虚设的销地运输费用为 0。例 3. 某公司从两个产地 A1、A2 将物品运往三个销地 B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表 7-5 所示，问：应如何调运可使总运输费用最小？解：增加一个虚设的产地运输费用为 0。3 运输问题的应用4 运输问题的表上作业法

28、1、数学模型在物流调运问题中，如何根据已有的交通网，制定调运方案，将货物运到各需求地，而使总运费最小，是很关键的问题。这类问题可用如下数学语言描述。已知有m个生产地点Ai（i=1，2m），可供应某种物质，其供应量分别为：ai（i=1，2，3，m），有n个销地（需要地）Bj（j=1，2n），其需求量分别为bj（j=1，2，n），从Ai到Bj运输单位物资的运价为Cij。这些数据可汇总于产销平衡表和单位运价表中，如表7-1、表7-2所示。表7-1 产销平衡表 销地产地1，2n产量1a12a2mam销量b1，b2bn表7-2 单位运价表 销地产地12n1C11C12C1n2C21C22C2nmCm1Cm2Cmn为了制定使总运费最小的调运方案，我们可以建立数学模型。如果我们设Xij表示由产地Ai供应给销地的运量，则运输问题的线性规划模型可分为三种情况：（1） 产销平衡，即在的情况下，求（总费用最少）。满足约束条件： 1，2，n）（满足各销地的需要量） 1，2，m）（各产地的发出量等于各地产量） Xij0（i=1，2，m；j=1，2，n）（调出量不能为负数）（2）产大于销，即在的情况下，求（总费用最少）。满足约束条件： 1，2，n） ai（i=1，2，m） Xij0（i=1，2，m；j=1，2，n）（3）销大于产，即在的情况下，求（总费用最少）。满足约束条件：bj（j=1，2，n） =a