運(yùn)輸問題的數(shù)學(xué)模型和應(yīng)用舉例

1、運(yùn)輸問題的數(shù)學(xué)模型和應(yīng)用舉例運(yùn)輸問題的數(shù)學(xué)模型表上作業(yè)法產(chǎn)銷不平衡的運(yùn)輸問題運(yùn)輸問題應(yīng)用舉例 運(yùn)輸問題（Transportation Problem，簡(jiǎn)記為TP）是一類常見而且極其特殊的線性規(guī)劃問題.它最早是從物資調(diào)運(yùn)工作中提出來的，是物流優(yōu)化管理的重要的內(nèi)容之一 。 從理論上講，運(yùn)輸問題也可用單純形法來求解，但是由于運(yùn)輸問題數(shù)學(xué)模型具有特殊的結(jié)構(gòu)，存在一種比單純形法更簡(jiǎn)便的計(jì)算方法 表上作業(yè)法，用表上作業(yè)法來求解運(yùn)輸問題比用單純形法可節(jié)約計(jì)算時(shí)間與計(jì)算費(fèi)用.但表上作業(yè)法的實(shí)質(zhì)仍是單純形法。 1.1 產(chǎn)銷平衡運(yùn)輸問題的數(shù)學(xué)模型1 運(yùn)輸問題的數(shù)學(xué)模型及其特點(diǎn) 設(shè)某種物資共有 m 個(gè)產(chǎn)地 A1，A

2、2，Am，各產(chǎn)地的產(chǎn)量分別是a1，a2 ，am；有n 個(gè)銷地 B1，B2，Bn ，各銷地的銷量分別為b1 ，b2，bn . 假定從產(chǎn)地Ai（i =1，2，m）向銷地Bj（j =1，2，n）運(yùn)輸單位物資的運(yùn)價(jià)是cij ，其中 .問怎樣調(diào)運(yùn)才能使總運(yùn)費(fèi)最小？ 設(shè) xij 表示產(chǎn)地 Ai 運(yùn)往銷地 Bj (i=1,2,m; j=1,2,n) 的運(yùn)量. 銷地產(chǎn)地 B1 B2 Bn產(chǎn)量 A1 x11c11 x12c21 x1n c1n a1 A2 x21c21 x22c22 x2nc2n a2 Am xm1cm1 xm2cm2 xmncmn am銷量 b1 b2 bn 運(yùn)輸表注意 : cij 在左下角

3、xij 在右上角 1.2 運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)平衡運(yùn)輸問題的約束方程系數(shù)矩陣 A矩陣A有m+n行，每行的特點(diǎn)：前m行有n個(gè)1，這n個(gè)1連在一起，其余元素為0；后n行每行有m個(gè)1，其余元素為0。矩陣A有mn列，每一列只有兩個(gè)元素為1，其余元素均為0。列向量Pij =(0,，0，1，0，,0,1,0,0)T，其中兩個(gè)元素1分別處于第i行和第m+j行,即將矩陣A分塊，特點(diǎn)是：前m行構(gòu)成m個(gè)mn階矩陣,而且第k個(gè)矩陣只有第k行元素全為1，其余元素全為0（k=1，m）；后n行構(gòu)成m個(gè)n階單位陣。其中e1是元素全為1的n維行向量，In為n階單位矩陣。定理 1 平衡運(yùn)輸問題必有可行解，也必有最優(yōu)解. 又因

4、為 ，對(duì)于任一可行解有目標(biāo)函數(shù)值 ，對(duì)于求極小化問題，目標(biāo)函數(shù)值有下界，則必有最優(yōu)解. 證明:則取又所以 ，是問題的一個(gè)可行解. 證明：定理2 說明：基可行解包含m+n-1個(gè)基變量.定理 2 平衡運(yùn)輸問題的約束方程系數(shù)矩陣 A 和增廣矩陣 的秩相等，且等于 m+n-1 . 即 2. 由 的第二至m+n行和前n列及 對(duì)應(yīng)的列交叉處元素構(gòu)成m+n-1階方陣D 非奇異。前m行相加之和減去后n行相加之和結(jié)果是零向量，說明m+n個(gè)行向量線性相關(guān)，因此 的秩小于m+n； 證明系數(shù)矩陣A及其增廣矩陣的秩都是m+n-1 因此 的秩恰好等于m+n-1，又D本身就含于A中，故A的秩也等于m+n-1 可以證明：m+

