3-整數規(guī)劃與分配問題(1)匯總課件(93頁PPT)

1、2022/7/161運籌學OPERATIONS RESEARCH第1頁，共93頁。2022/7/162第四章 整數規(guī)劃與分配問題（Integer Programming, IP) 整數規(guī)劃的有關概念及特點 指派問題及匈牙利解法整數規(guī)劃的求解方法：分枝定界法、割平面法 0-1規(guī)劃的求解方法：隱枚舉法整數規(guī)劃的應用第2頁，共93頁。2022/7/163純整數規(guī)劃：在整數規(guī)劃中，如果所有的變量都為非負整 數，則稱為純整數規(guī)劃問題；混合整數規(guī)劃：如果有一部分變量為非負整數，則稱之為 混合整數規(guī)劃問題。0-1變量：在整數規(guī)劃中，如果變量的取值只限于0和1，這 樣的變量我們稱之為0-1變量。0-1規(guī)劃：在

2、整數規(guī)劃問題中，如果所有的變量都為0-1變 量，則稱之為0-1規(guī)劃。1 整數規(guī)劃的有關概念及特點一、 概念整數規(guī)劃： 要求決策變量取整數值的規(guī)劃問題。 （線性整數規(guī)劃、非線性整數規(guī)劃等）第3頁，共93頁。松弛問題整數線性規(guī)劃模型第4頁，共93頁。整數線性規(guī)劃類型1.純整數線性規(guī)劃：2.混合整數線性規(guī)劃：3.01型整數線性規(guī)劃：人員安排問題投資組合問題物資運輸問題第5頁，共93頁。人員安排問題醫(yī)院護士24小時值班，每次值班8小時。不同時段需要的護士人數不等。據統(tǒng)計： 序號時段最少人數安排人數1061060 x12101470 x23141860 x34182250 x45220220 x5602

3、0630 x6最少需要多少護士？第6頁，共93頁。 min z=x1+x2+x3+x4+x5+x6 x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30 x6x160 xj 0,j=1,2,6設x1,x2,x6為各班新上班人數人員安排問題第7頁，共93頁。證券投資：把一定的資金投入到合適的有價證券上以規(guī)避風險并獲得最大的利潤。項目投資：財團或銀行把資金投入到若干項目中以獲得中長期的收益最大。投資組合問題第8頁，共93頁。 現有資金總額為B?？晒┻x擇的投資項目有n個，項目j所需投資額和預期收益分別為aj和cj（j=1,2,.,n）。此外， 由于種種原因，有三個

4、附加條件：第一，若選擇項目1，就必須同時選擇項目2。反之，則不一定；第二，項目3和4中至少選擇一個；第三，項目5，6和7中恰好選擇兩個。應當怎樣選擇投資項目，才能使總預期收益最大？第9頁，共93頁。模 型變量每個項目是否投資約束總金額不超過限制3個附加條件目標總收益最大第10頁，共93頁。模 型第11頁，共93頁。物資運輸問題工廠A1和A2生產某種物資。由于該種物資供不應求，故需要再建一家工廠。相應的建廠方案有A3和A4兩個。這種物資的需求地有B1，B2，B3，B4四個。各工廠年生產能力、各地年需求量、各廠至各需求地的單位物資運費cij(i,j=1,2,3,4).B1B2B3B4生產能力A12

5、934400A28357600A37612200A44525200需求量3504003001501200工廠A3或A4開工后，每年的生產費用估計分別為1200萬元或1500萬元?，F要決定應該建設工廠A3還是A4，才能使今后每年的總費用最少？第12頁，共93頁。再引入一個0-1變量y第13頁，共93頁。第14頁，共93頁。特征變量整數性要求來源 問題本身的要求 引入的邏輯變量的需要性質可行域是離散集合模型的特點第15頁，共93頁。與線性規(guī)劃的關系整數規(guī)劃放松的線性規(guī)劃可行解是松弛問題的可行解最優(yōu)值不會優(yōu)于其松弛問題的最優(yōu)值第16頁，共93頁。注 釋最優(yōu)解不一定在頂點上達到最優(yōu)解不一定是松弛問題最

6、優(yōu)解的鄰近整數解整數可行解遠多于頂點，枚舉法不可取第17頁，共93頁。2022/7/1618求整數解的線性規(guī)劃問題，不是用四舍五入法或去尾法對性規(guī)劃的非整數解加以處理就能解決的，用枚舉法又往往會計算量太大，所以要用整數規(guī)劃的特定方法加以解決。例： 求解下列整數規(guī)劃：二、 整數規(guī)劃的求解特點第18頁，共93頁。2022/7/1619分析： 若當作一般線性規(guī)劃求解，圖解法的結果如下。1、非整數規(guī)劃最優(yōu)解 顯然不是整數規(guī)劃的可行解。2、四舍五入后的結果 也不是整數規(guī)劃的可行解。3、可行解是陰影區(qū)域交叉點，可比較這些點對應的函數值，找出最優(yōu)。第19頁，共93頁。2022/7/16202 指派問題及匈牙

