(5.3.6)-2.3指派問題數(shù)學(xué)建模

腳本——指派問題(ppt1,ppt2)同學(xué)，你好，今天我們來學(xué)習(xí)規(guī)劃模型中的指派問題。(ppt3)我們先來看指派問題中的數(shù)學(xué)模型。(ppt4)（動畫1）首先提出問題。（動畫2）設(shè)有??個人被分配去完成??項(xiàng)工作，每人完成一項(xiàng)工作．因各人的專長不同，每個人去完成同一項(xiàng)工作所花費(fèi)的時間也不相同．設(shè)??_????(??,??=1,2,…,??)是第??個人完成第??項(xiàng)工作所花費(fèi)的時間，現(xiàn)在應(yīng)當(dāng)如何分配他們的工作，才能使完成任務(wù)所花費(fèi)的總時間最少。這就是指派問題或分派問題。其中稱矩陣??=(??_????)_(??×??)為指派問題的系數(shù)矩陣。(ppt5)（動畫1）先來建立數(shù)學(xué)模型。（動畫2）為建數(shù)學(xué)模型，我們引如變量??_????，若指派第??人完成第??項(xiàng)工作，則??_????=1，否則??_????=0，其中??,??=1,2,?,??。于是指派問題的數(shù)學(xué)模型為。（動畫3）目標(biāo)函數(shù)為：minz=sigemai從1到n，sigemaj從1到n,c_ij*x_ij。其約束條件為x_ij，i從1到n求和等于1，這表示（動畫4）一個人只能完成一件事。x_ij，j從1到n求和等于1，這表示（動畫5）一件事只能被一個人完成。X_ij=0或者1。（動畫6）上述模型中若將條件??_????=0或1改為??_????≥0，則模型就是一個特殊的運(yùn)輸問題：是??=??,???_??=??_??=1的一個特殊運(yùn)輸問題。(ppt6)我們來看指派問題的匈牙利算法。(ppt7)（動畫1）引入定理（動畫2）定理1：將系數(shù)矩陣??=(??_????)中的某一行（列）中的每一個元素都減去常數(shù)??，得到一個新矩陣??=(??_????)。若以??=(??_????)為系數(shù)矩陣的指派問題的最優(yōu)解為(??

bar_????)，則原指派問題的最優(yōu)解也為(??

bar_????)，且對任意的可行解都有sigemai從1到n，sigemaj從1到n,c_ij*x_ij等于sigemai從1到n，sigemaj從1到n,b_ij*x_ij再加上a。（動畫3）定理說明：我們做某一行（列）中的每一個元素都減去常數(shù)??這種變換，不會改變最優(yōu)解，只是目標(biāo)函數(shù)改變了常數(shù)??。(ppt8)（動畫1）證明：設(shè)從??=(??_????)的第??行減去元素??，得到當(dāng)i不等于j時，??_????=??_????；當(dāng)i=k時，??_????=??_????-a。由于對任意的可行解都有sigemaj從1到n，x_ij等于1，故有sigemai從1到n，sigemaj從1到n,b_ij*x_ij等于sigemai從1到n，j從1到n，??_????x_ij減去a。（動畫2）由于(??

?_????)是以(??_????)為系數(shù)矩陣的指派問題的最優(yōu)解，所以對于任意的可行解都有sigemai從1到n，sigemaj從1到n,b_ij*x_ij大于等于sigemai從1到n，j從1到n，??_????*xbar_ij減去a。故有sigemai從1到n，sigemaj從1到n,c_ij*x_ij大于等于sigemai從1到n，sigemaj從1到n,c_ij*xbar_ij。從而(??_????)為原問題的最優(yōu)解。(ppt9)（動畫1）定理2：將系數(shù)矩陣??=(??_????)的第??行各元素減去常數(shù)??_??(??=1,2,?,??)，第??列各元素減去常數(shù)??_??，得到一個新矩陣(??_????)，即??_????=??_???????_?????_??，若??_????≥0，且(??_????)中有??個不同行不同列的零元素，即有(1,2,?,??)的一個排列(??_1??_2???_??)，使??_(??_1)=??_(??_2)=???_(??_??)=0。取矩陣(??

bar_????)，其中??

bar_(1??_1)=??

bar_(2??_2)=???

bar_(?????_??)=1，其余的??

bar_????=0，則(??

bar_????)就是以(??_????)為系數(shù)矩陣的指派問題的最優(yōu)解，也是原指派問題的最優(yōu)解。（ppt10）（動畫1）證明：由已知條件可知sigemai從1到n，j從1到n，??_????*??