5、n個(gè)約束方程中的任意m+n-1個(gè)都是線性無關(guān)的。定理 3 平衡運(yùn)輸問題的約束方程系數(shù)矩陣 A 的所有各階子式只取 0，1 或 -1 三個(gè)值.定理 4 如果平衡運(yùn)輸問題中的所有產(chǎn)量 ai 和銷量 bj都是整數(shù)，那么，它的任一基可行解都是整數(shù)解.Proof :設(shè) x 是 Ax = b 的任一基可行解，B 為對(duì)應(yīng)的基矩陣，則 其中 Bt 是用 b 中對(duì)應(yīng)的 m+n-1元素替換 B 的第t 列元素得到的矩陣. 顯然，由定理 3 知，det Bt 是個(gè)整數(shù)， det B= ，因此， 都是整數(shù).其基變量為定理 4 如果平衡運(yùn)輸問題中的所有產(chǎn)量 ai 和銷量 bj都是整數(shù)，那么，它的任一基可行解都是整數(shù)解.

6、定義 1 將變量 在調(diào)運(yùn)表中所對(duì)應(yīng)的空格記作 ，下文將稱為格點(diǎn) 或格 ，而 的系數(shù)列向量 也稱作格點(diǎn) 所對(duì)應(yīng)的系數(shù)列向量，若 為基變量，則 稱為基格，否則是非基格。 凡是能排列成（其中 互不相同， 互不相同）形式的變量集合，稱為一個(gè)閉回路，其中諸變量稱為這個(gè)閉回路的頂點(diǎn).定義 2 B1 B2 B3 B4 B5 A1 x11 x12 x13 x14 x15 A2 x21 x22 x23 x24 x25 A3 x31 x32 x33 x34 x35 A4 x41 x42 x43 x44 x45如：變量集合變量集合或格組或格組3、每一行（或列）若有閉回路的頂點(diǎn)，則有兩個(gè)頂點(diǎn)；4、每?jī)蓚€(gè)頂點(diǎn)格子的連線

7、都是水平的或垂直的；1、閉回路中頂點(diǎn)的個(gè)數(shù)必為大于或等于4的偶數(shù).閉回路的幾何特征：2、每一個(gè)頂點(diǎn)格子都是 90轉(zhuǎn)角點(diǎn)； B1 B2 B3 B4 B5 A1 x11 x12 x13 x14 x15 A2 x21 x22 x23 x24 x25 A3 x31 x32 x33 x34 x35 A4 x41 x42 x43 x44 x45思考： 下面的折線構(gòu)成的封閉曲線連接的頂點(diǎn)變量哪些不可能是閉回路？為什麼？（a） （b） （c） （d） （e）閉回路的代數(shù)性質(zhì)：性質(zhì) 1 構(gòu)成閉回路的變量組對(duì)應(yīng)的列向量組必線性相關(guān).證明由直接計(jì)算可知故該向量組線性相關(guān).性質(zhì) 2 分組構(gòu)成閉回路，則該變量組對(duì)應(yīng)的列

8、向量組是線性相關(guān)的.推論 1 若變量組對(duì)應(yīng)的列向量組線性無關(guān)，則該變量組一定不包含閉回路.若變量組 中有一個(gè)部性質(zhì)2的證明可借助性質(zhì)1和高等代數(shù)中“若向量組中部分向量線性相關(guān)，則整個(gè)向量組就線性相關(guān)”的定理得到。在變量組 中，若有某一個(gè)變量 xij 是它所在的行（第 i 行）或列（第 j 列）中出現(xiàn)于（*）中的唯一變量，則稱該變量 xij 是該變量組的一個(gè)孤立點(diǎn).定義 3閉回路的特征注：孤立點(diǎn)不會(huì)是閉回路上的點(diǎn)。 B1 B2 B3 B4 B5 A1 x11 x12 x13 x14 x15 A2 x21 x22 x23 x24 x25 A3 x31 x32 x33 x34 x35 A4 x41

