運籌學(xué)-第四章-運輸與指派問題-第一講-運輸模型與運輸單純形法

運籌學(xué)OperationsResearchChapter4運輸與指派問題Transportation

andAssignmentProblem4.1運輸模型

MathematicalModelofTransportationProblems4.2運輸單純形法TransportationSimplexMethod4.3運輸模型的應(yīng)用

Applicationof

TransportationModel4.4

指派問題AssignmentProblem

4.1運輸模型

MathematicalModelofTransportationProblems人們在從事生產(chǎn)活動中，不可避免地要進行物資調(diào)運工作。如某時期內(nèi)將生產(chǎn)基地的煤、鋼鐵、糧食等各類物資，分別運到需要這些物資的地區(qū)，根據(jù)各地的生產(chǎn)量和需要量及各地之間的運輸費用，如何制定一個運輸方案，使總的運輸費用最小,這樣的問題稱為運輸問題。4.1運輸模型

ModelofTransportationProblems4.1.1數(shù)學(xué)模型產(chǎn)地銷地

A110

A2

8

A35

B43

B38

B27

B15354231682329圖4.1【例4.1】現(xiàn)有A1，A2，A3三個產(chǎn)糧區(qū)，可供應(yīng)糧食分別為10，8，5(萬噸)，現(xiàn)將糧食運往B1，B2，B3，B4四個地區(qū)，其需要量分別為5，7，8，3(萬噸)。產(chǎn)糧地到需求地的運價(元/噸)如表5－1所示，問如何安排一個運輸計劃，使總的運輸費用最少。地區(qū)產(chǎn)糧區(qū)B1B2B3B4產(chǎn)量A1326310A253828A341295需要量578323運價表(元/噸)表5－14.1運輸模型

ModelofTransportationProblems4.1運輸模型

ModelofTransportationProblems設(shè)xij(i=1,2,3；j=1,2,3,4)為i個產(chǎn)糧地運往第j個需求地的運量，這樣得到下列運輸問題的數(shù)學(xué)模型：

【解】注：有些問題表面上與運輸問題沒有多大關(guān)系，也可以建立與運輸問題形式相同的數(shù)學(xué)模型。【例4.2】有三臺機床加工三種零件，計劃第i臺的生產(chǎn)任務(wù)為ai(i=1,2,3)個零件，第j種零件的需要量為bj

(j=1,2,3)，第i臺機床加工第j種零件需要的時間為cij

，如表4－2所示。問如何安排生產(chǎn)任務(wù)使總的加工時間最少？零件機床B1B2B3生產(chǎn)任務(wù)A152350A264160A373440需要量703050150表4－24.1運輸模型

ModelofTransportationProblems【解】設(shè)xij(i=1,2,3；j=1,2,3,)為第i臺機床加工第j種零件的數(shù)量，則此問題的數(shù)學(xué)模型為4.1運輸模型

ModelofTransportationProblems運輸問題的一般數(shù)學(xué)模型設(shè)有m個產(chǎn)地生產(chǎn)某種物資,記作A1,A2,A3,…,Am，其產(chǎn)量分別為a1,a2,…,am；有n個銷地,記作B1，B2，…，Bn，其需要量分別為b1,b2,…,bn；且產(chǎn)銷平衡，即。從第i個產(chǎn)地到j(luò)個銷地的單位運價為cij

，在滿足各地需要的前提下，求總運輸費用最小的調(diào)運方案。設(shè)xij(i=1,2,…，m；j=1,2,…,n)為第i個產(chǎn)地到第j個銷地的運量，則數(shù)學(xué)模型為：4.1運輸模型

ModelofTransportationProblems設(shè)平衡運輸問題的數(shù)學(xué)模型為：4.1.2模型特征:4.1運輸模型

ModelofTransportationProblems1.運輸問題存在可行解，也一定存在最優(yōu)解;

2.當(dāng)供應(yīng)量和需求量都是整數(shù)時，則一定存在整數(shù)最優(yōu)解;3.有m+n個約束，mn個變量;4.有m+n－1個基變量;4.1運輸模型

ModelofTransportationProblems【定理4.1】

