運(yùn)籌學(xué)基礎(chǔ) 課件 宋志華 第8、9章 庫存優(yōu)化、旅行商問題

第8章庫存優(yōu)化8.1庫存系統(tǒng)8.2經(jīng)典EOQ8.3分段價(jià)格EOQ8.4帶有儲(chǔ)存上限的多種貨物EOQ8.5動(dòng)態(tài)EOQ

8.1庫存系統(tǒng)

大多從事產(chǎn)品制造、貿(mào)易、銷售和修理的單位都不可避免地持有一系列實(shí)物資產(chǎn)的庫存,以協(xié)助將來的利用和銷售。一般而言,庫存系統(tǒng)模型如圖8-1所示。圖8-1庫存系統(tǒng)模型

庫存優(yōu)化就是尋找最優(yōu)的進(jìn)貨策略(進(jìn)貨時(shí)間、進(jìn)貨量),以使庫存系統(tǒng)的總費(fèi)用最低。庫存管理的總費(fèi)用包括進(jìn)貨成本、持有成本、短缺代價(jià)等。

(1)進(jìn)貨成本包括實(shí)物資產(chǎn)本身的購買成本(實(shí)物資產(chǎn)單價(jià)可能會(huì)隨著訂單大小的變化而變化)和固定費(fèi)用(如手續(xù)費(fèi)、派人外出采購、包裝和運(yùn)輸費(fèi)用等)。

(2)持有成本需要考慮的因素包括資金的占用、空間的占用、實(shí)物資產(chǎn)的防護(hù)保險(xiǎn)等產(chǎn)生的費(fèi)用、實(shí)物資產(chǎn)折舊等。

(3)出貨產(chǎn)生的費(fèi)用一般只考慮短缺代價(jià),也就是由于實(shí)物資產(chǎn)短缺不能滿足需求而導(dǎo)致喪失訂單或者停產(chǎn)等帶來的機(jī)會(huì)損失。

進(jìn)貨策略就是要決定什么時(shí)間進(jìn)多少貨物。常見的進(jìn)貨策略有以下三種:

(1)周期性補(bǔ)充策略,即每隔固定的時(shí)間進(jìn)貨一次,進(jìn)貨的數(shù)量固定。

(2)庫存閾值策略,即持續(xù)地檢查庫存數(shù)量,每當(dāng)庫存數(shù)量達(dá)到某個(gè)閾值的時(shí)候進(jìn)貨一次,進(jìn)貨的數(shù)量要使庫存達(dá)到某個(gè)固定值。

(3)混合策略,即周期性地檢查庫存數(shù)量,每當(dāng)庫存數(shù)量達(dá)到某個(gè)閾值的時(shí)候進(jìn)貨一次,進(jìn)貨的數(shù)量要使庫存達(dá)到某個(gè)固定值。

8.2經(jīng)典EOQ

定義8-1經(jīng)濟(jì)訂貨數(shù)量(EconomicOrderQuantity,EOQ)是庫存系統(tǒng)進(jìn)貨時(shí)應(yīng)該在每筆訂單中訂購貨物的數(shù)量,這個(gè)數(shù)量使周期性補(bǔ)充策略的庫存系統(tǒng)的總費(fèi)用最小。

經(jīng)典EOQ對(duì)庫存系統(tǒng)的假設(shè)如下:

(1)每次當(dāng)庫存水平達(dá)到特定的重新訂購點(diǎn)b時(shí),進(jìn)貨數(shù)量固定為Q,進(jìn)貨過程是沒

有時(shí)延的;

(2)出貨速率v是固定的,也就是庫存以固定的速度消耗;

(3)單位數(shù)量的貨物單位時(shí)間的持有成本為c1;

(4)單位數(shù)量的貨物的價(jià)格為c2;

(5)每次訂購都會(huì)產(chǎn)生一個(gè)固定費(fèi)用c3。

根據(jù)假設(shè)可得進(jìn)貨周期為

則庫存貨物數(shù)量的變化如圖8-2所示。

圖8-2經(jīng)典EOQ模型的庫存數(shù)量變化曲線

例8-1假設(shè)某學(xué)校每年要使用3500升油漆,每升油漆的價(jià)格為50元,每次批量購買的固定費(fèi)用為15元,每升油漆每年的持有成本為3元。請(qǐng)為這樣的需求及價(jià)格狀況制訂最優(yōu)的訂貨策略。

8.3分段價(jià)格EOQ