9、x42 x43 x44 x45性質(zhì) 3 若一變量組中不包含任何閉回路，則該變量組必有孤立點(diǎn).注：性質(zhì)3的逆命題不一定成立。變量組 中雖有孤立點(diǎn) ，但包含閉回路 。證明 :用反證法設(shè)變量組（*）對(duì)應(yīng)的列向量組線性無關(guān)，但該變量組包含一個(gè)以其中某些變量為頂點(diǎn)的閉回路，則由性質(zhì) 2 知，這些變量對(duì)應(yīng)的列向量必線性相關(guān)，與假設(shè)矛盾.定理 5 變量組 對(duì)應(yīng)的列向量組線性無關(guān)的充要條件是該變量組中不包含任何閉回路.設(shè)有一組數(shù) 使得 由于變量組（*）中不包含任何閉回路，由性質(zhì) 3 可知其中必有孤立點(diǎn)，不妨設(shè) 為孤立點(diǎn)，但 仍不包含閉回路，其中還有孤立點(diǎn),與前面類似分析可證 k2= 0. 同理得 k3 = k

10、4 = kr = 0這就證明了向量組（*）線性無關(guān).又不妨設(shè) 是（*）在第i1行上唯一的變量，這時(shí)由pij的特征，（1）的左端第i1個(gè)分量和為k1，而右端為0，推論 2 平衡運(yùn)輸問題中的一組 m + n - 1 個(gè)變量能構(gòu)成基變量的充要條件是它不包含任何閉回路. 該推論給出了運(yùn)輸問題的基可行解中基變量的一個(gè)基本特征：基變量組不含閉回路. 這就是基可行解在表上的一個(gè)表現(xiàn)，利用它來判斷 m + n 1 個(gè)變量是否構(gòu)成基變量組，就看它是否包含閉回路.這種方法簡(jiǎn)便易行，它比直接判斷這些變量對(duì)應(yīng)的列向量是否線性無關(guān)要簡(jiǎn)便得多. 利用基變量的這個(gè)特征，將可以導(dǎo)出求平衡運(yùn)輸問題的初始基可行解的一些簡(jiǎn)便方法.

11、 表上作業(yè)法（又稱運(yùn)輸單純形法）是根據(jù)單純形法的原理和運(yùn)輸問題的特點(diǎn)，設(shè)計(jì)的一種在表上運(yùn)算的求解運(yùn)輸問題的簡(jiǎn)便而有效的方法.2 表上作業(yè)法主要步驟：1、求一個(gè)初始調(diào)運(yùn)方案（初始基可行解）；2、判別當(dāng)前方案是否為最優(yōu)，若是則迭代停止，否則 轉(zhuǎn)下一步；3、改進(jìn)當(dāng)前方案，得到新的方案（新的基可行解）， 再返回 2 。 已知某商品有三個(gè)產(chǎn)地A1、A2、A3和四個(gè)銷地B1、B2、B3、B4 ，產(chǎn)量、銷量及單位運(yùn)價(jià)如表.問應(yīng)如何調(diào)運(yùn)，在滿足各銷地需要的情況下，使總的運(yùn)費(fèi)支出為最少？ 一、初始方案的確定1、西北角法 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 2

12、0 A3 5 6 3 4 10 bj 50 25 10 15例 1 50解：51010205規(guī)則:從運(yùn)輸表的西北角開始,優(yōu)先安排編號(hào)小的產(chǎn)地和銷地的運(yùn)輸任務(wù).填了幾個(gè)數(shù)字？注意 : 在填入一個(gè)數(shù)時(shí)，如果行和列同時(shí)飽和， 規(guī)定只劃去一行或一列 BjAi B1 B2 B3 B4 ai A110 5 2 3 50 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15500 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15505101020550例1的初始調(diào)運(yùn)方案（西

