第六章_整數(shù)規(guī)劃(1)

1、運(yùn)運(yùn) 籌籌 帷帷 幄幄 之之 中中決決 勝勝 千千 里里 之之 外外整數(shù)規(guī)劃整數(shù)規(guī)劃運(yùn)籌學(xué)教學(xué)要求教學(xué)要求 重點(diǎn)掌握指派問題的建模與求解重點(diǎn)掌握指派問題的建模與求解。 掌握掌握線性整數(shù)規(guī)劃的建模方法，特別是0-1變量的運(yùn)用；掌握掌握分支定界求解方法的基本原理；了解了解割平面求解方法的基本原理；p整數(shù)規(guī)劃建模整數(shù)規(guī)劃建模 p分枝定界法分枝定界法 p割平面法割平面法p指派問題指派問題 重點(diǎn)：分枝定界、隱枚舉法重點(diǎn)：分枝定界、隱枚舉法難點(diǎn)：分枝定界法、指派問題求解難點(diǎn)：分枝定界法、指派問題求解第一節(jié)第一節(jié) 整數(shù)規(guī)劃實(shí)例與模型整數(shù)規(guī)劃實(shí)例與模型第二節(jié)第二節(jié) 0 01 1整數(shù)規(guī)劃的建模方法整數(shù)規(guī)劃的建模

2、方法第三節(jié)第三節(jié) 分支定界法分支定界法第四節(jié)第四節(jié) 割平面法割平面法第五節(jié)第五節(jié) 指派問題指派問題第六節(jié)第六節(jié) 應(yīng)用舉例和應(yīng)用舉例和ExcelExcel求解求解目目 錄錄p在現(xiàn)實(shí)生活中，經(jīng)常遇到一些需要變量取整數(shù)才有實(shí)際意義的問題，例如制定計(jì)劃、規(guī)劃時(shí)需要確定工人的人數(shù)，設(shè)備的臺(tái)數(shù)等。p許多有名的最優(yōu)化問題，如旅行商問題、背包問題、下料問題、工序安排問題等，也都可以歸結(jié)為整數(shù)規(guī)劃問題。第一節(jié)整數(shù)規(guī)劃實(shí)例與模第一節(jié)整數(shù)規(guī)劃實(shí)例與模型型某工廠準(zhǔn)備備用集裝箱托運(yùn)甲、乙兩種貨物，已知，每箱貨物的體積、利潤、重量、托運(yùn)限制如下表，問甲乙兩種貨物各托運(yùn)多少箱才能使總利潤最大？一、實(shí)例一、實(shí)例1貨物每箱體積

3、 每箱重量 每箱利潤甲5220乙4510托運(yùn)限制2413解：設(shè)甲乙兩種貨物各托運(yùn)x1,x2箱，依題意得：Max z=20 x1+10 x2s.t 5x1+4x224 2x1+5x2 13 x1,x20 x1,x2取整數(shù)第一節(jié)整數(shù)規(guī)劃實(shí)例與模第一節(jié)整數(shù)規(guī)劃實(shí)例與模型型 現(xiàn)有一位于城市B5的工廠，其年生產(chǎn)量是30000件，產(chǎn)品被運(yùn)往A1，A2，A3三個(gè)城市的銷售中心。經(jīng)預(yù)測該廠產(chǎn)品的需求量將會(huì)增長，工廠決定將在B1，B2，B3，B4四個(gè)城市中的一個(gè)或多個(gè)城市中新建工廠以增加生產(chǎn)力。綜合考慮在這四個(gè)城市中新建工廠的年固定成本和生產(chǎn)能力，以及每件產(chǎn)品從每個(gè)工廠送到每個(gè)銷售中心的運(yùn)費(fèi)。問如何選擇新的廠址

4、，才能使該工廠每年的總成本最小。第一節(jié)整數(shù)規(guī)劃實(shí)例與模第一節(jié)整數(shù)規(guī)劃實(shí)例與模型型一、實(shí)例一、實(shí)例2生產(chǎn)地銷售中心年固定成本年生產(chǎn)力(千件)A1A2A3B152317510B243430020B397537530B4104250040B5843需求量302020B1B2B3B4B5A3A2A11020304030202030第一節(jié)整數(shù)規(guī)劃實(shí)例與模第一節(jié)整數(shù)規(guī)劃實(shí)例與模型型總成本年固定成本運(yùn)輸成本第一節(jié)整數(shù)規(guī)劃實(shí)例與模第一節(jié)整數(shù)規(guī)劃實(shí)例與模型型首先做如下假設(shè)：首先做如下假設(shè)： 如果在如果在B B1 1建新廠，建新廠，y y1 1=1=1；否則，；否則，y y1 1=0=0。 如果在如果在B B2

5、2建新廠，建新廠，y y2 2=1=1；否則，；否則，y y2 2=0=0。 如果在如果在B B3 3建新廠，建新廠，y y3 3=1=1；否則，；否則，y y3 3=0=0。 如果在如果在B B4 4建新廠，建新廠，y y4 4=1=1；否則，；否則，y y4 4=0=0。 x xij ij：表示從工廠：表示從工廠i i 到銷售中心到銷售中心j j的運(yùn)輸量；的運(yùn)輸量；i=1,i=1,5,5；j=1,2,3j=1,2,3。 利用已知的數(shù)據(jù)，年運(yùn)輸成本為：利用已知的數(shù)據(jù)，年運(yùn)輸成本為： TCTC1 1=5x=5x11 11+2x+2x1212+3x+3x1313+4x+4x2121+3x+3x2

6、222+4x+4x2323+9x+9x3131+7x+7x3232 +5x+5x3333+10 x+10 x4141+4x+4x4242+2x+2x4343+8x+8x5151+4x+4x5252+3x+3x5353TCTC2 2=175y=175y1 1+300y+300y2 2+375y+375y3 3+500y+500y4 4；總成本為：總成本為：TC=TCTC=TC1 1+TC+TC2 2；生產(chǎn)能力的約束條件為：生產(chǎn)能力的約束條件為：從新工廠從新工廠B B1 1運(yùn)到運(yùn)到A A1 1，A A2 2，A A3 3三個(gè)城市銷售中心的總量應(yīng)小于等三個(gè)城市銷售中心的總量應(yīng)小于等于于B B1 1的

7、生產(chǎn)能力，所以約束條件為：的生產(chǎn)能力，所以約束條件為： x x11 11+x+x1212+x+x131310y10y1 1 B B1 1的生產(chǎn)能力；的生產(chǎn)能力；同理可得：同理可得：x x2121+x+x2222+x+x232320y20y2 2 B B2 2的生產(chǎn)能力；的生產(chǎn)能力；x x3131+x+x3232+x+x333330y30y3 3 B B3 3的生產(chǎn)能力；的生產(chǎn)能力；x x4141+x+x4242+x+x434340y40y4 4 B B4 4的生產(chǎn)能力；的生產(chǎn)能力；x x5151+x+x5252+x+x535330 B30 B5 5的生產(chǎn)能力；的生產(chǎn)能力；三個(gè)銷售中心的需求量為

