運輸問題的數(shù)學模型

01九月2023運輸問題人們在從事生產活動中，不可避免地要進行物資調運工作。如某時期內將生產基地的煤、鋼鐵、糧食等各類物資，分別運到需要這些物資的地區(qū)，根據(jù)各地的生產量和需要量及各地之間的運輸費用，如何制定一個運輸方案，使總的運輸費用最小。這樣的問題稱為運輸問題。第1頁/共10頁01九月2023運輸問題的特征CharacteristicsofTransportationProblems每一個出發(fā)地都有一定的供應量（supply）配送到目的地，每一個目的地都有需要從一定的需求量（demand），接收從出發(fā)地發(fā)出的產品。需求假設（TheRequirementsAssumption）可行解特性（TheFeasibleSolutionsProperty）成本假設（TheCostAssumption）整數(shù)解性質（IntegerSolutionsProperty）第2頁/共10頁01九月2023需求假設（TheRequirementsAssumption）：每一個出發(fā)地都有一個固定的供應量，所有的供應量都必須配送到目的地。與之相類似，每一個目的地都有一個固定的需求量，整個需求量都必須由出發(fā)地滿足，即總供應量＝總需求量

可行解特性（TheFeasibleSolutionsProperty）：當且僅當供應量的總和等于需求量的總和時，運輸問題才有可行解第3頁/共10頁01九月2023成本假設（TheCostAssumption）：從任何一個出發(fā)地到任何一個目的地的貨物配送成本和所配送的數(shù)量成線性比例關系，因此這個成本就等于配送的單位成本乘以所配送的數(shù)量整數(shù)解性質（IntegerSolutionsProperty）：只要它的供應量和需求量都是整數(shù)，任何有可行解的運輸問題必然有所有決策變量都是整數(shù)的最優(yōu)解。因此，沒有必要加上所有變量都是整數(shù)的約束條件第4頁/共10頁01九月2023【例1】現(xiàn)有A1，A2，A3三個產糧區(qū)，可供應糧食分別為10，8，5（萬噸），現(xiàn)將糧食運往B1，B2，B3，B4四個地區(qū)，其需要量分別為5，7，8，3（萬噸）。產糧地到需求地的運價（10萬元/萬噸）如表3－1所示，問如何安排一個運輸計劃，使總的運輸費用最少。鋼鐵廠礦山B1B2B3B4產量A1326310A253828A341295需要量578323運價表（元/噸）表3－1第5頁/共10頁01九月2023設xij(i=1,2,3；j=1,2,3,4)為i個產糧地運往第j個需求地的運量，這樣得到下列運輸問題的數(shù)學模型：運量應大于或等于零（非負要求），即Minz=3x11+2x12+6x13+3x14+5x21+3x22+8x23+2x24

+4x31+x32+2x33+9x34xij0,i=1,2,3;j=1,2,3,4第6頁/共10頁01九月2023

有些問題表面上與運輸問題沒有多大關系，但經過轉換，也可以建立與運輸問題形式相同的數(shù)學模型看一個例子：

【例2】

有三臺機床加工三種零件，計劃第i臺的生產任務為ai(i=1,2,3)個零件，第j種零件的需要量為bj(j=1,2,3)，第i臺機床加工第j種零件需要的時間為cij，如表3－2所示。問如何安排生產任務使總的加工時間最少？零件機床B1B2B3生產任務A152350A264160A373440需要量703050150表3－2第7頁/共10頁01九月2023【解】設xij

(i=1,2,3；j=1,2,3,)為第i臺機床加工第j種零件的數(shù)量，則此問題的數(shù)學模型為第8頁/共10頁01九月2023運輸問題的數(shù)學模型設有m個產地（記作A1，A2，A3,…,Am），生產某種物資，其產量分別為a1,a2，…，am；有n個銷地（記作B1，B2，…，Bn），其需要量分別為b1,b2，…，bn；且產銷平衡，即。從第i個產地到j個銷地的單位運價為cij，在滿足各地需要的前提下，求總運輸費用最小的調運方案。設xij(