1、第五章 整數(shù)規(guī)劃,教學(xué)目的：掌握若干特殊整數(shù)規(guī)劃的解法 教學(xué)內(nèi)容：1.整數(shù)規(guī)劃問題及特點(diǎn) 2.分枝定界法與割平面法 3.0-1規(guī)劃 4.指派問題 教學(xué)重點(diǎn)：割平面法與指派問題 教學(xué)難點(diǎn)：分枝定界法與割平面法 學(xué)時(shí)安排：4學(xué)時(shí)。,教學(xué)內(nèi)容,第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) 第二節(jié)解純整數(shù)規(guī)劃的割平面法 第三節(jié)分支定界法 第四節(jié) 0-1整數(shù)規(guī)劃 第五節(jié)指派問題,第一節(jié) 整數(shù)規(guī)劃問題的提出,1.整數(shù)規(guī)劃問題基本概念 2.整數(shù)規(guī)劃問題的特點(diǎn),1.整數(shù)規(guī)劃問題基本概念,（1）整數(shù)規(guī)劃：要求部分或全部決策變量取整數(shù)值的規(guī)劃問題。 （2）整數(shù)規(guī)劃問題的松弛問題：不考慮整數(shù)條件的規(guī)劃問題。 （3）整數(shù)線性規(guī)

2、劃部分或全部變量取整數(shù)值的線性規(guī)劃 純整數(shù)線性規(guī)劃（pure integer linear programming) 混合整數(shù)線性規(guī)劃（mixed） 0-1整數(shù)線性規(guī)劃(zero-one）,2.整數(shù)規(guī)劃問題的特點(diǎn),問題：能否將松弛問題的最優(yōu)解近似作為整數(shù)規(guī)劃問題的最優(yōu)解？,例5-1：求下述整數(shù)規(guī)劃的最優(yōu)解。,A (3.25,2.5),2x1+3x2=14,X1+0.5x2 =4.5,Z=3x1+2x2,最優(yōu)解為(4,1),2.整數(shù)規(guī)劃問題的特點(diǎn),結(jié)論： 不能把松弛問題的最優(yōu)解通過“四舍五入”或“截尾”（即湊整）處理后作為整數(shù)規(guī)劃的最優(yōu)解。不過，在變量取值很大時(shí)，用上述方法得到的解與最優(yōu)解差別不

3、大。 點(diǎn)(4,1)不是可行域的頂點(diǎn)，所以直接用圖解法或單純形法無法求出整數(shù)規(guī)劃問題的最優(yōu)解,整數(shù)線性規(guī)劃的解與松弛問題的解既有聯(lián)系，又有本質(zhì)的區(qū)別。設(shè) IP的松弛問題的可行域?yàn)镃，IP的可行域?yàn)镃，則有 CC 整數(shù)規(guī)劃的可行解是松弛問題可行解集合的一個(gè)子集。所以 IP的可行解一定是它的松弛問題的可行解。 IP的最優(yōu)值不會(huì)優(yōu)于其松弛問題的最優(yōu)值。,第二節(jié) 割平面法,A(3/4,7/4),C(1,1),一、基本思想： 在IP的松弛問題中,每次增加一個(gè)線性約束，即Gomory約束或割平面。它的作用是：割去可行域中不包含問題整數(shù)解的部分，使松弛問題的可行域逐步縮?。蛔罱K，目標(biāo)函數(shù)值達(dá)到最優(yōu)的整數(shù)點(diǎn)成為

4、縮減可行域的一個(gè)頂點(diǎn)。,二、求解步驟,、求出松弛問題最優(yōu)解，若為整數(shù)，則停止，否則轉(zhuǎn) 、構(gòu)造割平面方程。 構(gòu)造的割平面約束應(yīng)當(dāng)具備兩個(gè)性質(zhì)： 已獲得的非整數(shù)最優(yōu)解不滿足該線性約束，從而保證在以后的解中不可能再出現(xiàn)。 所有的整數(shù)解皆滿足該線性約束，從而保證整數(shù)最優(yōu)解始終都保留在以后每次所形成的新的線性規(guī)劃的可行域中。,X4=31/7不是整數(shù)，該行對應(yīng)的方程是：,CB,XB,b,x1,x2,x3,x4,x5,x1,x2,x4,X4 - 3/7 x3 + 22/7 x5 = 31/7,基變量（整數(shù)）,非基變量（整數(shù)）,-3/7 = -1+4/7 22/7= 3 + 1/7 31/7= 4 + 3/7

