運(yùn)籌學(xué)資料2運(yùn)輸問(wèn)題(已修改)
2025-10-25 21:04 本頁(yè)面
【正文】 運(yùn) 輸 規(guī) 劃 (Transportation Problem) 運(yùn)輸規(guī)劃的數(shù)學(xué)模型 表上作業(yè)法 產(chǎn)銷不平衡的運(yùn)輸問(wèn)題 31 運(yùn)輸問(wèn)題 問(wèn)題的提出 從 m個(gè)發(fā)點(diǎn) A1, A2, ….. Am向 n個(gè)收點(diǎn) B1, B2….. Bn發(fā)送某種貨物。 Ai發(fā)點(diǎn)的發(fā)量為 ai， Bj收點(diǎn)的收量為 bj。由 Ai 運(yùn)往 Bj 單位貨物的運(yùn)費(fèi)為 Cij，由 Ai 運(yùn)往 Bj 貨物的運(yùn)量為 Xij。 問(wèn)如何調(diào)配，才能使運(yùn)費(fèi)最??？ 當(dāng)發(fā)點(diǎn)的發(fā)量總和為 ? ai，收點(diǎn)的收量總和為 ? bj相等時(shí)，稱此運(yùn)輸問(wèn)題為平衡運(yùn)輸問(wèn)題。否則稱此運(yùn)輸問(wèn)題為非平衡運(yùn)輸問(wèn)題。 若沒有特別說(shuō)明，均假定運(yùn)輸問(wèn)題為平衡的運(yùn)輸問(wèn)題。 運(yùn)輸問(wèn)題的數(shù)學(xué)模型： Min S=? ? cijxij i j ? xij =ai (i=1,2…..m) j ? xij =bj (j=1,2……n) i xij ? 0(i=1,2…..m。 j=1,2……n) 運(yùn)輸問(wèn)題的數(shù)學(xué)模型： 其中 ai ? 0, bj ? 0, cij ? 0 且共有 m+n 個(gè)約束方程。 并成立： ? ai = ? bj i j 運(yùn)輸問(wèn)題的圖表形式 收點(diǎn)發(fā)點(diǎn)B1B2… . . Bn發(fā)量A1C11C12… . . C1na1A2C21C22… . . C2na2…. … . . … . . … . . … . . ….AmCm1Cm2… . . Cmnam收量 b1b2… . . bn總量運(yùn)輸問(wèn)題解的結(jié)構(gòu) 由于 ? ai = ? bj成立 i j 其 m+n個(gè)約束方程并不是獨(dú)立的。實(shí)際上只有 m+n1個(gè)是獨(dú)立的。即約束方程系數(shù)矩陣的秩為 m+n1。 32 運(yùn)輸問(wèn)題的求解 確定初始方案 1 西北角法 收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A16 5 3 4 4A24 4 7 5 6A37 6 5 8 3收量 2 4 3 4 13（ 1）從圖的西北角開始，填入 a1與 b1較小的值， b1 =2，即從 A1運(yùn)給 B1 （ 2噸） B1已經(jīng)滿足，劃去 b1列，并將 a1=42=2 收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A16 2 5 3 4 4A24 4 7 5 6A37 6 5 8 3收量 2 4 3 4 13（ 2）向 a1， b1運(yùn)價(jià) 較大方向移動(dòng)一格（或向右，或向下）此時(shí)向右移動(dòng)一格（ A1，B2） B2需要 4噸，而 A1只有 2噸， A1已發(fā)完，劃去 A1行，并把 b2改成（ 42） =2。 收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A16 2 5 2 3 4 4A24 4 7 5 6A37 6 5 8 3收量 2 4 3 4 13（ 3）繼續(xù)進(jìn)行 收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A16 2 5 2 3 4 4A24 4 2 7 5 6A37 6 5 8 3收量 2 4 3 4 13（ 4）繼續(xù)進(jìn)行 收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A16 2 5 2 3 4 4A24 4 2 7 3 5 6A37 6 5 8 3收量 2 4 3 4 13（ 5）繼續(xù)進(jìn)行 收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A16 2 5 2 3 4 4A24 4 2 7 3 5 1 6A37 6 5 8 3收量 2 4 3 4 13（ 6）繼續(xù)進(jìn)行 收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A16 2 5 2 3 4 4A24 4 2 7 3 5 1 6A37 6 5 8 3 3收量 2 4 3 4 13（ 7）得到初始方案： X11=2， X12=2，X22=2， X23=3， X24=1， X34=3，總運(yùn)費(fèi)=6*2+5*2+4*2+7*3+5*1+8*3=80（元） 收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A16 2 5 2 3 4 4A24 4 2 7 3 5 1 6A37 6 5 8 3 3收量 2 4 3 4 132 最小元素法 收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A16 5 3 4 4A24 4 7 5 6A37 6 5 8 3收量 2 4 3 4 13（ 1）從最小元素開始（ 3）即 A1優(yōu)先滿足 B3 3個(gè)單位， B3 已經(jīng)滿足，劃去 B3列 ， 收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A16 5 3 3 4 4A24 4 7 5 6A37 6 5 8 3收量 2 4 3 4 13（ 2）再?gòu)淖钚≡亻_始（ 4）即 A1優(yōu)先滿足 B4 1個(gè)單位， A1 已經(jīng)滿足，劃去 A1行 ， 收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A16 5 3 3 4 1 4A24 4 7 5 6A37 6 5 8 3收量 2 4 3 4 13（ 3）再?gòu)淖钚≡亻_始（ 4）即 A2優(yōu)先滿足 B1 2個(gè)單位， B1 已經(jīng)滿足，劃去 B1列 ， 收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A16 5 3 3 4 1 4A24 2 4 7 5 6A37 6 5 8 3收量 2 4 3 4 13（ 4）再?gòu)淖钚≡亻_始（ 4）即A2優(yōu)先滿足 B2 4個(gè)單位， B2 A2已經(jīng)滿足，劃去 B2列 A2 行 。 收點(diǎn)發(fā)點(diǎn)B1B2B3B4發(fā)量A16 5 3 3 4 1 4A2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1