bar_????等于0。而對于任意的可行解(??_????)，由于??_????≥0，故sigemai從1到n，j從1到n，??_??????_????大于等于0，即大于等于sigemai從1到n，j從1到n，??_????*??bar_????。故(??

?_????)為新指派問題的最優(yōu)解，根據(jù)定理一，它也是原指派問題的最優(yōu)解。(ppt11)（動畫1）現(xiàn)在我們來講解匈牙利算法。（動畫2）第一步：變換系數(shù)矩陣，先將系數(shù)矩陣的每一行的所有元素都減去本行中的最小元素，然后將每一列的所有元素都減去本列中的最小元素。這樣所得的變換矩陣的每一行每一列至少有一個“0”元素,而且沒有負(fù)元素。(ppt12)（動畫1）第二步：在變換后的系數(shù)矩陣中確定獨(dú)立的“0”元素（即不同行不同列的“0”元素）。（動畫2）若某行（或某列）只有一個“0”元素，則對此“0”元素畫框。（動畫3）把位于此“0”元素的同行同列的其他“0”元素劃去。（動畫4）若遇到所有的行列中的“0”元素都不只一個，我們?nèi)我膺x取一個“0”元素加框，同時劃去其同行同列的其他“0”元素。（動畫5）如此反復(fù)進(jìn)行，直到所有的“0”元素被畫上框，或者是被劃去為止。（動畫6）畫上方框的“0”元素就是矩陣中獨(dú)立的“0”元素。(ppt13)（動畫1）如果獨(dú)立的“0”元素有??個，則令解矩陣中與獨(dú)立“0”元素對應(yīng)的位置上的變量取1，其他變量取0，此對應(yīng)的指派方案總費(fèi)用為0，從而一定是最優(yōu)解。（動畫2）如獨(dú)立的“0”元素少于??個，即至少有一行或者一列中沒有畫方框的“0”元素，采取如下的步驟進(jìn)行變換：（動畫3，4，5，6，7）看背板。(ppt14)（動畫1）第三步，繼續(xù)變換矩陣。找出未被直線覆蓋的元素中的最小元素，令打橫三角的行中的所有元素都減去這個最小元素，打正三角的列元素都加上這個最小元素。則原先選中的“0”元素不變，而未被直線覆蓋的元素中至少有一個元素已經(jīng)變?yōu)椤?”元素，且新矩陣的指派問題與原指派問題有相同的最優(yōu)解。（動畫2）反復(fù)上面的步驟，直到找出n個獨(dú)立的“0”元素為止。(ppt15)（動畫1）我們來看一個例子。求設(shè)要給5個人分配5項(xiàng)工作，每個人做每件事情的費(fèi)用如下面系數(shù)矩陣??所示，要使得費(fèi)用最小，求對應(yīng)的指派問題的最優(yōu)解。（動畫2）：我們將第一行減去7，第二行減去6，第三行減去7，第四行減去6，第五行減去4，就得到新的矩陣。再按照上面的步驟，（動畫3）先找到每一行的獨(dú)立0元素，畫上方框，把每一行每一列的重復(fù)的0元素打上叉。（動畫4）在沒有方框的行畫上橫三角。（動畫5）給這一行0叉所在的列打上正三角。（動畫6）再給這一列中有方框的0元素所在的行打上橫三角。（動畫7）最后劃去沒有打標(biāo)記的行，和打了標(biāo)記的列，如圖所示。(ppt16)（動畫1，2）則上面矩陣中的第一、二、四行和第一列被直線覆蓋，未被直線覆蓋的行列中的最小元素是2，故將第三、五行的元素減去2，第一列的元素加上2，這樣就使得最后一行出現(xiàn)新的0元素，同時不會出現(xiàn)負(fù)數(shù)的元素，得到新的矩陣。（動畫3）故得到相應(yīng)的解為??_12=1,??_23=1,??_31=1,??_44=1,??_55=1，其他的??_????=0。(ppt17)下面我們來介紹一般的指派問題。(ppt18)一般指派問題轉(zhuǎn)化為標(biāo)準(zhǔn)指派問題的方法。（動畫1）1.最大化指派問題：若目標(biāo)函數(shù)是求最大不是求最小，設(shè)??=??????{??_????}，令??′=(??_????′)=(?????_????)，則以??′=(??_????′)為系數(shù)矩陣的最小化指派問題就與原問題同解。（動畫2）2.人與事的數(shù)目不等：若人多于事或者是事多于人,則添上相應(yīng)數(shù)目的虛擬“事”或者是虛擬“人”，使得人與事的數(shù)目相等，不過人做虛擬的事或者是虛擬的人做事的費(fèi)用都為0。（動畫3）3.一個人可以做幾件事：若一個人可以做幾件事，則將該人化為相同的幾個人，這幾個人做事的費(fèi)用也完全相同。（動畫4）4.某事一定不能由某人來做：某事一定不能由某人來做，可取此人做該事時的費(fèi)用是一個足夠大的數(shù)。(ppt19)最后我們來看模型應(yīng)用。(ppt20)（動畫1）指派問題可以應(yīng)用于很多最優(yōu)安排問題上，如團(tuán)體賽的安排，比如接力賽，有人擅長跑直線，有人擅長跑彎道，還有人擅長沖刺，因此這就需