2375运筹学基础复习资料6

第六章运输问题P94
本章以求总运输费用最低为目标值，故在求最优解时，在各个空格中选择调整格时，以绝对值最大的负改进指数（检验数）所在的空格为调整格的；若以求总运输利润最大（最大值）为目标值，则在求最优解时，在各个空格中选择调整格时，以正数最大值的改进指数（检验数）所在的空格为调整格。此情况与在线性规划中求极小值和求极大值的过程有部分不同是相似的。
在几个供应点与几个需求点之间，运输品种，规格，质量等相同的货物时，选择量佳运输方案
运输问题及其特殊结构（领会）P94
一、 运输问题
假设所有产地的总产量恰好与所有销地的总需求量相等，称为平衡运输问题，反之可通过虚设一个产地或销地使其化为平衡运输问题
二、 表上作业法概述：先找出一个初始方案，进行调整，求出最优方案
需要量等于供应量的运输问题P96
运输问题存在供需平衡，供大于需和供小于需三种情况
最佳运输方案程序：
一、 建立运输图（综合应用）P98
二、 求得一个最初的运输方案：西北角法（综合应用）P99
（1） 从运输图的西北角（左上角）开始，将供应量由西向东分配，直至分配完
（2） 最终供应量都已分配出去，需求量都已得到满足
（3） 数字格的数目 = m（行数）+ n（列数） –1，其余为空格（或无石方格）可用线性规划的原理解释
（4） 此方法也叫阶石法或登石法
（5） 得出最初方案的总运输费用
三、 寻求改进方案：阶石法，修正分配法（综合应用）P101
（1） 阶石法：改进路线（指从某一个空格开始，所寻求的那一条企图改变原来的运输方案的路线）和改进指数（指循着改进路线，当货物的运输量作一个单位的变动时，会引起总运输费用的改变量）。无论从水平或垂直方向进行调整都必须有增有减，以保持平衡
（2） 将改进路线画在运输图上（在同一行或同一列上，必然一增一减，配对进行，是一条闭合路线，故也叫闭合回路法）
（3） 计算改进指数
（4） 按同样方法，求得每个空格的改进路线和改进指数
四、 建立改进方案（综合应用）P103
（1） 原则：在所有空格中，挑选绝对值最大的负改进指数所在的空格作为调整格
（2） 调整格选 定后，调整路线也就选定了
（3） 在调整路线中，挑选负号格（即减少运量格）的最小运量为调整运量，以保证改进路线上的所有各格都能合理调整。 另，原来作为出发点的空格将变成数字格，而在减少运量的数字格中，运输量最小的数字格将变为空格；在寻求某个空格的改进路线时，在改进路线中，除了作为出发点的那个空格外，不能再有其他的空格 ：数字格的数目 = 行数 + 列数 - 1
（4） 调整后建立新的运输方案，然后按以上方法进行各个空格寻求改进路线和计算改进指数，只有当各个空格的改进指数都大于或等于0时，最优的运输方案求得
五、 对最优的运输方案的几点解释（领会）P106
（1） 求解的目标是整体最优而不是某个局部最优
（2） 最优的运输方案并不是只有一个
六、 修正分配法（位势法）（领会）P106
1．程序：
（1） 先把用西北角当求得的最初的运输方案图进行一些改进：顶上加一行，左侧例加一列，值根据每个数字格的单位运输费用分配给每列或每行的位势值
（2） 计算最初的运输方案中各空格的改进指数，改进指数亦称检验数或位势差
位势差：理论位势和实际位势。位势差这样求得：实际位势的列向位势 – 理论位势的列向位势
即（公式）
选绝对值最大的负改进指数所在空格作为调整格，在改进路线中，挑选是负号格的最小运量为调整运量，并对该方案的R值和K值也作调整，重复以上步骤至最优
2．修正分配法与闭合回路法的关系
（1） 修正分配法以闭合回路法为基础
（2） 在判断某个方案是否最优时，前者比后者简单，修正分配法只需对一个空格而不必对所有空格寻求闭合的改进路线
需要量不等于供应量的运输问题P112
一、 需求量小于供应量的运输问题（综合应用）P112
方法：虚设一个需求量；虚设的需求点的需求量 = 总供应量 – 总需求量；任何一个供应点到虚设的需求点的单位运费都等于0。
二、 需求量大于供应量的运输问题（综合应用）P114
方法：虚设一个供应点；虚设的供应点的供应量 = 总需求量 – 总供应量；任何一个供应点到虚设的需求点的单位运费都等于0。
三、 对于运输问题的一般求解程序（领会）P117
P118图
四、 求解运输问题时出现的退化现象（领会）P117
在求解运输问题时，必须符合一个条件，数字格的数目 = 行数 + 列数 – 1，但由于一些碰巧的原因，使数字格的数目＜行数 + 列数 – 1，这种现象称为退化现象