第4章 整數(shù)規(guī)劃與分配問題 管理運籌學(xué) 重慶三峽學(xué)院

1、第,4,章,整數(shù)規(guī)劃與分配問題,目錄,4,整數(shù)規(guī)劃,1,2,3,0-1,規(guī)劃,分配問題,本章小結(jié)與作業(yè),管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,4.1,整數(shù)規(guī)劃,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,導(dǎo)入案例,整數(shù)規(guī)劃的基本概念,圖解法,分枝定界法的基本思路,4.1.1,導(dǎo)入案例集裝箱托運計劃,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,貨物,每箱體積,m,3,每箱質(zhì)量,50kg,每箱利潤,百元,甲,乙,3,8,4,3,5,6,托運,限制,40,24,某廠擬用集裝箱托運甲、乙兩種貨物，每箱的體積、質(zhì)量、可獲得的利

2、,潤以及托運所受到的限制如表所示。問怎樣安排托運計劃，可使利潤最,大,1,2,1,2,1,2,1,2,1,2,max z,5,6,3,8,4,3,0,x,x,x,x,x,x,x,x,x,x,40,24,取整數(shù),設(shè),x1,x2,表示兩種貨物裝載數(shù)量,整,數(shù),依題意有如下數(shù)學(xué)模型,在實際中，許多要求變量取整,的數(shù)學(xué)模型，稱為整數(shù)規(guī)劃,4.1.2,整數(shù)規(guī)劃的基本概念,整數(shù)規(guī)劃,integer programming,IP,是指一類要求問,題中的全部或一部分變量為整數(shù)的數(shù)學(xué)規(guī)劃。在整數(shù)規(guī)劃,中，依決策變量的取值不同，又可進一步劃分,如果所有變量都限制為整數(shù)，則稱為純整數(shù)規(guī)劃,Pure,Integer

3、Programming,PIP,如果僅一部分變量限制為整數(shù)，則稱為混合整數(shù)規(guī)劃,Mixed Integer Programming,MIP,變量取二進制的整數(shù)規(guī)劃則稱為,0-1,規(guī)劃,Binary Integer,Programming,BIP,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,4.1.3,圖解法,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,例,4.1,用圖解法求解整數(shù)規(guī)劃,1,2,1,2,1,2,1,2,1,2,max,5,6,3,8,40,1,4,3,24,2,0,z,x,x,x,x,x,x,x,x,x,x,取整數(shù),1,建立直角坐標

4、系,圖示約束條件，確定,可行域,2,圖示目標函數(shù)一,根基線，按目標要求,平行移動，直到與可,行域相交,3,求出交點坐標與,目標值,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,x1,0,1,2,3,4,5,6,7,8,x,2,X,2,4),z=34,4.1.4,分枝定界法的基本思路,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,例,4.1,分枝定界法求解,1,2,1,2,1,2,1,2,1,2,max,5,6,3,8,40,1,4,3,24,2,0,z,x,x,x,x,x,x,x,x,x,x,取整數(shù),分枝定界法,Branch and Bound,M

