運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題-文庫(kù)吧資料
2025-05-22 22:11本頁(yè)面
【正文】 6 1 6 4 2 7 2 4 5 3 4 6 6 4 8 7 3 2 工作 人 I II III IV V VI 1 2 3 4 5 6 3 7 3 6 5 5 6 1 6 4 2 7 2 4 5 3 4 6 6 4 8 7 3 2 0 0 0 0 0 0 0 0 0 0 0 0 二、分配問(wèn)題與匈牙利法 目標(biāo)函數(shù)最大化的分配問(wèn)題 ? ?? ??mimjijij xa z1 1m a x ? ?? ??mimjijij/ xb z1 1min令 bij = M aij ? ?? ??mimjijij xa z1 1m a x標(biāo)準(zhǔn)化 ? ?? ???mimjijij xa z1 139。每項(xiàng)工作只交給一個(gè)人去完成。 最優(yōu)分配方案為：甲譯俄文，乙譯日文，丙譯英文，丁譯德文。 從矩陣未被直線覆蓋的數(shù)字中找出一個(gè)最小的數(shù) k；對(duì)矩陣的每行，當(dāng)該行有直線覆蓋時(shí)，令 ui=0，無(wú)直線覆蓋的，令 ui=k；對(duì)矩陣中有直線覆蓋的列，令 vj= k，對(duì)無(wú)直線覆蓋的列，令 vj=0。 二、分配問(wèn)題與匈牙利法 匈牙利法實(shí)例 (6) 順著閉回路的走向，對(duì)每個(gè)間隔的零元素打 ()，然后對(duì)所有打 ()的零元素或所在行或所在列畫(huà)一條直線，同樣得到最優(yōu)解。 二、分配問(wèn)題與匈牙利法 匈牙利法實(shí)例 (5) 1. 效率矩陣 每行都有一個(gè)打 () 的零元素 ，這些零元素都位于不同行不同列，令對(duì)應(yīng)打 () 零元素的 xij=1 就得到最優(yōu)解； 2. 矩陣中所有零元素或被劃去，或被打上() ，但打 () 的零元素 少于 m個(gè) ，這時(shí) 轉(zhuǎn)第四步 。用直線劃去其所在列；若該行沒(méi)有零元素或有兩個(gè)以上零元素 (已劃去的不計(jì)在內(nèi) )，則轉(zhuǎn)下一行，依次進(jìn)行到最后一行為止。 二、分配問(wèn)題與匈牙利法 匈牙利法實(shí)例 (2) 第二步： 找出矩陣每列的最小元素，再分別從各列中減去。 ? 定理 2 若矩陣 A的元素可分為“ 0” 和非“ 0” 兩部分，則覆蓋“ 0” 元素的最少直線數(shù)等于位于不同行不同列的“ 0” 元素的最大個(gè)數(shù)。這時(shí)完成總工作的時(shí)間為最少。 二、分配問(wèn)題與匈牙利法 匈牙利法的基本思想 ? 如果效率矩陣的所有元素 aij≥0, 而其中存在一組位于不同行不同列的零元素，則只要令對(duì)應(yīng)于這些零元素位置的 xij = 1，其余的 xij= 0，則所得到的可行解就是問(wèn)題的最優(yōu)解。 ? 庫(kù)恩 ()于 1955年提出了指派問(wèn)題的解法，他引用了匈牙利數(shù)學(xué)家康尼格 ()一個(gè)關(guān)于矩陣中零元素的定理： 系數(shù)矩陣中獨(dú)立 0元素的最多個(gè)數(shù)等于能覆蓋所有 0元素的最少直線數(shù) 。 建立整數(shù)規(guī)劃模型 分配問(wèn)題是 01整數(shù)規(guī)劃的特例，也是運(yùn)輸問(wèn)題的特例； n = m, aj = bj = 1。 人員 任務(wù) 甲 乙 丙 丁 譯成英文 譯成日文 譯成德文 譯成俄文 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 ???????????????9131541116141381441579102][ija二、分配問(wèn)題與匈牙利法 分配問(wèn)題實(shí)例 (3) ）；（項(xiàng)任務(wù)個(gè)人去完成第，不分配第項(xiàng)任務(wù)個(gè)人去完成第，分配第mjmijijix ij,1,1 0 1?? ???????????????????????????? ???? ?),1。現(xiàn)有甲、乙、丙、丁四人，他們將中文說(shuō)明書(shū)譯成不同語(yǔ)種的說(shuō)明書(shū)所需時(shí)間如下，問(wèn)應(yīng)指派何人去完成工作，使所需總時(shí)間最少 ? 人員 任務(wù) 甲 乙 丙 丁 譯成英
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1