沈 潔，祖天琪，宋雨徽，太文芳

(遼寧師范大學 數學學院，遼寧 大連 116029)

0 引言

優(yōu)化問題是基于現有資源使效益最大或為實現某目標使成本最低的問題[1].本文研究的列車時刻表效用值問題是非光滑優(yōu)化問題[2]，求解方法通常包括最速下降法、黑盒子方法、束方法等[3].最速下降法需要對次微分有整體地全面了解，黑盒子方法無法保證目標函數的下降，二者的不足較明顯，而束方法結合了最速下降法的下降性和黑盒子方法的穩(wěn)定性[3]，效果較好.常規(guī)的束方法有水平束方法、信賴域束方法、懲罰束方法等[3].在實際運算中，目標函數值往往不能被精確算出，通常得到的是近似值，故近幾年有多名學者利用目標函數近似值對束方法展開研究，如：張清葉等[4]提出了一種求解非光滑凸規(guī)劃問題的混合束方法；董小霞等[5-7]利用目標函數的近似信息研究非精確束方法；沈潔等[8-9]利用懲罰束方法解決通信數據網絡優(yōu)化問題近似模型的相關問題并研究了非光滑無約束凸規(guī)劃的混合束方法；U.Brannlund等[10]介紹了一種針對列車時刻表優(yōu)化問題的拉格朗日松弛方法；A.A.Abderrahman等[11]介紹了一種針對列車時刻表優(yōu)化問題的聚集束方法.列車時刻表效用值優(yōu)化問題是指尋找一個科學可執(zhí)行的列車時刻表來使軌道運輸產生的效用值達到最大的問題.本文針對列車時刻表效用值優(yōu)化問題提出了一種改進的束方法，即通過使用指示函數將約束問題轉換成無約束問題，利用束方法基本思想構建了切平面近似模型，在此基礎上以對偶理論為基礎，給出了原規(guī)劃與對偶規(guī)劃最優(yōu)解的顯式表達，并得到了近似優(yōu)化模型的一些相關結論，為后續(xù)算法構造奠定了基礎，對于軌道交通運營效率的提高具有重要的客觀參考價值.

1 預備知識與模型構建

首先給出非光滑優(yōu)化基本概念、束方法相關理論和列車時刻表優(yōu)化效用值優(yōu)化問題的近似模型.

定義1(次微分) 設f(x)是Rn上的凸函數，f(x)在x點處的次微分定義為

?f(x)={s∈Rn|f(y)≥f(x)+sT(y-x)，?y∈Rn}.

定義2(εk次微分) 設f(x)是Rn上的凸函數，εk>0為常數，f(x)在x點處的εk次微分定義為

?εkf(x)={s∈Rn|f(y)≥f(x)+sT(y-x)-εk，?y∈Rn}.

定義3(法錐) 設S?Rn非空，集合S在點x∈S處的法錐NS(x)定義為

NS(x)={d∈Rn|dT(y-x)≤0，?y∈S}.

列車時刻表效用值問題(TTP)是指尋找一個科學可執(zhí)行的列車時刻表來使軌道運輸產生的效用值達到最大的問題.科學可執(zhí)行意味著既要滿足每列列車在特定的時間段內不發(fā)生沖突，又不能超出鐵路系統(tǒng)的基礎設施與軌道容量的限制.優(yōu)化列車時刻表主要考慮的效用值規(guī)劃問題是[9]：

(1)

只考慮問題(1)中的第一個約束，引入對偶變量y∈Rn，則問題(1)的拉格朗日函數為

(2)

引入指示函數

其中D={y|y≥0}，y≥0表示y的每個坐標都大于或等于零，文中類似情形不再說明.則問題(2)可改寫為一個無約束優(yōu)化問題，具體為

(3)

為避免步長較大，問題(3)中增加二次項，引入控制參數uk調整步長，相應效用值子問題為

(4)

定義額定下降為

(5)

2 基于近似模型對偶問題最優(yōu)解的表達及相關性質研究

定理2.1設yk+1是列車時刻表近似模型子問題(4)的最優(yōu)解，那么

(6)

證明將問題(4)寫成一個帶有額外標量r的二次規(guī)劃問題，具體為

(7)

整理后得到

其中

因此

(8)

定理2.2對于時刻列車表效用值優(yōu)化模型近似問題(4)，有以下結論成立：

證明(ⅰ) 根據問題(4)的最優(yōu)性條件和k的定義，有

故

(ⅱ) 由于沒有對偶間隙，原規(guī)劃(4)與對偶規(guī)劃(8)最優(yōu)值等價，即

由式(4)和式(5)有

由于μk為穩(wěn)定中心，yk+1為最優(yōu)解，則iD(μk)=0，iD(yk+1)=0.應用式(5)額定下降的定義和(ⅱ)的結論，有

因此

φ(y)+iD(y)≥φ(μk)+iD(μk)+k*(y-μk)-εk.

故

k∈?εkφ(μk)+?εkiD(μk).

3 結語

本文采用傳統(tǒng)懲罰束方法對列車時刻表效用值優(yōu)化問題展開了研究.通過增加指示函數構建目標函數的近似模型，利用束方法基本思想構建了切平面近似模型，以對偶理論為基礎，給出了原規(guī)劃與對偶規(guī)劃最優(yōu)解的顯式表達以及近似優(yōu)化模型的一些相關結論，為后續(xù)算法構造奠定了基礎.