運籌學OperationsResearchChapter7運輸與指派問題Transportation

andAssignmentProblem7.1運輸模型

MathematicalModelofTransportationProblems7.2運輸單純形法TransportationSimplexMethod7.3運輸模型的應用

Aplicationof

TransportationModel7.4

指派問題Assignmentproblem

3/9/202317.1運輸模型

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

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

8A35B43B38B27B15354231682329圖7.13/9/20233設(shè)xij(i=1,2,3；j=1,2,3,4)為i個產(chǎn)糧地運往第j個需求地的運量，則運輸費用為：地區(qū)產(chǎn)糧區(qū)B1B2B3B4產(chǎn)量A1326310A253828A341295需要量5783233/9/20235地區(qū)產(chǎn)糧區(qū)B1B2B3B4產(chǎn)量A1326310A253828A341295需要量578323從產(chǎn)糧區(qū)運出去的量3/9/20236運給需求地的量地區(qū)產(chǎn)糧區(qū)B1B2B3B4產(chǎn)量A1326310A253828A341295需要量5783233/9/20237

有些問題表面上與運輸問題沒有多大關(guān)系，也可以建立與運輸問題形式相同的數(shù)學模型【例7.2】有三臺機床加工三種零件，計劃第i臺的生產(chǎn)任務為ai(i=1,2,3)個零件(三種零件)，第j種零件的需要量為bj(j=1,2,3)，第i臺機床加工第j種零件需要的時間為cij，如下表所示。問如何安排生產(chǎn)任務使總的加工時間最少？零件機床B1B2B3生產(chǎn)任務A152350A264160A373440需要量7030501503/9/20239

【解】設(shè)xij

(i=1,2,3；j=1,2,3,)為第i臺機床加工第j種零件的數(shù)量，零件機床B1B2B3生產(chǎn)任務A152350A264160A373440需要量703050150則總的加工時間為3/9/202310則此問題的數(shù)學模型為3/9/202311則數(shù)學模型為：3/9/202313設(shè)數(shù)學模型為

7.1.2最大值問題3/9/202314第一種方法：將極大化問題轉(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)解，目標函數(shù)值為3/9/2023151.當產(chǎn)大于銷時數(shù)學模型為即3/9/202317由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運送完，必須就地庫存，即每個產(chǎn)地設(shè)一個倉庫，庫存量為xi，n+1（i=1，2，…，m），總的庫存量為3/9/202318bn+1作為一個虛設(shè)的銷地Bn+1的銷量。各產(chǎn)地Ai到Bn+1的運價為零，即Ci，n+1=0,（i=1，…，m）。則平衡問題的數(shù)學模型為：具體求解時,只在運價表右端增加一列Bn+1，運價為零,銷量為bn+1即可3/9/2023192.當銷大于產(chǎn)時,即數(shù)學模型為3/9/202321由于總銷量大于總產(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/9/202322銷大于產(chǎn)平衡問題的數(shù)學模型為：具體計算時，在運價表的下方增加一行Am+1，運價為零。產(chǎn)量為am+1即可。3/9/202323先作如下分析：

（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/9/202325（3）虛設(shè)一個產(chǎn)地A5，產(chǎn)量是210－180=30，A5的產(chǎn)量只能供應B1或B2。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20～6050～703545180150～2103/9/2023267.1.5中轉(zhuǎn)問題產(chǎn)地銷地

A120A230A350A920A815A720A645354231682329圖5.2A4A