運籌學(xué)專題報告書

1、運籌學(xué)專題報告2Lingo語言求解東方服裝集團(tuán)童裝配送系統(tǒng)設(shè)計問題user2011/5/22目錄 TOC o 1-5 h z HYPERLINK l bookmark11 o Current Document 引言3 HYPERLINK l bookmark14 o Current Document 1、案例介紹3 HYPERLINK l bookmark18 o Current Document 1.1基本介紹3 HYPERLINK l bookmark21 o Current Document 1.2初步分析.4 HYPERLINK l bookmark24 o Current Docum

2、ent 2、建模思想5 HYPERLINK l bookmark28 o Current Document 2.1 0-1混合整數(shù)規(guī)劃法5 HYPERLINK l bookmark31 o Current Document 2.2模型描述5 HYPERLINK l bookmark34 o Current Document 2.3假設(shè)條件6 HYPERLINK l bookmark42 o Current Document 2.4費用構(gòu)成和變量規(guī)范62.5模型描述.7 HYPERLINK l bookmark55 o Current Document 3、案例求解8 HYPERLINK l b

3、ookmark59 o Current Document 3.1編寫lingo程序8 HYPERLINK l bookmark95 o Current Document 3.2運行求解10 HYPERLINK l bookmark98 o Current Document 4、討論：11 HYPERLINK l bookmark102 o Current Document 4.1非零庫存政策11 HYPERLINK l bookmark105 o Current Document 4.2各配送中心有年吞吐量上限11 HYPERLINK l bookmark137 o Current Docum

4、ent 4.3外部采購情況14 HYPERLINK l bookmark140 o Current Document 5、結(jié)束語15 HYPERLINK l bookmark144 o Current Document 6、參考文獻(xiàn)157、附錄16引言一般研究物流配送中心選址的方法較多，大致可以分為定性和定量兩類方法。定性方法 主要是結(jié)合AHP （層次分析法）和模糊綜合評價法對各方案進(jìn)行指標(biāo)評價，找出最優(yōu)選址。定 量方法主要有重心法、運輸規(guī)劃法、Cluster法與CFLP法、Baumol-Wolfe法、遺傳算法和 0- 1混合整數(shù)規(guī)劃法等。Lingo是美國LINDO系統(tǒng)公司開發(fā)的一套專門用于求

5、解最優(yōu)化問 題的軟包。主要用于求解線性規(guī)劃問題、二次規(guī)劃問題、非線性問題和一些線性和非線性方 程的求解。Lingo優(yōu)化軟件的最大特色在于可以允許優(yōu)化模型中決策變量為整數(shù)（支持整數(shù) 規(guī)劃），而且快捷、準(zhǔn)確。同時Lingo還是最優(yōu)化問題的一種建模語言，其程序使用自己的 專用語言編寫，普通人難以看懂，為此Lingo又提供其他文件（如文本文檔、Excel電子表 格、數(shù)據(jù)庫文件等）的接口，易于方便地輸入、求解和分析大規(guī)模的優(yōu)化問題。因此Lingo在 數(shù)學(xué)、科研和工業(yè)界得到廣泛應(yīng)用。以下案例將全部基于ling o語言的運算解釋。1、案例介紹1.1基本介紹東方服裝集團(tuán)考慮生產(chǎn)一種童衣系列。童衣產(chǎn)品將先運至配

6、送中心，再由配送中心將產(chǎn) 品運至分銷店。該集團(tuán)有5家工廠可生產(chǎn)這類童衣，有3家配送中心可以分配童衣產(chǎn)品，有4家分銷店可以經(jīng)營童衣產(chǎn)品。這些工廠和配送中心的下一年度的年固定成本如下表1。表1工廠與配送中心的固定成本單位工廠1工廠2工廠3工廠4工廠5配送中心1配送中心2配送中心3年固定成本（元）3 500045 00040 00042 00040 00040 00020 00060 000下一年度工廠的生產(chǎn)能力、工廠到被選的配送中心的單位運價如表2所示。表2各工廠至配送中心的運輸成本與生產(chǎn)能力終點f f、八、起點運輸成本（元/箱）生產(chǎn)能力（箱）配送中心1配送中心2配送中心3工廠18001 0001