5、ethod,用于求解整數(shù)規(guī)劃問題,是在,20,世紀,60,年代初，由,Land,Doig,和,Dakin,等人提出的,解,1,承例,4.1,由圖解法知，一般線性規(guī)劃解的坐標為,72/23,88/23,不在,網(wǎng)格線的交叉點上，非整數(shù)解（非可行解,2,對“解,1,分枝定界：選取,x1,進行分枝定界：在原模型的基礎(chǔ)上，分別添,加,x13,x14,優(yōu)化結(jié)果,解,2,X=(3,31/8,解,3,X=(4,8/3,均為非,整數(shù)（非可行解,3,先對“解,2,2,的坐標為,3,31/8,分別添加,x23,x24,優(yōu)化結(jié)果,解,4,X=(3,3,z=33,為可行解；“解,5,X=(8/3,4,z=37.33,為

6、非可行解，由于其目標值大于解,4,的目標值，先保留，待進一步分枝定界,4,再對“解,3,分枝定界：“解,3,的,x2,坐標,為非整數(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,目標值,z=33,這兩個整數(shù)解和非,整數(shù)解的目標值均不大于整數(shù)解,解,4,不再保留,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,x1,0,1,2,3,4,5,6,7,8,x,2,解,6,9/2,2),z=34.5,解,3,4,8/3,解,1,72/2

7、3,88/23,解,2,3,31/8,解,4,3,3),z=33,解,5,8/3,4),z=37.33,5,對“解,5,分枝定界：“解,5,的坐標,8/3,4,為非整數(shù)，添加,x12,x13,為非可行域），優(yōu)化結(jié)果為,X=(2,17/4,再添加,x2=4,和,x2=5,求得整數(shù)解,2,4,目標值,34,整數(shù)解,0,5,目標值,30,取,2,4,如圖“解,7,解,7,2,4),z=34,6,剪枝：將“解,4,X=(3,3,z=33,與,解,7,X=(2,4,z=34,相比較，“解,7,目標值為,34,對應(yīng)的最優(yōu)方案,4.2 0-1,規(guī)劃,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配

8、,問,題,0-1,規(guī)劃的概念與隱枚舉法簡介,0-1,變量在數(shù)學(xué)建模中的應(yīng)用,案例,1,球隊隊員篩選,案例,2,選址問題,案例,3,集合覆蓋問題,4.2.1 0-1,規(guī)劃的概念,0-1,規(guī)劃是一種特殊類型的整數(shù)規(guī)劃，即決策變量只取,0,或,1,0-1,規(guī)劃在整數(shù)規(guī)劃中占有重要地位，許多實際問,題，例如指派問題、選址問題、送貨問題都可歸結(jié)為此,類規(guī)劃。求解,0-1,規(guī)劃的常用方法是隱枚舉法，對各種,特殊問題還有一些特殊方法，例如求解指派問題的匈牙,利方法,0-1,規(guī)劃的數(shù)學(xué)模型為,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,0,1,max(min,z,CX,AX,b,s,t

9、,X,取,或,4.2.2,隱枚舉法簡介,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,1,2,3,1,2,3,1,2,3,1,2,1,2,3,max,3,2,2,1,4,4,2,s.t,3,3,0,1,z,x,x,x,x,x,x,x,x,x,x,x,x,x,x,例,求最優(yōu)解,或,1,2,3,1,2,3,1,2,3,1,2,1,2,3,min,min,3,2,2,4,4,s.t,3,0,1,j,c,w,x,x,x,x,x,x,x,x,x,x,x,x,x,x,改變,符號,變?yōu)?或,1,1,2,2,3,3,1,1,1,x,x,x,x,x,x,令,1,2,3,1,2,3,1,2,

10、3,1,2,1,2,3,min,3,5,2,0,4,2,s.t,1,0,1,w,x,x,x,x,x,x,x,x,x,x,x,x,x,x,或,2,3,1,2,3,1,2,3,1,2,1,1,2,3,min,3,5,2,0,4,2,s.t,1,0,1,w,x,x,x,x,x,x,x,x,x,x,x,x,x,x,目標系數(shù)升序排序,或,1,化成標準形式,1,目標函數(shù),min ,cj0,目標若,max,目標系數(shù)改變符號,變?yōu)?min,2,若,cj0,令,yj=1-xj,使其變正,3,目標函數(shù)中,變量按目標系數(shù),從小到大排列,約束條件中也跟,著相應(yīng)改變,2,令標準化后的,0-1,問題所有變,量為,0,若滿

11、足約束,即為最優(yōu),否,則轉(zhuǎn)下步,3,按目標函數(shù)中排列順序依次,令各變量分別取,1,或,0,進行枚舉,1,2,3,0,1,0,x,x,x,解得,1,2,3,1,0,1,x,x,x,max,4,z,4.2.4 0-1,變量在數(shù)學(xué)建模中的應(yīng)用,1) n,中（至少、最多）選,k,個,2,選甲必選乙，選乙不一定選,3,選了甲或乙，丙就不能入選，選了丙，甲、乙都不能入選,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,1,1,0,1,x,x,x,x,x,x,x,甲,丙,乙,丙,甲,乙,丙,或,1,0,1,n,j,j,j,x,k,x,或,0,1,j,x,x,x,乙,甲,或,4,變量以離散

12、數(shù)值,c1,c2,cn,1,1,1,0,1,1,n,j,j,j,n,j,j,j,y,c,x,x,x,j,n,或,解,該問題可表示成如下約束,1,2,3,4,1,2,3,4,3,5,7,9,1,0,1,1,4,j,y,x,x,x,x,x,x,x,x,x,j,或,4.2.4 0-1,變量在數(shù)學(xué)建模中的應(yīng)用,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,例,4.3,用,0-1,變量表示約束,變量,y,取,3,5,7,9,中的一個,例,4.4,用,0-1,變量表示約束,只需滿足一個,5,兩個約束滿足一個,1,1,2,2,1,0,1,f,X,g,My,f,X,g,M,y,y,或,1

13、,2,1,1,2,2,1,2,1,2,1,2,1,2,2,3,2,10,1,0,1,2,1,3,2,10,0,1,x,x,y,M,x,x,y,M,y,y,y,y,x,x,y,M,x,x,yM,y,解,該問題可表示成,或,或,或,1,2,1,2,2,3,2,10,x,x,x,x,和,4.2.4 0-1,變量在數(shù)學(xué)建模中的應(yīng)用,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,6) n,個約束（至少、最多,滿足,k,個,1,1,1,0,1,1,2,n,n,n,j,j,f,X,g,My,f,X,g,My,y,n,k,y,j,n,M,或,1,2,1,3,3,4,5,2,2,6,x,x

14、,x,x,x,x,1,2,1,1,2,3,3,3,4,4,1,2,3,4,14,5,2,2,6,2,0,1,x,x,y,M,x,y,M,x,y,M,x,x,y,M,y,y,y,y,y,或,例,4.5,以下四個約束中至少,滿足兩個,解,該問題可表示成,4.2.4 0-1,變量在數(shù)學(xué)建模中的應(yīng)用,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,7,兩組約束滿足一組,2,1,5,1,2,2,5,2,1,2,1,2,4,0,4,3,1,0,1,x,y,M,x,y,M,x,y,M,x,y,M,y,y,y,或,2,5,2,5,4,0,4,1,3,1,0,1,x,yM,x,yM,x,y,

15、M,x,y,M,y,或,或,2,5,2,5,4,0,4,3,x,x,x,x,則,否則,例,4.6,用,0-1,表示：若,解,該問題可表示成,1,1,2,2,3,3,4,4,1,1,0,1,f,X,g,My,f,X,g,My,f,X,g,M,y,f,X,g,M,y,y,或,4.2.4 0-1,變量在數(shù)學(xué)建模中的應(yīng)用,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,8,分段函數(shù)的,0-1,表述,0,0,0,0,1,x,f,x,k,cx,x,f,x,yk,cx,y,Mx,x,My,y,當(dāng),當(dāng),對,可表示為,或,生產(chǎn)過程的種類,固定投資,元,生產(chǎn)成本,元,千克,最大日產(chǎn)量,千克,甲

16、,乙,丙,1,000,2,000,3,000,5,4,3,2,000,3,000,4,000,例,P76,第,6,題,某企業(yè)接受某項產(chǎn)品訂貨,需求量為每日,3,500,千克，現(xiàn)有,3,種生產(chǎn),過程供選擇，各生產(chǎn)過程所需固定投資,成本,生產(chǎn)成本，最大日產(chǎn)量如表,所示。問,企業(yè)需要決定采用哪種,一種,或多種,生產(chǎn)過程和日產(chǎn)量多少千克,才能既保證按合同交貨又使總成本最小,試列出該問題的整數(shù)規(guī)劃數(shù)學(xué)模型,4.2.4 0-1,變量在數(shù)學(xué)建模中的應(yīng)用,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,1,0,1,2,3,i,i,i,i,y,x,i,i,采用第,種生產(chǎn)過程,不采用第,種生產(chǎn)

17、過程,采用第,種生產(chǎn)過程生產(chǎn)的數(shù)量,1,2,3,1,2,3,1,2,3,1,1,2,2,3,3,1,1,2,2,3,3,13,13,min,1000,2000,3000,5,4,3,3000,4000,0,1,z,y,y,y,x,x,x,x,x,x,x,y,x,y,x,y,s,t,y,x,M,y,x,M,y,x,M,y,x,3500,2000,或,0,解,設(shè),采用生產(chǎn)過程丙生產(chǎn),3500kg,總成本,13500,元,生產(chǎn),過程,固定投資,元,生產(chǎn)成本,元,千克,最大日產(chǎn)量,千克,甲,乙,丙,1,000,2,000,3,000,5,4,3,2,000,3,000,4,000,4.2.4 0-1,

18、變量在數(shù)學(xué)建模中的應(yīng)用,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,某?；@球隊準備從以下,6,名預(yù)備隊員中選,拔,3,名為正式隊員，并使平均的身高盡可,能高。這六名預(yù)備隊員情況如表所示,隊員的挑選要滿足下列條件,1) 6,位預(yù)備隊員選,3,名,2,至少補充,1,名后衛(wèi)人員,3) B,或,E,中間最多入選,1,名,4,最多補充,1,名中鋒,5,無論,B,或,D,入選,F,都不能入選,案例,4-1,球隊隊員篩選,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,預(yù)備隊員,身高,cm,位置,A,B,C,D,E,F,193,191,187,186,180,18

