運(yùn)籌學(xué)07-運(yùn)輸問題.ppt

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

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

3、學(xué)模型為: 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 運(yùn)輸問題的數(shù)學(xué)模型,(2) 運(yùn)輸問題的一般數(shù)學(xué)模型,運(yùn)輸問題的一般描述: m個產(chǎn)地Ai,I=1,2.,m,產(chǎn)量分別為ai個單位, n個產(chǎn)地Bj,j=1,2.,n,產(chǎn)量分別為bj個單位; Ai與Bj之間的單位運(yùn)價(jià)爲(wèi)Cij ,問如何安排運(yùn)輸方案,使總運(yùn)費(fèi)最少?,3.1 運(yùn)輸問題的數(shù)學(xué)

4、模型,(2) 運(yùn)輸問題的一般數(shù)學(xué)模型,此問題的數(shù)學(xué)模型: 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 。,運(yùn)輸問題的特點(diǎn),系數(shù)矩陣為0-1稀疏矩陣， 系數(shù)矩陣為m+n行,mn列的矩陣 系數(shù)矩陣的秩為m+n-1 需求總量與總產(chǎn)量相等則約束條件為等式約束。,3.2 表上作業(yè)法,模型的矩陣表述 表上作業(yè)法的計(jì)算步驟 確定初始基可行解 最優(yōu)解的判別 閉回

5、路調(diào)整法,對于平衡運(yùn)輸問題化成矩陣形式: 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ù)矩陣中對應(yīng)于變量xij的系數(shù)向量Pij ，其分量中除第i個和第m+j個為1外，其余的都為零。即 Pij (0, 0, 0,1,0, ,0,1,0 , 0

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

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

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

9、的偶數(shù)頂點(diǎn)運(yùn)價(jià)之和 閉回路上的奇數(shù)頂點(diǎn)運(yùn)價(jià)之和),閉回路: 以某空格為起點(diǎn)，用水平或垂直線向前劃，每(?)碰到一數(shù)字格轉(zhuǎn)90度后，繼續(xù)前進(jìn)，直到回到起始空格為止，得到一個閉回路。 從每一個空格出發(fā)一定存在和可以找到一個惟一的閉回路。（非基變量對應(yīng)的系數(shù)列向量由基唯一地線性表示）,閉回路法,閉回路法,閉回路法,23=3-6+3-2=-2,閉回路法,位勢法（推薦）,設(shè)u1, u2 , um;v1 , v2 , , vn是對應(yīng)運(yùn)輸問題的m+n個約束條件的對偶變量。B是含有一個人工變量xa 的(m+n)(m+n)初始基矩陣。人工變量在目標(biāo)函數(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 。于是檢驗(yàn)數(shù) ij cij CB B-1 Pij = cij （ uivj ） 當(dāng)xij為基變量時(shí)，有cij （ uivj ）=0,即uivjcij 非基變量的檢驗(yàn)數(shù)為：ij cij （ uivj ） 其中cij為對應(yīng)的運(yùn)價(jià)，稱 ui為對應(yīng)的行位勢， vj為對應(yīng)的列位勢。,位勢法（步驟）,位勢法： 第一步：給出初始解，在對應(yīng)的數(shù)字格處填入單位運(yùn)價(jià)。 第二步：在表中增加一行一列，在列中填入u1, u2 , , um，在行中填入v1 ,

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

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

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

14、6142 323 15 36(元),無窮多最優(yōu)解,此運(yùn)輸問題的解為上述兩個特解的凸組合。,表上作業(yè)法的解題過程,分析實(shí)際問題,建立運(yùn)輸表,求出初始方案 (最小元法或伏格爾法),找出絕對值最大的負(fù)檢驗(yàn)數(shù), 經(jīng)閉回路調(diào)整法得新方案,得最優(yōu)解, 算出運(yùn)費(fèi),終止,求出檢驗(yàn)數(shù) (閉回路法或位勢法),是,否,所有檢 驗(yàn)數(shù)0,產(chǎn)大于銷( ai bJ )的情況 銷大于產(chǎn)( ai bJ )的情況 習(xí)題,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) 引人虛設(shè)的銷地Bn+1其需要量為:bn+1= ai - bj ,這樣,m個產(chǎn)地、n個銷地的不平衡運(yùn)輸問題,轉(zhuǎn)換為m個產(chǎn)地,n+1個銷地的平衡問題. 計(jì)算中,在運(yùn)輸表中添加Bn+1這列,其需求量為: bn+1= ai - bj, Ai到Bn+1的單位運(yùn)價(jià)為單位存儲費(fèi)用(或?yàn)榱?。,3.3.1 產(chǎn)大于銷的運(yù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) 引人虛設(shè)的產(chǎn)地Am+1其產(chǎn)量為:am+1 bj - ai,等于銷地的物資缺少量 。這樣,m個產(chǎn)地、n個銷地的不平衡運(yùn)輸問題就轉(zhuǎn)換為m +1個產(chǎn)地,n個銷地的平衡問題. 計(jì)算中,在運(yùn)輸表中添加Am+1這行,其產(chǎn)量為am+1 bj - ai , Am+1到Bj的單位運(yùn)價(jià)為單位缺貨成本(或?yàn)榱?.,3.3.2 銷大于產(chǎn)的運(yùn)輸