“量大從優(yōu)”是市場經(jīng)濟(jì)下很常見的現(xiàn)象。在經(jīng)典EOQ的基礎(chǔ)上,我們考慮針對(duì)不同訂貨量有不同單位商品價(jià)格的分段價(jià)格EOQ問題。分段價(jià)格EOQ與經(jīng)典EOQ唯一的不同在于單位商品的進(jìn)貨價(jià)格不再為常數(shù),而是一個(gè)訂貨量Q的函數(shù)c2(Q)。

分段價(jià)格EOQ問題的假設(shè)如下:

(1)每次當(dāng)庫存水平達(dá)到特定的重新訂購點(diǎn)b時(shí),進(jìn)貨數(shù)量固定為Q,進(jìn)貨過程是沒有時(shí)延的;

(2)出貨速率v是固定的,也就是庫存以固定的速度消耗;

(3)單位數(shù)量的貨物單位時(shí)間的持有成本為c1;

(4)單位數(shù)量的貨物的價(jià)格為c2(Q),是訂貨量Q的分段函數(shù);

(5)每次訂購都會(huì)產(chǎn)生一個(gè)固定費(fèi)用c3。

例8-2設(shè)某學(xué)校每年要使用3500升油漆,每次訂貨300升以上每升價(jià)格為45元,否則為50元,每次批量購買的固定費(fèi)用為15元,每升油漆每年的持有成本為3元。請(qǐng)為這樣的需求及價(jià)格狀況制訂最優(yōu)的訂貨策略。

根據(jù)已知條件,分段價(jià)格為

8.4帶有儲(chǔ)存上限的多種貨物EOQ

當(dāng)經(jīng)典EOQ和分段價(jià)格EOQ用于求解多個(gè)貨物的最優(yōu)庫存策略時(shí),如果多個(gè)貨物相互之間沒有關(guān)聯(lián),則只需分別求解。現(xiàn)在考慮一種有關(guān)聯(lián)的情況,也就是多個(gè)貨物存放到一個(gè)倉庫里,而倉庫的容積是有限的,這也是一種很常見的情形。

帶有儲(chǔ)存上限的多貨物EOQ問題的假設(shè)如下:

(1)每次當(dāng)貨物i庫存水平達(dá)到特定的重新訂購點(diǎn)bi時(shí),進(jìn)貨數(shù)量固定為Qi,進(jìn)貨過程是沒有時(shí)延的;

(2)貨物i的出貨速率vi是固定的,也就是庫存以固定的速度消耗;

(3)單位數(shù)量的貨物i單位時(shí)間的持有成本為ci1;

(4)單位數(shù)量的貨物i的價(jià)格為ci2;

(5)每次訂購貨物i都會(huì)產(chǎn)生一個(gè)固定費(fèi)用ci3;

(6)單位貨物i占用倉庫容積為si,倉庫的總?cè)莘e為S。

例8-3假設(shè)要確定三種貨物的最優(yōu)庫存策略,倉庫的最大可用面積為150平方米,其他參數(shù)如表8-1所示。

代入相關(guān)參數(shù),得到數(shù)學(xué)模型:

這是一個(gè)帶約束的非線性規(guī)劃模型,可以使用Excel的規(guī)劃工具求解。圖8-3給出了所用的公式和Excel規(guī)劃求解的參數(shù)。注意決策變量必須要給出一個(gè)非零的初始值,因?yàn)槟繕?biāo)函數(shù)中決策變量出現(xiàn)在分母中。

圖8-3例8-3的Excel規(guī)劃求解

Excel求解得到的最優(yōu)解如圖8-4所示。因此,三種貨物的訂貨周期分別為

圖8-4例8-3的Excel規(guī)劃求解得到的最優(yōu)解

8.5動(dòng)態(tài)EOQ

動(dòng)態(tài)EOQ問題的假設(shè)如下:(1)庫存優(yōu)化分為多個(gè)周期,第i個(gè)周期的進(jìn)貨數(shù)量為Qi,進(jìn)貨過程是沒有時(shí)延的;(2)第i個(gè)周期的貨物需求量為Di;(3)單位數(shù)量的貨物在第i個(gè)周期的持有成本為ci1;(4)單位數(shù)量的貨物在第i個(gè)周期的價(jià)格為ci2;(5)第i個(gè)周期每筆訂貨的固定費(fèi)用為ci3。

例8-4已知某單位年初剩余原材料為2噸,假設(shè)原材料的需求量、持有成本、價(jià)格以及進(jìn)貨的固定費(fèi)用每個(gè)季度都各不相同,表8-2給出了未來一年各個(gè)季度的數(shù)據(jù),請(qǐng)為其生產(chǎn)使用的原材料制訂未來一年的最優(yōu)庫存策略。

