運(yùn)籌學(xué)教程課件-第3章-整數(shù)規(guī)劃

1、第3章 整數(shù)規(guī)劃主要介紹三種方法：1、分支定界法（branch and bound method）2、割平面法（cutting plane approach）3、匈牙利法第3章 整數(shù)規(guī)劃主要介紹三種方法：第3章 整數(shù)規(guī)劃3.1 整數(shù)規(guī)劃模型介紹3.2 分支定界法3.3 割平面法3.4 匈牙利算法第3章 整數(shù)規(guī)劃3.1 整數(shù)規(guī)劃模型介紹33.1 整數(shù)規(guī)劃模型介紹 整數(shù)規(guī)劃的一般形式（IP）問題 Max（min） z = cjxj aijxj （或=，）bi i=1，2，m xj 0 j=1，2，n xj Zs.t.（LIP）松弛問題 Max（min） z = cjxj aijxj （或=，）bi

2、 i=1，2，m xj 0 j=1，2，ns.t.33.1 整數(shù)規(guī)劃模型介紹 （IP）問題 M43.1 整數(shù)規(guī)劃模型介紹（IP）問題與（LIP）問題關(guān)系（Min）1. (IP)問題的值(LIP)問題的最優(yōu)值。2. (LIP)問題最優(yōu)解若是整數(shù)，則一定是(IP)問題的最優(yōu)解。43.1 整數(shù)規(guī)劃模型介紹53.1 整數(shù)規(guī)劃模型介紹整數(shù)規(guī)劃分類純整數(shù)線性規(guī)劃：決策變量都取整數(shù)值。混合整數(shù)線性規(guī)劃：決策變量中一部分取整數(shù)值，另一部分可以不取整數(shù)值。0-1整數(shù)線性規(guī)劃：決策變量只能取值 0 或 1 。 53.1 整數(shù)規(guī)劃模型介紹整數(shù)規(guī)劃分類63.1 整數(shù)規(guī)劃模型介紹整數(shù)規(guī)劃引例背包問題廠址選擇問題 組合投

3、資問題（見教材107-108頁(yè)） Return63.1 整數(shù)規(guī)劃模型介紹整數(shù)規(guī)劃引例7 3.2 分支定界法 分支定界法是一種隱枚舉方法或部分枚舉方法，是枚舉方法基礎(chǔ)上的改進(jìn)，是組合優(yōu)化重要方法。其關(guān)鍵是分支和定界。例1 Min Z = -2X1 -3X2 5X1 +7X2 35 4X1 + 9X2 36 X1 ，X2 0 X1 ，X2 Z7 3.2 分支定界法 分支定界8解：先求相應(yīng)線性規(guī)劃的最優(yōu)解，為：取 分割可行域，得到子問題Sub-1, Sub-2： 3.2 分支定界法Sub-2 min z=-2x1-3x2 5x1+7x235 4x1+9x236 x2 3 x1 x2 0Sub-1 m

4、in z=-2x1-3x2 5x1+7x235 4x1+9x236 x22 x1 x2 08解：先求相應(yīng)線性規(guī)劃的最優(yōu)解，為： 3.2 分9 3.2 分支定界法Sub-1的最優(yōu)解為：取 分割可行域，得到兩個(gè)子問題Sub-3, Sub-4 ：Sub-3 min z=-2x1-3x2 5x1+7x235 4x1+9x236 x22 x1 4 x1 x2 0Sub-4 min z=-2x1-3x2 5x1+7x235 4x1+9x236 x2 2 x1 5 x1 x2 09 3.2 分支定界法Sub-1的最優(yōu)解為：S10 3.2 分支定界法Sub-3的最優(yōu)解為：獲得整數(shù)解，取得上界 ，停止分枝！10

5、 3.2 分支定界法Sub-3的最優(yōu)解為：11 3.2 分支定界法Sub-4的最優(yōu)解為：Sub-6 min z=-2x1-3x2 5x1+7x235 4x1+9x236 x22 x1 5 x2 2 x1 x2 0Sub-5 min z=-2x1-3x2 5x1+7x235 4x1+9x236 x22 x1 5 x21 x1 x2 0取 分割可行域，得到兩個(gè)子問題： Sub-5, Sub-611 3.2 分支定界法Sub-4的最優(yōu)解為：12 3.2 分支定界法Sub-5的最優(yōu)解為：取 分割可行域，得到兩個(gè)子問題： Sub-7, Sub-8Sub-7 min z=-2x1-3x2 5x1+7x23