13、北角法）2、最小元素法 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15規(guī)則:優(yōu)先安排單位運(yùn)價(jià)最小的產(chǎn)地與銷地之間的運(yùn)輸 任務(wù)，即就近供應(yīng)。40102551010注意 : 在某行（或列）填入一個(gè)數(shù)時(shí)，如果行和列同時(shí)飽和，規(guī)定只劃去該行（或列） BjAi B1 B2 B3 B4 ai A1 1 5 3 2 60 A2 4 1 2 3 20 A3 5 6 1 4 10 bj 50 20 10 100010102050填了幾個(gè)數(shù)字？定理 6 用西北角法或最小元素法得到的初始解是平衡運(yùn)輸問題的基可行

14、解， m+n-1 個(gè)填入數(shù)字的格子對(duì)應(yīng)的是基變量.證明 :首先，得到的初始解 為可行解是顯然的. 其次，由于行列數(shù)共有 m+n ，而按填數(shù)字的方法,除填最后一個(gè)數(shù)時(shí)，劃去一行一列外，每填一個(gè)數(shù)劃去一行或一列. 因此, 共填 m+n-1 個(gè)數(shù). 最后，證明所填 m+n-1 個(gè)數(shù)對(duì)應(yīng)的變量組不含閉回路.用反證法若含有閉回路 不妨設(shè)此閉回路如右（其他情形同理可證） 不妨設(shè)填 后劃去行，故 必須較 先填，且填后劃去的是列，從而 必須較 先填，且填后劃去的是行，而這又說明 必須較 先填，且填后劃去的是列，這又得到 必須較 先填，且填后劃去的是行，這樣就得到了矛盾，所以，填數(shù)的 m+n-1 個(gè)格子對(duì)應(yīng)的變

15、量組不含閉回路，從而，證得了本定理. 關(guān)鍵1、填一個(gè)數(shù)字劃去一行或一列 不產(chǎn)生閉回路； 2、填一個(gè)數(shù)字只劃去一行或一列 填滿m+n-1個(gè)數(shù). BjAi B1 B2 ai A1 8 2 5 A2 3 1 4 bj 6 3 315按最小元素法3、伏格爾法 (元素差額法) 最小元素法的缺點(diǎn)：為了節(jié)省一處的費(fèi)用，有時(shí)造成在其它處要花幾倍的運(yùn)費(fèi)。所以我們考慮若一產(chǎn)地的產(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)增加越多。 因而，對(duì)差額最大處，就優(yōu)先采用最小運(yùn)費(fèi)調(diào)運(yùn)，這就是伏格爾法的基本思想 BjAi B1 B2 ai A1 8 2 5 A2 3 1

16、 4 bj 6 3 差額 6 2 差額 5 1315 BjAi B1 B2 ai A1 8 2 5 A2 3 1 4 bj 6 3 342注：伏格爾法給出的初始解比用最小元素法給出的初始解更接近最優(yōu)解。優(yōu)先安排差額最大的所在行或列的單位運(yùn)價(jià)最小的產(chǎn)地與銷地之間的運(yùn)輸任務(wù)規(guī)則：計(jì)算各行各列的最小元素與次小元素的差額， BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 155052040例1的初始調(diào)運(yùn)方案（伏格爾法）101510二、最優(yōu)性檢驗(yàn)定理 7 設(shè) 是平衡運(yùn)輸問題的一組基變量， 是非基變量，則格

