運籌學第三版之第三章運輸問題第三章運輸問題運輸問題的數(shù)學模型表上作業(yè)法產(chǎn)銷不平衡的運輸問題求初始基可行解的方法：西北角法、最小元素法、元素差額法基可行解的改進方法：閉回路調(diào)整法、位勢法例：某運輸問題的資料如下：單位銷地運價產(chǎn)地產(chǎn)量2910791342584257銷量3846一、運輸問題的數(shù)學模型試制定一個調(diào)運方案，使得總運費最?。?/p>

數(shù)學模型的一般形式

已知資料如下：單位銷運價地產(chǎn)地產(chǎn)量銷量當產(chǎn)銷平衡時，其模型如下：(3.1)當產(chǎn)大于銷時，其模型是：(3.2)當產(chǎn)小于銷時，其模型是：(3.3)

運輸問題的特征：1、平衡運輸問題必有可行解，也必有最優(yōu)解；證設(shè)m行n行第i行第m+j行3、運輸問題的基可行解中應(yīng)包括m+n－1個基變量。前2~m行后n行閉回路：凡是能排列成形式的變量集合，若用一條封閉折線將它們連接起來形成的圖形稱為一個閉回路，其中諸變量稱為閉回路的頂點，連接相鄰兩個頂點及最后一個頂點與第一個頂點的線段稱為閉回路的邊。B1B2B3B4B5A1x11x14A2x21x22A3x32x35A4x44x45閉回路具有以下性質(zhì)：(1)每一個頂點都是轉(zhuǎn)角點；基格：閉回路的頂點閉回路在基格處可以直行，也可以拐彎，在空格處必須直行，不能拐彎。(2)每一條邊都是水平線或垂直線，閉回路是由這些水平線或垂直線構(gòu)成的一條封閉折線；(3)每一行(或列)若有閉回路的頂點，則必有兩個。空格：基格外的格。閉回路的性質(zhì)：充要條件是它不含閉回路。則加入空格后的m+n個格中必含有唯一的閉回路。二、初始基可行解的求法(表上作業(yè)法)運輸問題(3.1)的解法主要有圖上作業(yè)法和表上作業(yè)法兩種。表上作業(yè)法又稱為運輸單純形法，它是根據(jù)單純形法的原理和運輸問題的特征，設(shè)計出來的一種便于在表上運算的方法，作為一種迭代方法，它的主要步驟：(1)求一個初始基可行解(又稱初始調(diào)運方案)；(2)判別當前的基可行解是否為最優(yōu)解，若是，則迭代停止；否則，轉(zhuǎn)下一步；(3)改進當前的基可行解，得新的基可行解，再返回(2)此法是純粹的人為的規(guī)定，沒有理論依據(jù)和實際背景，但它易操作，特別適合在計算機上編程計算，因而備受歡迎。

