第7章運輸問題

1、管管 理理 運運 籌籌 學學1第七章第七章 運運 輸輸 問問 題題1 1運運 輸輸 模模 型型2 2運輸問題的計算機求解運輸問題的計算機求解3 3運輸問題的應用運輸問題的應用4 4* *運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法管管 理理 運運 籌籌 學學2例例1、某公司從兩個產地A1、A2將物品運往三個銷地B1、B2、B3，各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如下表所示，問：應如何調運可使總運輸費用最??？B1B2B3產 量A1646200A2655300銷 量150150200 1 1運運 輸輸 模模 型型管管 理理 運運 籌籌 學學3例例1、某公司從兩個產地A1、A2將

2、物品運往三個銷地B1、B2、B3，各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如下表所示，問：應如何調運可使總運輸費用最??？解：解： 產銷平衡問題： 總產量 = 總銷量 設 xij 為從產地Ai運往銷地Bj的運輸量，得到下列運輸量表： Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3） 1 1運運 輸輸 模

3、模 型型兩個產地三產銷地管管 理理 運運 籌籌 學學41 1運運 輸輸 模模 型型一般運輸模型：一般運輸模型：產銷平衡 A1、 A2、 Am 表示某物資的m個產地； B1、B2、Bn 表示某物質的n個銷地；ai 表示產地Ai的產量； bj 表示銷地Bj 的銷量； cij 表示把物資從產地Ai運往銷地Bj的單位運價。設 xij 為從產地Ai運往銷地Bj的運輸量，得到下列一般運輸量問題的模型： m n Min f = cij xij i = 1 j = 1 n s.t. xij = ai i = 1,2,m j = 1 m xij = bj j = 1,2,n i = 1 xij 0 (i = 1

4、,2,m ; j = 1,2,n) 管管 理理 運運 籌籌 學學51 1運運 輸輸 模模 型型變化：變化： 1）有時目標函數求最大。如求利潤最大或營業(yè)額最大等； 2）當某些運輸線路上的能力有限制時，在模型中直接加入約束條件（等式或不等式約束)； 3）產銷不平衡時，可加入假想的產地（銷大于產時）或銷地（產大于銷時）。管管 理理 運運 籌籌 學學6mnmmnnxxxxxxxxx,;,212222111211111111111111111111m行行n行行1運運 輸輸 模模 型型管管 理理 運運 籌籌 學學7管管 理理 運運 籌籌 學學8nmbbbaaaA1111111111111111112121

5、mnmmnnxxxxxxxxx,;,212222111211管管 理理 運運 籌籌 學學9 AAA13121,mxxx管管 理理 運運 籌籌 學學10nmbbbaaaA1111111111111111112121mnmmnnxxxxxxxxx,;,212222111211管管 理理 運運 籌籌 學學1101011111111111111mD）（按第一列展開：管管 理理 運運 籌籌 學學12132222111,jijijijijijisssxxxxxxsssjijijijijijixxxxxx123221211,siii,21sjjj,21管管 理理 運運 籌籌 學學13（a） （b） （c）

