整數(shù)線性規(guī)劃理論

1、 整數(shù)線性規(guī)劃理論§1 概論1.1 定義規(guī)劃中的變量（部分或全部）限制為整數(shù)時，稱為整數(shù)規(guī)劃。若在線性規(guī)劃模型中，變量限制為整數(shù)，則稱為整數(shù)線性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法，往往只適用于整數(shù)線性規(guī)劃。目前還沒有一種方法能有效地求解一切整數(shù)規(guī)劃。1.2 整數(shù)規(guī)劃的分類如不加特殊說明，一般指整數(shù)線性規(guī)劃。對于整數(shù)線性規(guī)劃模型大致可分為兩類：1o 變量全限制為整數(shù)時，稱純（完全）整數(shù)規(guī)劃。2o 變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。1.3 整數(shù)規(guī)劃特點（i） 原線性規(guī)劃有最優(yōu)解，當(dāng)自變量限制為整數(shù)后，其整數(shù)規(guī)劃解出現(xiàn)下述情況：原線性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)

2、解一致。整數(shù)規(guī)劃無可行解。例1 原線性規(guī)劃為 其最優(yōu)實數(shù)解為：。LINGO1.lg4 LINGO11.lg4有可行解（當(dāng)然就存在最優(yōu)解），但最優(yōu)解值變差。例2 原線性規(guī)劃為 其最優(yōu)實數(shù)解為：。若限制整數(shù)得：。LINGO2.lg4 LINGO21.lg4（ii） 整數(shù)規(guī)劃最優(yōu)解不能按照實數(shù)最優(yōu)解簡單取整而獲得。1.4 求解方法分類：（i）分枝定界法可求純或混合整數(shù)線性規(guī)劃。（ii）割平面法可求純或混合整數(shù)線性規(guī)劃。（iii）隱枚舉法求解“0-1”整數(shù)規(guī)劃： 過濾隱枚舉法； 分枝隱枚舉法。（iv）匈牙利法解決指派問題（“0-1”規(guī)劃特殊情形）。（v）蒙特卡洛法求解各種類型規(guī)劃。下面將簡要介紹常用的

3、幾種求解整數(shù)規(guī)劃的方法。§2 分枝定界法對有約束條件的最優(yōu)化問題（其可行解為有限數(shù)）的所有可行解空間恰當(dāng)?shù)剡M(jìn)行系統(tǒng)搜索，這就是分枝與定界內(nèi)容。通常，把全部可行解空間反復(fù)地分割為越來越小的子集，稱為分枝；并且對每個子集內(nèi)的解集計算一個目標(biāo)下界（對于最小值問題），這稱為定界。在每次分枝后，凡是界限超出已知可行解集目標(biāo)值的那些子集不再進(jìn)一步分枝，這樣，許多子集可不予考慮，這稱剪枝。這就是分枝定界法的主要思路。分枝定界法可用于解純整數(shù)或混合的整數(shù)規(guī)劃問題。在本世紀(jì)六十年代初由Land Doig和Dakin等人提出的。由于這種方法靈活且便于用計算機(jī)求解，所以現(xiàn)在它已是解整數(shù)規(guī)劃的重要方法。目前

4、已成功地應(yīng)用于求解生產(chǎn)進(jìn)度問題、旅行推銷員問題、工廠選址問題、背包問題及分配問題等。設(shè)有最大化的整數(shù)規(guī)劃問題，與它相應(yīng)的線性規(guī)劃為問題，從解問題開始，若其最優(yōu)解不符合的整數(shù)條件，那么的最優(yōu)目標(biāo)函數(shù)必是的最優(yōu)目標(biāo)函數(shù)的上界，記作；而的任意可行解的目標(biāo)函數(shù)值將是的一個下界。分枝定界法就是將的可行域分成子區(qū)域的方法。逐步減小和增大，最終求到?，F(xiàn)用下例來說明：例3 求解下述整數(shù)規(guī)劃 解 （i）先不考慮整數(shù)限制，即解相應(yīng)的線性規(guī)劃，得最優(yōu)解為：可見它不符合整數(shù)條件。這時是問題的最優(yōu)目標(biāo)函數(shù)值的上界，記作。而顯然是問題的一個整數(shù)可行解，這時，是的一個下界，記作，即。（ii）因為當(dāng)前均為非整數(shù)，故不滿足整數(shù)