1、西北角法（或左上角法）：遵循的原則：優(yōu)先安排運價表上編號最小的產(chǎn)地和銷地之間(即運價表的西北角位置)的運輸業(yè)務(wù)。例1設(shè)有某物資共有3個產(chǎn)地A1,A2,A3,其產(chǎn)量分別為9,5,7個單位，另有4個銷地B1,B2,B3,B4,其銷量分別為3,8,4,6,已知由產(chǎn)地Ai運往銷地Bj的單位運價見下表，問應(yīng)如何調(diào)運,才能使總運費最省？1、求初始調(diào)運方案：單位銷地運價產(chǎn)地B1B2B3B4產(chǎn)量A1291079A213425A384257銷量3846單位銷地運價產(chǎn)地B1B2B3B4產(chǎn)量A1291079A213425A384257銷量3846首先安排產(chǎn)地A1與銷地B1之間的運輸業(yè)務(wù)，即從運價表上西北角(或左上角)位置x11開始分配運輸量，并使x11取盡可能大的數(shù)值?，F(xiàn)在產(chǎn)地A1的產(chǎn)量為9,而銷地B1的需求量為3.故安排產(chǎn)地A1運送3個單位的貨物給銷地B1,即取x11=min{a1,b1}=min{3,9}=3，當產(chǎn)地A1運出3個單位貨物后，還剩9-3=6個單位，此時銷地B1的需求量已得到滿足，此時A2,A3不可能再運送貨物給銷地B1了，此時將B1列劃去；再在剩下的運價表上，重復(fù)上述過程，即決定x12306602203301160600A1運送6個單位貨物給B2,此時A1的供應(yīng)量為0，劃去A1行，B2的需求量為2.用同樣的方法得初始基可行解X(0)的各分量為：相應(yīng)的目標函數(shù)值2、最小元素法遵循原則：優(yōu)先安排單位運價最小的產(chǎn)地與銷地之間的運輸業(yè)務(wù)。依次安排最小元素、次小元素，從而得到一個初始基可行解。用此方法制定出來的調(diào)運方案，其總運費一般會比用西北角法制定的調(diào)運方案要省。單位銷地運價產(chǎn)地B1B2B3B4產(chǎn)地A1291079A213425A384257銷地3846例2用最小元素法制定例1的初始調(diào)運方案。第1個最小元素為c21=1,此時比較A2的產(chǎn)量和B1的銷量此時取其最小值，x21=min{5,3}=3,則安排A2運送3個單位貨物給B1,此時A2剩余2個單位，B1的需求量已滿足，將B1列劃去；再在剩余表格中找最小元素c24=2,此時令x24=min{2,6}=2則安排A2運送2個單位貨物給B4,則A2的供應(yīng)量已盡，B4余4個單位，則將A2行劃去；再在剩余表格中重復(fù)以上過程，最終得初始調(diào)運方案。302204403305450500西北角法與最小元素法的比較西北角法的最大優(yōu)點是實現(xiàn)簡單，特別適合編制程序上機計算，但缺點是所制定的初始方案往往離最優(yōu)解較遠，后面的調(diào)整量較大。而最小元素法的最大優(yōu)點是制定的初始方案一般離最優(yōu)解較近，后面調(diào)整量較小。但要在一張大型的運價表上每次搜索最小元素，其計算量也是很可觀的。當然，當問題的規(guī)模不大，用手工計算時，可以通過人的判斷力，很快找到最小元素，因此，用手工計算時，一般采用最小元素法求初始調(diào)運方案較好。3、元素差額法元素差額法是在最小元素法的基礎(chǔ)上改進的一種求初始方案的方法，在分配運量以確定產(chǎn)銷關(guān)系時，不是從最小元素開始，而是從運價表中各行和各列的最小元素和次小元素之差額來確定產(chǎn)銷關(guān)系，(按最大差額所在行或列中的最小元素安排產(chǎn)地與銷地之間的運輸業(yè)務(wù))因此稱為元素差額法。單位銷地運價產(chǎn)地B1B2B3B4產(chǎn)地差額A1291079A213425A384257銷地3846差額

3061512112212123358222500345221305972501100初始調(diào)運方案為1閉回路求檢驗數(shù)對于給定的調(diào)運方案(基可行解)，從非基變量xij出發(fā)作一條閉回路，要求該閉回路上其余的頂點均為基變量，并從xij開始將該閉回路上的頂點順序編號(順時針或逆時針均可)稱編號為奇數(shù)的點為奇點，編號為偶數(shù)的點為偶點，則xij處對應(yīng)的檢驗數(shù)為奇點處運價的總和與偶點處運價的總和之差。(理論依據(jù)：xij處的運量增加一個單位，則閉回路同行中頂點處運量減少一個單位,同列中頂點處運量增加一個單位，依此類推，直至考慮閉回路所有頂點.)閉回路的做法：從空格出發(fā)，遇基格可直行亦可拐彎，遇空格必須直行不可拐彎，目的是保證閉回路的頂點為基格。最優(yōu)性判別與基可行解的改進檢驗數(shù)的求法單位銷地運價產(chǎn)地B1B2B3B4產(chǎn)地A1

291079A213425A384257銷地3846324345用最小元素法求出的例1的初始調(diào)運方案見下表-4x11的檢驗數(shù)為2-7+2-1=-4單位銷地運價產(chǎn)地B1B2B3B4產(chǎn)地A1

291079A213425A384257銷地3846324345用最小元素法求出的例1的初始調(diào)運方案見下表x13的檢驗數(shù)為10-2+4-9=33單位銷地運價產(chǎn)地B1B2B3B4產(chǎn)地A1

291079A213425A384257銷地3846324345用最小元素法求出的例1的初始調(diào)運方案見下表x22的檢驗數(shù)為3-9+7-2=-1-1單位銷地運價產(chǎn)地B1B2B3B4產(chǎn)地A1

291079A213425A384257銷地3846324345用最小元素法求出的例1的初始調(diào)運方案見下表x23的檢驗數(shù)為4-2+7-9+4-2=22單位銷地運價產(chǎn)地B1B2B3B4產(chǎn)地A1

291079A213425A384257銷地3846324345用最小元素法求出的例1的初始調(diào)運方案見下表x31的檢驗數(shù)為8-1+2-7+9-4=77單位銷地運價產(chǎn)地B1B2B3B4產(chǎn)地A1

