【正文】 61010043310√ √ √ ???????????????0746350010052200最優(yōu)解矩陣： ??????????????1000001001000001min f =20 （ 3）目標(biāo)函數(shù)求最大值的指派問(wèn)題 匈牙利算法適用于： 所有 cij≥0 對(duì)于目標(biāo)函數(shù)為 max型的指派問(wèn)題，將效率矩陣中所有 cij反號(hào)，則等效于求 min型問(wèn)題；在利用定理 1進(jìn)行變換，使所有 bij ≥0， 則可采用匈牙利算法求解。 最優(yōu)解矩陣為： 如果以完成所有生產(chǎn)任務(wù)所需總時(shí)間最少為目標(biāo)，利用前面的常規(guī)指派問(wèn)題的算法可得到最優(yōu)解矩陣為： ??????????????????0000100100100000100000010)( nnijx所需的總時(shí)間為 30個(gè)月 ， 但其相應(yīng)工期為 max{6, 6, 9, 6, 3}=9個(gè)月 。 若 l n,說(shuō)明必須再變換當(dāng)前的效率矩陣，才能找到 n個(gè)獨(dú)立的0元素。 匈牙利算法的 基本思路 ： ? 根據(jù)定理 1變換效率矩陣，使矩陣中有足夠多的零。 修改 A的最優(yōu)目標(biāo)函數(shù)值的上下界 。一、 整數(shù)規(guī)劃簡(jiǎn)介 ?整數(shù)規(guī)劃 是數(shù)學(xué)規(guī)劃的一個(gè)重要分支，它研究的是一類要求其部分或全部變量取整數(shù)的最優(yōu)化問(wèn)題。 在各分枝問(wèn)題的最優(yōu)解中，找出最優(yōu)目標(biāo)函數(shù)值最大者作為新的上界。若矩陣中存在 n個(gè)不同行不同列的零，就找到了最優(yōu)解。為此轉(zhuǎn)入第四步。 。 再回到第二步。 匈牙利算法的 理論基礎(chǔ) 定理 1如果從效率矩陣 (cij)的某一行 (列 )各元素中分別減去一個(gè)常數(shù) k， 得到一個(gè)新的矩陣 (bij)， 那么 ， 以 (bij)為效率矩陣的指派問(wèn)題的最優(yōu)解和原問(wèn)題的最優(yōu)解相同 。 Step6 比較與剪枝。它既能解決純整數(shù)規(guī)劃問(wèn)題，又能解決混合整數(shù)規(guī)劃問(wèn)題。構(gòu)造兩個(gè)約束條件： xj≤ [bj] 和 xj ≥ [bj]+1 將這兩個(gè)約束條件分別加入問(wèn)題 B， 得到 B的兩個(gè)分枝 B1和 B2。如： ? 指派 問(wèn)題，有著名的匈牙利算法 指派問(wèn)題的特點(diǎn)： ???????????????1000000101000010)( ijx指派問(wèn)題實(shí)例 例 1 有四個(gè)熟練工人，他們都是多面手，有四項(xiàng)任務(wù)要他們完成。 ⑸ 對(duì)沒有打 ?號(hào)的行畫橫線 ， 所有打 ?號(hào)的列畫豎線 ， 所得直線就是能覆蓋所 有 0元素的最少直線集合 。 ijck m in?B bij n n? ?( )D d ij n n? ?( )njibbbbDijijbjiijijij,2,1,0,m i n0,00,????????????若若最短工期指派問(wèn)題的算法 Step1： 令 ； Step2： 若 B的每一行每一列都有零元素 ， 轉(zhuǎn) Step4， 否則轉(zhuǎn) Step3； Step3:令 這里 轉(zhuǎn) Step2。 各人完成不同工作的產(chǎn)值如下表所示 ， 問(wèn)如何分配任務(wù)才能使總產(chǎn)值最大 ？ A B C D 甲 乙 丙 丁 1 5 4 3 8 7 5 1 4 6 6 4 1 3 3 2 人員 任務(wù) 解：先把最大化問(wèn)題化為最小化問(wèn)題，再按匈牙利法求解。 ⑶ 反復(fù)進(jìn)行 ⑴、⑵ 直到所有的 0元素都被圈出和劃掉為止 。 ffff ?*各分枝問(wèn)題的解可能出現(xiàn)的情況 序號(hào) 問(wèn)題 B 1 問(wèn)題 B 2 說(shuō) 明 1 無(wú)可行解 無(wú)可行解 整數(shù)規(guī)劃無(wú)可行解 2 無(wú)可行解 整數(shù)解 此整數(shù)解即最優(yōu)解 3 無(wú)可行解 非整數(shù)解 對(duì)問(wèn)題 B 2 繼續(xù)分枝 4 整數(shù)解 整數(shù)解 較優(yōu)的一個(gè)為最優(yōu)解 5 整數(shù)解，目標(biāo)函數(shù)優(yōu)于問(wèn)題 B 2 非整數(shù)解 問(wèn)題 B 1 的解即最優(yōu)解 6 整數(shù)解 非整數(shù)解，目標(biāo)函數(shù)優(yōu)于問(wèn)題 B 1 問(wèn)題 B 1 停止分枝 ( 剪枝 ) ，其整數(shù)解為界，對(duì)問(wèn)題 B 2 繼續(xù)分枝 ? 情況 2, 4, 5 找到最優(yōu)解 ? 情況 3 在縮減的域上繼續(xù)分枝定界法 ? 情況 6 問(wèn)題 1 的整數(shù)解作為界被保留，用于以后與問(wèn)題 2 的后續(xù)分枝所得到的解進(jìn)行比較，結(jié)論如情況 4或 5 例 1 ????????????且為整數(shù) 0,7 2134246m a x21212121xxxxxxxxf解：松弛問(wèn)題 B的最優(yōu)解為 x1= , x2=2 , f =23 ??????????????? 0,2 7 2134246m a x2112121121xxxxxxxBxxf問(wèn)題??????????????? 0,3 7 2134246m a x2112121221xxxxxxxBxxf問(wèn)題分枝定界法舉例 問(wèn)題 A ???????????? 0,7 2