【正文】 個 Aij0，則選擇負檢驗數(shù)中絕對值最大的閉回路進行調整，建立新的方案。 ⑥ 重復 3—5 步，直至獲得最優(yōu)調運方案。 運輸路線合理化 運輸合理化的實施途徑運輸合理化的實施途徑（ 1）表上作業(yè)法 例 1 某公司下屬三個儲存某種物資的料庫，供應四個工地的需要。三個料庫的供應量和四個工地的需求量以及由個料庫到諸工地調運單位物資的運價（元 /t）由表 51給出：試求運輸費用最少的合理調運方案。 運輸路線合理化 運輸合理化的實施途徑運輸合理化的實施途徑（ 1）表上作業(yè)法 ① 列出調運物資的供需 (產(chǎn)銷 )平衡表及運價表。 運輸路線合理化 運輸合理化的實施途徑運輸合理化的實施途徑（ 1）表上作業(yè)法 ①②③④⑤⑥② 按最小元素法建立初始調運方案。 運輸路線合理化 運輸合理化的實施途徑運輸合理化的實施途徑（ 1）表上作業(yè)法 ② 按最小元素法建立初始調運方案。根據(jù)得到的初始調運方案，可以計算其運輸費用是： S=1300+4600+3400+2100+10300+5300=8600（元） 運輸路線合理化 運輸合理化的實施途徑運輸合理化的實施途徑（ 1）表上作業(yè)法 ?最優(yōu)方案的數(shù)字表征 檢驗數(shù)?閉回路從理論上得知 :對于表上作業(yè)法的初始方案來說，從調運方案表上的一個空格出發(fā)，存在一條且僅存在一條以該空格（用 xij表示）為起點，以其它填有數(shù)字的點為其它頂點的閉合回路，簡稱閉回路。這個閉合回路具有下列性質：（ 2） 閉合回路是一條封閉折線，每一條邊都是水平或垂直的（ 1）每個頂點都是轉角點（ 3） 每一行（列）若有閉合回路的頂點，則必有兩個。 運輸路線合理化 運輸合理化的實施途徑運輸合理化的實施途徑（ 1）表上作業(yè)法 只有從空格出發(fā)，其余各轉角點所對應的方格內均填有數(shù)字時，所構成的閉合回路，才是我們這里所說的閉回路；另外，過任一空格的閉合回路不僅是存在的，而且是唯一的。以表 512給定的初始調運方案為例，說明閉回路的性質。表 512中給出了空格（ 1， 1）和（ 3， 1）所形成的閉回路：（ 1， 1） （ 1， 3） （ 2， 3） （ 2， 1） （ 1， 1）（ 3， 1） （ 2， 1） （ 2， 3） （ 1， 3） （ 1， 4） （ 3， 4） （ 3， 1） 運輸路線合理化 運輸合理化的實施途徑運輸合理化的實施途徑（ 1）表上作業(yè)法 在調運方案內的每個空格所形成的閉回路上，作單位物資的運量調整，可以計算出相應的運費是增加還是減少的。我們把所計算出來的每條閉回路上調整單位運量而使運輸費用發(fā)生變化的增減值，稱其為檢驗數(shù)。如果檢驗數(shù)小于零，表示在該空格的閉回路上調整運量使運費減少；相反，如果檢驗數(shù)大于零，則會使運費增加。 運輸路線合理化 運輸合理化的實施途徑運輸合理化的實施途徑（ 1）表上作業(yè)法 有了檢驗數(shù)這一概念，我們就可以想到，對于 求運費最小 的物資調運問題來說，如果所有空格的檢驗數(shù)都大于零，那么如果再對調運方案進行任何調整，都會增加運輸費用，因此調運方案是否是最優(yōu)方案的判定準則就是： 初始調運方案，如果它所有的檢驗數(shù)都是非負的，那么這個初始調運方案一定最優(yōu)。否則，這一調運方案不一定是最優(yōu)的。 運輸路線合理化 運輸合理化的實施途徑運輸合理化的實施途徑（ 1）表上作業(yè)法 ③ 采用位勢法計算初始方案每個空格的閉回路的檢驗數(shù) Cij 。設 Cij（ i=1， 2， 3； j=1， 2， 3， 4）表示變量 xij相應的運價，我們將初調運方案中填有數(shù)值方格的 Cij分解成兩部分： Cij =Ui+Vj 其中 Ui和 Vj分別稱為該方格對應于 i行和 j列的位勢量。 運輸路線合理化 運輸合理化的實施途徑運輸合理化的實施途徑（ 1）表上作業(yè)法 ③ 采用位勢法計算初始方案每個空格的閉回路的檢驗數(shù) Cij 。 運輸路線合理化 運輸合理化的實施途徑運輸合理化的實施途徑（ 1）表上作業(yè)法 ③ 采用位勢法計算初始方案每個空格的閉回路的檢驗數(shù) Cij 。減 運輸路線合理化 運輸合理化的實施途徑運輸合理化的實施途徑（ 1）表上作業(yè)法 ④⑤ 檢查檢驗數(shù)，調整方案直到最優(yōu)。 運輸路線合理化 運輸合理化的實施途徑運輸合理化的實施途徑（ 1）表上作業(yè)法 ④⑤ 檢查檢驗數(shù)，調整方案直到最優(yōu)。S（新）=3500+10200+8100+1300+4600+5300=8500 （元）S（初）=1300+4600+3400+2100+10300+5300=8600（元） 運輸路線合理化 運輸合理化的實施途徑運輸合理化的實施途徑（ 2）圖上作業(yè)法 例 2 有某物資 7萬噸，由發(fā)點 A A A3發(fā)出，發(fā)量分別為 1（萬噸），運往收點 B B B B4，收量分別為 1（萬噸），收發(fā)量平衡，交通圖如圖 510所示，問應如何調運，才使噸公里最小？ 運輸路線合理化 運輸合理化的實施途徑運輸合理化的實施途徑（ 2）圖上作業(yè)法 ① 用 “ 去線破圈 ” 的方法，作一個沒有對流的流向圖。 運輸路線合理化 運輸合理化的實施途徑運輸合理化的實施途徑（ 2）圖上作業(yè)法 ② 檢查有無迂回，如果沒有迂回，這個初始方案就是最優(yōu)方案。如果其中某一圈有迂回，這個方案就不是最優(yōu)方案，需要改進。圈 A1B1B2A3B4v總長為 23公里（ 5+4+4+3+7=23）v外流長為 5+4+3=12公里v1223/2，需要調整 運輸路線合理化 運輸合理化的實施途徑運輸合理化的實施途徑（ 2）圖上作業(yè)法 ② 檢查有無迂回，如果沒有迂回，這個初始方案就是最優(yōu)方案。如果其中某一圈有迂回，這個方案就不是最優(yōu)方案，需要改進。圈 B2A2B3A3v總長為 13公里（ 3+2+4+4=13）v外流長為 2公里v213/2， 313/2，不需要調整v內流長為 3公里 運輸路線合理化 運輸合理化的實施途徑運輸合理化的實施途徑（ 2）圖上作業(yè)法 ② 檢查有無迂回，如果沒有迂回，這個初始方案就是最優(yōu)方案。如果其中某一圈有迂回，這個方案就不是最優(yōu)方案，需要改進。v對圈 A1B1B2A3B4的調整方法是： 在外圈的各流量中，減去外圈的最小流量 1萬噸；然后在內圈的各流量中加上 1萬噸，在此圈中，因無內流量，所以無處可加；另外，再在無流量的線段上，新添上內圈流量 1萬噸，這樣得出新的流量圖 。 運輸路線合理化 運輸合理化的實施途徑運輸合理化的實施途徑（ 2）圖上作業(yè)法 ② 檢查有無迂回，如果沒有迂回，這個初始方案就是最優(yōu)方案。如果其中某一圈有迂回，這個方案就不是最優(yōu)方案，需要改進。 運輸路線合理化 運輸合理化的實施途徑運輸合理化的實施途徑（ 2）圖上作業(yè)法 ② 檢查有無迂回，如果沒有迂回，這個初始方案就是最優(yōu)方案。如果其中某一圈有迂回，這個方案就不是最優(yōu)方案，需要改進。v新的流量圖中，在 A1B1B2A3B4圈內， 內流長 為： 4+7=11公里，外流長 為： 5公里，都不超過全圈長（ 23公里）的一半；在B2A2B3A3圈內， 內流長 為 3公里， 外流長 為 4+2=6公里，也都沒有超過全圈長（ 13公里）的一半， 因此，這個流向圖沒有迂回現(xiàn)象，是本問題的最優(yōu)調運方案 ，總運輸力為：17+25+14+23+21=29噸公里。講課完畢講課完畢謝謝觀看 /歡迎下載BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES. BY FAITH I BY FAITH