運(yùn)籌學(xué)課件第5章_整數(shù)規(guī)劃及分配問題

1、第第4章章 整數(shù)規(guī)劃與分配問題整數(shù)規(guī)劃與分配問題管理運(yùn)籌學(xué)課件2021年10月20日星期三教學(xué)目標(biāo)與要求教學(xué)目標(biāo)與要求n【教學(xué)目標(biāo)教學(xué)目標(biāo)】n通過本章學(xué)習(xí)，了解求解整數(shù)規(guī)劃通過本章學(xué)習(xí)，了解求解整數(shù)規(guī)劃“分枝定界法分枝定界法”的其中思路，掌握的其中思路，掌握0-1變量在數(shù)學(xué)建模中的應(yīng)用；熟練掌握變量在數(shù)學(xué)建模中的應(yīng)用；熟練掌握“匈牙利法匈牙利法”，至少掌握一，至少掌握一種軟件求得整數(shù)規(guī)劃及分配問題的最優(yōu)解。種軟件求得整數(shù)規(guī)劃及分配問題的最優(yōu)解。n【知識結(jié)構(gòu)知識結(jié)構(gòu)】 整數(shù)規(guī)劃與分配問題 分配問題數(shù)學(xué)模型 0-1 變量用法：添加特殊約束的 LP 變量取整的 LP 整數(shù)規(guī)劃 變量取 0-1 的 L

2、P 數(shù)學(xué)模型 計(jì)算機(jī)求解 匈牙利法 應(yīng)用 管理運(yùn)籌學(xué)課件2021年10月20日星期三本章主要內(nèi)容本章主要內(nèi)容 n4.1 整數(shù)規(guī)劃整數(shù)規(guī)劃n4.1.1 整數(shù)規(guī)劃的概念整數(shù)規(guī)劃的概念n4.1.2 分枝定界法的基本思路分枝定界法的基本思路*n4.2 0-1規(guī)劃規(guī)劃n4.2.1 0-1規(guī)劃的概念規(guī)劃的概念n4.2.2 0-1規(guī)劃的隱枚舉法簡介規(guī)劃的隱枚舉法簡介*n4.2.4 0-1變量在數(shù)學(xué)建模中的用途變量在數(shù)學(xué)建模中的用途n案例案例4-1 球隊(duì)隊(duì)員篩選球隊(duì)隊(duì)員篩選n案例案例4-2 選址問題選址問題n案例案例4-3 集合覆蓋問題集合覆蓋問題n4.3 分配問題分配問題n4.3.1 分配問題數(shù)學(xué)模型分配問

3、題數(shù)學(xué)模型n4.3.2 分配問題的解題方法分配問題的解題方法匈牙利法匈牙利法n案例案例4-4 任務(wù)分派任務(wù)分派n本章小結(jié)本章小結(jié)管理運(yùn)籌學(xué)課件2021年10月20日星期三導(dǎo)入案例導(dǎo)入案例集裝箱托運(yùn)計(jì)劃集裝箱托運(yùn)計(jì)劃某廠擬用集裝箱托運(yùn)甲、乙兩種貨物，每箱的體積、質(zhì)量、可獲得的某廠擬用集裝箱托運(yùn)甲、乙兩種貨物，每箱的體積、質(zhì)量、可獲得的利潤以及托運(yùn)所受到的限制如表利潤以及托運(yùn)所受到的限制如表4-1所示。問怎樣安排托運(yùn)計(jì)劃，可所示。問怎樣安排托運(yùn)計(jì)劃，可使利潤最大？使利潤最大？貨物貨物每箱體積每箱體積/米米3每箱質(zhì)量每箱質(zhì)量/50千克千克每箱利潤每箱利潤/百元百元甲甲乙乙384356托運(yùn)限制托運(yùn)限制

4、40241212121212max z563843,0,xxxxxxx xx x4024取整數(shù)(1)(2)(3)(4)(5)設(shè)設(shè) x1,x2表示兩種貨物裝載數(shù)量表示兩種貨物裝載數(shù)量(整數(shù)整數(shù))，依題意有如下數(shù)學(xué)模型：，依題意有如下數(shù)學(xué)模型：在實(shí)際中，許多要求變量取整的在實(shí)際中，許多要求變量取整的數(shù)學(xué)模型，稱為整數(shù)規(guī)劃。本章數(shù)學(xué)模型，稱為整數(shù)規(guī)劃。本章將討論整數(shù)規(guī)劃求解的基本思路、將討論整數(shù)規(guī)劃求解的基本思路、0-1變量的用法、分配問題及匈變量的用法、分配問題及匈牙利法，以及利用牙利法，以及利用Excel, Lingo, WinQSB求解的演示。求解的演示。管理運(yùn)籌學(xué)課件2021年10月20日星

