運輸與指派模型問題

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

andAssignmentProblem7.1運輸模型

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

Aplicationof

TransportationModel7.4

指派問題Assignmentproblem

3/2/20231運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第1頁!7.1運輸模型

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

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

8A35B43B38B27B15354231682329圖7.13/2/20233運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第3頁!設(shè)xij(i=1,2,3；j=1,2,3,4)為i個產(chǎn)糧地運往第j個需求地的運量，則運輸費用為：地區(qū)產(chǎn)糧區(qū)B1B2B3B4產(chǎn)量A1326310A253828A341295需要量5783233/2/20234運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第4頁!運給需求地的量地區(qū)產(chǎn)糧區(qū)B1B2B3B4產(chǎn)量A1326310A253828A341295需要量5783233/2/20235運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第5頁!

有些問題表面上與運輸問題沒有多大關(guān)系，也可以建立與運輸問題形式相同的數(shù)學(xué)模型【例7.2】有三臺機(jī)床加工三種零件，計劃第i臺的生產(chǎn)任務(wù)為ai(i=1,2,3)個零件(三種零件)，第j種零件的需要量為bj(j=1,2,3)，第i臺機(jī)床加工第j種零件需要的時間為cij，如下表所示。問如何安排生產(chǎn)任務(wù)使總的加工時間最少？零件機(jī)床B1B2B3生產(chǎn)任務(wù)A152350A264160A373440需要量7030501503/2/20236運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第6頁!則此問題的數(shù)學(xué)模型為3/2/20237運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第7頁!則數(shù)學(xué)模型為：3/2/20238運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第8頁!種方法：將極大化問題轉(zhuǎn)化為極小化問題。設(shè)極大化問題的運價表為C=（Cij）m×n，用一個較大的數(shù)M（M≥max{Cij}）去減每一個Cij得到矩陣C′=（C′ij）m×n，其中C/ij=M－Cij≥0,將C/作為極小化問題的運價表，用表上用業(yè)法求出最優(yōu)解，目標(biāo)函數(shù)值為3/2/20239運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第9頁!1.當(dāng)產(chǎn)大于銷時數(shù)學(xué)模型為即3/2/202310運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第10頁!bn+1作為一個虛設(shè)的銷地Bn+1的銷量。各產(chǎn)地Ai到Bn+1的運價為零，即Ci，n+1=0,（i=1，…，m）。則平衡問題的數(shù)學(xué)模型為：具體求解時,只在運價表右端增加一列Bn+1，運價為零,銷量為bn+1即可3/2/202311運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第11頁!2.當(dāng)銷大于產(chǎn)時,即數(shù)學(xué)模型為3/2/202312運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第12頁!銷大于產(chǎn)平衡問題的數(shù)學(xué)模型為：具體計算時，在運價表的下方增加一行Am+1，運價為零。產(chǎn)量為am+1即可。3/2/202313運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第13頁!先作如下分析：

（1）總產(chǎn)量為180，B1，…，B4的最低需求量20+50+35+45=150<180，這時屬產(chǎn)大于銷；（2）B1，…，B4的最高需求是60+70+35+45=210>180，這時屬銷大于產(chǎn);B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20～6050～703545180150～2103/2/202314運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第14頁!（4）將B1與B2各分成兩部分的需求量是20，的需求量是40，的需求量分別是50與20，因此必須由A1，…，A4供應(yīng)，可由A1、…、A5供應(yīng)。B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj2040502035452103/2/202315運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第15頁!7.1.5中轉(zhuǎn)問題產(chǎn)地銷地

A120A230A350A920A815A720A645354231682329圖5.2A4A522715中轉(zhuǎn)地34133/2/202316運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第16頁!【例7.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)糧地到需求地的運價（元/噸）如表7－1所示.問如何安排一個運輸計劃，使總的運輸費用最少。地區(qū)產(chǎn)糧區(qū)B1B2B3B4產(chǎn)量A1326310A253828A341295需要量578323運價表（元/T）表7－13/2/202317運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第17頁!地區(qū)產(chǎn)糧區(qū)B1B2B3B4產(chǎn)量A1326310A253828A341295需要量578323從產(chǎn)糧區(qū)運出去的量3/2/202318運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第18頁!運量應(yīng)大于或等于零（非負(fù)要求），即這樣得到下列運輸問題的數(shù)學(xué)模型：3/2/202319運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第19頁!

【解】設(shè)xij

(i=1,2,3；j=1,2,3,)為第i臺機(jī)床加工第j種零件的數(shù)量，零件機(jī)床B1B2B3生產(chǎn)任務(wù)A152350A264160A373440需要量703050150則總的加工時間為3/2/202320運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第20頁!運輸問題的一般數(shù)學(xué)模型設(shè)有m個產(chǎn)地（記作A1，A2，A3,…,Am），生產(chǎn)某種物資，其產(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é)模型為：3/2/202321運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第21頁!設(shè)數(shù)學(xué)模型為

7.1.2最大值問題3/2/202322運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第22頁!

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

BjAiB1B2B3產(chǎn)量A1659120

A212107100A3698130銷量100100803/2/202323運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第23頁!由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運送完，必須就地庫存，即每個產(chǎn)地設(shè)一個倉庫，庫存量為xi，n+1（i=1，2，…，m），總的庫存量為3/2/202324運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第24頁!2.當(dāng)銷大于產(chǎn)時,即

BjAiB1B2B3產(chǎn)量A1659120

A212107100A3698130銷量2001001503/2/202325運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第25頁!由于總銷量大于總產(chǎn)量,故一定有些需求地不完全滿足,這時虛設(shè)一個產(chǎn)地Am+1，產(chǎn)量為xm+1,j是Am+1運到Bj的運量，也是Bj不能滿足需要的數(shù)量。Am+1到Bj的運價為零,即Cm+1,j=0(j=1,2,…,n)3/2/202326運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第26頁!上例中，假定B1的需要量是20到60之間，B2的需要量是50到70，試求極小化問題的最優(yōu)解。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20～6050～703545180150～2107.1.4需求量不確定的運輸問題3/2/202327運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第27頁!（3）虛設(shè)一個產(chǎn)地A5，產(chǎn)量是210－180=30，A5的產(chǎn)量只能供應(yīng)B1或B2。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20～6050～703545180150～2103/2/202328運輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第28頁!（5）上述A5不能供應(yīng)某需求地的運價用大M表示，A5到、的運價為零。得到下表的產(chǎn)銷平衡表。B3B4aiA155992360A2MM4