7、 200300工廠2700500700200工廠3800600500300工廠4500600700200工廠5700600500400從配送中心運至分銷店的運輸成本和各分銷店的需求量如表3所示。終點ff、八、起點、運輸成本（兀/箱）分銷店1分銷店2分銷店3分銷店4配送中心140809050配送中心270406080配送中心380305060需求量（箱）200300150250假定各配送中心的庫存政策為零庫存，即配送中心從工廠得到的產(chǎn)品均分配給分銷店， 不留作庫存。集團(tuán)要設(shè)計一種童衣分配系統(tǒng)，在滿足需求的前提下，確定使用哪些工廠與配 送中心進(jìn)行童衣的生產(chǎn)與配送，以使得總成本最小。1.2初步分析通

8、過初步分析，我們可以認(rèn)定此例題的性質(zhì)，即一般意義上的物流選址模型。主要分析物流 系統(tǒng)中庫存管理、運輸、配送中心之間的聯(lián)系，應(yīng)用最優(yōu)化方法建立了物流配送中心選址 的數(shù)學(xué)模型。該模型是一個混合整數(shù)規(guī)劃。物流系統(tǒng)中配送是重要一環(huán)，因此搞好配送中心 選址對提高整個物流系統(tǒng)的效益具有重要意義，配置配送中心應(yīng)考慮下述必要性：首控制物流成本。再按照集約庫存來維持合理的庫存量，為了防止庫存過剩和庫存偏頗， 把過去分散在數(shù)家的自家倉庫，集約到配送中心進(jìn)行管理，提高服務(wù)水平，擴大銷售。把配送中心配置在兼顧消費地和生產(chǎn)地處，既可以及早掌握發(fā)生的銷售信息，把顧客的 實際需要和需要動向迅速地反映到生產(chǎn)計劃部門和采購計劃

9、部門;也可以迅速將產(chǎn)地貨物輸 送各地。具體選址還要視貨物情況而定。商物分離。把進(jìn)行商品交易的場所和進(jìn)行物流活動的場所分離，明確商品交易功能和物 流功能，以配送中心為中心來提高物流的效益化。防止交錯運輸。分散在全國各地的工廠生產(chǎn)著不同品種的商品，從各個工廠到消費地難 免發(fā)生交錯運輸，使成本提高，因此，在適當(dāng)?shù)膱鏊渲门渌椭行?，把從各個工廠集約起來 的商品有計劃地運輸?shù)较M地。2、建模思想2.10-1混合整數(shù)規(guī)劃法01混合整數(shù)規(guī)劃法的主要優(yōu)點是它能夠把固定成本以最優(yōu)的方式考慮進(jìn)去，它是商 業(yè)選址模型中最受歡迎的方法。用0- 1混合整數(shù)規(guī)劃來解決選址模型時，目標(biāo)是使各種成 本費用的總和最小，而用整數(shù)

10、變量表示各種選擇，用連續(xù)變量表示工廠的生產(chǎn)能力、各種資 源的分配等，用約束表示物流平衡關(guān)系和供需關(guān)系等。其主要思想是將每一個備選配送中心 （RDC）分別納入目標(biāo)函數(shù)中看各自對目標(biāo)函數(shù)的影響程度，最后決定是否需要該RDC。2.2模型描述假設(shè)有J個（備選）配送中心可從I個工廠中進(jìn)貨，同時又必須給K個客戶提供配送服 務(wù)，于是商品的供需關(guān)系和流動況將形成了一個完整的物流配送網(wǎng)絡(luò)結(jié)構(gòu)。工廠和客戶的數(shù) 量和位置是固定的，從J個備選RDC中選出j個RDC，并求出工廠和配送中心、配送中心 與客戶的供需關(guān)系，使總費用最小。如圖1所示。1模型示意E工廠舊1模型示意E工廠舊客戶郵）V被透RDC(W)2.3假設(shè)條件企

