基于數論的純整數規劃問題的解法研究

周 斌

（三明醫學科技職業學院，福建三明 365001）

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

1 相關理論概述

1.1 純整數規劃問題算法思路

1.1.1 一般純整數規劃問題 一般純整數規劃問題的模型〔10〕為

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

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

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

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

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

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

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

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

2 實例驗證

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

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

2.1 割平面法

（1）求解松弛問題

表1 迭代單純形表

表2 迭代后的單純形表

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

（2）求解割平面方程

2.2 分枝定界法

（1）求解松弛問題

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

（2）分枝

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

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

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

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

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

圖3 新解法計算流程圖

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

3 結語

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