設(shè)有m個產(chǎn)地n個銷地且產(chǎn)銷平衡的運輸問題，則基變量數(shù)為m+n-1。分析：由于運輸問題的方程總數(shù)為m+n個，對于平衡型的運輸問題，當(dāng)確定其中的m+n-1個方程后，剩下的一個方程也就確定了，因而平衡運輸問題的基變量共有m+n-1個。詳細(xì)證明過程見書本P95頁，此處略。【證】為了在mn個變量中找出m+n－1個變量作為一組基變量，就是要在A中找出m+n-1個線性無關(guān)的列向量，下面引用閉回路的概念尋找這些基變量。首先介紹一些概念。為一個閉回路，集合中的變量稱為回路的頂點，相鄰兩個變量的連線為閉回路的邊。【定理5.2】

若變量組B

包含有閉回路，則B中的變量對應(yīng)的列向量線性相關(guān)。4.1運輸模型

ModelofTransportationProblems注：由定理4.2可知，當(dāng)一個變量組中不包含有閉回路，則這些變量對應(yīng)的系數(shù)向量線性無關(guān)。孤立點：若變量組中某一變量是它所在行或列中出現(xiàn)的惟一變量，則稱這個變量是關(guān)于變量組的孤立點?！径ɡ?.3】

m+n－1個變量組構(gòu)成基變量的充要條件是它不包含任何閉回路。注：定理4.3告訴了一個求基變量的簡單方法，同時也可以判斷一組變量是否可以作為某個運輸問題的基變量。這種方法是直接在運價表中進行的，不需要在系數(shù)矩陣A中去尋找，從而給運輸問題求初始基可行解帶來極大的方便。4.2運輸單純形法

TransportationSimplexMethod設(shè)平衡運輸問題的數(shù)學(xué)模型為：4.2運輸單純形法

TransportationSimplexMethod運輸單純形法基本思路：是基可行解最優(yōu)否否停運輸單純形法也稱為表上作業(yè)法，是直接在運價表上求最優(yōu)解的一種方法，它的步驟是：

Step1：求初始基可行解(初始調(diào)運方案)。常用的方法有最小元素法、元素差額法(Vogel近似法)、左上角法等。

Step2：求檢驗數(shù)并判斷是否得到最優(yōu)解。常用于求檢驗數(shù)的方法有閉回路法和位勢法，當(dāng)非基變量的檢驗數(shù)λij全都非負(fù)時得到最優(yōu)解，若存在檢驗數(shù)λlk<0，說明還沒有達到最優(yōu)，轉(zhuǎn)第三步。

Step3：調(diào)整運量，即換基。選一個變量出基，對原運量進行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步。4.2運輸單純形法

TransportationSimplexMethod注:

表上作業(yè)法的條件是產(chǎn)銷平衡和運價非負(fù)。4.2.1初始基可行解的確定1.最小元素法：最小元素法的思想是就近優(yōu)先運送，即最小運價Cij

對應(yīng)的變量xij

優(yōu)先賦值然后再在剩下的運價中取最小運價對應(yīng)的變量賦值并滿足約束，依次下去，直到最后得到一個初始基可行解。4.2運輸單純形法

TransportationSimplexMethod【例4.3】求表4－6所示的運輸問題的初始基可行解。表4－6銷地產(chǎn)地B1B2B3產(chǎn)量A1A2A3847634758304525銷量60301010042888B1121051414B2B311696814B4A1A2A3銷量161022產(chǎn)量12銷地產(chǎn)地4311210210686最小元素法：

BjAiB1B2B3產(chǎn)量A186730A243545A374825銷量603010100表4－7【解】30××15×10×25204.2運輸單純形法

TransportationSimplexMethod【例4.4】求表4-10給出的運輸問題的初始基本可行解．

B1B2B3B4aiA14104420A2773815A31210615bj510251050表4-104.2運輸單純形法

TransportationSimplexMethod表4-11

BjAiB1B2B3B4aiA14104420A2773815A31210615bj510251050【解】5××10××××015×10104.2運輸單純形法

TransportationSimplexMethod初始基本可行解可用下列矩陣表示表4－11中，基變量恰好是3+4－1=6個且不包含閉回路，是一組基變量，其余標(biāo)有符號×的變量是非基變量4.2運輸單純形法

TransportationSimplexMethod2．元素差額法(Vogel近似法):最小元素法只考慮了局部運輸費用最小。有時為了節(jié)省某一處的運費，而在其它處可能運費很大。元素差額法對最小元素法進行了改進，考慮到產(chǎn)地到銷地的最小運價和次小運價之間的差額，如果差額很大，就選最小運價先調(diào)運，否則會增加總運費。例如下面兩種運輸方案前一種按最小元素法求得，總運費是Z1=10×8+5×2+15×1=105后一種方案考慮到C11與C21之間的差額是8－2=6，先調(diào)運x21，再是x22，其次是x12這時總運費Z2=10×5+15×2+5×1=85<Z1。4.2運輸單純形法

