運籌學學習(自制筆記)第3章 運輸問題

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

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

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

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

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

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

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