分配問題與匈牙利法.ppt

《分配問題與匈牙利法.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、分配問題與匈牙利法指派問題的數(shù)學(xué)模型的標準形式：設(shè)n個人被分配去做n件工作，規(guī)定每個人只做一件工作，每件工作只有一個人去做。已知第i個人去做第j件工作的效率（時間或費用）為Cij(i=1.2…n;j=1.2…n)并假設(shè)Cij≥0。問應(yīng)如何分配才能使總效率（時間或費用）最高？設(shè)決策變量分配問題與匈牙利法指派問題的數(shù)學(xué)模型為：分配問題與匈牙利法克尼格定理:如果從分配問題效率矩陣[aij]的每一行元素中分別減去(或加上)一個常數(shù)ui，從每一列中分別減去(或加上)一個常數(shù)vj，得到一個新的效率矩陣[bij]，則以[bij]為效率矩陣的分配問題與以[aij]為效率矩陣的分配問題具有相同的最優(yōu)解。分配問

2、題與匈牙利法指派問題的求解步驟：1)變換指派問題的系數(shù)矩陣(cij)為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即從(cij)的每行元素都減去該行的最小元素；再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。2)進行試指派，以尋求最優(yōu)解。在(bij)中找盡可能多的獨立0元素，若能找出n個獨立0元素，就以這n個獨立0元素對應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。分配問題與匈牙利法找獨立0元素，常用的步驟為：從只有一個0元素的行開始，給該行中的0元素加圈，記作◎。然后劃去◎所在列的其它0元素，記作?；這表示該列所代表的任務(wù)已指派完，不必再考慮別人了。依次進行到最后一行

3、。從只有一個0元素的列開始（畫?的不計在內(nèi)），給該列中的0元素加圈，記作◎；然后劃去◎所在行的0元素，記作?，表示此人已有任務(wù)，不再為其指派其他任務(wù)了。依次進行到最后一列。若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少這個0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素?？煞磸?fù)進行，直到所有0元素都已圈出和劃掉為止。分配問題與匈牙利法若◎元素的數(shù)目m等于矩陣的階數(shù)n（即：m＝n），那么這指派問題的最優(yōu)解已得到。若m

4、√”的行中所有含?元素的列打“√”；再對打有“√”的列中含◎元素的行打“√”；重復(fù)①、②直到得不出新的打√號的行、列為止；對沒有打√號的行畫橫線，有打√號的列畫縱線，這就得到覆蓋所有0元素的最少直線數(shù)l。注：l應(yīng)等于m，若不相等，說明試指派過程有誤，回到第2步，另行試指派；若l＝m

5、與匈牙利法例4.6有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D。現(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下表所示，問如何分派任務(wù)，可使總時間最少？任務(wù)人員ABCD甲67112乙4598丙31104丁5982分配問題與匈牙利法解：1）變換系數(shù)矩陣，增加0元素。－52）試指派（找獨立0元素）◎◎◎??找到3個獨立零元素但m=3

6、個最小元素；直線交點處的元素加上這個最小值。得到新的矩陣，重復(fù)2）步進行試指派分配問題與匈牙利法000000試指派◎◎◎??◎得到4個獨立零元素，所以最優(yōu)解矩陣為：即完成4個任務(wù)的總時間最少為：2＋4＋1+8=15分配問題與匈牙利法例4.7已知四人分別完成四項工作所需時間如下表，求最優(yōu)分配方案。任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119分配問題與匈牙利法解：1）變換系數(shù)矩陣，增加0元素?！?◎??◎◎2）試指派（找獨立0元素）獨立0元素的個數(shù)為4,指派問題的最優(yōu)指派方案即為甲負責(zé)D工作，乙負責(zé)B工作，丙負責(zé)A工作，丁負責(zé)C工作。這樣安排能使總的工作時間最少，為

7、4＋4＋9＋11＝28。分配問題與匈牙利法例4.8已知五人分別完成五項工作耗費如下表，求最優(yōu)分配方案。任務(wù)人員ABCDE甲759811乙9127119丙85468丁73696戊467511分配問題與匈牙利法-1-2解：1）變換系數(shù)矩陣，增加0元素。分配問題與匈牙利法◎?◎◎◎??2）試指派（找獨立0元素）獨立0元素的個數(shù)l＝4<5，故畫直線調(diào)整矩陣。分配問題與匈牙利法◎?◎◎◎??√√√選擇直線外的最小元素為