第12次课--第三章 运输问题

1、信息系统与管理学院 第三章第三章 运输问题运输问题温故知新信息系统与管理学院 第三章第三章 运输问题运输问题 表上作业法表上作业法小结：小结： 表上作业法的流程表上作业法的流程步步 骤骤: :支持方法支持方法:一、确定初一、确定初始基可行解始基可行解二、判别是二、判别是否为最优解否为最优解三、解三、解的改进的改进四、返回四、返回步骤二步骤二伏格尔法伏格尔法最小元素法最小元素法闭回路法闭回路法位势法位势法闭回路调整法闭回路调整法信息系统与管理学院 第三章第三章 运输问题运输问题 1 1、表上作业法计算中需注意的问题、表上作业法计算中需注意的问题 2 2、产销不平衡运输问题及其转化为产销平衡、产销

2、不平衡运输问题及其转化为产销平衡运输问题的方法运输问题的方法 3 3、运输问题的总结、进一步的思考、运输问题的总结、进一步的思考信息系统与管理学院 第三章第三章 运输问题运输问题（一）无穷多最优解（一）无穷多最优解 判别准则：判别准则： 若终表（最优表）有若终表（最优表）有某个空格（非基变量）的检某个空格（非基变量）的检验数为验数为0 0时，则该问题有无穷多最优解，否则有时，则该问题有无穷多最优解，否则有唯一唯一最优解最优解。需注意的问题需注意的问题信息系统与管理学院 第三章第三章 运输问题运输问题（二）调入格（换入变量）的选取（二）调入格（换入变量）的选取 确定调入格（换入变量）时，有确定调

3、入格（换入变量）时，有两个或者多个空两个或者多个空格（非基变量）的检验数为负数格（非基变量）的检验数为负数，通常，通常取检验数为负取检验数为负中值最小的空格为调入格（换入变量）中值最小的空格为调入格（换入变量）。 若空格检验数中出现若空格检验数中出现两个或者多个相等的最小负两个或者多个相等的最小负数数时，只能选择其一为调入格，可以时，只能选择其一为调入格，可以选择调整量较大选择调整量较大的为调入格的为调入格。需注意的问题需注意的问题信息系统与管理学院 第三章第三章 运输问题运输问题（三）退化情形（三）退化情形 退化解：在产销平衡表上退化解：在产销平衡表上某个数字格（基变量）的某个数字格（基变量

4、）的值为值为0 0。 出现退化解的两种情况：出现退化解的两种情况： 1 1、确定初始解的各供需关系时、确定初始解的各供需关系时 2 2、用闭回路法调整时、用闭回路法调整时需注意的问题需注意的问题信息系统与管理学院 第三章第三章 运输问题运输问题（三）退化情形（三）退化情形1 1、确定初始解的各供需关系时、确定初始解的各供需关系时 若在若在(i,j(i,j) )格填入某数字时，出现格填入某数字时，出现AiAi处产量的余量等处产量的余量等于于BjBj处需量的余量处需量的余量，这时，这时在产销平衡表上填上一个数，在产销平衡表上填上一个数，而在单位运价表上相应地要划去一行和一列而在单位运价表上相应地要

5、划去一行和一列。 为了使在产销平衡表上有为了使在产销平衡表上有(m+n-1)(m+n-1)个数字格，这时需个数字格，这时需要要添一个添一个0 0，它的，它的位置可在对应同时划去的那行或那列的位置可在对应同时划去的那行或那列的任一空格处任一空格处。需注意的问题需注意的问题信息系统与管理学院 第三章第三章 运输问题运输问题 （三）退化情形（三）退化情形（2 2）用闭回路法调整时）用闭回路法调整时 在闭回路上出现在闭回路上出现两个或两个以上的具有（两个或两个以上的具有（1 1）标记的相等的最小值标记的相等的最小值，只能选择一个作为调出格。，只能选择一个作为调出格。 这时除调出格外，在其余数据格上填上

6、调整后这时除调出格外，在其余数据格上填上调整后的数字（的数字（包括包括0 0，表明此格是基变量，表明此格是基变量）。这就得到退）。这就得到退化解。化解。需注意的问题需注意的问题信息系统与管理学院 第三章第三章 运输问题运输问题 （三）退化情形（三）退化情形 当出现退化解后，下次再作改进调整时，可能当出现退化解后，下次再作改进调整时，可能在某闭路上有在某闭路上有标记为（标记为（1 1）的的取值为取值为0 0的数字格的数字格。这时应取这时应取调整量：调整量： 需注意的问题需注意的问题0信息系统与管理学院 第三章第三章 运输问题运输问题 前面表上作业法是在前面表上作业法是在“产销平衡产销平衡”条件下

