運(yùn)輸與指派模型問(wèn)題課件

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

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

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

Aplicationof

TransportationModel7.4

指派問(wèn)題Assignmentproblem

3/9/202317.1運(yùn)輸模型

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

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

8A35B43B38B27B15354231682329圖7.13/9/20233設(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/9/20235地區(qū)產(chǎn)糧區(qū)B1B2B3B4產(chǎn)量A1326310A253828A341295需要量578323從產(chǎn)糧區(qū)運(yùn)出去的量3/9/20236運(yùn)給需求地的量地區(qū)產(chǎn)糧區(qū)B1B2B3B4產(chǎn)量A1326310A253828A341295需要量5783233/9/20237

有些問(wèn)題表面上與運(yùn)輸問(wèn)題沒(méi)有多大關(guān)系，也可以建立與運(yùn)輸問(wè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，如下表所示。問(wèn)如何安排生產(chǎn)任務(wù)使總的加工時(shí)間最少？零件機(jī)床B1B2B3生產(chǎn)任務(wù)A152350A264160A373440需要量7030501503/9/20239

【解】設(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/9/202310則此問(wèn)題的數(shù)學(xué)模型為3/9/202311則數(shù)學(xué)模型為：3/9/202313設(shè)數(shù)學(xué)模型為

7.1.2最大值問(wèn)題3/9/202314第一種方法：將極大化問(wèn)題轉(zhuǎn)化為極小化問(wèn)題。設(shè)極大化問(wèn)題的運(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/作為極小化問(wèn)題的運(yùn)價(jià)表，用表上用業(yè)法求出最優(yōu)解，目標(biāo)函數(shù)值為3/9/2023151.當(dāng)產(chǎn)大于銷(xiāo)時(shí)數(shù)學(xué)模型為即3/9/202317由于總產(chǎn)量大于總銷(xiāo)量，必有部分產(chǎn)地的產(chǎn)量不能全部運(yùn)送完，必須就地庫(kù)存，即每個(gè)產(chǎn)地設(shè)一個(gè)倉(cāng)庫(kù)，庫(kù)存量為xi，n+1（i=1，2，…，m），總的庫(kù)存量為3/9/202318bn+1作為一個(gè)虛設(shè)的銷(xiāo)地Bn+1的銷(xiāo)量。各產(chǎn)地Ai到Bn+1的運(yùn)價(jià)為零，即Ci，n+1=0,（i=1，…，m）。則平衡問(wèn)題的數(shù)學(xué)模型為：具體求解時(shí),只在運(yùn)價(jià)表右端增加一列Bn+1，運(yùn)價(jià)為零,銷(xiāo)量為bn+1即可3/9/2023192.當(dāng)銷(xiāo)大于產(chǎn)時(shí),即數(shù)學(xué)模型為3/9/202321由于總銷(xiāo)量大于總產(chǎn)量,故一定有些需求地不完全滿(mǎn)足,這時(shí)虛設(shè)一個(gè)產(chǎn)地Am+1，產(chǎn)量為xm+1,j是Am+1運(yùn)到Bj的運(yùn)量，也是Bj不能滿(mǎn)足需要的數(shù)量。Am+1到Bj的運(yùn)價(jià)為零,即Cm+1,j=0(j=1,2,…,n)3/9/202322銷(xiāo)大于產(chǎn)平衡問(wèn)題的數(shù)學(xué)模型為：具體計(jì)算時(shí)，在運(yùn)價(jià)表的下方增加一行Am+1，運(yùn)價(jià)為零。產(chǎn)量為am+1即可。3/9/202323先作如下分析：

（1）總產(chǎn)量為180，B1，…，B4的最低需求量20+50+35+45=150<180，這時(shí)屬產(chǎn)大于銷(xiāo)；（2）B1，…，B4的最高需求是60+70+35+45=210>180，這時(shí)屬銷(xiāo)大于產(chǎn);B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20～6050～703545180150～2103/9/202325（3）虛設(shè)一個(gè)產(chǎn)地A5，產(chǎn)量是210－180=30，A5的產(chǎn)量只能供應(yīng)B1或B2。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20～6050～703545180150～2103/9/2023267.1.5中轉(zhuǎn)問(wèn)題產(chǎn)地銷(xiāo)地

A120A230A350A920A815A720A645354231682329圖5.2A4A