19、5,中鋒,中鋒,前鋒,前鋒,后衛(wèi),后衛(wèi),s.t,1,2,3,4,5,6,max,193,191,187,186,180,185,z,x,x,x,x,x,x,0,1,i,i,x,i,第,名未進入正式隊,設(shè),第,名進入正式隊,5,6,1,2,x,x,1,2,3,4,5,6,3,1,x,x,x,x,x,x,2,5,1,3,x,x,1,2,1,4,x,x,2,6,4,6,1,5,1,x,x,x,x,16,0,1,x,或,案例,4-2,選址問題,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,地點,A,1,A,2,A,3,A,4,A,5,A,6,A,7,建點成本,20,20,25,2

20、4,22,24,23,估計利潤,30,30,35,34,38,40,45,某公司在城市東、西、南,三區(qū)擬建立門市部。計劃,有,7,個位置,點,A,j,j=1,7,可供選擇。規(guī)定,在東區(qū)，由,A,1,A,2,A,3,三個,點至多選兩個；在西區(qū),由,A,4,A,5,兩個點至少選一,個；在南區(qū)，由,A,6,A,7,兩,個點至少選一個。設(shè)各位,置建點的成本與預(yù)計利潤,見表，若建點總成本控制,在,100,萬元以內(nèi)，試問應(yīng),該選取哪幾個點可使年利,潤為最大,1,1,2,7,0,i,i,i,A,x,i,A,L,當(dāng),被選中,設(shè),當(dāng),未被選中,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,

