管理运筹学复习提纲

1、 管理运筹学复习提纲第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 + +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.重要结论如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；无穷多个最优解。若将例 1 中的目标

6、函数变为 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 和 x1 + x

8、2 = 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。此变化对总利润无影响，该约束条件的对偶

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

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

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

12、减少到 799 万元。也可知约束条件 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。

14、课本重点习题：P34-38 习题1 2 3 4第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 与

17、 B2 设备上加工。数据如表 4-4 所示。问：为使该厂获得最大利润，应如何制定产品加工方案？解：设 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 (7x11

18、2+9x212+12x312)-250/4 000(6x121+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，问：应如何

19、下料，可使所用原料最省？解：共可设计下列 8 种下料方案，如表 4-5 所示。设 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 的含量。这样我

21、们建立数学模型时，要考虑：对于甲：x11，x12，x13；对于乙：x21，x22，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+

22、x22+x23）x220.5（x21+x22+x23）从表 4-7 中可知，生产甲、乙、丙的原材料不能超过原材料的供应限额，故有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。

23、7;6 投 资 问 题例 9 某部门现有资金 200 万元，今后五年考虑给以下的项目投资。项目 A：从第一年到第五年每年年初都可投资，当年末能收回本利 110%；项目 B：从第一年到第四年每年年初都可投资，次年末能收回本利 125%，但规定每年最大投资额不能超过 30 万元；项目 C：第三年年初需要投资，第五年末能收回本利 140%，但规定最大投资额不能超过 80 万元；项目 D：第二年年初需要投资，第五年末能收回本利 155%，但规定最大投资额不能超过 100 万元。据测定每次投资 1 万元的风险指数如右表 4-10 所示：问：（1）应如何确定这些项目每年的投资额，使得第五年年末拥有资金的本

24、利金额最大？（2）应如何确定这些项目每年的投资额，使得第五年年末拥有资金的本利在 330万元的基础上总的风险系数最小？ 所设变量与问题相同，目标函数为风险最小，有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+ x3

25、3 = 1.1x21+ 1.25x12；x41 + x42 = 1.1x31+ 1.25x22；x51 = 1.1x41+ 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

26、6第七章 运输问题(P126-P162)§1 运 输 模 型例 1. 某公司从两个产地 A1、A2 将物品运往三个销地 B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如表 7-1 所示，问：应如何调运可使总运输费用最小？一般运输问题的线性规划模型：产销平衡A1、A2、Am 表示某物资的 m 个产地；B1、B2、Bn 表示某物质的 n 个销地；si 表示产地Ai 的产量；dj 表示销地 Bj 的销量；cij 表示把物资从产地 Ai 运往销地 Bj 的单位运价。设 xij 为从产地 Ai 运往销地 Bj 的运输量，得到下列一般运输量问题的模型：变化：（1）

27、有时目标函数求最大。如求利润最大或营业额最大等。（2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束)。（3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。§2运输问题的计算机求解例 2. 某公司从两个产地 A1、A2 将物品运往三个销地 B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表 7-3 所示，问：应如何调运可使总运输费用最小？解：增加一个虚设的销地运输费用为 0。例 3. 某公司从两个产地 A1、A2 将物品运往三个销地 B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运

28、费如表 7-5 所示，问：应如何调运可使总运输费用最小？解：增加一个虚设的产地运输费用为 0。§3 运输问题的应用§4 运输问题的表上作业法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

29、-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=

30、1，2，m） Xij0（i=1，2，m；j=1，2，n）（3）销大于产，即在的情况下，求（总费用最少）。满足约束条件：bj（j=1，2，n）=ai（i=1，2，m） Xij0（i=1，2，m；j=1，2，n）物资调运问题可采用图上作业法或表上作业法求其最佳的调运方案。2、物资调运问题的表上作业法物资调运的表上作业法，是指在物资调运平衡表上确定物资调运最优方案的一种调运方法。利用表上作业法，寻求运费最少的运输方案，其步骤可归纳如下：（1）列出运输物资平衡表及运价表；（2）在表上做出初始方案；（3）检查初始方案是否为最优方案；（4）调整初始方案得到最优解。一般说来，每调整一次得到一个新的方案，而这

