運(yùn)籌學(xué) 北京郵電大學(xué).ch3-1

Chapter3運(yùn)輸問題Transportation

Problem運(yùn)輸問題是一種特殊的線性規(guī)劃問題,用一種特殊的方法(表上作業(yè)法)求解更為簡(jiǎn)單運(yùn)籌學(xué)OperationsResearch1.運(yùn)輸模型MathematicalModelof

TransportationProblems2.基變量與閉回路BasisVariableandClosedpath3.表上作業(yè)法TransportationSimplexMethod4.運(yùn)輸問題的變體VariantsofTransportationProblems1/6/2023運(yùn)輸問題人們?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)輸問題。1/6/2023運(yùn)輸問題的特征CharacteristicsofTransportationProblems每一個(gè)出發(fā)地都有一定的供應(yīng)量（supply）配送到目的地，每一個(gè)目的地都有需要從一定的需求量（demand），接收從出發(fā)地發(fā)出的產(chǎn)品。需求假設(shè)（TheRequirementsAssumption）可行解特性（TheFeasibleSolutionsProperty）成本假設(shè)（TheCostAssumption）整數(shù)解性質(zhì)（IntegerSolutionsProperty）1/6/2023需求假設(shè)（TheRequirementsAssumption）：每一個(gè)出發(fā)地都有一個(gè)固定的供應(yīng)量，所有的供應(yīng)量都必須配送到目的地。與之相類似，每一個(gè)目的地都有一個(gè)固定的需求量，整個(gè)需求量都必須由出發(fā)地滿足，即總供應(yīng)量＝總需求量

可行解特性（TheFeasibleSolutionsProperty）：當(dāng)且僅當(dāng)供應(yīng)量的總和等于需求量的總和時(shí)，運(yùn)輸問題才有可行解1/6/2023成本假設(shè)（TheCostAssumption）：從任何一個(gè)出發(fā)地到任何一個(gè)目的地的貨物配送成本和所配送的數(shù)量成線性比例關(guān)系，因此這個(gè)成本就等于配送的單位成本乘以所配送的數(shù)量整數(shù)解性質(zhì)（IntegerSolutionsProperty）：只要它的供應(yīng)量和需求量都是整數(shù)，任何有可行解的運(yùn)輸問題必然有所有決策變量都是整數(shù)的最優(yōu)解。因此，沒有必要加上所有變量都是整數(shù)的約束條件1/6/2023【例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à)（10萬元/萬噸）如表3－1所示，問如何安排一個(gè)運(yùn)輸計(jì)劃，使總的運(yùn)輸費(fèi)用最少。鋼鐵廠礦山B1B2B3B4產(chǎn)量A1326310A253828A341295需要量578323運(yùn)價(jià)表（元/噸）表3－11/6/2023設(shè)xij(i=1,2,3；j=1,2,3,4)為i個(gè)產(chǎn)糧地運(yùn)往第j個(gè)需求地的運(yùn)量，這樣得到下列運(yùn)輸問題的數(shù)學(xué)模型：運(yùn)量應(yīng)大于或等于零（非負(fù)要求），即Minz=3x11+2x12+6x13+3x14+5x21+3x22+8x23+2x24

+4x31+x32+2x33+9x34xij0,i=1,2,3;j=1,2,3,41/6/2023有些問題表面上與運(yùn)輸問題沒有多大關(guān)系，但經(jīng)過轉(zhuǎn)換，也可以建立與運(yùn)輸問題形式相同的數(shù)學(xué)模型看一個(gè)例子：

【例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，如表3－2所示。問如何安排生產(chǎn)任務(wù)使總的加工時(shí)間最少？零件機(jī)床B1B2B3生產(chǎn)任務(wù)A152350A264160A373440需要量703050150表3－21/6/2023【解】設(shè)xij

(i=1,2,3；j=1,2,3,)為第i臺(tái)機(jī)床加工第j種零件的數(shù)量，則此問題的數(shù)學(xué)模型為1/6/2023運(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，在滿足各地需要的