5、期三4.1.1 整數(shù)規(guī)劃的基本概念整數(shù)規(guī)劃的基本概念n整數(shù)規(guī)劃（整數(shù)規(guī)劃（integer programming，IP）是指一）是指一類要求問題中的全部或一部分變量為整數(shù)的數(shù)學(xué)類要求問題中的全部或一部分變量為整數(shù)的數(shù)學(xué)規(guī)劃。規(guī)劃。n在整數(shù)規(guī)劃中，依決策變量的取值不同，又可進(jìn)在整數(shù)規(guī)劃中，依決策變量的取值不同，又可進(jìn)一步劃分：一步劃分：如果所有變量都限制為整數(shù)，則稱為純整數(shù)規(guī)劃如果所有變量都限制為整數(shù)，則稱為純整數(shù)規(guī)劃（Pure Integer Programming，PIP）；）；如果僅一部分變量限制為整數(shù)，則稱為混合整數(shù)如果僅一部分變量限制為整數(shù)，則稱為混合整數(shù)規(guī)劃（規(guī)劃（Mixed Int

6、eger Programming，MIP）；）；變量取二進(jìn)制的整數(shù)規(guī)劃則稱為變量取二進(jìn)制的整數(shù)規(guī)劃則稱為0-1規(guī)劃（規(guī)劃（Binary Integer Programming，BIP）。）。管理運(yùn)籌學(xué)課件2021年10月20日星期三4.1.2 分枝定界法的基本思路分枝定界法的基本思路*【例例4.1】 用圖解法求解整數(shù)規(guī)劃用圖解法求解整數(shù)規(guī)劃1212121212max 563840(1)4324(2),0,zxxxxxxx xx x取整數(shù)分枝定界法分枝定界法(Branch and Bound Method)用于求解整數(shù)規(guī)劃問題，用于求解整數(shù)規(guī)劃問題，是在是在20世紀(jì)世紀(jì)60年代初，由年代初，由L

7、and Doig和和Dakin等人提出的。等人提出的。解解 (1) 繪制直角坐標(biāo)系，圖示約束條件，圖示目標(biāo)函數(shù)一根基線繪制直角坐標(biāo)系，圖示約束條件，圖示目標(biāo)函數(shù)一根基線(z=30)，使其平行移動，求得非整數(shù)最優(yōu)解。該解的坐標(biāo)為，使其平行移動，求得非整數(shù)最優(yōu)解。該解的坐標(biāo)為(72/23,88/23)，不在網(wǎng)格線的交叉點(diǎn)上，非整數(shù)解（非可行解）。，不在網(wǎng)格線的交叉點(diǎn)上，非整數(shù)解（非可行解）。(2) 對對“解解1”分枝定界：選取分枝定界：選取x1 進(jìn)行分枝定界：在原模型的基礎(chǔ)上，進(jìn)行分枝定界：在原模型的基礎(chǔ)上，分別添加分別添加x13,x14 。優(yōu)化結(jié)果。優(yōu)化結(jié)果 “解解2” ，X=(3,31/8)，

8、z=38.25；“解解3”，X=(4,8/3)，z=36，均為非整數(shù)（非可行解）。，均為非整數(shù)（非可行解）。(3) 先對先對“解解2”分枝定界：分枝定界：“解解2”的坐標(biāo)為的坐標(biāo)為(3,31/8)，分別添加，分別添加 x23，x24，優(yōu)化結(jié)果，優(yōu)化結(jié)果 “解解4”，X=(3,3)，z=33，為可行解；，為可行解；“解解5”，X=(8/3,4)，z=37.33，為非可行解。，為非可行解。(4) 再對再對“解解3”分枝定界：分枝定界：“解解3”的坐標(biāo)的坐標(biāo) ， 為非整數(shù)，添加為非整數(shù)，添加x22 （x2 3為非可行域），優(yōu)化結(jié)果為為非可行域），優(yōu)化結(jié)果為X=(9/2,2)，z=34.5；再添加；再

