第二講 整數(shù)規(guī)劃及0-1規(guī)劃

整數(shù)規(guī)劃與0-1規(guī)劃主講：毛何悅電話息與計(jì)算科學(xué)1什么是整數(shù)規(guī)劃與0-1規(guī)劃？定義規(guī)劃中的變量（部分或全部）限制為整數(shù)時(shí)，稱為整數(shù)規(guī)劃。若在線性規(guī)劃模型中，變量限制為整數(shù)，則稱為整數(shù)線性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法，往往只適用于整數(shù)線性規(guī)劃。目前還沒有一種方法能有效地求解一切整數(shù)規(guī)劃。整數(shù)規(guī)劃的分類（一般指整數(shù)線性規(guī)劃）變量全限制為整數(shù)時(shí)，稱純（完全）整數(shù)規(guī)劃。變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。變量只能取0或1時(shí)，稱之為0-1整數(shù)規(guī)劃。2例13例2背包問題4

整數(shù)規(guī)劃特點(diǎn)(1)原線性規(guī)劃有最優(yōu)解，當(dāng)自變量限制為整數(shù)后，其整數(shù)規(guī)劃解出現(xiàn)下述情況：原線性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。原線性規(guī)劃最優(yōu)解不全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解小于原線性規(guī)劃最優(yōu)解（max）或整數(shù)規(guī)劃最優(yōu)解大于原線性規(guī)劃最優(yōu)解（min）。整數(shù)規(guī)劃無可行解。(2)整數(shù)規(guī)劃最優(yōu)解不能按照實(shí)數(shù)最優(yōu)解簡(jiǎn)單取整而獲得。5整數(shù)規(guī)劃求解方法分類（i）分枝定界法—可求純或混合整數(shù)線性規(guī)劃。（ii）割平面法—可求純或混合整數(shù)線性規(guī)劃。（iii）隱枚舉法—求解“0-1”整數(shù)規(guī)劃：①過濾隱枚舉法；②分枝隱枚舉法。（iv）匈牙利法—解決指派問題（“0-1”規(guī)劃特殊情形）。（v）蒙特卡洛法—求解各種類型規(guī)劃。6整數(shù)規(guī)劃-分枝定界法對(duì)有約束條件的最優(yōu)化問題的可行解空間恰當(dāng)?shù)剡M(jìn)行系統(tǒng)搜索，這就是分枝與定界內(nèi)容。通常，把全部可行解空間反復(fù)地分割為越來越小的子集，稱為分枝；并且對(duì)每個(gè)子集內(nèi)的解集計(jì)算一個(gè)目標(biāo)下界（對(duì)于最小值問題），這稱為定界。在每次分枝后，凡是界限不優(yōu)于已知可行解集目標(biāo)值的那些子集不再進(jìn)一步分枝，這樣，許多子集可不予考慮，這稱剪枝。這就是分枝定界法的主要思路。7例題演示例3求解下述整數(shù)規(guī)劃s.t.

AB先不考慮整數(shù)限制，即解相應(yīng)的線性規(guī)劃，得最優(yōu)解為：

8顯然它不符合整數(shù)條件。這時(shí)Z是問題A的最優(yōu)目標(biāo)函數(shù)值Z*的上界，記作。而顯然是問題A的一個(gè)整數(shù)可行解，這時(shí)Z=0，是Z*的一個(gè)下界，記作，即9分支因?yàn)楫?dāng)前均為非整數(shù)，故不滿足整數(shù)要求，任選一個(gè)進(jìn)行分枝。設(shè)選進(jìn)行分枝，把可行集分成2個(gè)子集：因?yàn)?與5之間無整數(shù)，故這兩個(gè)子集內(nèi)的整數(shù)解必與原可行集合整數(shù)解一致。這一步稱為分枝。這兩個(gè)子集的規(guī)劃及求解如下：10再定界：

對(duì)問題B1再進(jìn)行分枝得問題B11和B12，它們的最優(yōu)解為:

再定界：，并將B12剪枝。對(duì)問題B2再進(jìn)行分枝得問題B21和B22，它們的最優(yōu)解為:

無可行解。將剪枝，于是可以斷定原問題的最優(yōu)解為：110<=Z*<=355.8799340<=Z*<=355.8799340<=Z*<=341.4121314小結(jié)從以上解題過程可得用分枝定界法求解整數(shù)規(guī)劃（最大化）問題的步驟為：首先，將要求解的整數(shù)規(guī)劃問題稱為問題A，將與它相應(yīng)的線性規(guī)劃問題稱為問題B。i）解問題B可能得到以下情況之一：（a）B沒有可行解，這時(shí)A也沒有可行解，則停止．（b）B有最優(yōu)解，并符合A問題的整數(shù)條件，B的最優(yōu)解即為A的最優(yōu)解，則停止。（c）B有最優(yōu)解，但不符合問題的整數(shù)條件，記它的目標(biāo)函數(shù)值為。15小結(jié)（續(xù)）ii）用觀察法找問題A的一個(gè)整數(shù)可行解，一般可取試探，求得其目標(biāo)函數(shù)值，并記作。以表示問題的最優(yōu)目標(biāo)函數(shù)值；這時(shí)有其次，進(jìn)行迭代。第一步：分枝，在B的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量xj，其值為bj，以[bj]表示小于bj的最大整數(shù)。構(gòu)造兩個(gè)約束條件:將這兩個(gè)約束條件，分別加入B問題，求兩個(gè)后繼規(guī)劃問題B1和B2。不考慮整數(shù)條件求解這兩個(gè)后繼問題。定界，以每個(gè)后繼問題為一分枝標(biāo)明求解的結(jié)果，與其它問題的解的結(jié)果中，找出最優(yōu)目標(biāo)函數(shù)值最大者作為新的上界。從已符合整數(shù)條件的各分支中，找出目標(biāo)函數(shù)值為最大者作為新的下界，若無作用=0。第二步：比較與剪枝，各分枝的最優(yōu)目標(biāo)函數(shù)中若有小于者，則剪掉這枝，即以后不再考慮了。若大于，且不符合整數(shù)條件，則重復(fù)第一步驟。一直到最后得到=為止。得最優(yōu)整數(shù)解。

16分析整數(shù)規(guī)劃關(guān)鍵是找到一下限-最大化問題（或上限-最小化問題），用來剪枝，通過觀察法，我們往往可以得到這個(gè)下限或上限，但是有沒有更好的辦法來得到一個(gè)相對(duì)較好的值呢？初值選取----蒙特卡洛法17MATALB求解命令%[x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x,id)%整數(shù)線性規(guī)劃分支定界法，可求解全整數(shù)或混合整數(shù)線性規(guī)劃。%y=minf'*xs.t.G*x<=hGeq*x=heqx為全整數(shù)或混合整數(shù)列向量。%[x,y]=IntLp(f,G,h)%[x,y]=IntLp(f,G,h,Geq,heq)%[x,y]=IntLp(f,G,h,Geq,heq,lb,ub)%[x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x)%[x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x,id)%[x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x,id,options)%x:最優(yōu)解列向量；y:目標(biāo)函數(shù)最小值；f:目標(biāo)函數(shù)系數(shù)列向量%G:約束不等式條件系數(shù)矩陣；h:約束不等式條件右端列向量%Geq:約束等式條件系數(shù)矩陣；heq：約束登時(shí)條件右端列向量%lb:自變量下界列向量（default:-inf）%ub:自變量上界列向量（default:inf）%x:迭代初值列向量%id:整數(shù)變量指標(biāo)列向量，1-整數(shù)，0-實(shí)數(shù)（default:1）%options的設(shè)置請(qǐng)參見optimset或linprog18求解例1f=[-20-10];G=[54;25];h=[24;13];[x,y]=IntLp(f,G,h,[],[],[0;0],[inf;inf])

x=[4.00001.0000]z=90190-1型整數(shù)規(guī)劃

0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃中的特殊情形，它的變量xj僅取值0或1。這時(shí)xj稱為0-1變量，或稱二進(jìn)制變量。xj僅取值0或1這個(gè)條件可由下述約束條件：整數(shù)所代替，是和一般整數(shù)規(guī)劃的約束條件形式一致的。我們先介紹引入0-1變量的實(shí)際問題，再研究解法。20例4投資場(chǎng)所的選定—相互排斥的計(jì)劃

某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個(gè)位置（點(diǎn)）Ai(i=1,2,…,7)可供選擇。規(guī)定在東區(qū)：由A1,A2,A3三個(gè)點(diǎn)中至多選兩個(gè)；在西區(qū)：由A4,A5兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)：由A6,A7兩個(gè)點(diǎn)中至少選一個(gè)。

如選用點(diǎn)Ai，設(shè)備投資估計(jì)為bi元，每年可獲利潤(rùn)估計(jì)為ci元，但投資總額不能超過B元。問應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤(rùn)為最大？21解題時(shí)先引入0-1變量xi(i=1,2,…,7),令：于是問題可列寫成：22例5關(guān)于固定費(fèi)用的問題（FixedCostProblem）