17、組 中必存在唯一的閉回路.證明 : （1）存在性：設(shè)與變量組 所對(duì)應(yīng)的系數(shù)列向量組為 ，則它們一定線性相關(guān)，據(jù)定理5 ，變量組 所對(duì)應(yīng)的格子組必包含閉回路，而且這個(gè)閉回路必包含非基變量 所對(duì)應(yīng)的非基格 。否則，就說基格組（或一部分）構(gòu)成了閉回路，這與基的定義和定理5相矛盾。（2）唯一性：若格組中存在兩個(gè)不同的閉回路，由（1）分析可知，這兩個(gè)閉回路中必都有非基格 ，即 可由基向量組寫出兩種不同的線性組合 。.-知設(shè)據(jù)基變量組所對(duì)應(yīng)的系數(shù)列向量組線性無關(guān)知 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25

18、10 15401025510101、閉回路法+1-1+1-1 BjAi B1 B2 B3 B4 A1 A2 A3檢驗(yàn)數(shù)表-5-10 6 6 6檢驗(yàn)數(shù)檢驗(yàn)數(shù) BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 1540102551010+1-1+1-1閉回路的經(jīng)濟(jì)解釋:在已給出的初始解的表中，可以從任意一個(gè)空格出發(fā)，如 ，若讓 的產(chǎn)品調(diào)運(yùn)1個(gè)單位給 ，為了保持產(chǎn)銷平衡，就要依次調(diào)整：在 處減少一個(gè)單位，在 處增加一個(gè)單位，在 減少一個(gè)單位，即構(gòu)成了以空格 為起點(diǎn)，其它為數(shù)字格的閉回路?？梢娺@樣調(diào)整得運(yùn)

19、費(fèi)的改變量為：2、位勢(shì)法（對(duì)偶變量法）約束方程的系數(shù)矩陣的秩為m+n -1由于xj 的檢驗(yàn)數(shù) ui 稱為行位勢(shì)，vj 稱為列位勢(shì)解上面第一個(gè)方程，將ui、vj代入第二個(gè)方程求出 。 BjAi B1 B2 B3 B4 ui A1 4010 25 5 2 5 3 A2 4 3 10 1 10 2 A3 10 5 6 3 4 vj BjAi B1 B2 B3 B4 A1 A2 A3檢驗(yàn)數(shù)表-5-10 6 6 6-2-120273見 例 1 最小元素法得到的初始基可行解10053-12-5 若 ，則此時(shí)的運(yùn)輸方案為最優(yōu)的 定理 8 檢驗(yàn)數(shù) 與初始給定 的取值無關(guān)。 （下面的證明摘自教材最優(yōu)化方法書后參

20、考文獻(xiàn)1）證明： 引理1 引理2 由此定理可知，我們用位勢(shì)法求檢驗(yàn)數(shù)時(shí)給定初始的Vn=0是合理的，從而計(jì)算出的ij 是唯一的。三、基可行解的改進(jìn) BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 1540102551010 BjAi B1 B2 B3 B4 A1 A2 A3檢驗(yàn)數(shù)表-5-10 6 6 6選擇進(jìn)基變量則取非基變量 xst 為進(jìn)基變量確定出基變量調(diào)整量則基變量 xkl 出基（運(yùn)量擦去）調(diào)整方法：在該閉回路上，奇點(diǎn)運(yùn)量加 ，偶點(diǎn)減去 153010 6 5 4 2010 1-5 6 520

