当前位置： >>
4.2表上作业法表上作业法 表上作业法与单纯形法的关系 表上作业法的基本步骤 确定初始基可行解 最小元素法的基本步骤 伏格尔法三、 运输问题的求解1.表上作业法?运输问题的求解采用表上作业法，即用列 表的方法求解线性规划问题中的运输模型的 计算方法，实质上是单纯形法。 ?表上作业法是
一种特定形式的单纯形法， 它与单纯形法有着完全相同的解题步骤，所 不同的只是完成各步采用的具体形式。2.表上作业法与单纯形法的关系? 表上作业法中的最小元素法和伏格尔法实质上是在求单纯形表中的初始基可行解； ? 表上作业法中的“位势法”实质上是在求单 纯形表中的检验数； ? 调运方案表中数字格的数实质上就是单纯形 法中基变量的值； ? 调运方案表上的“闭回路法”实质上是在做 单纯形表上的换基迭代。3.表上作业法的基本步骤?（1）找出初始基可行解： m+n-1个数字格（基变量）； ?（2）求各非基变量（空格）的检验数。?（3）确定入基变量，若min{? ij | ? ij ? 0} ? ? lk ,那么选取xij为入基变量；? （4）确定出基变量，找出入基变量的闭合回路； ? （5）在表上用闭合回路法调整运输方案； ? （6）重复2、3、4、5步骤，直到得到最优解。4、确定初始基可行解? 与一般的线性规划不同，产销平衡的运输问题一定具有可行解（同时也一定存在最优 解）。 ? 最小元素法（the least cost rule）和伏格尔法 （Vogel’s approximation method）。 最小元素法 ?最小元素法的基本思想是就近供应，即从单位 运价表中最小的运价开始确定产销关系，依此 类推，一直到给出基本方案为止.5、最小元素法的基本步骤? 找出最小运价，确定供求关系，最大量的供应 ； ? 划掉已满足要求的行或 (和) 列，如果需要 同时划去行和列，必须要在该行或列的任意 位置填个“0”； ? 在剩余的运价表中重复1、2两步，直到得到 初始基可行解。?最小元素法最小元素法的基本思想是就近供应，即 从单位运价表中最小的运价开始确定产 销关系，依此类推，一直到给出基本方 案为止。最小元素法的应用（以引例4-1为例）表4-1甲 3 1 7 3 乙 11 9 4 6 丙 3 2 10 5 丁 10 8 5 6 产量（ai） 7 4 9A B C 销量（bj）第一步：从表4-1中找出最小运价“1”， 最小运 价所确定的供应关系为（B，甲），在（B，甲） 的交叉格处填上“3”，形成表4-2；将运价表的 甲列运价划去得表4-3.甲A B C 销量（bj） 3 3 甲 3 1 7 3表4-2 乙丙丁产量（ai） 7 4 96 表4-3 乙 11 9 4 65 丙 3 2 10 56 丁 10 8 5 6 产量（ai） 7 4 9A B C销量（bj）表4-3 甲 3 1 7 3 乙 11 9 4 6 丙 3 2 10 5 丁 10 8 5 6 产量（ai） 7 4 9A B C 销量（bj）第二步：在表4-3的未被划掉的元素中再找出最小 运价“2”，最小运价所确定的供应关系为（B， 丙），即将B余下的1个单位产品供应给丙，表4-2 转换成表4-4。划去B行的运价，划去B行表明B所 生产的产品已全部运出，表4-3转换成表4-5。甲A B C 销量（bj） 3 3 甲 3 1 7 3表4-4 乙丙1丁产量（ai） 7 4 96 表4-5 乙 11 9 4 65 丙 3 2 10 56 丁 10 8 5 6 产量（ai） 7 4 9A B C销量（bj）表4-5 甲 3 1 7 乙 11 9 4 丙 3 2 10 丁 10 8 5 产量（ai） 7 4 9A B C销量（bj）3656第三步：在表4-5中再找出最小运价“3”， 这样一步步地进行下去，直到单位运价表上 的所有元素均被划去为止。表4-6 A B C 甲 3 1 7 乙 11 9 4 丙 3 2 10 丁 10 8 5 6 丁 3 3 5 6 产量（ai） 7 4 9销量（bj）表4-73甲6乙5丙 4 1A B C销量（bj）3 3 6 6产量（ai） 7 4 9? 最后在产销平衡表上得到一个调运方案，见表4-6。这一方案的总运费为86个单位。?最小元素法各步在运价表中划掉的行或列是需求得 到满足的列或产品被调空的行。一般情况下，每填 入一个数相应地划掉一行或一列，这样最终将得到 一个具有m+n-1个数字格（基变量）的初始基可行解。6.应注意的问题在供需关系格（i，j ）处填入一数字，刚好 使第 i个产地的产品调空，同时也使第j个销地的 需求得到满足。填入一数字同时划去了一行和一 列，那么最终必然无法得到一个具有m+n-1个数字 格（基变量）的初始基可行解。 为了使在产销平衡表上有m+n-1个数字格，这时 需要在第行或第列此前未被划掉的任意一个空格 上填一个“0”。填“0”格虽然所反映的运输量 同空格没有什么不同；但它所对应的变量却是基 变量，而空格所对应的变量是非基变量。7. 举例将例4-1的各工厂的产量做适当调整（调 整结果见表4-7），就会出现上述特殊情况。表4-7A B C 销量（bj）甲 31 7 3 甲乙 119 4 6 乙丙 32 10 5 丙丁 108 5 6 丁产量（ai） 44 12表4-8A B C 销量（bj） 30 3 664 1 65 6产量（ai） 4 4 128.伏格法尔法每次从当前运价表上，计算各行各列 中两个最小运价之差值（行差值hi，列差 值kj），优先取最大差值的行或列中最小 的格来确定运输关系，直到求出初始方案。8.伏格尔法伏格尔法的基本步骤：1.计算每行、列两个最小运价的差； 2.找出最大差所在的行或列； 3.找出该行或列的最小运价，确定供求关系，最大量 的供应 ； 4.划掉已满足要求的行或 (和) 列，如果需要同时划 去行和列，必须要在该行或列的任意位置填个 “0”； 5.在剩余的运价表中重复1~4步，直到得到初始基可 行解。表4-1 A B C 甲 3 1 7 乙 11 9 4 丙 3 2 10 丁 10 8 5 产量（ai） 7 4 9销量（bj）表4-123甲 3 1 76乙 11 95丙 3 2 10 丁 10 8 56两最小元素之差A B C两最小元素之差40 1 12513表4-13甲 A B C 销量（bj） 3 甲 3 乙 丙 丁 产量（ai） 7 4 9 5 乙 11 丙 3 6 丁 10两最小元素之差66表4-14AB C两最小元素之差1 79 452 1085 30 1 221表4-15 甲 乙 丙 丁A B C 销量（bj）表4-1663甲 335丙 3 2 10 丁 10 8 5产量（ai） 7 4 96乙 11 9 46两最小元素之差A B C两最小元素之差170 1212表4-17甲A B乙丙丁3 63 6 5C销量（bj） 表4- 18 甲 3 1 736产量（ai） 7 4 9A B C两最小元素之差乙 11 9 4丙32 10丁 10 8 5两最小元素之差7612表4-19甲A B C 销量（bj） 表4-20 甲 3 1 7两最小元素之差乙丙丁53 63 6 52 1 36产量（ai） 7 4 9A B C乙 11 9 4丙 3 2 10丁 10两最小元素之差852表4-23 甲 A B C 销量（bj） 3 乙 丙 丁5 3 66 5 62 1 3产量（ai） 7 4 9? 总运费为85 ? 由以上可见，伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤是完 全相同的。伏格尔法给出的初始解比最小元 素法给出的初始解一般来讲会更接近于最优 解。4.2.2基可行解的最优性检验? 对初始基可行解的最优性检验有闭合回路法和位势法两种基本方法。闭合回路法具体、 直接，并为方案调整指明了方向；而位势法 具有批处理的功能，提高了计算效率。 ? 所谓闭合回路是在已给出的调运方案的运输 表上从一个代表非基变量的空格出发，沿水 平或垂直方向前进，只有遇到代表基变量的 填入数字的格才能向左或右转90度（当然也 可以不改变方向）继续前进，这样继续下去， 直至回到出发的那个空格，由此形成的封闭 折线叫做闭合回路。一个空格存在唯一的闭 回路。1.闭合回路? 所谓闭合回路法，就是对于代表非基变量的空格（其调运量为零），把它的调运量调整 为1，由于产销平衡的要求,我们必须对这个 空格的闭回路的顶点的调运量加上或减少1。 最后我们计算出由这些变化给整个运输方案 的总运输费带来的变化。如果所有代表非基 变量的空格的检验数也即非基变量的检验数 都大于等于零，则已求得最优解，否则继续 迭代找出最优解。?下面就以表4-6中给出的初始基可行解（最 小元素法所给出的初始方案）为例，讨论闭合 回路法。表4-24 甲 A B C （+3） 3 （-1） 6 6 乙 丙 4（-3） 1 （+2） 3 6 丁 3 产量（ai） 7 4 93 5 销量（bj） ? 从表4-6给定的初始方案的任一空格出发寻找闭合回路，如对 于空格（A，甲）在初始方案的基础上将A生产的产品调运一个 单位给甲，为了保持新的平衡，就要依次在（A，丙）处减少 一个单位、（B，丙）处增加一个单位、（B，甲）处减少一个 单位；即要寻找一条除空格（A，甲）之外其余顶点均为有数 字格（基变量）组成的闭合回路。表4-24中用虚线画出了这条 闭合回路。闭合回路顶点所在格括号内的数字是相应的单位运表4-24 甲 A 乙B C销量（bj）（+3） 3 （-1）3 6 6丙 4（-3）丁 3 3 6产量（ai） 71 （+2）54 9?对应这样的方案调整，运费会有什么变化呢？可以看出（A，甲）处增加一个单位，运费增加3个单位； 在（A，丙）处减少一个单位，运费减少3个单位；在 （B，丙）处增加一个单位，运费增加2个单位；在 （B，甲）处减少一个单位，运费减少1个单位。增减 相抵后，总的运费增加了1个单位。由检验数的经济 含义可以知道，（A，甲）处单位运量调整所引起的 运费增量就是（A，甲）的检验数，即σ 11=1。? 仿照此步骤可以计算初始方案中所有空格的检验数，表4-25～表4-30展示了各 检验数的计算过程，表4-30给出了最终 结果。可以证明，对初始方案中的每一 个空格来说“闭合回路存在且唯一”。表4-25甲A B?11 = 1 3乙（+11）丙4 1丁3（-10）产量（ai）7 4C销量（bj） 表4-2636（-4）6 53（+5）69乙 甲 A B C 销量（bj）?11 = 1 3 ?12 = 2 （+9） 6（-4） 3 6丙4（+3） 1（-2）丁3（-10）产量（ai）7 43（+5） 5 69表4-27甲A B C 销量（bj）3 ?11 = 1 3乙?12 = 2 ?22 = 1 6 6丙4（+3） 1（-2）丁3（-10） （+8） 3产量（ai）7 4 956表4-28甲 A?11 = 1乙?12 = 2丙4（-3）丁3（+10）产量（ai）7B C销量（bj）3?22 = 16 61（+10） 5?24 = -13（-5） 6493表4-29 甲 A B C 销量（bj） 表4-30 A?11 = 1 3（-1） （+7） 3乙?12 = 2 ?22 = 1 6 6丙4（-3） 1（+2） ?33 = 12 5丁3（+10） ?24 = -1 3（-5） 6产量（ai）7 4 9?31 = 10 3 销量（bj）B C甲 ?11 = 1 3乙 ?12 = 2丙 4丁 3产量（ai） 7?22 = 1 6 61?33 = 12 5?24 = -1 3 64 9? 如果检验数表中所有数字均大于等于零，这表明对调运方案做出任何改变都将导 致运费的增加，即给定的方案是最优方 案。在表4-30中， ?24 = -1,说明方案 需要进一步改进。2.位势法?对于特定的调运方案的每一行给出一个因子 ui（称为行位势），每一列给出一 个因子vj（称为列位势），使对于目前 解的每一个基变量xij 有cij= ui + vj，这 里的ui 和 vj可正、可负也可以为零。那 么任一非基变量 xij的检验数就是? ij ? cij ? (ui ? v j )?这一表达式完全可以通过先前所述的闭合回路法得到。在某一的闭合回路上（如下表 所示），由于基变量的运价等于其所对应的 行位势与列位势之和，即：cik ? ui ? vclk ? ul ? vk非基变量 x lj （+c ） （-cik）基变量 xik u i ij x k 基变量 xlk （-clj） （+clk）基变量 ij u l vk vjclj ? u l ? v j于是? ij ? cij ? cik ? clk ? clj ? cij ? (ui ? vk ) ? (ul ? vk ) ? (ul ? v j )所以? ij ? cij ? (ui ? v j )? 对于一个具有m个产地、n个销地的运输问题，应具有m个行位势、n个列位势，即具有“m+n”个位势。 运输问题基变量的个数只有“m+n-1”个，所以利 用基变量所对应的“m+n-1”个方程，求出“m+n” 个位势，进而计算各非基变量的检验数是不现实的。? 通常可以通过在这些方程中对任意一个因子假定一个任意的值（如u1=0等等），再求解其余的“m+n1”个未知因子，这样就可求得所有空格（非基变量） 的检验数。仍以表4-6中给出的初始基可行解（最小 元素法所给出的初始方案）为例，讨论位势法求解 非基变量检验数的过程。? 第一步：把方案表中基变量格填入其相应的运价并令u1=0 ；让每一个基变量xij都有cij= ui + vj ，可求得所有的位势，如表4-32所 示。表4-32 甲 A B C 1 4 乙 丙 3 2 丁 10 5ui0 -1 -5vj29ij3? cij ? (ui ? v j )10 计算各非基变量xij?第二步：利用 ?的检验数，结果见表4-30。4.2.3方案的优化? 在负检验数中找出最小的检验数，该检验数所对应的变量即为入基变量。在入基变量所 处的闭合回路上，赋予入基变量最大的增量， 即可完成方案的优化。在入基变量有最大增 量的同时，一定存在原来的某一基变量减少 为“0”，该变量即为出基变量。切记出基 变量的“0”运量要用“空格”来表示，而 不能留有“0”。在表4-30中， min{? ij | ? ij ? 0} ? ? 24 ? ?1 ，故选择x24为入基变量。在入基变量x24所处的闭合回路上 （如表4-33所示），赋予最大的增量“1”，相应地 有 x23最大的增量“1”，相应地有x23出基, x13=5,x14=2. 利用闭合回路法或位势法计算各空格（非基变量）的 检验数，可得表4-34（同伏格尔法的初始解表4-23）。表4-30 A B甲 ?11 = 1 3?31 = 10 3 销量（bj） C乙 ?12 = 2 ?22 = 1 6 6丙 4 1 ?33 = 12 5丁 3?24 = -1 3 6产量（ai） 7 4 9表4-33 乙 ?12 = 2 ?22 = 1 C 6 ?31 = 10 3 6 销量（bj） A B 表4-34 甲 乙 甲 ?11 = 1 3 丙 4 1 丁 3 产量（ai） 7 4 9?24 = -1 3 ?33 = 12 5 6 丙 5 丁 2 1 3A B C 销量（bj）?11 = 13?31 = 93?12 = 2 ?22 = 2 ?23 = 16 ?33 = 12产量（ai） 7 4 9656由于表4-33中的检验数均大于等于零，所以表4-33（同伏格尔法 所给出的初始解表4-23）给出的方案是最优方案，这个最优方案的§4.3运输问题的拓展4.3.1产大于销的运输问题? 总产量大于总销量的运输问题即为产大于销的运输问题。 ? 在实际问题中，产大于销意味着某些产品 被积压在仓库中。可以这样设想，如果把 仓库也看成是一个假想的销地，并令其销 量刚好等于总产量与总销量的差；那么， 产大于销的运输问题就转换成产销平衡的 运输问题 ? 假想一个销地，相当于在原产销关系表上 增加一列。?假想列所对应的运价? 由于假想的销地代表的是仓库，而我们优化的运费是产地与销地间的运输费用， 并不包括厂内的运输费用；所以假想列 所对应的运价都应取为“0”。? 至此，我们已经将产大于销的运输问题转换成产销平衡的运输问题，进一步的 求解可利用上节介绍的表上作业法来完 成。?[例4-2] 将表4-35所示的产大于销 的运输问题转换成产销平衡的运输问 题表4-35 甲 3 1 7 乙 11 9 4 丙 3 2 10 丁 10 8 5 产量（ai） 7 4 12A B C 销量（bj）3656? 解 此运输问题的总产量为23、总销量为20，所以假设一个销地戊并令其销量刚好等于总产量与总销 量的差“3”。取假想的戊列所对应的运价都为 “0”，可得表4-36所示的产销平衡运输问题。表4-36 甲 3 1 7 3 乙 11 9 4 6 丙 3 2 10 5 丁 10 8 5 6 戊 0 0 0 3 产量（ai） 7 4 12A B C 销量（bj）4.3.2销大于产的运输问题? 总销量大于总产量的运输问题即为销大于产的运输问题。 ? 可以这样设想，假想一个产地，并令其产量刚好 等于总销量与总产量的差；那么，销大于产的运 输问题同样可以转换成产销平衡的运输问题 ? 假想的产地并不存在，于是各销地从假想产地所 得到的运量，实际上所表示的是其未满足的需求。 ? 由于假想的产地与各销地之间并不存在实际的运 输，所以假想的产地行所有的运价都应该是“0”。 ? 至此，我们又将销大于产的运输问题转换成了产 销平衡的运输问题。[例4-3] 将表4-37所示的销大于产 的运输问题转换成产销平衡的运输 问题表4-37 甲 3 1 7 乙 11 9 4 丙 3 2 10 丁 10 8 5 产量（ai） 7 4 9A B C 销量（bj）11656?解此运输问题的总产量为20、总销量为28，所以 假设一个产地D并令其产量刚好等于总销量与总产量 的差“8”。令假想的D行所对应的运价都为“0”， 可得表4-37所示的产销平衡运输问题。表4-38 A B C D 销量（bj） 甲 3 1 7 0 11 乙 11 9 4 0 6 丙 3 2 10 0 5 丁 10 8 5 0 6 产量（ai） 7 4 9 84.3.3运输问题的应用举例? [例4-4] 设有三个化肥厂供应四个地区的化肥需求，假定等量化肥在这些地区的使用 效果相同。各化肥厂年产量、各地区年需要 量及从各化肥厂到各地区运送单位化肥的单 位运价如表4-39所示，试求出总的运费最 节省的化肥调拨方案。表4-39化肥厂A 化肥厂B 化肥厂C 年需要量 最低需求 /万t 最高需求地区1 16 14 19地区2 13 13 20地区3 22 19 23地区4 年产量 17 50 15 60 M 5030 5070 700 3010不限?解 这是一个产销不平衡的运输问题，总产量 为160万吨，四个地区的最低需求为110万吨，最 高需求为无限。 ? 根据现有产量，除满足地区1、地区2和地区3的 最低需求外，地区4每年最多能分配到60万吨， 这样其不限的最高需求可等价认为是60万吨。 160 ? 30 ? 70 ? 0 ? 60? 按最高需求分析，总需求为210万吨，大于总产量160万吨，将此问题定义为销大于产的运 输问题。 ? 为了求得平衡，在产销平衡表中增加一个假想 210 的化肥厂D，令其年产量为50万吨。 ?160 ? 50 ? 各地区的需要量包含最低和最高两部分：如地 区1，其中30万吨是最低需求，故这部分需求 不能由假想的化肥厂D来供给，因此相应的运 价定义为任意大正数M ；而另一部分20万吨满 足与否都是可以的，因此可以由假想化肥厂D 来供给，按前面讲的，令相应运价为“0”。?凡是需求分两种情况的地区，实际上可按 照两个地区来看待，这样可以将表4-39所示 的运输问题转换为表4-40所示的运输问题。（单位：万吨） 地区1 地区1 地区2 地区3 地区4 16 16 13 22 17 化肥厂A 14 14 13 19 15 化肥厂B 19 19 20 23 M 化肥厂C M 0 M 0 M 化肥厂D 20 70 30 10 年需要量 30 表4-40 地区4 17 15 M 0 50 年产量 50 60 50 50用表上作业法计算，可以求得这个问题的最优方案 如表4-41所示。A B C D两最小元素差地区1 地区1 地区2 16 16 13 14 14 13 19 M 19 0 20 M地区3 地区4 22 17 19 15 23地区4 17 15 M 0两最小元素差21400 19M M3 1 0 02地区415地区4 年产量 50地区1 地区1 地区2 地区3 AB C D年需要量60 503030 20 70 30 10 5050A B C D两最小元素差地区1 地区1 地区2 16 16 13 14 14 13 19 M 19 0 20 M地区3 22 19 23 0地区4 17 15 M M地区4 17 15 M两最小元素差21402地区40 15地区43 1 0 0年产量 50 60 50地区1 地区1 地区2 地区3 A B C D年需要量3030 20 70 30 10205050A B C D两最小元素差地区1 地区1 地区2 16 16 13 14 14 13 19 M 19 0 20 M地区3 22 19 23 0地区4 17 15 M M地区4 17 15 M两最小元素差2202地区40 2地区43 1 0 0地区1 地区1 地区2 地区3 A B C D年需要量年产量 50 60 50503030 20 70 30 10205050A B C D两最小元素差地区1 地区1 地区2 16 16 13 14 14 13 19 M 19 0 20 M地区3 22 19 23 0地区4 1715M M地区4 17 15 M两最小元素差557M地区40 M地区43 1 0 0地区1 地区1 地区2 地区3 A B C D年需要量年产量 5050 10 3030 20 70 30 1060 50205050A B C D两最小元素差地区1 地区1 地区2 16 16 13 14 14 13 19 M 19 0 20 M地区3 22 19 23 0地区4 17地区4 17两最小元素差15M M15M557M地区40 M地区43 1 0 0地区1 地区1 地区2 地区3 A B C D年需要量年产量 5050 10 3030 20 70 30 1030 205060 50 50A B C D两最小元素差地区1 地区1 地区2 16 16 13 14 13 14 19 M 19 0 20 M地区3 22 19 23 0地区4 17地区4 17两最小元素差15M M15M557M地区40 M地区43 0 0 0地区1 地区1 地区2 地区3 A B C D年需要量年产量 5050 20 3030 20 70 30 101030 205060 50 50A B C D两最小元素差地区1 地区1 地区2 16 16 13 13 14 14 19 M 19 0 20 M地区3 22 19 23 0地区4 17地区4 17两最小元素差15M M15M557M地区40 M地区43 1 0 0地区1 地区1 地区2 地区3 A B C D年需要量年产量 5050 3030202020 0 3070 301030 2060 50 501050[例4-6] 在A1、A2、A3、A4、A5和A6六个经济区 之间有砖、砂子、炉灰、块石、卵石、木材和 钢材七种物资需要运输。具体的运输需求如表 4-43所示，各地点间的路程（公里）见表4-44， 试确定一个最优的汽车调度方案。表4-43货物 起点 终点 车次 A1 A3 11 砖 A1 14 砂子 A2 A1 9 炉灰 A3 起点 A1 A2 A4 终点 A5 A3 A1 车次 起点 终点 2 A1 A6 3 A2 A6 4 车次 6 3块石 卵石 木材 钢材A3 A4 A5 A6A4 A2 A2 A47 8 2 4A3 A4A6 A55 3表4-44到从 A1A2 2A3 11A4 9A5 13A6 15?汽车的最优调度实质上就是空车行驶的 公里数最少。先构造如表4-45所示的各地 区汽车出入平衡表，表中“十”号表示该 点产生空车，“―”号表示该点需要调进 空车。A2 A3 A4 A5210 414 5 410 9 16 6表4-44 出车数 来车数 平衡数 A1 19 27 +8 A2 20 10 -10 A3 21 14 -7 A4 15 11 -4 A5 2 5 +3 A6 4 14 +10? 平衡结果A1、A5、A6除装运自己的货物外，可多出空车21车次；A2、A3、A4缺21车次。按最 小空驶调度，可构造表4-46所示的运输问题 数据表，进而可得表4-47所示的最优调度方 案。表4-45 A1 A5 A6 bj 表4-46 A2 A3 A4 3 1 aiA2 2 14 10 10A3 11 5 9 7A4 9 4 16 4ai 8 3 10A1 A5 A6 bj82 78 3 101074作 业课本P62：6、7题 课本P63：8题第62页习题6.已知某厂每月可生产甲产品270吨，先运至 A1、A2、A3三个仓库，然后在分别供应B1、B2、 B3、B4、B5五个用户。已知仓库容量分别为50、 100、150吨，各用户的需要量分别为25、105、 60、30、70吨。已知从该厂经各仓库然后供应 各用户的运费如下表所示，试确定一个使总运 费最少的调运方案。A1 A2 A3B1 10 20 30B2 15 40 35B3 20 15 40B4 20 30 55B5 40 30 25此题属于产销不平衡问题A1 A2 A3 B1 10 20 30 B2 15 40 35 B3 20 15 40 B4 20 30 55 B5 40 30 25? 仓库总容量：50+100+150=300（t） ? 各地区需求：25+105+60+30+70=290（t）? 由于该厂每月最多生产甲产品270t，则仓库有30t不满，各地区有20t不能满足需求 ? 可假设存在仓库A4，它的存储量为20t，用户B6 的 需求量为30t。这样就转化为产销平衡问题。由于 A4 与B6都是假设的，不需要运输，故运价都为0， 但是由A4运到B6的运输无法发生，因两者皆为假设 的，运价为无穷大，设为M。第62页习题产地 A1 A2 A3 A4 销量 B1 10 20 30 0 25 B2 15 40 35 0 105 销 B3 20 15 40 0 60 地 B4 20 30 55 0 30 B5 40 30 25 0 70 B6 0 0 0 M 30 产量 50 100 150 20?用伏格尔法求解初始基可行解得： B1 B2 B3 B4 30 60 60 30 50 30 30 B5 B6 产量 50 100 150A1 A2 A3 A4销量25v u ij50 45 101052520 7020数字格内填入相应价格，用位势法检验是否为最优解，得： B1 A1 B2 15 B3 B4 B5 B6 ui 0A2 A3 A4 vj2040 35 153040 25 0 025 20 -5-52055-20产地 A1 A2 A3 A4 销量B1 10 20 30 0 25B2 15 40 35 0 105销 B3 20 15 40 0 60地 B4 20 30 55 0 30B5 40 30 25 0 70B6 0 0 0 M 30产量 50 100 150 20用位势法检验是否为最优解，得： B1 B2 B3 B4 A1 A2 A3σ11=15 20 σ31=15 15 40 35 σ13= 0 σ23=-30 40 σ14= 15 30 σ34=30B5σ15=35 σ25=0 25B6σ16=20 σ26=-5 0ui0 25 20A4 vjσ41= 10σ42=-10σ43=-15σ44=00σ46=M+25-5-5152055-20因检验数存在负数，故需用闭合回路法调整B1 A1 A2 A3 A4 销量σ11=15 25 σ31=15 σ41= 10B250 45 10 σ42=-10B3σ13= 0 σ23=-30 60 σ43=-15B4σ14= 15 30 σ34=30 σ44=0B5σ15=35 σ25=0 50 20B6σ16=20 σ26=-5 30 σ46=M+25产量 50 100 150 202510560307030用闭合回路法调整得： B1 A1 A2 A3 A4 销量 25 25 50 5 105 60 15 30 B2 50 B3 60 B4 15 70 70 30 30 B5 B6 产量 50 100 150 20用位势法检验得： A1 A2 A3 A4 vj B3 (20) （5） 20 （10） 15 (5) 35 （20） (10) 0 (15) 5 15 0 B1 B2 15 B4 (5) 30 (20) 0 15 B5 (35) (10) 25 (10) 5 B6 (20) (5) 0 (M+35) -20 ui 0 15 20 -15因检验数全为正，所以已得最优方案。 即A3差30t没有得到满足， B2缺5t，B4缺15t。7、已知某运输问题的单位运价及最优调运方 案如表所示（括号中的数据代表运输数量）， 由于产地A2至销地B2的道路关闭，故最优调运 方案将发生变化，试在原最优调运方案的基础 上，寻找新的最优调运方案。表4-50 B1 A1 A2 A3 bj 10 2 B2 20 B3 B4 B5 ai 9 4 8 5（4） 9（5） 10 10 30 6 10（4） 7 1（3） 20（1） 10（1）4（3） 3 5 4 6 3解：由于A2 到B2道路关闭，则其运价为M，应 令其出基，以实现最优调度。先将M反映进产 销平衡表，然后用位势法作检验，有：B1 B2 B3 B4 B5ui0 M-19 1A1 （10） （1） A2 （21-M） M A3 1 20 vj 0 195 9 (7) (24-M) （40-M） (22-M) 10 4 （1） 5 9 3要令A2 B2出基，即令其运输量为0，找出负检验数最小的来 进行调整，得： B1 B2 B3 B4 B5 1 2 产量 9 4 8A1 A2 A3 销量43 5513B15B24B3 5 (2) （1） 56B4 9 （18） 10 93B5 (7) 6 4 3用位势法作检验，有：ui0 3 1A1 A2 A3（11） （1） 2 （M-22） （1） -1 20 19vj检验数已全为非负，故已得最优调度方案。8、已知某运输问题的单位运价及最优调运方案如表4所示，试回答下述问题： (1)A1到B2、A3到B5、和A4到B1的单位运价， 分别在什么范围内变化时上表中给出的最 优方案不变； (2)若A1到B2的单位运价由1变为3，最优方案 将发生怎样的变化； (3)若A3到B5的单位运价由4变为2，最优方案 将发生怎样的变化；表4-51 B1 B2 B3 B4 B5 B6 aiA1 A2 A3 A4 bj3 3 5 2（20）1（30） 3 4 2（20）2（20） 4 4 4 4 2（39） 4 1（11） 3（10） 5 4 2 2 1（1）2（30） 2 30 50 20 40 30 1150 40 60 31解：（1）设A1 到B2的单位运价为c12，因A1 到B2是 基变量，它的运价变化会引起非基变量检验系数的 变化，此时，只需对其再进行位势法分析即可。B1B2c122B3(3- c12)2B4(2)（20） 2B5(1)(1+ c12) （1）B6(5)(2+ c12) 1ui02- c12 1A1 A2 A3 A42（ c12 ） 3（4- c12 ） （3- c12 ）(c12)2(2- c12)c12(1)c121122(2)00vj(1)? 要令最优方案不变，则非基变量的检验数非负；故有c12 ≥0；3- c12 ≥ 0；4- c12 ≥0；2- c12 ≥ 0；2+ c12≥0；1+ c12 ≥ 0 解上述不等式得0≤ c12 ≤2。即A1 到B2的单位 运价在[0，2]内变化时，最有方案不变。?化不会引起其它检验数变化，故只需保证其 检验数非负即可。先用位势法算出原方案的检验数： B1 B2 B3 B4 A1 2 1 (2) (2) B5 (1) B6 (5) ui 0A3 到B5的单位运价属于非基变量，它的变A2 A3 A4 vj2 （1） 2 （3） 3 （3） （2） 2 (2) (1) (1) 1 2 1 1 1(1)（1） 22(3) 1 (2) 01 1 0设A3 到B5的单位运价为c35，则其检验数满足 c35 -（1+2）≥ 0，即c35 ≥ 3。也就是说A3 到B5的 单位运价大于等于3时，最有方案不变。? A4 到B1的单位运价属于非基变量，它的变化不会引起其它检验数变化，故只需保证其检 验数非负即可。 设A4到B1的单位运价为c41，则其检验数 满足c41 -（0+2）≥ 0，即c35 ≥2。也就是说 A4到B1的单位运价大于等于2时，即A4 到B1的 单位运价变化范围是[2，+∞)最有方案不变。B1 2 B2 1 B3 (2) B4 (2) B5 (1) B6 (5) ui 0先用位势法算出原方案的检验数：A1A2 A3 A4 vj2 （1） 2 （3） 3 （3） （2） 2 (2) (1) (1) 1 2 1 1 1(1)（1） 22(3) 1 (2) 01 1 0(2)若A1到B2的单位运价由1变为3，最优方案将发生 怎样的变化；把变化直接反映到表中可得下表： A1 A2 A3 A4 B1 2 B2 3 2 B3 (0) 2 B4 (2) B5 (1) (4) B6 (5) (5) 1 (2) 0ui0 -1 1 0vj（3） （20） 3 （1） （0） 2 （1） (3) (-1) (1) 1 2 2 3 3 1 2因存在检验数为负数，最优方案发生改变，用闭合回路法调整得： A1 A2 A3 A4 bj 表4-51 B1 A1 A2 A3 A4 bj B2 B3 B4 B5 B6 ai 50 40 60 31 11 2（20）3（30） 2（20）2（20） 3（10） 2（39） 30 50 20 B1 21 9 1 30 50 20 40 B2 29 20 B3 20 40 30 30 11 11 B4 B5 B6 ai 50 40 60 311（11）1（1）2（30） 40 30重新计算检验数，得： B1 2 B2 3 2 B3 (0) 2 B4 (2) B5 (0) (2)（0） 2 3A1 A2 A3 A4vj（3） （4） 3 （1） （0） 2 (3) 2 (0) （1） 2 3 3 1B6 (5) (5) 1 (3) 0ui0 -1 1 -1非基变量检验数均为非负，故为最优方案。（3）把A3 到B5的单位运价改为2，然后求检验数得： A1 A2 A3 A4 B1 2 B2 1 2 B3 (2) 2 B4 (2) B5 (1) (1) B6 (5) (3) 1 (2) 0 B6ui0 1 1 0vj表4-51（1） （3） 3 2 （3） （2） （-1） (2) (1) (1) 1 2 2 1 1 1 2 B1 B2 B3 B4 B5ai 50 40A1 A2A3 A4 bj3 3 5 2（20）1（30） 3 4 2（20）2（20） 4 4 4 4 2（39） 4 1（11） 3（10） 5 4 2 2 1（1） 2（30） 2 30 50 20 40 30 1160 31由于存在负检验数，故最优方案发生变化，此时用闭合回路法调 整得： A1 A2 A3 A4 bjB1 20v u ijB2 30 20B320B4B5B610 30 B1 50 B2 20 B39 31 40 B430 30 B511 11 B6ai 50 40 60 31重新计算检验数，得： A1 A2 A3 A4 2 1 2 (2) 2检验数全为非负，故已得最优方案。 (2) (1) (1)（1） 2 2（1） （2） 3 （3） （2） 2 (2) (1) (1) 1 2 1 1 1(5) (3) 1 (2) 00 1 1 0B1A1σ11=15B250B3σ13= 0B4σ14= 15B5σ15=35B6σ16=20产量 50 100 15020A2 A3A4 销量25σ31=15 σ41= 104510 σ42=-10σ23=-3060 σ43=-1530σ34=30 σ44=0σ25=050 20σ26=-530 σ46=M+252510560307030B1 A1 A2 A3 A4 销量σ11=15 25 σ31=15 σ41= 10B250B3σ13= 0 45B4σ14= 15 30B5σ15=35 σ25=0B6σ16=20 σ26=-5 30 σ46=M+25产量 50 100 150 2055 50σ42=-10 5105σ34=30 15 σ43=-15 σ44=0 1525603070 50 65 5 20 7030
13 1 长治学院学士学位论文 线性规划在运输问题中的应用
李勇 信息与计算科学 董建新 指导教师 引言线性规划是决策系统的静态最优化数学规划方法之一。它...火车运输木材只与火车运输的单位成本和路程 有关,故建立规划模型求解最小运输问题。 目标函数为最小年金成本,约束为每年木材资源区能够生产的木材量和每年市 场能够...运输问题 (在下列各题中,从备选答案中选出 1 个或多个正确答案) ) 下列变量组是一个闭回路的有( A.{ x21, x11, x 12, x32, x33, x23...运输问题 摘要: 摘要: 本文是针对解决某港口对某地区 8 个公司所需原材料 A、B、C 的运输调度问 题的方案。 对于问题一,我们依货运里程短,空载里程长;派车...运输问题与指派问题_人力资源管理_经管营销_专业资料。运筹学天津理工大学 课程论文运筹学 运输问题与指派问题――匈牙利法 姓名: 系别: 机械工程系 开始日期: 2013...如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 运输问题 运筹学运输问题运筹学运输问题隐藏&& 作业: 问题 1: 某公司...运输问题练习_管理学_高等教育_教育专区。已知某运输问题如下(单位:百元/吨),求总运费最小的调运方案和最小运费。 单位运价 产地 A1 A2 A3 需求量(吨) 10...应用表上作业法求解时,运输问题的初始方案必须( A.用最小元素法获得 C.包含 m ? n ? 1 个非零数字 ) B.用差值法获得 D.包含 m ? n ? 1 个非基...最优化运输问题_数学_自然科学_专业资料。摘要:根据运输问题的基本特征,运用最优化的线性规划解决问题,通过实例对运输问题进行优化分析, 建立运输问题的线性规划数学模...物流中的运输问题_生产/经营管理_经管营销_专业资料。物流中的运输问题一、运输的地位和作用物流是物品实体的物理性运动,这种运动不仅改变了物品的时间状态,同时 也...
All rights reserved Powered by
copyright &copyright 。文档资料库内容来自网络，如有侵犯请联系客服。