運(yùn)籌學(xué)學(xué)習(xí)(自制筆記)第3章 運(yùn)輸問(wèn)題

1、第3章 運(yùn)輸問(wèn)題3.1標(biāo)準(zhǔn)運(yùn)輸問(wèn)題及模型3.1.1標(biāo)準(zhǔn)運(yùn)輸問(wèn)題：某種物資有m個(gè)產(chǎn)地Ai（i=1,2,m）,產(chǎn)量分別為ai，另有n個(gè)銷地Bj（j=1,2,n），銷量（需求量）分別為bj，現(xiàn)在需要把這種物資從各個(gè)產(chǎn)地運(yùn)送到各個(gè)銷地，已知從Ai到Bj的單位運(yùn)價(jià)(或運(yùn)距)為cij，假定產(chǎn)量總數(shù)等于銷量總數(shù)，即,問(wèn)就如何組織調(diào)運(yùn)，才能使總運(yùn)費(fèi)（或總運(yùn)輸量）最省?3.1.2標(biāo)準(zhǔn)運(yùn)輸問(wèn)題的有關(guān)信息表單位運(yùn)價(jià) 銷地或運(yùn)距產(chǎn)地B1B2Bn產(chǎn)量A1c11c 12c 1na1A2c 21c 22c 2na2Amc m1c m2c mnamb1b2bn3.1.3標(biāo)準(zhǔn)運(yùn)輸問(wèn)題的數(shù)學(xué)模型 設(shè)xij為從產(chǎn)地Ai運(yùn)到銷地Bj

2、的物資數(shù)量（i=1,2,m；j=1,2,n），由于從Ai運(yùn)出的物資總量等于Ai的產(chǎn)量，運(yùn)到的物資總量等于的銷量，得模型如下： minZ= s.t. 且有 即滿足產(chǎn)銷平衡條件，故此模型描述的是產(chǎn)銷平衡運(yùn)輸問(wèn)題。3.1.4標(biāo)準(zhǔn)運(yùn)輸問(wèn)題的特點(diǎn)平衡條件下的運(yùn)輸問(wèn)題必有最優(yōu)解此問(wèn)題是一個(gè)有m×n個(gè)變量，m+n個(gè)等型約束條件的線性規(guī)劃最小化問(wèn)題，由于目標(biāo)函數(shù)不可能為負(fù)，故有下界存在，而是問(wèn)題的一組可行解，因此一定有最優(yōu)解。既是線性規(guī)劃問(wèn)題，無(wú)疑可用單純形法求解，但其數(shù)學(xué)模型自身結(jié)構(gòu)有其特殊性，可以利用更簡(jiǎn)便的表上作業(yè)法求解。標(biāo)準(zhǔn)運(yùn)輸問(wèn)題約束方程組的系數(shù)矩陣運(yùn)輸問(wèn)題是一個(gè)具有m×n個(gè)變量

3、，m+n個(gè)等型約束條件的線性規(guī)劃問(wèn)題，問(wèn)題的約束方程組的系數(shù)矩陣A是一個(gè)只有0和1兩個(gè)數(shù)值的稀疏矩陣，對(duì)應(yīng)的列只有第i行和第m+j行為1，其余各行皆為0。標(biāo)準(zhǔn)運(yùn)輸問(wèn)題的基變量總數(shù)為m+n-1?？梢宰C明系數(shù)矩陣A和增廣矩陣A的秩為m+n-1。增廣矩陣A的前m行相加之和減后n行相加之和等于0，說(shuō)明m+n個(gè)行向量線性相關(guān)，A和A的秩都小于m+n；另外，可以在A中找出一個(gè)行列式的值不為0的m+n-1階方陣D(取第二行至第n行的前n列及所在的列，其中i=2，3，m,得到一個(gè)副對(duì)角線上為兩單位矩陣，上方為零矩陣的矩陣，顯然，此矩陣滿秩)，所以,A和A的秩為m+n-1。 m+n-1個(gè)變量構(gòu)成基變量的充要條件