5、,在上述式子中，除第一部分X4 （即整數(shù)部分）外，我們將后面變量的系數(shù)與常數(shù)項(xiàng)皆化為兩部分：不超過該數(shù)的最大整數(shù)與非負(fù)分?jǐn)?shù)，即,將整數(shù)部分放在等式的左邊,其余部分放在右邊,得：,上式的左邊是一個(gè)整數(shù)，右邊是一個(gè)小于的數(shù)，因此，右邊是一個(gè)小于或等于的整數(shù)，即,通過分析，可以得出上式具有如下兩個(gè)性質(zhì)：,松弛問題的非整數(shù)最優(yōu)解不滿足該式,IP的所有整數(shù)可行解都滿足此式,構(gòu)造割平面約束的一般方法如下： (1)在松弛問題的最優(yōu)表中，設(shè)b列的第k個(gè)分量bk為非整數(shù)，可將它分解為整數(shù)和非整數(shù)部分之和，即bk =Nk + fk ， Nk bk 且為整數(shù)，0 fk 1。 (2)然后，第k行中的每一個(gè)非基變量 x

6、j的系數(shù) akj也分解為整數(shù)與非負(fù)數(shù)之和的形式，即 akj= Nkj + fkj ;Nkj akj ; 0 fk 1,則割平面方程為：,xj為非基變量,通常，從最優(yōu)單純形表中，選擇具有最大分?jǐn)?shù)部分的非整分量所在行構(gòu)造割平面約束，可以提高切割效果，減少切割次數(shù)。,例5-2用割平面法求解純整數(shù)規(guī)劃。,解: 用單純形法求得松弛問題的最優(yōu)表如下。,松弛問題的最優(yōu)解為非整數(shù),而在13/7=1+6/7 ， 9/7=1+2/7 ， 31/7=4+3/7的非負(fù)分?jǐn)?shù)中,6/7最大。所以，將13/7所在的行中非基變量所對應(yīng)的系數(shù)進(jìn)行分解: 1/7=0+1/7 2/7=0+2/7。割平面方程為：,將割平面約束變?yōu)榈?/p>

7、式約束后，并入松弛問題的最優(yōu)表中，見下表。,利用對偶單純形法求出最優(yōu)解，見下表。,由上表第四行產(chǎn)生的割平面約束為：,E,例5-3,求出松弛問題的最優(yōu)解,x1,x2,CB,XB,b,x1,x2,x3,x4,構(gòu)造割平面,x1,x2,CB,XB,b,x1,x2,x3,x4,x5,x5,x1,x2,CB,XB,b,x1,x2,x3,x4,x3,x5,構(gòu)造割平面,x1,x2,CB,XB,b,x1,x2,x3,x4,x3,x5,x6,x6,x1,x2,CB,XB,b,x1,x2,x3,x4,x3,x5,x5,x6,B(1,16/5),C(9/5,12/9),D(0,4),E(2,2),F(1,3),例5-

8、4：某公司欲在東、西、南三區(qū)建立門市部，共有7個(gè)地方可供選擇。規(guī)定；在東區(qū)，由A1、A2、A3三個(gè)點(diǎn)中至多選兩個(gè)；在西區(qū)，由A4、A5兩點(diǎn)中至少選一個(gè)；在南區(qū)，由A6、A7兩點(diǎn)中至少選一個(gè)。選用Ai點(diǎn)，投資為bi元，每年可獲利潤ci元，但投資總額不能超過B元。問應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤最大？,解：設(shè),0-1變量作為邏輯變量，常用來表示系統(tǒng)處于某個(gè)特定狀態(tài)，或?qū)δ硞€(gè)決策方案的選擇。,第三節(jié) 0-1整 數(shù) 規(guī) 劃,一、0-1變量及其應(yīng)用,例5-5 含有相互排斥的約束條件問題,120,0.4,0.2,40,25,利潤 （元件）,150,0.5,0.3,B3,100,0.1,0.2,B2,250,工時(shí)

