1、第七章 運輸問題,7.1 運輸問題的數(shù)學(xué)模型 7.2 運輸問題的應(yīng)用 7.3 表上作業(yè)法,7.1 運輸問題的數(shù)學(xué)模型,(1) 運輸問題的引入,例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ū)到各紡織廠的單位運價如左表,問如何安排運輸方案,使總運費最小.設(shè)由Ai運往Bj的棉花的運量為xij(kt),如右表:,7.1 運輸問題的數(shù)學(xué)模型,(1) 運輸問題的引入,由于各個產(chǎn)棉區(qū)Ai運往各個紡織廠Bj的總量應(yīng)該等于它的產(chǎn)量，所以 x11 + x12 + x13 =

2、70 x21 + x22 + x23 =50 另外,由于各個紡織廠收到各個產(chǎn)棉區(qū)運輸?shù)目偭繎?yīng)該等于它的需求量 x11 + x21 =50 x12 + x22 =40 x13 + x23 =30 目標(biāo)是總運費最小，即 minz=5 x11 +8 x12 +6 x13 +4 x21 +3 x22 +8 x23,7.1 運輸問題的數(shù)學(xué)模型,(1) 運輸問題的引入,此運輸問題的數(shù)學(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 +

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

4、j1,m,n,7.1 運輸問題的數(shù)學(xué)模型,(3) 運輸問題的模型變化,有時目標(biāo)函數(shù)求最大。如求利潤最大或營業(yè)額最大等； 當(dāng)某些運輸線路上的能力有限制時，在模型中直接加入約束條件（等式或不等式約束)； 產(chǎn)銷不平衡時，可加入假想的產(chǎn)地（銷大于產(chǎn)時）或銷地（產(chǎn)大于銷時）。,7.1 運輸問題的數(shù)學(xué)模型,(3) 運輸問題的模型變化,例 某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最小？,增加一個虛設(shè)的銷地運輸費用為0,7.1 運輸問題的數(shù)學(xué)模型,(3) 運輸問題的模型變化,例 某公司從兩個

5、產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最小？,增加一個虛設(shè)的產(chǎn)地運輸費用為0,7.2 運輸問題的應(yīng)用,(1) 產(chǎn)銷不平衡的運輸問題,例 石家莊北方研究院有三個區(qū)。每年分別需要用煤3000、1000、2000噸，由河北臨城、山西盂縣兩處煤礦負(fù)責(zé)供應(yīng)，價格、質(zhì)量相同。供應(yīng)能力分別為1500、4000噸，運價為： 由于需大于供，經(jīng)院研究決定一區(qū)供應(yīng)量可減少0-300噸，二區(qū)必須滿 足需求量，三區(qū)供應(yīng)量不少于1500噸，試求總費用為最低的調(diào)運方案。,解： 根據(jù)題意，作出產(chǎn)銷平衡與運價表： 這里

6、 M 代表一個很大的正數(shù)，其作用是強迫相應(yīng)的 x31、 x33、 x34取值為0。,7.2 運輸問題的應(yīng)用,(1) 產(chǎn)銷不平衡的運輸問題,例 設(shè)有A、B、C三個化肥廠供應(yīng)1、2、3、4四個地區(qū)的農(nóng)用化肥。假設(shè)效果相同，有關(guān)數(shù)據(jù)如下表： 試求總費用為最低的化肥調(diào)撥方案。 解： 根據(jù)題意，作出產(chǎn)銷平衡與運價表：,7.2 運輸問題的應(yīng)用,(2) 生產(chǎn)與存儲問題,例 某廠按合同規(guī)定須于當(dāng)年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如右表。如果生產(chǎn)出來的柴油機當(dāng)季不交貨，每臺每積壓一個季度需儲存、維護等費用0.15萬元。試求在完成合同的情況

7、下，使該廠全年生產(chǎn)總費用為最小的決策方案。,7.2 運輸問題的應(yīng)用,解： 設(shè) xij為第 i 季度生產(chǎn)的第 j 季度交貨的柴油機數(shù)目，那么應(yīng)滿足： 交貨： x11 = 10 生產(chǎn)： 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 季度生產(chǎn)的柴油機數(shù)目看作第 i 個生產(chǎn)廠的產(chǎn)量；把第 j 季度交 貨的柴油機數(shù)目看作第 j 個銷售點的銷量；成本加儲存、維護等費用看作 運費。可構(gòu)造下列產(chǎn)

