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

整數(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ī)劃模型大致可分為兩類：1。變量全限制為整數(shù)時，稱純(完全)整數(shù)規(guī)劃。2。變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。1.3整數(shù)規(guī)劃特點原線性規(guī)心有最優(yōu)解，當自變量限制為整數(shù)后，其整數(shù)規(guī)劃解出現(xiàn)下述情況：原線性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。整數(shù)規(guī)劃無可行解。例1原線性規(guī)劃為niiiiz=xt+x22xk+4X2=5,X>0,X2>。其最優(yōu)實數(shù)解為：不二0內(nèi)二言寸皿#。LINGOl.lg4LINGOll.lg4有可行解(當然就存在最優(yōu)解)，但最優(yōu)解值變差。例2原線性規(guī)劃為ninz=xL+x22Xl+4x,=6,xY>0,x2>0其最優(yōu)實數(shù)解為：X,=0,a=￡,minz=￡。若限制整數(shù)得：^=i,a=1,1111112=20LINGO2.1g4LINGO21.1g4整數(shù)規(guī)劃最優(yōu)解殛按照實數(shù)最優(yōu)解簡單取整而獲得。1.4求解方法分類：(1)分枝定界法一可求純或混合整數(shù)線性規(guī)劃。割平面法一可求純或混合整數(shù)線性規(guī)劃。隱枚舉法一求解整數(shù)規(guī)劃：過濾隱枚舉法；分枝隱枚舉法。匈牙利法一解決指派問題("0-1"規(guī)劃特殊情形)。蒙特卡洛法一求解各種類型規(guī)劃。下面將簡要介紹常用的幾種求解整數(shù)規(guī)劃的方法。§2分枝定界法對有約束條件的最優(yōu)化問題(其可行解為有限數(shù))的所有可行解空間恰當?shù)剡M行系統(tǒng)搜索，這就是分枝與定界內(nèi)容。通常，把全部可行解空間反復地分割為越來越小的子集，稱為分枝；并且對每個子集內(nèi)的解集計算一個目標下界（對于最小值問題），這稱為定界。在每次分枝后，凡是界限超出已知可行解集目標值的那些子集不再進一步分枝，這樣，許多子集可不予考慮，這稱剪枝。這就是分枝定界法的主要思路。分枝定界法可用于解純整數(shù)或混合的整數(shù)規(guī)劃問題。在本世紀六十年代初由LandDoig和Dakin等人提出的。由于這種方法靈活且便于用計算機求解，所以現(xiàn)在它已是解整數(shù)規(guī)劃的重要方法。目前已成功地應用于求解生產(chǎn)進度問題、旅行推銷員問題、工廠選址問題、背包問題及分配問題等。設有最大化的整數(shù)規(guī)劃問題4,與它相應的線性規(guī)劃為問題B,從解問題B開始，若其最優(yōu)解不符合A的整數(shù)條件，那么B的最優(yōu)目標函數(shù)必是A的最優(yōu)目標函數(shù)/的上界，記作而A的任意可行解的目標函數(shù)值將是/的一個下界1分枝定界法就是將B的可行域分成子區(qū)域的方法。逐步減小Z和增大2,最終求到現(xiàn)用下例來說明：例3求解下述整數(shù)規(guī)劃Maxz=40-+90X2+lx2<567兀+20x2<70>0且為整數(shù)解（i）先不考慮整數(shù)限制，即解相應的線性規(guī)劃B,得最優(yōu)解為：兀=4.8092,x2=1.8168,z=355.8779可見它不符合整數(shù)條件。這時Z是問題A的最優(yōu)目標函數(shù)值正的上界，記作Z。而x1_0,x2=0顯然是問題4的一個整數(shù)可行解，這時“（是/的一個下界，記作即0<f<356o（ii）因為再忑當前均為非整數(shù)，故不滿足整數(shù)要求，任選一個進行分枝。設選人進行分枝，把可行集分成2個子集：<[4.8092]=4,人>[4.8092]+1=5因為4與5之間無整數(shù)，故這兩個子集的整數(shù)解必與原可行集合整數(shù)解一致。這一步稱為分枝。這兩個子集的規(guī)劃及求解如下：問題B]:Maxz=40Xj+909兀+弗2<56<+2Ox,<700<A<4,X2>0最優(yōu)解為：=4.0,x2=2.1,%=349o問題B2:Maxz=40召+909兀+弗2<567x{+2Ox,<70xl>5必2>0最優(yōu)解為：x1=5.0,x2=1.57,a=341.4o再定界：0"乜349。對問題色再進行分枝得問題乞和％，它們的最優(yōu)解為=4、兀,=2,Z］］=340B「：=1.43,Xr=3.00，s=327.14再定界：340<f<341，并將久剪枝。對問題禺再進行分枝得問題％和坊2,它們的最優(yōu)解為B21:x=5.44,x2=1.00,z22=308呢無可行解。將久幾剪枝。于是可以斷定原問題的最優(yōu)解為：兀=4,x,=2,z=340從以上解題過程可得用分枝定界法求解整數(shù)規(guī)劃(最大化)問題的步驟為：開始，將要求解的整數(shù)規(guī)劃問題稱為問題A，將與它相應的線性規(guī)劃問題稱為問題Bo⑴解問題3可能得到以下情況之一：3沒有可行解，這時4也沒有可行解，則停止.B有最優(yōu)解，并符合問題A的整數(shù)條件，B的最優(yōu)解即為A的最優(yōu)解，則停止。B有最優(yōu)解，但不符合問題4的整數(shù)條件，記它的目標函數(shù)值為Z。(ii)用觀察法找問題A的一個整數(shù)可行解，一般可取Xj=0J=t，試探，求得其目標函數(shù)值，并記作&。以/表示問題A的最優(yōu)目標函數(shù)值；這時有z<z<z進行迭代。第一步：分枝，在B的最優(yōu)解中任選一個不符合整數(shù)條件的變量廠，其值為S，以也］表示小于乞的最大整數(shù)。構(gòu)造兩個約束條件?<［巧］和將這兩個約束條件，分別加入問題B,求兩個后繼規(guī)劃問題d和5。不考慮整數(shù)條件求解這兩個后繼問題。定界，以每個后繼問題為一分枝標明求解的結(jié)果，與其它問題的解的結(jié)果中，找出最優(yōu)目標函數(shù)值最大者作為新的上界Z。從已符合整數(shù)條件的各分支中，找出目標函數(shù)值為最大者作為新的下界Z，若無作用2=0。第二步：比較與剪枝，窘分枝的最優(yōu)目標函數(shù)中若有小于2者，則剪掉這枝，即以后不再考慮了。若大于3且不符合整數(shù)條件，則重復第一步驟一直到最后得到為止。得最優(yōu)整數(shù)解X；,j=i-,no§30-1型整數(shù)規(guī)劃0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃中的特殊情形，它的變量廠僅取值0或1。這時廠稱為0-1變量，或稱二進制變量。巧僅取值O或1這個條件可由下述約束條件：0<x.<1,整數(shù)所代替，是和一般整數(shù)規(guī)劃的約束條件形式一致的。在實際問題中，如果引入0-1變量，就可以把有各種情況需要分別討論的線性規(guī)劃問題統(tǒng)一在一個問題中討論了。我們先介紹引入0-1變量的實際問題，再研究解法。3.1引入0-1變量的實際問題3.1.1投資場所的選定一一相互排斥的計劃例4某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個位置(點)4(心1,2,...,7)可供選擇。規(guī)定在東區(qū)。由人三個點中至多選兩個；在西區(qū)。由人'人兩個點中至少選一個；在南區(qū)，由人，人兩個點中至少選一個。如選用人點，設備投資估計為勺元，每年可獲利潤估計為q元，但投資總額不能超過3元。問應選擇哪幾個點可使年利潤為最大？解題時先引入0-1變量兀(i=1,2,...,7)令當州點被選中，.=[0,當令點沒被選中.(=12...,7.于是問題可列寫成：Maxz二工侖兀/=10內(nèi)<B1=1?xY+x2+X3<2X4+x5>lX6+X7>1，Xf=0或13.1.2相互排斥的約束條件有兩個相互排斥的約束條件5召+4X2<24或7X[+3X2<45o為了統(tǒng)一止一個問題中，弓IAO-1變量y,則上述約束條件可改寫為：5xy+4x2<24+yM<7xx+3x2<45+(1-y)My=0或1其中M是充分大的數(shù)。約束條件jq=0或500<A<800可改寫為500y<xx<800y\=0或1

