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

Chapter3運輸問題Transportation

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

TransportationProblems2.基變量與閉回路BasisVariableandClosedpath3.表上作業(yè)法TransportationSimplexMethod4.運輸問題的變體VariantsofTransportationProblems1/6/2023運輸問題人們在從事生產(chǎn)活動中，不可避免地要進行物資調(diào)運工作。如某時期內(nèi)將生產(chǎn)基地的煤、鋼鐵、糧食等各類物資，分別運到需要這些物資的地區(qū)，根據(jù)各地的生產(chǎn)量和需要量及各地之間的運輸費用，如何制定一個運輸方案，使總的運輸費用最小。這樣的問題稱為運輸問題。1/6/2023運輸問題的特征CharacteristicsofTransportationProblems每一個出發(fā)地都有一定的供應(yīng)量（supply）配送到目的地，每一個目的地都有需要從一定的需求量（demand），接收從出發(fā)地發(fā)出的產(chǎn)品。需求假設(shè)（TheRequirementsAssumption）可行解特性（TheFeasibleSolutionsProperty）成本假設(shè)（TheCostAssumption）整數(shù)解性質(zhì)（IntegerSolutionsProperty）1/6/2023需求假設(shè)（TheRequirementsAssumption）：每一個出發(fā)地都有一個固定的供應(yīng)量，所有的供應(yīng)量都必須配送到目的地。與之相類似，每一個目的地都有一個固定的需求量，整個需求量都必須由出發(fā)地滿足，即總供應(yīng)量＝總需求量

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

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

【例2】有三臺機床加工三種零件，計劃第i臺的生產(chǎn)任務(wù)為ai(i=1,2,3)個零件，第j種零件的需要量為bj(j=1,2,3)，第i臺機床加工第j種零件需要的時間為cij，如表3－2所示。問如何安排生產(chǎn)任務(wù)使總的加工時間最少？零件機床B1B2B3生產(chǎn)任務(wù)A152350A264160A373440需要量703050150表3－21/6/2023【解】設(shè)xij

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