6、（d） （e） 表中的折線構成一條封閉曲線，且所有的表中的折線構成一條封閉曲線，且所有的邊都是邊都是或或的；為什麼？的；為什麼？ 表中的表中的和和；為什麼？；為什麼？管管 理理 運運 籌籌 學學14 132222111,jijijijijijisssxxxxxx132222111,jijijijijijisssPPPPPP0132222111jijijijijijisssPPPPPP管管 理理 運運 籌籌 學學150132222111jijijijijijisssPPPPPP0)()()(132222111jmijmijmijmijmijmieeeeeeeeeeeesss管管 理理 運運 籌籌

7、 學學16rrjijijixxx,2211管管 理理 運運 籌籌 學學17rrjijijixxx,2211管管 理理 運運 籌籌 學學18管管 理理 運運 籌籌 學學192 2運輸問題的計算機求解運輸問題的計算機求解例例2、某公司從兩個產地A1、A2將物品運往三個銷地B1、B2、B3，各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如下表所示，問：應如何調運可使總運輸費用最??？解解：增加一個虛設的銷地運輸費用為0 B1 B2 B3 產產量量 A1 6 4 6 300 A2 6 5 5 300 銷銷量量 150 150 200 600 500 B1 B2 B3 B4 產產量量 A1 6

8、 4 6 0 300 A2 6 5 5 0 300 銷銷量量 150 150 200 100 600 600 產大于銷，生產能力富余，可假想為庫存，運費為零管管 理理 運運 籌籌 學學202 2運輸問題的計算機求解運輸問題的計算機求解例例3、某公司從兩個產地A1、A2將物品運往三個銷地B1、B2、B3，各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如下表所示，問：應如何調運可使總運輸費用最小？解解：增加一個虛設的產地運輸費用為0 B1 B2 B3 產產量量 A1 6 4 6 200 A2 6 5 5 300 銷銷量量 250 200 200 500 650 B1 B2 B3 產產量

9、量 A1 6 4 6 200 A2 6 5 5 300 A3 0 0 0 150 銷銷量量 250 200 200 650 650 銷售能力富余，假想產地，運費為零管管 理理 運運 籌籌 學學213 3運輸問題的應用運輸問題的應用一、產銷不平衡的運輸問題一、產銷不平衡的運輸問題例例4、石家莊北方研究院有一、二、三三個區(qū)。每年分別需要用煤、石家莊北方研究院有一、二、三三個區(qū)。每年分別需要用煤3000、1000、2000噸，由河北臨城、山西盂縣兩處煤礦負責供應，價格、質量相同。供噸，由河北臨城、山西盂縣兩處煤礦負責供應，價格、質量相同。供應能力分別為應能力分別為1500、4000噸，運價為：噸，運

10、價為： 由于需大于供，經院研究決定一區(qū)供應量可減少由于需大于供，經院研究決定一區(qū)供應量可減少0-300噸，二區(qū)必須滿噸，二區(qū)必須滿足需求量，三區(qū)供應量不少于足需求量，三區(qū)供應量不少于1500噸，試求總費用為最低的調運方案。噸，試求總費用為最低的調運方案。解：解： 根據題意，作出產銷平衡與運價表：根據題意，作出產銷平衡與運價表：這里這里 M 代表一個很大的正數，其作用是強迫相應的代表一個很大的正數，其作用是強迫相應的 x31、 x33、 x34取值為取值為0。管管 理理 運運 籌籌 學學223 3運輸問題的應用運輸問題的應用一、產銷不平衡的運輸問題一、產銷不平衡的運輸問題例例5、設有A、B、C三

11、個化肥廠供應1、2、3、4四個地區(qū)的農用化肥。假設效果相同，有關數據如下表： 試求總費用為最低的化肥調撥方案。解：解： 根據題意，作出產銷平衡與運價表： 最低要求必須滿足，因此把相應的虛設產地運費取為 M ，而最高要求與最低要求的差允許按需要安排，因此把相應的虛設產地運費取為 0 。對應 4”的銷量 50 是考慮問題本身適當取的數據，根據產銷平衡要求確定 D的產量為 50。 1234產量A1613221750B1413191560C192023-50最低需要量3070010最高需要量507030不限 1 1” 2 3 4 4” 產量 A 16 16 13 22 17 17 50 B 14 14

12、 13 19 15 15 60 C 19 19 20 23 M M 50 D M 0 M 0 M 0 50 銷量 30 20 70 30 10 50 210 210 管管 理理 運運 籌籌 學學233 3運輸問題的應用運輸問題的應用二、生產與儲存問題二、生產與儲存問題例例6、某廠按合同規(guī)定須于當年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機。已知該廠各季度的生產能力及生產每臺柴油機的成本如下表。如果生產出來的柴油機當季不交貨，每臺每積壓一個季度需儲存、維護等費用0.15萬元。試求在完成合同的情況下，使該廠全年生產總費用為最小的決策方案。生產能力（臺） 單位成本（萬元）一季度251

13、0.8二季度3511.1三季度3011.0四季度1011.3管管 理理 運運 籌籌 學學243 3運輸問題的應用運輸問題的應用解：解： 設 xij為第 i 季度生產的第 j 季度交貨的柴油機數目，那么應滿足： 交貨：x11 = 10 生產：x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10 把第 i 季度生產的柴油機數目看作第 i 個生產廠的產量；把第 j 季度交貨的柴油機數目看作第 j 個銷售

14、點的銷量；成本加儲存、維護等費用看作運費?？蓸嬙煜铝挟a銷平衡問題：目標函數：目標函數：Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44 第一季度 第二季度 第三季度 第四季度 D 產量 第一季度 10.80 10.95 11.10 11.25 0 25 第二季度 M 11.10 11.25 11.40 0 35 第三季度 M M 11.00 11.15 0 30 第四季度 M M M 11.30 0 10 銷量 10 15

15、25 20 30 100 100 管管 理理 運運 籌籌 學學253 3運輸問題的應用運輸問題的應用二、生產與儲存問題二、生產與儲存問題例例7、光明儀器廠生產電腦繡花機是以銷定產的。已知1至6月份各月的生產能力、合同銷量和單臺電腦繡花機平均生產費用見下表： 已知上年末庫存103臺繡花機，如果當月生產出來的機器當月不交貨，則需要運到分廠庫房，每臺增加運輸成本0.1萬元,每臺機器每月的平均倉儲費、維護費為0.2萬元。在7-8月份銷售淡季，全廠停產1個月，因此在6月份完成銷售合同后還要留出庫存80臺。加班生產機器每臺增加成本1萬元。問應如何安排1-6月份的生產，可使總的生產費用（包括運輸、倉儲、維護

16、）最少？正常生產能力（臺） 加班生產能力（臺） 銷量（臺）單臺費用（萬元）1 月份6010104152 月份501075143 月份902011513.54 月份10040160135 月份10040103136 月份80407013.5管管 理理 運運 籌籌 學學263 3運輸問題的應用運輸問題的應用解：解： 這個生產存儲問題可化為運輸問題來做?？紤]：各月生產與交貨分別視為產各月生產與交貨分別視為產地和銷地地和銷地 1）1-6月份合計生產能力（包括上年末儲存量）為743臺，銷量為707臺。設一假想銷地銷量為36； 2）上年末庫存103臺，只有倉儲費和運輸費，把它列為第0行； 3）6月份的需求

