第4章-整數(shù)規(guī)劃與分配問題-管理運(yùn)籌學(xué)

1、第4章 整數(shù)規(guī)劃與分配問題目錄4整數(shù)規(guī)劃1230-1規(guī)劃分配問題本章小結(jié)與作業(yè)管理運(yùn)籌學(xué) 第4章 整數(shù)規(guī)劃與分配問題4.1 整數(shù)規(guī)劃管理運(yùn)籌學(xué) 第4章 整數(shù)規(guī)劃與分配問題導(dǎo)入案例整數(shù)規(guī)劃的基本概念圖解法分枝定界法的基本思路4.1.1導(dǎo)入案例集裝箱托運(yùn)計(jì)劃管理運(yùn)籌學(xué) 第4章 整數(shù)規(guī)劃與分配問題貨物每箱體積(m3)每箱質(zhì)量(50kg)每箱利潤(百元)甲乙384356托運(yùn)限制4024某廠擬用集裝箱托運(yùn)甲、乙兩種貨物，每箱的體積、質(zhì)量、可獲得的利潤以及托運(yùn)所受到的限制如表所示。問怎樣安排托運(yùn)計(jì)劃，可使利潤最大？設(shè) x1,x2表示兩種貨物裝載數(shù)量(整數(shù))，依題意有如下數(shù)學(xué)模型：在實(shí)際中，許多要求變量取整

2、的數(shù)學(xué)模型，稱為整數(shù)規(guī)劃。4.1.2 整數(shù)規(guī)劃的基本概念整數(shù)規(guī)劃（integer programming，IP）是指一類要求問題中的全部或一部分變量為整數(shù)的數(shù)學(xué)規(guī)劃。在整數(shù)規(guī)劃中，依決策變量的取值不同，又可進(jìn)一步劃分：如果所有變量都限制為整數(shù)，則稱為純整數(shù)規(guī)劃（Pure Integer Programming，PIP）；如果僅一部分變量限制為整數(shù)，則稱為混合整數(shù)規(guī)劃（Mixed Integer Programming，MIP）；變量取二進(jìn)制的整數(shù)規(guī)劃則稱為0-1規(guī)劃（Binary Integer Programming，BIP）。管理運(yùn)籌學(xué) 第4章 整數(shù)規(guī)劃與分配問題4.1.3 圖解法管理運(yùn)籌

3、學(xué) 第4章 整數(shù)規(guī)劃與分配問題【例4.1】 用圖解法求解整數(shù)規(guī)劃（1）建立直角坐標(biāo)系，圖示約束條件，確定可行域。（2）圖示目標(biāo)函數(shù)一根基線，按目標(biāo)要求平行移動，直到與可行域相交。（3）求出交點(diǎn)坐標(biāo)與目標(biāo)值。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 x10 1 2 3 4 5 6 7 8 x2X=(2,4),z=344.1.4 分枝定界法的基本思路*管理運(yùn)籌學(xué) 第4章 整數(shù)規(guī)劃與分配問題【例4.1】 分枝定界法求解分枝定界法(Branch and Bound Method)用于求解整數(shù)規(guī)劃問題，是在20世紀(jì)60年代初，由Land Doig和Dakin等人提出的。解 (

4、1) 承例4.1，由圖解法知，一般線性規(guī)劃解的坐標(biāo)為(72/23,88/23)，不在網(wǎng)格線的交叉點(diǎn)上，非整數(shù)解（非可行解）。(2) 對“解1”分枝定界：選取x1 進(jìn)行分枝定界：在原模型的基礎(chǔ)上，分別添加x13,x14 。優(yōu)化結(jié)果 “解2” ，X=(3,31/8) ；“解3”，X=(4,8/3) ，均為非整數(shù)（非可行解）。(3) 先對“解2”分枝定界：“解2”的坐標(biāo)為(3,31/8)，分別添加 x23，x24，優(yōu)化結(jié)果 “解4”，X=(3,3)，z=33，為可行解；“解5”，X=(8/3,4)，z=37.33，為非可行解，由于其目標(biāo)值大于解4的目標(biāo)值，先保留，待進(jìn)一步分枝定界。(4) 再對“解3