6、5 4x1+9x236 x2 2 x1 5 x2 1 x1 5 x1 x2 0Sub-8 min z=-2x1-3x2 5x1+7x235 4x1+9x236 x2 2 x1 5 x2 1 x1 6 x1 x2 012 3.2 分支定界法Sub-5的最優(yōu)解為：13 3.2 分支定界法Sub-6的可行域是空集，停止分枝。Sub-7的最優(yōu)解為：獲得整數(shù)解，停止分枝！由于上界仍保持為13 3.2 分支定界法Sub-6的可行域是空集14 3.2 分支定界法Sub-8的最優(yōu)解為：取 分割可行域，得到兩個(gè)子問題： Sub-9, Sub-10Sub-10 min z=-2x1-3x2 5x1+7x235 4

7、x1+9x236 x22 x15 x21 x16 x21 x1 x2 0Sub-9 min z=-2x1-3x2 5x1+7x235 4x1+9x236 x22 x15 x21 x16 x20 x2 014 3.2 分支定界法Sub-8的最優(yōu)解為：15 3.2 分支定界法Sub-9的最優(yōu)解為：獲得整數(shù)解，停止分枝！由于上界仍保持為15 3.2 分支定界法Sub-9的最優(yōu)解為：16 3.2 分支定界法Sub-10的可行域是空集，停止分枝!16 3.2 分支定界法17 3.2 分支定界法Sub-2的最優(yōu)解為： ，停止分支！17 3.2 分支定界法Sub-2的最優(yōu)解為：18 3.2 分支定界法至此已

8、將所有可能分解的子問題都已分解到底，最后得到兩個(gè)目標(biāo)函數(shù)值相等的最優(yōu)整數(shù)解： （x1，x2）=（4，0）和（x1，x2）=(0，7) 他們的目標(biāo)函數(shù)值都是-14。Return原問題Sub-1Sub-2Sub-3Sub-4Sub-5Sub-6Sub-7Sub-8Sub-9Sub-10剪枝(4,2)，-14(5,1)，-13無(wú)可行解(7,0)，-14無(wú)可行解18 3.2 分支定界法Return原問題Su193.3 割平面法割平面法思想 求解(IP)的松馳問題(LIP)：若最優(yōu)解 X* Z，則從 X* 的非整分量中選取一個(gè)構(gòu)造線性約束（Gomory 割平面），將其加入原(LIP)問題，形成一個(gè)新的線

9、性規(guī)劃并求解， （重復(fù)），直至得到整數(shù)最優(yōu)解。 關(guān)鍵：新增的線性約束將切割掉部分非整數(shù)解，至少切割掉當(dāng)前松馳問題的非整數(shù)最優(yōu)解，而不會(huì)切割掉問題的任何整數(shù)解!193.3 割平面法203.3 割平面法 構(gòu)造割平面的步驟：1、令 xi 是(LIP)問題最優(yōu)解中非整數(shù)值的一個(gè)基變量，得： xi + aik xk = bi （1）其中，k B （B：非基變量下標(biāo)集）203.3 割平面法213.3 割平面法構(gòu)造割平面的步驟：2、將 bi 和 aik 分解成整數(shù)部分 I（不超過 b 的最大整數(shù)）與非負(fù)真分?jǐn)?shù)部分 F 之和： bi = Ii + Fi ，其中 0 Fi 1.(2 ) aik = Iik +

10、Fik ，其中 0 Fik 1213.3 割平面法構(gòu)造割平面的步驟：223.3 割平面法 構(gòu)造割平面的步驟：3、將（2）代入（1）： xi + Iik xk - Ii = Fi - Fik xk （3）4、割平面方程： Fi - Fik xk 0 （4 ）！將（4）加入原來(LIP)問題繼續(xù)求解。223.3 割平面法 構(gòu)造割平面的步驟：23 3.3 割平面法例2 用割平面法求解下列整數(shù)規(guī)劃。IP Min Z = 3X1 + 4X2 3X1 + X2 4 X1 + 2X2 4 X1 ，X2 0 X1 ，X2 Z LIP Min Z = 3X1 + 4X2 3X1 + X2 4 X1 + 2X2

