線性規(guī)劃和匈牙利法

1、 二、 生產(chǎn)任務(wù)分配的匈牙利法在實(shí)際的生產(chǎn)管理工作中，常會遇到這樣的問題，就是如何根據(jù)生產(chǎn)作業(yè)汁劃將不同任務(wù)在不同的工人(或班組)之間分配，使完成任務(wù)總的消耗時間或費(fèi)用最小。解決這類問題的簡便而有效的方法是匈牙利法，它是由匈牙利數(shù)學(xué)家D. Konig所提出。例 有4項(xiàng)任務(wù)A、B、C、D，分別由甲、乙、丙、丁4個人去完成，規(guī)定每人承擔(dān)其中一項(xiàng)任務(wù)，不同的人完成同一任務(wù)所花時間(h)不同，見表3-3，求如何分配，使完成這4項(xiàng)任務(wù)的總時間最小。匈牙利法求解此問題的步驟是：1） 按表3-3列出矩陣 2) 將矩陣作行、列約簡：首先進(jìn)行行約簡。在矩陣的每一行中選取最小元素，然后將該行的各元素都減去此數(shù)，得

2、到如下新矩陣 行約簡是比較一名工人擔(dān)任不同任務(wù)時所花的時間，各行中減去最小值后的時間表示該工人擔(dān)任其它任務(wù)時，所多花費(fèi)的時間，每行中的“0”表示該工人承擔(dān)這項(xiàng)任務(wù)最有利。 然后將經(jīng)過行約筒后的矩陣中沒有“0”的列再進(jìn)行約簡，即從該列中選出最小元素，并將其它元素減去此數(shù)，得到新矩陣 列約簡是比較一項(xiàng)任務(wù)有不同工人承擔(dān)所托時間，各列中減去最小值后的時間表示任務(wù)由其他工人擔(dān)任時，所多花費(fèi)的時間，每列中的“0”表示這項(xiàng)任務(wù)由該工人承擔(dān)最有利。 3) 檢驗(yàn)是否已得最優(yōu)分配方案；作零的覆蓋線，即對有“0”的行和列，劃上一條覆蓋線，能覆蓋所有零元素的最少覆蓋線數(shù)稱為維數(shù)，當(dāng)覆蓋線的維數(shù)等于矩陣階數(shù)時，可知已

3、得最優(yōu)分配方案，若維數(shù)小于階數(shù)，再作調(diào)整。本例可用三條覆蓋線覆蓋住所有零元素，維數(shù)是3，矩陣的階數(shù)是4，維數(shù)不等于階數(shù)，因此矩陣還必須調(diào)整。 4) 矩陣的調(diào)整。在上述矩陣中有三種元素，一種是無線覆蓋元素，另一種是單線覆蓋元素，還有一種是雙線覆蓋元素。在無線覆荒元素中找出最小值，本例為“1”，將無線覆蓋得元素都減去“1”，而雙線覆蓋的元素加上“1”，單線覆蓋的元素不變。這樣得到新矩陣 5) 再檢驗(yàn)作覆蓋線，方法與步驟3相同。現(xiàn)在的最少覆蓋線數(shù)為4，與矩陣階數(shù)相等，可知已能進(jìn)行最優(yōu)分配。 6) 確定最優(yōu)分配方案。進(jìn)行具體分配時，可以對只有一個零元素的列(行)先分配(記號)，分配后，劃去與該零元素同行(列)的其他零元素(記×號)這樣依改做完各列(行)，得到分配結(jié)果。如果矩陣能通過直接觀察找到位于不同行不同列的零元素，那么就可以直接確定分配方