整數(shù)規(guī)劃-模型

1、1整數(shù)規(guī)劃方法整數(shù)規(guī)劃方法一一. .整數(shù)規(guī)劃的一般模型整數(shù)規(guī)劃的一般模型二二. .整數(shù)規(guī)劃的求解方法整數(shù)規(guī)劃的求解方法 三三.0-1.0-1整數(shù)規(guī)劃整數(shù)規(guī)劃 四四. .整數(shù)規(guī)劃案例分析整數(shù)規(guī)劃案例分析2一一. .整數(shù)規(guī)劃的一般模型整數(shù)規(guī)劃的一般模型1. 問題的提出：固定資源分配問題問題的提出：固定資源分配問題34 在這個問題中，所求解均是整數(shù)，初看起來，在這個問題中，所求解均是整數(shù)，初看起來，似乎只要把已得到的帶有分?jǐn)?shù)或小數(shù)的解經(jīng)過似乎只要把已得到的帶有分?jǐn)?shù)或小數(shù)的解經(jīng)過“舍入化整舍入化整”就可以了，實際上這常常是不行的，就可以了，實際上這常常是不行的，因為化整后不見得是可行解，或雖是可行解但

2、不因為化整后不見得是可行解，或雖是可行解但不一定是最優(yōu)解。這種求最優(yōu)整數(shù)解的問題就是整一定是最優(yōu)解。這種求最優(yōu)整數(shù)解的問題就是整數(shù)規(guī)劃。數(shù)規(guī)劃。 整數(shù)規(guī)劃中如果所有的變量都限制為（非負(fù)）整數(shù)規(guī)劃中如果所有的變量都限制為（非負(fù)）整數(shù)，稱為純整數(shù)規(guī)劃；如果僅一部分變量限制整數(shù)，稱為純整數(shù)規(guī)劃；如果僅一部分變量限制為整數(shù)，稱為混合整數(shù)規(guī)劃；整數(shù)規(guī)劃一種特殊為整數(shù)，稱為混合整數(shù)規(guī)劃；整數(shù)規(guī)劃一種特殊的情形是的情形是0-1規(guī)劃，它的變量取值僅限于規(guī)劃，它的變量取值僅限于0和和1。52. 整數(shù)規(guī)劃模型的一般形式整數(shù)規(guī)劃模型的一般形式問題是如何求解整數(shù)規(guī)劃問題呢？問題是如何求解整數(shù)規(guī)劃問題呢？能否設(shè)想先略去

3、決策變量整數(shù)約束，即變?yōu)榫€性能否設(shè)想先略去決策變量整數(shù)約束，即變?yōu)榫€性規(guī)劃問題求解，再對其最優(yōu)解進(jìn)行取整處理呢？規(guī)劃問題求解，再對其最優(yōu)解進(jìn)行取整處理呢？實際上，可借鑒這種思想來解決整數(shù)規(guī)劃問題實際上，可借鑒這種思想來解決整數(shù)規(guī)劃問題6二二. .整數(shù)規(guī)劃的求解方法整數(shù)規(guī)劃的求解方法1. 分枝定界法的基本思想（舉例說明）分枝定界法的基本思想（舉例說明）分枝定界法分枝定界法.ppt7 繼續(xù)求解定界，重復(fù)下去，直到得到最優(yōu)解繼續(xù)求解定界，重復(fù)下去，直到得到最優(yōu)解為止為止. .82. 分枝定界法的一般步驟分枝定界法的一般步驟 問題問題(B)(B)無可行解，則無可行解，則(A)(A)也無可行解，停止；也

