數(shù)學(xué)建模中優(yōu)化模型之運(yùn)輸問(wèn)題

運(yùn)輸問(wèn)題

運(yùn)輸問(wèn)題的表示 網(wǎng)絡(luò)圖、線性規(guī)劃模型、運(yùn)輸表

初始基礎(chǔ)可行解 西北角法、最小元素法

求解方法 閉回路法、對(duì)偶變量法

特殊形式運(yùn)輸問(wèn)題 不平衡問(wèn)題、轉(zhuǎn)運(yùn)問(wèn)題2321341運(yùn)輸問(wèn)題網(wǎng)絡(luò)圖s2=27s3=19d1=22d2=13d3=12d4=13s1=14供應(yīng)量供應(yīng)地運(yùn)價(jià)需求量需求地6753842759106運(yùn)輸問(wèn)題線性規(guī)劃模型供應(yīng)地約束需求地約束一般情形：有m各供應(yīng)地，n個(gè)需求地，則有運(yùn)輸問(wèn)題的表格表示——運(yùn)輸表需求地供應(yīng)地1234供應(yīng)量1675314x11x12x13x142842727x21x22x23x2435910619x31x32x33x34需求量221312136060初始基礎(chǔ)可行運(yùn)輸方案—西北角法8131314661234167531428427273591061922131213初始可行解運(yùn)輸方案確定—最小元素法123416753142842727359106192213121312015130113021931020200依運(yùn)費(fèi)從小到大的次序安排運(yùn)輸方案,知道所有限制滿足!5空格改進(jìn)指數(shù)計(jì)算—閉回路法(1)單位費(fèi)用變化：7＋8－6－4＝55閉回路法(2)5單位費(fèi)用變化：5＋8－6－2＝55閉回路法(3)75單位費(fèi)用變化：3＋10＋8－6－2－6＝75閉回路法(4)957單位費(fèi)用變化：7＋10－6－2＝95閉回路法(5)－11579單位費(fèi)用變化：2+5－8－10＝－115閉回路法(6)－3579－11單位費(fèi)用變化：2+9－4－10＝－3空格檢驗(yàn)數(shù)計(jì)算—對(duì)偶變量法(1)v4=0對(duì)偶變量法(2)u3+v4=c34 u3=6對(duì)偶變量法(3)u3+v3=c33 v3=4對(duì)偶變量法(4)u2+v3=c23 u2=－2對(duì)偶變量法(5)u2+v2=c22 v2=6對(duì)偶變量法(6)u2+v1=c21 v1=10對(duì)偶變量法(7)u1+v1=c11 u1=-4對(duì)偶變量法(8)5單位費(fèi)用變化：7－(6＋(－4)＝5對(duì)偶變量法(9)55單位費(fèi)用變化：5－(4＋(－4)＝5對(duì)偶變量法(10)755單位費(fèi)用變化：3－(0＋(－4)＝7對(duì)偶變量法(11)9557單位費(fèi)用變化：7－(0＋(－2)＝9對(duì)偶變量法(12)-115579單位費(fèi)用變化：5－(10＋6)＝－11對(duì)偶變量法(13)-35579-11單位費(fèi)用變化：9－(6＋6)＝－3改進(jìn)調(diào)運(yùn)方案——選擇降低費(fèi)用最大的格子31格增加運(yùn)量，增加幅度min{8,6}=6(負(fù)號(hào)格里最小的)-35579-11調(diào)整運(yùn)量；調(diào)整完后重新計(jì)算檢驗(yàn)數(shù)14格調(diào)整運(yùn)量,調(diào)整量min{14,13}=13+1155-4-2+8調(diào)整運(yùn)量,重新計(jì)算檢驗(yàn)數(shù)所有格子的運(yùn)費(fèi)增加都為正數(shù),得到最優(yōu)解。Minz=6×1+3×13+8×2+4×13+2×12+5×19=1421155482特殊運(yùn)輸問(wèn)題——不平衡運(yùn)輸需求地供應(yīng)地123虛設(shè)需求點(diǎn)供應(yīng)量1675014x11x12x13x142842027x21x22x23x2435910019x31x32x33x33需求量22131510605060特殊運(yùn)輸問(wèn)題——不平衡運(yùn)輸需求地供應(yīng)地123供應(yīng)量A67522x11x12x13B84213x21x22x23C591015x31x32x33虛設(shè)的供應(yīng)地00010x41x42x43需求量142719506060特殊運(yùn)輸問(wèn)題——轉(zhuǎn)運(yùn)問(wèn)題def供量A70408040B60309030C502010020需量303030平衡工廠A,B,C要運(yùn)送某種貨物到倉(cāng)庫(kù)d,e,f去,運(yùn)輸表如下.但現(xiàn)在所有這些工廠或倉(cāng)庫(kù)又都可以作為轉(zhuǎn)運(yùn)點(diǎn),如:A可運(yùn)往B再運(yùn)往各倉(cāng)庫(kù),工廠與倉(cāng)庫(kù)間地運(yùn)費(fèi)如下表.試建立模型求解費(fèi)用最小的調(diào)運(yùn)方案.轉(zhuǎn)運(yùn)1ABCA02030B20025C30250轉(zhuǎn)運(yùn)2defd02020e20015f20150提示：假設(shè)：1)

沿相反方向的同線路運(yùn)費(fèi)相同;2)

設(shè)定合理的轉(zhuǎn)運(yùn)量(如總產(chǎn)量)；

建模：將工廠及倉(cāng)庫(kù)既作為供應(yīng)點(diǎn)也作為需求點(diǎn)建立運(yùn)輸表;注意：有興趣的話——建立運(yùn)輸表、寫出規(guī)劃模型、解出結(jié)果(編程最好)、推廣到混合型問(wèn)題(含純發(fā)/純收/可收可發(fā)類問(wèn)題)、并分析轉(zhuǎn)運(yùn)量對(duì)結(jié)果的影響.需求地供應(yīng)地ABCdef供量A020307040801309040B200256030901205070C3025050201001102090d70605002020903060e40302020015906030f8090100201509090需量909090120120120＝××××××××××××××××-15-25-75-15-15-65-20-15-50運(yùn)費(fèi)——8700需求地供應(yīng)地ABCDef供量A0203070408013090B200256030901209030C3025050201001106050d70605002020907020e40302020015906030f8090100201509090需量909090120120120＝××××××××××××××××-15-65-20-15-5040××××運(yùn)費(fèi)——5550需求地供應(yīng)地ABCdef供量A020307040801309040B20025603090120901020C3025050201001108030d706050020209090e40302020015906030f8090100201509090需量909090120120120＝××××××××××××-25××××-5-15×-15××××運(yùn)費(fèi)——4400需求地供應(yīng)地ABCdef供量A020307040801309040B200256030901209030C3025050201001109020d706050020209090e4030202001590105030f8090100201509090需量909090120120120＝××××××××××××××××××-10××××××運(yùn)費(fèi)——3950需求地供應(yīng)地ABCdef供量A020307040801309040B200256030901209030C3025050201001109020d706050020209090e4030202001590303030f8090100201509090需量909090120120120＝×××××××××××××××××××××××××運(yùn)費(fèi)——3500需求地供應(yīng)地ABCdef供量A02030704080130901030B20025603090