運籌學(xué)學(xué)習(xí)第3章運輸問題

1、第3章運輸問題3.1標(biāo)準(zhǔn)運輸問題及模型3.1.1標(biāo)準(zhǔn)運輸問題：某種物資有 m個產(chǎn)地Ai (i=1,2,m),產(chǎn)量分 別為a，另有n個銷地Bj (j=1,2,n )，銷量(需求量)分別為bj, 現(xiàn)在需要把這種物資從各個產(chǎn)地運送到各個銷地，已知從A到B的單位運價(或運距)為Cij，假定產(chǎn)量總數(shù)等于銷量總數(shù)，即mnaibj,問就如何組織調(diào)運，才能使總運費(或總運輸量)最省 ？i 1j 13.1.2標(biāo)準(zhǔn)運輸問題的有關(guān)信息表單位運價、銷地 或運距B1B2Bn產(chǎn)量A1C11c 12C 1na1A2C 21C 22C 2na?AmC m1C m2C mnamb1b2bnmnaibji 1j 13.1.3標(biāo)準(zhǔn)

2、運輸問題的數(shù)學(xué)模型設(shè)xij為從產(chǎn)地 Ai運到銷地 Bj的物資數(shù)量(i=1,2,m ;j=1,2，,n ),由于從Ai運出的物資總量等于Ai的產(chǎn)量，運到的物資總量等于的銷量，得模型如下：mnminZ=cij xiji 1 j 1nxij ais.t.j1mxijbji1xij 0且有mnaibj Qi 1 j 1即滿足產(chǎn)銷平衡條件，故此模型描述的是產(chǎn)銷平衡運輸問題。3.1.4 標(biāo)準(zhǔn)運輸問題的特點平衡條件下的運輸問題必有最優(yōu)解此問題是一個有mP< n個變量，m+n個等型約束條件的線性規(guī)劃最 小化問題， 由于目標(biāo)函數(shù)不可能為負， 故有下界存在， 而 xij aibj/Q 是問題的一組可行解，因

3、此一定有最優(yōu)解。既是線性規(guī)劃問題，無疑可用單純形法求解，但其數(shù)學(xué)模型自身 結(jié)構(gòu)有其特殊性，可以利用更簡便的表上作業(yè)法求解。標(biāo)準(zhǔn)運輸問題約束方程組的系數(shù)矩陣運輸問題是一個具有mix n個變量，m+n個等型約束條件的線性規(guī) 劃問題，問題的約束方程組的系數(shù)矩陣 A 是一個只有 0和 1 兩個數(shù) 值的稀疏矩陣， xij 對應(yīng)的列 Pij 只有第 i 行和第 m+j 行為 1，其余各 行皆為0。標(biāo)準(zhǔn)運輸問題的基變量總數(shù)為 m+n-1?？梢宰C明系數(shù)矩陣A和增廣矩陣A的秩為m+n-1。增廣矩陣A的前m行相加之和減后n行相加之和等于0,說明 m+n個行向量線性相關(guān)，A和A的秩都小于m+n另外，可以在A 中找出

4、一個行列式的值不為0的m+n-1階方陣D（取第二行至第n行 的前n列及Xii所在的列，其中i=2 , 3,m,得到一個副對角線上為 兩單位矩陣，上方為零矩陣的矩陣，顯然，此矩陣滿秩），所以，A和A的秩為m+n-1。m+n-1個變量構(gòu)成基變量的充要條件是它們不構(gòu)成回路。運輸模型中能排列成 Xi" 燦2,畑2, Xi2j3,川Xisjs,畑的變量組 稱為一個閉回路，其中ii,i 2,i s互不相同，ji,j 2,js也互不相同， 出現(xiàn)在組中的變量稱為回路的頂點。由于Xij所對應(yīng)的列向量Pij僅有第i行和m+j行為1,其余各行 皆為0,所以很容易得出Pi 1 j 1 Pil j 2 Pi2

