運籌學07-運輸問題.ppt

1、第三章 運輸問題,3.1 運輸問題的數(shù)學模型 3.2 表上作業(yè)法 3.3 產(chǎn)銷不平衡問題,3.1 運輸問題模型及有關概念,問題的提出 一般的運輸問題就是要解決把某種產(chǎn)品從若干個產(chǎn)地調運到若干個銷地，在每個產(chǎn)地的供應量與每個銷地的需求量已知，并知道各地之間的運輸單價的前提下，如何確定一個使得總的運輸費用最小的方案。,3.1 運輸問題的數(shù)學模型,(1) 運輸問題的引入,例1 有一個地區(qū)有兩個產(chǎn)棉區(qū)A1, A2向三個紡織廠B1 B2,B3供應棉花,產(chǎn)棉區(qū)每年的供應量分別為70kt和50kt;紡織廠每年的需求量分別為50kt,40kt和30kt.已知各產(chǎn)棉區(qū)到各紡織廠的單位運價如左表,問如何安排運輸方

2、案,使總運費最小.設由Ai運往Bj的棉花的運量為xij(kt),如右表:,3.1 運輸問題的數(shù)學模型,(1) 運輸問題的引入,由于各個產(chǎn)棉區(qū)Ai運往各個紡織廠Bj的總量應該等于它的產(chǎn)量，所以 x11 + x12 + x13 =70 x21 + x22 + x23 =50 另外,由于各個紡織廠收到各個產(chǎn)棉區(qū)運輸?shù)目偭繎摰扔谒男枨罅?x11 + x21 =50 x12 + x22 =40 x13 + x23 =30 目標是總運費最小，即 minz=5 x11 +8 x12 +6 x13 +4 x21 +3 x22 +8 x23,3.1 運輸問題的數(shù)學模型,(1) 運輸問題的引入,此運輸問題的數(shù)

3、學模型為: min z=5 x11 +8 x12 +6 x13 +4 x21 +3 x22 +8 x23 x11 + x12 + x13 =70 x21 + x22 + x23 =50 x11 + x21 =50 x12 + x22 =40 x13 + x23 =30 xij 0(i=1,2;j=1,2,3),3.1 運輸問題的數(shù)學模型,(2) 運輸問題的一般數(shù)學模型,運輸問題的一般描述: m個產(chǎn)地Ai,I=1,2.,m,產(chǎn)量分別為ai個單位, n個產(chǎn)地Bj,j=1,2.,n,產(chǎn)量分別為bj個單位; Ai與Bj之間的單位運價爲Cij ,問如何安排運輸方案,使總運費最少?,3.1 運輸問題的數(shù)學

4、模型,(2) 運輸問題的一般數(shù)學模型,此問題的數(shù)學模型: min z= cij xij s.t xij = ai (i=1,2.m) xij = bj (j=1,2.n) xij0 (i=1,2.m ,j=1,2.n),i1,j1,m,n,系數(shù)矩陣為 ：,共有 2+3 行，分別表示糧庫和糧店；有 2*3 列分別表示各變量；每列只有兩個 1，其余為 0 。,運輸問題的特點,系數(shù)矩陣為0-1稀疏矩陣， 系數(shù)矩陣為m+n行,mn列的矩陣 系數(shù)矩陣的秩為m+n-1 需求總量與總產(chǎn)量相等則約束條件為等式約束。,3.2 表上作業(yè)法,模型的矩陣表述 表上作業(yè)法的計算步驟 確定初始基可行解 最優(yōu)解的判別 閉回

5、路調整法,對于平衡運輸問題化成矩陣形式: min z=CX ; AX=b ;X0 其中C=(c11, c12 ,. , C1n ,., cm1 , cm2 , , cmn)， b=(a1, a2, am, b1, b2 , bn)T, X=(x11, x12, x1n, , xm1, xm2, xmn) T 。 1 1 1 1 1 1 A= 1 1 1 1 1 1 1 1 1 1 1 1 R(A)=m+n-1,3.2.1 模型的矩陣表示,該系數(shù)矩陣中對應于變量xij的系數(shù)向量Pij ，其分量中除第i個和第m+j個為1外，其余的都為零。即 Pij (0, 0, 0,1,0, ,0,1,0 , 0

6、)T ei + em+j 對產(chǎn)銷平衡的運輸問題，由于有以下關系式存在： bj = ( xij )= ( xij )=ai 所以模型最多只有m+n-1個獨立約束方程。即 系數(shù)矩陣的秩m+n-1。,3.2.1 模型的矩陣表示,表上作業(yè)法的實質是單純形法。其計算步驟為： （1）找出初始基可行解。即在（mn）產(chǎn)銷平衡表上給出（m+n1）個數(shù)字格。 （2）求各非基變量的檢驗數(shù)。在表上即是空格的檢驗數(shù)。判別是否達到最優(yōu)解。如果已經(jīng)是最優(yōu)解，則停止計算，否則轉到下一步。 （3）確定換入變量和換出變量，找出新的基可行解。在表上用閉回路法調整。 （4）重復（2），（3）直到得到最優(yōu)解(肯定存在)為止。 以上運算

