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

整數(shù)規(guī)劃方法一.整數(shù)規(guī)劃的一般模型二.整數(shù)規(guī)劃的求解方法三.0-1整數(shù)規(guī)劃四.整數(shù)規(guī)劃案例分析1一.整數(shù)規(guī)劃的一般模型1.問題的提出：固定資源分配問題23在這個問題中，所求解均是整數(shù)，初看起來，似乎只要把已得到的帶有分?jǐn)?shù)或小數(shù)的解經(jīng)過“舍入化整”就可以了，實(shí)際上這常常是不行的，因?yàn)榛蟛灰姷檬强尚薪猓螂m是可行解但不一定是最優(yōu)解。這種求最優(yōu)整數(shù)解的問題就是整數(shù)規(guī)劃。整數(shù)規(guī)劃中如果所有的變量都限制為（非負(fù)）整數(shù)，稱為純整數(shù)規(guī)劃；如果僅一部分變量限制為整數(shù)，稱為混合整數(shù)規(guī)劃；整數(shù)規(guī)劃一種特殊的情形是0-1規(guī)劃，它的變量取值僅限于0和1。42.整數(shù)規(guī)劃模型的一般形式問題是如何求解整數(shù)規(guī)劃問題呢？能否設(shè)想先略去決策變量整數(shù)約束，即變?yōu)榫€性規(guī)劃問題求解，再對其最優(yōu)解進(jìn)行取整處理呢？實(shí)際上，可借鑒這種思想來解決整數(shù)規(guī)劃問題．5二.整數(shù)規(guī)劃的求解方法1.分枝定界法的基本思想（舉例說明）分枝定界法.ppt6繼續(xù)求解定界，重復(fù)下去，直到得到最優(yōu)解為止.72.分枝定界法的一般步驟

問題(B)無可行解，則(A)也無可行解，停止；8910113.整數(shù)規(guī)劃的lingo解法12例：一個簡單的整數(shù)規(guī)劃模型13其lingo語句如下：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;enddata[OBJ]max=@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):@gin(x(j)););END運(yùn)行該程序后可得最優(yōu)解為（0，4），目標(biāo)函數(shù)最優(yōu)值為4.14三.0-1整數(shù)規(guī)劃1.0-1整數(shù)規(guī)劃的模型152.指派（分配）問題（0-1規(guī)劃的特例）

在生產(chǎn)管理上，總希望把人員最佳分派，以發(fā)揮其最大工作效率，創(chuàng)造最大的價(jià)值。例如：某部門有n項(xiàng)任務(wù)，正好需要n個人去完成，由于任務(wù)的性質(zhì)和各人的專長不同，如果分配每個人僅能完成一項(xiàng)任務(wù)。如何分派使完成n項(xiàng)任務(wù)的總效益為最高（效益量化），這是典型的分配問題。16

（1）例1：現(xiàn)在不妨設(shè)有4個人，各有能力去完成4項(xiàng)科研任務(wù)中的任一項(xiàng)，由于4個人的能力和經(jīng)驗(yàn)不同，所需完成各項(xiàng)任務(wù)的時(shí)間如下表：問如何分配何人去完成何項(xiàng)目使完成4項(xiàng)任務(wù)所需總時(shí)間最少？17181920

（2）指派問題的一般模型21223.用lingo求解0-1整數(shù)規(guī)劃模型23P16頁例1用lingo求解后，可知讓甲去完成任務(wù)D，乙完成任務(wù)B，丙完成任務(wù)A，丁完成任務(wù)C，所用時(shí)間最少為28.24四.整數(shù)規(guī)劃案例分析1.兼職值班員問題25實(shí)驗(yàn)室開放時(shí)間為上午8:00至晚上10:00;開放時(shí)間內(nèi)須有且僅有一名學(xué)生值班;規(guī)定大學(xué)生每周值班不少于8小時(shí);研究生每周值班不少于7小時(shí);每名學(xué)生每周值班不超3次;每次值班不少于2小時(shí);每天安排值班的學(xué)生不超過3人，且其中必須有一名