最短路徑、指派、運(yùn)輸問題

1、1,2,3,指派問題,一、指派問題數(shù)學(xué)模型,引例：今有4輛裝載不同貨物的待卸車，派班員要分派給4個(gè)裝卸班組，每個(gè)班組卸1輛，由于各個(gè)班組的技術(shù)專長不同，各個(gè)班組卸不同車輛所需的時(shí)間如下表，問派班員應(yīng)該如何分配卸車任務(wù)可使卸車所花費(fèi)的時(shí)間最小？,4,二、指派問題算法匈牙利算法,定理：如果對系數(shù)矩陣任意行或列的各元素（cij）分別減去該行或列的最小元素，得到新矩陣（bij），則以新矩陣為系數(shù)的指派問題的最優(yōu)解和原問題的最優(yōu)解相同。,5,匈牙利算法步驟：,第一步：使系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)0元素： （1）從系數(shù)矩陣的每行元素減去該行的最小元素； （2）再從所得矩陣的每列元素中減去該列的最小

2、元素。 若某行（列）已有0元素，那就不必再減了。引例的計(jì)算為：,6,第二步：進(jìn)行試指派以尋求最優(yōu)解。 （1）進(jìn)行行檢驗(yàn)：從只有一個(gè)0元素的行開始，給這個(gè)0元素加（），記作（0）；再劃去（0）所在列的其它0元素，記作。若遇到有兩個(gè)0元素以上的行，先放下。 （2）進(jìn)行列檢驗(yàn)：給只有一個(gè)0元素的列0元素加（），記作（0）；然后劃去（0）所在行的0元素，記作。 （3）再對兩個(gè)以上0元素的行和列標(biāo)記，任意取一個(gè)加（）。,若（0）的個(gè)數(shù)為n個(gè)，則得出最優(yōu)解，否則轉(zhuǎn)第三步。,7,第三步：若mn，作最少的直線覆蓋所有的0元素，以確定在該系數(shù)矩陣中能找到最多的獨(dú)立元素，按下列步驟進(jìn)行： （1）對沒有(0)的行打

3、號； （2）對已打號的行中所在列打號； （3）再對打有號的列中，含(0)元素的行打號； （4）重復(fù)(2)、(3)直到得不出新的打號的行、列為止。 （5）對沒有打號的行畫一橫線，有打號的列畫一縱線， 這就得到覆蓋所有0元素的最少直線數(shù)。,8,第四步：在沒有被直線覆蓋的部分元素中找出最小元素，然后： （1）對沒有畫橫線的行中各元素中減去這一最小元素； （2）在打列中各元素加上這個(gè)最小元素； 目的是保證原來的0元素不變，這樣得到新系數(shù)矩陣（它的最 優(yōu)解與原問題相同）。 （3）若得到n個(gè)獨(dú)立的0元素，則問題已取得最優(yōu)解，否則再 回到第三步重復(fù)進(jìn)行。,1,-1,-1,+1,最優(yōu)解為c13+c21+c34

4、+c42=20此類問題有多個(gè)解結(jié)構(gòu)（指派方案）？,9,例：某商業(yè)公司計(jì)劃開辦五家新商店。為了盡早建成營業(yè)，商業(yè)公司決定由5家建筑公司分別承建。已知各建筑公司對新商店的建造費(fèi)用報(bào)價(jià)如下圖所示。商業(yè)公司應(yīng)對5家公司怎樣分配建造任務(wù)，才能使總的建造費(fèi)用最少？,10,11,（1）目標(biāo)函數(shù)求最大值的指派問題,三、其它指派問題,對于此問題可做一個(gè)新的矩陣B=(bij)。找出原矩陣的最大元素m，令B=(bij)=m-cij,12,例：需要分派5人去做5項(xiàng)工作，每人做各項(xiàng)工作的能力評分見表，應(yīng)如何分派，才能使總得分最大？,13,（2）非標(biāo)準(zhǔn)指派問題,1、人數(shù)和事數(shù)不等的指派問題； 若人少事多，則虛擬人，系數(shù)為

