第8章庫存優化8.1庫存系統8.2經典EOQ8.3分段價格EOQ8.4帶有儲存上限的多種貨物EOQ8.5動態EOQ

8.1庫存系統

大多從事產品制造、貿易、銷售和修理的單位都不可避免地持有一系列實物資產的庫存,以協助將來的利用和銷售。一般而言,庫存系統模型如圖8-1所示。圖8-1庫存系統模型

庫存優化就是尋找最優的進貨策略(進貨時間、進貨量),以使庫存系統的總費用最低。庫存管理的總費用包括進貨成本、持有成本、短缺代價等。

(1)進貨成本包括實物資產本身的購買成本(實物資產單價可能會隨著訂單大小的變化而變化)和固定費用(如手續費、派人外出采購、包裝和運輸費用等)。

(2)持有成本需要考慮的因素包括資金的占用、空間的占用、實物資產的防護保險等產生的費用、實物資產折舊等。

(3)出貨產生的費用一般只考慮短缺代價,也就是由于實物資產短缺不能滿足需求而導致喪失訂單或者停產等帶來的機會損失。

進貨策略就是要決定什么時間進多少貨物。常見的進貨策略有以下三種:

(1)周期性補充策略,即每隔固定的時間進貨一次,進貨的數量固定。

(2)庫存閾值策略,即持續地檢查庫存數量,每當庫存數量達到某個閾值的時候進貨一次,進貨的數量要使庫存達到某個固定值。

(3)混合策略,即周期性地檢查庫存數量,每當庫存數量達到某個閾值的時候進貨一次,進貨的數量要使庫存達到某個固定值。

8.2經典EOQ

定義8-1經濟訂貨數量(EconomicOrderQuantity,EOQ)是庫存系統進貨時應該在每筆訂單中訂購貨物的數量,這個數量使周期性補充策略的庫存系統的總費用最小。

經典EOQ對庫存系統的假設如下:

(1)每次當庫存水平達到特定的重新訂購點b時,進貨數量固定為Q,進貨過程是沒

有時延的;

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

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

(4)單位數量的貨物的價格為c2;

(5)每次訂購都會產生一個固定費用c3。

根據假設可得進貨周期為

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

圖8-2經典EOQ模型的庫存數量變化曲線

例8-1假設某學校每年要使用3500升油漆,每升油漆的價格為50元,每次批量購買的固定費用為15元,每升油漆每年的持有成本為3元。請為這樣的需求及價格狀況制訂最優的訂貨策略。

8.3分段價格EOQ

“量大從優”是市場經濟下很常見的現象。在經典EOQ的基礎上,我們考慮針對不同訂貨量有不同單位商品價格的分段價格EOQ問題。分段價格EOQ與經典EOQ唯一的不同在于單位商品的進貨價格不再為常數,而是一個訂貨量Q的函數c2(Q)。

分段價格EOQ問題的假設如下:

(1)每次當庫存水平達到特定的重新訂購點b時,進貨數量固定為Q,進貨過程是沒有時延的;

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

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

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

(5)每次訂購都會產生一個固定費用c3。

例8-2設某學校每年要使用3500升油漆,每次訂貨300升以上每升價格為45元,否則為50元,每次批量購買的固定費用為15元,每升油漆每年的持有成本為3元。請為這樣的需求及價格狀況制訂最優的訂貨策略。

根據已知條件,分段價格為

8.4帶有儲存上限的多種貨物EOQ

當經典EOQ和分段價格EOQ用于求解多個貨物的最優庫存策略時,如果多個貨物相互之間沒有關聯,則只需分別求解。現在考慮一種有關聯的情況,也就是多個貨物存放到一個倉庫里,而倉庫的容積是有限的,這也是一種很常見的情形。

帶有儲存上限的多貨物EOQ問題的假設如下:

(1)每次當貨物i庫存水平達到特定的重新訂購點bi時,進貨數量固定為Qi,進貨過程是沒有時延的;

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

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

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

(5)每次訂購貨物i都會產生一個固定費用ci3;

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

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

代入相關參數,得到數學模型:

這是一個帶約束的非線性規劃模型,可以使用Excel的規劃工具求解。圖8-3給出了所用的公式和Excel規劃求解的參數。注意決策變量必須要給出一個非零的初始值,因為目標函數中決策變量出現在分母中。

圖8-3例8-3的Excel規劃求解

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

圖8-4例8-3的Excel規劃求解得到的最優解

8.5動態EOQ

動態EOQ問題的假設如下:(1)庫存優化分為多個周期,第i個周期的進貨數量為Qi,進貨過程是沒有時延的;(2)第i個周期的貨物需求量為Di;(3)單位數量的貨物在第i個周期的持有成本為ci1;(4)單位數量的貨物在第i個周期的價格為ci2;(5)第i個周期每筆訂貨的固定費用為ci3。

例8-4已知某單位年初剩余原材料為2噸,假設原材料的需求量、持有成本、價格以及進貨的固定費用每個季度都各不相同,表8-2給出了未來一年各個季度的數據,請為其生產使用的原材料制訂未來一年的最優庫存策略。

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

將庫存數量作為模型的狀態,增加一個虛擬的起始狀態和一個虛擬的結束狀態,中間每個階段考慮一個季度的庫存,將問題分成5個階段。

第1階段:年初剩余原材料的數量為2噸,因此第1階段的狀態x1=2。

第2階段:將第1階段的狀態作為起始狀態,其對應的決策(進貨數量)、到達狀態(庫存數量)及行動成本(持有成本+固定費用)如表8-3所示。假設每個季度的貨物的需求在本季度不計算持有成本。

第3階段:將第2階段的狀態作為起始狀態,其對應的決策(進貨數量)、到達狀態(庫存數量)及行動成本(持有成本+固定費用)如表8-4所示。假設每個季度的貨物的需求在本季度不計算持有成本。

第4階段:將第3階段的狀態作為起始狀態,其對應的決策(進貨數量)、到達狀態(庫存數量)及行動成本(持有成本+固定費用)如表8-5所示。假設每個季度的貨物的需求在本季度不計算持有成本。

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

9.1TSP的構造啟發式算法

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

9.2線性規劃模型

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

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

9.3TSP路徑構造的貪婪啟發式算法

9.3.1最近鄰算法所謂最近鄰算法,就是從一個點開始逐步增加距離當前點最近的點構造出一個TSP路徑。

例9-1在Matlab上實現最近鄰函數,并隨機生成城市節點進行驗證。

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

在平面上隨機生成30個點,使用最近鄰方法構造TSP路徑的代碼如下:

進行4次實驗,算法構造生成的TSP路徑如圖9-1所示。圖9-1最近鄰算法生成的幾個TSP路徑

9.3.2插入算法

插入算法是從一個較小的圈開始,逐步將不在圈上的點插入圈上,直到擴充為一條TSP路徑為止。

例9-2在Matlab上實現插入函數,并隨機生成城市節點進行驗證。

在平面上隨機生成30個點,使用插入算法構造TSP路徑的代碼如下:

進行4次實驗,算法構造生成的TSP路徑如圖9-2所示。由圖可見,生成的不是最優解,而是優化解。圖9-2插入算法生成的幾個TSP路徑

9.3.3Merger算法

9.4TSP的改進啟發式算法

9.4.12opt操作

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

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

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

例9-4在Matlab上實現2opt函數,并隨機生成城市節點進行驗證。

進行實驗,結果如圖9-4所示,可以發現在平面上已經沒有交叉了。圖9-42opt操作通過消除平面交叉改進TSP路徑

9.4.2k－opt操作

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

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

如果一條TSP路徑是n－optimal的,則這條TSP路徑是最優的。

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

9.5TSP的遺傳算法

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

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

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

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

步驟2:進行交叉、變異、選擇等操作,計算每個染色體的適應度函數值,更新染色體群。

步驟3:直到滿足算法停止條件的時候,停止計算,最優的染色體代表的解即為所得的優化解,否則轉步驟2。

9.5.2算法設計要點

1.解的編碼

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

2.生成初始種群

所謂生成初始種群,就是生成一定數量的可行解,一般隨機生成,而不太采用構造啟發式算法。作為全局性算法,