291079A213425A384257銷地3846324345用最小元素法求出的例1的初始調(diào)運方案見下表x34的檢驗數(shù)為5-7+9-4=33單位銷地運價產(chǎn)地B1B2B3B4產(chǎn)地A1

291079A213425A384257銷地3846324345用最小元素法求出的例1的初始調(diào)運方案見下表-43-12732位勢法求檢驗數(shù)首先寫出運輸問題的對偶問題由于運輸問題的約束條件共有m+n個，前m個是關(guān)于產(chǎn)地的產(chǎn)量限制，后n個是關(guān)于銷地銷量的限制。因此對偶問題中的對偶變量也應(yīng)有m+n個，前m個記為u1,u2,…,um,后n個記為v1,v2,…,vn,并記運輸問題的對偶問題單純形法中有一個重要的規(guī)定，即基變量對應(yīng)的檢驗數(shù)為零，根據(jù)這一原理，可以建立關(guān)于ui,vj的方程組，可以很快求出ui,vj.設(shè)給定了一個初始調(diào)運方案，其基變量為于是得到如下的方程組這個方程組共有m+n-1個方程，可以證明此方程有解，而要確定的未知數(shù)共有m+n個，故其中必有一個自由未知量，取它為任意常數(shù)，就可以把其余的未知量解出來。例如取uij=0,就可以決定其余的ui和vj

vjui單位產(chǎn)地運價銷地B1B2B3B4產(chǎn)地

0

A1

291079

A213425

A384257

銷地3846324345用位勢法求例1中的初始基可行解對應(yīng)的檢驗數(shù)9－577－56由于閉回路法和位勢法中，檢驗數(shù)的定義方式與單純形法完全一致，因此最優(yōu)性判別條件也完全一致。注意運輸問題中的目標函數(shù)是求極小值，于是定理對于運輸問題的一個基可行解，若所有的檢驗數(shù)則此基可行解必為最優(yōu)解?；尚薪獾母倪M確定出基變量的方法利用閉回路調(diào)整法：從進基變量xrs出發(fā)作一條閉回路，并從xrs出發(fā)將該閉回路上的頂點順序編號，則調(diào)整量為調(diào)整的方法是：在該閉回路上，將奇點處的運量加上?，偶點處的運量減去?，而表中的其余點處的運量不變，這樣得到新的基可行解，進基變量的選擇和單純形法一樣

vjui單位產(chǎn)地運價銷地B1B2B3B4產(chǎn)地

0

A1

291079

A213425

A384257

銷地3846324345對例1繼續(xù)求解9－577－56

vjui單位產(chǎn)地運價銷地B1B2B3B4產(chǎn)地

0

A1

291079

A213425

A384257

銷地384643159－577－6235

vjui單位產(chǎn)地運價銷地B1B2B3B4產(chǎn)地

0

A1

291079

A213425

A384257

銷地384643609－577－6235由于檢驗數(shù)全非負，故現(xiàn)有的基可行解即為最優(yōu)解，且最優(yōu)調(diào)運方案為

1、產(chǎn)大于銷：模型方法是先將原問題變成平衡問題，需假設(shè)一個銷地(Bn+1)(實際上考慮產(chǎn)地的存量)，三、產(chǎn)銷不平衡的運輸問題及其求解方法模型為：2、銷大于產(chǎn)：同樣假設(shè)一個產(chǎn)地即可，變化同上。單位運價表中的單位運價為B1B2B3B4A12113470A21035950A378127020304060B1B2B3B4B5

A121134070A210359050A378120702030406040B1B2B3B4B5

A170A250A370203040604040303020302020用最小元素法求初始方案例題：已知某運輸問題的資料如下表所示B1B2B3B4產(chǎn)量A1265315A2132112A3327413銷量10131251、表中的產(chǎn)量、銷量單位為：噸，運價單位為：元/噸,試求出最優(yōu)運輸方案.練習1：2、如將A2的產(chǎn)量改為17，其它資料不變，試求最優(yōu)調(diào)運方案。B1B2B3B4產(chǎn)量A112315A210212A313013銷量1013125B1B2B3B4產(chǎn)量A1265315A2132112A3327413銷量1013125解：1、用最小元素法求初始方案B1B2B3B4產(chǎn)量A112315A210212A313013銷量1013125B1B2B3B4A153A211A324運費為108元/噸2、用位勢法判斷：B1B2B3B4ui

A153u1A211u2A324u3vj

v1v2v3v4成本表B1B2B3B4ui

A153u1A211u2A324u3vj

v1v2v3v4u1+v3=5u2+v4=1u1+v4=3u3+v2=2u2+v1=1u3+v4=4令：u1＝0u1＝0v1＝3u2＝－2v2＝1u3＝1v3＝5v4＝3B1B2B3B4ui

