0-1規(guī)劃的一種連續(xù)化和罰函數(shù)解法

祝麗華

(福建工程學(xué)院數(shù)理系，福建福州 350118)

0-1規(guī)劃的一種連續(xù)化和罰函數(shù)解法

祝麗華

(福建工程學(xué)院數(shù)理系，福建福州 350118)

針對0-1規(guī)劃問題變量的離散特點，提出一種連續(xù)化和罰函數(shù)解法。先通過一個非線性等式約束表示為［0，1］區(qū)間上等價的連續(xù)變量非線性規(guī)劃等式，再利用罰函數(shù)法將約束問題轉(zhuǎn)化為無約束問題求解。對多個算例進行計算，數(shù)值結(jié)果表明該方法是可行和有效的。

0-1規(guī)劃;連續(xù)化;約束非線性規(guī)劃;罰函數(shù)

0-1規(guī)劃問題是變量只取0或1的整數(shù)規(guī)劃問題的特殊情形，是運籌學(xué)中典型的組合優(yōu)化難題。在機械、化工、計算機、經(jīng)濟、生物、軍事、社會等各領(lǐng)域的許多優(yōu)化問題可以歸結(jié)為0-1規(guī)劃問題，如最常見的背包問題、分配問題和生產(chǎn)與存儲計劃問題等。因此構(gòu)造0-1規(guī)劃問題的求解方法是一個具有理論意義和實用價值的研究課題。

目前求解這類問題的經(jīng)典方法有分支定界法、割平面法和隱枚舉法等，除此之外人們已研究出一些啟發(fā)式算法，如貪婪算法，全局優(yōu)化方法如遺傳算法［1］、模擬退火算法［2］和蟻群算法［3］等?？紤]到該類問題中變量只能取0或1這兩個離散點，一般的連續(xù)算法不適用該類問題，許多學(xué)者應(yīng)用不同的連續(xù)化方法先將問題轉(zhuǎn)化為連續(xù)變量的規(guī)劃問題然后求解，最易想到的方法是直接將變量松弛為［0，1］區(qū)間上的連續(xù)變量，然后對連續(xù)解“舍入取整”。高峰等［4］提出針對一種整系數(shù)多項式0-1整數(shù)規(guī)劃問題，應(yīng)用罰函數(shù)將含等式和不等式的0-1多項式規(guī)劃連續(xù)化為無約束多項式規(guī)劃問題。Kiwie等［5］提出通過應(yīng)用求解凸規(guī)劃的Bregman臨近點算法來求解大規(guī)模0-1規(guī)劃問題。李艷艷等［6］利用拉格朗日松弛對偶將問題轉(zhuǎn)化為無約束問題，再應(yīng)用凝聚函數(shù)連續(xù)化對偶問題求解。隋允康［7］等人通過一個非線性等式約束，將0-1離散規(guī)劃表示為［0，1］區(qū)間上等價的連續(xù)變量非線性規(guī)劃，再使用乘子法、離散約束變換法處理非線性的等式約束后，利用遺傳算法GENOCOP進行求解，這些方法都是對0-1規(guī)劃問題求解的有益嘗試，但一般只適用于某一類0-1規(guī)劃問題，在應(yīng)用上有一定的局限性。

本文根據(jù)0-1規(guī)劃變量的離散特點，利用一個整數(shù)變量的非線性等式約束替換原變量的整數(shù)約束，從而將原離散的0-1規(guī)劃問題轉(zhuǎn)化為一個變量約束在［0，1］區(qū)間上的等價連續(xù)規(guī)劃問題，由于連續(xù)化后的問題是約束非線性問題，求解比較困難，本文利用罰函數(shù)［8］將約束吸收到目標函數(shù)，再應(yīng)用牛頓法求解。算例的數(shù)值結(jié)果表明該方法是有效的、可行的。

1 0-1規(guī)劃的連續(xù)化

考慮如下0-1規(guī)劃問題

其中x=(x1，x2，…，xn)，n決策變量個數(shù)，f(x)，gj(x)(j=1，2，…，m)目標分別為目標函數(shù)和約束函數(shù)，m為不等式約束數(shù)目。取文獻［7］中的參數(shù)αi=1(i=1，2，…，n)，上述問題可等價地表示為如下連續(xù)變量優(yōu)化問題

