Chapter3運輸問題Transportation

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

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

可行解特性（TheFeasibleSolutionsProperty）：當且僅當供應量的總和等于需求量的總和時，運輸問題才有可行解4/8/2025成本假設（TheCostAssumption）：從任何一個出發地到任何一個目的地的貨物配送成本和所配送的數量成線性比例關系，因此這個成本就等于配送的單位成本乘以所配送的數量整數解性質（IntegerSolutionsProperty）：只要它的供應量和需求量都是整數，任何有可行解的運輸問題必然有所有決策變量都是整數的最優解。因此，沒有必要加上所有變量都是整數的約束條件4/8/2025【例1】現有A1，A2，A3三個產糧區，可供應糧食分別為10，8，5（萬噸），現將糧食運往B1，B2，B3，B4四個地區，其需要量分別為5，7，8，3（萬噸）。產糧地到需求地的運價（10萬元/萬噸）如表3－1所示，問如何安排一個運輸計劃，使總的運輸費用最少。鋼鐵廠礦山B1B2B3B4產量A1326310A253828A341295需要量578323運價表（元/噸）表3－14/8/2025設xij

(i=1,2,3；j=1,2,3,4)為i個產糧地運往第j個需求地的運量，這樣得到下列運輸問題的數學模型：運量應大于或等于零（非負要求），即Minz=3x11+2x12+6x13+3x14+5x21+3x22+8x23+2x24

+4x31+x32+2x33+9x34xij0,i=1,2,3;j=1,2,3,44/8/2025有些問題表面上與運輸問題沒有多大關系，但經過轉換，也可以建立與運輸問題形式相同的數學模型看一個例子：

【例2】有三臺機床加工三種零件，計劃第i臺的生產任務為ai(i=1,2,3)個零件，第j種零件的需要量為bj(j=1,2,3)，第i臺機床加工第j種零件需要的時間為cij

，如表3－2所示。問如何安排生產任務使總的加工時間最少？零件機床B1B2B3生產任務A152350A264160A373440需要量703050150表3－24/8/2025【解】設xij

(i=1,2,3；j=1,2,3,)為第i臺機床加工第j種零件的數量，則此問題的數學模型為4/8/2025運輸問題的數學模型設有m個產地（記作A1，A2，A3,…,Am），生產某種物資，其產量分別為a1,a2，…，am；有n個銷地（記作B1，B2，…，Bn），其需要量分別為b1,b2，…，bn；且產銷平衡，即。從第i個產地到j個銷地的單位運價為cij

，在滿足各地需要