周 斌

（三明醫(yī)學科技職業(yè)學院，福建三明 365001）

整數(shù)規(guī)劃（integer programming，IP）問題是一類要求問題的解中一部分或全部變量為整數(shù)的規(guī)劃問題，是1958 年戈莫里提出割平面法后形成的獨立分支〔1〕。整數(shù)規(guī)劃問題是要求決策變量取整數(shù)值的線性規(guī)劃（linear programing，LP）或非線性規(guī)劃（nonlinear programming，NP）問題〔2〕。而純整數(shù)規(guī)劃（pure integer programming，PIP）問題作為整數(shù)規(guī)劃問題的一種特殊形式，目前求此類規(guī)劃問題比較成功又流行的方法是分枝定界法和割平面法〔3〕。分枝定界法的主要思路〔3〕是首先求解整數(shù)規(guī)劃的伴隨規(guī)劃，通過添加約束的方法縮小可行域，使最優(yōu)解符合整數(shù)條件〔4〕。割平面法有許多種類型，但思路基本相同，也是用增加新的約束條件來切割可行域，增加的新約束條件稱為割平面方程，通過不斷地切割縮小過程，最終得到整數(shù)最優(yōu)解〔5〕。分枝定界法屬于一種隱枚舉法，對于自變量較多的情況，會存在“組合爆炸”的問題，難以適用〔6〕；而割平面法往往存在收斂速度很慢，甚至不收斂的問題〔7〕。此外，近年來還出現(xiàn)了許多智能算法，但智能算法往往無法保證它的收斂性，例如代數(shù)式恒等變形、不等式估算法、同余法、構(gòu)造法、無窮遞推法等〔8-9〕。然而這些運算方法均比較復雜，收斂速度比較慢。針對這個問題，利用不定方程與最優(yōu)化模型的一些共性，根據(jù)解不定方程問題的不等式估算法，提出一種高效的純整數(shù)規(guī)劃問題的新解法。這種新解法與傳統(tǒng)的純整數(shù)規(guī)劃問題的解法最大的不同點在于它不需要求解原規(guī)劃問題所伴隨的松弛線性規(guī)劃問題，而僅需要進行一些簡單的求解方程和代數(shù)運算。以純整數(shù)規(guī)劃問題為例子，分別用割平面法、分枝定界法和提出的新解法進行求解，驗證本文提出新解法的可行性。

1 相關(guān)理論概述

1.1 純整數(shù)規(guī)劃問題算法思路

1.1.1 一般純整數(shù)規(guī)劃問題 一般純整數(shù)規(guī)劃問題的模型〔10〕為

其中，A 是m 行n 列矩陣，其元素全為整數(shù)；b 為m維列向量，其元素全為整數(shù)；C 是n 維列向量，其元素全為整數(shù)；X 是n 維列向量，其元素為非負整數(shù)。1.1.2 二維變量的純整數(shù)規(guī)劃問題 二維變量的純整數(shù)規(guī)劃問題的模型〔11〕為

其中，a11，a12，a21，a22，b1，b2，c1，c2全為整數(shù)。由于約束條件的限制，可以得出約束變量x1，x2的上限，而根據(jù)x1，x2的非負要求，又可以得出x1，x2的下限，即x11≤x1≤x1s，x21≤x2≤x2r。根據(jù)整數(shù)限制又可以得到x1∈［x11，x1s］，x2∈［x21，x2r］。由此，可以得出函數(shù)f（x1，x2）的取值只能是某個范圍內(nèi)的整數(shù)，通過x1，x2的取值范圍，就可以確定f（x1，x2）的取值范圍為f∈［fmin，fmax］。因此，可以添加一個約束條件到原整數(shù)規(guī)劃問題中，從而縮小x 的可行域，減少計算量，以提高計算速度。則式（2）可轉(zhuǎn)化為如下等價形式：

這也就是把可行域縮小到了原可行域與平面f＝c1x1+c2x2的相交處，然后讓f 的值從fmax向fmin依次取整數(shù)，即從大到小開始取值。當?shù)竭_第一個f 的值所對應(yīng)的約束變量解組（x1i，x2j）（1≤i≤s，1≤j≤r）滿足約束條件時，此時的約束變量解組（x1i，x2j）即為此純整數(shù)規(guī)劃問題的最優(yōu)解組。而當所有的f 值所對應(yīng)的約束變量解組（x1i，x2j）（1≤i≤s，1≤j≤r）都不滿足約束條件時，則表示此純整數(shù)規(guī)劃問題無最優(yōu)解。

1.2 相關(guān)定理及推論采用數(shù)論的常用記號，記（c1，c2）為c1與c2的最大公約數(shù)，（c1，c2，…，cn）為c1，c2，…，cn的最大公約數(shù)。

證明：記d=（c1，c2，…，cn），d 為一個整數(shù)，

定理2 f＝c1x1+c2x2+…+cnxn有整數(shù)解的充分必要條件為（c1，c2，…，cn）｜f，即c1，c2，…，cn的最大公約數(shù)能整除f。

