强烈推荐第五章运输问题及解法.ppt

3 6 3 5 1 2 2 7 6 2 新版课件 * 3.求空格检验数的方法之二—位势法 原理：设有运输问题 的对偶问题为 新版课件 * 3 1 4 6 3 3 3 10 1 2 4 5 仍以例一为例：对偶变量表面上是7个，实际上只有6个。∴有一个是自由变量。 新版课件 * 当找出σij0的格后，调整方法仍用闭回路法。 位势法步骤：①由有数格cij=ui+vj求得ui和vj （先令u1=0），原有数格（基变量）的检验数σij=0；②空格σij= cij — (ui+vj) ；③由此可得检验数表。 新版课件 * （Ⅲ）产销不平衡的运输问题 1.产大于销的情况： 添加松弛变量xi,n+1 xin+1的定义：由Ai向Bn+1的运量，而Bn+1并不存在，相当于增加了一个虚设的销地—Ai自己的仓库里，自己往自己的地方运，运费cin+1显然为0。实际上xin+1即Ai的剩余量。 新版课件 * A1 Am B1 …… Bn Bn+1 C11 0 0 C1n Cm1 Cmn 产大于销的单位运价表 产大于销的产销量表 A1 Am a1 am B1 …… Bn Bn+1 b1 …… bn 新版课件 * 2.销大于产的情况： 添加松弛变量xm+1j 同理，此时xm+1j的意义为销售短缺的量，同样，Am+1不存在， cm+1j为0。 新版课件 * 销大于产的产销量表 A1 Am a1 am B1 …… Bn b1 …… bn Am+1 A1 Am B1 …… Bn C11 0 0 C1n Cm1 Cmn 销大于产的单位运价表 Am+1 …… 新版课件 * 四 应 用 举 例 由于在变量个数相等的情况下，表上作业法的计算远比单纯形法简单得多。所以在解决实际问题时，人们常常尽可能把某些线性规划的问题化为运输问题的数学模型。下面介绍几个典型的例子。 新版课件 * 例3 某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表3-29所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用0.15万元。要求在完成合同的情况下，作出使该厂全年生产(包括储存、维护)费用最小的决策。 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 新版课件 新版课件 * 第五章 运输问题 一.运输问题的一般提法 在经济建设中，经常碰到物资调拨中的运输问题。 例如 煤、钢材、粮食、木材等物资，在全国都有若干生产基地，分别将这些物资调到各消费基地去，应如何制定调运方案，使总的运输费用最少？ 新版课件 * 运输问题的一般提法是：1.产销平衡问题 新版课件 * 2.产销不平衡问题 此时分为两种情形来考虑： 供不应求：即产量小于销量时有 供过于求：即产量大于销量时有 新版课件 * 二.运输问题的模型 产销平衡问题模型 新版课件 * 将约束方程式展开可得 约束方程式中共mn个变量，m+n个约束。 新版课件 * 新版课件 * 新版课件 * 2.m+n个约束中有一个是多余的（因为其间含有一个平衡关系式 ） 所以R(A)=m+n-1，即解的mn个变量中基变量 为m+n-1个。 新版课件 * 三.运输问题的解法 运输问题仍然是线性规划问题，可以用线性规划法中的单纯形法来解决。但是： 1.运输问题所涉及的变量多，造成单纯 形表太大； 2.若把技术系数矩阵A中的0迭代成非0，会使问题更加复杂。 以上两个原因使得我们不得不利用运输问题的特点设计出它的特殊解法——表上作业法。 新版课件 * 表上作业法，实质上还是单纯形法。其步骤如下： 1.确定一个初始可行调运方案。可以通过最小元素法、Vogel 法来完成； 2.检验当前可行方案是否最优，常用的方法有闭回路法和位势法，用这两种方法计算出检验数，从而判别方案是否最优； 3.方案调整，从当前方案出发寻找更好方案，常采用闭回路法。 新版课件 * （Ⅰ）运输问题的常用解法： 最小元素法（确定初始方案）→闭回路法（检验当前方案）→闭回路法（方案调整） 以下面例题说明这种方法的具体步骤： 例12：某食品公司下设3个加工厂A1， A2，A3，和4个门市部B1， B2，B3，B4。各加工厂每天的产量、各门市部每天的销售量以及从各加工厂到各门市部的运价如下表所示。 问：该公