17、除70臺銷量外，還要80臺庫存，其需求應為70+80=150臺； 4）1-6表示1-6月份正常生產情況， 1-6表示1-6月份加班生產情況。產銷平衡與運價表： 1 月 2 月 3 月 4 月 5 月 6 月 虛銷地 正常產量 加班產量 0 0.3 0.5 0.7 0.9 1.1 1.3 0 103 1 15 15.3 15.5 15.7 15.9 16.1 0 60 1 16 16.3 16.5 16.7 6.9 17.1 0 10 2 M 14 14.3 14.5 14.7 14.9 0 50 2 M 15 15.3 15.5 15.7 15.9 0 10 3 M M 13.5 13.8 1

18、4.0 14.2 0 90 3 M M 14.5 14.8 15.0 15.2 0 20 4 M M M 13.0 13.3 13.5 0 100 4 M M M 14.0 14.3 14.5 0 40 5 M M M M 13.0 13.3 0 100 5 M M M M 14.0 14.3 0 40 6 M M M M M 13.5 0 80 6 M M M M M 14.5 0 40 銷量 104 75 115 160 103 150 36 743 743 管管 理理 運運 籌籌 學學273 3運輸問題的應用運輸問題的應用 用“管理運籌學”軟件解得的結果是：1-6月最低生產費用為8307