5、要求，任選一個進(jìn)行分枝。設(shè)選進(jìn)行分枝，把可行集分成2個子集：，因為4與5之間無整數(shù)，故這兩個子集的整數(shù)解必與原可行集合整數(shù)解一致。這一步稱為分枝。這兩個子集的規(guī)劃及求解如下：問題： 最優(yōu)解為：。問題： 最優(yōu)解為：。再定界：。（iii）對問題再進(jìn)行分枝得問題和，它們的最優(yōu)解為再定界：，并將剪枝。（iv）對問題再進(jìn)行分枝得問題和，它們的最優(yōu)解為無可行解。將剪枝。于是可以斷定原問題的最優(yōu)解為：從以上解題過程可得用分枝定界法求解整數(shù)規(guī)劃（最大化）問題的步驟為：開始，將要求解的整數(shù)規(guī)劃問題稱為問題，將與它相應(yīng)的線性規(guī)劃問題稱為問題。（i）解問題可能得到以下情況之一： （a）沒有可行解，這時也沒有可行解，

6、則停止 （b）有最優(yōu)解，并符合問題的整數(shù)條件，的最優(yōu)解即為的最優(yōu)解，則停止。 （c）有最優(yōu)解，但不符合問題的整數(shù)條件，記它的目標(biāo)函數(shù)值為。（ii）用觀察法找問題的一個整數(shù)可行解，一般可取，試探，求得其目標(biāo)函數(shù)值，并記作。以表示問題的最優(yōu)目標(biāo)函數(shù)值；這時有 進(jìn)行迭代。第一步：分枝，在的最優(yōu)解中任選一個不符合整數(shù)條件的變量，其值為，以表示小于的最大整數(shù)。構(gòu)造兩個約束條件 和 將這兩個約束條件，分別加入問題，求兩個后繼規(guī)劃問題和。不考慮整數(shù)條件求解這兩個后繼問題。 定界，以每個后繼問題為一分枝標(biāo)明求解的結(jié)果，與其它問題的解的結(jié)果中，找出最優(yōu)目標(biāo)函數(shù)值最大者作為新的上界。從已符合整數(shù)條件的各分支中，找

7、出目標(biāo)函數(shù)值為最大者作為新的下界，若無作用。第二步：比較與剪枝，各分枝的最優(yōu)目標(biāo)函數(shù)中若有小于者，則剪掉這枝，即以后不再考慮了。若大于，且不符合整數(shù)條件，則重復(fù)第一步驟。一直到最后得到為止。得最優(yōu)整數(shù)解。§3 型整數(shù)規(guī)劃型整數(shù)規(guī)劃是整數(shù)規(guī)劃中的特殊情形，它的變量僅取值0或1。這時稱為變量，或稱二進(jìn)制變量。僅取值0或1這個條件可由下述約束條件： ，整數(shù)所代替，是和一般整數(shù)規(guī)劃的約束條件形式一致的。在實際問題中，如果引入 變量，就可以把有各種情況需要分別討論的線性規(guī)劃問題統(tǒng)一在一個問題中討論了。我們先介紹引入變量的實際問題，再研究解法。3.1 引入變量的實際問題 3.1.1 投資場所的選

8、定相互排斥的計劃 例4 某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個位置（點）可供選擇。規(guī)定 在東區(qū)。由三個點中至多選兩個； 在西區(qū)。由兩個點中至少選一個；在南區(qū)，由兩個點中至少選一個。 如選用點，設(shè)備投資估計為元，每年可獲利潤估計為元，但投資總額不能超過元。問應(yīng)選擇哪幾個點可使年利潤為最大？解題時先引入變量令 .于是問題可列寫成： 3.1.2 相互排斥的約束條件有兩個相互排斥的約束條件 或 。為了統(tǒng)一在一個問題中，引入變量，則上述約束條件可改寫為： 其中是充分大的數(shù)。約束條件 或 可改寫為如果有個互相排斥的約束條件：為了保證這個約束條件只有一個起作用，我們引入個變量和一個充分大的常數(shù)，

9、而下面這一組個約束條件 （1） （2）就合于上述的要求。這是因為，由于（2），個中只有一個能取0值，設(shè)，代入（1），就只有的約束條件起作用，而別的式子都是多余的。3.1.3 關(guān)于固定費用的問題（Fixed Cost Problem）在討論線性規(guī)劃時，有些問題是要求使成本為最小。那時總設(shè)固定成本為常數(shù)，并在線性規(guī)劃的模型中不必明顯列出。但有些固定費用（固定成本）的問題不能用一般線性規(guī)劃來描述，但可改變?yōu)榛旌险麛?shù)規(guī)劃來解決，見下例。例5 某工廠為了生產(chǎn)某種產(chǎn)品，有幾種不同的生產(chǎn)方式可供選擇，如選定的生產(chǎn)方式投資高（選購自動化程度高的設(shè)備），由于產(chǎn)量大，因而分配到每件產(chǎn)品的變動成本就降低；反之，如選