11、業(yè)物流配送中心選址問題是在給定某一地區(qū)所有備選點的地址集合中選出一定數(shù)目 的地址建立配送中心，從而建立一系列的配送區(qū)域，以實現(xiàn)選出點建立的配送中心與各需求 點和工廠(供貨點)形成的配送系統(tǒng)總物流費用最小。為了便于建立數(shù)學(xué)模型，作如下假設(shè)：由工廠到配送中心、由配送中心到客戶的單位運輸價格和運距均已知。各工廠的總生產(chǎn)能力已知；配送中心的容量及個數(shù)有限制；各客戶的需求量己知；配送中心的固定費用、單位管理費用為已知常數(shù)。2.4費用構(gòu)成和變量規(guī)范由于配送中心選址中包括多種費用，所涉及的變量不下十個，在配送中心選址模型中說 法太多，且很亂，于是下面將對各種費用和所涉及到得變量做以科學(xué)的規(guī)范：費用界定將與配

12、送中心選址有關(guān)的物流環(huán)節(jié)細(xì)分為進(jìn)貨運輸、存貨倉、送貨配送三個環(huán)節(jié)，于是 費用也就考慮以下三種：從工廠到配送中心的進(jìn)貨運輸費用，簡稱運輸費用(Transportation costs)、從配送中心到客戶的送貨配送費用，簡稱配送費用(Distributioncosts)和貨物流經(jīng) 配送中心時的倉儲費用，其中倉儲費用又包括新建配送中心的固定投資費用(Warehouse fixed costs)和保管暫存貨物可變倉儲費用(Variable warehousing costs)。即總費用主要包 括運輸費用、倉儲費用、配送費用三部分。規(guī)范變量T：運輸費用；D：配送費用；W：倉儲費用；Pij：備選區(qū)域配送中

13、心Wj向工廠Fi的單位 進(jìn)貨費用；Xij:備選區(qū)域配送中心Wj向工廠Fi進(jìn)貨數(shù)量；Mij:備選區(qū)域配送中心Wj到 工廠玨的運距；Qij：備選區(qū)域配送中心Wj到客戶區(qū)Rk單位配送費用；Yij：備選區(qū)域配 送中心Wj到客戶區(qū)Rk送貨數(shù)量；Nj k：備選區(qū)域送中心Wj到客戶區(qū)Rk的運距；Hj:備選 區(qū)域配送中心Wj單位庫存成本；Sj：新建配送中心Wj需要投資的固定費用；Zj： 0-1變量， 1表示開設(shè)配送中心Wj；人1：是工廠Fi的供應(yīng)總量；Bj：配送中心Wj的倉儲容量；Ck： 是客戶區(qū)Rk的需求量。通過以上對配送中心選址問題的研究，我們結(jié)合0-1整 數(shù)規(guī)劃建立如下的模型。目標(biāo)函數(shù)：總費用運輸費用仃

