1第一章線性規(guī)劃2§1-6運(yùn)輸問題

一.運(yùn)輸問題的數(shù)學(xué)模型二.表上作業(yè)法三.產(chǎn)銷不平衡運(yùn)輸問題3一.運(yùn)輸問題的數(shù)學(xué)模型

在線性規(guī)劃問題求解的實(shí)際工作中，常常會(huì)遇到一些特殊類型的結(jié)構(gòu)，由于這些問題的特殊結(jié)構(gòu)，使得這些可以用比單純形法更簡單的方法來求解。運(yùn)輸問題就是屬于這樣一類比較特殊的結(jié)構(gòu)。

1.問題的提出

2.建表

3.建立數(shù)學(xué)模型41.問題的提出運(yùn)輸問題是這樣提出的：設(shè)有三座鐵礦山Ai（i＝1，2，3），生產(chǎn)礦石，另有四個(gè)煉鐵廠Bj（j＝1，2，3，4）需要礦石，各礦日產(chǎn)量為ai，各廠日需量為bj，以及對應(yīng)的運(yùn)價(jià)（單位物資的運(yùn)輸費(fèi)用）為cij，cij由下面產(chǎn)銷運(yùn)價(jià)表給出。B1B2B3B4aiA16912760A2136142A3513448bj50302545問：應(yīng)怎樣調(diào)運(yùn)礦石才能使運(yùn)費(fèi)最?。?2.建表

根據(jù)問題的結(jié)構(gòu)我們可以給所提供的數(shù)據(jù)建立一個(gè)可供計(jì)算的表格，該表格是我們進(jìn)行表上作業(yè)法的基礎(chǔ)。在該表格中，將產(chǎn)地Ai和銷地Bj分別作為表格的行和列，則由Ai行和Bj列所構(gòu)成的矩陣中的數(shù)即為從Ai產(chǎn)地到Bj銷地的運(yùn)輸費(fèi)用Cij，最后一列為各產(chǎn)地的日產(chǎn)量ai，最后一行為各銷地的日需要量bj，當(dāng)總的日產(chǎn)量和總的日需要量相等，即∑ai＝∑bj時(shí)，稱為產(chǎn)銷平衡運(yùn)輸問題，不相等時(shí)為產(chǎn)銷不平衡運(yùn)輸問題。B1B2B3B4aiA1C11C12C13C14a1A2C21C22C23C24a2A3C31C32C33C34a3bjb1b2b3b4∑ai∑bj6

根據(jù)上面所建表格的構(gòu)成，前面提出的問題可表示為：B1B2B3B4aiA16912760A2136142A3513448bj50302545∑ai=150∑bj=150

再根據(jù)∑ai=∑bj＝150可知：該問題為產(chǎn)銷平衡問題。15073.建立數(shù)學(xué)模型（1）確定決策變量假設(shè)從礦山

Ai（i＝1，2，3）運(yùn)到煉鐵廠Bj（j＝1，2，3，4）的礦石量為決策變量，用xij（i＝1，2，3；j＝1，2，3，4）表示，則決策變量的個(gè)數(shù)為i×j，可以放在表中Cij相應(yīng)的位置，后面我們在計(jì)算的時(shí)候，放在相應(yīng)的Cij的右上角，并用方括弧[]包括，如下表所示。B1B2B3B4aiA1C11[x11]C12[x12]C13[x13]C14[x14]a1A2C21[x21]C22[x22]C23[x23]C24[x24]a2A3C31[x31]C32[x32]C33[x33]C34[x34]a3bjb1b2b3b4∑ai∑bj8（2）確定目標(biāo)函數(shù)根據(jù)“總運(yùn)費(fèi)最小”可得目標(biāo)函數(shù)表達(dá)式為：B1B2B3B4aiA16[x11]9[x12]12[x13]7[x14]60A21[x21]3[x22]6[x23]1[x24]42A35[x31]1[x32]3[x33]4[x34]48bj50302545

1509（3）確定約束條件根據(jù)“各產(chǎn)地產(chǎn)量ai”和“各銷地銷量bj”的限制，可得約束條件表達(dá)式為：B1B2B3B4aiA16[x11]9[x12]12[x13]7[x14]60A21[x21]3[x22]6[x23]1[x24]42A35[x31]1[x32]3[x33]4[x34]48bj50302545

15010上面的約束條件中各變量的系數(shù)用矩陣表示為：x11x12x13x14x21x22x23x24x31x32x33x34J=4111111111111I=311111111111111

從上面的矩陣中很容易發(fā)現(xiàn)該數(shù)學(xué)模型的特點(diǎn)：

約束方程中所有變量的系數(shù)全是1，而且按一定規(guī)律排列；因?yàn)橛校?1)+(2)+(3)＝(4)+(5)+(6)+(7)，所以，約束條件中的7個(gè)方程最多只有6個(gè)是獨(dú)立的。12

