劉山，張林玲，郝立東，曹盛文

（中國(guó)民航大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津300300）

0-1線(xiàn)性規(guī)劃的連續(xù)化求解方法

劉山，張林玲，郝立東，曹盛文

（中國(guó)民航大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津300300）

針對(duì)0-1線(xiàn)性規(guī)劃的優(yōu)化問(wèn)題，提出一種懲罰函數(shù)方法?？紤]到0-1線(xiàn)性規(guī)劃的最優(yōu)值特征，通過(guò)在目標(biāo)函數(shù)中加上懲罰函數(shù)，將0-1離散線(xiàn)性規(guī)劃模型連續(xù)化成非線(xiàn)性規(guī)劃模型，并使用Matlab的Fmincon函數(shù)進(jìn)行求解。經(jīng)對(duì)多個(gè)算例的計(jì)算，并和其他算法比較，結(jié)果表明懲罰函數(shù)法的可行性和有效性。將該方法應(yīng)用于實(shí)際的飛機(jī)排班問(wèn)題上，取得比較滿(mǎn)意的結(jié)果。

0-1線(xiàn)性規(guī)劃；懲罰函數(shù)法；連續(xù)化

0-1線(xiàn)性規(guī)劃是整數(shù)規(guī)劃的一種特殊形式，是運(yùn)籌學(xué)中一個(gè)典型的組合優(yōu)化難題。0-1線(xiàn)性規(guī)劃在飛機(jī)排班、廠址選擇、人員安排、項(xiàng)目評(píng)價(jià)、資金分配等方面有著廣泛的應(yīng)用。研究0-1線(xiàn)性規(guī)劃問(wèn)題的求解方法具有很重要的理論意義和實(shí)用價(jià)值。

目前求解0-1線(xiàn)性規(guī)劃問(wèn)題的方法主要有分枝定界法、完全枚舉法、啟發(fā)式算法和連續(xù)化方法等。前兩種方法實(shí)質(zhì)是組合優(yōu)化方法，窮舉所有的可行解并選擇其中的最優(yōu)解，這類(lèi)方法隨著問(wèn)題規(guī)模的擴(kuò)大計(jì)算代價(jià)會(huì)增加，當(dāng)問(wèn)題規(guī)模很大時(shí)，可能出現(xiàn)無(wú)法求解的情況。啟發(fā)式算法是建立符合實(shí)際問(wèn)題的啟發(fā)式規(guī)則的搜索算法，如用0，1編碼表示的遺傳算法[1]，但是遺傳算法在如何處理約束的問(wèn)題上存在困難，大多數(shù)遺傳算法只是針對(duì)某一類(lèi)問(wèn)題的改進(jìn)，沒(méi)有通用和完善的計(jì)算機(jī)程序。連續(xù)化方法是將原問(wèn)題轉(zhuǎn)化為關(guān)于連續(xù)變量的規(guī)劃問(wèn)題后求解。0-1離散模型屬于組合優(yōu)化問(wèn)題，當(dāng)問(wèn)題規(guī)模很大時(shí)，面臨組合爆炸的難題，連續(xù)化方法可以避開(kāi)組合優(yōu)化的問(wèn)題，不受求解問(wèn)題規(guī)模大小的限制。隋允康[2]等人將0-1離散規(guī)劃通過(guò)一個(gè)非線(xiàn)性等式約束表示為[0，1]區(qū)間上等價(jià)的連續(xù)變量非線(xiàn)性規(guī)劃列式，使用乘子法、離散約束變換法處理后利用遺傳算法GENOCOP進(jìn)行求解。但是沒(méi)有考慮目標(biāo)函數(shù)中變量的系數(shù)對(duì)目標(biāo)函數(shù)值的影響，在有些情況下并不能有效的求得0，1最優(yōu)解或近似最優(yōu)解。李興斯[3]等人利用互補(bǔ)約束代替0-1條件，并利用凝聚函數(shù)法進(jìn)行光滑處理來(lái)求解0-1線(xiàn)性規(guī)劃問(wèn)題。但是該方法只適用于某一類(lèi)0-1線(xiàn)性規(guī)劃問(wèn)題，應(yīng)用上有局限性。