21、4,5,6,7,max,30,30,35,34,38,40,45,20,20,25,24,22,24,23,100,2,s.t,1,1,0,1,i,z,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,東區(qū),西區(qū),南區(qū),或,數(shù)學(xué)模型為,某區(qū)有,6,個街道。這個區(qū)必須確定在什,么地方修建消防站。在保證至少有一,個消防站在每個街道的,15min,行駛時,間內(nèi)的情況下，這個區(qū)希望修建的消,防站最少。各街道間行駛時間如表,案例,4-3,集合覆蓋問題,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,街道,1,街道,2,街道,3,街道,4,街道,5

22、,街道,6,街道,1,0,10,20,30,30,20,街道,2,10,0,25,35,20,10,街道,3,20,25,0,15,30,20,街道,4,30,35,15,0,15,25,街道,5,30,20,30,15,0,14,街道,6,20,10,20,25,14,0,1,2,1,2,6,3,4,3,4,5,4,5,6,2,5,6,16,1,1,1,1,1,1,0,1,x,x,x,x,x,x,x,s,t,x,x,x,x,x,x,x,x,x,x,或,1,0,1,6,i,i,i,i,x,L,第,街道設(shè)消防站,第,街道不設(shè)消防站,設(shè),1,2,3,4,5,6,min,z,x,x,x,x,x,x,

23、目標,消防站數(shù)目最少,4.3,分配問題,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,分配問題數(shù)學(xué)模型,匈牙利法,案例,任務(wù)分派,4.3.1,分配問題數(shù)學(xué)模型,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,項目,張,王,李,趙,仰泳,蛙泳,蝶泳,自由泳,37,43,33,30,33,33,29,26,38,42,39,29,37,34,30,29,導(dǎo)入案例,任務(wù)分配,某游泳隊有四名運動員，其平,時訓(xùn)練成績,s/50m,如表所示,問如何安排可使總成績最好,人員,任務(wù),效率矩陣,cij,1,0,ij,i,j,i,j,x,第,分配給第,人,第,不分給第,人