因此，對于具有m個(gè)產(chǎn)地，n個(gè)銷地的一般產(chǎn)銷平衡運(yùn)輸問題，其完整的數(shù)學(xué)模型表示為：13

則產(chǎn)銷平衡情況下的約束方程矩陣有m+n行，且有：

由于有上列等式成立，所有(m+n)行矩陣中最多只有(m+n)-1個(gè)獨(dú)立的約束方程。

上面這些特征，使得這一類問題在求解的時(shí)候可以采用一種比較簡便的計(jì)算方法，稱為表上作業(yè)法。

14二.表上作業(yè)法

1.基本步驟

2.尋找初始方案的方法（1）－最小元素法

3.尋找初始方案的方法（2）－最大差值法

4.判斷最優(yōu)解的方法（1）－閉回路法

5.判斷最優(yōu)解的方法（2）－位勢法

6.非最優(yōu)方案的改進(jìn)－閉回路調(diào)整法

7.多最優(yōu)解的判斷及處理方法151.基本步驟

表上作業(yè)法是單純形法在求解運(yùn)輸問題，或者能夠用運(yùn)輸問題的數(shù)學(xué)模型表示的各類問題的一種簡化的方法，所以其實(shí)質(zhì)和理論基礎(chǔ)還是單純形法。該方法的主要步驟可歸納為：

①尋找最初方案。即初始可行解的確定。一般的方法有最小元素法和最大差值法（也叫伏格爾法，vogel法）。

16注意：由于只有m+n-1個(gè)獨(dú)立方程，所以初始可行解中必有一個(gè)為0；在確定初始計(jì)可行解的時(shí)候，由于產(chǎn)銷平衡問題滿足:

所以必然存在xij0,i=1,2,…,m;j=1,2,…,n，即：產(chǎn)銷平衡問題必然有解；又因?yàn)?xij

min（ai，bj），所以該類問題又必定存在一個(gè)最優(yōu)解。（注：為什么？）17②確定所得到的初始解是否是最優(yōu)解。即求非基變量對應(yīng)的檢驗(yàn)數(shù)σ，對于求解目標(biāo)函數(shù)值最小的優(yōu)化問題，如果所有非基變量的檢驗(yàn)數(shù)都為非負(fù)的正數(shù)，則所得方案為最優(yōu)解。一般采用兩個(gè)方法來檢驗(yàn)：閉回路法和位勢法。③如果所得方案為非最優(yōu)解，則要確定換入變量和換出變量，找到新的基可行解。一般采用閉回路法在表上進(jìn)行調(diào)整，直到得到新得基可行解。④回到第二步進(jìn)行判斷，重復(fù)第二步和第三步直到得到最優(yōu)解。182.最小元素法基本思想：就近供應(yīng)（或就廉供應(yīng)）。即從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開始確定供銷關(guān)系，盡量滿足最小運(yùn)價(jià)所需的礦石量，然后次之，直到得到初始可行解。例：對于上面得到的運(yùn)價(jià)及供需量表：B1B2B3B4aiA16912760A2136142A3513448bj50302545在表中找到最小運(yùn)價(jià)，如果出現(xiàn)多個(gè)則任取一個(gè)。

這里，出現(xiàn)C21=C24=C32=1,111

任取C21=1開始，把A2礦山的生產(chǎn)礦石盡量以單位運(yùn)價(jià)為1的運(yùn)費(fèi)供應(yīng)給B1煉鐵廠，運(yùn)送量按下式確定：

1[42]19B1B2B3B4aiA16912760A21[42]36142A3513448bj50302545a(1)60048這時(shí)，A2礦山生產(chǎn)的礦石全部供給了B1廠，不再有可能供給其它煉鐵廠，該行的其它元素不再考慮，用數(shù)字上的×表示不再考慮的元素。該處運(yùn)送量確定以后，各處能夠提供和需要的礦石量調(diào)整如a(1)列和b(1)行所示。3×6×1×b(1)8302545

在剩余的元素中再找最小的。這里C32＝1為最小，即把A3礦山生產(chǎn)的礦石盡量滿足B2煉鐵廠，運(yùn)送量按下式確定：9×a(2)60018b(2)802545則B2列所需的銷量全部從A3得到，不再接受其它礦山的礦石。1[30]20同理：由C33＝3得：由C11＝6得：由C14＝7得：由C13＝12得：由此可以得到初始可行解為：

x21=42;x32=30;x33=18;x11=8;x14=45;x13=7初始方案的運(yùn)輸費(fèi)用為：f1=6×8+12×7+7×45+1×42+1×30+3×18=573完整的計(jì)算過程見下表。21最小元素法計(jì)算表