8、：三個(gè)銷售中心的需求量為：x x11 11+x+x2121+x+x3131+x+x4141+x+x5151=30 A=30 A1 1的需求量；的需求量；x x1212+x+x2222+x+x3232+x+x4242+x+x5252=20 A=20 A2 2的需求量；的需求量；x x1313+x+x2323+x+x3333+x+x4343+x+x5353=20 A=20 A3 3的需求量；的需求量；建新工廠的年固定成本為：建新工廠的年固定成本為：所以選址模型為：所以選址模型為： min TC= TCmin TC= TC1 1+TC+TC2 2s.ts.tx x11 11+x+x1212+x+x1

9、31310y10y1 1 x x2121+x+x2222+x+x232320y20y2 2 x x3131+x+x3232+x+x333330y30y3 3 x x4141+x+x4242+x+x434340y40y4 4 x x5151+x+x5252+x+x53533030 x x11 11+x+x2121+x+x3131+x+x4141+x+x5151=30=30 x x1212+x+x2222+x+x3232+x+x4242+x+x5252=20=20 x x1313+x+x2323+x+x3333+x+x4343+x+x5353=20=20 x xij ij00，對所有的，對所有的i

10、 i，j j； y y1 1，y y2 2，y y3 3，y y4 4=0=0，1 1 第一節(jié)整數(shù)規(guī)劃實(shí)例與模第一節(jié)整數(shù)規(guī)劃實(shí)例與模型型nixbbbxatsxciniiiniii,2, 1 ,0 ) ( .min)max(11且為整數(shù)或部分為整數(shù)或或或第一節(jié)整數(shù)規(guī)劃實(shí)例與模第一節(jié)整數(shù)規(guī)劃實(shí)例與模型型二、整數(shù)規(guī)劃一般模型二、整數(shù)規(guī)劃一般模型如果決策變量全部為整數(shù)，則稱為純整數(shù)規(guī)劃部分決策變量是整數(shù)，其他變量可以是非整數(shù)，則稱為混合整數(shù)規(guī)劃如果變量僅取0或1，此時(shí)的整數(shù)規(guī)劃稱為 0-1規(guī)劃，是整數(shù)規(guī)劃的特殊情況整數(shù)規(guī)劃模型是一類特殊的線性規(guī)劃模型，但用求解線性規(guī)劃模型的單純形法所得到的最優(yōu)解往往不

11、能保證其一定是整數(shù)。解相應(yīng)的線性規(guī)劃問題得到最優(yōu)解之后，采用最優(yōu)解湊整的方法，往往得不到整數(shù)規(guī)劃的最優(yōu)解，甚至得不到可行解第一節(jié)整數(shù)規(guī)劃實(shí)例與模第一節(jié)整數(shù)規(guī)劃實(shí)例與模型型Max z=20 x1+10 x2s.t 5x1+4x224 2x1+5x2 13 x1,x20,且為整數(shù)Max z=20 x1+10 x2s.t 5x1+4x224 2x1+5x2 13 x1,x20通過單純法可求得最優(yōu)解為x1=4.8,x2=0 maxz=96若采用湊整的方法得 X1=5 x2=0 根本不是原整數(shù)規(guī)劃的可行解(2) x1=4 x2=0 z=80 不是整數(shù)規(guī)劃的最優(yōu)解實(shí)際上原問題的最優(yōu)解為X1=4,x2=1

12、max z=90將將x1,x2取取整條件去掉整條件去掉第一節(jié)整數(shù)規(guī)劃實(shí)例與模第一節(jié)整數(shù)規(guī)劃實(shí)例與模型型用窮舉法求解：Max z=20 x1+10 x2s.T 5x1+4x224 2x1+5x2 13 x1,x20,且為整數(shù)解：在 中令x2=0 得 x124/5=4 x1 13/2=6 x1 4所以 x1 只能取 0,1,2,3,4同理 在 中令x1=0 得 0 x2 2故 x2只能取0,1,2第一節(jié)整數(shù)規(guī)劃實(shí)例與模第一節(jié)整數(shù)規(guī)劃實(shí)例與模型型點(diǎn)點(diǎn)條件條件可行解可行解Z值值(0,0)0(0,1)10(0,2)20(1,0)20(1,1)30(1,2)40(2,0)40(2,1)50(2,2)1(3

13、,0)60(3,1)70(3,2)1(4,0)80(4,1)90(4,2)第一節(jié)整數(shù)規(guī)劃實(shí)例與模第一節(jié)整數(shù)規(guī)劃實(shí)例與模型型第二節(jié)第二節(jié) 01整數(shù)規(guī)劃的建模方法整數(shù)規(guī)劃的建模方法 一、 0-1整數(shù)規(guī)劃 在整數(shù)規(guī)劃中，如果變量只能取0,1兩個(gè)數(shù)，稱整數(shù)規(guī)劃為0-1整數(shù)規(guī)劃 在現(xiàn)實(shí)世界中存在許多具有組合特性的以及涉及是或非決策的最優(yōu)化問題，這些問題都可歸結(jié)為0-1整數(shù)規(guī)劃例 某公司擬在市東西南三區(qū)建立門市部，擬議中有7個(gè)位置Ai(i=1,27)可供選擇，規(guī)定（1）在東區(qū)A1,A2,A3三個(gè)點(diǎn)中至多選兩個(gè)（2）在西區(qū)A4,A5兩個(gè)點(diǎn)中至少選一個(gè)（3）在南區(qū)A6,A7兩個(gè)點(diǎn)中至少選一個(gè)如果用Ai點(diǎn)，設(shè)備

14、投資估計(jì)了bi元，每年可獲利估計(jì)為ci元，但投資額不超過B元，問應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤最大？解，引入0-1變量,xi(i=1,27)，令Xi=1，表示Ai點(diǎn)被選用0，表示Ai點(diǎn)沒被選用第二節(jié)第二節(jié) 01整數(shù)規(guī)劃的建模方法整數(shù)規(guī)劃的建模方法X1+x2+x32 X4+x5 1 X6+x7 1 b1x1+b2x2+b3x3+b7x7Bmax Z=c1x1+c2x2+c3x3+c7x7s.t. b1x1+b2x2+b3x3+b7x7B X1+x2+x32 X4+x5 1 X6+x7 1 Xi=0或1 i=1,27第二節(jié)第二節(jié) 01整數(shù)規(guī)劃的建模方法整數(shù)規(guī)劃的建模方法實(shí)例：某電冰箱廠正在考慮隨后4年內(nèi)

15、有不同資金要求的投資方案。面對每年有限的資金，工廠領(lǐng)導(dǎo)需要選擇最好的方案，使資金預(yù)算方案的當(dāng)前估算凈值最大化。每種方案的現(xiàn)金估算凈值（現(xiàn)金估算凈值為第一年開始時(shí)的凈現(xiàn)金流的值）、資金需求和4年內(nèi)擁有的資金見下表：擴(kuò)建廠房 擴(kuò)建倉庫 更新機(jī)器 新產(chǎn)品研制現(xiàn)值90401037總可用成本第1年資金1510101540第2年資金20151050第3年資金20201040第4年資金15541035項(xiàng)目（千元）第二節(jié)第二節(jié) 01整數(shù)規(guī)劃的建模方法整數(shù)規(guī)劃的建模方法 x1表示擴(kuò)建工廠的變量，=1表示擴(kuò)建工廠，0表示不擴(kuò)建 同理，變量x2,x3,x4依次表示擴(kuò)建倉庫、更新機(jī)器、新產(chǎn)品研制。變變 量量第1年的可

16、用資金為40千元，所以相應(yīng)的約束條件為：同理得到后三年的約束條件。約束條件約束條件40151010154321xxxx當(dāng)前估算凈值最大，即max 目標(biāo)函數(shù)目標(biāo)函數(shù)432137104090 xxxx擴(kuò)建倉庫 更新機(jī)器 新產(chǎn)品研制現(xiàn)值90401037總可用成本第1年資金1510101540第2年資金20151050第3年資金20201040第4年資金15541035項(xiàng)目（千元）第二節(jié)第二節(jié) 01整數(shù)規(guī)劃的建模方法整數(shù)規(guī)劃的建模方法擴(kuò)建廠房可得上例的模型Max z=90 x1+40 x2+10 x3+37x4s.t. 15x1+10 x2+10 x3+15x440 20 x1+15x2 +10 x4

17、50 20 x1+20 x2 +10 x440 15x1+5x2 +4x3 +10 x435 xi=0,1 (i=1,2,3,4)第二節(jié)第二節(jié) 01整數(shù)規(guī)劃的建模方法整數(shù)規(guī)劃的建模方法njxmibxcxczjnjijijnjjj, 2 , 1, 10, 2 , 1, min11或必須 必須大于等于0 解法解法p 全枚舉法 p隱枚舉法標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型二、 01整數(shù)規(guī)劃的標(biāo)準(zhǔn)型和解法整數(shù)規(guī)劃的標(biāo)準(zhǔn)型和解法第二節(jié)第二節(jié) 01整數(shù)規(guī)劃的建模方法整數(shù)規(guī)劃的建模方法p（1 1）令全部都是自由變量且取0值，檢驗(yàn)解是否可行。若可行，已得最優(yōu)解；若不可行，進(jìn)行步驟（2）。p（2 2）將某一變量轉(zhuǎn)為固定變量，令其取值

18、為1或0，使問題分成兩個(gè)子域。令一個(gè)子域中的自由變量都取0值，加上固定變量取值，組成此子域的解。p（3 3）計(jì)算此解的目標(biāo)函數(shù)值，與已求出的可行解最小目標(biāo)函數(shù)值比較。如果前者大，則不必檢驗(yàn)其是否可行而停止分枝，若子域都檢驗(yàn)過，轉(zhuǎn)步驟（7），否則轉(zhuǎn)步驟（6）。因繼續(xù)分枝即使得到可行解，其目標(biāo)函數(shù)值也較大，不會(huì)是最優(yōu)解；如前者小，進(jìn)行步驟（4）。對第一次算出的目標(biāo)函數(shù)值，不必進(jìn)行比較，直接轉(zhuǎn)到步驟（4）。p（4 4）檢驗(yàn)解是否可行。如可行，已得一個(gè)可行解，計(jì)算并記下它的z值，并停止分枝，若子域都檢驗(yàn)過，轉(zhuǎn)步驟（7），否則轉(zhuǎn)步驟（6）。因繼續(xù)分枝，即使得到可行解，目標(biāo)函數(shù)值也比記下的z值大，不會(huì)是最

19、優(yōu)解；如不可行，進(jìn)行步驟（5）。隱枚舉法求解步驟（一）隱枚舉法求解步驟（一）p（5 5）將子域固定變量的值代入第一個(gè)不等式約束條件方程，并令不等式左端的自由變量當(dāng)系數(shù)為負(fù)時(shí)取值為1，系數(shù)為正時(shí)取值為0，這就是左端所能取得最小值。若此最小值大于右端值，則稱此子域?yàn)椴豢尚凶佑虿豢尚凶佑?，不再往下分枝，若此最小值小于右端值，則依次檢驗(yàn)下一個(gè)不等式約束方程，直至所有的不等式約束方程都通過，若子域都檢驗(yàn)過，轉(zhuǎn)步驟（7），否則，轉(zhuǎn)步驟（6）。p（6 6）定出尚未檢驗(yàn)過的另一個(gè)子域的解，執(zhí)行步驟（3）（5），若所有子域都停止分枝，計(jì)算停止，目標(biāo)函數(shù)值最小的可行解就是最優(yōu)解；否則，轉(zhuǎn)（7）。p（7 7）檢查有

