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

1、 整數(shù)線性規(guī)劃理論§1 概論1.1 定義規(guī)劃中的變量（部分或全部）限制為整數(shù)時(shí)，稱為整數(shù)規(guī)劃。若在線性規(guī)劃模型中，變量限制為整數(shù)，則稱為整數(shù)線性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法，往往只適用于整數(shù)線性規(guī)劃。目前還沒有一種方法能有效地求解一切整數(shù)規(guī)劃。1.2 整數(shù)規(guī)劃的分類如不加特殊說明，一般指整數(shù)線性規(guī)劃。對(duì)于整數(shù)線性規(guī)劃模型大致可分為兩類：1o 變量全限制為整數(shù)時(shí)，稱純（完全）整數(shù)規(guī)劃。2o 變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。1.3 整數(shù)規(guī)劃特點(diǎn)（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í)數(shù)解為：。LINGO1.lg4 LINGO11.lg4有可行解（當(dāng)然就存在最優(yōu)解），但最優(yōu)解值變差。例2 原線性規(guī)劃為 其最優(yōu)實(shí)數(shù)解為：。若限制整數(shù)得：。LINGO2.lg4 LINGO21.lg4（ii） 整數(shù)規(guī)劃最優(yōu)解不能按照實(shí)數(shù)最優(yōu)解簡(jiǎn)單取整而獲得。1.4 求解方法分類：（i）分枝定界法可求純或混合整數(shù)線性規(guī)劃。（ii）割平面法可求純或混合整數(shù)線性規(guī)劃。（iii）隱枚舉法求解“0-1”整數(shù)規(guī)劃： 過濾隱枚舉法； 分枝隱枚舉法。（iv）匈牙利法解決指派問題（“0-1”規(guī)劃特殊情形）。（v）蒙特卡洛法求解各種類型規(guī)劃。下面將簡(jiǎn)要介紹常用的

3、幾種求解整數(shù)規(guī)劃的方法。§2 分枝定界法對(duì)有約束條件的最優(yōu)化問題（其可行解為有限數(shù)）的所有可行解空間恰當(dāng)?shù)剡M(jìn)行系統(tǒng)搜索，這就是分枝與定界內(nèi)容。通常，把全部可行解空間反復(fù)地分割為越來越小的子集，稱為分枝；并且對(duì)每個(gè)子集內(nèi)的解集計(jì)算一個(gè)目標(biāo)下界（對(duì)于最小值問題），這稱為定界。在每次分枝后，凡是界限超出已知可行解集目標(biāo)值的那些子集不再進(jìn)一步分枝，這樣，許多子集可不予考慮，這稱剪枝。這就是分枝定界法的主要思路。分枝定界法可用于解純整數(shù)或混合的整數(shù)規(guī)劃問題。在本世紀(jì)六十年代初由Land Doig和Dakin等人提出的。由于這種方法靈活且便于用計(jì)算機(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ù)值將是的一個(gè)下界。分枝定界法就是將的可行域分成子區(qū)域的方法。逐步減小和增大，最終求到?，F(xiàn)用下例來說明：例3 求解下述整數(shù)規(guī)劃 解 （i）先不考慮整數(shù)限制，即解相應(yīng)的線性規(guī)劃，得最優(yōu)解為：可見它不符合整數(shù)條件。這時(shí)是問題的最優(yōu)目標(biāo)函數(shù)值的上界，記作。而顯然是問題的一個(gè)整數(shù)可行解，這時(shí)，是的一個(gè)下界，記作，即。（ii）因?yàn)楫?dāng)前均為非整數(shù)，故不滿足整數(shù)

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

6、則停止 （b）有最優(yōu)解，并符合問題的整數(shù)條件，的最優(yōu)解即為的最優(yōu)解，則停止。 （c）有最優(yōu)解，但不符合問題的整數(shù)條件，記它的目標(biāo)函數(shù)值為。（ii）用觀察法找問題的一個(gè)整數(shù)可行解，一般可取，試探，求得其目標(biāo)函數(shù)值，并記作。以表示問題的最優(yōu)目標(biāo)函數(shù)值；這時(shí)有 進(jìn)行迭代。第一步：分枝，在的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量，其值為，以表示小于的最大整數(shù)。構(gòu)造兩個(gè)約束條件 和 將這兩個(gè)約束條件，分別加入問題，求兩個(gè)后繼規(guī)劃問題和。不考慮整數(shù)條件求解這兩個(gè)后繼問題。 定界，以每個(gè)后繼問題為一分枝標(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ī)劃中的特殊情形，它的變量?jī)H取值0或1。這時(shí)稱為變量，或稱二進(jìn)制變量。僅取值0或1這個(gè)條件可由下述約束條件： ，整數(shù)所代替，是和一般整數(shù)規(guī)劃的約束條件形式一致的。在實(shí)際問題中，如果引入 變量，就可以把有各種情況需要分別討論的線性規(guī)劃問題統(tǒng)一在一個(gè)問題中討論了。我們先介紹引入變量的實(shí)際問題，再研究解法。3.1 引入變量的實(shí)際問題 3.1.1 投資場(chǎng)所的選

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

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

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

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

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

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