第4章 整數(shù)規(guī)劃與分配問(wèn)題

第4章整數(shù)規(guī)劃與分配問(wèn)題重慶三峽學(xué)院關(guān)文忠/guanwenzhong1/31/2023管理運(yùn)籌學(xué)課件教學(xué)目標(biāo)與要求【教學(xué)目標(biāo)】通過(guò)本章學(xué)習(xí)，了解求解整數(shù)規(guī)劃“分枝定界法”的其中思路，掌握0-1變量在數(shù)學(xué)建模中的應(yīng)用；熟練掌握“匈牙利法”，至少掌握一種軟件求得整數(shù)規(guī)劃及分配問(wèn)題的最優(yōu)解?！局R(shí)結(jié)構(gòu)】1/31/2023管理運(yùn)籌學(xué)課件本章主要內(nèi)容4.1整數(shù)規(guī)劃4.1.1整數(shù)規(guī)劃的概念4.1.2分枝定界法的基本思路*4.20-1規(guī)劃4.2.10-1規(guī)劃的概念4.2.20-1規(guī)劃的隱枚舉法簡(jiǎn)介*4.2.40-1變量在數(shù)學(xué)建模中的用途案例4-1球隊(duì)隊(duì)員篩選案例4-2選址問(wèn)題案例4-3集合覆蓋問(wèn)題4.3分配問(wèn)題4.3.1分配問(wèn)題數(shù)學(xué)模型4.3.2分配問(wèn)題的解題方法——匈牙利法案例4-4任務(wù)分派本章小結(jié)1/31/2023管理運(yùn)籌學(xué)課件導(dǎo)入案例——集裝箱托運(yùn)計(jì)劃某廠擬用集裝箱托運(yùn)甲、乙兩種貨物，每箱的體積、質(zhì)量、可獲得的利潤(rùn)以及托運(yùn)所受到的限制如表4-1所示。問(wèn)怎樣安排托運(yùn)計(jì)劃，可使利潤(rùn)最大？貨物每箱體積/米3每箱質(zhì)量/50千克每箱利潤(rùn)/百元甲乙384356托運(yùn)限制4024

設(shè)x1,x2表示兩種貨物裝載數(shù)量(整數(shù))，依題意有如下數(shù)學(xué)模型：在實(shí)際中，許多要求變量取整的數(shù)學(xué)模型，稱為整數(shù)規(guī)劃。本章將討論整數(shù)規(guī)劃求解的基本思路、0-1變量的用法、分配問(wèn)題及匈牙利法，以及利用Excel,Lingo,WinQSB求解的演示。1/31/2023管理運(yùn)籌學(xué)課件4.1.1整數(shù)規(guī)劃的基本概念整數(shù)規(guī)劃（integerprogramming，IP）是指一類要求問(wèn)題中的全部或一部分變量為整數(shù)的數(shù)學(xué)規(guī)劃。在整數(shù)規(guī)劃中，依決策變量的取值不同，又可進(jìn)一步劃分：

如果所有變量都限制為整數(shù)，則稱為純整數(shù)規(guī)劃（PureIntegerProgramming，PIP）；

如果僅一部分變量限制為整數(shù)，則稱為混合整數(shù)規(guī)劃（MixedIntegerProgramming，MIP）；