20、無自由變量。若有，轉(zhuǎn)（2）；如沒有，計(jì)算停止。目標(biāo)函數(shù)值最小的可行解就是最優(yōu)解。隱枚舉法求解步驟（一）隱枚舉法求解步驟（一）第二節(jié)第二節(jié) 01整數(shù)規(guī)劃的建模方法整數(shù)規(guī)劃的建模方法. , 10423523233 s.t.57428min543215432154321jxxxxxxxxxxxxxxxxzj對一切或(0,0,0,0,0)(0,1,0,0,0)(0,1,0,1,0)(0,1,0,0,0)(0,1,1,0,0)(0,0,0,0,0)(0,1,0,0,0)(0,0,0,0,0)(1,0,0,0,0)說明：說明： 彩色字體為固定變量。Z1=8，可行，停止分支。Z2=0 Z1 ，不可行；可行子

21、域，分支。Z3=2 Z1 ，不可行，可行子域，分支。Z4=0 Z1 ，不可行，不可行子域，停止分支。Z5=6 Z1 ，可行，停止分支。Z6=2 Z5 ，停止分支。Z8=2Z0，則將過濾條件換成ZZ1 一般地，過濾條件是所有約束條件中關(guān)鍵的一個(gè)，因而先檢查它是否滿足，如不滿足，其他約束條件也就不再檢查了(不論這個(gè)變量的組合是否是可行解，對我們都沒有用)這樣也就減少了計(jì)算工作量第二節(jié)第二節(jié) 01整數(shù)規(guī)劃的建模方法整數(shù)規(guī)劃的建模方法利用隱枚舉法求解下面的0-1整數(shù)規(guī)劃第二節(jié)第二節(jié) 01整數(shù)規(guī)劃的建模方法整數(shù)規(guī)劃的建模方法Max z=3x1-2x2+5x3 s.t x1+2x2-x3 2 x1+4x2

