分配問題指派問題與匈牙利法

第5講分配問題（指派問題）與匈牙利法分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第1頁!分配問題的提出分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第2頁!分配問題的提出若干項工作或任務需要若干個人去完成。由于每人的知識、能力、經(jīng)驗的不同，故各人完成不同任務所需要的時間不同（或其他資源）。問：應指派哪個人完成何項工作，可使完成所有工作所消耗的總資源最少？分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第3頁!整體解題思路總結(jié)例題：工作者1工作者2工作者3工作者4工作者5工作14871512工作279171410工作3691287工作46714610工作56912106單位：小時分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第4頁!標準形式的分配問題分派方案滿足下述兩個條件：任一個工人都不能去做兩件或兩件以上的工作任一件工作都不能同時接受兩個及以上的工人去做設某公司準備派n個工人x1，x2，…，xn，去作n件工作y1，y2，…，yn。已知工人xi完成工作yj所需時間為cij(i,j=1,2,…,n)?，F(xiàn)問：如何確定一個分派工人去工作的方案，使得工人們完成工作的總時間為最少。分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第5頁!數(shù)學模型n個人n件事cij：第i人做第j事的費用xij＝1若指派第i人做第j事0若指派第i人不做第j事總費用：i，j＝1,

...,

nj＝1,...,ni＝1,...,n每件事必有且只有一個人去做每個人必做且只做一件事時間、原料、金錢等資源分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第6頁!匈牙利法1955年由美國數(shù)學家W.W.kuhn(庫恩)提出，利用了匈牙利數(shù)學家D.Konig(康尼格)證明的2個定理。系數(shù)矩陣(效率矩陣)解矩陣(決策變量矩陣)n個人n件事分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第7頁!014丙085乙210甲CBA時工作間人員004丙075乙200甲CBA時工作間人員458丙4129乙987甲CBA時工作

間