19、.5萬元，每月的銷售安排如下表所示管管 理理 運運 籌籌 學學283 3運輸問題的應用運輸問題的應用三、轉運問題：三、轉運問題： 在原運輸問題上增加若干轉運站。運輸方式有：產地 轉運站、轉運站 銷地、產地 產地、產地 銷地、銷地 轉運站、銷地 產地等。例8、騰飛電子儀器公司在大連和廣州有兩個分廠生產同一種儀器，大連分廠每月生產400臺，廣州分廠每月生產600臺。該公司在上海和天津有兩個銷售公司負責對南京、濟南、南昌、青島四個城市的儀器供應。另外因為大連距離青島較近，公司同意大連分廠向青島直接供貨，運輸費用如圖，單位是百元。問應該如何調運儀器，可使總運輸費用最低？圖中 1- 廣州、2 - 大連、

20、3 - 上海、4 - 天津、5 - 南京、6 - 濟南、7 - 南昌、8 - 青島管管 理理 運運 籌籌 學學293 3運輸問題的應用運輸問題的應用解：解：設 xij 為從 i 到 j 的運輸量，可得到有下列特點的線性規(guī)劃模型：目標函數：Min f = 所有可能的運輸費用（運輸單價與運輸量乘積之和）約束條件： 對產地（發(fā)點） i ：輸出量 - 輸入量 = 產量 對轉運站（中轉點）：輸入量 - 輸出量 = 0 對銷地（收點） j ：輸入量 - 輸出量 = 銷量例8（續(xù)）目標函數： Min f = 2x13+ 3x14+ 3x23+ x24+ 4x28 + 2x35+ 6x36+ 3x37+ 6x