22、+x3 4 x1+ x2 3 4x2+x3 6 xi=0,1 i=1,2,3點(diǎn)點(diǎn)過濾條件過濾條件條件條件滿足滿足條件條件Z值值3x1-2x2+5x3 3(0,0,0)(0,0,1)53x1-2x2+5x3 5(0,1,0)(0,1,1)(1,0,0)(1,0,1)83x1-2x2+5x3 8(1,1,0)(1,1,1)即最優(yōu)解為(1,0,1)T，最優(yōu)值為8Max z=3x1-2x2+5x3 s.t x1+2x2-x3 2 x1+4x2+x3 4 x1+ x2 3 4x2+x3 6 xi=0,1 i=1,2,3第二節(jié)第二節(jié) 01整數(shù)規(guī)劃的建模方法整數(shù)規(guī)劃的建模方法利用隱枚舉法求解下面的0-1整數(shù)

23、規(guī)劃min z=3x1-2x2+5x3 s.t x1-2x2-x3 -2 x1+x2+x3 4 x1-4x2 -3 xi=0,1 i=1,2,3 第二節(jié)第二節(jié) 01整數(shù)規(guī)劃的建模方法整數(shù)規(guī)劃的建模方法點(diǎn)點(diǎn)過濾條件過濾條件條件條件滿足滿足條件條件Z值值3x1-2x2+5x3 6(1,1,1)6(1,1,0)(1,0,1)(1,0,0)(0,1,1)33x1-2x2+5x3 3(0,1,0)-23x1-2x2+5x3 -2(0,0,1)(0,0,0)min z=3x1-2x2+5x3 s.t x1-2x2-x3 -2 x1+x2+x3 4 x1-4x2 -3 xi=0,1 i=1,2,3 即最優(yōu)解

24、為(0,1,0)T，最優(yōu)值為-2第二節(jié)第二節(jié) 01整數(shù)規(guī)劃的建模方法整數(shù)規(guī)劃的建模方法 分支定界法的主要思路是首先求解整數(shù)規(guī)劃的伴隨規(guī)劃，如果求得的最優(yōu)解不符合整數(shù)條件，則增加新約束縮小可行域；將原整數(shù)規(guī)劃問題分枝分成兩個(gè)子規(guī)劃，再解子規(guī)劃的伴隨規(guī)劃、通過求解一系列子規(guī)劃的伴隨規(guī)劃及不斷地定界，最后得到原整數(shù)規(guī)劃問題的整數(shù)最優(yōu)解第三節(jié)第三節(jié) 分支定界法分支定界法例，某公司計(jì)劃建筑兩種類型的宿舍，甲種每棟占地250平米，乙種每棟占地400平米，該公司擁有地地3000平米，計(jì)劃甲種宿舍不超過8棟，乙種宿舍不超過4棟，甲種宿舍每棟利潤為10萬元，乙種宿每棟利潤為20萬元，問該公司應(yīng)計(jì)劃甲乙兩種類型的

25、宿舍各建多少棟時(shí)，能使公司利潤最大？解：設(shè)計(jì)劃甲乙兩種類型的宿舍分別建x1,x2棟，則本題的數(shù)學(xué)模型為： max z=10 x1+20 x2 25x1+40 x2300 x1 8 x2 4 x1,x20 x1,x2 取整數(shù)第三節(jié)第三節(jié) 分支定界法分支定界法這個(gè)純整數(shù)規(guī)劃問題稱為問題A0，去掉整數(shù)條件，得到問題A0的伴隨規(guī)劃，稱之為問題B0max z=10 x1+20 x25x1+8x260 x1 8 x2 4 x1,x20求解上述問題，得到最優(yōu)解X0（5.6,4)最優(yōu)值為f0=136第三節(jié)第三節(jié) 分支定界法分支定界法x1x2(5.6,4)(8,2.5)841、計(jì)算原問題A0目標(biāo)函數(shù)的初始上界Z

26、上界 因?yàn)閱栴}B0的最優(yōu)解X0不滿足整數(shù)條件，因此X0不是問題A0的最優(yōu)解，又因?yàn)锳0的可行域K0包含問題B0的可行域K0，故問題A0的最優(yōu)值不會(huì)超過問題B0的最優(yōu)值，即有Zf0 因此可令f0作為Z的初始上界Z，即上界Z上界1362、計(jì)算原問題A0目標(biāo)函數(shù)值的初始下界Z下界 若能從問題A0的約束條件中觀察到一個(gè)整數(shù)可行解，則可將其目標(biāo)函數(shù)值作為問題A0目標(biāo)函數(shù)值的初始下界，否則可令初始下界Z，給定下界的目的，是希望在求解過程中尋找比當(dāng)前Z更好的原問題的目標(biāo)函數(shù)值 對于本例，容易得到一個(gè)可行解X（0,0），故可令初始下界Z下界0第三節(jié)第三節(jié) 分支定界法分支定界法3、增加約束條件將原問題分枝 當(dāng)問

27、題B0的最優(yōu)解不滿足整數(shù)條件時(shí)，在x0中任選一個(gè)不符合整數(shù)條件的變量，如上例x15.6，顯然A0的整數(shù)最優(yōu)解只能是x15或x16，而絕不會(huì)在5與6之間，因此可將可行域K0切去5x16部分時(shí)，并沒有切去A0的整數(shù)可行解，可以用分別增加約束條件x1 5及x16來達(dá)到切去的目的，即將問題A0分為問題A1及問題A2兩枝子規(guī)劃問題A1問題A2max z=10 x1+20 x25x1+8x260 x1 8x2 4x1 5x1,x20，取整數(shù)max z=10 x1+20 x25x1+8x260 x1 8x2 4x16x1,x20，取整數(shù)第三節(jié)第三節(jié) 分支定界法分支定界法作出問題A1，A2的伴隨規(guī)劃B1，B2

28、，則問題B1，B2的可行域K1，K2，如下圖所示x1x2K1k2第三節(jié)第三節(jié) 分支定界法分支定界法max z=10 x1+20 x25x1+8x260 x1 8x2 4x1 5x1,x20B14、分別求解一對分枝 在一般情況下，對某個(gè)分析問題（伴隨規(guī)劃）求解時(shí)，可能出現(xiàn)以下幾種可能：（1）無可行解，說明該枝情況已查明，不需要由此再繼續(xù)分枝，該分枝稱為樹葉（2）得到整數(shù)最優(yōu)解,若求得整數(shù)最優(yōu)解，則該分枝情況也已查明，不需要再對其繼續(xù)分枝，該分枝也是樹葉（3）得到非整數(shù)最優(yōu)解（包括兩種情況） A：該最優(yōu)解的目標(biāo)函數(shù)值Z不大于當(dāng)前的下界Z，則該分枝內(nèi)不可能含有原問題的整數(shù)最優(yōu)解，因此該分枝不需要繼續(xù)