5、0.若人多事少，則虛擬事，系數(shù)為0.,14,（2）非標(biāo)準(zhǔn)指派問題,2、一個(gè)人可做幾件事的指派問題； 可將該人化作相同的幾個(gè)人來接受指派。這幾個(gè)人做同一件事的費(fèi)用系數(shù)當(dāng)然一樣。,15,（2）非標(biāo)準(zhǔn)指派問題,3、某事一定不能由某人做的指派問題。 可將相應(yīng)的費(fèi)用系數(shù)取做足夠大的數(shù)M。,16,例：某商業(yè)公司計(jì)劃開辦五家新商店。為了盡早建成營業(yè)，商業(yè)公司決定由5家建筑公司分別承建。已知各建筑公司對新商店的建造費(fèi)用報(bào)價(jià)如下圖所示。商業(yè)公司應(yīng)對5家公司怎樣分配建造任務(wù)，才能使總的建造費(fèi)用最少？,17,18,對于上述問題，為了保證工程質(zhì)量，經(jīng)研究決定，舍棄建筑公司A4和A5，而讓技術(shù)力量較強(qiáng)的建筑公司A1、A

6、2、A3來承建。根據(jù)實(shí)際情況，可以允許每家建筑公司承建一家或兩家商店。求使總共費(fèi)用最少的指派方案。,19,指派問題復(fù)習(xí),1、某物流公司安排四個(gè)人：甲、乙、丙、丁去完成四項(xiàng)任務(wù)A、B、C、D，他們完成任務(wù)所需時(shí)間如表所示，問應(yīng)指派何人去完成何工作，所需總時(shí)間最少？,20,2、現(xiàn)有4份工作，6個(gè)人應(yīng)聘，由于個(gè)人的技術(shù)專長不同，他們承擔(dān)各項(xiàng)工作所需時(shí)間如表所示，且規(guī)定每人只能做一項(xiàng)工作，每一項(xiàng)工作只能由一個(gè)人承擔(dān)，試求總時(shí)間最少的指派方案。,21,22,運(yùn)輸問題,引例：某公司設(shè)有A1、A2、A3三個(gè)加工廠，產(chǎn)量分別為：9噸、5噸、7噸；有B1、B2、B3、B4四個(gè)銷售點(diǎn)，銷量分別為：3噸、8噸、4噸

7、、6噸；從各工廠到銷售點(diǎn)的單位產(chǎn)品的運(yùn)價(jià)為下表所示，問該公司應(yīng)該如何調(diào)運(yùn)產(chǎn)品使總運(yùn)費(fèi)最少？,23,6.1 運(yùn)輸問題線性規(guī)劃模型,某公司有m個(gè)產(chǎn)地A1，A2， ，Am，產(chǎn)量分別為a1，a2， ，am；有n個(gè)銷售地B1，B2， ，Bn，銷量分別為b1，b2， ，bm；從產(chǎn)地Ai到銷地Bj的單位產(chǎn)品的運(yùn)價(jià)為Cij，問該公司應(yīng)該如何調(diào)運(yùn)產(chǎn)品使總運(yùn)費(fèi)最少？,前提條件：,產(chǎn)量與銷量平衡,解：,設(shè)產(chǎn)地Ai到銷地Bi的運(yùn)量為xij，由問題構(gòu)造運(yùn)量平衡表,可以知道：,（1）產(chǎn)銷平衡,（2）Ai運(yùn)出量等于產(chǎn)量,（3）Bj運(yùn)入量等于銷量,將問題歸納為線性規(guī)劃問題：,約束方程,目標(biāo)函數(shù),（1）所有的約束條件（不包括非

