管理计划运筹学-复习材料提纲.doc

.* 《管理运筹学》复习提纲 第1章 绪论（P1-P9) 1.决策过程（解决问题的过程） （1）认清问题。 （2）找出一些可供选择的方案。 （3）确定目标或评估方案的标准。 （4）评估各个方案：解的检验、灵敏性分析等。 （5）选出一个最优的方案：决策。 （6）执行此方案：回到实践中。 （7）进行后评估：考察问题是否得到圆满解决。 其中： （1）（2）（3）形成问题。 （4）（5）分析问题：定性分析与定量分析，构成决策 2. 运筹学的分支：线性规划、整数线性规划、动态规划、图与网络模型、存储论、排队论、排序与统筹方法、决策分析、对策论、预测、目标规划，此外，还有多目标规划、随机规划、模糊规划等。 3. 运筹学在工商管理中的应用 1）生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、 物料管理等，追求利润最大化和成本最小化。 2）库存管理：多种物资库存量的管理，某些设备的库存方式、库存量等 的确定。 3）运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度 以及建厂地址的选择等。 4）人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分 配，建立人才评价体系等。 5）市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等。 6）财务和会计：预测、贷款、成本分析、定价、证券管理、现金管理等。 此外，还有设备维修、更新，项目选择、评价，工程优化设计与管理等。 3. 学习管理运筹学必须使用相应的计算机软件，必须注重学以致用的原则。 第二章 线性规划的图解法(P10-P26) 1.一些典型的线性规划在管理上的应用 合理利用线材问题：如何在保证生产的条件下，下料最少； 配料问题：在原料供应量的限制下如何获取最大利润； 投资问题：从投资项目中选取方案，使投资回报最大； 产品生产计划：合理利用人力、物力、财力等，使获利最大； 劳动力安排：用最少的劳动力来满足工作的需要； 运输问题：如何制定调运方案，使总运费最小。 2.线性规划的组成 目标函数：max f 或 min f ； 约束条件：s.t. (subject to)，满足于； 决策变量：用符号来表示可控制的因素。 3.建模过程 （1）理解要解决的问题，明确在什么条件下，要追求什么目标。 （2）定义决策变量（x1 ，x2 ，…，xn），每一组值表示一个方案。 （3）用决策变量的线性函数形式写出目标函数，确定最大化或最小化 目标。 （4）用一组决策变量的等式或不等式表示解决问题过程中必须遵循的 约束条件。 一般形式 目标函数：max（min）z = c1 x1 + c2 x2 + … + cn xn 约束条件：s.t. a11 x1 + a12 x2 + … + a1n xn ≤（=, ≥）b1 a21 x1 + a22 x2 + … + a2n xn ≤（=, ≥）b2 …… am1 x1 + am2 x2 + … + amn xn ≤（=, ≥）bm x1 ，x2 ，… ，xn ≥0 对于只包含两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示 线性规划问题的有关概念，并求解。下面通过例 1 详细介绍图解法的解题过程 取各约束条件的公共部分（如图 2-1（f） 所示）。 目标函数 z = 50x1 + 100x2，当 z 取某一固定值时得到一条直线， 直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动 等值线，当移动到 B 点时，z 在可行域内实现了最大化。A、B、C、D、E 是可行域的顶点，有限个约束条件其可行域的顶点也是有限的。 线性规划的标准化内容之一—引入松弛变量（资源的剩余量） 例 1 中引入 s1，s2，s3，模型变化为： 4.重要结论 —如果线性规划有最优解，则一定有一个可行域的顶点对应一个最 优解； —无穷多个最优解。若将例 1 中的目标函数变为 max z=50x1+50x2， 则线段 BC 上的所有点都代表了最优解； —无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大 或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束 条件； —无可行解。若在例 1 的数学模型中再增加一个约束条件 4x1+3x2 ≥1200，则可行域为空域，不存在满足约束条件的解，当然也就 不存在最优解了。 5.线性规划的标准化 6.线性规划的标准形式有四个特点： —目标最大化； —约束为等式； —决策变量均非负； —右端项非负。 对于各种非标准形式的线性规划问题，我们总可以通过变换，将其转 化为标准形式。 7.为了使约束由不等式成为等式而引进的变量 s，当不等式为“小于等 于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。 如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各 个约束引进不同的松弛变量或剩余变量。 8. 9.灵敏度分析：在建立数学模型和求得最优解之后，研究线性规划的一 个或多个参数（系数）ci , aij , bj 变化时，对最优解产生的影响。 一、目标函数中的系数 ci 的灵敏度分析 二、约束条件中常数项 bj 的灵敏度分析 当约束条件中常数项 bj 变化时，线性规划的可行域发生变化，可能 引起最优解的变化。 A.考虑例 1 的情况： 假设设备台时增加 10 个台时，即 b1 变化为 310，这时可行域扩大， 最优解为 x2 = 250 和 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。 解释：原最优解没有把原料 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 版）的升级版。它包括：线性规划、运输 2. 问题、整数规划（0-1 整数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法，共 15 个子模块。 3. “管理运筹学”软件的输出信息分析 当有多个系数变化时，需要进一步讨论。 百分之一百法则：对于所有变化的目标函数决策系数（约束条件右端 常数值），当其所有允许增加的百分比与允许减少的百分比之和不超过 100%时，最优解不变（对偶价格不变，最优解仍是原来几个线性方程的解）。 在使用百分之一百法则进行灵敏度分析时，要注意以下几方面。 （1）当允许增加量（允许减少量）为无穷大时，则对任意增加量（减 少量），其允许增加（减少）百分比均看作零。 （2）百分之一百法则是充分条件，但非必要条件；也就是说超过 100%， 最优解或对偶价格并不一定变化。 （3）百分之一百法则不能用于目标函数决策变量系数和约束条件右边 常数值同时变化的情况。这种情况下，只能重新求解。 在松弛/剩余变量栏中，约束条件 2 的值为 125，它表示对原料 A 的最低需求，即对 A 的剩余变量值为 125；同理可知约束条件 1 的剩余变量值为 0；约束条件 3 的松弛变量值为 0。 在对偶价格栏中，约束条件 3 的对偶价格为 1 万元，也就是说如果把加工时数从 600 小时增加到 601 小时，则总成本将得到改进，由 800万元减少到 799 万元。也可知约束条件 1 的对偶条件为-4 万元，也就是说如果把购进原料 A 和 B 的总量下限从 350t 增加到 351t，那么总成本将增加，由 800 万元增加到 804 万元。当然如果减少对原料 A 和 B 的总量的下限，那么总成本将得到改进。 在常数项范围一栏中，知道当约束条件 1 的常数项在 300 到 475 范围内变化，且其他约束条件不变时，约束条件 1 的对偶价格不变，仍为-4；当约束条件 2 的常数项在负无穷到 250 范围内变化，且其他约束条件的常数项不变时，约束条件 2 的对偶价格不变，仍为 0；当约束条件 3 的常数项在 475 到 700 范围内变化，且其他约束条件的常数项 不变时，约束条件 3 的对偶价格不变，仍为 1。 3.注意 （1）当约束条件中的常数项增加一个单位时，最优目标函数值增加的数量称为影子价格。在求目标函数最大值时，当约束条件中的常数项增加一个单位时，目标函数值增加的数量就为改进的数量，此时影子价格等于对偶价格；在求目标函数最小值时，改进的数量就是减少的数量，此时影子价格即为负的对偶价格。 （2） 管理运筹学”软件可以解决含有 100 个变量 50 个约束方程的线性规划问题，可以解决工商管理中大量的问题。如果想要解决更大的线性规划问题，可以使用由芝加哥大学的 L.E.Schrage 开发的 LINDO 计算机软件包的微型计算机版本 LINDO/PC。 课本重点习题：P34-38 习题1 2 3 4 第4章 线性规划在工商管理中的应用(P39-P66) 包括：人力资源分配的问题 生产计划的问题 套裁下料问题 配料问题 投资问题 1人力资源分配问题 例 1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数 如表 4-1 所示。 设司机和乘务人员分别在各时间段一开始时上班，并连续工作 8h， 问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又使配备最 少司机和乘务人员的人数最少？ 例 2．一家中型的百货商场对售货员的需求经过统计分析如表 4-2 所 示。为了保证售货员充分休息，要求售货员每周工作五天，休息两天，并 要求休息的两天是连续的。问应该如何安排售货员的休息日期，既满足工 作需要，又使配备的售货员的人数最少？ 2 生产计划的问题 例 3．某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，这三种产品都需要经过铸造、机加工和装配三道工序。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表 4-3 所示。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和外包协作各应多少件？ 解：设 x1，x2，x3 分别为三道工序都由本公司加工的甲、乙、丙三 种产品的件数，x4,x5 分别为由外包协作铸造再由本公司进行机械加工和 装配的甲、乙两种产品的件数。每件产品的利润如下： 可得到 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 所示。问：为使该厂获得最大利润，应如何制定产品加工方案？ 解：设 xijk 表示第 i 种产品，在第 j 种工序上的第 k 种设备上加工的数 量。建立如下的数学模型。 目标函数为计算利润最大化，利润的计算公式为： 利润 = [（销售单价 − 原料单价） 产品件数]之和 −（每台时的 设备费用 设备实际使用的总台时数）之和。这样得到目标函数： max (1.25−0.25) (x111+x112) + (2−0.35) (x211+x212) + (2.80−0.5) x312 – 300/6 000(5x111+10x211) -321/10 000 (7x112+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，问：应如何下料，可使所用原料最省？ 解：共可设计下列 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 套钢架。 注意： 在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。 若可能的下料方案太多，可以先设计出较好的几个下料方案。首先要求每个方案下料后的料头较短；其次方案总体能裁下所有各种规格的圆钢，且不同方案有着不同的各种所需圆钢的比。这样套裁即使不是最优解，也是次优解，也能满足要求并达到省料目的。如我们用前 5 种下料方案供套裁用，进行建模求解，也可得到上述最优解。 5 配 料 问 题 例 6．某工厂要用三种原料1、2、3 混合调配出三种不同规格的产品甲、乙、丙，数据如表4-6 和表 4-7 所示。问：该厂应如何安排生产，使利润最大？ 解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学模型时，要考虑： 对于甲：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 中可知 x11≥0.5（x11+x12+x13） x12≤0.25（x11+x12+x13） x21≥0.25（x21+x22+x23） x22≤0.5（x21+x22+x23） 从表 4-7 中可知，生产甲、乙、丙的原材料不能超过原材料的供应限额，故有 x11+x21+x31≤100 x12+x22+x32≤100 x13+x23+x33≤60 通过整理，得到以下模型： 目标函数：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：从第一年到第五年每年年初都可投资，当年末能收回本利 110%； 项目 B：从第一年到第四年每年年初都可投资，次年末能收回本利 125%，但规定每年最大投资额不能超过 30 万元； 项目 C：第三年年初需要投资，第五年末能收回本利 140%，但规定最 大投资额不能超过 80 万元； 项目 D：第二年年初需要投资，第五年末能收回本利 155%，但规定最大投资额不能超过 100 万元。 据测定每次投资 1 万元的风险指数如右表 4-10 所示： 问：（1）应如何确定这些项目每年的投资额，使得第五年年末拥有资金的本利金额最大？ （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.5x24 s. t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33 = 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 ≤100 1.1x51 + 1.25x42+ 1.4x33+ 1.55x24≥330 xij ≥ 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 将物品运往三个销地 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）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束)。 （3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。 2 运输问题的计算机求解 例 2. 某公司从两个产地 A1、A2 将物品运往三个销地 B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表 7-3 所示，问：应如何调运可使总运输费用最小？ 解：增加一个虚设的销地运输费用为 0。 例 3. 某公司从两个产地 A1、A2 将物品运往三个销地 B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表 7-5 所示，问：应如何调运可使总运输费用最小？ 解：增加一个虚设的产地运输费用为 0。 3 运输问题的应用 4 运输问题的表上作业法 1、数学模型 在物流调运问题中，如何根据已有的交通网，制定调运方案，将货物运到各需求地，而使总运费最小，是很关键的问题。这类问题可用如下数学语言描述。 已知有m个生产地点Ai（i=1，2…m），可供应某种物质，其供应量分别为：ai（i=1，2，3，…m），有n个销地（需要地）Bj（j=1，2…n），其需求量分别为bj（j=1，2，…n），从Ai到Bj运输单位物资的运价为Cij。这些数据可汇总于产销平衡表和单位运价表中，如表7-1、表7-2所示。 表7-1 产销平衡表 销地 产地 1，2……n 产量 1 a1 2 a2 ┆ ┆ m am 销量 b1，b2…bn 表7-2 单位运价表 销地 产地 1 2 … n 1 C11 C12 … C1n 2 C21 C22 … C2n ┆ ┆ ┆ ┆ ┆ ┆ ┆ ┆ ┆ ┆ m Cm1 Cm2 … Cmn 为了制定使总运费最小的调运方案，我们可以建立数学模型。 如果我们设Xij表示由产地Ai供应给销地的运量，则运输问题的线性规划模型可分为三种情况： （1） 产销平衡，即在的情况下，求（总费用最少）。满足约束条件： 1，2，…，n）（满足各销地的需要量） 1，2，…，m）（各产地的发出量等于各地产量） Xij≥0（i=1，2，…，m；j=1，2，…，n）（调出量不能为负数） （2）产大于销，即在＞的情况下，求（总费用最少）。 满足约束条件： 1，2，…，n） ≤ai（i=1，2，…，m） Xij≥0（i=1，2，…，m；j=1，2，…，n） （3）销大于产，即在＜的情况下，求（总费用最少）。 满足约束条件： ≤bj（j=1，2，…，n） =ai（i=1，2，…，m） Xij≥0（i=1，2，…，m；j=1，2，…，n） 物资调运问题可采用图上作业法或表上作业法求其最佳的调运方案。 2、物资调运问题的表上作业法 物资调运的表上作业法，是指在物资调运平衡表上确定物资调运最优方案的一种调运方法。利用表上作业法，寻求运费最少的运输方案，其步骤可归纳如下： （1）列出运输物资平衡表及运价表； （2）在表上做出初始方案； （3）检查初始方案是否为最优方案； （4）调整初始方案得到最优解。 一般说来，每调整一次得到一个新的方案，而这个新方案的运费比前一个方案要少一些，如此经过几次调整，最后可以得到最优方案。下面举例说明： 某公司有三个储存某种物资的仓库，供应四个工地的需要。三个仓库的供应量和四个工地的需求量以及由各仓库到各工地调运单位物资的运价（元/吨），如表7-3 所示，试求运输费用最少的合理运输方案。 表7-3 供需情况和单位运价 工地 运价 （元/吨） 仓库 B1 B2 B3 B4 供应量 （t） A1 3 11 3 10 700 A2 1 9 2 8 400 A3 7 4 10 5 900 需求量 300 600 500 600 2000 求解步骤如下： （1）列出调运物资平衡表7-4和运价表7-5 表7-4 物资平衡表 需 供 B1 B2 B3 B4 供应量（t） A1 700 A2 400 A3 900 需求量（t） 300 600 500 600 2000 表7-5 运价表 工地 运价 仓库 B1 B2 B3 B4 A1 3 11 3 10 A2 1 9 2 ② 8 A3 7 4 10 5 ① 平衡表和运价表是表上作业法的基本资料和运算的依据。表上作业法的实质就是利用运价表在平衡表上进行求解。 为了叙述和考虑问题的方便，通常把上面的平衡表看作为矩阵，并把表中的方格记为（i，j）的形式。如（2，3）表示第二行第三列的方格；（1，4）表示第一行第四列的方格等。此外，在求解过程中，如果平衡表的（2，1）方格中表写上300，即表示A2仓库调运300吨物质到第一个工地。 （2）编制初始调运方案 一般最优方案是由初始方案经过反复调整得到的。因此，编制出较好的初始调运方案显得非常重要。确定初始方案通常有两种方法：一是西北角法，二是最小元素法。 ① 西北角法。从供需平衡表的西北角第一格开始，按集中供应的原则，依次安排调运量。由于集中供应，所以未填数值的格子的Xij均为0，从而得到一个可行方案。按西北角法，本例的初始运输方案如表7-6所示。 表7-6 初始方案 需 供 B1 B2 B3 B4 供应量（t） A1 300 400 700 A2 200 200 400 A3 300 600 900 需求量（t） 300 600 500 600 2000 由A1→B1余400；A1→B2400缺200；A2→B2200余200；A2→B3200缺300；A3→B3300余600；A3→B4600余0。此时运输总成本为： S=3003＋40011＋2009＋2002＋30010+6005＝13500（元） ② 最小元素法。所谓最小元素法，就是按运价表一次挑选运费小的供需点尽量优先安排供应的运输方法。首先针对具有最小运输成本的路径，并且最大限度地予以满足；然后按“最低运输成本优先集中供应”的原则，依次安排其他路径的运输量。仍以上述实例，具体做法是在表7-5 上找出最小的数值（当此数值不止一个时，可任意选择一个，方格（2，1）数值是1，最小。这样，参考A2尽可能满足B1工地的需求，于是在平衡表中有（2，1）=300，即在空格（2，1）中填入数字300，此时由于工地B1已全部得到满足，不再需求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吨的需求，为了满足供需平衡，所以最后在平衡表上应有（1，4）=300，这样就得到表7-8的初始调运方案。 表中填有数字的方格右上角是其相应的运价（元/吨）。根据得到的初始调运方案，可以计算其运输费用。 （元） 表7-7 供需量的分配 需 供 B1 B2 B3 B4 供应量（t） A1 400 700 A2 300 100 400 A3 600 300 900 需求量（t） 300 600 500 600 2000 表7-8 初始调运方案 需 供 B1 B2 B3 B4 供应量（t） A1 400 3 300 10 700 A2 300 1 100 2 400 A3 600 4 300 5 900 需求量（t） 300 600 500 600 2000 对于应用最小元素法编制初始方案说明以下几点： ① 应用最小元素法编制初始调运方案，这里的“最小”是指局部而言，而整体考虑的运费不见得一定是最小的。 ② 特别需要指出，并不是任意一个调运方案都可以作为表上作业法的初始方案。可以作为初始方案的调运方案，其填有数字的方格将恰好是（行数m+列数n-1）个，在我们这个例子中为（3+4-1=6），因此，可以作为初始调运方案提出。但是，在制定初始方案有时会碰到按最小元素所确定的方格中，其相应的供应点再无物资可供应或需求点已全部得到满足的情况，此时平衡表上填有数字的方格数小于（m+n-1）。我们规定，在未填有数字的方格中必须填上一个，并将这和其他发生供需关系的格子同样看待，而不能作为空格，其目的是保证使填有数字的方格数等于（m+n-1）的要求。 下面用一个例子来说明上述情况的处理。 表7-9和表7-10给出了一个物资调运问题，运用最小元素经过三次运算后，得到下面表7-11和表7-12。 表7-9 供需平衡表 产地 销地 B1 B2 B3 供应量（t） A1 10 A2 20 A3 40 需求量（t） 10 20 40 70 表7-10 运价表 销地 运价 产地 B1 B2 B3 A1 1 2 2 A2 3 1 3 A3 2 3 1 可以看出，表7-13虽然构成了一个调运方案。但在运价表中，（1，3）及（2，3）方格尚未被划去，所以在平衡表7-12中，方格（1，3）及（2，3）处在各填上一个“0”，随后得表7-13，表7-13填有数字（包括0）的方格数恰是3+3-1=5，如此才可以构成调运问题的初始方案。 表7-11 运价表 销地 运价 产地 B1 B2 B3 A1 1 2 2 A2 3 1 3 A3 2 3 1 表7-12 供需平衡表 产地 销地 B1 B2 B3 供应量（t） A1 10 10 A2 20 20 A3 40 40 需求量（t） 10 20 40 70 表7-13 初始调用方案 产地 销地 B1 B2 B3 供应量（t） A1 10 0 10 A2 20 0 20 A3 40 40 需求量（t） 10 20 40 70 （3）初始方案的检验 在制定了初始调运方案之后，需要对它进行检验，如果制定的初始调运方案不是最优方案，需要对其进行调整直到获得最优调运方案。运输问题表上作业法，判断调运方案是否为最优解，有两种方法：一种叫做闭回路法，另一种是位势法。 ① 闭合回路法。对于表上作业法的初始方案来说，从调运方案表上的一个空格出发，存在一条且仅一条以某空格（用表示）为起点，以其他填有数字的点为其他顶点的闭合回路，简称闭回路。这个闭回路具有以下性质： 第一，每个顶点都是转角点；第二，闭合回路是一条封闭折线，每一边条都是水平或垂直的；第三，每一行（列）若有闭合回路的顶点，则必有两个。只有从空格出发，其余各转角点所对应的方格内均填有数字时，所构成的闭合回路，才是我们所说的闭回路；另外，过任一空格的闭回路不仅是存在的，而且是惟一的。 下面以表7-8给定的初始调运方案为例，说明闭回路的性质，表7-14给出了空格，（1，1）和（3，1）所形成的闭回路： （1，1）—（1，3）—（2，3）—（2，1）—（1，1） （3，1）—（2，1）—（2，3）—（1，3）—（1，4）—（3，4）—（3，1） 表7-14 初始调运方案 需 供 B1 B2 B3 B4 供应量（t） A1 400 300 700 A2 300 100 400 A3 600 300 900 需求量（t） 300 600 500 600 2000 其他空格的闭回路与此同理。 在调运方案内的每个空格所形成的闭回路上，作单位物资的运量调整，总可以计算出相应的运费是增加还是减少。我们把所计算出来的每条闭回路上调整单位运量而使运输费用发生变化的增减值，称其为检验数。检验数的求法，就是在闭回路上，从空格出发，沿闭回路，将各顶点的运输成本依次设置“+”、“-”，交替正负符号，然后求其代数和。这个代数和数字称为检验数，用λij表示。例如，上述表格上的检验数λ11=3-11＋9-1＝0。用同样的方法可以求其他空格的检验数，见表7-15。如果检验数小于0，表示在该空格的闭合回路上调整运量使运费减少；相反，如果检验数大于0，则会使运费增加。因此调运方案是否是最优方案的判定标准就是：初始调运方案，如果它所有的检验数都是非负的，那么这个初始调运方案一定最优。否则，这一调运方案不一定是最优的。 表7-15 检验数计算 需 供 B1 B2 B3 B4 供应量（t） A1 0 3 +2 11 400 3 300 10 700 A2 300 1 +1 9 100 2 -1 8 400 A3 +10 7 600 4 +5 10 300 5 900 需求量（t） 300 600 500 600 2000 ② 位势法。用该调运问题的相对运价减去表7-17中的数值，那么对初始方案中每个填有运量数值的方格来说，都会满足 （7-1） 而对每个空格来说，相应得到的数值就是该空格的检验数