變量取二進(jìn)制的整數(shù)規(guī)劃則稱為0-1規(guī)劃（BinaryIntegerProgramming，BIP）。1/31/2023管理運(yùn)籌學(xué)課件4.1.2分枝定界法的基本思路*【例4.1】用圖解法求解整數(shù)規(guī)劃分枝定界法(BranchandBoundMethod)用于求解整數(shù)規(guī)劃問(wèn)題，是在20世紀(jì)60年代初，由LandDoig和Dakin等人提出的。解(1)繪制直角坐標(biāo)系，圖示約束條件，圖示目標(biāo)函數(shù)一根基線(z=30)，使其平行移動(dòng)，求得非整數(shù)最優(yōu)解。該解的坐標(biāo)為(72/23,88/23)，不在網(wǎng)格線的交叉點(diǎn)上，非整數(shù)解（非可行解）。①(2)對(duì)“解1”分枝定界：選取x1進(jìn)行分枝定界：在原模型的基礎(chǔ)上，分別添加x1≤3,x1≥4。優(yōu)化結(jié)果“解2”，X=(3,31/8)，z=38.25；“解3”，X=(4,8/3)，z=36，均為非整數(shù)（非可行解）。(3)先對(duì)“解2”分枝定界：“解2”的坐標(biāo)為(3,31/8)，分別添加x2≤3，x2≥4，優(yōu)化結(jié)果“解4”，X=(3,3)，z=33，為可行解；“解5”，X=(8/3,4)，z=37.33，為非可行解。(4)再對(duì)“解3”分枝定界：“解3”的坐標(biāo)，為非整數(shù)，添加x2≤2（x2≥3為非可行域），優(yōu)化結(jié)果為X=(9/2,2)，z=34.5；再添加x1=4,x1≥5。解得整數(shù)解X=(4,2)，z=32和非整數(shù)解X=(21/4,1)，目標(biāo)值z(mì)=31.25；整數(shù)解目標(biāo)值大于非整數(shù)解，取(4,2)，得“解6”。01234567891011121314x1012345678x2②(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)對(duì)“解5”分枝定界：“解5”的坐標(biāo)(8/3,4)，為非整數(shù)，添加x1≤2（x1≥3為非可行域），優(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)剪枝：上述有三個(gè)區(qū)域的整數(shù)解分別為“解4”X=(3,3)，z=33；“解6”X=(4,2)，z=32；“解7”X=(2,4)，z=34。相比較，目標(biāo)值最大的為34，對(duì)應(yīng)的最優(yōu)方案。演示：利用WinQSB,ExcelORM+規(guī)劃求解,ExcelORM+Lingo求例4.11/31/2023管理運(yùn)籌學(xué)課件4.2.10-1規(guī)劃的概念0-1規(guī)劃是一種特殊類型的整數(shù)規(guī)劃，即決策變量只取0或1。0-1規(guī)劃在整數(shù)規(guī)劃中占有重要地位，許多實(shí)際問(wèn)題，例如指派問(wèn)題、選址問(wèn)題、送貨問(wèn)題都可歸結(jié)為此類規(guī)劃。求解0-1規(guī)劃的常用方法是隱枚舉法，對(duì)各種特殊問(wèn)題還有一些特殊方法，例如求解指派問(wèn)題用匈牙利方法就比較方便。0-1規(guī)劃的數(shù)學(xué)模型為：1/31/2023管理運(yùn)籌學(xué)課件4.2.2隱枚舉法簡(jiǎn)介1.化成標(biāo)準(zhǔn)形式

(1)目標(biāo)函數(shù):min,cj>0

(2)目標(biāo)若max,目標(biāo)系數(shù)改變符號(hào),變?yōu)閙in;

(2)若cj<0,令yj=1-xj使其變正;

(3)目標(biāo)函數(shù)中,變量按目標(biāo)系數(shù)從小到大排列,約束條件中也跟著相應(yīng)改變.2.令標(biāo)準(zhǔn)化后的0-1問(wèn)題所有變量為0,若滿足約束,即為最優(yōu),否則轉(zhuǎn)下步.3.按目標(biāo)函數(shù)中排列順序依次令各變量分別取1或0,進(jìn)行枚舉.1/31/2023管理運(yùn)籌學(xué)課件4.2.40-1變量在數(shù)學(xué)建模中的應(yīng)用1/31/2023管理運(yùn)籌學(xué)課件案例4-1球隊(duì)隊(duì)員篩選預(yù)備隊(duì)員身高/厘米位置ABCDEF193191187186180185中鋒中鋒前鋒前鋒后衛(wèi)后衛(wèi)某?；@球隊(duì)準(zhǔn)備從以下6名預(yù)備隊(duì)員中選拔3名為正式隊(duì)員，并使平均的身高盡可能高。這六名預(yù)備隊(duì)員情況如表所示。