8、負(fù)約束）都是等式。 （2）產(chǎn)量之和等于銷量之和。 （3）運(yùn)輸問題顯然是一個(gè)線性規(guī)劃問題，可以用學(xué)過的單純形法求解，但求解時(shí)對每一個(gè)等式必須加上一個(gè)人工變量（參考當(dāng)約束條件方程為等式約束時(shí)求初始基本可行解的方法），這樣將使一個(gè)很小規(guī)模的運(yùn)輸問題變得較為煩瑣。,表上作業(yè)法是一種迭代算法 ，也是從先求出初始基本可行解，然后用檢驗(yàn)數(shù)判定是否最優(yōu)解，若是就停止計(jì)算，否則就要對解進(jìn)行調(diào)整、判定，直到求出最優(yōu)解為止。因?yàn)殛P(guān)于以上計(jì)算都可以在產(chǎn)銷平衡表中進(jìn)行，所以叫表上作業(yè)法。,一般單純形法,表上作業(yè)法,簡便方法,6.2 初始基本可行解的求法,運(yùn)輸問題有m+n個(gè)約束條件、m*n個(gè)變量。在運(yùn)輸問題中有一個(gè)是多余

9、的，所以起作用的約束只有m+n-1個(gè)。這是因?yàn)檫\(yùn)輸問題約束條件方程中前m個(gè)約束相加正好得出一個(gè)與后n個(gè)約束相加完全相等似的約束，這說明約束條件中起作用的約束只有m+n-1個(gè)。,相關(guān)知識,下面的變量就構(gòu)成一個(gè)閉回路。盡管閉回路有多種形式，但是所有“連線”不是垂直就是平行，這樣才符合行列一個(gè)變另一個(gè)不變的要求；“連線”不能是“斜線”，因?yàn)橹挥行辛腥兓瘯r(shí)才出現(xiàn)“斜線”。,相關(guān)定理,利用前面相關(guān)知識、閉回路概念及相關(guān)定理即可求出運(yùn)輸問題的初始基本可行解。,一、西北角法,西北角法步驟： （1）將運(yùn)價(jià)表和平衡表合并為綜合表，將運(yùn)價(jià)Cij左下角，運(yùn)量xij標(biāo)在右上角。,（2）由下式?jīng)Q定 左上角變量 的值，

10、并將 這個(gè)數(shù)字標(biāo) 在對應(yīng)運(yùn)費(fèi)的右上角。,（3）在填數(shù)的格子所在的行或列應(yīng)該為0的格子上打“”； 若行或列都應(yīng)該取0，則在行上打“”后，就不能在列 上打“”；反之，在列上“”后就不能在行上打“”。,（4）對沒有填數(shù)及打“”的地方重復(fù)上述步驟，若剩余空格 對應(yīng)的變量應(yīng)該取0，則應(yīng)寫上0，而不能打“”，以保 證初始解的個(gè)數(shù)為m+n-1個(gè)。,得到可行解x11=3,x12=6,x22=2,x23=3,x33=1,x34=6. z=2*3+9*6+3*2+4*3+2*1+5*6=110,二、最小元素法,西北角法不足之處是只滿足了約束方程，沒圍繞目標(biāo)函數(shù)處理問題，即沒考慮Cij值。若將Cij考慮進(jìn)去，得到的

11、基本可行解就會使目標(biāo)函數(shù)更小些，即更接近最優(yōu)解，也使迭代次數(shù)減小。,利用西北角法思路，但取值是從Cij最小的位置開始。,（1）從運(yùn)費(fèi)（一般用cij表示）取最小值的空格開始（若有幾個(gè)地方同時(shí)達(dá)到，可任選一個(gè)）。 （2）與它對應(yīng)的變量按照西北角法取最大值。 （3）在不可能分配運(yùn)量的地方畫“”，以此類推，直到選夠m+n-1個(gè)變量為止。 （4）若只剩下一行或一列未填數(shù)和打“”的格子時(shí)，只能填數(shù)不能打“”，目的是保證解的個(gè)數(shù)為m+n-1個(gè)。,規(guī)則：,得到可行解x21=3,x12=5,x32=3,x33=4,x14=4,x34=2. z=1*3+9*5+4*3+2*4+7*4+2*2=100,最小元素法的

