《運(yùn)籌學(xué)與運(yùn)輸問題》

運(yùn)輸規(guī)劃

(TransportationProblem)1.運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型2.表上作業(yè)法3.運(yùn)輸問題的應(yīng)用本章主要內(nèi)容：.1.運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型例3.1某公司從兩個產(chǎn)地A1、A2將物品運(yùn)往三個銷地B1,B2,B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費用最??？B1B2B3產(chǎn)量A1646200A2655300銷量150150200.解：產(chǎn)銷平衡問題：總產(chǎn)量=總銷量＝500設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量表：B1B2B3產(chǎn)量A1x11x12x13200A2x21x22x23300銷量150150200MinC=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1、2；j=1、2、3）.運(yùn)輸問題的一般形式：產(chǎn)銷平衡

A1、A2、…、Am表示某物資的m個產(chǎn)地；B1、B2、…、Bn表示某物質(zhì)的n個銷地；ai

表示產(chǎn)地Ai的產(chǎn)量；bj表示銷地Bj的銷量；cij表示把物資從產(chǎn)地Ai運(yùn)往銷地Bj的單位運(yùn)價。設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列一般運(yùn)輸量問題的模型：.變化：

1）有時目標(biāo)函數(shù)求最大。如求利潤最大或營業(yè)額最大等；2）當(dāng)某些運(yùn)輸線路上的能力有限制時，在模型中直接加入約束條件（等式或不等式約束)；3）產(chǎn)銷不平衡時，可加入假想的產(chǎn)地（銷大于產(chǎn)時）或銷地（產(chǎn)大于銷時）。定理:設(shè)有m個產(chǎn)地n個銷地且產(chǎn)銷平衡的運(yùn)輸問題，則基變量數(shù)為m+n-1。.2.表上作業(yè)法表上作業(yè)法是一種求解運(yùn)輸問題的特殊方法，其實質(zhì)是單純形法。步驟描述方法第一步求初始基行可行解（初始調(diào)運(yùn)方案）西北角法、最小元素法、元素差額法第二步求檢驗數(shù)并判斷是否得到最優(yōu)解當(dāng)非基變量的檢驗數(shù)σij全都非負(fù)時得到最優(yōu)解，若存在檢驗數(shù)σij<0，說明還沒有達(dá)到最優(yōu)，轉(zhuǎn)第三步。閉回路法、位勢法運(yùn)價矩陣法第三步調(diào)整運(yùn)量，即換基，選一個變量出基，對原運(yùn)量進(jìn)行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步閉回路調(diào)整法.例3.2

某運(yùn)輸資料如下表所示：單位銷地運(yùn)價產(chǎn)地產(chǎn)量311310719284741059銷量3656問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費用最?。?解：第1步求初始方案，見下表所示。最小元素法

基本思想是就近供應(yīng)，即從運(yùn)價最小的地方開始供應(yīng)（調(diào)運(yùn)），然后次小，直到最后供完為止。B1B2B3B4產(chǎn)量A17A2

4A39銷量3656311310192741058341633總的運(yùn)輸費＝(3×1)+(6×4)+(4×3)+(1×2)+(3×10)+(3×5)=86元.第2步最優(yōu)解的判別（檢驗數(shù)的求法）

求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗數(shù)來判斷，記xij的檢驗數(shù)為λij由第一章知，求最小值的運(yùn)輸問題的最優(yōu)判別準(zhǔn)則是：所有非基變量的檢驗數(shù)都大于等于，則運(yùn)輸方案最優(yōu)求檢驗數(shù)的方法有三種：閉回路法位勢法（▲）運(yùn)價矩陣法.運(yùn)價矩陣法.當(dāng)存在非基變量的檢驗數(shù)kl<0

且kl=min{ij}時，令Xkl進(jìn)基。從表中知可選x24進(jìn)基。第3步確定換入基的變量第4步確定換出基的變量

