運(yùn)籌學(xué)06-運(yùn)輸問題.ppt

第六章運(yùn)輸問題6.1運(yùn)輸問題的數(shù)學(xué)模型6.2初始基可行解的確定6.3最優(yōu)性檢驗(yàn)與基可行解的改進(jìn)6.4其他運(yùn)輸問題運(yùn)輸問題（紡紗廠）工廠123庫存?zhèn)}121350222430庫334210需求401535運(yùn)輸單價求：運(yùn)輸費(fèi)用最小的運(yùn)輸方案。解：設(shè)xij為i倉庫運(yùn)到j(luò)工廠的原棉數(shù)量其中：i1，2，3j1，2，3MinZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33x11+x12+x1350x21+x22+x2330x31+x32+x3310x11+x21+x3140x12+x22+x3215x13+x23+x3335xij0s.t類似的例子：教材P6-P7，例36.1運(yùn)輸問題的數(shù)學(xué)模型若一家公司擁有多個工廠，這些工廠位于不同的地點(diǎn)，并且生產(chǎn)同一種產(chǎn)品。這些產(chǎn)品要運(yùn)輸?shù)讲煌牡攸c(diǎn)，以滿足用戶的需求（或者如前例中類似的問題）。供應(yīng)節(jié)點(diǎn)：這些工廠，它們是運(yùn)輸?shù)钠瘘c(diǎn)；需求節(jié)點(diǎn)：用戶所在點(diǎn)，它們是運(yùn)輸?shù)慕K點(diǎn)或目的地。同時假定產(chǎn)品不能在供應(yīng)節(jié)點(diǎn)之間運(yùn)輸，也不能在需求節(jié)點(diǎn)之間運(yùn)輸。公司面臨的問題是：應(yīng)如何組織運(yùn)輸，才能在滿足供應(yīng)節(jié)點(diǎn)的供應(yīng)量約束和需求節(jié)點(diǎn)的需求量約束的前提下，使得運(yùn)輸成本最低。這類問題就是運(yùn)輸問題。(1)運(yùn)輸問題數(shù)學(xué)模型xij供應(yīng)節(jié)點(diǎn)i至需求節(jié)點(diǎn)j的運(yùn)輸量；ai供應(yīng)節(jié)點(diǎn)i的可供應(yīng)量，i=1,2,m；bj需求節(jié)點(diǎn)j的需求量，j=1,2,n；cij供應(yīng)節(jié)點(diǎn)i至需求節(jié)點(diǎn)j的單位運(yùn)輸成本。jixnjbxmiaxtsxcZMinijmijijinjijminjijij和對所有的,0,2,1,2,1.1111根據(jù)運(yùn)輸問題中總供應(yīng)量與總需求量的關(guān)系可將運(yùn)輸問題分為兩類：平衡型運(yùn)輸問題和不平衡型運(yùn)輸問題。平衡型運(yùn)輸問題：njjmiiba11不平衡型運(yùn)輸問題：njjmiiba11對于不平衡型運(yùn)輸問題通常通過設(shè)立虛擬供應(yīng)節(jié)點(diǎn)或虛擬需求節(jié)點(diǎn)將其轉(zhuǎn)化為平衡型運(yùn)輸問題求解。(2)運(yùn)輸問題的分類jixnjbxmiaxtsxcZMinijmijijinjijminjijij和對所有的,0,2,1,2,1.1111平衡型運(yùn)輸問題的數(shù)學(xué)模型111111111111111111A模型包含變量：mn個約束方程：m+n個秩：r(A)=m+n-1m行n行(3)運(yùn)輸問題的特征定理：平衡運(yùn)輸問題必有可行解與最優(yōu)解。證：對于平衡運(yùn)輸問題令：njjmiibaQ11jixnjbxmiaxtsxcZMinijmijijinjijminjijij和對所有的,0,2,1,2,1.1111njmiQbaxjiij,2,1,2,1則有njmixij,2,1；,2,10njbaQbQbaxmijijmijimiij,2,1111miabQaQbaxnjijinjjinjij,2,1111所以是運(yùn)輸問題的一個可行解。njmiQbaxjiij