7、利解法 一、 指派問題與模型 m項任務分配給m個人去完成，每人只能完成其中一項，每項任務只能分給一人完成，應如何分配使得效率最高？ aij是第j個人完成第i項任務的效率。 人任務12 m1a11a12a1m2a21a22a2mmam1am2amm第20頁，共93頁。2022/7/1621設于是建立模型如下： 第21頁，共93頁。2022/7/1622二、 指派問題的匈牙利解法該指派問題可當作運輸問題解決，但匈牙利解法更有效。解法思想：效率矩陣的元素 ，若有一組位于不同行不同列的零元素，則令這些位置的決策變量取值為1，其余均為0，這顯然就是最優(yōu)解。第22頁，共93頁。2022/7/1623定理2

8、：若矩陣A的元素可分為“0”元和“非0”元，則覆蓋“0”元的最少直線數等于位于不同行、不同列的“0”元的最大個數。定理1：效率矩陣 的每一行元素分別減去（加上）一個常數 ，每一列元素分別減去（加上）一個元素 ，得新效率矩陣 ， ，則 的最優(yōu)解等價于 的最優(yōu)解。第23頁，共93頁。2022/7/1624例：有一份說明書，要分別譯成英、日、德、俄四種語言，交給甲、乙、丙、丁四人去完成，各人的效率不同，如何分配任務，可使總效率最高。 人任務甲乙丙丁英文21097日文154148德文13141611俄文415139第24頁，共93頁。2022/7/1625匈牙利解法步驟：1、在效率矩陣每行減去該行最小

9、元素；2、在效率矩陣每列減去該列最小元素；第25頁，共93頁。2022/7/16263、尋找獨立“0”元素(不同行不同列）（1）從第一行開始，若該行只有一個“0”元素，則對該“0”元素打括號（ ）（表示這一行的人只有這一個任務可指派），并劃去該“0”元素所在的列（表示該項任務不能再指派給別人） ；若該行無“0”元素或有兩個以上的“0”元素（不含劃去的0），則轉下一行；（2）從第一列開始，若該列只有一個“0”元素，則對該“0”元素打括號（ ），并劃去該“0”元素所在的行；若該列無“0”元素或有兩個以上的“0”元素（不含劃去的0），則轉下一列；第26頁，共93頁。2022/7/1627（0）825

10、11（0）5423（0）001145完成上述步驟后可能出現下列情況：）效率矩陣的每一行都有一個打括號的0元素，則按照打括號的0元素位置指派任務，即是最優(yōu)解；）打括號的0元素個數小于m，但未被劃去的0元素之間存在閉回路，則沿此閉回路，每隔一個0元打一括號，然后對打括號的0元素所在行或所在列畫直線；）矩陣中所有0元素或被打括號，或被劃去，但打括號的0元素個數 ，則進入下一步；第27頁，共93頁。2022/7/16283、設法使每一行都有一個打括號的“0”元素。按定理1繼續(xù)對矩陣進行變換：）從矩陣未被直線覆蓋的元素中找出最小者k，）對矩陣中無直線覆蓋的行，令 ，有直線覆蓋的列，令 。其余為0。）對矩

11、陣的每個元素計算 ，得到一個新矩陣，轉第三步重復進行，直至每一行都有一打括號的0元素。第28頁，共93頁。2022/7/1629（0）82511（0）5423（0）001145根據上圖，k=2，最優(yōu)解：第29頁，共93頁。2022/7/1630思考：1、任務數 人數 時如何處理 2、指派問題中目標函數變?yōu)镸AX時如何處理 第30頁，共93頁。兩點說明1.效率矩陣不是方陣的情況。（即人員與工作數不相等） 處理方法：增加虛擬人或工作，使兩者相等。虛擬人或工作對應的效率矩陣中元素為0。2.最大化分配問題的處理。如果給出的效率矩陣中的數字表示每個人完成各項任務的收益，則問題變成了如何分配任務才能使總收