4、是它們不構(gòu)成回路。 運(yùn)輸模型中能排列成的變量組稱為一個(gè)閉回路，其中i1,i2,is互不相同，j1,j2,js也互不相同，出現(xiàn)在組中的變量稱為回路的頂點(diǎn)。 由于所對(duì)應(yīng)的列向量?jī)H有第i行和m+j行為1，其余各行皆為0,所以很容易得出 所以，若變量組中若有一部分構(gòu)成回路，則變量組所對(duì)應(yīng)的系數(shù)列向量組必線性相關(guān)。 若變量組中不含任何閉回路，則變量組中至少有一變量的行標(biāo)或列標(biāo)只出現(xiàn)一次，即變量組中必有孤立點(diǎn)。若有孤立點(diǎn)則變量組所對(duì)應(yīng)的所有列向量中只有的ir行或第m+jr行為1，其余各列向量的第ir行或第m+jr行皆為0，變量組所對(duì)應(yīng)的系數(shù)列向量組必線性無(wú)關(guān)。 故得結(jié)論又 所以，m+n-1個(gè)變量構(gòu)成基變量

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

6、是這m+n-1個(gè)變量不包含任何回路，因此，只要定出這m+n-1個(gè)變量的方式能保證它們不包含任何回路即可得出這m+n-1個(gè)變量線性無(wú)關(guān)。由于總變量數(shù)為m×n個(gè)，當(dāng)m和n取值較大時(shí)m×n遠(yuǎn)大于m+n-1，且任一變量均出現(xiàn)在兩個(gè)約束中，為保證所有變量值非負(fù)，的取值不能大于和，所以，可以考慮用“滿值法”，即選擇一個(gè)變量，取。具體作法是：在作業(yè)表中，按某種規(guī)則選擇一個(gè)，若則取，將用所取的具體值替換，劃除第i行其它變量（除前面已經(jīng)定出的變量外），并將變?yōu)椋蝗?，則取，劃除第j列其它變量（除前面已經(jīng)定出的變量外），并將變?yōu)?，然后再在剩余的變量按某種規(guī)則選擇另一個(gè)變量，再運(yùn)用同樣的方法，最后

7、得出m+n-1個(gè)變量和它們的取值,以這m+n-1個(gè)變量為基變量（后面將證明它們確實(shí)可以構(gòu)成基變量），其余被劃除的變量為非基變量，均取值為0，此時(shí)的和都已經(jīng)變?yōu)?，即產(chǎn)銷已經(jīng)達(dá)到平衡。在上述操作中可能會(huì)遇到兩種特殊情況：一種是，此時(shí)可以劃去行也可以劃去列，但不能同時(shí)劃去；另一種情況是產(chǎn)銷已達(dá)平衡，但選取的變量個(gè)數(shù)未達(dá)m+n-1，此時(shí)可將選取未劃去的變量，并取值為0?？梢宰C明，用“滿值法”得到的解是基可行解，證明如下：假設(shè)用“滿值法”選定的m+n-1個(gè)變量可以包含某一個(gè)回路，那么取這個(gè)回路中最先定出的一個(gè)變量，這個(gè)變量必與后來(lái)定出的一個(gè)變量同行另一個(gè)變同列，這和定出變量后劃除了第i行或第j列的其它變量（除前面已經(jīng)定出的變量外）相矛盾，所以用“滿值法”定出的m+n-1個(gè)變量不包含任何回路，所以這m+n-1個(gè)變量對(duì)應(yīng)的系數(shù)列向量線性無(wú)關(guān)，即這m+n-1個(gè)系數(shù)列向量是系數(shù)矩陣的一個(gè)基，而“滿值法”既保證了所有約束的成立又保證了所有變量取值非負(fù)，所以用“滿值法”得出的解為基可行解，于是初始方案得以確定。3.2.2最優(yōu)性檢驗(yàn)檢驗(yàn)初始方案是否最優(yōu)方案的過(guò)程就是最優(yōu)