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

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