7、进行的。条件下进行的。 对于对于产销不平衡问题产销不平衡问题，使用数学常用的方法，使用数学常用的方法转化转化，通过虚设产地或销地，将产销不平衡问题转化，通过虚设产地或销地，将产销不平衡问题转化为产销平衡问题。为产销平衡问题。 产销不平衡问题产销不平衡问题信息系统与管理学院 第三章第三章 运输问题运输问题下面讨论两种产销不平衡问题。下面讨论两种产销不平衡问题。 1 1、产大于销、产大于销 2 2、销大于产、销大于产产销不平衡问题产销不平衡问题11mnijijab11mnijijab信息系统与管理学院 第三章第三章 运输问题运输问题11mnijijab1 1、 产大于销产大于销数学模型数学模型 当

8、且仅当当且仅当 有可行解。有可行解。产销不平衡问题产销不平衡问题信息系统与管理学院 第三章第三章 运输问题运输问题 1 1、 产大于销产大于销产销量和单位运价表产销量和单位运价表产销不平衡问题产销不平衡问题信息系统与管理学院 第三章第三章 运输问题运输问题1 1、 产大于销产大于销产销不平衡问题产销不平衡问题转化办法转化办法：当产大于销时，只要增加一个假想的销地：当产大于销时，只要增加一个假想的销地Bn+1Bn+1（实际上是贮存在本地），该销地总需要量为：（实际上是贮存在本地），该销地总需要量为： 在单位运价表中从各产地到假想销地的单位运价在单位运价表中从各产地到假想销地的单位运价一般假设为一

9、般假设为c ci,n+1i,n+1=0=0（若考虑有贮存费用等情况，则若考虑有贮存费用等情况，则应根据实际情况具体分析，比如将贮存费用作为单位应根据实际情况具体分析，比如将贮存费用作为单位运价运价），就可以转化成一个产销平衡问题。），就可以转化成一个产销平衡问题。11mnijijab信息系统与管理学院 第三章第三章 运输问题运输问题设设x xi,n+1i,n+1是产地是产地A Ai i到销地到销地B Bn+1n+1的运量（的运量（ A Ai i储存量），有：储存量），有：(1,;1, )0(1,;1)i jiji jccim jncim jn令令产销不平衡问题产销不平衡问题(1) (1) 产大

10、于销产大于销1,1111,11111(1,)(1, )nniji nijijjmijjimmni nijniijxxxaimxbjnxabb信息系统与管理学院 第三章第三章 运输问题运输问题1,1,11111111111min1,1,10mnmnmi jiji jiji ni nijijimnijijijnijijmijjiijzc xc xcxc xxaimxbjnx满足：转化为了产销平衡问题转化为了产销平衡问题 产销不平衡问题产销不平衡问题(1) (1) 产大于销产大于销信息系统与管理学院 第三章第三章 运输问题运输问题 练习题练习题产销量和单位运价表产销量和单位运价表产销不平衡问题产销不

11、平衡问题信息系统与管理学院 第三章第三章 运输问题运输问题产销不平衡问题产销不平衡问题2 2、 销大于产销大于产数学模型数学模型 当且仅当当且仅当 有可行解。有可行解。11mnijijab信息系统与管理学院 第三章第三章 运输问题运输问题 产销量和单位运价表产销量和单位运价表产销不平衡问题产销不平衡问题2 2、 销大于产销大于产信息系统与管理学院 第三章第三章 运输问题运输问题2 2、 销大于产销大于产产销不平衡问题产销不平衡问题转化办法转化办法：可以在产销平衡表中增加一个假想的产地：可以在产销平衡表中增加一个假想的产地Am+1Am+1，该地产量为：该地产量为： 在单位运价表上令从该假想产地到

12、各销地的单位运价为在单位运价表上令从该假想产地到各销地的单位运价为ccm+1,jm+1,j=0=0（若是某销地需要实际的货物，未满足需求有惩罚若是某销地需要实际的货物，未满足需求有惩罚费用等情况，则应根据实际问题具体分析，比如将惩罚费用费用等情况，则应根据实际问题具体分析，比如将惩罚费用作为单位运价作为单位运价），就可以转化成产销平衡问题。），就可以转化成产销平衡问题。11nmjijiba信息系统与管理学院 第三章第三章 运输问题运输问题 设设x xm+1,j m+1,j 是虚拟产地是虚拟产地A Am+1m+1到销地到销地B Bj j的运量，有：的运量，有：1,1,101i jijmjccim