TransportationSimplexMethod

基于以上思路，元素差額法求初始基本可行解的步驟是：

Step1:求出每行次小運價與最小運價之差，記為ui，i=1,2,…,m；同時求出每列次小運價與最小運價之差，記為vj，j=1，2，…，n；

Step2:找出所有行、列差額的最大值，即L=max{ui，vj}，差額L對應(yīng)行或列的最小運價處優(yōu)先調(diào)運；Step3:這時必有一列或一行調(diào)運完畢，在剩下的運價中再求最大差額，進行第二次調(diào)運，依次進行下去，直到最后全部調(diào)運完畢，就得到一個初始調(diào)運方案。

用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱為近似方案。4.2運輸單純形法

TransportationSimplexMethod沃格爾法：42812105431111968141214161022B1B2B3B4A1A2A3產(chǎn)量銷量銷地產(chǎn)地1254301101201760012354251321321212214881224行罰數(shù)列罰數(shù)所以初始基可行解為x12=12,x14=4,x21=8,x24=2,x32=14,x34=8目標(biāo)函數(shù)值4.2運輸單純形法

TransportationSimplexMethod3.西北角法:(亦稱左上角法)是優(yōu)先從運價表的左上角的變量賦值，當(dāng)行或列分配完畢后，再在表中余下部分的左上角賦值，依次類推，直到右下角元素分配完畢．當(dāng)出現(xiàn)同時分配完一行和一列時，仍然應(yīng)在打“×”的位置上選一個變量作基變量，以保證最后的基變量數(shù)等于m+n－1.42888B112105614B2B311961414B4A1A2A3銷量161022產(chǎn)量12銷地產(chǎn)地4311484681488求出一組基可行解后，判斷其是否最優(yōu)，仍然是用檢驗數(shù)來判斷，記xij的檢驗數(shù)為λij

，由第一章知，求最小值的運輸問題的最優(yōu)判別準(zhǔn)則是：所有非基變量的檢驗數(shù)都非負(fù)，則運輸方案最優(yōu)(即為最優(yōu)解)。求檢驗數(shù)的方法有兩種，閉回路法和位勢法。1．閉回路法求某一非基變量的檢驗數(shù)的方法是：在基本可行解矩陣中，以該非基變量為起點，以基變量為其它頂點，找一條閉回路，由起點開始，分別在頂點上交替標(biāo)上代數(shù)符號+、-、+、-、…，以這些符號分別乘以相應(yīng)的運價，其代數(shù)和就是這個非基變量的檢驗數(shù)。4.2運輸單純形法

TransportationSimplexMethod4.2.2求檢驗數(shù)【解】用最小元素法得到下列一組基本可行解【例4.7】求下列運輸問題的一個初始基本可行解及其檢驗數(shù)。矩陣中的元素為運價Cij

，矩陣右邊的元素為產(chǎn)量ai

，下方的元素為銷量bj

。4.2運輸單純形法

TransportationSimplexMethod只求非基變量的檢驗數(shù)：求λ11，先找出x11的閉回路，對應(yīng)的運價為再用正負(fù)號分別交替乘以運價有直接求代數(shù)和得4.2運輸單純形法

TransportationSimplexMethod

BjAiB1B2B3B4aiA1938470×6010×A2765150××2030A3210922010×10×bj1060403080966-35.2運輸單純形法

TransportationSimplexMethod這里λ34<0，說明這組基本可行解不是最優(yōu)解。注：只要求得的基變量是正確的且數(shù)目為m+n－1，則某個非基變量的閉回路存在且唯一，因而檢驗數(shù)唯一。42888B1121051414B2B311696814B4A1A2A3161022124311210產(chǎn)量銷量銷地產(chǎn)地B1B2B3B4A1A2A3銷量產(chǎn)量銷地產(chǎn)地檢驗數(shù)表閉回路法：(+1)(-1)(-1)(+1)(+1)(+1)(-1)(-1)(-1)1210121-1(+1)2．位勢法求檢驗數(shù):

位勢法求檢驗數(shù)是根據(jù)對偶理論推導(dǎo)出來的一種方法。設(shè)平衡運輸問題為設(shè)前m個約束對應(yīng)的對偶變量為ui(i=1,2,…,m)，后n個約束對應(yīng)的對偶變量為vj(j=1,2,…,n),則運輸問題的對偶問題是4.2運輸單純形法