本文首先將0-1線(xiàn)性規(guī)劃問(wèn)題表示成一個(gè)[0，1]區(qū)間上的連續(xù)變量的非線(xiàn)性規(guī)劃問(wèn)題，在目標(biāo)函數(shù)中設(shè)計(jì)一個(gè)具有大M法功能的懲罰函數(shù)，將變量驅(qū)趕到使模型取得最優(yōu)值的0或1。然后采用Matlab的Fmincon函數(shù)求解模型的最優(yōu)解，最后對(duì)該規(guī)劃問(wèn)題求得的小數(shù)解，根據(jù)修正策略進(jìn)行合理的修正，最終得到原規(guī)劃問(wèn)題的0，1最優(yōu)解或近似最優(yōu)解。

1 問(wèn)題的提出

對(duì)于0-1線(xiàn)性規(guī)劃問(wèn)題P

一般連續(xù)化方法的做法是在目標(biāo)函數(shù)中加上一個(gè)關(guān)于對(duì)變量約束的函數(shù)，轉(zhuǎn)化為如下規(guī)劃問(wèn)題P1

此時(shí)目標(biāo)函數(shù)f（xs1）＞f（xs2），顯然，當(dāng)xs取1時(shí)，目標(biāo)函數(shù)值最優(yōu)，而乘子法在處理這類(lèi)規(guī)劃問(wèn)題時(shí)不能準(zhǔn)確地判斷變量的取值對(duì)目標(biāo)函數(shù)值的影響?；诔俗臃ǖ牟蛔?，本文提出一種懲罰函數(shù)法。

2 懲罰函數(shù)法

2.1 懲罰函數(shù)法的思想及連續(xù)化

懲罰函數(shù)法首先將0-1離散模型表示成連續(xù)變量的非線(xiàn)性規(guī)劃模型，然后求解該模型找到滿(mǎn)足約束、使目標(biāo)函數(shù)值最優(yōu)的0，1最優(yōu)解或近似最優(yōu)解。懲罰函數(shù)法的基本思想：當(dāng)求解目標(biāo)函數(shù)最小值時(shí)，在滿(mǎn)足約束的條件下，使用具有大M法功能的函數(shù)將對(duì)應(yīng)大于0的目標(biāo)函數(shù)系數(shù)的變量驅(qū)趕到0，對(duì)應(yīng)小于0的目標(biāo)函數(shù)系數(shù)的變量驅(qū)趕到1。利用這個(gè)思想，在原目標(biāo)函數(shù)中加上一個(gè)懲罰函數(shù)，進(jìn)而得到一個(gè)增廣的目標(biāo)函數(shù)，通過(guò)該懲罰函數(shù)值的變化控制變量的取值趨勢(shì)。

對(duì)于上述0-1線(xiàn)性規(guī)劃問(wèn)題P，在目標(biāo)函數(shù)中加上懲罰函數(shù)得到如下連續(xù)的非線(xiàn)性規(guī)劃問(wèn)題

2.2 懲罰函數(shù)的構(gòu)成

圖1 –ln（x）和sin（x）的圖像Fig.1Image of–ln（x）and sin（x）

3 連續(xù)化0 -1 非線(xiàn)性規(guī)劃問(wèn)題的求解

3.1 求解原理