13、jncjn 令令产销不平衡问题产销不平衡问题2 2、 销大于产销大于产,11,11111,1,1111ni jijnnmmjmjijjimmi jmji jjiixaimxabaxxxbjn 信息系统与管理学院 第三章第三章 运输问题运输问题11minmnijijijzc x满足：满足：111(1,2,1)1,2,0nijijmijjiijxaimxbjnx产销不平衡问题产销不平衡问题2 2、 销大于产销大于产信息系统与管理学院 第三章第三章 运输问题运输问题 练习题练习题产销量和单位运价表产销量和单位运价表产销不平衡问题产销不平衡问题信息系统与管理学院 第三章第三章 运输问题运输问题运输问题

14、总结运输问题总结1 1、运输问题模型及与线性规划问题的关系、运输问题模型及与线性规划问题的关系2 2、产销平衡问题的表上作业法、产销平衡问题的表上作业法3 3、多解和退化情况、多解和退化情况4 4、产销不平衡问题以及转化为产销平衡问题的方法、产销不平衡问题以及转化为产销平衡问题的方法课后进一步思考研究课后进一步思考研究：1 1、有限制的情况（、有限制的情况（收发量有界、某产地货物只能运收发量有界、某产地货物只能运给某销地、某产地货物不能运给某销地等给某销地、某产地货物不能运给某销地等）2 2、有转运的运输问题、有转运的运输问题信息系统与管理学院 第三章第三章 运输问题运输问题P98 4.4、

15、4.7课后作业：课后作业：信息系统与管理学院 第三章第三章 运输问题运输问题 思考题思考题1 1 某工厂按合同规定应在明年每个季度末分别向客户提供某工厂按合同规定应在明年每个季度末分别向客户提供1010，1515，2525，2020台同一规格的机床。已知该厂各季度的生产能力台同一规格的机床。已知该厂各季度的生产能力及生产每台机床的成本如下表：及生产每台机床的成本如下表：季度季度生产能力生产能力( (台台) )每台机床成本（万元）每台机床成本（万元）1 1252510.810.82 2353511.111.13 3303011.011.04 4101011.311.3如果生产出来的机床当季度不交

16、货，那么每台机床每积压一个如果生产出来的机床当季度不交货，那么每台机床每积压一个季度要支付季度要支付储存和维护费用储存和维护费用0.150.15万元万元。现在要在完成合同的情。现在要在完成合同的情况下，作出使该厂明年生产成本况下，作出使该厂明年生产成本( (包括储存、维护包括储存、维护) )最小的生产最小的生产安排。试解此问题。安排。试解此问题。应用思考题应用思考题信息系统与管理学院 第三章第三章 运输问题运输问题 这是一个产大于销的运输问题。注意到这个问题中当这是一个产大于销的运输问题。注意到这个问题中当i ij j时，时，x xijij=0=0，所以应令对应的，所以应令对应的c cijij

17、=M=M，再加上一个假想的需求，再加上一个假想的需求D D，就可以把这个问题变成产销平衡的运输模型，并写出产销量就可以把这个问题变成产销平衡的运输模型，并写出产销量和单位运价表。和单位运价表。应用思考题应用思考题信息系统与管理学院 第三章第三章 运输问题运输问题 经用表上作业法求解，可得多个最优方案，下表经用表上作业法求解，可得多个最优方案，下表列出了最优方案之一。按此方案生产，该厂总的生产列出了最优方案之一。按此方案生产，该厂总的生产( (包括储存、维护包括储存、维护) )的费用为的费用为773773万元。万元。应用思考题应用思考题信息系统与管理学院 第三章第三章 运输问题运输问题思考题思考

18、题2 2 设有三个化肥厂供应四个地区的农用化肥。假定等量设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如下表所示。需要量及从各化肥厂到各地区运送单位化肥的运价如下表所示。试求出总的运费最节省的化肥调拨方案。试求出总的运费最节省的化肥调拨方案。应用思考题应用思考题6060信息系统与管理学院 第三章第三章 运输问题运输问题解：解： 这是一个产销不平衡的问题。这是一个产销不平衡的问题。 总产量为总产量为160160万吨，四个地区的最低需求为万吨，四个

19、地区的最低需求为110110万吨，最高需求为无限。根据现有产量，第万吨，最高需求为无限。根据现有产量，第个地个地区每年最多可分配到区每年最多可分配到6060万吨。这样四个地区的最高万吨。这样四个地区的最高需求为需求为210210万吨，大于产量。万吨，大于产量。 为求得平衡，在产销平衡表中增加一个假想的为求得平衡，在产销平衡表中增加一个假想的化肥产地化肥产地D D，其年产量为，其年产量为5050万吨。万吨。应用思考题应用思考题信息系统与管理学院 第三章第三章 运输问题运输问题解：解： 由于各地区的需要量包含两个部分，分两个部由于各地区的需要量包含两个部分，分两个部分考虑。分考虑。 如地区如地区，其中，其中3030万吨是最低需求，故不能由万吨是