問題(1)和(2)的等價證明參見文獻［7］。

由于上述連續(xù)變量問題為約束優(yōu)化問題，沒有統(tǒng)一的較好的解法，而無約束問題中有很多經(jīng)典的并且收斂較好易于上機實現(xiàn)的算法，本文下面考慮應(yīng)用罰函數(shù)的特點將約束條件吸收到目標函數(shù)中，使約束問題變?yōu)闊o約束問題，再應(yīng)用牛頓法搜索最優(yōu)解。

為了方便應(yīng)用罰函數(shù)將問題(2)轉(zhuǎn)化為序列無約束問題，本文將問題(2)改寫成如下形式

2 連續(xù)化后0-1規(guī)劃的罰函數(shù)解法

2.1 罰函數(shù)法

罰函數(shù)法包括外點罰函數(shù)法、內(nèi)點罰函數(shù)法和混合罰函數(shù)法。罰函數(shù)法的基本思想是根據(jù)約束特點構(gòu)造某種罰函數(shù)，然后把它加到目標函數(shù)中，使得對約束最優(yōu)化問題的求解轉(zhuǎn)化為對一系列無約束問題，其極小點或者無限地向可行域靠近，或者一直保持在可行域內(nèi)移動，直到收斂于原來約束最優(yōu)化問題的極小點。外點罰函數(shù)法是通過一系列懲罰因子，求無約束增廣目標函數(shù)的極小點來逼近原約束問題的最優(yōu)點。隨著懲罰因子的不斷增大，迫使懲罰項的值不斷減小，從而使增廣目標函數(shù)的極小點沿著某一運動軌跡從原約束問題的可行域外逐漸逼近可行域內(nèi)的最優(yōu)點，當懲罰因子趨于無窮大時，無約束問題的極小點就是原約束問題的最優(yōu)點。內(nèi)點罰函數(shù)法通過構(gòu)造一個障礙函數(shù)轉(zhuǎn)化為無約束問題，由于障礙函數(shù)的作用使得當從原約束問題的可行域中某點出發(fā)，每次迭代過程均在可行域中進行，隨著障礙因子的不斷減小，使得無約束問題的極小點序列不斷逼近原約束問題的最優(yōu)解。由于外點罰函數(shù)法的初始點可以任選，適用于求解等式約束問題;而內(nèi)點罰函數(shù)法要求初始點在可行域內(nèi)，適用于求解不等式約束優(yōu)化問題。綜合考慮兩者的優(yōu)點，將兩種算法結(jié)合起來，形成了混合罰函數(shù)法。

上述連續(xù)化方法將0-1規(guī)劃問題轉(zhuǎn)化為一個在［0，1］區(qū)間上的非線性約束規(guī)劃問題。考慮到約束非線性問題求解的困難，本文利用罰函數(shù)將約束問題轉(zhuǎn)化為較好求解的無約束問題。又問題(3)帶有等式和不等式約束，本文采用混合罰函數(shù)法將兩種類型的約束吸收到目標函數(shù)中再應(yīng)用牛頓法求解序列的無約束問題。對于一般的約束優(yōu)化問題

本文采用如下內(nèi)點形式的混合罰函數(shù)

因此問題(3)轉(zhuǎn)化為如下無約束問題

2.2 混合罰函數(shù)算法

混合罰函數(shù)算法如下:

(1)選定初始點x0，要求滿足不等式約束，初始障礙因子r1，懲罰因子縮小系數(shù)c＜1，終止限ε=10－6，置k=1。

(2)假設(shè)已獲迭代點xk－1，以xk－1為初始點，求解minF(x，rk)，設(shè)其最優(yōu)解為x(rk)。

(3)若xk－xk－1≤ε，則x(rk)是問題(1)的最優(yōu)解，打印x(rk)，f(x(rk))，否則轉(zhuǎn)(4)。

(4)rk+1=crk，k=k+1，轉(zhuǎn)(2)。

3 數(shù)值算例

算例1

表1 算例1的計算結(jié)果及精確解

算例2

表2 算例2的計算結(jié)果及精確解

分析表1和表2可知，無論目標函數(shù)是線性還是非線性函數(shù)，應(yīng)用本文提出的方法都搜索到了較好的近似解，說明該方法是可行和有效的，為求解0-1規(guī)劃問題提供了一個新途徑。