在討論線性規(guī)劃時(shí)，有些問題是要求使成本為最小。那時(shí)總設(shè)固定成本為常數(shù)，并在線性規(guī)劃的模型中不必明顯列出。但有些固定費(fèi)用（固定成本）的問題不能用一般線性規(guī)劃來描述，但可改變?yōu)榛旌险麛?shù)規(guī)劃來解決。某工廠為了生產(chǎn)某種產(chǎn)品，有幾種不同的生產(chǎn)方式可供選擇，如選定的生產(chǎn)方式投資高（選購自動(dòng)化程度高的設(shè)備），由于產(chǎn)量大，因而分配到每件產(chǎn)品的變動(dòng)成本就降低；反之，如選定的生產(chǎn)方式投資低，將來分配到每件產(chǎn)品的變動(dòng)成本可能增加。所以必須全面考慮。今設(shè)有三種方式可供選擇，令

xj表示采用第j種方式時(shí)的產(chǎn)量；

cj表示采用第j種方式時(shí)每件產(chǎn)品的變動(dòng)成本；

kj表示采用第j種方式時(shí)的固定成本。23為了說明成本的特點(diǎn)，暫不考慮其它約束條件。采用各種生產(chǎn)方式的總成本分別為:在構(gòu)成目標(biāo)函數(shù)時(shí)，為了統(tǒng)一在一個(gè)問題中討論，現(xiàn)引入0-1變量yj，令

于是目標(biāo)函數(shù)240-1型整數(shù)規(guī)劃解法之一（過濾隱枚舉法）

解0-1型整數(shù)規(guī)劃最容易想到的方法，和一般整數(shù)規(guī)劃的情形一樣，就是窮舉法，即檢查變量取值為0或1的每一種組合，比較目標(biāo)函數(shù)值以求得最優(yōu)解，這就需要檢查變量取值的2n個(gè)組合。對(duì)于變量個(gè)數(shù)n較大（例如n>10），這幾乎是不可能的。因此常設(shè)計(jì)一些方法，只檢查變量取值的組合的一部分，就能求到問題的最優(yōu)解。這樣的方法稱為隱枚舉法（ImplicitEnumeration），分枝定界法也是一種隱枚舉法。當(dāng)然，對(duì)有些問題隱枚舉法并不適用，所以有時(shí)窮舉法還是必要的。

25例6求解思路及改進(jìn)措施：先試探性求一個(gè)可行解，易看出滿足約束條件，故為一個(gè)可行解，且相應(yīng)的目標(biāo)函數(shù)值為因?yàn)槭乔髽O大值問題，故求最優(yōu)解時(shí)，凡是目標(biāo)值的解不必檢驗(yàn)是否滿足約束條件即可刪除，因它肯定不是最優(yōu)解，于是應(yīng)增加一個(gè)約束條件（目標(biāo)值下界）：稱該條件為過濾條件(FilteringContraint)。

26從而原問題等價(jià)于：

s.t.

27從而得最優(yōu)解，最優(yōu)值28MATALB求解命令x=bintprog(f)x=bintprog(f,A,b)x=bintprog(f,A,b,Aeq,beq)x=bintprog(f,A,b,Aeq,beq,x0)x=bintprog(f,A,b,Aeq,Beq,x0,options)[x,fval]=bintprog(...)[x,fval,exitflag]=bintprog(...)[x,fval,exitflag,output]=bintprog(...)[x,f]=Lp01_e(c,A,b,N)%枚舉法[x,f]=Lp01_ie(c,A,b,N)%隱枚舉法%Lp01_e和Lp01_ie分別為枚舉法和隱枚舉法%求解0-1線性規(guī)劃問題%minf=c'*x,s.t.A*x<=b,x的分量全為整數(shù)0或1,%其中N表示約束條件Ax≤b中的前N個(gè)是等式，N=0時(shí)可以省略。%返回結(jié)果x是最優(yōu)解，f是最優(yōu)解處的函數(shù)值。29練習(xí)（一個(gè)分派問題）有5個(gè)工人，要分派他們分別完成5項(xiàng)工作，每人做各項(xiàng)工作所消耗的時(shí)間如下表，問應(yīng)如何安排工作，可使總的消耗時(shí)間最?。抗ぷ鞴と思滓冶∥霢BCDE53567645748675646927518683031c=[5684534661557986757674628];A=[1000010000100001000010000010000100001000010000100000100001000010000100001000001000010000100001000010000010000100001000010000111111000000000000000000000000011111000000000