本文采用Matlab的Fmincon函數(shù)求解連續(xù)化后的0-1非線(xiàn)性規(guī)劃問(wèn)題。函數(shù)的主要輸入?yún)?shù)有目標(biāo)函數(shù)表達(dá)式、初始值、約束矩陣等，主要輸出有規(guī)劃問(wèn)題的最優(yōu)解、目標(biāo)函數(shù)的最優(yōu)值和每次迭代過(guò)程的優(yōu)化信息等。對(duì)于不包含梯度信息的非線(xiàn)性規(guī)劃問(wèn)題，F(xiàn)mincon主要運(yùn)用了序列二次規(guī)劃算法、擬牛頓法和線(xiàn)性搜索法的結(jié)合求解問(wèn)題。序列二次規(guī)劃算法是將求解非線(xiàn)性約束優(yōu)化問(wèn)題轉(zhuǎn)化成求解一系列二次規(guī)劃子問(wèn)題來(lái)實(shí)現(xiàn)。在一次次迭代中，產(chǎn)生可行解的一個(gè)迭代序列，這個(gè)序列收斂得到問(wèn)題的解。設(shè)xk是當(dāng)前問(wèn)題的迭代點(diǎn)，則求搜索方向d的二次規(guī)劃子問(wèn)題的目標(biāo)函數(shù)為

3.2 解的修正策略

在求解某些規(guī)劃問(wèn)題時(shí)，可能出現(xiàn)小數(shù)解，需要修正。假設(shè)求得的解中變量xj為小數(shù)，判斷xj系數(shù)cj是否大于0，分為兩種情況：①當(dāng)cj>0時(shí)，根據(jù)以上分析，要使懲罰函數(shù)中F2=0，則因?yàn)?≤xj≤1，顯然，xj =0不能滿(mǎn)足約束條件。因此將xj修正為1。②當(dāng)cj＜0時(shí)，同理，xj=1使懲罰函數(shù)中F1=0。因?yàn)?≤xj≤1，顯然，xj=1不能滿(mǎn)足約束條件。因此將xj修正為0。

4 算例分析

為了驗(yàn)證本文提出方法的有效性，運(yùn)用懲罰函數(shù)法、乘子法和分枝定界法求解以下算例。其中乘子法為文獻(xiàn)[2]中的方法。分枝定界法采用Matlab的bintprog函數(shù)求解，函數(shù)的主要輸入和輸出與Fmincon函數(shù)類(lèi)似。

4.1 算例1

算例1的計(jì)算結(jié)果如表1所示。

表1 算例1的計(jì)算結(jié)果Tab.1Result of example 1

4.2 算例2

懲罰函數(shù)方法求解得（0.000 0，1.000 0，0.000 0，0.800 0，0.900 0，1.000 0，1.000 0），經(jīng)過(guò)修正策略得（0，1，0，1，1，1，1）。

算例2的計(jì)算結(jié)果如表2所示。

表2 算例2的計(jì)算結(jié)果Tab.2Result of example 2

4.3 算例3

算例3的計(jì)算結(jié)果如表3所示。

表3 算例3的計(jì)算結(jié)果Tab.3Result of example 3

算例1中目標(biāo)函數(shù)的系數(shù)為正，由計(jì)算結(jié)果看到，懲罰函數(shù)法和分枝定界計(jì)算結(jié)果相同，略?xún)?yōu)于乘子法。算例2和算例3中目標(biāo)函數(shù)的系數(shù)為負(fù)，計(jì)算結(jié)果表明，隨著變量個(gè)數(shù)的增多，懲罰函數(shù)的效果明顯比乘子法好。從整體上看，無(wú)論變量個(gè)數(shù)多少，目標(biāo)函數(shù)中變量系數(shù)的正負(fù)個(gè)數(shù)多少，懲罰函數(shù)法在求解0-1線(xiàn)性規(guī)劃問(wèn)題上具有一定的優(yōu)勢(shì)。

5 懲罰函數(shù)法在飛機(jī)排班問(wèn)題上的應(yīng)用