由于總的貨物的購買成本是常數(shù),因此在規(guī)劃的時(shí)候可以不予考慮。

將庫存數(shù)量作為模型的狀態(tài),增加一個(gè)虛擬的起始狀態(tài)和一個(gè)虛擬的結(jié)束狀態(tài),中間每個(gè)階段考慮一個(gè)季度的庫存,將問題分成5個(gè)階段。

第1階段:年初剩余原材料的數(shù)量為2噸,因此第1階段的狀態(tài)x1=2。

第2階段:將第1階段的狀態(tài)作為起始狀態(tài),其對(duì)應(yīng)的決策(進(jìn)貨數(shù)量)、到達(dá)狀態(tài)(庫存數(shù)量)及行動(dòng)成本(持有成本+固定費(fèi)用)如表8-3所示。假設(shè)每個(gè)季度的貨物的需求在本季度不計(jì)算持有成本。

第3階段:將第2階段的狀態(tài)作為起始狀態(tài),其對(duì)應(yīng)的決策(進(jìn)貨數(shù)量)、到達(dá)狀態(tài)(庫存數(shù)量)及行動(dòng)成本(持有成本+固定費(fèi)用)如表8-4所示。假設(shè)每個(gè)季度的貨物的需求在本季度不計(jì)算持有成本。

第4階段:將第3階段的狀態(tài)作為起始狀態(tài),其對(duì)應(yīng)的決策(進(jìn)貨數(shù)量)、到達(dá)狀態(tài)(庫存數(shù)量)及行動(dòng)成本(持有成本+固定費(fèi)用)如表8-5所示。假設(shè)每個(gè)季度的貨物的需求在本季度不計(jì)算持有成本。

第5階段:將第4階段的狀態(tài)作為起始狀態(tài),其對(duì)應(yīng)的決策(進(jìn)貨數(shù)量)、到達(dá)狀態(tài)(庫存數(shù)量)及行動(dòng)成本(持有成本+固定費(fèi)用)如表8-6所示。假設(shè)每個(gè)季度的貨物的需求在本季度不計(jì)算持有成本。第9章旅行商問題9.1TSP的構(gòu)造啟發(fā)式算法9.2線性規(guī)劃模型9.3TSP路徑構(gòu)造的貪婪啟發(fā)式算法9.4TSP的改進(jìn)啟發(fā)式算法9.5TSP的遺傳算法

9.1TSP的構(gòu)造啟發(fā)式算法

旅行商問題(TravelingSalesmanProblem,TSP)是這樣一個(gè)問題:給定一系列城市和每對(duì)城市之間的距離,求解訪問每一座城市一次并回到起始城市的最短回路。TSP是運(yùn)籌學(xué)中目前研究最為廣泛的問題之一,但對(duì)于一般情況,還沒有有效的解決方法。雖然TSP的復(fù)雜性未知,但60多年來,其求解方法在不斷改進(jìn)。表9-1顯示了TSP問題的求解記錄。

9.2線性規(guī)劃模型

此模型的決策變量有n(n-1)個(gè),式(9-2)和式(9-3)均有n個(gè),連通性約束有2n-2n-2個(gè),因此共有2n-2個(gè)約束條件,即使對(duì)于n=318這樣小規(guī)模的TSP問題,也有5.34e+95個(gè)約束條件,比宇宙中的原子數(shù)量還要多!

一般來講,通過算法構(gòu)建一條可行的旅行商路徑并不困難,雖然一般情況下證明是最優(yōu)的很困難。在這種情況下,我們不知道找到的路徑是否是最優(yōu)解,但是知道這個(gè)解還不錯(cuò),因此可以稱之為優(yōu)化解,它可能是最優(yōu)的,也可能不是,并且很多情況下,可以通過解的下界大概估計(jì)優(yōu)化解的優(yōu)化程度。

9.3TSP路徑構(gòu)造的貪婪啟發(fā)式算法

9.3.1最近鄰算法所謂最近鄰算法,就是從一個(gè)點(diǎn)開始逐步增加距離當(dāng)前點(diǎn)最近的點(diǎn)構(gòu)造出一個(gè)TSP路徑。

例9-1在Matlab上實(shí)現(xiàn)最近鄰函數(shù),并隨機(jī)生成城市節(jié)點(diǎn)進(jìn)行驗(yàn)證。

使用Matlab編寫最近鄰函數(shù)的代碼如下:

在平面上隨機(jī)生成30個(gè)點(diǎn),使用最近鄰方法構(gòu)造TSP路徑的代碼如下:

進(jìn)行4次實(shí)驗(yàn),算法構(gòu)造生成的TSP路徑如圖9-1所示。圖9-1最近鄰算法生成的幾個(gè)TSP路徑

9.3.2插入算法

插入算法是從一個(gè)較小的圈開始,逐步將不在圈上的點(diǎn)插入圈上,直到擴(kuò)充為一條TSP路徑為止。

例9-2在Matlab上實(shí)現(xiàn)插入函數(shù),并隨機(jī)生成城市節(jié)點(diǎn)進(jìn)行驗(yàn)證。

在平面上隨機(jī)生成30個(gè)點(diǎn),使用插入算法構(gòu)造TSP路徑的代碼如下:

進(jìn)行4次實(shí)驗(yàn),算法構(gòu)造生成的TSP路徑如圖9-2所示。由圖可見,生成的不是最優(yōu)解,而是優(yōu)化解。圖9-2插入算法生成的幾個(gè)TSP路徑

9.3.3Merger算法

9.4TSP的改進(jìn)啟發(fā)式算法

9.4.12opt操作

例9-3在如圖9-3所示的TSP路徑上,查看有沒有兩條邊能滿足交叉消除操作的條件。圖9-3TSP路徑的交叉消除操作

如圖9-3所示,當(dāng)前TSP路徑上有(1,2)和(3,4)兩條邊在平面上是有交叉的,于是根據(jù)三角不等式可得

因此,在TSP路徑上去掉(1,2)和(3,4)兩條邊,并增加(1,3)和(2,4)兩條邊,TSP路徑的總長度縮短,解得到改進(jìn)。

例9-4在Matlab上實(shí)現(xiàn)2opt函數(shù),并隨機(jī)生成城市節(jié)點(diǎn)進(jìn)行驗(yàn)證。

進(jìn)行實(shí)驗(yàn),結(jié)果如圖9-4所示,可以發(fā)現(xiàn)在平面上已經(jīng)沒有交叉了。圖9-42opt操作通過消除平面交叉改進(jìn)TSP路徑

9.4.2k－opt操作

所謂k－opt操作,就是在TSP路徑上去掉k條邊,并使用另外的k條總長度更小的邊將其代替并重新連接成一條可行TSP路徑的操作。

如果一條TSP路徑無法通過kopt操作改進(jìn),則稱其為k－optimal的。如果一條TSP路徑是koptimal的,則對(duì)于比k小的自然數(shù)k',這條路徑一定也是k'optimal的。

如果一條TSP路徑是n－optimal的,則這條TSP路徑是最優(yōu)的。

雖然能夠驗(yàn)證k－optimal中的k越大,解越接近最優(yōu),但是隨著k的增大,k－optimal的驗(yàn)證難度呈指數(shù)級(jí)增加,因此一般情況下只利用k=2,3來改進(jìn)。

9.5TSP的遺傳算法

9.5.1基本原理與步驟TSP路徑構(gòu)造的貪婪啟發(fā)式算法通過貪婪規(guī)則從無到有構(gòu)造一個(gè)優(yōu)化解,TSP的改進(jìn)啟發(fā)式算法對(duì)一個(gè)已有的解進(jìn)行改進(jìn),而TSP的遺傳算法中上述兩個(gè)算法的工作都要做,因此,也稱之為元啟發(fā)式算法。遺傳算法計(jì)算的過程框架如圖9-5所示。

圖9-5遺傳算法(元啟發(fā)式算法)計(jì)算的過程框架

遺傳算法的基本步驟如下:

步驟1:將問題的解編碼為染色體,并生成初始染色體群,每個(gè)染色體代表一個(gè)解。

步驟2:進(jìn)行交叉、變異、選擇等操作,計(jì)算每個(gè)染色體的適應(yīng)度函數(shù)值,更新染色體群。

步驟3:直到滿足算法停止條件的時(shí)候,停止計(jì)算,最優(yōu)的染色體代表的解即為所得的優(yōu)化解,否則轉(zhuǎn)步驟2。

9.5.2算法設(shè)計(jì)要點(diǎn)

1.解的編碼

在旅行商問題中,對(duì)問題解的編碼應(yīng)該采用城市編號(hào)序列的方法,這樣更加有利于交叉、變異等操作生成可行解,否則一個(gè)交叉之后,生成可行解的概率很低。

2.生成初始種群

所謂生成初始種群,就是生成一定數(shù)量的可行解,一般隨機(jī)生成,而不太采用構(gòu)造啟發(fā)式算法。作為全局性算法,