5、”分枝定界：“解3”的x2坐標(biāo) 為非整數(shù)，添加x22 （x2 3為非可行域），優(yōu)化結(jié)果為“解6”X=(9/2,2)，z=34.5；再添加x1 =4,x1 5 。解得整數(shù)解X=(4,2)，z=32和非整數(shù)解X=(5,4/3)，目標(biāo)值z=33，這兩個整數(shù)解和非整數(shù)解的目標(biāo)值均不大于整數(shù)解解4，不再保留。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解6(9/2,2),z=34.5解3 (4,8/3)解1 (72/23,88/23)解2 (3,31/8)解4 (3,3),z=33解5 (8/3,4),z=37.33 (5) 對“解5

6、”分枝定界：“解5”的坐標(biāo)(8/3,4)， 為非整數(shù)，添加x12 （ x13為非可行域），優(yōu)化結(jié)果為X=(2,17/4)，再添加x2=4 和x2=5 。求得整數(shù)解(2,4)，目標(biāo)值34；整數(shù)解(0,5)，目標(biāo)值30，取(2,4)。如圖“解7”。解7 (2,4),z=34(6) 剪枝：將“解4”X=(3,3)，z=33與 “解7”X=(2,4)，z=34。相比較，“解7”目標(biāo)值為34，對應(yīng)的最優(yōu)方案 。4.2 0-1規(guī)劃管理運(yùn)籌學(xué) 第4章 整數(shù)規(guī)劃與分配問題0-1規(guī)劃的概念與隱枚舉法簡介0-1變量在數(shù)學(xué)建模中的應(yīng)用案例1：球隊(duì)隊(duì)員篩選案例2：選址問題案例3：集合覆蓋問題4.2.1 0-1規(guī)劃的概

7、念0-1規(guī)劃是一種特殊類型的整數(shù)規(guī)劃，即決策變量只取0或1。0-1規(guī)劃在整數(shù)規(guī)劃中占有重要地位，許多實(shí)際問題，例如指派問題、選址問題、送貨問題都可歸結(jié)為此類規(guī)劃。求解0-1規(guī)劃的常用方法是隱枚舉法，對各種特殊問題還有一些特殊方法，例如求解指派問題的匈牙利方法。0-1規(guī)劃的數(shù)學(xué)模型為：管理運(yùn)籌學(xué) 第4章 整數(shù)規(guī)劃與分配問題4.2.2 隱枚舉法簡介管理運(yùn)籌學(xué) 第4章 整數(shù)規(guī)劃與分配問題1.化成標(biāo)準(zhǔn)形式(1)目標(biāo)函數(shù):min ,cj0。目標(biāo)若max,目標(biāo)系數(shù)改變符號,變?yōu)閙in;(2)若cj1) 項(xiàng)工作任務(wù)，需要 m(n1)個人去完成，并且每個人只干一件工作，每項(xiàng)工作都必須有人干，通過權(quán)衡，合理分派

8、任務(wù)，使總的消耗(或收益)達(dá)到最小(或最大)的0-1規(guī)劃問題，稱為分配問題(Assignment Problem，AP)當(dāng)n=m時為人員與任務(wù)平衡，nm為人多任務(wù)少，nm為人少任務(wù)多，其數(shù)學(xué)模型如下。人少任務(wù)多(nm)人員與任務(wù)平衡(n=m)4.3.1 分配問題數(shù)學(xué)模型管理運(yùn)籌學(xué) 第4章 整數(shù)規(guī)劃與分配問題匈牙利法是1955年庫恩(W.W.Kuhu) 引用匈牙利數(shù)學(xué)家考尼格(D.Konig) 關(guān)于“一個矩陣中獨(dú)立0元素最多個數(shù)等于能夠覆蓋所有0元素的最少直線數(shù)”的定理而提出的分配問題的解題方法。雖然在此以后方法不斷改進(jìn)，但仍沿用這個名稱。匈牙利法解題首先要將模型標(biāo)準(zhǔn)化（人員任務(wù)平衡、目標(biāo)極?。?/p>