飛機(jī)排班是指為每個(gè)航班指定一架具體執(zhí)行的飛機(jī)。航班銜接條件[4]是指：①相鄰航班的機(jī)場(chǎng)、時(shí)間約束，即前一航班的到達(dá)機(jī)場(chǎng)和后一航班的出發(fā)機(jī)場(chǎng)必須相同，且有一定的時(shí)間間隔；②相鄰的兩個(gè)航班的前一個(gè)航班的到達(dá)時(shí)間和后一個(gè)航班的出發(fā)時(shí)間如果不在同一天，應(yīng)確定兩航班是否能夠過(guò)夜。航班環(huán)[5]是指由一架飛機(jī)連續(xù)執(zhí)行的飛機(jī)路線(xiàn)，即一組滿(mǎn)足航班銜接條件的航班組合，且首個(gè)航班的出發(fā)機(jī)場(chǎng)和終止航班的到達(dá)機(jī)場(chǎng)為維修基地。目前國(guó)內(nèi)飛機(jī)排班的流程分為兩步，第一步構(gòu)建航班環(huán)，第二步篩選航班環(huán)，為每架飛機(jī)安排實(shí)際運(yùn)營(yíng)路線(xiàn)。構(gòu)建航班環(huán)的主要方法有列生成法[5]、深度優(yōu)先搜索算法[6]等。

本文選取國(guó)內(nèi)某航空公司A320飛機(jī)一周執(zhí)行的航班，共100個(gè)，飛機(jī)共8架。考慮一種機(jī)型的飛機(jī)分配問(wèn)題。首先通過(guò)深度優(yōu)先搜索生成所有可行的一天航班環(huán)和任意相鄰的兩天航班環(huán)，共245個(gè)。其次考慮航班計(jì)劃、飛機(jī)數(shù)量限制等因素，建立篩選模型

式（1）中xj表示第j個(gè)航班環(huán)，即目標(biāo)函數(shù)是保證航班環(huán)的個(gè)數(shù)最少；約束條件（2）是航班覆蓋約束，即每個(gè)航班只能被一個(gè)航班環(huán)覆蓋，共有100個(gè)約束條件；約束條件（3）是飛機(jī)數(shù)量的約束，即執(zhí)行每天的航班環(huán)所需的飛機(jī)架數(shù)不能超過(guò)此機(jī)型當(dāng)天可用的飛機(jī)數(shù)量，Pw表示第w天的可用飛機(jī)數(shù)量，共有7個(gè)約束條件。

篩選航班環(huán)的目的是確定一個(gè)航班環(huán)是否被選擇，被選擇為1，不被選擇為0，實(shí)質(zhì)是0-1規(guī)劃問(wèn)題。上述模型有變量245個(gè)，等式約束100個(gè)，不等式約束7個(gè)，屬于大規(guī)模0-1線(xiàn)性規(guī)劃問(wèn)題，隨著航班量的增多，計(jì)算量呈指數(shù)增長(zhǎng)，求解難度加大。目前求解航班環(huán)篩選模型的算法有單純形法[4]、遺傳算法[5]等。使用遺傳算法時(shí)，由于等式約束的存在，在遺傳過(guò)程中不利于新個(gè)體的產(chǎn)生。單純形法對(duì)于解決大型規(guī)模的規(guī)劃問(wèn)題并沒(méi)有很好的效果。使用本文提出的方法對(duì)0-1篩選離散模型連續(xù)化得

xj∈{0，1}j=1，2，…，245

利用Matlab的Fmincon函數(shù)求解0-1非線(xiàn)性連續(xù)化模型。其中每個(gè)航班環(huán)是連續(xù)化模型中的一個(gè)變量。求解得滿(mǎn)足約束的最少航班環(huán)的個(gè)數(shù)為28個(gè)，即在245個(gè)變量中，28個(gè)變量的值為1，其余變量的值為0。篩選出的航班環(huán)能夠覆蓋一周所有航班且每個(gè)航班只被覆蓋一次。航班環(huán)的篩選結(jié)果如表4所示。

表4 航班環(huán)篩選結(jié)果Tab.4Result of optimization of flight-loop

6 結(jié)語(yǔ)