如果有加個互相排斥的約束條件：*5〃i=1,2,…，加為了保證這加個約束條件只有一個起作用，我們引入加個0-1變量）刃二1,2,…沖）和一個充分大的常數(shù)M,而下面這一組加+1個約束條件4內(nèi)+???+amxn-?+yMi=1,2,...，加（1）弘+???+兒“-1（2）就合于上述的要求。這是因為，由于（2），加個％中只有一個能取0值，設片二。，代入（1）,就只有，二廠的約束條件起作用，而別的式子都是多余的。3.1.3關于固定費用的問題（FixedCostProblem）在討論線性規(guī)劃時，有些問題是要求使成本為最小。那時總設固定成本為常數(shù)，并在線性規(guī)劃的模型中不必明顯列出。但有些固定費用（固定成本）的問題不能用一般線性規(guī)劃來描述，但可改變?yōu)榛旌险麛?shù)規(guī)劃來解決，見下例。例5某工廠為了生產(chǎn)某種產(chǎn)品，有幾種不同的生產(chǎn)方式可供選擇，如選定的生產(chǎn)方式投資高（選購自動化程度高的設備），由于產(chǎn)量大，因而分配到每件產(chǎn)品的變動成本就降低；反之，如選定的生產(chǎn)方式投資低，將來分配到每件產(chǎn)品的變動成本可能增加。所以必須全面考慮。今設有三種方式可供選擇，令?表示采用第/種方式時的產(chǎn)量；5表示采用第/種方式時每件產(chǎn)品的變動成本；忍表示采用第J種方式時的固定成本。為了說明成本的特點，暫不考慮其它約束條件。采用各種生產(chǎn)方式的總成本分別為k.+c.x.,當兀>0/=1,2,3.10,當?=0J在構(gòu)成目標函數(shù)時，為了統(tǒng)一在一個問題中討論，現(xiàn)引入0-1變量兒，令1,當采用第J種生產(chǎn)方式，即Xj>0H4,0,當不采用第/種生產(chǎn)方式，即X.=0IN.（3）于是目標函數(shù)minz=dminz=d+q")+（皿+c2x2)+伙3兒+c3x3)（3）式這個規(guī)定可表為下述3個線性約束條件:7=1,23（4）其中M是個充分大的常數(shù)。（4）式說明，當勺>0時兒必須為1；當勺=0時只有兒為0時才有意義，所以（4）式完全可以代替（3）式。3.20-1型整數(shù)規(guī)劃解法之一（過濾隱枚舉法）解0-1型整數(shù)規(guī)劃最容易想到的方法，和一般整數(shù)規(guī)劃的情形一樣，就是窮舉法，即檢查變量取值為0或1的每一種組合，比較目標函數(shù)值以求得最優(yōu)解，這就需要檢查變量取值的2”個組合。對于變量個數(shù)〃較大（例如”>10），這幾乎是不可能的。因此常設計一些方法，只檢查變量取值的組合的一部分，就能求到問題的最優(yōu)解。這樣的方法稱為隱枚舉法（ImplicitEnumeration)，分枝定界法也是一種隱枚舉法。當然，對有些問題隱枚舉法并不適用，所以有時窮舉法還是必要的。下面舉例說明一種解0-1型整數(shù)規(guī)劃的隱枚舉法。例6Maxz=3xt-2x2+5x3Xj+2x2叫<2x，+4X2+<4xt+x2<34x2+x3<6x15x2,x3=0或1求解思路及改進措施：⑴先試探性求一個可行解，易看出(x15x2,x3)=(1,0,0)滿足約束條件，故為一個可彳亍，日z=3o一'(ii)因為是求極大值問題，故求最優(yōu)解時，凡是目標值ZV3的解不必檢驗是否滿足約束條件即可刪除，因它肯定不是最優(yōu)解，于是應增加一個約束條件(目標值下界)：改進過濾條件。由于對每個組合首先計算目標值以驗證過濾條件，故應優(yōu)先計算目標值Z大的組合，這樣可提前抬高過濾門檻，以減少計算量?！?蒙特卡洛法(隨機取樣法)前面介紹的常用的整數(shù)規(guī)劃求解方法，主要是針對線性整數(shù)規(guī)劃而言，而對于非線性整數(shù)規(guī)劃目前尚未有一種成熟而準確的求解方法，因為非線性規(guī)劃本身的通用有效解法尚未找到，更何況是非線性整數(shù)規(guī)劃。然而，盡管整數(shù)規(guī)劃由于限制變量為整數(shù)而增加了難度；然而乂由于整數(shù)解是有限個，于是為枚舉法提供了方便。當然，當自變量維數(shù)很大和取值范圍很寬情況下，企圖用顯枚舉法(即窮舉法)計算出最優(yōu)值是不現(xiàn)實的，但是應用概率理論可以證明，在一定的計算量的情況下，完全可以得出一個滿意解。例7已知非線性整數(shù)規(guī)劃為：Maxz=￡+x；+—8X1—2Xj0<x,.<99(i=l,,5)Xk+X2+Xz+X4+X5<400<Xk+2x24-2x、+x4+6x5<800+x2+6X3<200x3++5X5<200對該題，目前尚無有效方法求出準確解。如果用顯枚舉法試探，共需計算(100)5=10」。個點，其計算量非常之大。然而應用蒙特卡洛去隨機計算106個點，便可找到滿意解，那么這種方法的可信度究竟怎樣呢？下面就分析隨機取樣采集10。個點計算時，應用概率理論來估計一下可信度。不失一般性，假定一個整數(shù)規(guī)劃的最優(yōu)點不是孤立的奇點。假設目標函數(shù)落在高值區(qū)的概率分別為0.01,0.00001,則當計算106個點后，有任一個點能落在高值區(qū)的概率分別為1-0.991000000?0.9999(100多位)，析：P(IJX)=1-X,)=1-QP(X,.)i=lf=l1=11-O.999991000000y0.999954602。解(i)首先編寫M文件mente.m定義目標函數(shù)f和約束向量函數(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(l)=sum(x)-400;g(2)=x(l)+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;Lii)編寫如下程序求問題的解：rand(?state',sum(clock));p0=0;ticfori=l:10A5x=99*rand(5,1);xl=floor(x);x2_ceil(x);[f,g]=mengte(xl);ifsum(g〈二0)二二4ifpO<=fx0=xl;pO=f;endend[f,g]=mengte(x2);ifsum(g〈二0)二二4ifpO