管理运筹学 课件 04运输问题

运筹学——

第三章运输问题运输问题的数学模型及其应用表上作业法

销地运费单价产地B1B2B3B4产量（吨）A13113107A219284A3741059

销量（吨）3656运输问题的典例：运输问题的典例m个产地n个销地问题及分析运输问题的典例问题及分析15运输问题的典例问题及分析问题建立表格模型哈尔滨大连拉萨产量北京53113上海96132销量221运输问题表格模型——产销平衡表12…n产量12…ma1a2…am销量b1

b2…bn

销地产地运输问题表格模型——单位运价表12…n12…m

销地产地C11C12…

C1nC21C22…

C2n…………Cm1Cm2…

Cmn运输问题表格模型12…n产量12…ma1a2…am销量b1

b2…bn

销地产地C11C12…

C1nC21C22…

C2n…………Cm1Cm2…

Cmn问题建立表格模型哈尔滨大连拉萨产量北京53113上海96132销量221求解——表上作业法

销地运费单价产地B1B2B3B4产量（吨）A13113107A219284A3741059

销量（吨）3656运输问题的典例——求解

销地运价产地B1B2B3B4A1311310A21928A374105

销地方案产地B1B2B3B4产量（吨）A17A24A39

销量（吨）3656运输问题的典例——求解表上作业法12…n产量12…ma1a2…am销量b1

b2…bn

销地产地C11C12…

C1nC21C22…

C2n…………Cm1Cm2…

Cmn产销不平衡的运输问题建模总产量总销量哈尔滨大连拉萨假想销地产量北京531103上海961304销量2311

销地产地产销不平衡的运输问题建模总产量>总销量哈尔滨大连拉萨产量北京53113上海96132假想产地0001销量231

销地产地总销量>总产量产销不平衡的运输问题建模例2设有三个化肥厂供应四个地区的化肥，假设等量的化肥在各个地区的使用效果相同。各厂的产量、各地区的需要量、单位运价如表所示。求出运费最省的调拨方案。产销不平衡的运输问题建模——销量不确定的情况例2设有三个化肥厂供应四个地区的化肥，假设等量的化肥在各个地区的使用效果相同。各厂的产量、各地区的需要量、单位运价如表所示。求出运费最省的调拨方案。产销不平衡的运输问题建模——销量不确定的情况

销地运费单价产地ⅠⅠ’ⅡⅢⅣⅣ’供应量（吨）A1613221750B1413191560C19202350假想产地50需求／万吨302070301050210解：可建立如下模型：解：求得最优方案：50201030302003020例3合同规定某厂今年每季度末应分别提供10、15、25、20台专用柴油机。该厂各季度产能及生产成本如下表。产出的柴油机若当季不交货，每台积压一个季度会产生存储费0.1万元。要求制定成本费用最低的生产计划。季度生产能力/台单位成本/万元Ⅰ2510.8Ⅱ3511.1Ⅲ3011.0Ⅳ1011.3运输问题的扩展应用例3合同规定某厂今年每季度末应分别提供10、15、25、20台专用柴油机。该厂各季度产能及生产成本如下表。产出的柴油机若当季不交货，每台积压一个季度会产生存储费0.1万元。要求制定成本费用最低的生产计划。运输问题的扩展应用运输问题的扩展应用销售成本生产Ⅰ'Ⅱ'Ⅲ'Ⅳ'虚拟销地供应量（台）Ⅰ25Ⅱ35Ⅲ30Ⅳ10需求量/台1015252010070解：建立表格模型8销售成本生产Ⅰ'Ⅱ'Ⅲ'Ⅳ'虚拟销地供应量（台）Ⅰ25Ⅱ35Ⅲ30Ⅳ10需求量/艘1015252030解：建立表格模型销售成本生产Ⅰ'Ⅱ'Ⅲ'Ⅳ'虚拟销地供应量（台）Ⅰ10.810.911.011.1025ⅡM11.111.211.3035ⅢMM11.011.1030ⅣMMM11.3010需求量/台1015252030解：建立表格模型问题求解——表上作业法运输问题的典例四季度三季度二季度一季度例4：运输问题的扩展应用运输问题生产计划

资金管理

人员分配

资源优化使用问题建立表格模型哈尔滨大连拉萨产量北京53113上海96132销量221求解——表上作业法运输问题的典例

销地运费单价产地B1B2B3B4产量（吨）A13113107A219284A3741059

销量（吨）36563.2.1确定初始调运方案1.最小元素法：从单位运价表上最小的开始确定供销关系，直到给出全部答案。例1：已知运输问题的单位运价表和产销平衡表如下，用

最小元素法求初始方案。3.2表上作业法最小元素法

求初始方案

销地运价产地B1B2B3B4A1311310A21928A374105

销地方案产地B1B2B3B4产量（吨）A1437A2314A3639

销量（吨）3656最小元素法中解的退化情况

销地运费单价产地B1B2B3B4A1311310A23948A312105

销地方案产地B1B2B3B4产量（吨）A17A24A39

销量（吨）3656最小元素法习题：例：已知运输问题的单位运价表和产销平衡表如下，用

最小元素法求初始方案。解：由单位运价表，在产销平

衡表上计算初始方案：解：由单位运价表，在产销平

衡表上计算初始方案：

销地运费单价产地B1B2B3B4产量（吨）A13113107A219284A3741059

