伏格尔法解决传输运输问题

本文主要是介绍伏格尔法解决传输运输问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

含义

伏格尔法又称差值法，该方法考虑到，某产地的产品如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。同理也适用于产销量分配。

具体步骤

        1、计算单位运价表中同行或者同列的最小运费与次小运费之差，分别列在单位运价表的最右列和最下行（行差和列差）。
        2、对行差和列差进行对比，找出最大差额。以与最大差额值同行（或同列）的最小运价为准，根据所在行的产量，最大限度地满足所在列的需求；一旦需求（或库存）被彻底满足（或库存调光），则随即划去该列和该列的所有运价信息。
        3、重新计算同行同列的最小运费与次小运费之差，并对其它未被确定调拨值的行列，重复第二步的处理，直至构造出调拨方案。

例题分析

例题：某公司有东部、中部、西部三个生产基地，生产的产品需要运送到甲、乙、丙、丁四个市场，从生产基地到各个市场的单位运价及产量和需求量如表所示，完成该运输任务所需的最小运费。

	甲	乙	丙	丁	产量
东部	4	12	4	11	16
中部	2	10	3	9	10
西部	8	5	11	6	22
需求量	8	14	12	14

解题步骤1：计算每行每列的最小元素和次小元差值。

	甲	乙	丙	丁	产量	行差
东部	4	12	4	11	16	4-4=0
中部	2	10	3	9	10	3-2=1
西部	8	5	11	6	22	6-5=1
需求量	8	14	12	14
列差	4-2=2	10-5=5	4-3=1	9-6=3

步骤2：找到最大差值为乙的列差5，与最大差额同行或同列的最小运价为准，用其所在行的产量，最大限度满足所在列的需求。即西部运送14吨到乙，运费14*5=70;乙的需求被满足，删除乙这一列，西部的产量余8。

	甲	乙	丙	丁	产量	行差
东部	4	12	4	11	16	0
中部	2	10	3	9	10	1
西部	8	5	11	6	22-14=8	1
需求量	8	14	12	14
列差	2	5	1	3

步骤3：找到最大差额为丁的列差3，第一次重复以最大差额同行或同列的最小运价为准，用其所在行的产量，最大限度满足所在列的需求。即西部余下的8吨全部运送到丁，运费8*6=48；西部产量用完，删除西部这一行，丁余下的需求为6。

	甲	丙	丁	产量	行差
东部	4	4	11	16	0
中部	2	3	9	10	1
西部	8	11	6	~~22-14=8~~	1
需求量	8	12	14-8=6
列差	2	1	3

步骤4：找到最大差额为丁的列差2，第二次重复以最大差额同行或同列的最小运价为准，用其所在行的产量，最大限度满足所在列的需求。即中部的10吨运送6吨到丁，运费6*9=54；丁的需求全部满足，删除丁这一列，中部产量余4。

	甲	丙	丁	产量	行差
东部	4	4	11	16	0
中部	2	3	9	10-6=4	1
需求量	8	12	~~14-8=6~~
列差	2	1	3

步骤5：找到最大差额为甲的列差2，第三次重复以最大差额同行或同列的最小运价为准，用其所在行的产量，最大限度满足所在列的需求。即中部余下的4吨运送到甲，运费4*2=8；中部产量用完，删除这一行，甲的需求剩余4。

	甲	丙	产量	行差
东部	4	4	16	0
中部	2	3	~~10-6=4~~	1
需求量	8-4=4	12
列差	2	1

步骤6：最后只剩下东部有产量16吨，将其中的4吨运送到甲，12吨运输到丙完成运输任务。

	甲	丙	产量	行差
东部	4	4	16-4=12	0
需求量	~~8-4=4~~	12
列差	2	1

步骤7：总结所有运价，将所有运价求和：西部运送14吨到乙，每吨运价5，14*5=70；西部运送8吨到丁，每吨运价6，8*6=48；中部运送6吨到丁，每吨运价9，6*9=54；中部运送4吨到甲，每吨运价2，4*2=8；东部运送4吨到甲，每吨运价4，4*4=16; 东部运送12吨到丙，每吨运价4，12*4=48; 70+48+54+8+16+48=244。

	丙	产量	行差
东部	4	16-4=12	0
需求量	12
列差	1

有一种更简单的方法从左到右，依次取最小运价满足甲、乙、丙的需求，剩余的产量给丁。中部产量满足甲的需求8，剩余2，运价8*2=16；西部产量满足乙的需求14，剩余8，运价14*5=70；东部产量满足丙的需求12，剩余4，运价12*4=48;东部、中部、西部剩余的产量全部给丁，运价为：4*11 +9*2+8+6=110；总运价：16+ 70+48+ 110=244。