31、个新方案的运费比前一个方案要少一些，如此经过几次调整，最后可以得到最优方案。下面举例说明：某公司有三个储存某种物资的仓库，供应四个工地的需要。三个仓库的供应量和四个工地的需求量以及由各仓库到各工地调运单位物资的运价（元/吨），如表7-3 所示，试求运输费用最少的合理运输方案。表7-3 供需情况和单位运价 工地运价 （元/吨）仓库B1B2B3B4供应量（t）A1311310700A21928400A374105900需求量3006005006002000求解步骤如下：（1）列出调运物资平衡表7-4和运价表7-5 表7-4 物资平衡表 需供B1B2B3B4供应量（t）A1700A2400

32、A3900需求量（t）3006005006002000表7-5 运价表 工地运价仓库B1B2B3B4A1311310A21928A374105平衡表和运价表是表上作业法的基本资料和运算的依据。表上作业法的实质就是利用运价表在平衡表上进行求解。为了叙述和考虑问题的方便，通常把上面的平衡表看作为矩阵，并把表中的方格记为（i，j）的形式。如（2，3）表示第二行第三列的方格；（1，4）表示第一行第四列的方格等。此外，在求解过程中，如果平衡表的（2，1）方格中表写上300，即表示A2仓库调运300吨物质到第一个工地。（2）编制初始调运方案一般最优方案是由初始方案经过反复调整得到的。因此，编制出较好的初始

33、调运方案显得非常重要。确定初始方案通常有两种方法：一是西北角法，二是最小元素法。 西北角法。从供需平衡表的西北角第一格开始，按集中供应的原则，依次安排调运量。由于集中供应，所以未填数值的格子的Xij均为0，从而得到一个可行方案。按西北角法，本例的初始运输方案如表7-6所示。表7-6 初始方案 需供B1B2B3B4供应量（t）A1300400700A2200200400A3300600900需求量（t）3006005006002000由A1B1余400；A1B2400缺200；A2B2200余200；A2B3200缺300；A3B3300余600；A3B4600余0。此时运输总成本为：S=300

34、×3400×11200×9200×2300×10+600×513500（元） 最小元素法。所谓最小元素法，就是按运价表一次挑选运费小的供需点尽量优先安排供应的运输方法。首先针对具有最小运输成本的路径，并且最大限度地予以满足；然后按“最低运输成本优先集中供应”的原则，依次安排其他路径的运输量。仍以上述实例，具体做法是在表7-5 上找出最小的数值（当此数值不止一个时，可任意选择一个，方格（2，1）数值是1，最小。这样，参考A2尽可能满足B1工地的需求，于是在平衡表中有（2，1）=300，即在空格（2，1）中填入数字300，此时由于工地B1

35、已全部得到满足，不再需求A1和A3仓库的供应，运价表中的第一列数字已不起作用，因此将原运价表7-5 的第一列划去，并标注（如表7-5 所示）。然后，在运价表未划去的行、列中，再选取一个最小的数值，即（2，3）=2，让A2仓库尽量满足B3工地的需求。由于A2仓储量400吨已供给B1工地300吨，所以最多只能供应B3工地100吨。于是在平衡表（2，3）左格填入100。相应地，由于仓库A2所储物资已全部供应完毕，因此，在运价表中与A2同行的运价也已不再起作用，所以也将它们划去，并标注，仿照上面的方法，一直作下去，得表7-7。此时，在运价表中只有方格（1，4）处的运价表没有划掉，而B4尚有300吨的需