9、限額（h/周）,0.7,A2,0.3,A1,B1,產(chǎn)品,工時(shí)件,工序,方式方式,要求 B3 只能從加工方式與中選擇一種，那么工廠應(yīng)如何安排生產(chǎn)，才能使總利潤最大？,解：設(shè)生產(chǎn)兩種產(chǎn)品分別為x1與x2件。,當(dāng)工序B3選用加工方式，即滿足,當(dāng)工序B3不選用加工方式,當(dāng)工序B3選用加工方式，即滿足,當(dāng)工序B3不選用加工方式,方式與中選擇一種等價(jià)于,該問題也可以令,當(dāng)工序B3采用加工方式,當(dāng)工序B3采用加工方式,則，僅從加工方式中選擇一種等價(jià)于：,設(shè)：P個(gè)約束條件中有q個(gè)約束起作用，,令,當(dāng)?shù)?i 個(gè)約束起作用,當(dāng)?shù)?i 個(gè)約束不起作用,相互排斥約束的一般情況。,則該問題等價(jià)于,例5-6 試?yán)?-1

10、變量將下列各約束條件表示成一般的線性約束條件。, x1+x23 或 2x1+3x28,解： 令,選第一個(gè)約束,選第二個(gè)約束,則原命題等價(jià)于,則, 若x24,則x50;否則， x53。,設(shè),則, 用0-1變量表示整數(shù)變量。 任何一個(gè)整數(shù)變量xu，可以表示為：,其中，K滿足 2k+1u+1。,例如， x9，可以表示為： x = 20y0 + 21y1 + 22y2 + 23y3 ，y0 等為0-1變量。,枚舉法是解0-1規(guī)劃的一種算法。具體做法是：檢查每個(gè)變量等于0或1的所有組合。滿足所有約束條件，且使目標(biāo)函數(shù)值最優(yōu)的組合就是0-1規(guī)劃的最優(yōu)解。 由于n個(gè)變量時(shí)，須檢查2n個(gè)變量組合，而當(dāng) n15

11、時(shí)，這幾乎是不可能的。所以，有人提出了隱枚舉法。,二、0-1規(guī)劃的解法隱枚舉法,例5-7,先找一個(gè)可行解,如（0,0,0)，并將其目標(biāo)函數(shù)值Z=0作為下界。,由上步得出過濾性約束條件,對某種變量的組合，檢驗(yàn)其是否滿足上述過濾條件，若滿足且又是可行解，則修改過濾條件，重復(fù)。,注意:上述計(jì)算步驟還可以進(jìn)一步得到改善，即對極大化問題，若將目標(biāo)函數(shù)中xj的價(jià)值系數(shù)按遞增（不減）的次序排列（求極小，價(jià)值系數(shù)按照遞減的次序排列）。即,則可知(0,0,1)的目標(biāo)值一定不小于(0,1,0)及(1,0,0)的目標(biāo)值。同樣(0,1,1)的目標(biāo)值一定不小于(1,1,0)與(1,0,1)的目標(biāo)值。故若(0,0,0)、

12、(0,0,1)、(0,1,1)、(1,1,1)都為可行解，則其他變量的組合可不必考慮。,第四節(jié)分支定界法,B,C,例5-8,LP2(CGE): C(2,23/9);Z=41/9,LP1(BFD): B(1,7/3);Z=10/3,M,H,LP21(HMEG): M(33/14,2);Z=61/14,x1=3,N,L,LP212(NEL): N(3,1);Z=4,LP211(HG): H(2,2);Z=4,分支定界法步驟,1分支 假設(shè)松弛問題的最優(yōu)解不是整數(shù)解，則選擇一個(gè)非整數(shù)分量構(gòu)造兩個(gè)約束條件：,分別加入松弛問題中，得到兩個(gè)子問題LP1與LP2, 即后繼問題，并求解之。,第四節(jié):分 支 定

13、界 法,2定界（以求極大值為例） 以最優(yōu)目標(biāo)函數(shù)值中最大者（針對沒有分支的線性規(guī)劃問題而言）為上界，以符合整數(shù)條件的各子問題中目標(biāo)函數(shù)值最大者作為下界。若無整數(shù)解，在Z0的情況下，令Z=0 3比較與剪枝 若上界等于下界，則停止；否則，剪去小于下界的分支。對于大于下界的分支，繼續(xù)重復(fù)2（函數(shù)值較大的分支優(yōu)先）。,X11,X12,X22,X23,X1 3,X1 2,使用范圍:純整數(shù)、混合整數(shù)規(guī)劃,9x1+7x2 = 56,7x1+20 x2 =70,x1=4,x1=5,LP2(OGBH):B,LP1(MKC):C,H,M,X1 5,X1 4,X22,X23,X21,X22,第五節(jié)指派問題,一、標(biāo)準(zhǔn)

