朱美樺，王興芳，韓 瑛

（蘭州交通大學 交通運輸學院，甘肅 蘭州 730070）

1 供應(yīng)鏈中分級協(xié)調(diào)機制的問題闡述和模型建立

1.1 問題描述

圖1為庫存系統(tǒng)圖，圖中箭頭方向表示物流的方向，有向線段表示銷售商、供應(yīng)商、生產(chǎn)商之間的物流。

圖1 供應(yīng)調(diào)查

為了滿足銷售商的要求，生產(chǎn)商需從供應(yīng)商那里提前訂購零件，但由于種種原因，有時供應(yīng)商不能按時交貨，這樣產(chǎn)品就不能按時被生產(chǎn)商生產(chǎn)出來，進而影響了銷售商的銷售市場。但是，任何事物都是有規(guī)則的，供應(yīng)商、生產(chǎn)商、銷售商也不例外，為了彼此達到“互利共贏”的目的，一張合同將它們緊密聯(lián)系在了一起。

因此，為了協(xié)調(diào)這種關(guān)系，提出方法—懲罰費用。對于供應(yīng)商不能按時交貨，給出懲罰費用，對于生產(chǎn)商不能按時交貨，也給出一個懲罰費用。

1.2 供應(yīng)鏈的基本數(shù)學模型

1.2.1 模型假設(shè)

本文所做的假設(shè)如下：①生產(chǎn)商和供應(yīng)商是長期的合作伙伴，并且相互信任；②生產(chǎn)商和供應(yīng)商信息不對稱，也就是說，他們之間保持一定的隱私，不透漏其所有數(shù)據(jù)；③供應(yīng)商、生產(chǎn)商和銷售商是一個相互合作的團隊，所有參與者都為了使一個共同的目標得到最優(yōu)化；④在整個供應(yīng)鏈中，已知的量是銷售商訂單；⑤在整個供應(yīng)鏈中，只考慮成本不考慮時間，供應(yīng)商的模型是線性的；⑥零件費用相等；⑦零件最大供量應(yīng)該相同。

1.2.2 模型建立

1.2.2.1 生產(chǎn)商的模型（P）

假設(shè)供應(yīng)鏈中有i∈（i＝1，2，…I）個零件，j∈（j＝1，2，…，J）作業(yè)。在計劃期t∈（t＝1，2，…T）內(nèi)，按定單滿足客戶產(chǎn)品量和時間需求。

1）目標函數(shù)

2）約束條件

生產(chǎn)力約束

網(wǎng)絡(luò)約束

物質(zhì)平衡約束

訂單交貨約束

整數(shù)約束

3）參數(shù)和變量

參數(shù)：i為零件，j為作業(yè)，t為時間，I為總零件數(shù)，J為總作業(yè)數(shù)，c為生產(chǎn)力單位成本，Y為單周期最大生產(chǎn)力，Pi為購買單個零件i的費用，hpi為生產(chǎn)商對零件i的單位庫存成本，Δt為延期時間，F(xiàn)為延期交付的單位懲罰費用（P→C），k為延期交付的單位懲罰費用（S→P）。

變量：qi為購買零件i的數(shù)量，Ipi為生產(chǎn)商對零件i的庫存量，ei為延期交付零件i的數(shù)量（S→P），di為要交付零件i的數(shù)量（S→P），aj為作業(yè)j的生產(chǎn)消耗，Dj為作業(yè)j的生產(chǎn)持續(xù)時間，Ei為預(yù)期交付時間（P→C），vij為開始作業(yè)j需要的零件量i。

從上面可以看出：生產(chǎn)商的模型為總成本最小，它包含存儲費用、購買費用和懲罰費用。

1.2.2.2 供應(yīng)商的模型（S）

1）目標函數(shù)

2）約束條件

物質(zhì)平衡約束

訂單交貨約束

整數(shù)約束

3）參數(shù)和變量