14、=罵心沖衫4配送費用w B=Q”偵M VZj;倉儲費用：卬=WER=HjX*+S由，即】總費用=卒/*+H占 4 淄4+Q* Y職 V*由上式可得目標(biāo)函數(shù)如下：I IJ K岫二 XX Xi = J i = JJ = J k = J+ 砰奪移i = /j = J約束條件；各工廠（Q調(diào)出的物資總量不應(yīng)大于其生產(chǎn)、供應(yīng)能力 CVo *聲枷 H3X = 1各配送中心（B9,其進(jìn)貨量不應(yīng)大于器倉儲能力凸玄*及 廣1,2,3 i = 1各經(jīng)銷商（AQ調(diào)運進(jìn)來的物資總量不應(yīng)小于其需求總量勇匕QG123i = 1對于每-區(qū)域配送中心（叫）由于其既不能成產(chǎn)也不能消 耗物資，因此每個區(qū)域配送中心調(diào)出的物資總量等于

15、調(diào)入的物 資總量：I X尸邕.1 - i - f3、案例求解假定各配送中心的庫存政策為零庫存，即配送中心從工廠得到的產(chǎn)品均分配給分銷店，不留 作庫存。集團(tuán)要設(shè)計一種童衣分配系統(tǒng)，在滿足需求的前提下，確定使用哪些工廠與配送中 心進(jìn)行童衣的生產(chǎn)與配送，以使得總成本最小。參考物流選址模型，本題也是物流選址模型的一個實例。由于本題沒有單位物資的可變倉儲 費用，即不考慮物資在配送中心內(nèi)部所發(fā)生的費用。3.1編寫lingo程序MODEL:!設(shè)置變量；sets:!工廠3, b，u分別表示產(chǎn)量，固定費用，01變量；factory/1.5/:a，b，u;!配送中心臼v分別表示固定費用，0-1變量；warhous

16、e/1.3/:f，v;customer/1.4/:c;而工廠到配送中心的價格數(shù)據(jù)，乂各工廠到配送中心的運量；link1(factory，warhouse):m，x;!n配送中心到客戶的價格數(shù)據(jù)，y各配送中心到客戶的運量；link2(warhouse，customer):n，y;endsets!數(shù)據(jù)區(qū)；data:a=300 200 300 200 400;b=35000 45000 40000 42000 40000;c=200 300 150 250;f=40000 20000 60000;m=800 1000 1200 700 500 700 800 600 500 500 600700 7

17、00 600 500;n=40 80 90 50 70 40 60 80 80 30 50 60;enddata!目標(biāo)函數(shù)；min=sum (warhouse (j):sum (factory (i):m (i, j)*x (i, j)*v (j)+sum (customer (k):sum (warhouse (j):n (j, k)*y (j, k)*v (j)+sum(warhouse(j):f(j)*v(j)+sum (factory(j):b(j)*u(j);!約束條件，工廠輸出小于產(chǎn)能；for(factory(i):sum(warhouse(j):x(i, j)=c(k);for(

18、warhouse:bin(v);for(factory:bin(u);for(warhouse(j):sum(factory(i):x(i, j)=99999999*v(j);for(factory(i):sum(warhouse(j):x(i, j)=99999999*u(i);3.2運行求解根據(jù)Lingo的解答得到下表:各工廠至配送中心的運輸量與產(chǎn)量、終點、八、運七F俞成本（兀/箱）起點、配送中心1配送中心2配送中心3生產(chǎn)能力（箱）工廠1工廠2工廠3工廠4工廠5200300400表：配送中心至分銷店運量終點%、八、起點、運輸量（箱）分銷店1分銷店2分銷店3分銷店4配送中心1配送中心2 配送

19、中心3200300150250需求量（箱）200300150250從上表中可以看出，在最滿足要求的情況下最小成本為700500元。其中使用工廠2、3、5, 配送中心2、3,具體產(chǎn)量和配送額如上圖。4、討論：4.1非零庫存政策如各配送中心的庫存不實行零庫存政策，即配送中心有一定的期初、期末庫存。首先考慮期末庫存的情況：在本例中，工廠可以提供的最大產(chǎn)能遠(yuǎn)大于顧客需求。如果配送中心追求最小成本，其 必須支持零庫存，顯而易見，當(dāng)工廠產(chǎn)能大于需求時，多余部分即可儲存在配送中心，但在 目標(biāo)函數(shù)的限制下，計算機算法是減少工廠的產(chǎn)量來達(dá)到零庫存。舉例來說，假如工廠2的 產(chǎn)能為250箱，通過此l ing o程序

20、求解最終工廠2只是生產(chǎn)了200箱物資，如果富余產(chǎn)能50生產(chǎn) 的話會相對原來增加工廠2到配送中心2的運費。因為費用的限制，此例中供給是滿足需求的。假設(shè)限定一項條件為：開工工廠必須按照最大產(chǎn)能生產(chǎn)，則結(jié)果就會相應(yīng)變化。同樣以 工廠2為例，假如工廠2的產(chǎn)能為250箱，其必須生產(chǎn)250箱以滿足最大設(shè)備利用率，則供給減 去需求剩余的50箱物資就會儲存在配送中心2,費用也相應(yīng)的增加?，F(xiàn)在考慮期初庫存的情況：如果配送中心中本來就有期初庫存，則相應(yīng)的工廠就會減少產(chǎn)量以減少成本。同樣的有 一種情況，即追求設(shè)備利用率最大，開工工廠必須按照最大產(chǎn)能生產(chǎn)，此時會怎樣？簡單闡 述為，在配送中心的庫存尚不能一次滿足配送點

21、需求時，相應(yīng)工廠會不斷增加配送中心的庫 存。當(dāng)下一期配送中心的庫存可以滿足配送需要，則本期工廠暫停使用，需求由庫存解決。 同樣以工廠2為例，假如工廠2的產(chǎn)能為250箱，其必須生產(chǎn)250箱以滿足最大設(shè)備利用率，每 期在配送中心2中積累50箱物資。第四期末積累200箱，則第五期工廠2暫停使用，將庫存200 配送。4.2各配送中心有年吞吐量上限1、現(xiàn)在配送中心最大的實際吞吐700箱，即如果限額大于700箱，最優(yōu)結(jié)果不變化。2、如果最大吞吐量小于700箱，利用原代碼修改，對配送中心吞吐量進(jìn)行限制。比如最大吞吐量為 650 箱，在代碼中加入for(warhouse(j):sum(link1(i，j):x

22、(i，j)650);進(jìn)行限制，得到結(jié)果圖為Lingo 12.0 Solver Status 演箸學(xué)ySolver btatGsModel Cla-MINLPStat己Local I3ptObisctive:7 0 6 0 0 0Infeasibility 2 . 3885Ge-010Iterations2 6 4 4variaulesTotal:35Nonlinear:30Integers:8Total:癥 4Nonlinear:1I al II lrril I IATotal:1 彼Nonlinear:&0Solver Tvpe：B-and-BBest Obj:0G000 bj Bound7

23、060005teps:4 0Active:0Generator M emory U aed K31-Elapsed Runtime (hh;mnn;)00:00:01Update Interval: 2口。范即最優(yōu)解變?yōu)?06000元，比原來增加了 5500元。此時各工廠各配送中心量如下表:各工廠至配送中心的運輸量與產(chǎn)量終點、八、起點運輸成本（元/箱）生產(chǎn)能力（箱）配送中心1配送中心2配送中心3工廠1工廠2工廠3工廠4工廠520050250400表：配送中心至分銷店運量、終點起點運輸量（箱）分銷店1分銷店2分銷店3分銷店4配送中心1配送中心2配送中心320030050100250需求量（箱）2

24、00300150250對比發(fā)現(xiàn)，工廠3原來向配送中心3輸送的300箱物資中50箱轉(zhuǎn)移至配送中心2.最多轉(zhuǎn)移多少可達(dá)到極限？通過計算吞吐量450是配送中心1啟用的臨界條件。加入for(warhouse(j):sum(link1(i，j):x(i，j)450);結(jié)果為Lingo 12.0 Solver Status 旗碧學(xué)ySolver StatusModel Class:MINLPState:local OptObjective:72 80 00Inreasibility:2 ,42267e-010Iterations:14 51VariablesTotal:3 5Nonlinear:3 01

25、ntegers:8JUI IMI 口II 113Total:24Nonlinear1Total:142Nonlinear:3 0Solver T卯日：B-and-BBesl0b|：72 80 00Obj Bound:72 80 00Generator M&nory UsedKJ31p Elapsed Runtime (hh:mnn:s3)心妃000:00:01Update Interval; 2Jnt日ri叩t 5口由 | U甌關(guān)于配送中心01變量取值為U( 1)0.0000000.000000U( 2)1.00000045000.00U( 3)1.00000040000.00將代碼改為for

26、(warhouse(j): sum(link1(i，j):x(i，j)449);結(jié)果為最優(yōu)解變化很大，V( 1)1.000000148000.0V( 2)1.000000173640.0V( 3)1.000000305470.0三個配送中心全部啟用。4.3外部采購情況本題目考慮的是一家集團(tuán)企業(yè)內(nèi)部的問題，如果是企業(yè)向外部采購呢？隨著市場經(jīng)濟(jì)的發(fā)展和完善，采購已由單純的商業(yè)買賣發(fā)展成為一種職能、一門專業(yè)。 現(xiàn)代企業(yè)經(jīng)營管理中，采購越來越重要，外購件與原材料的采購成功與否，大大影響到企業(yè) 的競爭力。對于企業(yè)向外部采購的話，我們依然基于此模型討論。假設(shè)：1物資必須經(jīng)過配送中心才可以到客戶2費用計算只

27、核算直接采購費用模型的最優(yōu)解也是基于費用最小理論。如果企業(yè)只采購物資，物資的下一步配送即由配送中心到客戶仍由企業(yè)來做，則此模型 中的工廠即可代表供應(yīng)商。模型求解如前例。如果企業(yè)將物資采購和配送全部外包，其只提供技術(shù)設(shè)計、資金等，則只需要在投資和 收益之間權(quán)衡。所選第三方可提供最大化的利潤則為最優(yōu)解。5、結(jié)束語0-1混合整數(shù)規(guī)劃法，由于其處理數(shù)據(jù)是在整數(shù)中進(jìn)行，運算結(jié)果更加符合現(xiàn)實情況， 因此0- 1混合整數(shù)規(guī)劃法被廣泛運用于RDC選址模型中，但有其現(xiàn)實情況中備選RDC的 數(shù)目較大，不同地區(qū)的運輸、配送、倉儲費用又有較大的差別，這將使模型變的十分的復(fù)雜， 我們無法再用傳統(tǒng)的運籌學(xué)方法去解決問題，

28、于是我們引ALING O編程的方法，使配送中 心選址問題得到了快速、精確、科學(xué)的解決。6、參考文獻(xiàn)1丁小東，姚志剛,程高.LINGO語言與0- 1混合整數(shù)規(guī)劃選址模型的再結(jié)合J.物流工 程與管理,2009,(31) 魏光興.物流配送中心選址綜述J.物流與交通,2007, (2).徐國松.LINGO軟件在運輸問題中的應(yīng)用J.科技創(chuàng)新導(dǎo)報，2008, NO.3楊滌塵.數(shù)學(xué)軟件與數(shù)學(xué)建模J.湖南人文科技學(xué)院學(xué)報，2006, (12).解答數(shù)據(jù)（原始解）Local optimal solution found.Objective value:Objective bound:Infeasibilitie

29、s:Extended solver steps:Total solver iterations:700500.0700500.00.000000634684Model Class:INLPTotal variables:35Nonlinear variables:30Integer variables:8Total constraints:21Nonlinear constraints:1Total nonzeros:127Nonlinear nonzeros:30VariableValueReduced CostA( 1)300.00000.000000A( 2)200.00000.0000

30、00A( 3)300.00000.000000A( 4)200.00000.000000A( 5)400.00000.000000B( 1)35000.000.000000B( 2)45000.000.000000B( 3)40000.000.000000B( 4)42000.000.000000B( 5)40000.000.000000U( 1)0.0000000.000000U( 2)1.00000045000.00U( 3)1.00000040000.00U( 4)0.0000000.000000U( 5)1.00000040000.00F( 1)40000.000.000000F( 2

31、)20000.000.000000F( 3)60000.000.000000V( 1)0.000000-0.5699975E+110.4500000E-030.1000000E-030.2200000E-03V(2)1.00000077000.00V(3)1.000000441500.0C(1)200.00000.000000C(2)300.00000.000000C(3)150.00000.000000C(4)250.00000.000000,M1)1800.00000.000000,M2)11000.0000.000000,M3)11200.0000.000000,M1)2700.0000

32、0.000000,M2)2500.00000.000000,M3)2700.00000.000000,M1)3800.00000.000000,M2)3600.00000.000000,M3)3500.00000.000000,M1)4500.00000.000000,M 2)4600.00000.000000,M3)4700.00000.000000,M1)5700.00000.000000,M2)5600.00000.000000,M3)5500.00000.000000,X1)10.000000,X 2)10.000000499.9999,X 3)10.000000699.9997,X 1)20.0000000.000000,X2)2200.00000.000000,X3)20.000000199.9998,X1)30.000000,X2)30.00000099.99990,X3)3300.00000.000000,X1)4