基于等價(jià)轉(zhuǎn)換的產(chǎn)量未定運(yùn)輸模型的優(yōu)化

基于等價(jià)轉(zhuǎn)換的產(chǎn)量未定運(yùn)輸模型的優(yōu)化

1問(wèn)題的描述省略2報(bào)價(jià)購(gòu)買計(jì)劃（1）僅考慮訂單和運(yùn)輸成本，而不考慮裝卸等其他成本。(2)鋼管單價(jià)與訂購(gòu)量、訂購(gòu)次數(shù)、訂購(gòu)日期無(wú)關(guān).(3)訂購(gòu)計(jì)劃是指對(duì)每個(gè)廠商的定貨數(shù)量;運(yùn)輸方案是指具有如下屬性的一批記錄:管道區(qū)間,供應(yīng)廠商,具體運(yùn)輸路線.(4)將每一單位的管道所在地看成一個(gè)需求點(diǎn),向一單位管道的所在地運(yùn)輸鋼管即為向一個(gè)點(diǎn)運(yùn)輸鋼管.3產(chǎn)量上限.pim:鋼廠總數(shù).n:單位管道總數(shù).Si:第i個(gè)鋼廠.si:第i個(gè)鋼廠的產(chǎn)量上限.pi:第i個(gè)鋼廠單位鋼管的銷售價(jià).Ai:管道線上第i個(gè)站點(diǎn).di:管道線上第i個(gè)單位管道的位置.F:總費(fèi)用.Cij:從鋼廠Si(i=1,2,…,m)到點(diǎn)dj(j=1,2,…,n)的最低單位費(fèi)用.4鐵路和銷價(jià)等價(jià)轉(zhuǎn)換法運(yùn)輸費(fèi)用等價(jià)轉(zhuǎn)換法則:按單位運(yùn)費(fèi)相等原則將任意兩點(diǎn)間的最短鐵路線轉(zhuǎn)換為公路線.對(duì)于鐵路線上的任意兩點(diǎn)Vi、Vj,用Floyd算法找出兩點(diǎn)間最短鐵路路線的長(zhǎng)度Lij,查鐵路運(yùn)價(jià)表求得Lij對(duì)應(yīng)的鐵路單位運(yùn)費(fèi)fij;又設(shè)與該段鐵路等費(fèi)用的公路長(zhǎng)度為lij,則:fij=0.1×lij由此,我們就在Vi、Vj之間用一條等價(jià)的公路線來(lái)代替Vi、Vj間的最短鐵路線.如果Vi、Vj之間原來(lái)就有公路,就選擇新舊公路中較短的一條.這樣,我們就把鐵路運(yùn)輸網(wǎng)絡(luò)轉(zhuǎn)換成了公路運(yùn)輸網(wǎng)絡(luò).銷價(jià)等價(jià)轉(zhuǎn)換法則:按單位費(fèi)用相等將任意鋼廠的單位銷價(jià)轉(zhuǎn)換為公路單位運(yùn)價(jià).對(duì)于鋼廠Si的銷售單價(jià)pi,我們可以虛設(shè)一條公路線,連接鋼廠Si及另一虛擬鋼廠S′i,其長(zhǎng)度為li,并且滿足li=0.1×pi;從而將鋼廠的銷售單價(jià)轉(zhuǎn)換成公路運(yùn)輸單價(jià),而新鋼廠S′i的銷售價(jià)為0.將鐵路和銷價(jià)轉(zhuǎn)換為公路的過(guò)程可以由計(jì)算機(jī)編程實(shí)現(xiàn).通過(guò)上述的分析,我們可以將原問(wèn)題化為一個(gè)相對(duì)簡(jiǎn)單的產(chǎn)量未定的運(yùn)輸問(wèn)題,利用A1到A15之間的管道距離和鋼廠和站點(diǎn)之間的公路距離建立一個(gè)產(chǎn)量未定的運(yùn)輸問(wèn)題的模型.但是由于A1,A2,…A15并不能代表所有的實(shí)際需求點(diǎn)(實(shí)際需求點(diǎn)是n個(gè)單位管道),因此,我們可以用Floyd算法進(jìn)一步算出7個(gè)鋼廠到所有實(shí)際的n個(gè)需求點(diǎn)(對(duì)于問(wèn)題一,n=5171;對(duì)于問(wèn)題三,n=5903)的最短路徑,并由此得出一個(gè)具有7個(gè)供應(yīng)點(diǎn)、n個(gè)需求點(diǎn)的產(chǎn)量未定的運(yùn)輸模型.5模型的構(gòu)建如何確定個(gè)產(chǎn)量測(cè)定的模型根據(jù)假設(shè)4,我們可以將每一單位的管道看成一個(gè)需求點(diǎn),向一單位管道的所在地運(yùn)輸鋼管即為向一個(gè)點(diǎn)運(yùn)輸鋼管.對(duì)每個(gè)點(diǎn),我們可以根據(jù)該點(diǎn)的位置和最短等價(jià)公路距離,求出各鋼廠與該點(diǎn)之間最小單位運(yùn)輸費(fèi)用Cij(銷價(jià)已經(jīng)歸入運(yùn)輸費(fèi)用之中了).設(shè)總共有m個(gè)供應(yīng)點(diǎn)(鋼廠),n個(gè)需求點(diǎn),我們就可以得到一個(gè)產(chǎn)量未定的運(yùn)輸模型:有m個(gè)供應(yīng)點(diǎn)、n個(gè)需求點(diǎn),每個(gè)供應(yīng)點(diǎn)的供應(yīng)量ui∈{0}∪{500,si};每個(gè)需求點(diǎn)需要1單位,運(yùn)輸單價(jià)矩陣為C,求使得總運(yùn)輸費(fèi)用最小的運(yùn)輸方案.其數(shù)學(xué)規(guī)劃模型:minF=m∑i=1n∑j=1Cijxijs.t.{n∑j=1xij∈{0}∪{500,Si}i=1,2,?,mm∑i=1xij=1j=1,2,?nxij=0或1其中∶C=(C11?Cm1C12Cm2??C1n?Cmn)為單位費(fèi)用矩陣X=(x11?xm1x12xm2??x1n?xmn)為決策矩陣,也為0-1矩陣minF=∑i=1m∑j=1nCijxijs.t.???????????????????∑j=1nxij∈{0}∪{500,Si}i=1,2,?,m∑i=1mxij=1j=1,2,?nxij=0或1其中∶C=???C11?Cm1C12Cm2??C1n?Cmn???為單位費(fèi)用矩陣X=???x11?xm1x12xm2??x1n?xmn???為決策矩陣,也為0?1矩陣6預(yù)改進(jìn)算法的篩選對(duì)于本題,上述0—1規(guī)劃規(guī)模宏大,現(xiàn)有的一些算法不能勝任,我們必須具體問(wèn)題具體分析,結(jié)合本題實(shí)際情況,尋找行之有效的算法.(1)初始方案的改進(jìn)的最小元素法和改進(jìn)的伏格爾法第i行數(shù)據(jù)的更新改進(jìn)的最小元素法又稱為貪婪法或瞎子爬山法,它的宗旨是每一步都取當(dāng)前的最優(yōu)值.算法步驟為,對(duì)費(fèi)用矩陣C作n次下列循環(huán):①C中找一個(gè)最小值Cij;②令xij=1;③C的第j列的所有數(shù)據(jù)改為+∞;④如果n∑j=1xij=si∑j=1nxij=si,第i個(gè)供應(yīng)點(diǎn)的供應(yīng)量已達(dá)上限,將C的第i行數(shù)據(jù)全改為+∞;對(duì)于問(wèn)題一和問(wèn)題三,我們用貪婪法求得的最小總費(fèi)用的初始分別為:1286692.1萬(wàn)元和1414515.2萬(wàn)元.改進(jìn)的伏格爾法改進(jìn)的最小元素法確定的初始方案往往缺乏全局觀念,即為了節(jié)省一處的費(fèi)用,在其它處要花費(fèi)更多.改進(jìn)的伏格爾法的主要思想:一個(gè)目的地如果不能采用最小值供應(yīng)(供應(yīng)點(diǎn)供應(yīng)不足),就必須考慮次小值供應(yīng),這里就存在一個(gè)差額.差額越大,在不能采用最小值時(shí),損失越大.因此,改進(jìn)的伏格爾法的宗旨是每一步對(duì)當(dāng)前差值最大的點(diǎn)取當(dāng)前最小值.算法的步驟為,對(duì)矩陣C做n次下列循環(huán):①指出每一行最小值與最大值之差最大的一行,第i行,找出該行的最小值為Cij;②令xij=1;③令C的第j列的數(shù)據(jù)為+∞;④如果n∑j=1xij∑j=1nxij=si,第i個(gè)供應(yīng)點(diǎn)供應(yīng)量已達(dá)上限,令C的第i行的所有數(shù)據(jù)為+∞.對(duì)于問(wèn)題一和問(wèn)題三,我們用改進(jìn)的伏格爾法求得方案的總費(fèi)用分別為1279019萬(wàn)元和1407383萬(wàn)元.(2)調(diào)整優(yōu)化調(diào)整優(yōu)化是將一個(gè)離最優(yōu)解很近的初始解調(diào)整到在調(diào)整算法下無(wú)法更優(yōu)的程度.調(diào)整優(yōu)化分兩個(gè)部分,第一部分是用試探法對(duì)供應(yīng)點(diǎn)的供應(yīng)量進(jìn)行優(yōu)化.第二部分是用迭代法對(duì)供應(yīng)點(diǎn)進(jìn)行兩兩對(duì)調(diào)優(yōu)化.整合并進(jìn)行分配保證,從充對(duì)每個(gè)實(shí)際供應(yīng)量在500以下的供應(yīng)點(diǎn),只存在兩種合理的優(yōu)化方法:一種是將其供應(yīng)量增加到500,另一種是將其供應(yīng)量減少到0.試探法將分別試探進(jìn)行下列兩種優(yōu)化:其一是先將供應(yīng)點(diǎn)的供應(yīng)量強(qiáng)行提升至500,使用改進(jìn)的伏格爾法的優(yōu)先順序,從其它供應(yīng)點(diǎn)負(fù)責(zé)供應(yīng)的需求點(diǎn)搶奪一部分,再用對(duì)調(diào)法優(yōu)化至無(wú)法更優(yōu),得出一個(gè)總費(fèi)用F1;其二是先將該供應(yīng)點(diǎn)的供應(yīng)量調(diào)整為0,其原供應(yīng)的需求點(diǎn)由其它鋼廠用改進(jìn)的伏格爾法的優(yōu)先順序補(bǔ)充,再用對(duì)調(diào)法優(yōu)化至無(wú)法更優(yōu),得出一個(gè)總費(fèi)用F2.那么,就應(yīng)當(dāng)采取總費(fèi)用較小的方法.例如,對(duì)于第一問(wèn),按改進(jìn)的伏格爾法獲得的初始方案中,S7的用量?jī)H為245,優(yōu)化時(shí),試探將其降為0和將其提升為500后的最優(yōu)結(jié)果,分別為1279019萬(wàn)元和1280506萬(wàn)元,則說(shuō)明應(yīng)將S7降為0.最優(yōu)條件的確定改進(jìn)的伏格爾法給出的初始值雖然很接近最優(yōu)值,但仍有不足之處,即可能存在兩個(gè)需求點(diǎn),調(diào)換供應(yīng)點(diǎn)能使總費(fèi)用更小,例如,需求點(diǎn)a和b的供應(yīng)點(diǎn)是x和y,費(fèi)用分別是C(x,a)和C(y,b),如果讓y供應(yīng)a,x供應(yīng)b的話,費(fèi)用將是C(y,a)和r(x,b),如果:C(y,a)+r(x,b)<C(x,a)+C(y,b)則說(shuō)明對(duì)調(diào)后總費(fèi)用更低.因此,我們可以采用迭代法對(duì)任意兩個(gè)需求點(diǎn)的供應(yīng)點(diǎn)兩兩對(duì)調(diào)至無(wú)法更優(yōu).由于一共只有m=7個(gè)供應(yīng)點(diǎn),所以兩兩對(duì)調(diào)的可行方案一共有C27=21種,因此,兩兩對(duì)調(diào)供應(yīng)點(diǎn)的方法是可行的,具體步驟如下:Step1對(duì)于任意兩個(gè)供應(yīng)點(diǎn)xi和xji=1,2,…,mj=1,2,…,mi≠j1)找出所有由xi供應(yīng)的需求點(diǎn),構(gòu)成點(diǎn)集A={a1,a2,c}2)找出所有由xj供應(yīng)的需求點(diǎn),構(gòu)成點(diǎn)集B={b1,b2,…}3)對(duì)A中所有點(diǎn),如果改用xj來(lái)供應(yīng),將付出的代價(jià)構(gòu)成向量A′={a′1,a′1,…}4)對(duì)B中所有點(diǎn),如果改用xi來(lái)供應(yīng),將付出的代價(jià)構(gòu)成向量B′={b′1,b′1,…}5)對(duì)A′和B′分別按升序排序.6)同時(shí)對(duì)A′和B′從前向后遍歷,如果a′i+b′i<0(表示對(duì)調(diào)供應(yīng)者將降低總費(fèi)用),則對(duì)調(diào)其供應(yīng)者,直到出現(xiàn)a′i+b′