運(yùn)輸與指派模型問題

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

andAssignmentProblem7.1運(yùn)輸模型

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

Aplicationof

TransportationModel7.4

指派問題Assignmentproblem

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

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

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

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

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

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

A120A230A350A920A815A720A645354231682329圖5.2A4A522715中轉(zhuǎn)地34133/2/202316運(yùn)輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第16頁!【例7.1】現(xiàn)有A1，A2，A3三個(gè)產(chǎn)糧區(qū)，可供應(yīng)糧食分別為10，8，5（萬噸），現(xiàn)將糧食運(yùn)往B1，B2，B3，B4四個(gè)地區(qū)，其需要量分別為5，7，8，3（萬噸）。產(chǎn)糧地到需求地的運(yùn)價(jià)（元/噸）如表7－1所示.問如何安排一個(gè)運(yùn)輸計(jì)劃，使總的運(yùn)輸費(fèi)用最少。地區(qū)產(chǎn)糧區(qū)B1B2B3B4產(chǎn)量A1326310A253828A341295需要量578323運(yùn)價(jià)表（元/T）表7－13/2/202317運(yùn)輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第17頁!地區(qū)產(chǎn)糧區(qū)B1B2B3B4產(chǎn)量A1326310A253828A341295需要量578323從產(chǎn)糧區(qū)運(yùn)出去的量3/2/202318運(yùn)輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第18頁!運(yùn)量應(yīng)大于或等于零（非負(fù)要求），即這樣得到下列運(yùn)輸問題的數(shù)學(xué)模型：3/2/202319運(yùn)輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第19頁!

【解】設(shè)xij

(i=1,2,3；j=1,2,3,)為第i臺(tái)機(jī)床加工第j種零件的數(shù)量，零件機(jī)床B1B2B3生產(chǎn)任務(wù)A152350A264160A373440需要量703050150則總的加工時(shí)間為3/2/202320運(yùn)輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第20頁!運(yùn)輸問題的一般數(shù)學(xué)模型設(shè)有m個(gè)產(chǎn)地（記作A1，A2，A3,…,Am），生產(chǎn)某種物資，其產(chǎn)量分別為a1,a2，…，am；有n個(gè)銷地（記作B1，B2，…，Bn），其需要量分別為b1,b2，…，bn；且產(chǎn)銷平衡，即

。從第i個(gè)產(chǎn)地到j(luò)個(gè)銷地的單位運(yùn)價(jià)為cij，在滿足各地需要的前提下，求總運(yùn)輸費(fèi)用最小的調(diào)運(yùn)方案。設(shè)xij(i=1,2,…，m；j=1,2,…,n)為第i個(gè)產(chǎn)地到第j個(gè)銷地的運(yùn)量，則數(shù)學(xué)模型為：3/2/202321運(yùn)輸與指派模型問題共30頁，您現(xiàn)在瀏覽的是第21頁!設(shè)數(shù)學(xué)模型為

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

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

BjAiB1B2B3產(chǎn)量A1659120

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

BjAiB1B2B3產(chǎn)量A1659120

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