隊(duì)員的挑選要滿足下列條件：

(1)6位預(yù)備隊(duì)員選3名。

(2)至少補(bǔ)充1名后衛(wèi)人員。

(3)B或E中間最多入選1名。

(4)最多補(bǔ)充1名中鋒。

(5)無(wú)論B或D入選，F(xiàn)都不能入選。1/31/2023管理運(yùn)籌學(xué)課件案例4-2選址問(wèn)題某公司在城市東、西、南三區(qū)擬建立門市部。計(jì)劃有7個(gè)位置(點(diǎn))Aj(j=1,…,7)可供選擇。規(guī)定：在東區(qū)，由A1,A2,A3三個(gè)點(diǎn)至多選兩個(gè)；在西區(qū)，由A4,A5兩個(gè)點(diǎn)至少選一個(gè)；在南區(qū)，由A6,A7兩個(gè)點(diǎn)至少選一個(gè)。設(shè)各位置建點(diǎn)的成本與預(yù)計(jì)利潤(rùn)見(jiàn)表，若建點(diǎn)總成本控制在100萬(wàn)元以內(nèi)，試問(wèn)應(yīng)該選取哪幾個(gè)點(diǎn)可使年利潤(rùn)為最大？。地點(diǎn)A1A2A3A4A5A6A7建點(diǎn)成本20202524222423估計(jì)利潤(rùn)30303534384045數(shù)學(xué)模型為：1/31/2023管理運(yùn)籌學(xué)課件案例4-3集合覆蓋問(wèn)題街道1街道2街道3街道4街道5街道6街道101020303020街道210025352010街道320250153020街道430351501525街道530203015014街道620102025140某區(qū)有6個(gè)街道。這個(gè)區(qū)必須確定在什么地方修建消防站。在保證至少有一個(gè)消防站在每個(gè)街道的15min行駛時(shí)間內(nèi)的情況下，這個(gè)區(qū)希望修建的消防站最少。各街道間行駛時(shí)間如表1/31/2023管理運(yùn)籌學(xué)課件4.3.1分配問(wèn)題數(shù)學(xué)模型項(xiàng)目張王李趙仰泳蛙泳蝶泳自由泳37433330333329263842392937343029在管理活動(dòng)中，人們會(huì)經(jīng)常遇到這樣的問(wèn)題，某單位有n(n>1)項(xiàng)工作任務(wù)，需要m(n>1)個(gè)人去完成，并且每個(gè)人只干一件工作，每項(xiàng)工作都必須有人干，通過(guò)權(quán)衡，合理分派任務(wù)，使總的消耗(或收益)達(dá)到最小(或最大)的0-1規(guī)劃問(wèn)題，稱為分配問(wèn)題(AssignmentProblem，AP)導(dǎo)入案例運(yùn)動(dòng)項(xiàng)目分配問(wèn)題某游泳隊(duì)有四名運(yùn)動(dòng)員，其平時(shí)訓(xùn)練成績(jī)(s/50m)如表所示。問(wèn)如何安排可使總成績(jī)最好？人員任務(wù)效率矩陣cij1/31/2023管理運(yùn)籌學(xué)課件4.3.1分配問(wèn)題數(shù)學(xué)模型1/31/2023管理運(yùn)籌學(xué)課件4.3.2匈牙利法1/31/2023管理運(yùn)籌學(xué)課件4.3.2匈牙利法【例4.7】用匈牙利法求引例中的最小化分配問(wèn)題。①⑥②③④⑤1/31/2023管理運(yùn)籌學(xué)課件4.3.2匈牙利法【例4.8】用匈牙利法求引例中的最小化分配問(wèn)題。k=2最優(yōu)方案：，其余=0，最優(yōu)值z(mì)=34

1/31/2