多商品配送問題的數(shù)學(xué)模型及快速算法

PAGEPAGE18多商品配送問題的數(shù)學(xué)模型及快速算法摘要:多商品的配送問題日益成為現(xiàn)實社會的熱點。本文描述了商品價格，需求以及銷售網(wǎng)絡(luò)已定的前提下，一個多貨棧多商品多客戶的供貨商如何制定商品配送計劃，以實現(xiàn)供應(yīng)成本的最小化。在考慮了運輸成本與時間的關(guān)系以及提前/推遲供貨帶來的懲罰之后，以實現(xiàn)運輸成本與懲罰之和最小為目標，進行了系統(tǒng)建模。首先建立了原始模型，分析模型結(jié)構(gòu)后，討論了幾種可行的算法。然后在運輸時間小于一個訂貨時段，懲罰與誤期的時段成正比的假定下，將模型轉(zhuǎn)化為可求解的線性規(guī)劃模型，并由最簡單的情況開始逐級深化討論模型。對各個簡化模型，給出相應(yīng)的具體算例，用lingo進行求解，結(jié)果分析表明了模型的正確性和有效性。當深化為多貨棧多商品多零售商模型時，通過深入分析模型，提出一種快速算法，并由lingo編程實現(xiàn)，極大地減少了線性規(guī)劃的變量個數(shù)（由O（）減少為O（）），降低了線性規(guī)劃的復(fù)雜度。通過兩種算法對帶有個變量的大規(guī)模銷售網(wǎng)絡(luò)的計算比較，驗證了快速算法的優(yōu)越性。最后根據(jù)一種更符合實際情況的假設(shè)，進一步優(yōu)化，建立了更加有效，更加節(jié)省成本的供銷模型。關(guān)鍵詞：多商品配送提前/推遲供貨懲罰運輸成本二次規(guī)劃線性規(guī)劃快速算法優(yōu)化模型一、問題的重述：考慮供貨商的多種商品配送問題．假設(shè)該供貨商在某地區(qū)有多個倉儲的貨棧，它們位于該地區(qū)的不同地點．供貨商的目標是按照不同零售商的需求將商品及時發(fā)送給零售商，使總成本盡可能?。@里的總成本主要由以下幾部分組成．（1）運輸成本，它與運輸?shù)臅r間和運輸?shù)纳唐废嚓P(guān)．（2）由于貨?？梢砸圆煌瑑r格將同一種商品供給不同的零售商，且同一種商品在不同貨棧的售價也可以不同，這樣零售商會按照價格優(yōu)先的原則選擇發(fā)貨的貨棧．另一方面，每一時段每個商品在貨棧中的存儲量有一個上限．當一個貨棧被指派為一個特定的零售商提供規(guī)定數(shù)量的商品的時候，可能會出現(xiàn)零售商的需求和貨棧儲量不平衡的情況．當某時段容量不足的時候，貨棧通過提前或推遲供貨給零售商的方式來補償需求．如果提前供應(yīng)，將會導(dǎo)致零售商的商品持有成本上升,因此零售商會向供貨商索要賠償；若推遲,則會降低貨棧的信譽，且零售商也會向供貨商索要賠償．所以，提前和推遲所帶來的賠償都是供應(yīng)成本的一部分，而賠償費用與商品的價格和提前、推遲的時間有關(guān)．現(xiàn)假設(shè)在一個周期（例如一年）開始時，每個零售商對所有商品在不同時間(時段)的需求已知，以及商品的價格已知，問題是供貨商如何安排不同時間(時段)的供貨，使得一個周期的總成本盡可能小．1．對此問題，并針對你所理解的實際中的多商品配送問題，建立數(shù)學(xué)模型,討論求解算法的設(shè)計．2．分析當運輸成本和運輸?shù)臅r間是什么關(guān)系,提前、推遲懲罰與商品的價格以及提前、推遲的時間是什么關(guān)系時，或在其他你認為合理的假設(shè)下，該問題可以有快速算法求解．這里，你對這些關(guān)系的假設(shè)應(yīng)與實際背景較吻合．3．舉一個和幾個實際算例來說明你的算法或模型．二、問題的分析考慮某地區(qū)的一個供貨商，有J個貨棧，分布在該地區(qū)的不同地方。該供貨商可提供K種商品，每一個貨?？蓳碛腥康纳唐芬部梢允瞧渲械囊徊糠郑恳粋€貨棧又給多個零售商供貨。假設(shè)供貨商給I個零售商供貨。在一個周期T（例如一年，并分為T個時段）開始時，每個零售商對所有商品在不同時段的需求已知，每種商品的價格已知，且這一價格在一個周期內(nèi)保持不變。零售商選擇價格最低的一個貨棧給它供貨（如果存在多個最低價格時，由零售商任意選擇其中的一個），因此一個周期內(nèi)貨棧與零售商間的銷售網(wǎng)絡(luò)已經(jīng)確定。我們認為根據(jù)所給價格既定的銷售網(wǎng)絡(luò)是健康的，不存在極度不平衡的供需關(guān)系。該問題考慮的供應(yīng)成本由兩部分組成：運輸成本和由于提前或延誤供貨造成的賠償：（1）、運輸成本。該供貨商在不同的地方設(shè)有多個貨棧，而該地區(qū)的零售商也位于不同的地方，因此存在運輸問題，即運輸時間、運輸費用。設(shè)運輸成本為G，它與運輸時間，運輸商品的種類k及運輸量有關(guān)。（2）、由于提前或延誤供貨造成的賠償，，稱為懲罰函數(shù)，表示x單位價格的商品提前或延誤時段對零售商的賠償。當＝0或x＝0時，F(xiàn)＝0；當<0時，表示提前供貨；當>0時表示推遲供貨。三、基本假設(shè)1、零售商以時段為時間間隔向零售商訂貨，且每一時段至多訂一次貨。貨棧以時段為時間間隔給零售商發(fā)貨，且每一時段至多發(fā)一次貨。當某貨棧某時段容量不足時，供貨商只通過由零售商按價格最低原則選定的貨棧提前或推遲供貨的方式來補償需求，而不考慮貨棧之間的相互調(diào)貨，或者由其它貨棧給該零售商供貨。供貨商有充足的運輸能力，運輸成本只與時間與運輸商品以及運輸量有關(guān)，而不考慮具體的運輸細節(jié)。當配送區(qū)域比較大的時候，運輸?shù)臅r間可能比較長，貨物經(jīng)過幾個時段才能送到零售商處。這時，供貨商為了協(xié)調(diào)供貨以達到總成本的最小，可以選擇不同的方式，改變運輸時間，從而改變運輸成本。[1]當配送區(qū)域比較小的時候，運輸時間比較短，與一個時段相比可忽略，即當期發(fā)貨當期可到。每一時段每個商品在貨棧中的存儲量有一個上限。供貨商貨源充足，且每一時段初給貨棧補一次貨，每次補貨都可達到貨棧的存儲上限。不考慮補貨的運輸成本。不考慮商品在貨棧中的存儲成本。四、變量及符號的說明j:表示第j個貨棧i：表示第i個零售商k：表示第k種商品：j貨棧給i零售商提供k商品的價格：對i零售商t時段的訂貨，j貨棧在t’時段的發(fā)貨量：j貨棧在t’時段運輸k商品到i零售商的運輸時間：i零售商t時段對商品k的需求量：j貨棧存儲量的上限：單位的k商品運輸時間產(chǎn)生的運輸成本。：懲罰函數(shù)，表示單位價格的商品提前或延誤時段對零售商的賠償。當＝0或＝0時，F(xiàn)＝0；當<0時，表示提前供貨；當>0時表示推遲供貨。五、模型的建立目標函數(shù)的建立根據(jù)題目要求，將模型的目標值考慮為兩部分：運輸成本和供貨提前/延期的懲罰費用。由假設(shè)條件（4），在一個周期內(nèi)，一個零售商對一種商品的需求只由一個貨棧滿足，不存在貨棧之間的相互調(diào)整，各個貨棧的供貨是獨立的，因此，在下面的最優(yōu)化討論中，我們只討論一個貨棧供貨的最優(yōu)化情況，整個供貨商的最優(yōu)化供貨可通過J個貨棧的線性疊加得到。為了不失一般性，我們考慮第j個貨棧供貨情況（j＝1，2，…，J）。、運輸成本前面已經(jīng)假設(shè)第k種商品的運輸成本與運輸時間、商品數(shù)量的關(guān)系，很容易寫出j貨棧在一個周期之內(nèi)所承擔(dān)的所有運輸成本：、提前/推遲供貨的懲罰費用由前面假設(shè)的提前/延遲供貨與懲罰費用的函數(shù)關(guān)系，且＝t’＋－t，代入懲罰函數(shù)，通過線性疊加易得j貨棧在一個周期內(nèi)的所有懲罰費用：因此，一個周期內(nèi)，j貨棧的供應(yīng)成本之和可表示為：約束條件：（1）、貨棧應(yīng)當滿足零售商在不同時段t的需求量，表達式如下：t＝1，2，…，T；i＝1，2，…，I；k＝1，2，…，K其中表示i貨棧t時段對k商品的需求量，為已知。（2）、根據(jù)實際情況，j貨棧所有商品的儲存量之和有上限，列出表達式為：j＝1，2，…，J其中為j貨棧的最大存儲量，為已知量。原始模型如下：s.t.i＝1，2，…，I;k＝1，2，…，K；t＝1，2，…，T;j＝1，2，…，Jt＝1，2，…，T;t’＝1，2，…，T;i＝1，2，…，I;j＝1，2，…，J;k＝1，2，…，K3.模型的初步分析及算法設(shè)計：在上述數(shù)量決策的的數(shù)學(xué)規(guī)劃模型中，已知條件為各個零售商的需求，各個貨棧的容量上限以及供貨價格。 在目標函數(shù)中我們假設(shè)某種商品的懲罰函數(shù)與延誤時間成正比，與延誤貨品的數(shù)量成正比，而其運輸費用與運輸時間成正比，與運輸?shù)呢浟砍烧?。由于實際發(fā)貨量與實際發(fā)貨采用的運輸時間均是待求解的未知量，從而它們的乘積將使目標函數(shù)的維數(shù)達到二維，該決策模型轉(zhuǎn)化為二次規(guī)劃問題。對二次規(guī)劃問題，傳統(tǒng)的算法有直接消去法、廣義消去法、有效集法等。這些算法雖然能算得問題的精確解，但其計算的復(fù)雜性隨著求解規(guī)模的增大而迅速增大，所以這些算法對于大規(guī)模問題都不具有實際可行性。Mcarthy和Liu[102]認為經(jīng)典的生產(chǎn)規(guī)劃理論及其最優(yōu)算法只具有學(xué)術(shù)價值，在實際應(yīng)用中運用很少。為使算法更加使用，我們建議采用以下幾種近似算法：規(guī)則方法：這是一種在生產(chǎn)計劃和調(diào)度問題研究中，運用最廣泛的啟發(fā)式方法。其優(yōu)點在于，計算時間較少，便與生產(chǎn)中的實時生產(chǎn)與調(diào)度。仿真方法：其主要是通過計算機模擬現(xiàn)實生產(chǎn)環(huán)境，對可能的生產(chǎn)計劃和調(diào)度方案進行計算機上虛擬實施，比較計算結(jié)果，尋求最優(yōu)方案[]。這種利用近似枚舉的方法在缺乏有效的理論支持的情況下是一種最直觀也最有效的方法。智能化方法：智能化生產(chǎn)計劃的方法主要有：遺傳算法（GA）、設(shè)禁搜索（TS）、模擬退火（SA）和人工智能網(wǎng)絡(luò)等智能化算法。這些智能算法的優(yōu)點是能跳出局部最優(yōu)，搜索全局最優(yōu)解，但解的準確性還有待考證。所列算法各有優(yōu)缺點，具體實施中我們可以根據(jù)問題的規(guī)模及限制條件的復(fù)雜程度選擇合適的算法。比如我們可以采用遺傳算法（CP-GA）與模糊邏輯（CP-HA）相結(jié)合的智能混合算法（CP-FL），由于過程過于繁雜，此處不做詳細說明，具體過程可參見文獻[116，124，125]。事實上，現(xiàn)實生活當中運輸函數(shù)和成本函數(shù)有一些特殊的性質(zhì)，這樣便可以大大簡化模型和算法。為此，下一部分，我們將根據(jù)實際情況以及生產(chǎn)實踐，對運輸函數(shù)和懲罰函數(shù)做進一步的假設(shè)，再根據(jù)這些假設(shè)，從易到難，從單貨棧單商品單零售商模型，到多貨棧多商品多零售商模型，一步一步接近實際情況，給出快速的算法，并對各種模型舉出具體算例，以驗證模型的合理性。六、模型的簡化：（一）假設(shè)：1、運輸函數(shù)：?？紤]商品k的運輸費用為運輸時間，商品數(shù)量的線性函數(shù)。假設(shè)為從j貨棧到i零售商的平均運輸時間，我們假設(shè)小于一個時段，即當期發(fā)貨當期即可到達。它與時段和商品種類無關(guān)，只與貨棧與零售商的距離有關(guān)，我們大膽地做假設(shè)，為了達到最低成本的目的，商家必定會選擇一種最優(yōu)的運輸方式以及相應(yīng)的最佳運輸時間。設(shè)為單位商品k從貨棧運輸?shù)搅闶凵痰膯挝粫r間的運費成本因子，則可以得到所有商品的運輸費用：在一個周期開始時，零售商的需求已知，因此已經(jīng)確定，所以一個周期內(nèi)內(nèi)的總運輸成本也是一個定值，不能通過供貨安排來改變，因此在下列簡化模型中，要實現(xiàn)供應(yīng)成本的最小化，只考慮懲罰的最小即可，2、懲罰函數(shù)：如果因為核算方式的不同而算出不同的延誤賠償額，供貨商與零售商必將產(chǎn)生爭議。為了避免在清算時發(fā)生爭議，我們大膽假設(shè)懲罰函數(shù)對與延誤時間應(yīng)該是線性形的，以下我們給出簡單的數(shù)學(xué)證明：考慮某貨棧只有一個零售商購買一種貨品的情況，假設(shè)貨棧上限不隨時間變化。設(shè)懲罰函數(shù)可簡單表示為F（x,Δt）,x為延誤貨量，Δt為延誤時間。設(shè)貨棧上限為C。現(xiàn)只考慮推遲的情況。設(shè)某期的定單為貨棧上限的兩倍，則當期只能發(fā)出定單一半的貨量，然后設(shè)之后連續(xù)N期的定單都為貨棧的上限，第N+1期無定單，則拖欠的貨物只能在第N+1期發(fā)出，可認為應(yīng)賠F（C，N）。但也可以認為是當期拖欠的貨物在第一期發(fā)出，而第一期的貨物在第二期發(fā)出，以次類推，直到第N期的貨物在第N+1期發(fā)出從而補完拖欠。在這種情況下，其賠償額為N*F（C，1）。如果F（C，N）≠N*F（C，1）則零售商會要求按照二者中賠償額高的那項索取賠償，而供貨商則會認為其調(diào)整方式是按二者中賠償額低的那項實施的，從而雙方產(chǎn)生爭議。為使不產(chǎn)生爭議，必須使F（C，N）=N*F（C，1）提前的情況可同樣證明。所以懲罰函數(shù)是延誤時間的線性函數(shù)，證畢。從現(xiàn)有的有關(guān)生產(chǎn)計劃與調(diào)度問題文獻[6]來看，產(chǎn)品的交貨期的描述方式有三種：精確交貨期、交貨期窗口和模糊交貨期。通常，提前與推遲的懲罰與訂單的價值成正比，且與提前、推遲時間成正比，設(shè)單位時間單位價值的提前與推遲供貨的懲罰因子為，一般來說,推遲供貨會引起信譽度的降低，因此假定，以使供貨商在供貨不足的情況下盡量采用提前供貨代替推遲供貨，則商品k的單位時間的提前與推遲供貨懲罰因子為，（k＝1，2，…，K）。設(shè)應(yīng)交貨時間為t，供貨時間為t’。精確交貨期：交貨時間為固定的時間點，如圖4-1所示.圖4-1精確交貨期地隸屬函數(shù)（用來描述客戶的滿意程度）可以表示為（式6.1）精確交貨期的提前/推遲供貨的懲罰函數(shù)可以描述為：（式6.2）交貨期窗口：交貨時間為一段時間，例如零售商要求在[，]這一區(qū)間內(nèi)交貨都可。為最早交貨期，為最晚交貨期。如圖6-2所示。圖6-2交貨期窗口的隸屬函數(shù)可以表示為：（式6.3）交貨期窗口的提前/推遲供貨的懲罰函數(shù)可以描述為：(式6.4)模糊交貨期：交貨時間為一段時間，并且反映了客戶對偏離這一時間的不同主觀滿意程度。如圖6-3所示，[，，，]，其中，分別是商品k的最早交貨期和最晚交貨期，，分別是客戶的最滿意交貨期的上限和下限，且滿足<<<. 圖6-3模糊交貨期的隸屬函數(shù)可以表示為：（式6.5）模糊交貨期的提前/推遲供貨懲罰函數(shù)為：（式6.6）在我們的模型當中，交貨的時間是離散的，因此精確交貨期和交貨期窗口的描述是等價的，為了簡化起見，我們不考慮客戶對誤期長短的主觀滿意程度，即要么滿意要么不滿意。我們采用函數(shù)關(guān)系式（6.2）,其中t，t’都表示時段，為離散的量。圖6-43、線性規(guī)劃因為貨品的單位都必須是整數(shù)，所以這道題應(yīng)該用整數(shù)規(guī)劃來求解。然而，考慮到每次的發(fā)貨量都是較大的整數(shù)，且別的約束條件也全部由整數(shù)組成，所以用線性規(guī)劃求解時得到非整數(shù)的概率并不大，即便出現(xiàn)非整數(shù)，四舍五入后得到的最優(yōu)值也與實際整數(shù)規(guī)劃的最優(yōu)解相差不多，所以我們將整數(shù)規(guī)劃簡化為線性規(guī)劃求解。（二）、簡化模型1．單貨棧單商品單零售商模型（簡化模型1）只考慮一個貨棧給一個零售商提供一種商品，由上述假設(shè),可列出簡化模型1：s.t.(t=1,2,…T)(t’=1,2,..T)變量說明：：對零售商t時段的訂單，該貨棧在t’時段的發(fā)貨量。：該商品的價格：零售商t時段對商品的需求量。：該商品的體積因子。：貨棧的最大儲存容量實例應(yīng)用：例1：假設(shè)一個周期分為5個時段，=0.2，=0.6，=1，=7，設(shè)有如下訂單：DiD1D2D3D4D5Di43986表6代入上述模型，由Lingo解得最優(yōu)解，各時段送貨量如X（i，j）X(1,1)X(2,2)X(3,3)X(3,2)X(4,4)X(4,2)X(5)X（i，j）4372716表6.1.2其具體運行程序見附錄[1]：結(jié)果分析：根據(jù)實驗結(jié)果，在該種情況下，供貨商實行的策略應(yīng)該是盡量先滿足當期的供貨，當某期供貨不足時，在附近時段搜索貨棧有無余量，并選擇其中賠償額最小的時段發(fā)貨。如此循環(huán)直至補足欠貨。符合實際情況。單貨棧單商品多零售商模型（簡化模型2）假設(shè)有單貨棧給I個零售商供單種商品，同簡化模型1，運輸成本不可調(diào)，由懲罰的最小化建立單貨棧單商品多零售商的最優(yōu)化模型：s.t.t＝1，2，…，T;i＝1，2，…，I;t＝1，2，…，T;t’＝1，2，…，T;i＝1，2，…，I;變量說明：：對i零售商t時段的訂單，該貨棧在t’時段的發(fā)貨量。：第i個零售商的進價：i零售商t時段對該商品的需求量：貨棧的最大存儲容量實例應(yīng)用：例2：假設(shè)一個周期分為5個時段，有3個零售商，=0.2，=0.6，＝1.5,=1,=2，V＝21，假設(shè)有如下訂單：D1D2D3D4D585136837958211248表6.2.1代入上述模型，用lingo解得最優(yōu)解，如表6.2.2。。X1(1,1)X1(2,2)X1(3,3)X1(4,4)X1(5,5)X2(1,1)8513683X2(2,1)X2(2,2)X2(3,1)X2(3,3)X2(4,4)X2(5,4)253653X2(5,5)X3(1,1)X3(2,2)X3(3,3)X3(4,4)X3(5,5)3211248表6.2.2具體運行程序見附錄[2]：結(jié)果分析：該模型除了保留簡化模型1的特征之外，還對客戶產(chǎn)生了不同的分級，購買價高的客戶，級別也越高，如上例中，第5時段3個客戶同時要8單位貨物，但客戶2的價格最低，（從而級別最低），被提前發(fā)了3單位貨。這與實際情況相符。單貨棧多商品多零售商模型（簡化模型3）假設(shè)該貨棧提供K種商品，其余假設(shè)和條件同簡化模型2，由于是單貨棧供貨，所以由假設(shè)，還是沒有運輸成本的變化，因此也只要考慮懲罰費用的最小化，由此建立單貨棧多商品多零售商的最優(yōu)化供貨模型，即簡化模型3。s.t.t＝1，2，…，T;i＝1，2，…，I;k＝1，2，…，K變量說明：：對i零售商t時段對k商品的訂單，該貨棧在t’時段的發(fā)貨量：該貨棧給i零售商提供k商品時的價格，已知：i零售商t時段對k商品的需求量，已知：k商品的體積因子，已知例3：：假設(shè)一個周期分為5個時段，該貨棧有4種商品，給3個零售商供貨，=0.2，=0.6，V＝21，價格如表6.3.1,＝訂單如表6.3.2，6.3.3，6.3.4：CikCi1Ci2Ci3Ci4C1k1882540C2k24103050C3k20123545表6.3.1Dik(t)D1k(1)D1k(2)D1k(3)D1k(4)D1k(5)D11(t)00000D12(t)1520253020D13(t)00000D14(t)65438表6.3.2Dik(t)D2k(1)D2k(2)D2k(3)D2k(4)D2k(5)D21(t)1012141210D22(t)2535404520D23(t)5060304020D24(t)57684表6.3.3Dik(t)D3k(1)D3k(2)D3k(3)D3k(4)D3k(5)D31(t)1412101010D32(t)3540502535D33(t)00000D34(t)65432表6.3.4代入上述模型，由Lingo解得最優(yōu)解，各時段送貨量如表6.3.5X12(1,1)X12(2,1)X12(2,2)X12(3,3)X12(4,4)X12(5,5)X14(1,1)X14(2,2)1581225302565X14(3,3)X14(4,4)X14(5,5)X21(1,1)X21(2,2)X21(3,3)X21(4,4)X21(5,5)4381012141210X22(1,1)X22(2,2)X22(3,3)X22(4,4)X22(5,5)X23(1,1)X23(2,2)X23(3,3)2535404520506030X23(4,4)X23(5,5)X24(1,1)X24(2,2)X24(3,3)X24(4,4)X24(5,5)X31(1,1)40205768414X31(2,2)X31(3,3)X31(4,4)X31(5,5)X32(1,1)X32(2,2)X32(3,3)X32(4,4)1210101035405025X32(5,5)X34(1,1)X34(2,2)X34(3,3)X34(4,4)X34(5,5)3565432表6.3.5其具體程序見附錄[3]：結(jié)果分析：在簡化模型2的基礎(chǔ)上，還對不同的產(chǎn)品產(chǎn)生了不同的分級，總體來看，價格越高，供貨的優(yōu)先級越高，其發(fā)貨期越要求接近訂貨期。符合實際情況。多貨棧多商品多零售商模型（簡化模型4）根據(jù)本文開始的問題分析，該模型退化為J個獨立的簡化模型3的線性組合。由此列出簡化模型4：s.t.t＝1，2，…，T;;i＝1，2，…，I;k＝1，2，…，Kj＝1，2，…，J;變量說明：：j貨棧給i零售商提供第k種商品的價格：對i零售商第t時段對第k種商品的訂單，j零售商在第t’時段的供貨：i零售商t時段對k商品的需求：j貨棧的存儲上限這就是原始模型的線性化模型，也是我們的最終模型。實例應(yīng)用：例4：設(shè)有2個貨棧，一個周期分為5個時段，貨棧有5種商品，給4個零售商供貨，=0.2，=0.6，V＝700500，價格如表6.4.1,訂單如表6.4.2，6.4.3，6.4.4,s6.4.5：CijkCij1Cij2Cij3Cij4Cij5C11k305501025C12k354501230C13k303401410C14k256451625C21k253401630C22k405601425C23k208451220C24k207501030表6.4.1,D1k(t)D1k(1)D1k(2)D1k(3)D1k(4)D1k(5)D11(t)2025304510D12(t)303560045D13(t)00808080D14(t)3510104525D15(t)1030302510表6.4.2D1k(t)D2k(1)D2k(2)D2k(3)D2k(4)D2k(5)D21(t)304510050D22(t)4075505085D23(t)403020300D24(t)252503510D25(t)401020530表6.4.3D1k(t)D3k(1)D3k(2)D3k(3)D3k(4)D3k(5)D31(t)1020304020D32(t)2040608020D33(t)510152025D34(t)81624328D35(t)1020304010表6.4.4D1k(t)D4k(1)D4k(2)D4k(3)D4k(4)D4k(5)D41(t)251035205D42(t)8060107040D43(t)00000D44(t)00404040D45(t)402010540表6.4.得到結(jié)果如下表：程序見附錄[4]X114(1,1)X114(2,2)X114(3,3)X114(4,4)X114(5,5)X115(1,1)X115(2,2)X115(3,3)3510104525103030X115(4,4)X115(5,5)X121(1,1)X121(2,2)X121(3,3)X121(5,5)X121(1,1)X122(2,2)2510304510504075X122(3,3)X122(4,4)X122(5,5)X123(1,1)X123(2,2)X123(3,3)X123(4,4)X124(1,1)5050854030203025X124(2,2)X124(4,4)X124(5,5)X132(1,1)X132(2,1)X132(2,2)X132(2,3)X132(3,3)25351020828560X132(4,3)X132(4,4)X132(5,5)X133(1,1)X133(2,2)X133(3,3)X133(4,4)X133(5,5)75520510152025X135(1,1)X135(2,2)X135(3,3)X135(4,4)X135(5,5)X142(1,1)X142(2,2)X142(3,3)1020304010806010X142(4,4)X142(5,5)X145(1,1)X145(2,2)X145(3,3)X145(4,4)X145(5,5)X211(1,1)704040201054020X211(2,2)X211(3,3)X211(4,4)X211(5,5)X212(1,1)X212(2,2)X212(3,2)X212(5,2)253045103035605X212(5,5)X213(3,3)X213(4,4)X213(5,5)X225(1,1)X225(2,2)X225(3,3)X225(4,4)408080804010205X225(5,5)X231(1,1)X231(2,2)X231(3,3)X231(4,4)X231(5,5)X234(1,1)X234(2,2)301020304010816X234(3,3)X234(4,4)X234(5,5)X241(1,1)X241(2,2)X241(3,3)X241(4,4)X241(5,5)24328251035205X44(3,2)X244(3,3)X244(4,4)X244(5,5)2384040表6.4.6;5、.算法的優(yōu)化 顯而易見以上線性規(guī)劃含I*J*K*T*T個變量。但考慮到每個零售商對某一具體商品都將選擇唯一的貨棧為其供貨，則他在其他貨棧對該商品的需求為零，進而可推知其他貨棧對該零售商需要的這種商品的各期供應(yīng)都為零?，F(xiàn)將按ijktt’遞增的順序排成一行矩陣，則此為一占空比達的稀疏矩陣。實際上，我們已知道其中有的變量為零，且可由人工目測的方式一一進行辨認，但不便于計算機求解。因此我們計劃采用降維的辦法將J下標消去，將變量數(shù)縮小為原來的。定義二元關(guān)系（i,k）表示i貨商購買k商品所選擇的貨棧號，則（i,k）=j,若i商對k貨無需求，則令（i,k）=0.從而我們寫出一m*l矩陣，里面的第i行第k列元素表示i商對k貨所選定的貨棧號，從而將i,k與j對應(yīng)，達到降維的目的，并且使變量和需求約束項數(shù)目都減為，大大簡化運算。在lingo上的具體實現(xiàn)，我們?yōu)榱寺缘羯鲜龅淖兞?，增加了一部對矩陣的過濾，為此要先引入一個新的need(i,j,k)矩陣，當i商從j貨棧購買k商品時，need（i，j，k）=1，否則為0?？芍猲eed（i，j，k）可由C（i，j，k）生成，再由need（i，j，k）來過濾X（i，j，k，t，t’）。具體編程請見附錄[5]。6、算法的比較，我們將兩種算法在lingo上進行了比較，數(shù)據(jù)選的是10*10*10*10*10的，數(shù)據(jù)及程序見附錄[6]。兩個程序都給出了相同最優(yōu)解，現(xiàn)將結(jié)果比較如下：變量數(shù)最優(yōu)值消耗內(nèi)存值用時（s）常規(guī)線性規(guī)劃1010001157.614104K0.08優(yōu)化算法100001157.61773K0.01可見，第二種顯著提高了速度。7、進一步改進設(shè)想?？紤]到第1次為第t次提前供貨不是很現(xiàn)實，我們可以簡單的認為一切提前和推遲供應(yīng)都應(yīng)在當時段的前兩個時段和后兩個時段之內(nèi)解決，如果這樣，又將減少一半以上變量，提高運算速度，但同時，也可能會增加不可解的情況。七、模型的評價及改進模型的評價：本文研究了供貨商的多商品配送問題，充分考慮實際情況，不失一般性，討論了多貨棧給多零售商提供多商品的情況，建立了考慮貨棧存儲容量約束的供貨商多商品配送的精確交貨期的提前/推遲供貨線性化模型CP4。該模型中有JKITT個變量，JT個約束項，是一個典型的一次線性化模型，利用lingo軟件很容易求解。通過上述實例，從模型優(yōu)化計算結(jié)果可以看出：各商品供應(yīng)在滿足存儲容量上限的前提下，各貨棧的存儲商品都得到了充分的利用，并且合理安排了供貨時間以及供貨渠道，使得懲罰和運輸成本之和達到最小值。由表格也可以看出各商品的供貨期都盡可能地靠近要求地供貨時段。上述例子的計算結(jié)果充分表明了該模型的有效性。但是上述例子當中的J，K，I，T都比較小，計算起來非?？臁５斶@些量稍微大時，例如K,I,J,T>10時，變量超過100000，計算量非常龐大，但考慮到這些變量當中大部分都是0，為此，我們設(shè)計了快速算法，由程序?qū)崿F(xiàn)。模型的改進：根據(jù)題意，每個零售商都根據(jù)價格最優(yōu)的原則選定發(fā)貨貨棧。實際上我們可以認為，零售商選定的只是最低的那個價格而不是貨棧。如果在具體配送的過程中，供貨商愿意在商品出售價格保持不變的基礎(chǔ)上選擇從其他貨棧發(fā)貨，供應(yīng)商自己補足差價，則收貨的零售商應(yīng)該沒有異議，因以為這么做對零售商的利益絲毫沒有影響，在懲罰因子較大的情況下甚至可以避免不必要的延誤。此時我們將各個貨棧對某零售商提供某種商品所提供的價格減去其中的最低價格，從而產(chǎn)生差價，將這些差價加到相應(yīng)的運費中去，產(chǎn)生虛擬運費（不低于原運費）或是折合成虛擬的運輸時間（不少于原運輸時間），在這種模型下各個貨棧對某個零售商提供某種商品的價格均是最低價格，零售商對供貨商指定的任何貨棧均無異議。此時，在定單不超過當期貨棧上限的情況下（即不需推遲或提前），供貨商只要選擇虛擬運費最低的那個貨棧發(fā)貨即可實現(xiàn)成本最低?；谶@種假設(shè)下建立的深化模型如下：s.t.t＝1，2，…，T;;i＝1，2，…，I;k＝1，2，…，Kj＝1，2，…，J;其中是虛擬運輸時間采用這種可根據(jù)具體定單情況以及客戶對象選派貨棧供貨的配送方式，比起自始至終由指派的貨棧對確定的客戶供貨的配送方式，要更加靈活，也更節(jié)省成本。八、參考文獻[1].張曙，分布式網(wǎng)絡(luò)化的全球制造，中國機械工程，1998[2].McCarthyBLandLiuJ,Addressingthegapinschedulingresearch:areviewofoptimizationandheuristicmethodsinproductionschedualing.InternationalJouralProductionResearch1994,32(4),903-915.[3].D,Wang,S-C.FangandH.L.Nuttle,Fussyrulequantificationanditsapplicationinfussydue-datebargaining,ProceedingofIFSACongress1999[4].Wang,Dingwei,Fang,S.C.andT.J.Hodgson,Afussydue-datebargainerformake-to-ordermanufacturingsystems,IEEETrans.onSMCPart-C,1999,29,566-575.[5].Wang,Dingwei,Fang,S.C.andH.L.W.Nuttle,Softcomputingformulticustumerdue-datebargaining,IEEETrans.OnSMCPart-C,1999,29,566-575[6]汪定偉，敏捷制造的ERP及其決策優(yōu)化，機械工業(yè)出版社，2003，106-107[7].馬建平，現(xiàn)代物流配送管理，中山大學(xué)出版社，2001.九．附錄，部分程序的源碼（略）目錄TOC\o"1-2"\h\z\u第一章總論 1一、項目概況 1二、項目提出的理由與過程 6三、項目建設(shè)的必要性 8四、項目的可行性 12第二章市場預(yù)測 15一、市場分析 15二、市場預(yù)測 16三、產(chǎn)品市場競爭力分析 19第三章建設(shè)規(guī)模與產(chǎn)品方案 22一、建設(shè)規(guī)模 22二、產(chǎn)品方案 22三、質(zhì)量標準 22第四章項目建設(shè)地點 25一、項目建設(shè)地點選擇 25二、項目建設(shè)地條件 25第五章技術(shù)方案、設(shè)備方案和工程方案 28一、技術(shù)方案 28二、產(chǎn)品特點 30三、主要設(shè)備方案 32四、工程方案 32第六章原材料與原料供應(yīng) 35一、原料來源及運輸方式 35二、燃料供應(yīng)與運輸方式 35第七章總圖布置、運輸、總體布局與公用輔助工程 37一、總圖布置 37二、運輸 38三、總體布局 38四、公用輔助工程 39第八章節(jié)能、節(jié)水與安全措施 44一、主要依據(jù)及標準 44二、節(jié)能 44三、節(jié)水 45四、消防與安全 45第九章環(huán)境影響與評價 47一、法規(guī)依據(jù) 47二、項目建設(shè)對環(huán)境影響 48三、環(huán)境保護措施 48四、環(huán)境影響評價