4、無可行解，停止；91011123. 整數(shù)規(guī)劃的整數(shù)規(guī)劃的lingo解法解法11min(1,2,)0,(1,2, )njjjnijjijjjzc xa xb imxxjn為整數(shù)13例：一個簡單的整數(shù)規(guī)劃模型例：一個簡單的整數(shù)規(guī)劃模型1212121212max264520,0,zxxxxxxx xx x且取整數(shù)14其其lingolingo語句如下：語句如下：MODEL:sets:row/1.2/:b; arrange/1.2/:c,x;link(row,arrange):a;endsetsdata: b=6,20;c=1,1;a=2,1,4,5;enddataOBJmax=sum(arrange(

5、j):c(j)*x(j);for(row(i):sum(arrange(j):a(i,j)*x(j)=0;);for(arrange(j):gin(x(j););END 運(yùn)行該程序后可得最優(yōu)解為（運(yùn)行該程序后可得最優(yōu)解為（0，4），目標(biāo)函），目標(biāo)函數(shù)最優(yōu)值為數(shù)最優(yōu)值為4.15三三.0-1.0-1整數(shù)規(guī)劃整數(shù)規(guī)劃1. 0-1整數(shù)規(guī)劃的模型整數(shù)規(guī)劃的模型162. 指派（分配）問題（指派（分配）問題（0-1規(guī)劃的特例）規(guī)劃的特例） 在生產(chǎn)管理上，總希望把人員最佳分派，在生產(chǎn)管理上，總希望把人員最佳分派，以發(fā)揮其最大工作效率，創(chuàng)造最大的價值。以發(fā)揮其最大工作效率，創(chuàng)造最大的價值。 例如：某部門有例如：

6、某部門有n n項任務(wù)，正好需要項任務(wù)，正好需要n n個個人去完成，由于任務(wù)的性質(zhì)和各人的專長不人去完成，由于任務(wù)的性質(zhì)和各人的專長不同，如果分配每個人僅能完成一項任務(wù)。同，如果分配每個人僅能完成一項任務(wù)。 如何分派使完成如何分派使完成n n項任務(wù)的總效益為最高項任務(wù)的總效益為最高（效益量化），這是典型的分配問題。（效益量化），這是典型的分配問題。17 （1 1）例例1 1：現(xiàn)在不妨設(shè)有現(xiàn)在不妨設(shè)有4 4個人，各有能力去個人，各有能力去完成完成4 4項科研任務(wù)中的任一項，由于項科研任務(wù)中的任一項，由于4 4個人的能力個人的能力和經(jīng)驗不同，所需完成各項任務(wù)的時間如下表：和經(jīng)驗不同，所需完成各項任務(wù)

7、的時間如下表： 項項目目人人員員ABCD甲甲乙乙丙丙丁丁2109715414813141611415139問如何分配何問如何分配何人去完成何項人去完成何項目使完成目使完成4 4項項任務(wù)所需總時任務(wù)所需總時間最少？間最少？18每每個個人人去去完完成成一一項項任任務(wù)務(wù)的的約約束束為為 111144434241343332312423222114131211xxxxxxxxxxxxxxxx 19目目標(biāo)標(biāo)函函數(shù)數(shù)： 444342413433323124232221141312119118713161491514410413152minxxxxxxxxxxxxxxxxz 2021 （2 2）指派問題的一

8、般模型指派問題的一般模型22 ), 2, 1,(10, 2, 1, 1, 2, 1, 111njixnjxnixijniijnjij或233.用用lingo求解求解 0-1整數(shù)規(guī)劃模型整數(shù)規(guī)劃模型MODEL:MODEL: sets: sets: row/1.m/:b; arrange/1.n/:c,x; link(row,arrange):a; endsets data: b=b(1),b(2),b(m); c=c(1),c(2),c(n); a=a(1,1),a(1,2),a(1,n), a(2,1),a(2,2),a(2,n), . . . . a(m,1),a(m,2),a(m,n);

9、enddata OBJ min=sum(arrange(j):c(j)*x(j); for(row(i):sum(arrange(j):a(i,j)*x(j)=b(i);); for(arrange(j):x(j)=0;); for(arrange(j):BIN(x(j);); END 11min(1,2,)01(1,2, )njjjnijjijjzc xa xb imxorjn24P16P16頁例頁例1 1用用lingolingo求解后，可知讓甲求解后，可知讓甲去完成任務(wù)去完成任務(wù)D D，乙完成任務(wù)，乙完成任務(wù)B B，丙完成，丙完成任務(wù)任務(wù)A A，丁完成任務(wù)，丁完成任務(wù)C C，所用時間最少，

10、所用時間最少為為28.28.25四四. . 整數(shù)規(guī)劃案例分析整數(shù)規(guī)劃案例分析1. 兼職值班員問題兼職值班員問題26實驗室開放時間為上午實驗室開放時間為上午8:008:00至晚上至晚上10:00;10:00;開放時間內(nèi)須有且僅有一名學(xué)生值班開放時間內(nèi)須有且僅有一名學(xué)生值班; ;規(guī)定大學(xué)生每周值班不少于規(guī)定大學(xué)生每周值班不少于8 8小時小時; ;研究生每周值班不少于研究生每周值班不少于7 7小時小時; ;每名學(xué)生每周值班不超每名學(xué)生每周值班不超3 3次次; ;每次值班不少于每次值班不少于2 2小時小時; ;每天安排值班的學(xué)生不超過每天安排值班的學(xué)生不超過3 3人，且其中必須人，且其中必須有一名研究生有一名研究生. . 試為該實驗室安排一張人員的值班表，使總試為該實驗室安排一張人員的值班表，使總支付的報酬額最少。支付的報酬額最少。2728問問題題的的數(shù)數(shù)學(xué)學(xué)模模型型：2930例例2：汽車廠生產(chǎn)計劃汽車廠生產(chǎn)計劃.ppt人有了知識，就會具備各種分析能力，人有了知識，就會具備各種分析能力，明辨是非的能力。明辨是非的能力。所以我們要勤懇讀書，廣泛閱讀，所以我們要勤懇讀書，廣泛閱讀，古人說古人說“書中自有黃金屋。書中自有黃金屋?！蓖ㄟ^閱讀科技書籍，我們能豐富知識，通過閱讀科技書籍，我們能豐富知識，培養(yǎng)邏輯思維能力；培養(yǎng)邏輯思維能力；通