21、 6 6 4 5 6 因?yàn)?，所以此運(yùn)輸方案為最優(yōu)方案 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 1550252020例1的最優(yōu)調(diào)運(yùn)方案101510model:!3發(fā)點(diǎn)4收點(diǎn)產(chǎn)銷平衡的運(yùn)輸問題;sets: cd/1.3/: capacity; xd/1.4/: demand; links(cd,xd): cost, variable;endsets!目標(biāo)函數(shù); min=sum(links: cost* variable);!需求約束; for(xd(j): sum(cd(i): varia

22、ble(i, j)=demand(j);!產(chǎn)量約束; for(cd(i): sum(xd(j): variable(i, j)=capacity(i);!這里是數(shù)據(jù);data: capacity= 70 20 10 ; demand=50 25 10 15;cost= 10 5 2 3 4 3 1 2 5 6 3 4;enddataend求解例1的lingo源代碼求解例1的lingo輸出報(bào)告練習(xí)1 某公司經(jīng)銷甲產(chǎn)品。它下設(shè)三個(gè)加工廠。每日的產(chǎn)量分別是：A1為7噸，A2為4噸，A3為9噸。該公司把這些產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn)。各銷售點(diǎn)每日銷量為：B1為3噸，B2為6噸，B3為5噸，B4為6噸。產(chǎn)銷

23、平衡表見表1。已知從各工廠到各銷售點(diǎn)的單位產(chǎn)品的運(yùn)價(jià)為表2所示。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，在滿足各銷點(diǎn)的需要量的前提下，使總運(yùn)費(fèi)為最少。 表1 產(chǎn)銷平衡表表2 單位運(yùn)價(jià)表 BOOK P122 例例表3 最優(yōu)調(diào)運(yùn)方案表4 檢驗(yàn)數(shù)表所以調(diào)運(yùn)的總運(yùn)費(fèi)最小是85元。解：求初始基本可行解時(shí)，當(dāng)minai,bj=ai=bj 時(shí)，此時(shí)要同時(shí)劃去第i行及第j列，為了確保調(diào)運(yùn)表上仍有m+n-1個(gè)基變量的取值，需要在所劃去的第i行或第j列任一空格上加0,表示這個(gè)格中的基變量的取值是0，這樣就出現(xiàn)了退化解。 若在閉回路上有幾個(gè)偶點(diǎn)處的運(yùn)量等于，則可任取其中一個(gè)作為出基變量（運(yùn)量擦去），其余幾個(gè)點(diǎn)的值調(diào)整后變?yōu)?，但應(yīng)

24、填入，說明這些變量還在基內(nèi)，這時(shí)就出現(xiàn)了退化。(1)有無窮多最優(yōu)解.最終解中有非基變量檢驗(yàn)數(shù)為零時(shí)，以此非基變量為換入變量，可求得另一基最優(yōu)解?；顑?yōu)解的任一凸組合都是最優(yōu)解。 BOOK P136 例表上作業(yè)法計(jì)算中的兩個(gè)問題(2)退化解.解中非零基變量個(gè)數(shù)小于m+n-1時(shí)，為退化解。一般在下面兩種情況下出現(xiàn)： BOOK P138 例1.4.5+例設(shè)數(shù)學(xué)模型為 關(guān)于極大化運(yùn)輸問題的求解例2 下列矩陣C是Ai到Bj的噸公里利潤(rùn), 產(chǎn)量、銷量及其單位利潤(rùn)合并于下表，問運(yùn)輸部門如何安排運(yùn)輸方案使總利潤(rùn)最大？ cij BjAi B1 B2 B3 ai A12 58 9 A29107 10 A3654

25、12 bj 8 14 9方法I：將極大化問題轉(zhuǎn)化為極小化問題。設(shè)極大化問題的運(yùn)價(jià)表為C=（cij）mn，用一個(gè)較大的數(shù)M（Mmaxcij）去減每一個(gè)cij得到矩陣C/=（c/ij）mn ，其中c/ij=Mcij0， 將C/作為極小化問題的運(yùn)價(jià)表，用表上作業(yè)法求出最優(yōu)解，目標(biāo)函數(shù)值為： cij BjAi B1 B2 B3 ai A12 58 9 A29107 10 A3654 12 bj 8 14 9 BjAi B1 B2 B3 ai A1 8 5 2 9 A21 03 10 A3 4 5 6 12 bj 8 14 9用最小元素法求初始運(yùn)輸方案910840 BjAi B1 B2 B3 A1 8

26、4 A2 2 2 A3檢驗(yàn)數(shù)表 由于檢驗(yàn)數(shù)全部非負(fù),因此該初始運(yùn)輸方案也是最優(yōu)運(yùn)輸方案, 則最大利潤(rùn)為： Z=89+1010+68+54=240方法II: 所有非基變量的檢驗(yàn)數(shù)ij0時(shí)最優(yōu).求初始運(yùn)輸方案可采用最大元素法.如上例,用最大元素得到的初始運(yùn)輸方案:8 14 9求檢驗(yàn)數(shù):11=8,12=4,21=2,23=2,全部非正,得到最優(yōu)解運(yùn)輸方案,結(jié)果與第一種方法相同.當(dāng)當(dāng)3 產(chǎn)銷不平衡的運(yùn)輸問題當(dāng)可以虛設(shè)一個(gè)產(chǎn)地 Am+1, 其產(chǎn)量為 并假設(shè)產(chǎn)地 Am+1 運(yùn)往各銷地的單位運(yùn)價(jià)為 cm+1, j = 0 ( j = 1 , 2 , , n ) . 則原問題可轉(zhuǎn)化為平衡運(yùn)輸問題： 產(chǎn)大于銷，

27、可通過虛設(shè)銷地，類似建立平衡運(yùn)輸模型例3已知運(yùn)輸問題由表給出，試建立運(yùn)輸模型 . Bj Ai B1 B2 B3 ai A14 25 10 A2638 15 bj 8 7 14解: Bj Ai B1 B2 B3 ai A14 25 10 A2638 15 A3000 4 bj 8 7 14本題產(chǎn)量為25，銷量為29，是銷大于產(chǎn)問題 虛設(shè)一個(gè)產(chǎn)地 A3，由于并沒有生產(chǎn)，所以運(yùn)價(jià)為零，得運(yùn)輸模型. 如果各銷地不滿足時(shí)，單位缺貨費(fèi)為 4，3，7，則運(yùn)輸模型為437 已知運(yùn)輸問題由表給出，如果產(chǎn)地 Ai 的產(chǎn)量必須運(yùn)走，試建立運(yùn)輸模型 . BjAi B1 B2 B3 ai A14 23 10 A2564

28、 15 A3345 20 最低需求量 10 10 10例4 BjAi B1 B2 B3 B4 ai A14 23 10 A2564 15 A3345 20 bj 10 10 10 15解:這是一個(gè)產(chǎn)大于銷的運(yùn)輸問題.234虛設(shè)一銷地 B4 ,銷量 b4 = 15 . BjAi B1 B2 B3 ai A14 23 10 A2564 15 A3345 20 最低需求量 10 10 10 最高需求量 20 10不限 BjAi B1 B2 B3 ai A14 23 10 A2564 15 A3345 20 bj 10 10 10 443B3B15351015A4M100MM0 三個(gè)銷地的最低需求為

29、30，最高需求不限. 根據(jù)現(xiàn)有產(chǎn)量，B3 至多能得到 25. 建立運(yùn)輸模型 .練習(xí)2 設(shè)有三個(gè)化肥廠(A，B，C)供應(yīng)四個(gè)地區(qū)(，)的農(nóng)用化肥。假定等量的化肥在這些地區(qū)使用效果相同。各化肥廠年產(chǎn)量，各地區(qū)年需要量及從各化肥廠到各地區(qū)運(yùn)送單位化肥的運(yùn)價(jià)如表1所示。試求出總的運(yùn)費(fèi)最節(jié)省的化肥調(diào)撥方案。BOOK P145 例解：這是一個(gè)產(chǎn)銷不平衡的運(yùn)輸問題，總產(chǎn)量為160萬(wàn)噸，四個(gè)地區(qū)的最低需求為110萬(wàn)噸，最高需求為無限。根據(jù)現(xiàn)有產(chǎn)量，第個(gè)地區(qū)每年最多能分配到60萬(wàn)噸，這樣最高需求為210萬(wàn)噸，大于產(chǎn)量。為了求得平衡，在產(chǎn)銷平衡表中增加一個(gè)假想的化肥廠D，其年產(chǎn)量為50萬(wàn)噸。由于各地區(qū)的需要量包含

30、兩部分，如地區(qū)，其中30萬(wàn)噸是最低需求，故不能由假想化肥廠D供給，令相應(yīng)運(yùn)價(jià)為M(任意大正數(shù))，而另一部分20萬(wàn)噸滿足或不滿足均可以，因此可以由假想化肥廠D供給，按前面講的，令相應(yīng)運(yùn)價(jià)為0。對(duì)凡是需求分兩種情況的地區(qū)，實(shí)際上可按照兩個(gè)地區(qū)看待。這樣可以寫出這個(gè)問題的產(chǎn)銷平衡和單位運(yùn)價(jià)表(表2)。產(chǎn)銷平衡表和單位運(yùn)價(jià)表合并于下面的表2根據(jù)表上作業(yè)法計(jì)算，可以求得這個(gè)問題的最優(yōu)方案如表3所示 某制冰廠每年1 4 季度必須供應(yīng)冰塊 15、20、25、10（千噸）.已知該廠各季度冰 塊的生產(chǎn)能力及冰塊的單位成本如表. 如果生產(chǎn)出來的冰塊不在當(dāng)季度使用，每千噸冰塊存儲(chǔ)一個(gè)季度費(fèi)用為4（千元）.又設(shè)該制冰

31、廠每年第3季度末對(duì)貯冰庫(kù)進(jìn)行清庫(kù)維修.問應(yīng)如何安排冰塊的生產(chǎn)，可使該廠全年生產(chǎn)、存儲(chǔ)費(fèi)用最少？4 運(yùn)輸問題應(yīng)用舉例例 5 (生產(chǎn)調(diào)度問題)季 度 生產(chǎn)能力（千噸） 單位成本（千元） 1 25 5 2 18 7 3 16 8 4 15 5季 度 生產(chǎn)能力（千噸） 單位成本（千元） 1 25 5 2 18 7 3 16 8 4 15 5 Bj Ai B1 B2 B3 B4 ai A1 25 A2 18 A3 16 A4 15 bj 15 20 25 10 解：5B54913M0MMMMM0005118179137 某航運(yùn)公司承擔(dān)六個(gè)港口城市 A、B、C、D、E、F 的四條固定航線的物資運(yùn)輸任務(wù).

32、已知各條航線的起點(diǎn)、終點(diǎn)城市及每天航班數(shù)見表1，假定各條航線使用相同型號(hào)的船只，又各城市間的航程天數(shù)見表2.例6(空車調(diào)度問題) 又知每條船只每次裝卸貨的時(shí)間各需一天，則該航運(yùn)公司至少應(yīng)配備多少條船，才能滿足所有航線的運(yùn)貨需求？航線起點(diǎn)城市終點(diǎn)城市每天航班數(shù)1ED32BC23AF14DB1表1 到從ABCDEFA0121477B1031388C23015557851703F7852030表2解：該公司所需配備船只分兩部分.1、載貨航程需要的周轉(zhuǎn)船只數(shù)航線起點(diǎn)城市終點(diǎn)城市每天航班數(shù)1ED32BC23AF14DB1表1 到從ABCDEFA0121477B1031388C2

33、3015557851703F7852030表2 如航線1，在港口E 裝貨1 天，E 至 D 航程17天，在D 卸貨1天，總計(jì)19天. 每天3 航班，故該航線周轉(zhuǎn)船只需57條.航線裝貨天數(shù)航程天數(shù)卸貨天數(shù)小計(jì)航班數(shù)需周轉(zhuǎn)船只數(shù)11171193572131521031719194113115115累計(jì)共需周轉(zhuǎn)船只數(shù)91條.2、各港口間調(diào)度所需船只數(shù)港口城市每天到達(dá)每天需求余缺數(shù)A01-1B12-1C202D312E03-3F101 港口每天到達(dá)與需要的船只不同，如表.為使配備船只數(shù)最少，應(yīng)做到周轉(zhuǎn)的空船數(shù)為最少. 建立運(yùn)輸模型，C、D、F 為空船的產(chǎn)地，A、B、E 為銷地，單位運(yùn)