參數(shù)：pi為購買單個零件i的 費用，hsi為供應(yīng)商對零件i的庫存成本，k為延期交付的單位懲罰費用（S→P），Qi為零件i的最大供應(yīng)量。

變量：di為要交付零件i的數(shù)量（S→P），Isi為供應(yīng)商對零件i的庫存量，ei為延期交付零件i的數(shù)量（S→P）。

從上面可以看出：供應(yīng)商的模型為總利潤最大，它也包含購買費用、存儲費用和懲罰費用。

2 模擬退火算法及求解

2.1 模擬退火算法的基本流程

根據(jù)模擬退火算法的基本框架，針對具體問題時還需要具體的設(shè)計。模擬退火具有兩層循環(huán)，內(nèi)循環(huán)模擬的是在給定的溫度下系統(tǒng)達到平衡的過程。在此循環(huán)中，每次從當前i的領(lǐng)域中隨機找出一個新解j，然后按照Metropolis的準則概率接受新解。算法中的random（0，1）是指在區(qū)間［0，1］上按均勻分布產(chǎn)生一個隨機數(shù)，而所謂的內(nèi)層達到熱平衡也是一個籠統(tǒng)的說法，可以定義為循環(huán)一定的代數(shù)，或者基于接受率定義平衡等。算法的外層循環(huán)是一個降溫的過程，當在一個溫度下達到平衡后，開始外層的降溫，然后在新的溫度下重新開始內(nèi)循環(huán)。降溫的方法可以根據(jù)具體問題具體設(shè)計，而且算法流程圖中給出了初始溫度T 也需要算法的使用者根據(jù)具體的問題而制定。

在用模擬退火算法求解最優(yōu)化問題時，涉及以下幾個方面的基本要素。

2.1.1 初始溫度

影響模擬退火算法全局搜索性能的重要因素之一是初始溫度t0的設(shè)置。實驗表明，要獲得高質(zhì)量解，初溫就得越大，但花費的計算時間也將越多。因此，初溫的確定應(yīng)折中考慮優(yōu)化效率和優(yōu)化質(zhì)量，常用方法有以下幾種：

1）以個狀態(tài)目標值的方差為初溫，均勻抽樣一組狀態(tài)；

2）利用經(jīng)驗公式給出初溫；

3）隨機產(chǎn)生一組狀態(tài)，確定出兩兩狀態(tài)間最大目標差值｜△max｜，然后根據(jù)差值，利用一定的函數(shù)確定初溫。例如t＝－△max／pr，其中pr為初始接受概率。

2.1.2 領(lǐng)域函數(shù)

領(lǐng)域函數(shù)（狀態(tài)產(chǎn)生函數(shù)）通常有兩部分組成，即候選解產(chǎn)生的概率分布和產(chǎn)生候選解的方式。概率分布可以是均勻分布、指數(shù)分布、正態(tài)分布等，候選解一般采用某一概率密度函數(shù)對解空間進行隨機采樣獲得。

2.1.3 接受概率

指從一個可行解Xk向另一個可行解Xnew的轉(zhuǎn)移概率，通俗的理解是接受一個新解為當前解的概率。與它有關(guān)的是當前的溫度參數(shù)tk，隨著溫度的下降而減小。一般采用Metropolis準則。

2.1.4 冷卻控制

指的是降溫管理表（降溫方式）即從某一較高溫的狀態(tài)t0向較低溫狀態(tài)冷卻。假設(shè)用tk來表示時刻k的溫度，則經(jīng)典模擬退火算法的降溫方式為

而快速模擬退火算法的降溫方式為

這2 種方式都能使模擬退火算法收斂于全局最小點。

2.1.5 內(nèi)層平衡

內(nèi)層平衡也稱Metropolis抽樣穩(wěn)定準則，相當于由各溫度下產(chǎn)生候選解的數(shù)目決定。以下幾項是常用的抽樣穩(wěn)定準則：預(yù)先設(shè)定的抽樣數(shù)目，內(nèi)循環(huán)代數(shù)；目標值變化較?。ㄟB續(xù)若干步）；目標函數(shù)的均值是否穩(wěn)定。