以進(jìn)基變量xik為起點的閉回路中，所有偶頂點中的最小運(yùn)量作為調(diào)整量θ，θ對應(yīng)的基變量為出基變量。.閉回路的概念為一個閉回路，集合中的變量稱為回路的頂點，相鄰兩個變量的連線為閉回路的邊。如下表.例下表中閉回路的變量集合是{x11,x12,x42,x43,x23,x25,x35,x31}共有8個頂點，這8個頂點間用水平或垂直線段連接起來，組成一條封閉的回路。B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43

一條回路中的頂點數(shù)一定是偶數(shù)，回路遇到頂點必須轉(zhuǎn)90度與另一頂點連接，上表中的變量x32及x33不是閉回路的頂點，只是連線的交點。.閉回路B1B2B3A1X11X12A2A3X32X33A4X41X43例如變量組

不能構(gòu)成一條閉回路，但A中包含有閉回路

變量組變量數(shù)是奇數(shù)，顯然不是閉回路，也不含有閉回路；.B1B2B3B4UiA1A2A3Vj311310192741058436313(＋)(－)(＋)(－)調(diào)整步驟為：在進(jìn)基變量的閉回路中所有奇頂點對應(yīng)的變量加上調(diào)整量θ，所有偶頂點對應(yīng)的變量減去調(diào)整量θ，其余變量不變，得到一組新的基可行解。125過x24的閉回路為：{x24，x14,x13,x23}.因為所有非基變量的檢驗數(shù)均非負(fù)，故當(dāng)前調(diào)運(yùn)方案即為最優(yōu)方案，如表此時最小總運(yùn)費：Z=(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元.表上作業(yè)法的計算步驟：分析實際問題列出產(chǎn)銷平衡表及單位運(yùn)價表確定初始調(diào)運(yùn)方案（最小元素法或Vogel法）求檢驗數(shù)（位勢法）所有檢驗數(shù)≥0找出絕對值最大的負(fù)檢驗數(shù)，用閉合回路調(diào)整，得到新的調(diào)運(yùn)方案得到最優(yōu)方案，算出總運(yùn)價.表上作業(yè)法計算中的問題：（1）若運(yùn)輸問題的某一基可行解有多個非基變量的檢驗數(shù)為負(fù)，在繼續(xù)迭代時，取它們中任一變量為換入變量均可使目標(biāo)函數(shù)值得到改善，但通常取σij<0中最小者對應(yīng)的變量為換入變量。（2）無窮多最優(yōu)解 產(chǎn)銷平衡的運(yùn)輸問題必定存最優(yōu)解。如果非基變量的σij＝0，則該問題有無窮多最優(yōu)解。.⑵退化解：

※表格中一般要有(m+n-1)個數(shù)字格。但有時在分配運(yùn)量時則需要同時劃去一行和一列，這時需要補(bǔ)一個0，以保證有(m+n-1)個數(shù)字格作為基變量。一般可在劃去的行和列的任意空格處加一個0即可。

※利用進(jìn)基變量的閉回路對解進(jìn)行調(diào)整時，所有偶頂點中的最小運(yùn)量（超過2個最小值）作為調(diào)整量θ，選擇任意一個最小運(yùn)量對應(yīng)的基變量作為出基變量，并打上“×”以示作為非基變量，另一個變量仍為基變量且它的值為0。.3.運(yùn)輸問題的應(yīng)用求極大值問題目標(biāo)函數(shù)求利潤最大或營業(yè)額最大等問題。求解方法：

將極大化問題轉(zhuǎn)化為極小化問題。設(shè)極大化問題的運(yùn)價表為C

，用一個較大的數(shù)M（M≥max{cij}）去減每一個cij得到矩陣C′，其中C′=（M－cij）≥0,將C′作為極小化問題的運(yùn)價表，用表上用業(yè)法求出最優(yōu)解。.例3.3下列矩陣C是Ai（I=1，2，3）到Bj的噸公里利潤,運(yùn)輸部門如何安排運(yùn)輸方案使總利潤最大.銷地產(chǎn)地B1B2B3產(chǎn)量A12589A2910710A365412銷量8149.銷地產(chǎn)地B1B2B3產(chǎn)量A12589A2910710A365412銷量8149得到新的最小化運(yùn)輸問題，用表上作業(yè)法求解即可。.產(chǎn)銷不平衡的運(yùn)輸問題

當(dāng)總產(chǎn)量與總銷量不相等時,稱為不平衡運(yùn)輸問題.這類運(yùn)輸問題在實際中常常碰到,它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解。

當(dāng)產(chǎn)大于銷時，即：數(shù)學(xué)模型為：.由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運(yùn)送完，必須就地庫存，即每個產(chǎn)地設(shè)一個倉庫，假設(shè)該倉庫為一個虛擬銷地Bn+1，bn+1作為一個虛設(shè)銷地Bn+1的銷量(即庫存量)。各產(chǎn)地Ai到Bn+1的運(yùn)價為零，即Ci,n+1=0,（i=1，…，m）。則平衡問題的數(shù)學(xué)模型為：具體求解時,只在運(yùn)價表右端增加一列Bn+1，運(yùn)價為0,銷量為bn+1即可.

當(dāng)銷大于產(chǎn)時，即：數(shù)學(xué)模型為：由于總銷量大于總產(chǎn)量,故一定有些需求地不完全滿足,這時虛設(shè)一個產(chǎn)地Am+1，運(yùn)價為0，產(chǎn)量為：.銷大于產(chǎn)化為平衡問題的數(shù)學(xué)模型為：具體計算時，在運(yùn)價表的下方增加一行Am+1，運(yùn)價為0。產(chǎn)量為am+1即可。

.例3.4求下列表中極小化運(yùn)輸問題的最優(yōu)解。

B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20603545180160因為有：.所以是一個產(chǎn)大于銷的運(yùn)輸問題。表中A2不可達(dá)B1，用一個很大的正數(shù)M表示運(yùn)價C21。虛設(shè)一個銷量為b5=180-160=20，Ci5=0，i=1,2,3,4，表的右邊增添一列，得到新的運(yùn)價表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180.下表為計算結(jié)果?？煽闯觯寒a(chǎn)地A4還有20個單位沒有運(yùn)出。B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180.3.生產(chǎn)與儲存問題例3.5某廠按合同規(guī)定須于當(dāng)年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本如右表。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺每積壓一個季度需儲存、維護(hù)等費用0.15萬元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費用為最小的決策方案。季度生產(chǎn)能力/臺單位成本/萬元Ⅰ2510.8Ⅱ3511.1Ⅲ3011Ⅳ1011.3.解：設(shè)xij為第i季度生產(chǎn)的第j季度交貨的柴油機(jī)數(shù)目，那么應(yīng)滿足：交貨：

x11=10x12+x22=15x13+x23+x33=25x14+x24+x34+x44=20生產(chǎn)：x11+x12+x13+x14≤25x22+x23+x24≤35

x33+x34≤30x44≤10把第i季度生產(chǎn)的柴油機(jī)數(shù)目看作第i個生產(chǎn)廠的產(chǎn)量；把第j季度交貨的柴油機(jī)數(shù)目看作第j個銷售點的銷量；設(shè)cij是第i季度生產(chǎn)的第j季度交貨的每臺柴油機(jī)的實際成本，應(yīng)該等于該季度單位成本加上儲存、維護(hù)等費用。可構(gòu)造下列產(chǎn)銷平衡問題：.jiⅠⅡⅢⅣ產(chǎn)量Ⅰ10.810.9511.111.2525ⅡM11.1011.2511.4035ⅢMM11.0011.1530ⅣMMM11.3010銷量1015252010070由于產(chǎn)大于銷，加上一個虛擬的銷地D，化為平衡問題，即可應(yīng)用表上作業(yè)法求解。.該問題的數(shù)學(xué)模型：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23 +11.4x24+11.0x33+11.15x34+11.3x44

jiⅠⅡⅢⅣD產(chǎn)量Ⅰ10.810.9511.111.25025ⅡM11.1011.2511.40035ⅢMM11.0011.15030ⅣMMM11.30010銷量