14、形式指派問題及其數(shù)學(xué)模型 二、標(biāo)準(zhǔn)形式指派問題數(shù)學(xué)模型的特點(diǎn) 三、標(biāo)準(zhǔn)形式指派問題的解法匈牙利解法 四、非標(biāo)準(zhǔn)形式的指派問題,假定n個(gè)人去做n件事，要求每人完成其中一件，每件事交給其中一個(gè)人去完成（即人與事都不閑置），每人做各種事的費(fèi)用（或時(shí)間）已知，試求總費(fèi)用最小的分配方案。,一、標(biāo)準(zhǔn)形式指派問題及其數(shù)學(xué)模型,1.問題的提出,特點(diǎn)： （1）人和事數(shù)目相等 （2）一人只能做一件事，一件事只能有一個(gè)人來做 （3）目標(biāo)極小化,2.指派問題的數(shù)學(xué)模型,x11,x12,x1n,xn1,xn2,xnn,minZ= c11 x11+ c12 x12+ cnn xnn,x11+ x12+ x1n =1 .

15、xn1+ xn2+ xnn =1,x11+ x21+ xn1 =1 x1n+ x2n+ xnn =1,xij =0或1；i,j=1,n,1.標(biāo)準(zhǔn)形式的指派問題是特殊的運(yùn)輸問題。用表上作業(yè)法求解時(shí)有2 n-1個(gè)基變量，其中只有n個(gè)取“1”值，其余都取“0”值。也是特殊的整數(shù)規(guī)劃問題，共有解組合2nn個(gè)，用隱枚舉法也不合適。,2.每一個(gè)可行解可用解矩陣來表示：,因?yàn)?X中每行及每列都有且僅有一個(gè)，所以，共有n!個(gè)可行解（ n個(gè)1的分配方式）。,二、指派問題數(shù)學(xué)模型的特點(diǎn),1.思想依據(jù),如果系數(shù)矩陣的所有元素cij0 ，而其中存在n個(gè)位于不同行不同列的零元素，則對應(yīng)的指派方案總費(fèi)用為零，從而也一定是

16、最優(yōu)的。,如,令,三、匈牙利方法,（1）如果從分配問題的系數(shù)矩陣C=(cij)nn的每行（或每列）各元素分別減去一個(gè)常數(shù)，得到一個(gè)新的矩陣C=(cij)nn ，則以C和C為系數(shù)矩陣的兩個(gè)指派問題具有相同的最優(yōu)解。,2.理論基礎(chǔ)（康尼格定理）,minZ(1)= (c11 k)x11+ (c12 k) x12+ (c1n k)x1n + c21 x21+ cnn xnn,minZ(1) = c11 x11+ c12 x12+ cnn xnn -k(x11 + x12+ + x1n ) = c11 x11+ c12 x12+ cnn xnn -k,（2）若矩陣C的元素可分成“”與非“”兩部分，則覆蓋

17、“”元素的最少直線數(shù)目，等于位于不同行不同列獨(dú)立零元素的最大個(gè)數(shù)。,（1）變換系數(shù)矩陣,對各行元素分別減去該行中的最小元素，再對各列元素分別減去該列中的最小元素。直到每行每列都有0元素為止。,3.匈牙利方法步驟,在零元素最少的行（或列）開始，選擇一個(gè)0元素，并加上標(biāo)記：,獨(dú)立零元素的含義是：它所在行的人，已經(jīng)不能再安排其他的事情做；它所在列的事（工作），已經(jīng)有人去做。 如此反復(fù)，直到所有的零元素都被劃去為止。在此過程中，若存在零元素的閉回路，可任選其中一個(gè)零元素加標(biāo)記，同時(shí)劃去同行和同列中的其他零元素。,（2）在變換后的矩陣中確定獨(dú)立零元素,同時(shí)，劃去此零元素所在行及其列的其他零元素。獲標(biāo)記的零元素稱為獨(dú)立零元素。,（3）覆蓋,對沒有獨(dú)立零元素的行打 。 在已打 的行中,對 元素所在的列打 。 在打的列中,對獨(dú)立零元素所在的行打 。 重復(fù)和,直到無法打?yàn)橹埂?對沒有打的行劃線,對打的列劃線,這樣就得到了能覆蓋所有零元素的最少直線數(shù)目的直線集合。,在未被直線覆蓋的元素中找出一個(gè)最小元素；對未被直線覆蓋的元素所在的行（或列）中各個(gè)元素都減去這一最小元素，然后在出現(xiàn)負(fù)元素的列(或行）中加上這一最小元素。,5、重復(fù)上述各個(gè)步驟，直至得到完全