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

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

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