7、都可以在表上進行。,3.2.2 表上作業(yè)法的矩陣表示,步驟詳解（例2）,例2 設某物資從A1 , A2, A3處運往B1, B2, B3, B4處,各處供應量,需求量及單位運價見下表。問如何安排運輸方案,才能使總運費最少?,最小元素法 伏格爾（Vogel）法,3.2.3 確定初始基可行解,最小元素法,根據(jù)單位運價最低處優(yōu)先供應的原則依次安排運輸量,最小元素法,單位運價,最小元素法,最小元素法,最小元素法,最小元素法,最小元素法,最小元素法,最小元素法,運量,初始基可行解,伏格爾（Vogel）法（推薦）,比較最小運費與次小運費的差額，在差額最大處，采用最小運費調運。,最小元素法的缺點是為了節(jié)省一

8、處的費用，有時候造成在其它地方要多化幾倍的運費。,伏格爾（Vogel）法,運價行差額,運價列差額,伏格爾（Vogel）法,伏格爾（Vogel）法,伏格爾（Vogel）法,伏格爾（Vogel）法,伏格爾（Vogel）法,伏格爾（Vogel）法,伏格爾（Vogel）法,伏格爾（Vogel）法,伏格爾（Vogel）法,初始基可行解,閉回路法 位勢法,判別的方法是計算空格（非基變量）的檢驗數(shù)C - CB B-1A 。因運輸問題的目標函數(shù)是要求實現(xiàn)最小化，故當所有的C - CB B-1A 0時，得最優(yōu)解。,5.2.4 最優(yōu)解的判別,3.2.4.1 閉回路法,閉回路法: Xij對應的檢驗數(shù)ij=(閉回路上

9、的偶數(shù)頂點運價之和 閉回路上的奇數(shù)頂點運價之和),閉回路: 以某空格為起點，用水平或垂直線向前劃，每(?)碰到一數(shù)字格轉90度后，繼續(xù)前進，直到回到起始空格為止，得到一個閉回路。 從每一個空格出發(fā)一定存在和可以找到一個惟一的閉回路。（非基變量對應的系數(shù)列向量由基唯一地線性表示）,閉回路法,閉回路法,閉回路法,23=3-6+3-2=-2,閉回路法,位勢法（推薦）,設u1, u2 , um;v1 , v2 , , vn是對應運輸問題的m+n個約束條件的對偶變量。B是含有一個人工變量xa 的(m+n)(m+n)初始基矩陣。人工變量在目標函數(shù)中的系數(shù)ca 0，從線性規(guī)劃的對偶理論可知： CB B-1

10、(u1, u2 , um;v1 , v2 , , vn) 而每個決策變量xij的系數(shù)向量Pij = ei + em+j ，所以CB B-1 Pij = uivj 。于是檢驗數(shù) ij cij CB B-1 Pij = cij （ uivj ） 當xij為基變量時，有cij （ uivj ）=0,即uivjcij 非基變量的檢驗數(shù)為：ij cij （ uivj ） 其中cij為對應的運價，稱 ui為對應的行位勢， vj為對應的列位勢。,位勢法（步驟）,位勢法： 第一步：給出初始解，在對應的數(shù)字格處填入單位運價。 第二步：在表中增加一行一列，在列中填入u1, u2 , , um，在行中填入v1 ,