9、添加x1 =4,x1 5 。解得整數(shù)解。解得整數(shù)解X=(4,2)，z=32和非整數(shù)解和非整數(shù)解X=(21/4,1)，目標(biāo)值，目標(biāo)值z=31.25；整數(shù)解目標(biāo)值大于非整數(shù)解，??；整數(shù)解目標(biāo)值大于非整數(shù)解，取(4,2)，得，得“解解6”。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 x10 1 2 3 4 5 6 7 8 x2(2,9/2),z=34.5解3 (4,8/3)解1 (72/23,88/23)解2 (3,31/8)5x1+6x2=30解4 (3,3),z=33解5 (8/3,4),z=37.33解6 (4,2),z=32 (5) 對對“解解5”分枝定界：分枝定界

10、：“解解5”的坐標(biāo)的坐標(biāo)(8/3,4)， 為非整數(shù)，添加為非整數(shù)，添加x12 （ x13為非可行域），優(yōu)化結(jié)果為為非可行域），優(yōu)化結(jié)果為X=(2,17/4)，再添加，再添加x2=4 和和x2=5 。求得整數(shù)解求得整數(shù)解(2,4)，目標(biāo)值，目標(biāo)值34；整數(shù)解；整數(shù)解(0,5)，目標(biāo)值，目標(biāo)值30，取，取(2,4)。如圖。如圖“解解7”。解7 (2,4),z=34(6) 剪枝：上述有三個(gè)區(qū)域的整數(shù)解分別為剪枝：上述有三個(gè)區(qū)域的整數(shù)解分別為“解解4”X=(3,3)，z=33；“解解6”X=(4,2)，z=32；“解解7”X=(2,4)，z=34。相比較，目標(biāo)值最大。相比較，目標(biāo)值最大的為的為34，對

11、應(yīng)的最優(yōu)方案，對應(yīng)的最優(yōu)方案 。演示：利用演示：利用WinQSB,ExcelORM+規(guī)劃求解規(guī)劃求解,ExcelORM+Lingo求例求例4.1管理運(yùn)籌學(xué)課件2021年10月20日星期三4.2.1 0-1規(guī)劃的概念規(guī)劃的概念n0-1規(guī)劃是一種特殊類型的整數(shù)規(guī)劃，即決策變量只取規(guī)劃是一種特殊類型的整數(shù)規(guī)劃，即決策變量只取0或或1。0-1規(guī)劃在整數(shù)規(guī)劃中占有重要地位，許多實(shí)際問題，規(guī)劃在整數(shù)規(guī)劃中占有重要地位，許多實(shí)際問題，例如指派問題、選址問題、送貨問題都可歸結(jié)為此類規(guī)劃。例如指派問題、選址問題、送貨問題都可歸結(jié)為此類規(guī)劃。求解求解0-1規(guī)劃的常用方法是隱枚舉法，對各種特殊問題還規(guī)劃的常用方法是

12、隱枚舉法，對各種特殊問題還有一些特殊方法，例如求解指派問題用匈牙利方法就比較有一些特殊方法，例如求解指派問題用匈牙利方法就比較方便。方便。n0-1規(guī)劃的數(shù)學(xué)模型為：規(guī)劃的數(shù)學(xué)模型為：01max(min)( ,). .zCXAXbstX取 或管理運(yùn)籌學(xué)課件2021年10月20日星期三4.2.2 隱枚舉法簡介隱枚舉法簡介12312312312123max 322(1)44(2)s.t.+ 3(3),01zxxxxxxxxxxxx x x例或12312312312123minmin 32244s.t.+ 3,01jcwxxxxxxxxxxxx xx 改變 符號,變?yōu)榛?12233111xxxxxx

13、令12312312312123min 352042s.t. 1,01wxxxxxxxxxxxx x x 或23123123121123min 352042s.t. +1,01wxxxxxxxxxxxx x x 目標(biāo)系數(shù)升序排序或1.化成標(biāo)準(zhǔn)形式化成標(biāo)準(zhǔn)形式(1)目標(biāo)函數(shù)目標(biāo)函數(shù):min ,cj0(2)目標(biāo)若目標(biāo)若max,目標(biāo)系數(shù)目標(biāo)系數(shù)改變符號改變符號,變?yōu)樽優(yōu)閙in;(2)若若cj1) 項(xiàng)工作任務(wù)，需項(xiàng)工作任務(wù)，需要要 m(n1)個(gè)人去完成，并且每個(gè)人只干個(gè)人去完成，并且每個(gè)人只干一件工作，每項(xiàng)工作都必須有人干，通一件工作，每項(xiàng)工作都必須有人干，通過權(quán)衡，合理分派任務(wù)，使總的消耗過權(quán)衡，合理