12、缺點(diǎn)是：為節(jié)省一處的費(fèi)用，有時(shí)要造成其它處多花幾倍的運(yùn)費(fèi)，,三、差值法,某地產(chǎn)品若不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有一個(gè)差額，差額越大，說明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加越多，因而對差額最大處，就應(yīng)當(dāng)采用最小運(yùn)費(fèi)調(diào)運(yùn)。,差值法步驟： （1）將運(yùn)價(jià)表和平衡表合并為新的綜合表，在新綜合表中包含 最下的差值行和最右的差值列。 （2）在表中分別計(jì)算出各行和各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的 差額，并填入該表的最右列和最下行。 （3）從最下的差值行和最右的差值列中選出最大者，選擇最大 者所在行或列中的最小Cij元素。 （4）按照西北角法的思路進(jìn)行標(biāo)示，然后依次對表中未標(biāo)示的 元素再分別計(jì)算出各行、

13、各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的 差額，再填入該表的最右列和最下行。 （5）重復(fù)第一、二步。直到給出初始解為止。用此法給出例1 的初始解列于下表。,產(chǎn)地Ai,銷地Bi,運(yùn)價(jià),銷量,產(chǎn)量,A1,A2,A3,B1,B2,B3,2,9,10,1,3,4,8,4,2,3,8,4,9,5,7,B4,7,2,5,6,21,3,5,5,3,4,1,選擇最大差值所在行或列的最小Cij可以避免將運(yùn)量調(diào)配到同一行或同一列的次小的空格中去；另外，最小元素法的規(guī)則在差值法中仍然適用。,差值,差值,1,1,2,3,5,1,2,得到可行解x11=3,x12=5,x32=3,x33=4,x14=1,x24=5. z=2*3+9

14、*5+4*3+2*4+7*1+2*5=88,定理：西北角法、最小元素法、差值法得到的xij值是一組基 本可行解，沒有畫“”的地方對應(yīng)變量正好是基變量。,定理：任何運(yùn)輸問題都有最優(yōu)解。 一是有唯一最優(yōu)解；二是有無限多個(gè)最優(yōu)解,6.3 求檢驗(yàn)數(shù)的求法,線性規(guī)劃中，通過檢驗(yàn)數(shù)cj-zj非負(fù)來判定最小化目標(biāo)函數(shù)的基本可行解是最優(yōu)解。針對特殊的運(yùn)輸問題，判定基本可行解是否最優(yōu)仍然采用線性規(guī)劃準(zhǔn)則，只是求檢驗(yàn)數(shù)有獨(dú)特的方法。,如何求運(yùn)輸問題的檢驗(yàn)數(shù)有兩種方法： （1）閉回路法 （2）位勢法,一、閉回路法,定理：運(yùn)輸問題的表上作業(yè)法中，任一個(gè)非基變量都能和若干個(gè)基變量構(gòu)成唯一的閉回路。,示例：以上面最小元素

15、法的基本可行解為例，求非基變量檢驗(yàn)數(shù)。 23=c11-c14+c24-c21=2-7+2-1=-4，同樣， 23=2， 。將檢驗(yàn)數(shù)另畫一張表。從表中看出，存在負(fù)的檢驗(yàn)數(shù)，不是最優(yōu)解。,把運(yùn)量給x11處分配一個(gè)單位，看看會對目標(biāo)函數(shù)值帶來什么影響（增加還是減少）。,由于表上作業(yè)法中表的每行上分配的運(yùn)量之和是一個(gè)常數(shù)（等于對應(yīng)產(chǎn)地的產(chǎn)量），所以若給x13（分配前x11=0，是非基變量）分配了1個(gè)單位的運(yùn)量，將增加110個(gè)單位的運(yùn)費(fèi)；同時(shí)為保持產(chǎn)量平衡，對應(yīng)的x14處就要減少一個(gè)單位的運(yùn)量，這樣將減少17個(gè)單位的運(yùn)費(fèi)；與此同時(shí)，由于表上作業(yè)法中表的每列上分配的運(yùn)量之和是一個(gè)常數(shù)（等于對應(yīng)銷地的銷量）