24、,設(shè),11,12,13,14,21,22,23,24,31,32,33,34,41,42,43,44,min,37,33,38,37,43,33,42,34,33,29,39,30,30,26,29,29,z,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,11,12,13,14,21,22,23,24,31,32,33,34,41,42,43,44,1,1,1,1,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,每項任務(wù),交給一人,0,1,1,4,1,4,ij,x,i,j,或,11,21,31,41,12,22,32,42,13,23,33,34,14,24,

25、34,44,1,1,1,1,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,每人分給,一項任務(wù),s,t,在管理活動中，人們會經(jīng)常遇到這樣的問題，某單位有,n(n1,項工作任務(wù),需要,m(n1,個人去完成，并且每個人只干一件工作，每項工作都必須有人,干，通過權(quán)衡，合理分派任務(wù)，使總的消耗,或收益,達到最小,或最大,的,0,1,規(guī)劃問題，稱為分配問題,Assignment Problem,AP,當(dāng),n=m,時為人員與任務(wù)平衡,nm,為人多任務(wù)少,nm,為人少任務(wù)多，其,數(shù)學(xué)模型如下,人少任務(wù)多,nM,人多任務(wù)少,nm,人員與任務(wù)平衡,n=m,1,1,1,1,min,max,1,1,

26、s.t,0,1,1,2,1,2,m,n,ij,ij,i,j,n,ij,j,m,ij,i,ij,z,z,c,x,x,x,x,i,m,j,n,或,4.3.1,分配問題數(shù)學(xué)模型,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,1,1,1,1,min,max,1,1,s.t,0,1,1,2,1,2,m,n,ij,ij,i,j,n,ij,j,m,ij,i,ij,z,z,c,x,x,x,x,i,m,j,n,或,1,1,1,1,min,max,1,1,s.t,0,1,1,2,1,2,m,n,ij,ij,i,j,n,ij,j,m,ij,i,ij,z,z,c,x,x,x,x,i,m,j,n,

27、或,匈牙利法是,1955,年庫恩,W.W.Kuhu,引用匈牙利數(shù)學(xué)家考尼格,D.Konig,關(guān)于“一個矩陣中獨立,0,元素最多個數(shù)等于能夠覆蓋所有,0,元,素的最少直線數(shù)”的定理而提出的分配問題的解題方法。雖然在此以,后方法不斷改進，但仍沿用這個名稱,匈牙利法解題首先要將模型標準化（人員任務(wù)平衡、目標極小,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,若目標函數(shù)為極大，則令,構(gòu)造新的效率矩陣,將目標函數(shù)轉(zhuǎn)化為最小,4.3.2,匈牙利法,管,理,運,籌,學(xué)

28、,第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,ij,M,ij,b,c,c,max,M,ij,n,n,c,c,4.3.2,匈牙利法,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,ij,M,ij,b,c,c,max,M,ij,n,n,c,c,1,1,n,n,ij,ij,i,j,z,c,x,1,1,1,1,max,min,n,n,n,n,ij,ij,ij,ij,i,j,i,j,c,x,b,x,等價于,1,1,n,n,M,ij,ij,i,j,nc,b,x,1,1,n,n,M,ij,ij,i,j,c,b,x,1,1,1,1,n,n,n,n,M,ij,ij,ij,i,j,i,j,

29、c,x,b,x,證,匈牙利法迭代步驟,每行減去該行最小數(shù),每列減去該列最小數(shù),先看行，只有,1,個,0,標記為,劃去所在列，轉(zhuǎn)下行，直到最后行,再看列，只有,1,個,0,標記為,劃去所在行，轉(zhuǎn)下列，直到最后列,重復(fù)上述過程,三種結(jié)局,處取,1,其余取,0,得最優(yōu)解,從未被劃去的數(shù)找,最小數(shù),k,末被劃,去的數(shù)字減,k,覆,蓋直線交叉處加,k,個數(shù),n,個數(shù),n,從閉回路任一,0,出發(fā),在轉(zhuǎn)彎處按順序編,號，取單號,或雙號,標記,存在,0,的閉回路,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,例,4.7,用匈牙利,法求解引例中最小化,分配問題,匈牙利法迭代例題,管,理,運

30、,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,X,37,33,38,37,43,33,42,34,33,29,39,30,30,26,29,29,C,min,33,33,29,26,4,0,5,4,10,0,9,1,4,0,10,1,4,0,3,3,min,4,0,3,1,0,0,2,4,6,0,6,0,0,0,7,0,0,0,0,2,1,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,X,129,z,最優(yōu)值,37,33,38,37,43,33,42,34,33,29,39,30,30,26,29,29,C

31、,例,4.8,用匈牙,利法求解最小化分,配問題,12,7,9,9,9,8,9,7,7,7,7,11,12,12,9,15,14,14,7,10,4,10,10,7,9,C,min,12,7,9,9,9,7,8,9,7,7,7,7,7,11,12,12,9,7,15,14,14,7,10,7,4,10,10,7,9,4,C,解,5,0,0,2,0,3,4,0,2,0,0,4,3,5,0,8,7,5,0,1,0,6,4,3,3,5,0,2,2,2,1,2,0,0,0,0,4,5,5,2,8,7,7,0,3,0,6,6,3,5,k=2,最優(yōu)方案,x11=x23=x35=x44,x51=1,其余,0,

32、最優(yōu)值,34,匈牙利法迭代例題,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,分配甲、乙、丙、丁四個人去完成,A,B,C,D,E,五項任務(wù)，每個人,完成各項任務(wù)的時間如表所示,由于任務(wù)數(shù)多于人數(shù)，故考慮,1,任務(wù),E,必須完成，其他,4,項中可任選,3,項完成,2,其中有一個人完成兩項，其他每人完成一項,3,任務(wù),A,由甲或丙完成，任務(wù),C,由丙或丁完成，任務(wù),E,由甲、乙或丁,完成，且規(guī)定,4,人中丙或丁完成兩項任務(wù)，其他每人完成一項,試分別確定最優(yōu)分配方案，使完成任務(wù)的總時間為最小,任務(wù),人員,A,B,C,D,E,甲,乙,丙,丁,25,39,34,24,29,38,2

33、7,42,31,26,28,36,42,20,40,23,37,33,32,45,案例,4-4,任務(wù)分派,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,4,5,1,1,5,1,4,1,4,5,1,min,1,1,2,3,4,s.t,1,1,2,3,4,1,0,1,ij,ij,i,j,ij,j,ij,i,i,ij,i,z,c,x,x,i,x,j,x,x,數(shù)學(xué)模型,或,1,任務(wù),E,必須完成，其他,4,項中可任選,3,項完成,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,25,29,31,42,37,39,38,26,20,33,34,27,28,40,

34、32,24,42,36,23,45,ij,A,B,C,D,E,c,甲,乙,丙,丁,該問題為人少任務(wù)多，應(yīng)添加,假想人員，但任務(wù),E,必須完成,故,c,55,應(yīng)為,M,25,29,31,42,37,39,38,26,20,33,34,27,28,40,32,24,42,36,23,45,0,0,0,0,ij,c,M,25,29,31,42,37,39,38,26,20,33,34,27,28,40,32,24,42,36,23,45,0,0,0,0,ij,c,M,匈牙利法求解,管,理,運,籌,學(xué),第,4,章,整,數(shù),規(guī),劃,與,分,配,問,題,0,4,6,17,12,19,18,6,0,13,7

35、,0,1,13,5,1,19,13,0,22,0,0,0,0,M,min,25,20,27,23,0,0,4,6,17,7,19,18,6,0,8,7,0,1,13,0,1,19,13,0,17,0,0,0,0,5,M,min,0,0,0,0,5,k=4,0,0,2,17,3,19,14,2,0,4,11,0,1,17,0,1,15,9,0,13,4,0,0,4,5,M,k=1,0,0,2,18,3,18,13,1,0,3,11,0,1,18,0,0,14,8,0,12,4,0,0,5,5,M,0,1,0,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,X,29,20,32,24,105,z,1,2,3,25,29,31,42,37,25,29,31,42,37,0,0,0,39