14、分派任務(wù)，使總的消耗(或或收益收益)達(dá)到最小達(dá)到最小(或最大或最大)的的0-1規(guī)劃問題，規(guī)劃問題，稱為分配問題稱為分配問題(Assignment Problem，AP)導(dǎo)入案例導(dǎo)入案例 運(yùn)動項(xiàng)目分配問題運(yùn)動項(xiàng)目分配問題某游泳隊(duì)有四名運(yùn)動員，其某游泳隊(duì)有四名運(yùn)動員，其平時(shí)訓(xùn)練成績平時(shí)訓(xùn)練成績(s/50m)如表如表所示。問如何安排可使總成所示。問如何安排可使總成績最好？績最好？人員人員任務(wù)任務(wù)效率矩陣效率矩陣cij1, 0, :ijijijx第 分配給第 人第 不分給第 人設(shè)11121314212223243132333441424344min373338374333423433293930302

15、62929zxxxxxxxxxxxxxxxx111213142122232431323334414243441111xxxxxxxxxxxxxxxx每項(xiàng)任務(wù)交給一人01(1,.,4;1,.,4)ijxij或112131411222324213233334142434441111xxxxxxxxxxxxxxxx 每人分給一項(xiàng)任務(wù). .st管理運(yùn)籌學(xué)課件2021年10月20日星期三4.3.1 分配問題數(shù)學(xué)模型分配問題數(shù)學(xué)模型管理運(yùn)籌學(xué)課件2021年10月20日星期三4.3.2 匈牙利法匈牙利法管理運(yùn)籌學(xué)課件2021年10月20日星期三4.3.2 匈牙利法匈牙利法【例例4.7】 用匈牙利法求引例中的

16、最小化分配問題。用匈牙利法求引例中的最小化分配問題。37333837433342343329393030262929Cmin33332926405410091401014033min 403100246060007000020100000110000010X0100000110000010X:129z 最優(yōu)值管理運(yùn)籌學(xué)課件2021年10月20日星期三4.3.2 匈牙利法匈牙利法【例例4.8】 用匈用匈牙利法求引例中牙利法求引例中的最小化分配問的最小化分配問題。題。12799989777 711 121291514147104101079C min1279997897777 711 121297

17、151414710741010794C解 50020340200435087501064335022212000045528770306635k=2最優(yōu)方案：最優(yōu)方案：12233544511xxxxx，其余，其余=0，最優(yōu)值，最優(yōu)值z=34 管理運(yùn)籌學(xué)課件2021年10月20日星期三案例案例4-4 任務(wù)分派任務(wù)分派管理運(yùn)籌學(xué)課件2021年10月20日星期三案例案例4-4 任務(wù)分派任務(wù)分派2529314237393826203334272840322442362345ijc效率矩陣1,:0,ijijxij第 人分派到第 項(xiàng)任務(wù)解第 人未分派到第 項(xiàng)任務(wù)4511111213141521222324

18、25313233343541424344451121314112223242132333431424344415253545min 11221s.t.11110ijijijijzc xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx1或（2）其中有一個(gè)人完成兩項(xiàng)，其他）其中有一個(gè)人完成兩項(xiàng)，其他每人完成一項(xiàng)；每人完成一項(xiàng)；（3）任務(wù)）任務(wù)A由甲或丙完成，任務(wù)由甲或丙完成，任務(wù)C由由丙或丁完成，任務(wù)丙或丁完成，任務(wù)E由甲、乙或丁完由甲、乙或丁完成，且規(guī)定成，且規(guī)定4人中丙或丁完成兩項(xiàng)任人中丙或丁完成兩項(xiàng)任務(wù)，其他每人完成一項(xiàng)。務(wù)，其他每人完成一項(xiàng)。（1）任務(wù)）任務(wù)E必須完成，其他必須完成，其他4項(xiàng)中可項(xiàng)中可任選任選3項(xiàng)完成；項(xiàng)完成；451111121314152122232425313233343541424344451121314112223242132333431424344415253545min 11111s.t.11