人員定理：若將分配問題系數(shù)矩陣的每一行及每一列分別減去各行及各列的最小元素，則新分配問題與原分配問題有相同的最優(yōu)解，只有最優(yōu)值差一常數(shù)。相關定理使每行每列都出現(xiàn)零元素分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第8頁!步驟2：進行試分配，判斷是否存在n個獨立零元素嘗試對所有零元素做標記，確定獨立零元素。（1）逐行檢驗對只有一個未標記的零元素的行，用記號O將該零元素圈起，然后將被圈起的零元素所在列的其他未標記的零元素用記號/劃去。重復行檢驗，直到每一行都沒有未被標記的零元素或至少有兩個未被標記的零元素為止。表示此人只能做該事（此事只能由該人做）表示此事已不能由其他人來做（此人已不能做其他事）分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第9頁!步驟2：進行試分配，判斷是否存在n個獨立零元素嘗試對所有零元素做標記，確定獨立零元素。（2）逐列檢驗與行檢驗類似：對只有一個未標記的零元素的列，用記號O將該零元素圈起，然后將被圈起的零元素所在行的其他未標記的零元素用記號/劃去。重復列檢驗，直到?jīng)]有未被標記的零元素或至少有兩個未被標記的零元素為止。分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第10頁!可能出現(xiàn)三種情況1.每一行均有圈0出現(xiàn)，圈0的個數(shù)恰好等于n2.存在未標記過的零元素，但它們所在的行和列中，未被標記過的零元素的個數(shù)均至少有兩個。3.不存在未被標記過的零元素，但圈0的個數(shù)<n可進行分配：令圈0位置的決策變量取值為1，其他為0（3）判斷獨立零元素的個數(shù)分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第11頁!分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第12頁!定理：系數(shù)矩陣C中獨立零元素的最多個數(shù)等于能覆蓋所有零元素的最少線數(shù)。由匈牙利數(shù)學家D.Konig(康尼格)所證明例：分別求下列矩陣中的獨立零元素的最多個數(shù)。44獨立零元素的個數(shù)最多：分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第13頁!⑥找未被直線覆蓋的最小數(shù)字k；⑦對矩陣的每行：當該行有直線覆蓋時，令ui=0；當該行無直線覆蓋時，令ui=k。ui01100⑧對矩陣的每列：當該列有直線覆蓋時，令vj=-k；當該列無直線覆蓋時，令vj=0。vj-10000分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第14頁!⑩再次尋找獨立零元素逐列檢驗原題：分配方案A=7+9+6+6+6=34分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第15頁!對不含圈0的行打；在打的行中，對所有零元素所在列打；在所有打的列中，對圈0所在行打；重復2,3步，直到不能打為止。對未打的每一行畫一橫線，對已打的每一列畫一縱線，即得到覆蓋當前0元素的最少直線集。圈0個數(shù)4<n=5分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第16頁!⑨從原矩陣的每個元素aij中分別減去ui和vj，得到新元素ui00202vj-20000分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第17頁!⑩再次尋找獨立零元素分配方案B分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第18頁!整體解題思路總結(jié)例題：人1人2人3人4人5工作14871512工作279171410工作3691287工作46714610工作56912106單位：小時分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第19頁!步驟1：變換系數(shù)矩陣，使其每行每列都出現(xiàn)0元素把各行元素分別減去本行元素的最小值，然后在此基礎上再把每列元素減去本列中的最小值。此時每行及每列中肯定都有0元素分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第20頁!可能出現(xiàn)三種情況3.不存在未被標記過的零元素，但圈0的個數(shù)<n（3）判斷獨立零元素的個數(shù)圈0個數(shù)4<n=5作最少直線覆蓋當前所有零元素，便于下步增加獨立零元素的個數(shù)。分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第21頁!⑥找未被直線覆蓋的最小數(shù)字k；⑦對矩陣的每行：當該行有直線覆蓋時，令ui=0；當該行無直線覆蓋時，令ui=k。ui01100⑧對矩陣的每列：當該列有直線覆蓋時，令vj=-k；當該列無直線覆蓋時，令vj=0。vj-10000分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第22頁!⑩再次尋找獨立零元素逐列檢驗原題：分配方案A=7+9+6+6+6=34分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第23頁!分配問題的提出設某公司準備派n個工人x1，x2，…，xn，去作n件工作y1，y2，…，yn。已知工人xi完成工作yj所需時間為cij(i,j=1,2,…,n)。現(xiàn)問：如何確定一個分派工人去工作的方案，使得工人們完成工作的總時間為最少。還比如：分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第24頁!標準形式的分配問題分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第25頁!標準形式的分配問題n個人n件事每件事必有且只有一個人去做每個人必做且只做一件事分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第26頁!數(shù)學模型j＝1,...,ni＝1,...,ns.t.線性規(guī)劃問題運輸問題0-1型整數(shù)規(guī)劃問題分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第27頁!定義：在系數(shù)矩陣C中，處在不同行不同列的一組零元素，稱為獨立零元素組，其中每個元素稱為獨立零元素。最優(yōu)解分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第28頁!步驟1：變換系數(shù)矩陣，使其每行每列都出現(xiàn)0元素把各行元素分別減去本行元素的最小值，然后在此基礎上再把每列元素減去本列中的最小值。此時每行及每列中肯定都有0元素分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第29頁!圈0即獨立零元素步驟2：進行試分配，判斷是否存在n個獨立零元素嘗試對所有零元素做標記，確定獨立零元素。（2）逐行檢驗分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第30頁!圈0即獨立零元素步驟2：進行試分配，判斷是否存在n個獨立零元素嘗試對所有零元素做標記，確定獨立零元素。（2）逐列檢驗分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第31頁!可能出現(xiàn)三種情況2.存在未標記過的零元素，但它們所在的行和列中，未被標記過的零元素的個數(shù)均至少有兩個。3.不存在未被標記過的零元素，但圈0的個數(shù)<n從某行（列）的兩個未被標記過的零元素中任選一個加上圈，然后給同列、同行的其他未被標記的零元素都加/，然后再進行行、列檢驗，可能出現(xiàn)情況1或3。（3）判斷獨立零元素的個數(shù)圈0個數(shù)等于n=5多重最優(yōu)解分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第32頁!可能出現(xiàn)三種情況3.不存在未被標記過的零元素，但圈0的個數(shù)<n（3）判斷獨立零元素的個數(shù)圈0個數(shù)4<n=5作最少直線覆蓋當前所有零元素，便于下步增加獨立零元素的個數(shù)。分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第33頁!對不含圈0的行打；在打的行中，對所有零元素所在列打；在所有打的列中，對圈0所在行打；重復2,3步，直到不能打為止。對未打的每一行畫一橫線，對已打的每一列畫一縱線，即得到覆蓋當前0元素的最少直線集。分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第34頁!ui01100vj-10000⑨從原矩陣的每個元素aij中分別減去ui和vj，得到新元素分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第35頁!⑩再次尋找獨立零元素逐列檢驗分配方案B=7+9+7+6+6=35分配問題指派問題與匈牙利法共44頁，您現(xiàn)在瀏覽的是第36頁!⑥找未被直線覆蓋的最小數(shù)字k；⑦對矩陣的每行：當該行有直線覆蓋時，令ui=0；當該行無直線覆蓋時，令ui=k。ui00202⑧對矩陣的每列：當該列有直線覆蓋時，令vj=-k；當該列無直線覆蓋時，令vj=0。vj-20000分配問題指派問題與匈牙利法共4