销量（吨）36563.2.1确定初始调运方案1.最小元素法：从单位运价表上最小的开始确定供销关系，直到给出全部答案。例1：已知运输问题的单位运价表和产销平衡表如下，用

最小元素法求初始方案。3.2表上作业法

销地运费单价产地B1B2B3B4产量（吨）A13113107A219284A3741059

销量（吨）3656例1：已知运输问题的单位运价表和产销平衡表如下，用Vogel法求初始方案。2.Vogel法求初始调运方案解：

销地运费单价产地B1B2B3B4A1311310A21928A374105

销地方案产地B1B2B3B4产量（吨）A17A24A39

销量（吨）3656

销地方案产地B1B2B3B4产量（吨）A1527A2314A3639

销量（吨）3656

销地运费单价产地B1B2B3B4A1311310A21928A374105说明：

差值最大，说明方案使总的运

费减少的多。

Vogel法求得方案就是最优解或

离最优解更近。③最后一步直接选择最小运费。解：最小元素法与Vogel法比较

销地运费单价产地B1B2B3B4A1311310A21928A374105最小元素法求得的初始方案Vogel法求得的初始方案Vogel法习题：例：已知运输问题的单位运价表和产销平衡表如下，用

Vogel法求初始方案。解：由单位运价表，在产销平

衡表上计算初始方案：3.2.2最优解的判别与方案调整1、计算检验数——闭回路法通过最优性检验判别目标函数值是否最优，为否时应进行调整优化。方案中由一个空格和若干个有数字格的水平和垂直连线包围成的封闭回路称为闭回路。

销地运费单价产地B1B2B3B4产量（吨）A13113107A219284A3741059

销量（吨）3656例：已知运输问题的单位运价表和产销平衡表如下:已用最小元素法求得初始方案如下：

销地方案产地B1B2B3B4产量（吨）A1437A2314A3639

销量（吨）3656已用最小元素法求得初始方案如下：

销地运价产地B1B2B3B4A1311310A21928A374105

销地方案产地B1B2B3B4产量（吨）A1437A2314A3639

销量（吨）3656用闭回路法求该方案的检验数。即：检验数表为方案销地及检验数产地B1B2B3B4产量（吨）A1（1）（2）437A23（1）1（-1）4A3（10）6（12）39

销量（吨）3656若所有的检验数均非负，表明对调动方案做出任何改变都不会导致运费减少，即当前方案为最优，否则应调整方案。473.2.2最优解的判别与方案调整2.方案调整——闭回路法

方案销地及检验数产地B1B2B3B4产量（吨）A1（1）（2）437A23（1）1（-1）4A3（10）6（12）39

销量（吨）3656

从一个检验数为负数且最小的空格出发，在闭回路上进行运量调整，使选定空格处的运量尽可能地增加。

48得调整后的方案：3.2.2最优解的判别与方案调整2.方案调整——闭回路法

方案调整前后总运价比较

销地运费单价产地B1B2B3B4A1311310A21928A374105最小元素法求得的初始方案调整后的方案50重新计算检验数（闭回路法）3.2.2最优解的判别与方案调整

销地运价产地B1B2B3B4A1311310A21928A374105513.2.2最优解的判别与方案调整注意：（1）多个最优解：如上例，最优解及检验数表为：523.2.2最优解的判别与方案调整注意：（1）多个最优解：如上例，规划求解工具求得结果：533.2.2最优解的判别与方案调整注意：（2）特殊的闭回路习题：例：已知运输问题的单位运价表和产销平衡表如下：已用最小元素法求出初始方案：计算该方案的检验数，如果不是最优方案，对方案进行调整并求出最优解。解：用闭回路法在初始方案表上计算检验数：解：用闭回路法在初始方案表上计算检验数：调整，得方案2解：用闭回路法在初始方案表上计算检验数：调整，得方案2解：用闭回路法在初始方案表上计算检验数：计算方案2检验数计算方案2检验数调整方案2得方案3计算方案3的检验数计算方案3的检验数64确定初始方案（最小元素法、Vogel法）（闭回路法、位势法）求检验数找出绝对值最大的负检验数，调整得到新方案（闭回路法）所有检验数≥0得到最优方案算出总运价是否表上作业法的求解过程产销平衡表单位运价表转运问题如果假定：（1）每个工厂生产的糖果不一定直接发运到销售点，可以

将其中几个产地的糖果集中起来一起运。（2）运往各销地的糖果可以先运给其中几个销地，再转运

给其他销地。（3）除产地、销地外，中间还可以有几个转运站，在产地

之间、销地之间或产地与销地之间转运。已知各产地、销地、中间转运站之间的单位运价，求如何在各地之间进行调运，使总的运费最小。66转运问题表3.33产地、销地、中间转运站间运价表：67转运问题单位运价表68转运问题建立产销平衡表：求解——表上作业法§3.2

运输问题的表上作业法位势法——另一种计算检验数的方法

销地运费单价产地B1B2B3B4产量（吨）A13113107A219284A3741059

销量（吨）3656例：已知运输问题的单位运价表和产销平衡表如下:已用最小元素法求得初始方案如下：

销地运价产地B1B2B3B4A1311310A21928A374105

销地方案产地B1B2B3B4产量（吨）A1437A2314A3639

销量（吨）3656用位势法求该方案的检验数。

销地运价产地B1B2B3B4A1311310A2