12、益最大.處理方法：用效率矩陣中的最大元減去矩陣中的各個元素得到一個新的矩陣，對這個新的矩陣用匈牙利方法求解。第31頁，共93頁。練習1. 用匈牙利方法求解下列問題例1：設某工程有B1,B2,B3,B4 四項任務，需由四個工人A1,A2,A3,A4去完成，由于任務性質和每個工人的技術水平不相同，他們完成各項任務所需的時間也不一樣（見下表）。問應當如何分配，即哪個人去完成哪項任務，才能使完成四項任務的總時間最少？ 任務人員B1B2B3B4A1215134A21041415A39141613A478119第32頁，共93頁。設效率矩陣：第33頁，共93頁。效率矩陣第一步：初始變換2151341041

13、415914161378119249701311260101105740142004201370606905320100第34頁，共93頁。得解矩陣找獨立0元素01370606905320100總時間為: 4+4+9+11=28第35頁，共93頁。練習2：用匈牙利解法解下列分配問題效率矩陣第一步：初始變換00000127979896667171214915146610410710912797989666717121491514661041071097676450202230000105729800406365第36頁，共93頁。50202230000105729800406365第二步：尋找獨

14、立0元素最小元素為 min10,5,7,2,6,3,6,5=2-2-2+2第37頁，共93頁。70202430000835011800404143它有5個獨立0元，得到最優(yōu)解相應的解矩陣為最優(yōu)目標值：7+6+9+6+4=32第38頁，共93頁。練習3：求解下列分配問題效率矩陣10978587754652345 工作人員ABCD甲10978乙5877丙5465丁2345第39頁，共93頁。 109785877546523457542320103221021012300013200032110200122-1-1+1第40頁，共93頁。4200021020200011420002102020001

15、1第一組最優(yōu)解第二組最優(yōu)解第41頁，共93頁。2022/7/16423 分枝定界法 分枝定界法是求解整數規(guī)劃的一種常用的有效的方法，它既能解決純整數規(guī)劃的問題，又能解決混合整數規(guī)劃的問題。 大多數求解整數規(guī)劃的商用軟件就是基于分枝定界法編制而成的。下面舉例來說明分枝定界法的思想和步驟。第42頁，共93頁。2022/7/1643性質 求MAX的問題：整數規(guī)劃的最優(yōu)目標函數值小于或等于相應的線性規(guī)劃的最優(yōu)目標函數值； 求MIN的問題：整數規(guī)劃的最優(yōu)目標函數值大于或等于相應的線性規(guī)劃的最優(yōu)目標函數值。1、求解整數規(guī)劃相應的一般線性規(guī)劃問題（即先去掉整數約束）。 易知：整數規(guī)劃的可行域（?。┌诰€性