29、分枝，稱之為枯枝 B：若該最優(yōu)解的目標(biāo)函數(shù)值Z大于當(dāng)前的下界Z下界，則仍需對該枝繼續(xù)分枝，以查明該分枝是否有目標(biāo)函數(shù)值比當(dāng)前的下界Z更好的整數(shù)最優(yōu)解第三節(jié)第三節(jié) 分支定界法分支定界法 因每個(gè)分枝的求解結(jié)果不外乎上述各種情況，因此每個(gè)分枝求解結(jié)果可表明它或是不需要繼續(xù)分枝（樹葉或枯枝）或是要繼續(xù)分枝， 若一對分枝都需要繼續(xù)分枝時(shí)，首先將目標(biāo)函數(shù)值較優(yōu)的分枝求解，而對目標(biāo)函數(shù)值稍差的那一枝暫且放下，待目標(biāo)函數(shù)較優(yōu)的那枝全部分解到不能再分，全部查清時(shí)為止，再考慮目標(biāo)函數(shù)值稍差的那枝，也將它全部查清，這樣做，有可能減少一部分計(jì)算工作量 對于本題問題B1，B2的模型及求解如下：第三節(jié)第三節(jié) 分支定界法分

30、支定界法問題B1：max z=10 x1+20 x25x1+8x260 x1 8x2 4x1 5x1,x20問題B2max z=10 x1+20 x25x1+8x260 x1 8x2 4x16x1,x20解為x1=(5,4) f1=130解為x2=(6,3.75) f2=135問題B1的解是整數(shù)解，它當(dāng)然也是問題A0的整數(shù)可行解，故A0的整數(shù)最優(yōu)解Zf1130，此時(shí)可將下界Z下界修改為Z下界f1130同時(shí)問題B1也被查清，不需要再繼續(xù)分枝，即問題B1是樹葉第三節(jié)第三節(jié) 分支定界法分支定界法 而問題B2的最優(yōu)解不是整數(shù)最優(yōu)解，且f2=135Z下界，因此需要繼續(xù)分枝 故問題A2分別增加約束條件，x

31、24,x23，分為A3，A4兩枝，建立相應(yīng)的伴隨規(guī)劃B3，B4問題B3：max z=10 x1+20 x25x1+8x260 x1 8x2 4x16x2 3x1,x20問題B4：max z=10 x1+20 x25x1+8x260 x1 8x2 4x16x2 4x1,x20求解問題B3，得到最優(yōu)解為X（7.2，3）f3=132問題B4無可行解第三節(jié)第三節(jié) 分支定界法分支定界法5、修改上、下界(1)修改下界Z下界 修改下界的時(shí)機(jī)：每求出一個(gè)整數(shù)可行解時(shí)，都要作修改下界Z的工作 修改原則：在至今所有計(jì)算出的整數(shù)可行解中，選目標(biāo)函數(shù)值最大的那個(gè)作為最新下界Z下界，因此用分枝定界法的求解過程中，下界Z

32、是不斷增大的(2)修改上界Z上界 上界Z的修改時(shí)機(jī)：每求解完一對分枝，都要考慮修改上界 修改原則：挑選在迄今為止所有未被分枝的問題的目標(biāo)函數(shù)值中最大的一個(gè)作為新的上界，新的上界Z應(yīng)該小于原來的上界，在分枝定界法的整個(gè)求解過程中，上界的值在不斷的減小，第三節(jié)第三節(jié) 分支定界法分支定界法 本例中，當(dāng)解完一對分枝問題B1，B2時(shí)，因?yàn)閤1是整數(shù)解，因此修改下界Z下界=f1=130 ,而f2是迄今未被分枝的問題中目標(biāo)函數(shù)最大的,因此修改上界Z上界=f2=135 在求解完B3，B4后，因?yàn)闊o新的整數(shù)可行解，因此下界Z不變，而迄今為止還沒被分枝的問題中(B1，B3，B4)，目標(biāo)函數(shù)值最大為f3=132，因

33、此修改上界Z上界=132 因?yàn)锽3的最優(yōu)解x3=(7.2,3),f3=132，還不是整數(shù)，但f3z下界=130，故問題A3 還需要繼續(xù)分枝，增加約束條件x17,x18，A3分為A5，A6兩枝，求解相應(yīng)的伴隨規(guī)劃B5，B6：第三節(jié)第三節(jié) 分支定界法分支定界法解得x5=(7,3),f5=130 修改下界Z下界=130，X6=(8,2.5) f6=130 修改上界Z上界=f1=f5=f6=130問題B5：max z=10 x1+20 x25x1+8x260 x1 8x2 4x1 6x2 3 x1 7x1,x20問題B6：max z=10 x1+20 x25x1+8x260 x1 8x2 4x1 6x

34、2 3x1 8x1,x20第三節(jié)第三節(jié) 分支定界法分支定界法6、結(jié)束準(zhǔn)則 當(dāng)所有分枝均已查明(或無可行解，或?yàn)檎麛?shù)可行解，或其目標(biāo)函數(shù)值不大于下界Z)且此時(shí)上界與下界相等，則已得到原問題的整數(shù)最優(yōu)解，即目標(biāo)函數(shù)值為下界Z的那個(gè)整數(shù)解 在本例中，當(dāng)解完B5，B6后，得到上下界相等，又B5是樹葉，B6為枯枝，因此所有分枝(B1,B4,B5,B6) 均已查明，故得問題A0的最優(yōu)解 X=X5=(7,3) Z=130 或X=X1=(5,4) Z=130第三節(jié)第三節(jié) 分支定界法分支定界法x1=5.6 x2=4f0=136問題B0A0Z上界 =136Z下界=0 x15x16x17x18x1=5 x2=4f1

35、=130問題B1x1=6 x2=3.75f2=135問題B2Z上界 =135Z下界=130 x23x24x1=7.2 x2=3f3=132問題B3不可行問題B4x1=7 x2=3f5=130問題B5x1=8 x2=2.5f6=130問題B6Z上界 =132Z下界=130Z上界 =130Z下界=130A1A2A3A4A5A6第三節(jié)第三節(jié) 分支定界法分支定界法分枝定界法計(jì)算步驟第1步：將原整數(shù)規(guī)劃稱為問題A0，去掉問題A0的整數(shù)條件，得到伴隨規(guī)劃B0第2步：求解問題B0，有以下幾種可能：(1)B0沒有可行解，則A0也沒有可行解，停止計(jì)算(2)得到最優(yōu)解，且滿足整數(shù)條件，則B0的最優(yōu)解也是A0的最優(yōu)