證明：若f＝c1x1+c2x2+…+cnxn有一整數(shù)解，設(shè)為x10，x20，…，xn0，則f=c1x10+c2x20+…+cnxn0，但（c1，c2，…，cn）整除c1，c2，…，cn，因而整除f，從而條件的必要性得證。反之，若（c1，c2，…，cn）｜f，則f＝k（c1，c2，…，cn），k為整數(shù)，則存在n 個整數(shù)s1，s2，…，sn滿足c1s1+c2s2+…+cnsn＝（c1，c2，…，cn）。令x10＝ks1，x20=ks2，…，xn0=ksn，即得c1x10+c2x20+…+cnxn0＝f，故f＝c1x1+c2x2+…+cnxn有整數(shù)解。

通過定理1 和定理2，就可以在不考慮x 的取值范圍時，使f＝c1x1+c2x2+…+cnxn總有整數(shù)解，而且可以有效地過濾掉明顯沒有意義的f 值。

2 實例驗證

在給出新解法的思路和步驟以及定理1、2 后，下面將用一些純整數(shù)規(guī)劃問題的具體算例來驗證此解法，并通過與分枝定界法和割平面法的對比，驗證此解法的優(yōu)缺點以及它的適用性?，F(xiàn)在對純整數(shù)規(guī)劃問題

分別用割平面法、分枝定界法和本文所提出的新解法來解決。

2.1 割平面法

（1）求解松弛問題

表1 迭代單純形表

表2 迭代后的單純形表

表3 再次迭代后的單純形表

（2）求解割平面方程

2.2 分枝定界法

（1）求解松弛問題

圖1 松弛問題式（4）的圖解法

（2）分枝

因為式（4）的最優(yōu)解x1，x2均非整數(shù)，取x1進行分枝，與最靠近的兩個整數(shù)為2 和3，故構(gòu)造兩個約束條件x1≤2 和x1≥3。分別并入式（4）中得

兩個子問題的可行域分別記為S1和S2，如圖2，S1US2包含了純整數(shù)規(guī)劃問題的全部整數(shù)解，點A被排除在外。

圖2 增加約束條件后的松弛問題圖解法

（3）求解兩個子問題的整數(shù)點，沒有必要再對式（5-2）進行分枝搜索。全部分枝都已查清，原純整數(shù)規(guī)劃問題的最優(yōu)解為點C，即X*＝（3，4）=18。

2.3 純整數(shù)規(guī)劃問題的新解法從約束條件可以得出x1與x2的取值范圍x1∈［0，1，2，3，4，5，6］，x2∈［0，1，2，3，4，5，6，7，8］，記f＝2x1+3x2，根據(jù)x1與x2的取值范圍，可以得出f 的取值范圍為f∈［0，1，2，…，36］。由于是問題，故由f 的值從大到小開始驗證，第一個滿足約束條件的最優(yōu)解組即為最優(yōu)解。新解法計算流程圖見圖3。

圖3 新解法計算流程圖

從圖3 得出，X*＝（3，4）即為最優(yōu)解，=18。從整個求解的過程來看，用割平面法和分枝定界法都需要解原純整數(shù)規(guī)劃問題的一些伴隨子規(guī)劃問題。而就這個問題而言，用割平面法比其他兩種方法要復雜得多，在求解子規(guī)劃問題的同時，割平面法需要求解平面S 的平面方程，而分枝定界法則需要求解平面S1和S2的平面方程。而本文所提出的這種方法不但不用求解伴隨的子規(guī)劃問題，運算過程也比其他兩種方法更簡單，計算量也更小，它只是求解一些方程，進行一些等式解的驗算。因而，在純整數(shù)規(guī)劃問題中，當維數(shù)不是很大或是f 的取值范圍不是很廣的情況下，本文所提出的方法所需要的計算量相比較而言要小得多，而且也比較簡單。在求解的過程中也不會出現(xiàn)一些傳統(tǒng)算法中必須解決的線性子規(guī)劃問題，只要求做一些簡單的方程求解與驗證。對于維數(shù)較大或是f 的取值范圍較廣的純整數(shù)規(guī)劃問題，這種算法也同樣適合，但也會像傳統(tǒng)的算法一樣，計算量大且煩瑣，要驗證的范圍會比較大。因此在做的過程中要求很細心，要考慮到每一個可能的取值和解組。

3 結(jié)語

區(qū)別于傳統(tǒng)的研究方法，從數(shù)論的角度來重新審視純整數(shù)規(guī)劃問題，利用數(shù)論中的不定方程理論，提出一種求解純整數(shù)規(guī)劃問題的新解法。此方法不但可以快速地發(fā)現(xiàn)并去掉沒有意義的f 值以及相對應(yīng)的最優(yōu)解組，而且還不用解決任何的伴隨線性子規(guī)劃問題。因而這種結(jié)合了數(shù)論和最優(yōu)化兩種學科的方法對解決純整數(shù)規(guī)劃問題不但快速而且簡單。在純整數(shù)規(guī)劃問題中，當f 的取值范圍非常廣或是維數(shù)很大的情況下，這種方法也可以用，但它更適用于一些f 的取值范圍不是非常大或是維數(shù)不是很大的純整數(shù)規(guī)劃問題。