21、38+ 4x45+ 4x46+ 6x47+ 5x48 約束條件： s.t. x13+ x14 600 (廣州分廠供應量限制） x23+ x24+ x28 400 (大連分廠供應量限制） -x13- x23 + x35 + x36+ x37 + x38 = 0 （上海銷售公司，轉運站） -x14- x24 + x45 + x46+ x47 + x48 = 0 （天津銷售公司，轉運站） x35+ x45 = 200 （南京的銷量） x36+ x46 = 150 （濟南的銷量） x37+ x47 = 350 （南昌的銷量） x38+ x48 + x28 = 300 （青島的銷量） xij 0 , i

22、,j = 1,2,3,4,5,6,7,8管管 理理 運運 籌籌 學學303 3運輸問題的應用運輸問題的應用用用“管理運籌學管理運籌學”軟件求得結果：軟件求得結果： x13 = 550 x14 =50 ； x23 = 0 x24 = 100 x28 = 300 ； x35 = 200 x36 = 0 x37 = 350 x38 = 0 ； x45 = 0 x46 = 150 x47 = 0 x48 = 0 。最小運輸費用為：最小運輸費用為：4600百元百元管管 理理 運運 籌籌 學學313 3運輸問題的應用運輸問題的應用例例9、某公司有A1、 A2、 A3三個分廠生產某種物資，分別供應B1、 B

23、2、 B3、 B4四個地區(qū)的銷售公司銷售。假設質量相同，有關數據如下表： 試求總費用為最少的調運方案。假設： 1.每個分廠的物資不一定直接發(fā)運到銷地，可以從其中幾個產地集中一起運； 2.運往各銷地的物資可以先運給其中幾個銷地，再轉運給其他銷地； 3.除產銷地之外，還有幾個中轉站，在產地之間、銷地之間或在產地與銷地之間轉運。B1B2B3B4產 量A13113107A219284A3741059銷 量3656和 =20管管 理理 運運 籌籌 學學323 3運輸問題的應用運輸問題的應用運價如下表：解：解：把此轉運問題轉化為一般運輸問題： 1、把所有產地、銷地、轉運站都同時看作產地和銷地； 2、運輸表

24、中不可能方案的運費取作M，自身對自身的運費為0； 3、Ai： 產量為 20+原產量， 銷量為 20； Ti ： 產量、銷量均為 20； Bi： 產量為 20， 銷量為 20 +原銷量，其中20為各點可能變化的最大流量； 4、對于最優(yōu)方案，其中 xi i 為自身對自身的運量，實際上不進行運作。A1A2A3T1T2T3T4B1B2B3B4A1132143311310A21-35-21928A33-1-2374105T12311322846T215-1114527T34-23121824T43232121-2621194858-121B332104222423B410856

25、746213管管 理理 運運 籌籌 學學333 3運輸問題的應用運輸問題的應用 擴大的運輸問題產銷平衡與運價表： A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4 產量 A1 0 1 3 2 1 4 3 3 11 3 10 27 A2 1 0 M 3 5 M 2 1 9 2 8 24 A3 3 M 0 1 M 2 3 7 4 10 5 29 T1 2 3 1 0 1 3 2 2 8 4 6 20 T2 1 5 M 1 0 1 1 4 5 2 7 20 T3 4 M 2 3 1 0 2 1 8 2 4 20 T4 3 2 3 2 1 2 0 1 M 2 6 20 B1 3 1 7

26、 2 4 1 1 0 1 4 2 20 B2 11 9 4 8 5 8 M 1 0 2 1 20 B3 3 2 10 4 2 2 2 4 2 0 3 20 B4 10 8 5 6 7 4 6 2 1 3 0 20 銷量 20 20 20 20 20 20 20 23 26 25 26 240 管管 理理 運運 籌籌 學學344 4* *運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法 表上作業(yè)法是一種求解運輸問題的特殊方法，其實質是單表上作業(yè)法是一種求解運輸問題的特殊方法，其實質是單純形法。純形法。 運輸問題都存在最優(yōu)解。運輸問題都存在最優(yōu)解。 計算過程（假設產銷平衡）：計算過程（假設產銷平衡）： 1

27、.找出初始基本可行解。對于有找出初始基本可行解。對于有m個產地個產地n個銷地的產銷平衡問題，個銷地的產銷平衡問題，則有則有m個關于產量的約束方程和個關于產量的約束方程和n個關于銷量的約束方程。由于產個關于銷量的約束方程。由于產銷平衡，其模型最多只有銷平衡，其模型最多只有m+n-1個獨立的約束方程，即運輸問題有個獨立的約束方程，即運輸問題有m+n-1個基變量。在個基變量。在mn的產銷平衡表上給出的產銷平衡表上給出m+n-1個數字格，其個數字格，其相對應的調運量的值即為基變量的值。相對應的調運量的值即為基變量的值。 2.求各非基變量的檢驗數，即檢驗除了上述求各非基變量的檢驗數，即檢驗除了上述m+n

28、-1個基變量以外的個基變量以外的空格的檢驗數判別是否達到最優(yōu)解，如果已是最優(yōu)，停止計算，否空格的檢驗數判別是否達到最優(yōu)解，如果已是最優(yōu)，停止計算，否則轉到下一步。則轉到下一步。 3.確定入基變量和出基變量，找出新的基本可行解。在表上用閉回確定入基變量和出基變量，找出新的基本可行解。在表上用閉回路法調整。路法調整。 4.重復重復2、3直到得到最優(yōu)解。直到得到最優(yōu)解。管管 理理 運運 籌籌 學學35 確定初始確定初始方案方案( ( 初初 始始 基本可行解基本可行解) ) 改進調整改進調整（換基迭代）（換基迭代）否否 判定是否判定是否 最最 優(yōu)？優(yōu)？是是結結 束束最優(yōu)方案最優(yōu)方案運輸問題求解思路圖運

29、輸問題求解思路圖4*運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法管管 理理 運運 籌籌 學學36調調 銷地銷地 運運 量量產地產地 B1 B2 B3 產產 量量 A1 c11 X11 c12 X12 c13 X13 a1 A2 c21 X21 c22 X22 c23 X23 a2 銷銷 量量 b1 b2 b33121jjiiba運輸問題作業(yè)表（產銷平衡表）運輸問題作業(yè)表（產銷平衡表） 4*運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法管管 理理 運運 籌籌 學學37個銷地需求滿足第個銷地第個產地的產量全部運到第jjbjiia4*運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法管管 理理 運運 籌籌 學學384*

30、運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法管管 理理 運運 籌籌 學學394*運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法管管 理理 運運 籌籌 學學404*運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法管管 理理 運運 籌籌 學學414*運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法 450 200 150 100 日銷量（需求量） 250 75 65 80 乙 200 100 70 90 甲 日產量日產量（供應量）（供應量） C B A運距運距 城市城市煤礦煤礦管管 理理 運運 籌籌 學學42調調 銷地銷地 運運 量量產地產地 B1 B2 B3 產產 量量 A1 90 X11 70 X12 100 X13

31、200 A2 80 X21 65 X22 75 X23 250 銷銷 量量 100 150 200 450 用最小元素法確定初始調運方案用最小元素法確定初始調運方案 1501001001001001001004*運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法管管 理理 運運 籌籌 學學434*運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法管管 理理 運運 籌籌 學學44調調 銷地銷地 運運 量量產地產地 B1 B2 B3 產產 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 銷銷 量量 100 150 200 450 用西北角法確定初

32、始調運方案用西北角法確定初始調運方案 100100100 50 502002004*運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法管管 理理 運運 籌籌 學學454*運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法管管 理理 運運 籌籌 學學464 4* *運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法例10.喜慶食品公司有三個生產面包的分廠A1，A2，A3，有四個銷售公司B1，B2，B3，B4，其各分廠每日的產量、各銷售公司每日的銷量以及各分廠到各銷售公司的單位運價如表所示，在表中產量與銷量的單位為噸，運價的單位為百元/噸。問該公司應如何調運產品在滿足各銷點的需求量的前提下總運費最少？這是一個產銷平衡的運輸問題

33、，因此不需要再設假想產地和銷地了。 銷地產地B1B2B3B4產量A13113107A219284A3741059銷量3656 2020管管 理理 運運 籌籌 學學474 4* *運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法一、確定初始基本可行解 為了把初始基本可行解與運價區(qū)分開，我們把運價放在每一欄的右上角，每一欄的中間寫上初始基本可行解（調運量）。 1.西北角法：先從表的左上角（即西北角）的變量x11開始分配運輸量，并使x11取盡可能大的值，即x11=min(7,3)=3,則x21與x31必為零。同時把B1的銷量與A1的產量都減去3填入銷量和產量處，劃去原來的銷量和產量。同理可得余下的初始基本可

34、行解。 銷地產地 B1 B2 B3 B4 產量 A1 3 47 4 0 A2 2 24 2 0 A3 3 69 6 0 銷量 3 0 6 2 0 5 3 0 6 0 2020311310851029471管管 理理 運運 籌籌 學學484 4* *運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法2.最小元素法 西北角法是對西北角的變量分配運輸量，而最小元素法是就近供應，即對單位運價最小的變量分配運輸量。在表上找到單位運價最小的x21，并使x21取盡可能大的值，即x21=min(4,3)=3,把A1的產量改為1，B1的銷量改為0，并把B1列劃去。在剩下的33矩陣中再找最小運價，同理可得其他的基本可行解。

35、 一般來說用最小元素法求得的初始基本可行解比西北角法求得的總運價要少。這樣從用最小元素法求得的初始基本可行解出發(fā)求最優(yōu)解的迭代次數可能少一些。 銷地產地 B1 B2 B3 B4 產量 A1 4 37 3 0 A2 3 1 4 1 0 A3 6 39 3 0 銷量 3 0 6 0 5 4 0 6 3 0 2020311310851029471管管 理理 運運 籌籌 學學494 4* *運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法 在求初始基本可行解時要注意的兩個問題： 1.當我們取定xij的值之后，會出現(xiàn)Ai的產量與Bj的銷量都改為零的情況，這時只能劃去Ai行或Bj列，但不能同時劃去Ai行與Bj列。

36、 2.用最小元素法時，可能會出現(xiàn)只剩下一行或一列的所有格均未填數或未被劃掉的情況，此時在這一行或者一列中除去已填上的數外均填上零，不能按空格劃掉。這樣可以保證填過數或零的格為m+n-1個，即保證基變量的個數為m+n-1個。管管 理理 運運 籌籌 學學504 4* *運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法二、最優(yōu)解的判別1.閉回路法 所謂閉回路是在已給出的調運方案的運輸表上從一個代表非基變量的空格出發(fā)，沿水平或垂直方向前進，只有遇到代表基變量的填入數字的格才能向左或右轉90度（當然也可以不改變方向）繼續(xù)前進，這樣繼續(xù)下去，直至回到出發(fā)的那個空格，由此形成的封閉折線叫做閉回路。一個空格存在唯一的

37、閉回路。 所謂閉回路法，就是對于代表非基變量的空格（其調運量為零），把它的調運量調整為1，由于產銷平衡的要求,我們必須對這個空格的閉回路的頂點的調運量加上或減少1。最后我們計算出由這些變化給整個運輸方案的總運輸費帶來的變化。如果所有代表非基變量的空格的檢驗數也即非基變量的檢驗數都大于等于零，則已求得最優(yōu)解，否則繼續(xù)迭代找出最優(yōu)解。管管 理理 運運 籌籌 學學514 4* *運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法從非基變量x11出發(fā)，找到一個閉回路如上表所示?；芈酚兴膫€頂點，除x11外，其余都為基變量。現(xiàn)在把x11的調運量從零增加為1噸，運費也增加了3元，為了使A1產量平衡，x13必須減少1噸

38、，運費減少3元。為了B3的銷量平衡，x23必須增加1噸，運費增加2元。同理把x21減少1噸，運費減少1元。調整后，總運費增加了3-3+2-1=1元。說明如果讓x11為基變量，運費就會增加，其增加值1作為x11的檢驗數，為了區(qū)別調整量，我們把1加圈。用同樣的方法可以找出所有空格（即非基變量）的檢驗數。 銷地產地 B1 B2 B3 B4 產量 A1 1 4 7 A2 3 1 4 A3 9 銷量 3 6 5 6 2020311310851029471管管 理理 運運 籌籌 學學52調調 銷地銷地 運運 量量產地產地 B1 B2 B3 產產 量量 A1 90 X11 70 X12 100 X13 20

39、0 A2 80 X21 65 X22 75 X23 250 銷銷 量量 100 150 200 450100100100150-2015管管 理理 運運 籌籌 學學531221管管 理理 運運 籌籌 學學544 4* *運輸問題的表上作業(yè)法運輸問題的表上作業(yè)法2.位勢法 所謂位勢法，我們對運輸表上的每一行賦予一個數值ui，對每一列賦予一個數值vj，它們的數值是由基變量xij的檢驗數 所決定的，則非基變量xij的檢驗數就可以用公式 求出。 我們先給u1賦個任意數值，不妨設u1=0，則從基變量x13的檢驗數求得v3=c13-u1=3-0=3。同理可以求得v4=10，u2=-1等等見上表。檢驗值的求法即用公式 ，如 。 銷地產地 B1 B2 B3 B4 ui A1 1 2 4 3 0 A2 3 1 1 -1 -1 A3 10 6 12 3 -5 vj 2 9 3 10 20203113108510294710jiijijvucjiijijvucjii