36、解，停止計(jì)算(3)得到不滿足整數(shù)條件的最優(yōu)解，記它的目標(biāo)函數(shù)值為f0，這時(shí)需要對問題進(jìn)行分枝，轉(zhuǎn)下一步第3步：確定初始上下界Z上界，Z下界 以f0作為上界Z上界，觀察出問題A0的一個(gè)整數(shù)可行解，將其目標(biāo)函數(shù)值記為下界Z，若觀察不到，則可記Z下界=-，轉(zhuǎn)下一步第三節(jié)第三節(jié) 分支定界法分支定界法第4步，將問題B0分枝 在B0的最優(yōu)解中，任選一個(gè)不符合整數(shù)條件的變量xj，其值為aj，以aj表示小于aj的最大整數(shù)，構(gòu)造兩個(gè)約束條件： xjaj xjaj+1 將這兩個(gè)約束條件分別加到問題B0的約束條件中，得到B0的兩個(gè)分枝：問題B1，B2第5步：求解分枝問題 對每個(gè)分枝問題求解，可能得到以下幾種可能 (

37、1)分枝無可行解：該分枝是樹葉 (2)求得該分枝的最優(yōu)解，且滿足整數(shù)條件，將該最優(yōu)解的目標(biāo)函數(shù)值作為新的下界Z下界，該分枝也是樹葉 (3)求得該分枝的最優(yōu)解，且不滿足整數(shù)條件，但其目標(biāo)函數(shù)值不大于當(dāng)前下界Z下界，則該分枝是枯枝，需要剪枝 (4)求得不滿足A0的整數(shù)條件的該分枝的最優(yōu)解，且其目標(biāo)函數(shù)值大于當(dāng)前下界Z下界，則該分枝需要繼續(xù)進(jìn)行分枝第三節(jié)第三節(jié) 分支定界法分支定界法 若是前3種情況，表明該分枝情況已探明，不需要繼續(xù)分枝 若求解一對分枝的結(jié)果表明這一對分枝都需要繼續(xù)分枝時(shí)，則可先對目標(biāo)函數(shù)值大的那個(gè)分枝進(jìn)行分枝計(jì)算，且沿著該分枝一直繼續(xù)進(jìn)行下去，直到全部探明情況為止，再過來求解目標(biāo)函數(shù)

38、值較小的那個(gè)分枝第三節(jié)第三節(jié) 分支定界法分支定界法第6步 修改上下界(1)修改下界：每求出一次符合整數(shù)條件的可行解時(shí)，都要考慮修改下界Z下界，選擇迄今為止最好的整數(shù)可行解相應(yīng)的目標(biāo)函數(shù)值作為下界(2)修改上界：每求解完一對分枝，都要考慮修改上界，上界的值應(yīng)是迄今為止，所有未被分枝的問題的目標(biāo)函數(shù)值中最大的一個(gè) 在每解完一對分枝，修改完上下界后，若已有Z上界=Z下界，此時(shí)所有分枝均已查明，即得到問題的最優(yōu)值，求解結(jié)束，若仍有Z上界Z下界，則說明仍有分枝沒有查明，需要繼續(xù)分枝，回到第4步第三節(jié)第三節(jié) 分支定界法分支定界法p分支定界的實(shí)質(zhì)是在保留原問題全部整數(shù)可行解前提下，將原問題分解為若干子問題，

39、即分支，并利用子問題的目標(biāo)值來判定分支的界限。 p整數(shù)線性規(guī)劃的分支原則是利用整數(shù)規(guī)劃的相鄰整數(shù)點(diǎn)之間無可行域這一特點(diǎn)，因而可以按相鄰整數(shù)為邊緣來分支。取整數(shù)且 , , 0, 62 2054 . .34max2121212121xxxxxxxxtsxxZ第三節(jié)第三節(jié) 分支定界法分支定界法0, 62 2054 . .34max21212121xxxxxxtsxxZ最優(yōu)解:(5/3,8/3)第三節(jié)第三節(jié) 分支定界法分支定界法一、分支定界法求解過程一、分支定界法求解過程去掉取整約束，求解下面相應(yīng)的線性規(guī)劃去掉取整約束，求解下面相應(yīng)的線性規(guī)劃B0 x2x1Z上界=14.75Z下界=0最優(yōu)解:(1,16

40、/5)目標(biāo)函數(shù)最優(yōu)值：68/5最優(yōu)解:(2,2)目標(biāo)函數(shù)最優(yōu)值：140, 1 62 2054 . .34max211212121xxxxxxxtsxxZ0, 2 62 2054 . .34max211212121xxxxxxxtsxxZB1B2整數(shù)解不再分支第一次對第一次對x1分支分支:分成分成 x15/3=1 和和x15/3+1=2，將，將約束分別添加到上面的線性規(guī)劃約束分別添加到上面的線性規(guī)劃B0中，得到線性規(guī)劃中，得到線性規(guī)劃B1和和B2x1x2第三節(jié)第三節(jié) 分支定界法分支定界法Z上界=14.75 Z下界=14最優(yōu)解:(1,3)目標(biāo)函數(shù)最優(yōu)值：11B11最優(yōu)解:(0,4)目標(biāo)函數(shù)最優(yōu)值：

41、12整數(shù)解不再分支B120, 3 , 1 62 2054 . .34max2121212121xxxxxxxxtsxxZ0, 4 , 1 62 2054 . .34max2121212121xxxxxxxxtsxxZ所有分支都檢查完畢，得到最優(yōu)解所有分支都檢查完畢，得到最優(yōu)解(2, 2)。整數(shù)解不再分支B1的最優(yōu)解中含有非整數(shù)，再對的最優(yōu)解中含有非整數(shù)，再對x2分支：分支：x2 16/5=3和和x2 16/5+1=4第三節(jié)第三節(jié) 分支定界法分支定界法求解過程可用下列樹狀結(jié)構(gòu)表示求解過程可用下列樹狀結(jié)構(gòu)表示 X1=5/3X2=8/3X1=1X2=16/5Z=68/5X1=2X2=2Z=14x11

42、x12子問題子問題B1X1=1X2=3Z=11X1=0X2=4Z=12x23x24子問題子問題B2子問題子問題B12子問題子問題B11停止分解，因?yàn)榻鉃檎麛?shù)停止分解，因?yàn)榻鉃檎麛?shù)Z上界=14.75Z下界=0Z上界=14Z下界=14練習(xí)：利用分枝定界法求解max z=x1+x2 14x1+9x251 -2x1+x2 1/3 x1,x20，取整數(shù)x1=3/2 x2=10/3f0=29/6問題B0A0Z上界 =29/6Z下界=0 x11x12x12x13x1=1 x2=7/3f1=10/3問題B1x1=2 x2=23/9f2=41/9問題B2Z上界 =41/9Z下界=0 x22x23x1=33/14

43、 x2=2f3=61/14問題B3無可行解問題B4x1=2 x2=3f5=4問題B5x1=3 x2=1f6=4問題B6Z上界 =61/14Z下界=0Z上界 =4Z下界=4A1A2A3A4A5A6第三節(jié)第三節(jié) 分支定界法分支定界法目目 錄錄p整數(shù)規(guī)劃實(shí)例與模型整數(shù)規(guī)劃實(shí)例與模型p0 01 1整數(shù)規(guī)劃的建模方法整數(shù)規(guī)劃的建模方法p分支定界法分支定界法p割平面法割平面法p指派問題指派問題p應(yīng)用舉例和應(yīng)用舉例和ExcelExcel求解求解p 基本思想基本思想：首先求解相應(yīng)的線性規(guī)劃，然后不斷增加適當(dāng)?shù)木€性約束，將原可行域中不含整數(shù)可行解的一部分割掉，最終得到一個(gè)極點(diǎn)是整數(shù)坐標(biāo)的可行域，而該極點(diǎn)恰好是原