11、4 X1 ，X2 0 23 3.3 割平面法例2 用割平面法求解下列24 3.3 割平面法解:（1）先求解線性規(guī)劃問題（LIP），得到最優(yōu)單純形表：Cj3400I 表CBXBB 1 bX1X2X3X40X3431-100X44120-1j03400B 表1X14/510-2/51/51X28/5011/5-3/5j44/500-2/5-9/524 3.3 割平面法解:（1）先求解線性規(guī)劃25 3.3 割平面法(2)選擇一個(gè)非整數(shù)的基變量，例如x2=8/5，構(gòu)造割平面。增加松弛變量x5后將這個(gè)約束加到線性規(guī)劃的最優(yōu)單純形表，得到b2=8/5=1+3/5，I2=1，F(xiàn)2=3/5a23=1/5=0+

12、1/5，I23=0，F(xiàn)23=1/5a24=-3/5=-1+2/5，I24=-1，F(xiàn)24=2/525 3.3 割平面法(2)選擇一個(gè)非整數(shù)的基26 3.3 割平面法(3)求解新的松弛問題Cj110001 表CBXBB 1 bX1X2X3X4X51X14/510-2/51/501X28/5011/5-3/500X5- 3/500- 1/5- 11j44/500- 2/5- 9/502 表1X121001- 21X21010- 110X330012- 5j10000- 1- 226 3.3 割平面法(3)求解新的松弛問題C27 3.3 割平面法整數(shù)規(guī)劃最優(yōu)解線性規(guī)劃 最優(yōu)解切割約束最優(yōu)解：x1=2,

13、 x2=1Return27 3.3 割平面法整數(shù)規(guī)劃最優(yōu)解線性規(guī)劃283.4 匈牙利算法0-1 變量 只取0或1，常被用來表示系統(tǒng)是否處于某個(gè)特定的狀態(tài)，或者是否取某個(gè)特定的決策方案。如xj = 1 當(dāng)方案 S j被選中0 否則283.4 匈牙利算法0-1 變量xj = 1 293.4 匈牙利算法0-1整數(shù)規(guī)劃例3 選址問題 WAL-MART擬在常州的天寧、鐘樓、新區(qū)建立分店，有 7 個(gè)位置（地點(diǎn)）Ai（i=1，2，7）供選擇。總部規(guī)定 在天寧，由 A1，A2，A3 三個(gè)點(diǎn)中至多選兩個(gè)； 在鐘樓，由 A4，A5 兩個(gè)點(diǎn)中至少選一個(gè)； 在新區(qū)，由 A6，A7 兩個(gè)點(diǎn)中至少選一個(gè)。 如果選 Ai

14、點(diǎn)，設(shè)備投資為 ai 元，每年可獲利潤(rùn)為 ci 元，但投資總額不能超過A元。問公司選擇哪幾個(gè)點(diǎn)可使年總利潤(rùn)最大？293.4 匈牙利算法0-1整數(shù)規(guī)劃303.4 匈牙利算法解：建立模型 引入 0-1 變量 1 當(dāng) Ai 點(diǎn)被選用 0 否則xi =（i=1，2，7）max z = cixi aixi A x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 xi 0，1303.4 匈牙利算法解：建立模型 1313.4 匈牙利算法例4 指派問題（assignment problem） 有 n 個(gè)人和 n 件事，已知第 i 人做第 j 事的費(fèi)用為 cij（i，j = 1，2，n），要求

15、確定人和事之間的一一對(duì)應(yīng)的指派方案，使完成這件事的總費(fèi)用最少。如任務(wù)人員ABCD甲乙丙丁3129714414813171611415139313.4 匈牙利算法例4 指派問題（assignme323.4 匈牙利算法解：建立模型 令 1 當(dāng)指派第 i 人完成第 j 項(xiàng)任務(wù) 0 否則xij =min z = cijxij xij = 1， j = 1，2，n xij = 1， i = 1，2，n xij 0， 1323.4 匈牙利算法解：建立模型 333.4 匈牙利算法匈牙利算法 1955年，庫(kù)恩（W.W.Kuhn）利用匈牙利數(shù)學(xué)家康尼格（D.Knig）的關(guān)于矩陣中獨(dú)立零元素的定理，提出了求解指派