8、銷平衡問題： 目標(biāo)函數(shù)：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,7.2 運輸問題的應(yīng)用,(3) 轉(zhuǎn)運問題,在原運輸問題上增加若干轉(zhuǎn)運站。運輸方式有：產(chǎn)地 轉(zhuǎn)運站、轉(zhuǎn) 運站 銷地、產(chǎn)地 產(chǎn)地、產(chǎn)地 銷地、銷地 轉(zhuǎn)運站、銷地 產(chǎn) 地等。 例 騰飛電子儀器公司在大連和廣州 有兩個分廠生產(chǎn)同一種儀器，大連分廠 每月生產(chǎn)400臺，廣州分廠每月生產(chǎn)600 臺。該公司在上海和天津有兩個銷售公 司負(fù)責(zé)對南京、濟南、南昌、青島四個

9、城市的儀器供應(yīng)。另外因為大連距離青 島較近，公司同意大連分廠向青島直接 供貨，運輸費用如圖，單位是百元。問應(yīng)該如何調(diào)運儀器， 可使總運輸費用最低？圖中 1- 廣州、2 - 大連、 3 - 上海、4 - 天津、5 - 南京、6 - 濟南、7 - 南昌、8 - 青島,7.2 運輸問題的應(yīng)用,解：設(shè) xij 為從 i 到 j 的運輸量，可得到有下列特點的線性規(guī)劃模型： 目標(biāo)函數(shù)：Min f = 所有可能的運輸費用（運輸單價與運輸量乘積之和） 約束條件： 對產(chǎn)地（發(fā)點） i ：輸出量 - 輸入量 = 產(chǎn)量 對轉(zhuǎn)運站（中轉(zhuǎn)點）：輸入量 - 輸出量 = 0 對銷地（收點） j ：輸入量 - 輸出量 = 銷