44、整數(shù)規(guī)劃問題的最優(yōu)解。p割平面法步驟：步驟：n（1）解除整數(shù)約束，用單純形法求解。如所得到的解為整數(shù)解，停止計(jì)算；否則轉(zhuǎn)步驟（2）。n（2）尋求附加約束（割平面方程）；n（3）將割平面方程標(biāo)準(zhǔn)規(guī)范化后加到約束方程組中求解，如所得到的解仍為非整數(shù)，則轉(zhuǎn)步驟（2），直到找到最優(yōu)整數(shù)解。p 難點(diǎn)及重點(diǎn)難點(diǎn)及重點(diǎn)：如何找到割平面方程，并使包含割平面約束在內(nèi)的新的規(guī)劃問題的一個(gè)極點(diǎn)解成為最優(yōu)整數(shù)解。第三節(jié)割平面法第三節(jié)割平面法取整數(shù) , , 0, 1824 1432 . .23max2121212121xxxxxxxxtsxxZ原問題去掉整數(shù)約束條件，得線性規(guī)劃問題，并標(biāo)準(zhǔn)化基變量x3x4x1x2bx2

45、0.50-0.500.001.002.50 x1-0.250.751.000.003.25-z-0.25-1.250.000.00-14.75最后的單純形表0 , , , 18 24 14 32 . .23max432142132121xxxxxxxxxxtsxxZ254213212xxx在最優(yōu)表b列各分?jǐn)?shù)中有最大小數(shù)部分對應(yīng)的行中寫下非整數(shù)解約束方程,即第一行： 第三節(jié)割平面法第三節(jié)割平面法 所有系數(shù)和常數(shù)項(xiàng)分解為整數(shù)和正真分?jǐn)?shù)之和，并把整系數(shù)項(xiàng)移到左邊 )(24213212142xxxx取整數(shù)且 , ,0, 2/12/121/ 1824 1432 .23max212143212121xxx

46、xxxxxxxtsxxZ 考慮到所有變量為非負(fù)整數(shù) 得到新的整數(shù)規(guī)劃問題：0)(42132121xx143 xx化化簡簡0)(42132121xx143 xx化化簡簡重復(fù)上面的過程，直到得到整數(shù)解第三節(jié)割平面法第三節(jié)割平面法左邊為整數(shù)且小于0否則如果大于1(x2-x4-2)-1/2=-1/2x3-1/2x4-1/2x3-1/2x4+x5=-1/2基變量x3x4x1x2x5bx21/2-1/20105/2x1-1/43/410013/4x5-1/2-1/2001-1/2-z-1/4-5/4000-59/4x20-10112x10110-1/27/2x31100-21-z0-100-1/2-58/

47、4最優(yōu)解為x1=7/2 x2=1仍為非整數(shù)解，所以轉(zhuǎn)到第二步再求割平面，從上表寫下非整數(shù)解x1的約束方程為 x1+x4-1/2x5=7/2重復(fù)上述分析過程得第三節(jié)割平面法第三節(jié)割平面法x1+x4-x5-3=1/2-1/2x50即為割平面方程，將新的約束條件加到原問題中，得到新問題對新問題用單純形法求解得到最優(yōu)解X1=4 ,x2=1 z=14 為整數(shù)解，計(jì)算停止第三節(jié)割平面法第三節(jié)割平面法p整數(shù)規(guī)劃實(shí)例與模型整數(shù)規(guī)劃實(shí)例與模型p0 01 1整數(shù)規(guī)劃的建模方法整數(shù)規(guī)劃的建模方法p分支定界法分支定界法p割平面法割平面法p指派問題指派問題p應(yīng)用舉例和應(yīng)用舉例和ExcelExcel求解求解第五節(jié)指派問題

48、第五節(jié)指派問題p(一)問題的提出n有n項(xiàng)不同的任務(wù)需要完成，而恰好有n個(gè)人（或n臺(tái)設(shè)備）可以分別完成其中的一項(xiàng)工作，但由于任務(wù)的性質(zhì)和個(gè)人的專長不同，因而不同的人去完成不同的工作產(chǎn)生的效率就不一樣。那么，應(yīng)派哪一個(gè)人去完成哪一項(xiàng)工作才能使總的效率最高？ 第五節(jié)指派問題第五節(jié)指派問題例設(shè)有4個(gè)A、B、C、D四個(gè)人，都可以各自完成四種不同工作中的任一種，其花時(shí)間如下表：規(guī)定每人應(yīng)做且只做一種工作，問應(yīng)如何安排，使他們完成四種工作的總時(shí)間最少？甲乙丙丁A6583B105415C137211D139710解令A(yù)為第1，B為第2，C為第3，D為第4甲為第1工作，乙為第2工作，丙為第3工作，丁為第4工作令

49、xij=1表示分配第i人做第j工作Xij=0表示不分配第i人做第j工作 依題意得：Minz=6x11+5x12+8x13+3x14+10 x21+5x22+4x23+15x24+13x31+7x32+2x33+11x34+13x41+9x42+7x43+10 x44X11+x12+x13+x14=1X21+x22+x23+x24=1X31+x32+x33+x34=1X41+x42+x43+x44=1X11+x21+x31+x41=1X12+x22+x32+x42=1X13+x23+x33+x43=1X14+x24+x34+x44=1Xij=1或0 i,j=1,2,3,4每人只許做一份工作每份工

50、作由一個(gè)人負(fù)責(zé)指派問題模型j.i, 1 0 ,2, 1 , 1 ,2, 1 , 1 .min1111對一切或 ijnjijniijninjijijxnixnjxtsxc第五節(jié)指派問題第五節(jié)指派問題例 某市計(jì)劃在今年內(nèi)修建4座廠房：發(fā)電廠、化肥廠、機(jī)械廠、食品廠，分別記為B1，B2，B3，B4。該市有4個(gè)大的建筑隊(duì)A1，A2，A3，A4都可以承擔(dān)這些廠房的建造任務(wù)。但由于各個(gè)建筑隊(duì)的技術(shù)水平、管理水平等不同，它們完成每座廠房所需要的費(fèi)用也不一樣。為計(jì)算簡單，設(shè)有關(guān)數(shù)據(jù)如下表所示。又因希望盡早把這4座廠房都建造好，故需把這4個(gè)建筑隊(duì)都動(dòng)用起來，即每個(gè)隊(duì)分配一項(xiàng)任務(wù)。市政府經(jīng)費(fèi)緊張，于是提出研究下述

51、問題：究竟應(yīng)該指派哪個(gè)隊(duì)修建哪個(gè)廠，才能使建造4座廠房所花的總費(fèi)用最少？ 各建筑隊(duì)完成每座廠房所需費(fèi)用（萬元） B1B2B3B4A13452A28576A39645A45366第五節(jié)指派問題第五節(jié)指派問題這就是一個(gè)指派問題，對于指派問題，必須 具有以下條件：(1)每項(xiàng)工作只能分配一個(gè)單位或一個(gè)人去完成(2)每個(gè)單位或人只能接受其中一項(xiàng)任務(wù)設(shè)cij(i,j=1,2n)為第i個(gè)人做第j項(xiàng)工作的費(fèi)用，由cij組成的方陣C=(cij)nn稱為效率矩陣 對上例其效率矩陣為6 6 3 55 4 6 96 7 5 82 5 4 3C定義決策變量如下：xij1，若指派第i人做第j項(xiàng)工作0，若不指派第i人做第j

52、 項(xiàng)工作第五節(jié)指派問題第五節(jié)指派問題二、可行解的性質(zhì)指派問題的可行解是矩陣(xij)nn，它是由一些單位向量構(gòu)成的n階方陣，方陣的每行每列有一個(gè)且只有一個(gè)1，其余為0，例如當(dāng)n=4時(shí)，其可行解可以 為：0 0 0 11 0 0 00 0 1 00 1 0 0X第五節(jié)指派問題第五節(jié)指派問題定理6.1 如果對系數(shù)矩陣C=(cij)nn的任一行(列)各元分別減去該行(列)的最小元，得到新矩陣B=(bij)nn，則以B為系數(shù)矩陣的指派問題的最優(yōu)解xij和原問題的最優(yōu)解相同匈牙利算法：首先通過行(列)變換使系數(shù)矩陣出現(xiàn)01。從系數(shù)矩陣的每行元減去該行的最小元2。從系數(shù)矩陣的每列元減去該列的最小元BC3

53、3 0 11 0 2 41 2 0 20 3 2 03 3 0 21 0 2 51 2 0 30 3 2 16 6 3 55 4 6 96 7 5 82 5 4 3第五節(jié)指派問題第五節(jié)指派問題定理6.2 設(shè) C=(cij)nn是一個(gè)效率矩陣，若可行解X的n 個(gè)1所對應(yīng)的n個(gè)cij等于0，則X是最優(yōu)解即在效率矩陣B中若能找到n 個(gè)位于不同行不同列上的0元，則就可找到最優(yōu)解。定理6.3設(shè)矩陣C中一部分元為0，一部分不為0，則劃去C中所有0元所需要的最少直線數(shù)等于C中不同行不列上0元的個(gè)數(shù)第五節(jié)指派問題第五節(jié)指派問題p獲取最少數(shù)直線的方法：p(1)找出矩陣C中沒有圈0并且含有0元最少的一行(列)，從

54、該行(列)中圈出一個(gè)0，再通過這個(gè)0作一豎(橫)線劃去此0所在之列(行)p逐行檢查，對每行只有一個(gè)且未被直線劃的零元時(shí)，將該零元素圈起，然后對該零元素所在的列劃一豎(表示該工作不再指派其他人去完成)p逐列檢查，對每列只有一個(gè)且未被直線劃的零元時(shí)，將該零元素圈起，然后對該零元素所在的行劃一橫p(2)對C中余下的各行各列重復(fù)步驟1，但已圈數(shù)的行和列不再圈數(shù)3 3 0 11 0 2 41 2 0 20 3 2 0由于rn=4 ，所以需要調(diào)整1 在所有未劃去數(shù)中找出最小數(shù)，設(shè)為d；2 將所有未畫去的數(shù)都減去d，而對位于兩直線交點(diǎn)處的數(shù)則加上d。3 得出新的指派方案。2 2 0 01 0 3 40 1

55、0 10 3 3 0第五節(jié)指派問題第五節(jié)指派問題0 0 1 00 1 0 01 0 0 00 0 0 1也就是最優(yōu)指派方案為A1隊(duì)修B1廠A2隊(duì)修B4廠，A3隊(duì)修B3廠A4隊(duì)修B2廠X11=x24=x33=x42=1其余為0總費(fèi)用為z=c11+c24+c33+c42=16萬將所有圈0換成1，其他都換成0得最優(yōu)解：第五節(jié)指派問題第五節(jié)指派問題2 2 0 01 0 3 40 1 0 10 3 3 0也就是最優(yōu)指派方案為A1隊(duì)修B4廠A2隊(duì)修B2廠，A3隊(duì)修B3廠A4隊(duì)修B1廠X14=x22=x33=x41=1其余為0總費(fèi)用為z=c14+c22+c33+c41=16萬0 0 0 10 1 0 00

56、0 1 01 0 0 0最優(yōu)解為：總費(fèi)用z=c41+c22+c33+c41=16萬最優(yōu)解不惟一第五節(jié)指派問題第五節(jié)指派問題匈牙利算法總結(jié)：第一步：使系數(shù)矩陣每行每列都出現(xiàn)0元素第二步 畫最少0元素的覆蓋線，逐行檢查，對每行只有一個(gè)且未被直線劃的零元時(shí)，將該零元素圈起，然后對該零元素所在的列劃一豎,逐列檢查，對每列只有一個(gè)且未被直線劃的零元時(shí)，將該零元素圈起，然后對該零元素所在的行劃一橫若所畫直線等于n，則問題已解決，否則轉(zhuǎn)下一步第三步 在未劃去的各數(shù)中找出最小的一個(gè)，設(shè)為d，然后將未劃去的各數(shù)都減去d，而對位于兩直線交叉的各數(shù)則都加上d，這樣，又得到一個(gè)新的矩陣，對此矩陣再重復(fù)第二步第五節(jié)指派

57、問題第五節(jié)指派問題19 16 17 2617 23 21 1918 22 23 1924 21 18 51求根據(jù)下面的效能矩陣求最優(yōu)指派19 16 17 2617 23 21 1918 22 23 1924 21 18 51解(1)根據(jù)效能矩陣，使每行每列都出現(xiàn)0元3 0 1 100 6 4 20 4 5 19 6 3 03 0 0 100 6 3 20 4 4 19 6 2 0每行減最小元每列減最小元第五節(jié)指派問題第五節(jié)指派問題3 0 0 100 6 3 20 4 4 19 6 2 0(2)試求最優(yōu)解(3)調(diào)整并試求最優(yōu)解4 0 0 100 5 2 10 3 3 010 6 2 0(4)調(diào)整并試求最優(yōu)解5 0 0 110 3 0 10 1 1 010 4 0 0即最優(yōu)解：X11=x24=x32=x43=1 其余為0最優(yōu)值為：z=15+18+21+16=700 1 0 00 0 1 01 0 0 00 0 0 1(5)原問題的最優(yōu)解為第五節(jié)指派問題第五節(jié)指派問題課堂作業(yè)：由4個(gè)人完成4項(xiàng)任務(wù)，由于能力不同，完成所需要的時(shí)