TransportationSimplexMethod加入松馳變量λij將約束化為等式:ui+vj+λij=cij記原問題基變量XB的下標(biāo)集為I，由第二章對偶性質(zhì)知，原問題xij的檢驗數(shù)的相反數(shù)是對偶問題的松弛變量λij

，當(dāng)（i，j）∈I時λij=0，因而有解上面第一個方程，將ui、vj

代入第二個方程求出λij4.2運輸單純形法

TransportationSimplexMethod【例8】用位勢法求例7給出的初始基本可行解的檢驗數(shù)?！窘狻康谝徊角笪粍輚1、u2、u3及v1、v2、v3、v4。10604030令u1=0得到位勢的解為4.2運輸單純形法

TransportationSimplexMethod再由公式求出檢驗數(shù)，其中Cij是非基變量對應(yīng)的運價。計算結(jié)果與例7結(jié)果相同。4.2運輸單純形法

TransportationSimplexMethodB1B2B3B4產(chǎn)量A1A2A31244112103985116銷量814102681610228141214uivj0411-5-1310銷地產(chǎn)地求位勢：B1B2B3B4產(chǎn)量A1A2A31244112103985116銷量814102681610228141214銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A31244112103985116銷量1610228141214銷地產(chǎn)地0-5-1vj411310ui1200010-1100120求檢驗數(shù)：4.2.3調(diào)整運量當(dāng)某個檢驗數(shù)小于零時，基可行解不是最優(yōu)解，總運費還可以下降，這時需調(diào)整運輸量，改進原運輸方案，使總運費減少，改進運輸方案的步驟是：第一步：確定進基變量:第二步：確定出基變量:

在進基變量xik的閉回路中，標(biāo)有負(fù)號的最小運量作為調(diào)整量θ，θ對應(yīng)的基變量為出基變量，并打上“×”以示作為非基變量。第三步：調(diào)整運量:

在進基變量的閉回路中標(biāo)有正號的變量加上調(diào)整量θ，標(biāo)有負(fù)號的變量減去調(diào)整量θ，其余變量不變，得到一組新的基可行解，然后求所有非基變量的檢驗數(shù)重新檢驗。4.2運輸單純形法

TransportationSimplexMethod

BjAiB1B2B3B4aiA1589270×40×30A236478045×35×A3101214540×2515×bj45655030190

【例4.9】求下列運輸問題的最優(yōu)解表4-194.2運輸單純形法

TransportationSimplexMethod

【解】用最小元素法求得初始基本可行解如表4-19用閉回路法求非基變量的檢驗數(shù)得：

BjAiB1B2B3B4aiA1589270×40×30A23647span>8045×35×A3101214540×2515×bj456550301905.2運輸單純形法

TransportationSimplexMethod+_+_+_因為有4個檢驗數(shù)小于零，所以這組基本可行解不是最優(yōu)解。對應(yīng)的非基變量x11進基.對應(yīng)的非基變量x11進基.x11的閉回路是x33最小，x33是出基量，調(diào)整量θ=15

BjAiB1B2B3B4aiA1589270×40×30A236478045×35×A3101214540×2515×bj456550301904.2運輸單純形法

TransportationSimplexMethod+_+_+_

BjAiB1B2B3B4ai30A236478030×50×A3101214540×40××bj45655030190在x11的閉回路上x11、x32、x23分別加上15，x12、x33、x21分別減去15，并且在x33處打上記號“×”作為基變量，其余變量不變，調(diào)整后得到一組新的基可行解：5.2運輸單純形法

TransportationSimplexMethod

BjAiB1B2B3B4ai30A236478030×50×A31012>14540×40××bj45655030190重新求所有非基變量的檢驗數(shù)得λ13=3，λ22=0，λ24=7，λ31=1，λ33=4，λ34=－1λ34=－1<0,說明還沒有得到最優(yōu)解，x34進基，在x34的閉回路中，標(biāo)負(fù)號的變量x14和x32，調(diào)整量為4.2運輸單純形法

TransportationSimplexMethod

BjAiB1B2B3B4ai×A236478030×50×A3101214540×10×30bj45655030190x14出基，調(diào)整運量得到：再求非基變量的檢驗數(shù)：λ13=3，λ14=1，λ22=0，λ24=8，λ31=1，λ33=44.