16、規(guī)劃的可行域 (大）。 若線性規(guī)劃的最優(yōu)解恰是整數解，則其就是整數規(guī)劃的最優(yōu)解。否則該最優(yōu)解，是整數規(guī)劃最優(yōu)解的上界或下界。第43頁，共93頁。2022/7/1644例： 求解下列整數規(guī)劃：解：1、解對應的線性規(guī)劃：其最優(yōu)解為 ，顯然不是整數規(guī)劃的可行解。L0：第44頁，共93頁。2022/7/16452、分枝與定界： 將對應的線性規(guī)劃問題分解成幾個子問題，每個子問題就是一分枝，而所有子問題的解集之和要包含原整數規(guī)劃的解集。 求解每一分枝子問題： 若其最優(yōu)解滿足整數約束，則它就是原問題的一個可行解（不一定是最優(yōu)）；否則，就是該枝的上界或下界。 若所有分支的最優(yōu)解都不滿足整數條件（即不是原問題的

17、可行解），則選取一個邊界值最優(yōu)的分支繼續(xù)分解，直至找到一個原問題的可行解。 若在同一級分枝中同時出現兩個以上的原問題可行解，則保留目標值最優(yōu)的一個，其余不再考慮。從各分枝中找原問題可行解的目的是為下一步的比較與剪枝。第45頁，共93頁。2022/7/1646將上述線性規(guī)劃問題分為兩枝，并求解。解得解得L1：L2：顯然兩個分枝均非整數可行解，選邊界值較大的L1繼續(xù)分枝。 第46頁，共93頁。2022/7/1647將L1分為兩枝，并求解。解得解得L11：L12：兩個分枝均是整數可行解，保留目標值較大的L12。 第47頁，共93頁。2022/7/16483、比較與剪枝 將各子問題的邊界值與保留下的整

18、數可行解對應的目標值比較，將邊界值劣于可行行解的分支減剪去。 若比較剪枝后，只剩下所保留的整數可行解，則該解就是原整數規(guī)劃的最優(yōu)解；否則選取邊界值最大的一個分枝繼續(xù)分解，在其后的過程中出現新的整數可行解時，則與原可行解比較，保留較優(yōu)的一個，重復第三步。第48頁，共93頁。2022/7/1649L0：X22X23X13X14用圖表示上例的求解過程與求解結果第49頁，共93頁。練習1：用分支定界法求解下列整數規(guī)劃第50頁，共93頁。123123(3/2,10/3)x1=3/2,分為x11與x12SS2S1x11x12S2S1分別解之先放棄“整數”要求求出一個最優(yōu)解。第51頁，共93頁。123123

19、S1S2解S1,求出一個最優(yōu)解(2,23/9),maxz=41/9解S2,求出一個最優(yōu)解(1,7/3),maxz=10/3SS2S1x11x12(2,23/9)x2=23/9,分為x22與x23S12S11x22x23可行域為空S12S11第52頁，共93頁。123123S12(33/14,2)解S12,求出一個最優(yōu)解(33/14,2),maxz=61/14SS2S1x11x12S12S11x22x23可行域為空10/361/14S122S121x12x13x1=33/14,分為x12與x13S121S122第53頁，共93頁。123123SS2S1x11x12S12S11x22x23可行域為

20、空10/3S122S121x12x13S121S122解S121,求出一個最優(yōu)解(3,1),maxz=4解S122,求出一個最優(yōu)解(2,2),maxz=4(2,2)(3,1)44最優(yōu)整數解為(3,1)和(2,2)最優(yōu)值為4第54頁，共93頁。2022/7/16554 割平面法 一、 基本思想 在整數規(guī)劃的松弛問題中，依次引進新的約束條件（割平面），使問題的可行域逐步減小，但每次割去的只是部分非整數解，直到使問題的目標函數值達到最優(yōu)的整數點成為縮小后的可行域的一個頂點，這樣就可以用線性規(guī)劃的方法求得整數最優(yōu)解。第55頁，共93頁。2022/7/1656例： 求解下列整數規(guī)劃：解：1、解對應的線性

21、規(guī)劃（松弛問題），并將約束條件的系數均化為整數：第56頁，共93頁。2022/7/1657加入松弛變量后求解，得最終單純形表：25/2011/2-1/2313/410-1/43/400-1/4-5/4如果上述求解結果是整數解，則結束；否則轉下一步；2、找出非整數解中分數部分最大的一個基變量，并將該行對應的約束方程所有常數（系數及常數項）分解成一個整數與一個正分數之和；將所有分式項移到等式右端。例如上例，取第一行約束 第57頁，共93頁。2022/7/1658易知，左端為整數，要是等式成立，右端也必為整數，且將 代入上式，得第58頁，共93頁。2022/7/1659這就是一個割平面。將其添加到原

22、約束中，得到新的可行域如圖所示。割去的只是部分非整數解。第59頁，共93頁。2022/7/16603、將新的約束添加到原問題中，得到一個新的線性規(guī)劃問題，求解此問題，可用靈敏度分析的方法。4、重復上述的1-3步，直至求出整數最優(yōu)解。25/2011/2-1/20313/410-1/43/400-1/200-1/2-1/2100-1/4-5/40將 反應到最終表中，得第60頁，共93頁。2022/7/1661運用對偶單純形法，解得22010-11/231001-1/2010011-2000-1-1/2此解仍非整數解，將基變量 對應的約束分解為： 得到新的約束 第61頁，共93頁。2022/7/16

23、6222010-11/2031001-1/20010011-200-1/20000-1/21000-1-1/2021010-1023410010-10300110-40100001-2000-10-1此時已得整數最優(yōu)解。第62頁，共93頁。2022/7/1663約束即為第63頁，共93頁。用割平面法求解整數規(guī)劃問題解：增加松弛變量x3和x4 ，得到(LP)的初始單純形表和最優(yōu)單純形表：Cj0100CBXBbx1x2x3x40 x3632100 x40-3201Z00100Cj0100CBXBbx1x2x3x40 x11101/6-1/61x23/2011/41/4Z-3/200-1/4-1/4

24、割平面法練習1第64頁，共93頁。第65頁，共93頁。將 x3=6-3x1-2x2 , x4=3x1-2x2 ,帶入 中，得到等價的割平面條件： x2 1 見下圖。x1x233第一個割平面第66頁，共93頁。Cj01000CBXBbx1x2x3x4s10 x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41Z-3/200-1/4-1/40現將生成的割平面條件加入松弛變量，然后加到表中：CBXBbx1x2x3x4s10 x12/3100-1/32/31x21010010 x320011-4Z-10000-1第67頁，共93頁。 此時，X1 (2/3, 1)

25、, Z=1,仍不是整數解。繼續(xù)以x1為源行生成割平面，其條件為： 用上表的約束解出x4 和s1 ，將它們帶入上式得到等價的割平面條件：x1 x2 ，見圖：x1x233第一個割平面第二個割平面第68頁，共93頁。將生成的割平面條件加入松弛變量，然后加到表中：CBXBbx1x2x3x4s1s20 x12/3100-1/32/301x210100100 x320011-400s2-2/3000-2/3-2/31Z-10000-10CBXBbx1x2x3x4s1s20 x1110001-1/21x210100100 x310010-53/20 x4100011-3/2Z-10000-10第69頁，共9

26、3頁。 至此得到最優(yōu)表，其最優(yōu)解為 X= (1 , 1) , Z = 1, 這也是原問題的最優(yōu)解。 有以上解題過程可見，表中含有分數元素且算法過程中始終保持對偶可行性，因此，這個算法也稱為分數對偶割平面算法。第70頁，共93頁。割平面法練習2Cj1100CBXBbx1x2x3x40 x3621100 x4204501Z1100CBXBbx1x2x3x41 x15/3105/61/61x28/3012/31/3Z-13/3001/61/6初始表最優(yōu)表第71頁，共93頁。在松弛問題最優(yōu)解中，x1, x2 均為非整數解，由上表有：將系數和常數都分解成整數和非負真分數之和 第72頁，共93頁。 以上式

27、子只須考慮一個即可，解題經驗表明，考慮式子右端最大真分數的式子，往往會較快地找到所需割平面約束條件。以上兩個式子右端真分數相等，可任選一個考慮。現選第二個式子，并將真分數移到右邊得： 引入松弛變量s1 后得到下式，將此約束條件加到上表中，繼續(xù)求解。 第73頁，共93頁。Cj11000CBXBbx1x2x3x4s11 x15/3105/61/601x28/3012/31/300s12/3001/31/31Z13/3001/61/60Cj11000CBXBbx1x2x3x4s11 x10100101x24010120 x3200113Z400001/2 得到整數最優(yōu)解，即為整數規(guī)劃的最優(yōu)解，而且此

28、整數規(guī)劃有兩個最優(yōu)解： X= (0, 4), Z = 4, 或 X= (2, 2), Z = 4。 第74頁，共93頁。第五節(jié) 01問題第75頁，共93頁。5 0-1規(guī)劃的求解 隱枚舉法解 01 規(guī)劃的隱枚舉法有其獨特的工作程序，具體過程如下。a. 模型轉化為求極小的問題b. 變量替換。極小問題模型的目標函數中所有變量系數為負的01變量，可利用變量替換xk=1xk (xk 是引入的新的01變量)，將目標函數中所有變量系數化為正數。c. 目標函數中變量按系數大小排列，約束條件中變量排列順序也相應調整。d. 按目標函數值由小到大的順序依次排列可能的解，并予以可行性檢驗。e. 發(fā)現求極小問題的最優(yōu)解

29、并停止。f. 轉化為原問題的最優(yōu)解。 01 整數規(guī)劃是一種特殊形式的整數規(guī)劃，這時的決策變量xi 只取兩個值0或1，一般的解法為隱枚舉法。第76頁，共93頁。第77頁，共93頁。第78頁，共93頁。第79頁，共93頁。第80頁，共93頁。第81頁，共93頁。第82頁，共93頁。 1、m個約束條件只有k個起作用m個約束條件可表示為：增加變量定義為：又設M為任意大的數，則 表明：m個約束條件中有m-k個的右端項為bi+Myi，不起約束作用6 應用舉例第83頁，共93頁?！緦嵗縨axZ= 3x1 +5 x2 x1 8 2x2 12三個約束中只有兩個起作用 3x1 +4 x2 36 x1 0, x2

30、 0 引入輔助變量 模型化為：maxZ= 3x1 +5 x2 x1 8+My1 2x2 12+My2 3x1 +4 x2 36+My3 y1+y2+y3=1 x1 0, x2 0,yi只取0或1第84頁，共93頁。2、約束條件的右端可能是b1或b2br即：引入變量定義為：則原約束可表示為【例如】某約束為 2x1+5x2-x32或3引入輔助變量y1,y2, 約束化為2x1+5x2-x32y1+3y2y1+y2=1y1,y2只取0或1第85頁，共93頁。3、兩組條件滿足其中一組若x14,則 x21；否則（即x14時）， x23引入變量定義為：又M為任意大的數，則問題可表達為第86頁，共93頁。4、用以表示含固定費用的函數用xj代表產品j的生產量，其生產費用函數通?？杀硎緸椋篕j為與生產量無關的生產準備費用解決方法：設置一個邏輯變量yj，當 xj=