10、量 例8（續(xù)） 目標(biāo)函數(shù)： Min f = 2x13+ 3x14+ 3x23+ x24+ 4x28 + 2x35+ 6x36+ 3x37+ 6x38+ 4x45+ 4x46+ 6x47+ 5x48 約束條件： s.t. x13+ x14 600 (廣州分廠供應(yīng)量限制） x23+ x24+ x28 400 (大連分廠供應(yīng)量限制） -x13- x23 + x35 + x36+ x37 + x38 = 0 （上海銷售公司，轉(zhuǎn)運站） -x14- x24 + x45 + x46+ x47 + x48 = 0 （天津銷售公司，轉(zhuǎn)運站） x35+ x45 = 200 （南京的銷量） x36+ x46 = 1

11、50 （濟南的銷量） x37+ x47 = 350 （南昌的銷量） x38+ x48 + x28 = 300 （青島的銷量） xij 0 , i,j = 1,2,3,4,5,6,7,8,7.3 表上作業(yè)法,模型的矩陣表述 表上作業(yè)法的計算步驟 確定初始基可行解 最優(yōu)解的判別 閉回路調(diào)整法,對于平衡運輸問題化成矩陣形式: 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

12、 1 1 1 1 A= 1 1 1 1 1 1 1 1 1 1 1 1 R(A)=m+n-1,7.3.1 模型的矩陣表示,該系數(shù)矩陣中對應(yīng)于變量xij的系數(shù)向量Pij ，其分量中除第i個和第m+j個為1外，其余的都為零。即 Pij (0, 0, 0,1,0, ,0,1,0 , 0)T ei + em+j 對產(chǎn)銷平衡的運輸問題，由于有以下關(guān)系式存在： bj = ( xij )= ( xij )=ai 所以模型最多只有m+n-1個獨立約束方程。即 系數(shù)矩陣的秩m+n-1。,7.3.1 模型的矩陣表示,表上作業(yè)法是運輸問題的特殊求解方法，實質(zhì)是單純形法。 運輸問題都存在最優(yōu)解。 其計算步驟為： （1

13、）找出初始基可行解。即在（mn）產(chǎn)銷平衡表上給出（m+n-1）個數(shù)字格。 （2）求各非基變量的檢驗數(shù)。在表上即是空格的檢驗數(shù)。判別是否達(dá)到最優(yōu)解。如果已經(jīng)是最優(yōu)解，則停止計算，否則轉(zhuǎn)到下一步。 （3）確定換入變量和換出變量，找出新的基可行解。在表上用閉回路法調(diào)整。 （4）重復(fù)（2），（3）直到得到最優(yōu)解(肯定存在)為止。 以上運算都可以在表上進(jìn)行。,7.3.2 表上作業(yè)法的矩陣表示,例 喜慶食品公司有三個生產(chǎn)面包的分廠A1，A2，A3，有四個銷售公司B1，B2，B3，B4，其各分廠每日的產(chǎn)量、各銷售公司每日的銷量以及各分廠到各銷售公司的單位運價如表所示，在表中產(chǎn)量與銷量的單位為噸，運價的單位為

14、百元/噸。問該公司應(yīng)如何調(diào)運產(chǎn)品在滿足各銷點的需求量的前提下總運費最少？ 這是一個產(chǎn)銷平衡的運輸問題，因此不需要再假想產(chǎn)地和銷地。,7.3.3 表上作業(yè)法的計算步驟,一、確定初始基本可行解 為了把初始基本可行解與運價區(qū)分開，我們把運價放在每一欄的右上角，每一欄的中間寫上初始基本可行解（調(diào)運量）。 1.西北角法：先從表的左上角（即西北角）的變量x11開始分配運輸量，并使x11取盡可能大的值，即x11=min(7,3)=3,則x21與x31必為零。同時把B1的銷量與A1的產(chǎn)量都減去3填入銷量和產(chǎn)量處，劃去原來的銷量和產(chǎn)量。同理可得余下的初始基本可行解。,3,11,3,10,8,5,10,2,9,4

15、,7,1,7.3.3 表上作業(yè)法的計算步驟,2.最小元素法 西北角法是對西北角的變量分配運輸量，而最小元素法是就近供應(yīng)，即對單位運價最小的變量分配運輸量。在表上找到單位運價最小的x21，并使x21取盡可能大的值，即x21=min(4,3)=3,把A1的產(chǎn)量改為1，B1的銷量改為0，并把B1列劃去。在剩下的33矩陣中再找最小運價，同理可得其他的基本可行解。 一般來說用最小元素法求得的初始基本可行解比西北角法求得的總運價要少。這樣從用最小元素法求得的初始基本可行解出發(fā)求最優(yōu)解的迭代次數(shù)可能少一些。,3,11,3,10,8,5,10,2,9,4,7,1,7.3.3 表上作業(yè)法的計算步驟,在求初始基本

16、可行解時要注意的兩個問題： 1.當(dāng)我們?nèi)《▁ij的值之后，會出現(xiàn)Ai的產(chǎn)量與Bj的銷量都改為零的情況，這時只能劃去Ai行或Bj列，但不能同時劃去Ai行與Bj列。 2.用最小元素法時，可能會出現(xiàn)只剩下一行或一列的所有格均未填數(shù)或未被劃掉的情況，此時在這一行或者一列中除去已填上的數(shù)外均填上零，不能按空格劃掉。這樣可以保證填過數(shù)或零的格為m+n-1個，即保證基變量的個數(shù)為m+n-1個。,7.3.3 表上作業(yè)法的計算步驟,二、最優(yōu)解的判別 1.閉回路法 所謂閉回路是在已給出的調(diào)運方案的運輸表上從一個代表非基變量的空格出發(fā)，沿水平或垂直方向前進(jìn)，只有遇到代表基變量的填入數(shù)字的格才能向左或右轉(zhuǎn)90度（當(dāng)然

17、也可以不改變方向）繼續(xù)前進(jìn)，這樣繼續(xù)下去，直至回到出發(fā)的那個空格，由此形成的封閉折線叫做閉回路。一個空格存在唯一的閉回路。 所謂閉回路法，就是對于代表非基變量的空格（其調(diào)運量為零），把它的調(diào)運量調(diào)整為1，由于產(chǎn)銷平衡的要求,我們必須對這個空格的閉回路的頂點的調(diào)運量加上或減少1。最后我們計算出由這些變化給整個運輸方案的總運輸費帶來的變化。如果所有代表非基變量的空格的檢驗數(shù)也即非基變量的檢驗數(shù)都大于等于零，則已求得最優(yōu)解，否則繼續(xù)迭代找出最優(yōu)解。,7.3.3 表上作業(yè)法的計算步驟,從非基變量x11出發(fā)，找到一個閉回路如上表所示。回路有四個頂點，除x11外，其余都為基變量?，F(xiàn)在把x11的調(diào)運量從零增

18、加為1噸，運費也增加了3元，為了使A1產(chǎn)量平衡，x13必須減少1噸，運費減少3元。為了B3的銷量平衡，x23必須增加1噸，運費增加2元。同理把x21減少1噸，運費減少1元。調(diào)整后，總運費增加了3-3+2-1=1元。說明如果讓x11為基變量，運費就會增加，其增加值1作為x11的檢驗數(shù)，為了區(qū)別調(diào)整量，我們把1加圈。 用同樣的方法可以找出所有空格（即非基變量）的檢驗數(shù)。,3,11,3,10,8,5,10,2,9,4,7,1,7.3.3 表上作業(yè)法的計算步驟,2.位勢法 所謂位勢法，我們對運輸表上的每一行賦予一個數(shù)值ui，對每一列賦 予一個數(shù)值vj，它們的數(shù)值是由基變量xij的檢驗數(shù) 所決定的，則非基變量xij的檢驗數(shù)就可以用公式