16、所以當(dāng)x14減少了1個(gè)單位的運(yùn)量時(shí)，為保持銷量平衡x24將增加1個(gè)單位的運(yùn)量，這樣將增加12個(gè)單位的運(yùn)費(fèi)；同理可知對應(yīng)的x33處就要減少一個(gè)單位的運(yùn)量，將減少12個(gè)單位的運(yùn)費(fèi)。綜上所述，目標(biāo)函數(shù)值增加了10+2，同時(shí)又減少了7+2。所以目標(biāo)函數(shù)總變化量為：（10+2）-（7+2）=3。這就是說，每給x11分配一個(gè)單位的運(yùn)量，目標(biāo)函數(shù)（總運(yùn)費(fèi)）將增加一個(gè)單位。因此在表上作業(yè)法中對檢驗(yàn)數(shù)大于零的地方不再分配運(yùn)量，若所有非基變量的檢驗(yàn)數(shù)全大于零，任何形式的運(yùn)量調(diào)整只能使目標(biāo)函數(shù)值增加，所以算法終止，此時(shí)的解就是最優(yōu)解。請大家參考上面的例子仔細(xì)想一想，若非基變量的檢驗(yàn)數(shù)小于零，是否應(yīng)該給該處分配運(yùn)量把

17、非基變量調(diào)整成基變量？答案是肯定的，為什么？,二、位勢法,用閉回路法求檢驗(yàn)數(shù)，需要對每一個(gè)非基變量（表上畫“”地方）尋找閉回路，然后再去求檢驗(yàn)數(shù)，當(dāng)一個(gè)運(yùn)輸問題的產(chǎn)銷點(diǎn)很多時(shí)，這種方法的計(jì)算工作量是很大的，所以介紹一下位勢法。,基本原理是： 針對基變量Xij給定系數(shù)ui和vj，建立方程組： ui+vj=cij 知道基變量有m+n-1個(gè)，所以系數(shù)ui和vj的個(gè)數(shù)也為m+n-1個(gè)，那么方程組的方程數(shù)也為m+n-1個(gè)，解方程組即可求出ui和vj。,定理： 對于非基變量的檢驗(yàn)數(shù)有： ij=cij-ui-vj。 簡單證明： 根據(jù)閉回路法和方程組有：,表上作業(yè)法是將方程組求出的解ui和vj分別列在表的左邊

18、和上邊，然后將利用定理求出的檢驗(yàn)數(shù)列在相應(yīng)的格子中。（書86頁例題）,40,6.4 方案的調(diào)整,前面已經(jīng)知道，在已求得的基本可行解及檢驗(yàn)數(shù)的平衡表中，若有負(fù)的檢驗(yàn)數(shù)，此時(shí)的解就不是最優(yōu)解，應(yīng)進(jìn)行調(diào)整，以求出另外一組基本可行解，使目標(biāo)函數(shù)值下降。求出下一組基本可行解，首先要決定哪一個(gè)非基變量要進(jìn)入基中去，哪一個(gè)要被換出來，調(diào)整量是多少，然后如何進(jìn)行調(diào)整。,1 確定換入變量 同單純形法一樣，在負(fù)的檢驗(yàn)數(shù)中，一般要取檢驗(yàn)數(shù)最小的 非基變量作為換入變量。,2 確定換出變量和調(diào)整量 由定理（課本定理4），由換入變量（此時(shí)還是非基變量）和 一組基變量可以組成唯一的一個(gè)閉回路，則以換入變量為起點(diǎn)，可以找到唯