A1530A211－2A3241vj

3153B1B2B3B4ui

A131530A21－131－2A342641vj

3153(ui+vj)B1B2B3B4A12653A21321A33274B1B2B3B4A13153A21－131A34264cij－B1B2B3B4A1－1500A204－10A3－1010＝表中還有負數(shù)，說明沒有得到最優(yōu)解，調(diào)整運輸方案。σij(ui+vj)B1B2B3B4A1123A2102A3130B1B2B3B4A1105A2102A3130＋2＋2－2－2新的運送方案B1B2B3B4A153A212A324新的成本表B1B2B3B4ui

A141530A21－220－3A352641vj

4153(ui+vj)1

總的運費105元/噸B1B2B3B4A14153A21－220A35264B1B2B3B4A12653A21321A33274－＝B1B2B3B4A1－2500A20501A3－2010表中還有負數(shù)，說明沒有得到最優(yōu)解，繼續(xù)調(diào)整運輸方案。cij(ui+vj)1

(σij)1

013A3210A2510A1B4B3B2B13512vj

14623A3－302－2－1A203512A1ui

B4B3B2B1(ui+vj)2

42A32A2352A1B4B3B2B1新的成本表013A312A25010A1B4B3B2B1新的運送方案總的運費85元/噸B1B2B3B4A12653A21321A33274cijB1B2B3B4A12153A2－1－220A33264(ui+vj)2

－＝B1B2B3B4A10500A22501A30010

(σij)2

表中沒有負數(shù)，說明已經(jīng)得到最優(yōu)解。但有無窮多最優(yōu)解。013A312A2510A1B4B3B2B1最終的運送方案總的運費85元/噸B1B2B3B4產(chǎn)量A131215A27512A313013銷量1013125B1B2B3B4產(chǎn)量A1265315A2132112A3327413銷量1013125B1B2B3B4A125A211A327B1B2B3B4ui

A125u1A211u2A327u3vj

v1v2v3v4成本表u1+v1=2u2+v4=1u1+v3=5u3+v2=2u2+v1=1u3+v3=7令：u1＝0u1＝0v1＝2u2＝－1v2＝0u3＝2v3＝5v4＝2B1B2B3B4ui

A120520A21-141-1A342742vj

2052(ui+vj)B1B2B3B4A12653A21321A33274cijB1B2B3B4ui

A10601A204-20A3-1000vj

σijB1B2B3B4產(chǎn)量A131215A27512A313013銷量1013125B1B2B3B4產(chǎn)量A110515A27512A313013銷量1013125B1B2B3B4B5產(chǎn)量A110515A2102517A313013銷量10131255B1B2B3B4B5產(chǎn)量A12653015A21321017A33274013銷量101312552.B1B2B3B4B5A150A2121A324B1B2B3B4B5ui

A150u1A2121u2A324u3vj

v1v2v3v4v5成本表u1+v3=5u2+v3=2u1+v5=0u2+v4=1u2+v1=1u3+v2=2u3+v4=4令：u1＝0u1＝0v1＝4u2＝-3v2＝2u3＝0v3＝5v4＝4v5＝0B1B2B3B4B5ui

A1425400A21-121-3-3A3425400vj

42540(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5

A1-240-10A204004A3-10200σij505B45121310銷量1313A317210A215510A1產(chǎn)量B5B3B2B1B1B2B3B4B5產(chǎn)量A1100515A212517A313013銷量10131255B1B2B3B4B5A1250A221A324B1B2B3B4B5ui

A1250u1A221u2A324u3vj

v1v2v3v4v5成本表u1+v1=2u2+v4=1u1+v3=5u3+v2=2u1+v5=0u3+v4=4u2+v3=2令：u1＝0u1＝0v1＝2u2＝-3v2＝2u3＝0v3＝5v4＝4v5＝0B1B2B3B4B5ui

A1225400A2-1-121-3-3A3225400vj

22540(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5

A1040-10A224004A310200σijB1B2B3B4B5產(chǎn)量A1100515A212517A313013銷量10131255B1B2B3B4B5產(chǎn)量A1100515A212517A313013銷量10131255B1B2B3B4B5產(chǎn)量A110515A212517A31313銷量10131255C=75已知資料如下表所示，問如何供電能使總的輸電費用為最??？發(fā)電廠發(fā)電量A1700A2200A3100城市需電量B1500B2250B3100B4150電力供需表B1B2B3B4A110523A24312A35634單位輸電費用作業(yè)1單位城市輸電發(fā)電廠費用B1B2B3B4發(fā)電量A1105