B1B2B3B4aia(1)a(2)a(3)a(4)a(5)A16[8]9×12[7]7[45]60606060527A21[42]3×6×1×4200000A35×1[30]3[18]4×484818000bj50302545b(1)8302545b(2)802545b(3)80745b(4)00745b(5)0070223.最大差值法基本思想：如果產(chǎn)品不能按最小運(yùn)費(fèi)運(yùn)送，就應(yīng)該考慮次小的運(yùn)費(fèi)。同樣是次小的運(yùn)費(fèi)，也有大小不同。次小運(yùn)費(fèi)和最小運(yùn)費(fèi)的差額越大，說明在該處如果不能以最小運(yùn)費(fèi)運(yùn)送，按次小運(yùn)費(fèi)運(yùn)送的費(fèi)用越大。因此，在進(jìn)行初始分配的時(shí)候應(yīng)該首先在最小運(yùn)費(fèi)和次小運(yùn)費(fèi)差額最大的地方盡量滿足最小運(yùn)費(fèi)所能運(yùn)送的貨物量，以達(dá)到盡量減少運(yùn)費(fèi)的目的。23具體方法如下：①增加一個(gè)行差值hi和列差值kj。行差值：一行中“次小運(yùn)價(jià)”和“最小運(yùn)價(jià)”的差值；列差值：一列中“次小運(yùn)價(jià)”和“最小運(yùn)價(jià)”的差值；②在最大差值的行（或者列）中找到最小的運(yùn)價(jià)，由此處開始分配。③去掉已經(jīng)分配了的行（或列），重新計(jì)算行差值與列差值。④反復(fù)第二、第三步，直到找到完整的初始方案。24還以上面的運(yùn)價(jià)表為例進(jìn)行計(jì)算如下：B1B2B3B4aiA16912760A2136142A3513448bj50302545kjhi42331021[42]3×6×1×b(1)a(1)830254560048K(1)h(1)18931-23[25]12×b(2)a(2)83004560023K(2)h(2)18-31-21[23]5×4×b(3)a(3)8704560006[8]b(4)a(4)0527045009[7]7[45]000所得到的初始運(yùn)費(fèi)為：f2=6×8+9×7+7×45+1×42+1×23+3×25=566254.閉回路法對于求產(chǎn)銷平衡運(yùn)輸費(fèi)用最小這樣結(jié)構(gòu)特殊的最優(yōu)化問題，我們已經(jīng)知道，如果有m+n個(gè)約束方程，最多只有m+n-1獨(dú)立方程和基變量。在表上作業(yè)法中，根據(jù)前面所介紹的方法，可以得出表中有數(shù)字的格對應(yīng)的是基變量。而帶×的格對應(yīng)的是非基變量。約定：把基變量所對應(yīng)的格稱為數(shù)字格；非基變量所對應(yīng)的格稱為空格，用×表示。則閉回路法首先要做的就是要給每一個(gè)空格（帶×的格）找到一條閉回路。26具體做法是：以某個(gè)空格為起點(diǎn)，用水平或者垂直線向前畫，碰到一個(gè)數(shù)字格就轉(zhuǎn)900后繼續(xù)前進(jìn)，直到回到起始空格，這樣就形成一條閉回路。上面所介紹的運(yùn)輸問題的初始方案表如下，其中空格用紅色表示，剩下的即為數(shù)字格。B1B2B3B4A16[8]9[7]12×7[45]A21[42]3×6×1×A35×1[23]3[25]4×

下面將分別從這6個(gè)空格出發(fā)，建立相應(yīng)的閉回路。12×3×6×1×5×4×27B1B2B3B4A16[8]9[7]12×7[45]A21[42]3×6×1×A35×1[23]3[25]4×B1B2B3B4A16[8]9[7]12×7[45]A21[42]3×6×1×A35×1[23]3[25]4×B1B2B3B4A16[8]9[7]12×7[45]A21[42]3×6×1×A35×1[23]3[25]4×B1B2B3B4A16[8]9[7]12×7[45]A21[42]3×6×1×A35×1[23]3[25]4×B1B2B3B4A16[8]9[7]12×7[45]A21[42]3×6×1×A35×1[23]3[25]4×B1B2B3B4A16[8]9[7]12×7[45]A21[42]3×6×1×A35×1[23]3[25]4×28

是不是每一空格都能找到一條而且是唯一的一條閉回路呢？回答是肯定的。因?yàn)閷τ冢╩+n-1）個(gè)數(shù)字格（即基向量），其對應(yīng)的系數(shù)向量是一個(gè)基，而任一空格（即非基變量）所對應(yīng)的系數(shù)向量總可以表示為基的線性組合，即所有的空格都可以表示為數(shù)字格的線性組合，且這種組合是唯一的。29

閉回路法的目的是要求