36、求，为了满足供需平衡，所以最后在平衡表上应有（1，4）=300，这样就得到表7-8的初始调运方案。表中填有数字的方格右上角是其相应的运价（元/吨）。根据得到的初始调运方案，可以计算其运输费用。（元）表7-7 供需量的分配 需供B1B2B3B4供应量（t）A1400700A2 300 100400A3600300900需求量（t）3006005006002000表7-8 初始调运方案 需供B1B2B3B4供应量（t）A1400330010700A230011002400A360043005900需求量（t）3006005006002000对于应用最小元素法编制初始方案说明以下几点： 应用最小元素

37、法编制初始调运方案，这里的“最小”是指局部而言，而整体考虑的运费不见得一定是最小的。 特别需要指出，并不是任意一个调运方案都可以作为表上作业法的初始方案。可以作为初始方案的调运方案，其填有数字的方格将恰好是（行数m+列数n-1）个，在我们这个例子中为（3+4-1=6），因此，可以作为初始调运方案提出。但是，在制定初始方案有时会碰到按最小元素所确定的方格中，其相应的供应点再无物资可供应或需求点已全部得到满足的情况，此时平衡表上填有数字的方格数小于（m+n-1）。我们规定，在未填有数字的方格中必须填上一个，并将这和其他发生供需关系的格子同样看待，而不能作为空格，其目的是保证使填有数字的方格数等于（

38、m+n-1）的要求。下面用一个例子来说明上述情况的处理。表7-9和表7-10给出了一个物资调运问题，运用最小元素经过三次运算后，得到下面表7-11和表7-12。表7-9 供需平衡表 产地销地B1B2B3供应量（t）A110A220A340需求量（t）10204070表7-10 运价表销地 运价 产地B1B2B3A1122A2313A3231可以看出，表7-13虽然构成了一个调运方案。但在运价表中，（1，3）及（2，3）方格尚未被划去，所以在平衡表7-12中，方格（1，3）及（2，3）处在各填上一个“0”，随后得表7-13，表7-13填有数字（包括0）的方格数恰是3+3-1=5，如此才可以构成调

39、运问题的初始方案。表7-11 运价表销地运价产地B1B2B3A1122A2313A3231表7-12 供需平衡表 产地销地B1B2B3供应量（t）A11010A22020A34040需求量（t）10204070表7-13 初始调用方案 产地销地B1B2B3供应量（t）A110010A220020A34040需求量（t）10204070（3）初始方案的检验在制定了初始调运方案之后，需要对它进行检验，如果制定的初始调运方案不是最优方案，需要对其进行调整直到获得最优调运方案。运输问题表上作业法，判断调运方案是否为最优解，有两种方法：一种叫做闭回路法，另一种是位势法。 闭合回路法。对于表上作业法的初始

40、方案来说，从调运方案表上的一个空格出发，存在一条且仅一条以某空格（用表示）为起点，以其他填有数字的点为其他顶点的闭合回路，简称闭回路。这个闭回路具有以下性质：第一，每个顶点都是转角点；第二，闭合回路是一条封闭折线，每一边条都是水平或垂直的；第三，每一行（列）若有闭合回路的顶点，则必有两个。只有从空格出发，其余各转角点所对应的方格均填有数字时，所构成的闭合回路，才是我们所说的闭回路；另外，过任一空格的闭回路不仅是存在的，而且是惟一的。下面以表7-8给定的初始调运方案为例，说明闭回路的性质，表7-14给出了空格，（1，1）和（3，1）所形成的闭回路：（1，1）（1·，3）（2，3）（2，

41、1）（1，1）（3，1）（2，1）（2，3）（1，3）（1，4）（3，4）（3，1）表7-14 初始调运方案 需供B1B2B3B4供应量（t）A1400300700A2300100400A3600300900需求量（t）300600·5006002000其他空格的闭回路与此同理。在调运方案的每个空格所形成的闭回路上，作单位物资的运量调整，总可以计算出相应的运费是增加还是减少。我们把所计算出来的每条闭回路上调整单位运量而使运输费用发生变化的增减值，称其为检验数。检验数的求法，就是在闭回路上，从空格出发，沿闭回路，将各顶点的运输成本依次设置“+”、“-”，交替正负符号，然后求其代数和。这