19、一的閉回路，取此回路偶數(shù)頂點(diǎn)中基變量取值最小的做為換出變量，調(diào)整量即為此基變量的值。,3 調(diào)整方法 （1）上述閉回路以外的變量的值均不變。 （2）上述閉回路寄頂點(diǎn)上的變量均加上調(diào)整量，偶頂點(diǎn)上的變量均減去調(diào)整量。,6.5 應(yīng)用問題,無窮多最優(yōu)解,退化,產(chǎn)銷不平衡問題,產(chǎn)量、銷量不確定問題,表上作業(yè)法如何處理現(xiàn)實(shí)中復(fù)雜現(xiàn)象,表上作業(yè)法兩個(gè)特殊問題,有轉(zhuǎn)運(yùn)點(diǎn)問題,復(fù)合問題,一、表上作業(yè)法兩個(gè)特殊問題的處理,（1）無窮多個(gè)最優(yōu)解問題：產(chǎn)銷平衡的運(yùn)輸問題必定存在最優(yōu)解（唯一或無窮）。若某個(gè)非基變量的檢驗(yàn)數(shù)為0，則有無窮個(gè)最優(yōu)解，處理方式是將此非基變量作為換入變量，即以此作閉回路，按照調(diào)整規(guī)則找出換出變

20、量，從而得到另一個(gè)最優(yōu)解，不斷迭代。,（2）退化問題：用表上作業(yè)法時(shí)在求初始解或者調(diào)整時(shí)會出現(xiàn)退化問題，處理方法是在相應(yīng)處用0進(jìn)行運(yùn)量處理，即必須保證基變量個(gè)數(shù)為m+n-1個(gè)。 （教材8890頁）,二、表上作業(yè)法處理現(xiàn)實(shí)中幾種復(fù)雜現(xiàn)象,（1）總產(chǎn)量大于總銷量，即 可虛增一個(gè)銷售點(diǎn)，令其銷量為a-b。實(shí)際問題中可以看 作存貯點(diǎn)，若不考慮存貯費(fèi)用，則單位運(yùn)費(fèi)為零；若考慮， 則單位運(yùn)費(fèi)就等于單位存貯費(fèi)Ci 。,1、產(chǎn)銷不平衡問題。,（2）總產(chǎn)量小于總銷量，即 可虛增一個(gè)產(chǎn)地，令其產(chǎn)量為b-a，實(shí)際問題中可以看作 缺貨量。若不考慮缺貨費(fèi)用，則單位運(yùn)費(fèi)為零；若考慮，則單 位運(yùn)費(fèi)就等于每單位缺貨費(fèi)用cj

21、，若某地不能缺貨，則對應(yīng) 的缺貨費(fèi)用為大M（是一個(gè)非常大的正數(shù)），表明若缺貨總費(fèi) 用將是任意大。,通過以上兩步，可以把產(chǎn)銷不平衡問題化為產(chǎn)銷平衡問題用表 上作業(yè)法求解。,示例：,此處Ci5為0，但有時(shí)根據(jù)具體情況定。,針對產(chǎn)量小于銷量可以同樣處理,2、產(chǎn)量（發(fā)送量）、銷量不確定問題的處理,在有些問題中，給出某產(chǎn)地的產(chǎn)量（銷量）在一個(gè)數(shù)字范圍內(nèi)，如（aaib或aaib ）。 這種情況下就要把一個(gè)產(chǎn)地拆成兩個(gè)“產(chǎn)地”，一個(gè)產(chǎn)量為a，另一個(gè)產(chǎn)量為b-a，單位運(yùn)費(fèi)參照上面所講的內(nèi)容設(shè)置。如課本92頁例題7中A1 、A3 兩個(gè)產(chǎn)地均屬這種情況。對需求量不確定的問題也可以參照上面的方法進(jìn)行處理，化為確定型的標(biāo)準(zhǔn)運(yùn)輸問題。,示例：,某物資從產(chǎn)地A1、A2、A3到銷