5、 j 2 Pi2j3Pisjs Pisj 1 0所以，若變量組Xi1j1, Xi2j2, Xi3j3, Xisjs中若有一部分構(gòu)成回路，則 變量組所對應(yīng)的系數(shù)列向量組必線性相關(guān)。若變量組中不含任何閉回路，則變量組中至少有一變量的行標(biāo)或列標(biāo)只出現(xiàn)一次，即變量組中必有孤立點。若有孤立點Xirjr則變量組所對應(yīng)的所有列向量中只有 Pirjr的ir 行或第m+jr行為1,其余各列向量的第ir行或第m+jr行皆為0,變量 組所對應(yīng)的系數(shù)列向量組必線性無關(guān)。故得結(jié)論變量組對應(yīng)的系數(shù)列向量線性無關(guān) 變量組不含任何回路又m+n-1個變量對應(yīng)的系數(shù)列向量線性無關(guān)此m+n-1個變量構(gòu)成基變量所以, m+n-1 個

6、變量構(gòu)成基變量的充要條件是它們不構(gòu)成回路。3.2 運輸問題的表上作業(yè)法表上作業(yè)法也是一種迭代法, 它的基本思想是： 先設(shè)法找出一個 初始方案,然后對方案進行檢驗、調(diào)整,直到得出最優(yōu)方案。這和單 純形法的思想完全一致,但是具體的作法則更加簡捷。3.2.1 初始方案的確定將決策變量 xij 填入運輸信息表的 cij 所在表格（可將 cij 填入右下 角而將 xij 填入中央）,得到所謂的“作業(yè)表” ,下面的操作均在作業(yè) 表中進行。確定初始方案就是找出一個初始基可行解,即定出 m+n-1 個變 量并賦予它們非負的值, 除這 m+n-1 個變量外,其余變量的值皆為 0, 且這 m+n-1 個變量所對應(yīng)

7、的系數(shù)列向量線性無關(guān)。由于上節(jié)已證明 m+n-1 個變量所對應(yīng)的系數(shù)列向量線性無 關(guān)的充要條件是這 m+n-1 個變量不包含任何回路, 因此,只要定出這 m+n-1 個變量的方式能保證它們不包含任何回路即可得出這 m+n-1 個 變量線性無關(guān)。由于總變量數(shù)為mix n個，當(dāng)m和n取值較大時mix n遠大于m+n-1, 且任一變量 xij 均出現(xiàn)在兩個約束中，為保證所有變量值非負， xij 的 取值不能大于aj和bj，所以，可以考慮用“滿值法”，即選擇一個變 量 xij ，取 xij min ai ,bj 。具體作法是：在作業(yè)表中，按某種規(guī)則選擇一個Xjj，若aj bj則 取 xij ai ，將

8、 xij 用所取的具體值替換，劃除第 i 行其它變量（除前 面已經(jīng)定出的變量外），并將bj變?yōu)閎j - aj ；若bj aj ,則取為 bj , 劃除第j列其它變量（除前面已經(jīng)定出的變量外），并將aj變?yōu)閍j - bj ，然后再在剩余的變量按某種規(guī)則選擇另一個變量，再運用同樣的方法，最后得出m+n-1個變量和它們的取值，以這m+n-1個變量為基 變量（后面將證明它們確實可以構(gòu)成基變量） ，其余被劃除的變量為 非基變量，均取值為 0，此時的 aj 和 bj 都已經(jīng)變?yōu)?0，即產(chǎn)銷已經(jīng)達 到平衡。在上述操作中可能會遇到兩種特殊情況：一種是aj bj ，此時可以劃去行也可以劃去列， 但不能同時劃去；

9、 另一種情況是產(chǎn)銷已達 平衡，但選取的變量個數(shù)未達 m+n-1,此時可將選取未劃去的變量， 并取值為 0。可以證明，用“滿值法”得到的解是基可行解，證明如下：假設(shè)用“滿值法”選定的m+n-1個變量可以包含某一個回路，那 么取這個回路中最先定出的一個變量 xjj ，這個變量必與后來定出的 一個變量同行另一個變同列， 這和定出變量 xjj 后劃除了第 j 行或第 j 列的其它變量 （除前面已經(jīng)定出的變量外） 相矛盾，所以用“滿值法” 定出的m+n-1個變量不包含任何回路，所以這m+n-1個變量對應(yīng)的系 數(shù)列向量線性無關(guān)，即這 m+n-1 個系數(shù)列向量是系數(shù)矩陣的一個基， 而“滿值法”既保證了所有約束的成立又保證了所有變量取值非負， 所以用“滿值法”得出的解為基可行解，于是初始方案得以確定。3.2.2 最優(yōu)性檢驗 檢驗初