16、問題算法匈牙利算法。333.4 匈牙利算法343.4 匈牙利算法 【性 質(zhì)】 若從指派問題的系數(shù)矩陣 C = （ cij ）nn 的某行（或某列）各元素分別減去一個(gè)常數(shù) k ，得到一個(gè)新的系數(shù)矩陣C = （ cij ）則以 C 和 C 為系數(shù)矩陣的兩個(gè)指派問題有相同的最優(yōu)解。343.4 匈牙利算法353.4 匈牙利算法算法步驟（1） 變換系數(shù)矩陣C，使每行及每列至少有一個(gè)零元素，同時(shí)不出現(xiàn)負(fù)元素。（2） 確定獨(dú)立零元素組。若|獨(dú)立零元素組|=n，結(jié)束；否則，轉(zhuǎn)步驟（3）。（3） 繼續(xù)變換系數(shù)矩陣，然后返回步驟（2）。353.4 匈牙利算法363.4 匈牙利算法例5 求解下列指派問題（教材121

17、頁(yè)）。 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 0 13 11 2 6 0 10 11 0 5 7 4 0 1 4 22497min（ cij ）=363.4 匈牙利算法例5 求解下列指派問題（教材121373.4 匈牙利算法例5（續(xù)） 0 13 11 2 6 0 10 11 0 4 7 4 0 1 4 2 0 0 4 2min 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0= （ cij ）373.4 匈牙利算法例5（續(xù)） 0 383.4 匈牙利算法例5（續(xù)） 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0此時(shí)圈

18、0 元素的個(gè)數(shù) m = n = 4.383.4 匈牙利算法例5（續(xù)） 0 393.4 匈牙利算法例5（續(xù)） 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0（ xij ）=最優(yōu)分配：393.4 匈牙利算法例5（續(xù)） 0 403.4 匈牙利算法例6 求下列指派問題（教材122頁(yè)）。任務(wù)人員ABCDE甲乙丙丁戊1287154791714109612677614610969109403.4 匈牙利算法例6 求下列指派問題（教材122413.4 匈牙利算法例6（續(xù)）解： 12 7 9 7 9 8 9 6 6 6 7 17 12 14 9 15 14 6 6 10 4 10 7 10 97

19、6764 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5413.4 匈牙利算法例6（續(xù)） 12 7 423.4 匈牙利算法例6（續(xù)） 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5 此時(shí)圈 0 元素（獨(dú)立零元素）的個(gè)數(shù) m = 4n = 5，不能確定最優(yōu)指派方案！ 需要繼續(xù)變換系數(shù)矩陣，以增加獨(dú)立零元素個(gè)數(shù)。方法如下：423.4 匈牙利算法例6（續(xù)） 5 0433.4 匈牙利算法例6（續(xù)）對(duì)未加圈0的行打號(hào)；對(duì)所有打號(hào)行的所有含0的列打號(hào)；對(duì)已打號(hào)的列中含0的行打號(hào)；重復(fù)2)和3)，直到

20、無(wú)可以打號(hào)行或列為止；對(duì)未打號(hào)的行畫一橫線，對(duì)打號(hào)的列畫一豎線，即得能覆蓋所有0的最少直線數(shù)目的直線集合。433.4 匈牙利算法例6（續(xù)）對(duì)未加圈0的行打號(hào)；443.4 匈牙利算法例6（續(xù)） 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5443.4 匈牙利算法例6（續(xù)） 5 0453.4 匈牙利算法例6（續(xù)）繼續(xù)變換系數(shù)矩陣： 在未被直線覆蓋的元素中找出一個(gè)最小元素 在打號(hào)行各元素都減去這一最小元素，在打號(hào)列的各元素都加上這一最小元素（以保證 0 元素不變），得新系數(shù)矩陣。 若得到 n 個(gè)獨(dú)立的 0 元素，則獲最優(yōu)解；否則，重復(fù)上步驟繼續(xù)變換系數(shù)矩陣。453.4 匈牙利算法例6（續(xù)）463.4 匈牙利算法例6（續(xù)） 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5最小元素= 2 7 0 2 0 2 4 3 0 0 0 0 8 3 5 0 11 8 0