10、定的生產(chǎn)方式投資低，將來分配到每件產(chǎn)品的變動成本可能增加。所以必須全面考慮。今設(shè)有三種方式可供選擇，令表示采用第種方式時的產(chǎn)量；表示采用第種方式時每件產(chǎn)品的變動成本；表示采用第種方式時的固定成本。為了說明成本的特點，暫不考慮其它約束條件。采用各種生產(chǎn)方式的總成本分別為 . 在構(gòu)成目標(biāo)函數(shù)時，為了統(tǒng)一在一個問題中討論，現(xiàn)引入變量，令 （3）于是目標(biāo)函數(shù) （3）式這個規(guī)定可表為下述3個線性約束條件： （4）其中是個充分大的常數(shù)。（4）式說明，當(dāng)時必須為1；當(dāng)時只有為0時才有意義，所以（4）式完全可以代替（3）式。3.2 型整數(shù)規(guī)劃解法之一（過濾隱枚舉法）解型整數(shù)規(guī)劃最容易想到的方法，和一般整數(shù)規(guī)劃

11、的情形一樣，就是窮舉法，即檢查變量取值為0或1的每一種組合，比較目標(biāo)函數(shù)值以求得最優(yōu)解，這就需要檢查變量取值的個組合。對于變量個數(shù)較大（例如），這幾乎是不可能的。因此常設(shè)計一些方法，只檢查變量取值的組合的一部分，就能求到問題的最優(yōu)解。這樣的方法稱為隱枚舉法（Implicit Enumeration），分枝定界法也是一種隱枚舉法。當(dāng)然，對有些問題隱枚舉法并不適用，所以有時窮舉法還是必要的。下面舉例說明一種解型整數(shù)規(guī)劃的隱枚舉法。 例6 求解思路及改進(jìn)措施：（i） 先試探性求一個可行解，易看出滿足約束條件，故為一個可行解，且。（ii） 因為是求極大值問題，故求最優(yōu)解時，凡是目標(biāo)值的解不必檢驗是否滿

12、足約束條件即可刪除，因它肯定不是最優(yōu)解，于是應(yīng)增加一個約束條件（目標(biāo)值下界）：（iii） 改進(jìn)過濾條件。（iv） 由于對每個組合首先計算目標(biāo)值以驗證過濾條件，故應(yīng)優(yōu)先計算目標(biāo)值大的組合，這樣可提前抬高過濾門檻，以減少計算量。§4 蒙特卡洛法（隨機(jī)取樣法）前面介紹的常用的整數(shù)規(guī)劃求解方法，主要是針對線性整數(shù)規(guī)劃而言，而對于非線性整數(shù)規(guī)劃目前尚未有一種成熟而準(zhǔn)確的求解方法，因為非線性規(guī)劃本身的通用有效解法尚未找到，更何況是非線性整數(shù)規(guī)劃。然而，盡管整數(shù)規(guī)劃由于限制變量為整數(shù)而增加了難度；然而又由于整數(shù)解是有限個，于是為枚舉法提供了方便。當(dāng)然，當(dāng)自變量維數(shù)很大和取值范圍很寬情況下，企圖用顯

13、枚舉法（即窮舉法）計算出最優(yōu)值是不現(xiàn)實的，但是應(yīng)用概率理論可以證明，在一定的計算量的情況下，完全可以得出一個滿意解。例7 已知非線性整數(shù)規(guī)劃為：對該題，目前尚無有效方法求出準(zhǔn)確解。如果用顯枚舉法試探，共需計算個點，其計算量非常之大。然而應(yīng)用蒙特卡洛去隨機(jī)計算個點，便可找到滿意解，那么這種方法的可信度究竟怎樣呢？下面就分析隨機(jī)取樣采集個點計算時，應(yīng)用概率理論來估計一下可信度。不失一般性，假定一個整數(shù)規(guī)劃的最優(yōu)點不是孤立的奇點。假設(shè)目標(biāo)函數(shù)落在高值區(qū)的概率分別為0.01，0.00001，則當(dāng)計算個點后，有任一個點能落在高值區(qū)的概率分別為，析：。解 （i）首先編寫M文件mente.m定義目標(biāo)函數(shù)f

14、和約束向量函數(shù)g，程序如下：function f,g=mengte(x);f=x(1)2+x(2)2+3*x(3)2+4*x(4)2+2*x(5)-8*x(1)-2*x(2)-3*x(3). -x(4)-2*x(5);g(1)=sum(x)-400;g(2)=x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800;g(3)=2*x(1)+x(2)+6*x(3)-200;g(4)=x(3)+x(4)+5*x(5)-200;（ii）編寫如下程序求問題的解：rand('state',sum(clock);p0=0;ticfor i=1:105 x=99*rand(5,1);x1=floor(x);x2=ceil(x);f,g=mengte(x1);if sum(g<=0)=4 if p0<=f x0=x1;p0=f; endendf,g=mengte(x2);if sum(g<=0)=4 if p