本文通過(guò)在目標(biāo)函數(shù)中增加一個(gè)懲罰函數(shù)的方法，將原0-1線(xiàn)性規(guī)劃問(wèn)題轉(zhuǎn)化為[0，1]區(qū)間上的連續(xù)變量非線(xiàn)性規(guī)劃問(wèn)題，并利用Matlab的Fmincon函數(shù)求解，對(duì)有些規(guī)劃問(wèn)題求得的小數(shù)解進(jìn)行合理的修正，最終得到滿(mǎn)足約束的0，1最優(yōu)解或近似最優(yōu)解。經(jīng)過(guò)多個(gè)算例的測(cè)試，結(jié)果表明該方法的可行性和有效性。通過(guò)將懲罰函數(shù)法用于飛機(jī)排班問(wèn)題上，并取得比較滿(mǎn)意的結(jié)果，表明該方法可以應(yīng)用于實(shí)際中0-1線(xiàn)性規(guī)劃問(wèn)題的計(jì)算。本文提出的方法不是局限于某一類(lèi)0-1線(xiàn)性規(guī)劃問(wèn)題，該方法的特點(diǎn)是對(duì)原目標(biāo)規(guī)劃處理簡(jiǎn)單，不需要復(fù)雜的特殊處理，求得的結(jié)果穩(wěn)定、有效，為求解大型規(guī)模的0-1線(xiàn)性規(guī)劃問(wèn)題開(kāi)拓一種新思路。根據(jù)懲罰函數(shù)法的思想可以將該方法應(yīng)用于求解0-1非線(xiàn)性整數(shù)規(guī)劃和0-1非線(xiàn)性混合整數(shù)規(guī)劃。由于本文的方法中懲罰函數(shù)是由ln（x）函數(shù)和sin（x）函數(shù)的組合構(gòu)成的，根據(jù)相關(guān)的數(shù)學(xué)知識(shí)推出，ln（1-x）的斜率比sin（x）的斜率大，更有利于懲罰函數(shù)有效判斷變量的取值趨勢(shì)，但是通過(guò)計(jì)算實(shí)際的算例，表明ln（1-x）并沒(méi)有sin（x）效果好，這也是下一步思考和研究的重點(diǎn)。

[1]李曉萌，戴光明，石紅玉.解決多維0/1背包問(wèn)題的遺傳算法綜述[J].電腦開(kāi)發(fā)與應(yīng)用，2006，19（1）：4-5.

[2]隋允康，賈志超.0-1線(xiàn)性規(guī)劃的連續(xù)化及其遺傳算法解法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2010，40（6）：119-127.

[3]李興斯，譚濤.求解二進(jìn)制二次規(guī)劃問(wèn)題的一種連續(xù)化方法[J].工程數(shù)學(xué)學(xué)報(bào)，2006，23（3）：500-504.

[4]沈中林，李延朵.遺傳算法在航班覆蓋問(wèn)題中的應(yīng)用研究[J].中國(guó)民航大學(xué)學(xué)報(bào)，2008，26（6）：5-9.

[5]肖東喜，朱金福.飛機(jī)排班中航班環(huán)的動(dòng)態(tài)構(gòu)建方法[J].系統(tǒng)工程，2007，25（11）：19-25.

[6]付維方，張偉剛，孫春林.航班排班中航班串生成與篩選問(wèn)題的算法與實(shí)現(xiàn)[J].中國(guó)民航學(xué)院學(xué)報(bào)，2006，24（5）：4-6.

（責(zé)任編輯：楊媛媛）

Continuous method for solving 0-1 linear programming

LIU Shan，ZHANG Lin-ling，HAO Li-dong，CAO Sheng-wen
（College of Computer Science and Technology，CAUC，Tianjin 300300，China）

To optimize the 0-1 linear programming，a method of penalty function is proposed.According to the features of the 0-1 linear programming optimal value，the penalty function is added with the target function and the 0-1 discrete model is changed into the continuous model which is nonlinear equally.The nonlinear model is solved by Fmincon function of Matlab.The results with example calculation and comparison with other algorithms show that this method is feasible and effective.This method is applied to the actual aircraft scheduling and the result is satisfying.

0-1 linear programming；a method of penalty function；continuous

F560

A

1674-5590（2013）03-0045-05

2012-06-15；

2012-09-06

國(guó)際合作與交流專(zhuān)項(xiàng)基金（2008DFA12300）

劉山（1955—），男，天津人，教授，學(xué)士，研究方向?yàn)閿?shù)據(jù)挖掘、計(jì)算機(jī)視頻.