42、个代数和数字称为检验数，用ij表示。例如，上述表格上的检验数11=3-119-10。用同样的方法可以求其他空格的检验数，见表7-15。如果检验数小于0，表示在该空格的闭合回路上调整运量使运费减少；相反，如果检验数大于0，则会使运费增加。因此调运方案是否是最优方案的判定标准就是：初始调运方案，如果它所有的检验数都是非负的，那么这个初始调运方案一定最优。否则，这一调运方案不一定是最优的。表7-15 检验数计算 需供B1B2B3B4供应量（t）A103+211400330010700A23001+191002-18400A3+1076004+5103005900需求量（t）3006005006002

43、000 位势法。用该调运问题的相对运价减去表7-17中的数值，那么对初始方案中每个填有运量数值的方格来说，都会满足 （7-1）而对每个空格来说，相应得到的数值就是该空格的检验数，即 （7-2）上式就是用位势法来求检验数的公式。本例中，设Cij（i=1，2，3；j=1，2，3，4）表示变量xij相应的运价，将初始调运方案中填有数字方格的Cij分解成两部分：其中ui和Vj分别称为该方格对应i行和j列的位势量，因为i有m=3行，j有n=4列，故位势的个数有m+n=3+4=7个。但·填有运量数的单元只有m+n-1=6个，这样，m+n-1=6个Cij的方程，要解出m+n=7个未知的位势量，ui

44、和Vj可以有很多解。所以，可以先任意给定一个未知数的位势量，如表7-16所示。表7-16 位势计算表 需点供点UiA310u1=2B12u2=1C45u3=-3Vjv1=0v2=7v3=1v4=8表7-17 准检验数 需点供点UiA29310u1=2B1829u2=1C-34-25u3=-3Vjv1=0v2=7v3=1v4=8V1=0，则由C21=V2+V1=1，可以得到u2=1，再由C23=2，又得到V3=1；由C13=3，可得u1=2，依次可以得到V4=8，u3=-3，V2=7等。由上面所求出的行位势量uj与列位势量Vj对应相加，得到准检验数，如表7-17所示。表中带有 者为初始调运方案表

45、里的空格。按照位势法计算本例初始调运方案的检验数，计算结果如表7-18所示。在本例中，由于检验数出现负值，依照最优方案判定准则，可知初始调运方案不一定是最优的，需要进行调整。表7-18 检验数表 需点供点A12B1-1C1012（4） 调运方案的调整当判定一个初始调运方案不是最优调运方案时，就要在检验出现负值的该空格进行调整。如果检验数是负值的空格不止一个时，一般选择负检验数绝对值大的空格作为具体调整对象。具体调整的方法仍用前例加以说明。由于从初始调运方案的检验数表7-18中发现，空格x24的检验数是负数，因此对其进行调整，具体过程如表7-19所示。表7-19 调运方案调整表 x13 x14

46、400+100=500 300-100=200 x23 x24 100-100=0 0+100=100从空格X24开始，沿闭回路在各奇数次转角点中挑选运量的最小数值作为调整量。本例是将x23方格的100作为调整量，将这个数值填入空格X24，同时调整该闭合回路中其他转角点上的运量，使各行、列保持原来的供需平衡，这样便得到一个新的调整方案，如表7-20所示。按新方案计算调运物资的运输费用为：（元）表7-20 调整后的方案 需供B1B2B3B4供应量（t）A131500320010700A23001921008400A376004103005900需求量（t）3006005006002000新方案是