11、v2 , , vn。先取定一個數(shù)u1 =0，根據(jù)uivjcij求得各個ui和vj值。 第三步：再根據(jù)ij cij （ uivj ）求得非基變量（空格）的檢驗數(shù)。,位勢法(第一步),位勢法(第二步),位勢法(第二步)【演排】,位勢法(第二步),位勢法(第三步)【演排】,位勢法(第三步),觀察與思考,閉回路法與位勢法所得的檢驗數(shù)是一樣的，但位勢法更簡便一些。,閉回路調整法,調整量=min(閉回路上的奇數(shù)頂點運量),（其原理與單純形法中按最小比值規(guī)則來確定換出變量相同。）,一般選擇其中最小的負檢驗數(shù)，以它對應的空格為調入格。,（即以它對應的非基變量為換入變量。）,閉回路調整法,調入格 （換入變量）,

12、閉回路調整法（調整過程）,調出格 （換出變量）,閉回路調整法,閉回路調整法（退化解）,說明： （1）在用閉回路法調整時，若在閉回路上出現(xiàn)兩個或兩個以上的奇數(shù)頂點的相等的最小值，這時只能選擇其中一個作為調入格。而經(jīng)調整后，得到退化解。這時有一個數(shù)字格必須填入一個零，表明它是基變量。 （2）得到新的調整方案（新的解）后，再用閉回路法或位勢法求各空格的檢驗數(shù)。 （3）若仍有檢驗數(shù)為負，則繼續(xù)調整。若所有檢驗數(shù)都非負，則表中的解為最優(yōu)解。,閉回路調整法演排,閉回路調整法,閉回路調整法演排,閉回路調整法,閉回路調整法（調整過程）,閉回路調整法,閉回路調整法演排,閉回路調整法,閉回路調整法,所有檢驗數(shù)非負

13、,此方案為最優(yōu)方案,閉回路調整法,運量,閉回路調整法（最優(yōu)解）,所有檢驗數(shù)非負,此方案爲最優(yōu)方案, 最小總運費為：f23162423142336(元),閉回路調整法（無窮多最優(yōu)解）,由于A3行、B4列處的非基變量（空格）x34的檢驗數(shù)為零，因此該問題有無窮多最優(yōu)解。 可在表中以（3，4）為調入格，作閉回路 (3，4)+ (1，4)- (1，1)+ (3，1)- (3，4)+ 確定min(2，1)1，經(jīng)調整后得到另一最優(yōu)解。,閉回路調整法,閉回路調整法,閉回路調整法,閉回路調整法,閉回路調整法,運量,閉回路調整法（無窮多最優(yōu)解）,所有檢驗數(shù)非負,經(jīng)調整后得到另一最優(yōu)方案, 最小總運費為：f331

14、6142 323 15 36(元),無窮多最優(yōu)解,此運輸問題的解為上述兩個特解的凸組合。,表上作業(yè)法的解題過程,分析實際問題,建立運輸表,求出初始方案 (最小元法或伏格爾法),找出絕對值最大的負檢驗數(shù), 經(jīng)閉回路調整法得新方案,得最優(yōu)解, 算出運費,終止,求出檢驗數(shù) (閉回路法或位勢法),是,否,所有檢 驗數(shù)0,產(chǎn)大于銷( ai bJ )的情況 銷大于產(chǎn)( ai bJ )的情況 習題,3.3 產(chǎn)銷不平衡問題,產(chǎn)大于銷( ai bj )的情況 Min f= Cij xij s.t xij ai (i=1,2,m) xij = bj (j=1,2,n) xij 0 (i=1,2,m ; j=1,2

15、,n) 引人虛設的銷地Bn+1其需要量為:bn+1= ai - bj ,這樣,m個產(chǎn)地、n個銷地的不平衡運輸問題,轉換為m個產(chǎn)地,n+1個銷地的平衡問題. 計算中,在運輸表中添加Bn+1這列,其需求量為: bn+1= ai - bj, Ai到Bn+1的單位運價為單位存儲費用(或為零)。,3.3.1 產(chǎn)大于銷的運輸情況,銷大于產(chǎn)( ai bj )的情況 Min f= Cij xij s.t xij = ai (I=1,2,m) xij bj (j=1,2,n) xij 0 (i=1,2,m ; j=1,2,n) 引人虛設的產(chǎn)地Am+1其產(chǎn)量為:am+1 bj - ai,等于銷地的物資缺少量 。這樣,m個產(chǎn)地、n個銷地的不平衡運輸問題就轉換為m +1個產(chǎn)地,n個銷地的平衡問題. 計算中,在運輸表中添加Am+1這行,其產(chǎn)量為am+1 bj - ai , Am+1到Bj的單位運價為單位缺貨成本(或為零).,3.3.2 銷大于產(chǎn)的運輸