2.1.6 終止條件

常用的算法中止準則包括以下幾項：外循環(huán)迭代次數(shù)；終止溫度的閥值；連續(xù)若干步保持不變直到算法搜索到最優(yōu)值；檢驗系統(tǒng)熵是否穩(wěn)定。

2.2 模擬退火算法的描述和實現(xiàn)

2.2.1 一般過程描述

模擬退火的一般過程可以描述為：

步驟1 給定初溫Tk＝T0，隨機產(chǎn)生初始生產(chǎn)順序向量（di，ei，I0p）＝（d0，e0，Ip0），計算目標值Cp。令k＝0。

步驟2 如果停止準則不滿足，重復以下過程。

步驟2.1 執(zhí)行以下過程Lk次：

步驟2.1.1 從狀態(tài)i的領(lǐng)域解中隨機選取新狀態(tài)j；

步驟2.1.2 令Δ＝f（j）－f（i）；

步驟2.1.3 若△＜＝0，則令i＝j(luò)，否則以概率exp（－△／tk）令i＝j(luò)。

步驟2.2 退溫：令k＝k＋1，計算tk＝d（tk），同時按規(guī)則更新Lk。

步驟3 輸出i。

2.2.2 參數(shù)設(shè)定

根據(jù)模擬退火算法的演算流程，表1是對模擬退火算法的參數(shù)設(shè)定。

表1 模擬退火算法的參數(shù)設(shè)定

3 實 例

為了說明該算法的有效性及可靠性，而且能夠直觀反映出一些模擬退火特征，實驗結(jié)果如表2～表4所示。

假設(shè)整個供應(yīng)鏈中有7個作業(yè)，7個訂單，其中一個訂單對應(yīng)一個作業(yè)。

表2 訂單數(shù)據(jù)和作業(yè)在第一階段的生產(chǎn)消耗

表3 生廠商的數(shù)據(jù)

表4 供應(yīng)商的數(shù)據(jù)

4 結(jié)束語

在本文中研究了一個供應(yīng)商和制造商的供應(yīng)鏈中的分級協(xié)調(diào)機制問題。根據(jù)其模型，運用模擬退火算法，提出求解該問題的一種求解方法。通過運用c＋＋對該問題進行了求解，得到了接近最優(yōu)解的生產(chǎn)總成本最小，供應(yīng)總利潤最大的解，最后的算例證明了針對供應(yīng)鏈角色，模擬退火算法是一種高效算法。但是，兩個模型僅僅提供了解決在確定條件下供應(yīng)商和生產(chǎn)商之間關(guān)系的框架，為了解決更廣泛的問題，并求得更精確的解，還需對模型添加相應(yīng)的決策變量和約束條件，或考慮有關(guān)模糊條件下的建模。

［1］林勇，馬士華.供應(yīng)鏈管理［M］.北京：高等教育出版社，2003.

［2］蔡連僑，陳劍.供應(yīng)鏈建模與優(yōu)化［J］.系統(tǒng)工程理論與實踐，2001（6）：26－33.

［3］邢文訓，謝金星.現(xiàn)代優(yōu)化計算方法［M］.北京：清華大學出版社，2005.

［4］黃平，孟永鋼.最優(yōu)化理論與方法［M］.北京：清華大學出版社，2009.

［5］汪定偉，王俊偉，王洪峰，張瑞友，郭哲.智能優(yōu)化方法［M］.北京：高等教育出版社，2007.

［6］何利英.面向客戶的供應(yīng)鏈優(yōu)化模型研究［D］.成都：西南交通大學，2003.

［7］孫文瑜，袁亞湘.最優(yōu)化理論與方法［M］.蘭州：科學出版社，1997.

［8］張文修，梁怡.遺傳算法的數(shù)學基礎(chǔ)［M］.西安：西安交通大學出版社，2003.