9、。(1) 若人員數(shù)(n)任務(wù)數(shù)(m)，則添加(n-m=k)個虛擬任務(wù)，效率矩陣中對應(yīng)的元素為0；(2) 若人員數(shù)(n)任務(wù)數(shù)(m)，則添加(m-n=s)個虛擬人員，效率矩陣中對應(yīng)的元素為0；(3) 若目標(biāo)函數(shù)為極大，則令 ，構(gòu)造新的效率矩陣 將目標(biāo)函數(shù)轉(zhuǎn)化為最小。4.3.2 匈牙利法管理運(yùn)籌學(xué) 第4章 整數(shù)規(guī)劃與分配問題4.3.2 匈牙利法管理運(yùn)籌學(xué) 第4章 整數(shù)規(guī)劃與分配問題證：匈牙利法迭代步驟每行減去該行最小數(shù)每列減去該列最小數(shù)先看行，只有1個0，標(biāo)記為，劃去所在列，轉(zhuǎn)下行，直到最后行再看列，只有1個0，標(biāo)記為，劃去所在行，轉(zhuǎn)下列，直到最后列重復(fù)上述過程三種結(jié)局處取1，其余取0，得最優(yōu)解從

10、未被劃去的數(shù)找最小數(shù)k，末被劃去的數(shù)字減k，覆蓋直線交叉處加k個數(shù)=n個數(shù)n從閉回路任一0出發(fā)，在轉(zhuǎn)彎處按順序編號，取單號(或雙號)標(biāo)記存在0的閉回路管理運(yùn)籌學(xué) 第4章 整數(shù)規(guī)劃與分配問題【例4.7】 用匈牙利法求解引例中最小化分配問題。匈牙利法迭代例題管理運(yùn)籌學(xué) 第4章 整數(shù)規(guī)劃與分配問題【例4.8】 用匈牙利法求解最小化分配問題。k=2最優(yōu)方案：x11=x23=x35=x44=x51=1,其余=0。最優(yōu)值=34匈牙利法迭代例題管理運(yùn)籌學(xué) 第4章 整數(shù)規(guī)劃與分配問題分配甲、乙、丙、丁四個人去完成A、B、C、D、E五項(xiàng)任務(wù)，每個人完成各項(xiàng)任務(wù)的時間如表所示。由于任務(wù)數(shù)多于人數(shù)，故考慮：（1）任

11、務(wù)E必須完成，其他4項(xiàng)中可任選3項(xiàng)完成；（2）其中有一個人完成兩項(xiàng)，其他每人完成一項(xiàng)；（3）任務(wù)A由甲或丙完成，任務(wù)C由丙或丁完成，任務(wù)E由甲、乙或丁完成，且規(guī)定4人中丙或丁完成兩項(xiàng)任務(wù)，其他每人完成一項(xiàng)。試分別確定最優(yōu)分配方案，使完成任務(wù)的總時間為最小。 任務(wù)人員ABCDE甲乙丙丁2539342429382742312628364220402337333245案例4-4任務(wù)分派管理運(yùn)籌學(xué) 第4章 整數(shù)規(guī)劃與分配問題（1）任務(wù)E必須完成，其他4項(xiàng)中可任選3項(xiàng)完成管理運(yùn)籌學(xué) 第4章 整數(shù)規(guī)劃與分配問題該問題為人少任務(wù)多，應(yīng)添加假想人員，但任務(wù)E必須完成，故c55應(yīng)為M。匈牙利法求解管理運(yùn)籌學(xué) 第4章 整數(shù)規(guī)劃與分配問題k=4k=1（2）其中一人完成兩項(xiàng),其他每人完成一項(xiàng)管理運(yùn)籌學(xué) 第4章 整數(shù)規(guī)劃與分配問題（3）任務(wù)A由甲或丙完成，任務(wù)C由丙或丁完成，任務(wù)E由甲、乙或丁完成，且規(guī)定4人中丙或丁完成兩項(xiàng)任務(wù)，其他每人完成一項(xiàng)。管理運(yùn)籌學(xué) 第4章 整數(shù)規(guī)劃與分配問題1.基本概念變量取整數(shù)的規(guī)劃問題稱為整數(shù)規(guī)劃。當(dāng)變量全部取整數(shù)，稱為純整數(shù)規(guī)劃；變量部分取整數(shù)，稱為混合整數(shù)規(guī)劃；變量取二進(jìn)制稱