4 罰函數(shù)法在指派問題上的應(yīng)用

實際中會遇到這樣的問題，有n項不同的任務(wù)，需要n個人分別完成其中的1項，每個人完成的時間不一樣，因此應(yīng)指派哪個人去完成哪項任務(wù)，使完成n項任務(wù)花費總時間最小的問題稱作指派問題。

現(xiàn)假設(shè)指派4個人完成4項工作，每人完成每項工作所需時間如表3

表3 工作所需時間表

其中Ai(i=1，2，…，4)表示工人，Bj(j=1，2，…，4)表示工作。

該指派問題可設(shè)變量

因此可建立如下0-1規(guī)劃模型，計算結(jié)果見表4。

表4 指派問題計算結(jié)果及精確解

分析表4可知當A1完成B1工作，A2完成B3工作，A3完成B4工作及A4完成B2工作時花費總時間最小為10.066 1，與精確值的誤差僅為0.06，說明了本文方法的有效性。

5 結(jié)論

本文應(yīng)用一個非線性等式約束將0-1規(guī)劃問題等價表示為［0，1］區(qū)間上的連續(xù)變量優(yōu)化問題，再利用混合罰函數(shù)法將帶有非線性約束的連續(xù)問題轉(zhuǎn)化為求解一序列無約束問題，應(yīng)用無約束方法中經(jīng)典的牛頓法求解原問題的近似最優(yōu)解。數(shù)值結(jié)果表明本文提出的方法對目標函數(shù)為線性或非線性的情況下都是有效可行的。由于牛頓法對初始點的選取要求比較苛刻以及當障礙因子越來越來小導(dǎo)致Hesse矩陣的病態(tài)，從而不能構(gòu)造Newton方向使迭代無法進行，這兩個問題將影響到最后解的質(zhì)量。因此如何提高此類方法解的精確性是今后繼續(xù)研究的一個方向。

［1］李曉萌，戴光明，石紅玉.解決多維0/1背包問題的遺傳算法綜述［J］.電腦開發(fā)與應(yīng)用，2006，19(1):4-5，8.

［2］梁國宏，張 生，黃 輝，等.一種改進的模擬退火算法求解0-1背包問題［J］.廣西民族大學(xué)學(xué)報(自然科學(xué)版)，2007，13(3):91-93.

［3］田烽楠，王 于.求解0-1背包問題算法綜述［J］.軟件導(dǎo)刊，2009，8(1):59-61.

［4］高 峰，張連生.多項式0-1整規(guī)劃的兩個連續(xù)化途徑［J］.上海大學(xué)學(xué)報(自然科學(xué)版)，1999，5(2):95-98.

［5］Kiwiel K C，Lindberg P O，Nou A.Bregman proximal relaxation of large-scale 0-1 problems［J］.Computational Optimization and Applications，2000，15(1):33-44.

［6］李艷艷，李興斯.求解線性0-1規(guī)劃的一種連續(xù)化方法［J］.大連理工大學(xué)學(xué)報，2009，49(2):299-302.

［7］隋允康，賈志超.0-1線性規(guī)劃的連續(xù)化及其遺傳算法解法［J］.數(shù)學(xué)的實踐與認識，2010，40(6):119-127.

［8］郭 科，陳 聆，魏友華.最優(yōu)化方法及其應(yīng)用［M］.北京:高等教育出版社，2007:120-130.

A continuous approach to 0-1 program and its solution with penalty function algorithm

ZHU Li-hua
(Mathematics and Physics Department，F(xiàn)ujian University of Technology，F(xiàn)uzhou350118，China)

To optimize the 0-1 programming，a method of penalty function is proposed，according to the feature of discrete variables.In this paper，a 0-1 discrete programming problem is converted to an equivalent continuous nonlinear programming formulation on the domain of［0，1］by a nonlinear equality constraint，then the constraint nonlinear problem is transformed into unconstraint nonlinear problem by means of penalty function.Two examples are presented and the numerical results show that the approach is affective and accurate.

0-1 programming;continuous;constraint nonlinear programming;penalty function

O221.4

：A

：1004-4329(2015)01-020-04

2014-09-22

福建工程學(xué)院青年基金(GY-Z13009)資助。

祝麗華(1979－)，女，講師。主要研究方向：最優(yōu)化、數(shù)學(xué)規(guī)劃。