47、否是最优方案，还要对它再进行检验。经计算，该新方案的所有检验数都是非负的，说明这个方案已是最优调运方案了。综上所述，采用表上作业法求解平衡运输问题的物资调运最优方案的步骤如图7-1所示。课本重点习题：P153-156习题1 2 第十三章 存储论(P287-P324)存储论主要解决存储策略问题，即如下两个问题。（1）补充存储物资时，每次补充数量（Q）是多少？（2）应该间隔多长时间（T）来补充这些存储物资？建立不同的存储模型来解决上面两个问题，如果模型中的需求率、生产率等一些数据皆为确定的数值时，存储模型被称为确定性存储模型；如果模型中含有随机变量则被称为随机性存储模型。§1 经济订购批

48、量存储模型经济订购批量存储模型，又称不允许缺货，生产时间很短存储模型，是一种最基本的确定性存储模型。在这种模型里，需求率即单位时间从存储中取走物资的数量，是常量或近似乎常量；当存储降为零时，可以立即得到补充并且所要补充的数量全部同时到位（包括生产时间很短的情况，我们可以把生产时间近似地看成零）。这种模型不允许缺货，并要求单位存储费，每次订购费，每次订货量都是常数，分别为一些确定的、不变的数值。例1 益民食品批发部是个中型的批发公司，它为附近 200 多家食品零售店提供货源。批发部的负责人为了减少存储的成本，他选择了某种品牌的方便面进行调查研究，制定正确的存储策略。下面为过去 12 周的该品牌方

49、便面的需求数据。过去 12 周里每周的方便面需求量并不是一个常量，即使以往 12 周里每周需求量是一个常量 ，而以后时间里需求量也会出现一些变动，但由于其方差相对来说很小，我们可以近似地把它看成一个常量，即需求量每周为 3 000 箱，这样的处理是合理的和必要的。计算存储费：每箱存储费由两部分组成，第一部分是购买方便面所占用资金的利息，如果资金是从银行贷款，则贷款利息就是第一部分的成本；如果资金是自己的，则由于存储方便面而不能把资金用于其他投资，我们把此资金的利息称为机会成本，第一部分的成本也应该等于同期的银行贷款利息。方便面每箱 30 元，而银行贷款年利息为 12%，所以每箱方便面存储一年要

50、支付的利息款为 3.6 元。第二部分由储存仓库的费用、保险费用、损耗费用、管理费用等构成，经计算每箱方便面储存一年要支付费用 2.4 元，这个费用占方便面进价 30 元的 8%。把这两部分相加，可知每箱方便面存储一年的存储费为 6 元，即 C1= 6 元/年·箱，占每箱方便面进价的 20%。计算订货费：订货费指订一次货所支付的手续费、费、交通费、采购人员的劳务费等，订货费与所订货的数量无关。这里批发部计算的每次的订货费为 C3=25 元/次。这种存储模型的特点如下。（1）需求率（单位时间的需求量）为 d；（2）无限供货率（单位时间入库的货物数量）；（3）不允许缺货；（4）单位货物单位

51、时间的存储费 c1；（5）每次的订货费 c3；（6）每期初进行补充，即期初存储量为 Q。单位时间总费用=单位时间的存储费用+单位时间的订货费用单位时间的存储费用=单位时间购买货物所占用资金的利息+储存仓库的费用+保险费用+损耗费用+管理费用等设每次的订货量为 Q，由于补充的货物全部同时到位，故 0 时刻的存储量为 Q。到 T 时刻存储量为 0，则 0 到 T 时间的平均存储量为 Q/2。又设单位时间的总需求量为 D，单位货物的进价成本即货物单价为 c，则灵敏度分析：批发部负责人在得到了最优方案存储策略之后。他开始考虑这样一个问题：这个最优存储策略是在每次订货费为 25 元，每年单位存储费 6 元，或占每箱方便面成本价格 30元的 20%（称之为存储率）的情况下求得的。一旦每次订货费或存储率预测值有误差，那么最优存储策略会有多大的变化呢？这就是灵敏度分析。为此，我们用管理运筹学软件计算了当存储率和订货费发生变动时，最优订货量及其最小的一年总费用以及取定订货量为 1 140.18 箱时相应的一年的总费用，如表 13-2 所示。从表 13-2 中可以看到当存储率和