伏格爾法

出自 MBA智库百科(https://wiki.mbalib.com/)

伏格爾法（Vogel Method）

　　伏格爾法又稱差值法，該方法考慮到，某產地的產品如不能按最小運費就近供應，就考慮次小運費，這就有一個差額。差額越大，說明不能按最小運費調運時，運費增加越多。因而對差額最大處，就應當採用最小運費調運。

　　伏格爾法一般能得到一個比用西北角法和最小元素法兩種方法所得的初始基本可行解更好的初始基本可行解。伏格爾法要求首先計算出各行各列中最小的c_ij，與次小的c_ij之間的差的絕對值，在具有最大差值的那行或列中，選擇具有最小的c_ij的方格來決定基變數值。這樣就可以避免將運量分配到該行（或該列）具有次小的c_ij的方格中，以保證有較小的目標函數值。所以，伏格爾法的基本步驟如下。

　　1、算出各行各列中最小元素和次小元素的差額，並標出差額最大的（若幾個差額同為最大，則可任取其一）。

　　2、在差額最大的行或列中的最小元素處填上儘可能大的數。

　　3、對未划去的行列重覆以上步驟，直到得到一個初始解。

　　由此可見，伏格爾法同最小元素法除在確定供求關係的原則上不同外，其餘步驟相同。伏格爾法給出的初始解比用最小元素法給出的初始解更接近最優解。

　　例：某公司有三個加工廠A₁,A₂,A₃ 生產某產品，每日的產量分別為7T，4T，9T，該公司把這些產品分別運往四個銷售點B₁,B₂,B₃,B₄，各銷售點的每日銷量分別為3T，6T，5T，6T。從各工廠到各銷售點的單位運價如表1所示。問該公司如何調運產品，才能在滿足各銷售點需要量的前提下，使總費用最少？

　　表1：

　　第一步：求各行各列最小和次小元素的差值。

　　在表2中，各行的差值分別為0，1，1，各列的差值分別為2，5，1，3。可見第二列差值最大，首先考慮第二列，在第二列中最小的cij 為c32＝4，令x32＝min{6，9}＝6，填入表5-10 中，第二列飽和，划去該列。

　　第二步：求餘下的各行各列最小和次小元素的差值。

　　對剩下的方格重新計算各行各列的差值，各行差值分別為0，1，2，各列差值分別為2，1，4，第四列差值最大，在第四列中，最小的c_ij為c₃₄ = 5，令x₃₄＝min{6，9-6}=3，於是第三行飽和，划去第三行。

　　第三步：重覆上述過程。

　　可得其他基變數的值為：x₂₁ = 3,x₁₃ = 4,x₂₃ = 1,x₁₄ = 3。見表3。

　　此例的解所對應的 Z=1×3+4×6+3×5+10×2+8×1+5×3=85。

　　求解線性優化運輸問題的方法有兩種：一種是將運輸問題轉化為線性規劃問題，然後利用單純形法求解；另一種是表上作業法，一般是先利用近似方法確定初始調運方案，然後檢驗該調運方案是否為最優，如果是最優調運方案則停止計算，如果還不是則進行調整，然後再檢驗，如此迴圈直到檢驗得到最優調運方案為止。前一種方法計算工作量較大，表上作業法計算量則相對較小。表上作業法的計算量主要取決於初始調運方案的近似程度，近似程度越高，後面經過檢驗、調整等迴圈步驟得到最優調運方案的速度就越快，從而計算量就越小。常見的確定初始調運方案的近似方法有西北角法、最小元素法和伏格爾法。其中伏格爾法是近似方法中近似程度最好的一種方法，這種方法得到的結果很接近最優調運方案。但在處理退化性的運輸問題的時候，各種教材對伏格爾法的描述中卻並不統一，多數教材描述不夠精確，這都嚴重影響伏格爾法的近似程度，文中將以實例的計算來進行說明，給出伏格爾法在處理退化性運輸問題中的規範應用方法以保證伏格爾法在應用中的計算效率。

　　一、伏格爾法

　　伏格爾法揭示，如果在任何行或列上，最便宜的選擇沒有被採用，那麼至少次便宜的選擇應該被採用．如果採用了次便宜的選擇，就存在一個罰金成本，其數額至少等於該行列中最便宜的選擇與次便宜的選擇之間的差。伏格爾法中確定初始調運方案的具體步驟如下：

　　第一步，計算運價表中每一行的罰金成本，即每行中次便宜選擇的成本和最便宜選擇的成本之差。

　　第二步，計算運價表中每一列的罰金成本，即每列中次便宜選擇的成本和最便宜選擇的成本之差。

　　第三步，找出這一罰金成本的最大值，並找出相應行或列成本的最低元素。

　　第四步，儘可能為這一元素分配運輸任務—— 以可能的供應量或剩餘的需求量為限分配運輸任務。分配了運輸任務的格稱為有貨流格。

　　第五步，從相應的供應量和需求量中減掉這一輪中已經分配的數量，然後不必再考慮那些已經沒有剩餘供應量的行和沒有剩餘需求量的列，重覆這一步驟，直到所有的供應量用完，所有的需求量都已得到滿足。

　　二、伏格爾法在退化性運輸問題中的應用問題

　　線性運輸問題也是一種線性規劃問題，其基變數的個數應為m+n-1個,其中，m為運價表中的行數，n為運價表中的列數。在用近似方法求解線性運輸問題時，運價表中最後應該有，m+n-1個有貨流格，即相當於線性規劃問題中的m+n-1個基變數。但可能遇到有貨流格少於，m+n-1個的情況．這就叫做退化問題。當出現退化問題時應補充零貨流格，即貨流量為零的格，相當於線性規劃問題中出現基變數等於零的情況。

　　但在具體做法上，很多教材並不統一。在各種教材中，都在著重強調有貨流格的個數應該為m+n-1，也就是說明這種線性運輸問題是一種有，m+n-1個相互獨立的約束條件的線性規劃問題。退化的運輸問題在計算過程中總會出現某行與某列同時平衡的時候，一般是認為划去相應行或列均可，然後再繼續按照伏格爾法進行新一輪的計算。為了滿足供需平衡以及有貨流格為，m+n-1的要求，會在必要的時候在相應格中填上數字“0”，使該格成為零貨流格。但這種說法是不夠準確的，在實際操作中可能會帶來比較大的誤差，這樣就體現不出伏格爾法的優點了。

　　例：用伏格爾法求表l所示的運輸問題的初始調運方案。

　　表4 運價表

　　解：首先計算各行各列的罰金成本，結果見表。

　　表5 第一次計算所得各行各列罰金成本的運價表

　　罰金成本最大為12，相應行的最小運價單元格為(Ⅲ，A)，所以應最先滿足其相應行或列的供需要求。此時發現此單元格對應的供應量與需求量相等，即當在(Ⅲ，A)單元格中填人“5”後供需同時滿足，由此可以判斷該運輸問題為退化問題。此時如果將第一列划去然後再繼續用伏格爾法計算，結果見表。

　　表6 在退化的運輸問題中期去相應列的計算表

產地	不同銷售地運價				產量	行罰金成本
	A	B	C	D
I		2(5)		11(10)	15	8	(9)	9
Ⅱ		7(10)	9(15)	20(10)	25	2	2	(11)
Ⅲ	2(5)			18(0)	5	(12)	2	2
銷量	5	15	15	lO
列罰金成本	8	5	7	7
		-	5	7	7
		-	-	7	7

　　由此調運表格可得運費為

　　2×5+2×15+9×15+l1×O十2O×1O+18×O＝375。

　　如果在上表5中(Ⅲ，A)單元格填入“5”後相應行列供需要求同時滿足，而選擇將第三行划去，繼續使用伏格爾法計算得到的結果如表7所示。

　　表7 在退化的運輸問題中划去相應行的計算表

產地	不同銷售地運價				產量	行罰金成本
	A	B	C	D
I		2(5)		11(10)	15	8	8	8	(8)
Ⅱ		7(10)	9(15)		25	2	2	5	5
Ⅲ	2(5)				5	(12)	-	-	-
銷量	1	5	15	lO
列罰金成本	8	5	7	7
		2	5	(11)	9
		2	5	-	(9)
		2	5	-	-

　　由此調運表格可得運費為2×5+12×0+2×5+7×10+9×l5+11×10=335。

　　表6和表7都是按照伏格爾法計算得到的，但顯然表7的結果比表6的結果更好，由此可見伏格爾法在退化的運輸問題的應用中，除了要註意補充零貨流格以保證有貨流格的個數為m+n-1外，還要註意當運價表中行列的供需要求同時得到滿足時應進行特殊處理。

　　三、伏格爾法在退化性運輸問題中的規範應用方法

　　用伏格爾法求運輸問題時，若在計算過程中出現一個有貨流格使得其所在的行與列的供需要求同時得到滿足時，應將其所在的行與列同時划去。為了保證運輸方案有，m+n-1個有貨流格，還必須在相應行或列中任選一個空格填人“0”。按此方法計算的結果如表8所示。

　　表8 在退化的運輸問題中規範方法的計算表

產地	不同銷售地運價				產量	行罰金成本
	A	B	C	D
I		2(5)		11(10)	15	8	9	9
Ⅱ		7(10)	9(15)		25	2	2	(13)
Ⅲ	2(5)		16(O)		5	(12)	(12)	-
銷量	1	5	15	lO
列罰金成本	8	5	7	7
	-	5	(11)9
		-	5	-	9

　　由此調運表格可得運費為2×5+2×5+7×1O+9×15+16×O+11×10=335。

　　如此計算保證了結果最優．而且罰金成本比表7少算一次。可見要想保證伏格爾法在應用過程中的效率，當運輸問題是一個退化性問題時．即在用伏格爾法的計算過程中出現一個有貨流格使得其所在的行與列的供需要求同時得到滿足時，應將相應行與列同時划去。為了保證運輸方案有，m+n-1個有貨流格．還必須在相應行或列中任選一個空格填入“0”。然後在繼續使用伏格爾法進行計算，直到出現m+n-1個有貨流格時結束計算。