系統(tǒng)工程---第四章整數(shù)規(guī)劃-資料下載頁
2024-10-18 18:55本頁面
【正文】 4 A1 A2 A3 A4 35 28 35 24 27 34 24 32 28 29 32 25 37 40 33 28 （ 4）最短工期指派問題 有 n項工作需要分派給 n個人去完成 ， 每個人做一項工作 ， 且每項工作只派一個人去完成 ， 設(shè)第 i個人完成第 j項工作的工時數(shù)為 cij， 若這 n個人同時開始工作 ， 問如何進行指派 ， 才能在最短的時間內(nèi)將這 n項工作完成 ？ 我們稱該問題為 最短工期的指派問題 。 ),2,1,(0 i1 njijx ij ?????? 否則 項工作個人去做第指派第設(shè)變量則該問題的數(shù)學模型為： ????njijijnixxcij 11m a xm in1,0,2,11,2,1111?????????ijniijnjijxnjxnix??（ P） 定理 1 若對效率矩陣 C中的每個元素分別減去一個正數(shù) ， 設(shè)得到的新矩陣為 ， 則以 B為效率矩陣的 （ P） 的最優(yōu)解和以 C為效率矩陣的 （ P） 的最優(yōu)解相同 。 定理 2 若矩陣 B中的所有零元素構(gòu)不成 n個位于不同行不同列的零元素 ， 此時令 ， 其中 則以 D為效率矩陣的問題 （ P） 有最優(yōu)解的充分必要條件是以B為效率矩陣的問題 （ P） 有最優(yōu)解 ， 且最優(yōu)解相同 。 ijck m in?B bij n n? ?( )D d ij n n? ?( )njibbbbDijijbjiijijij,2,1,0,m i n0,00,????????????若若最短工期指派問題的算法 Step1： 令 ； Step2： 若 B的每一行每一列都有零元素 ， 轉(zhuǎn) Step4， 否則轉(zhuǎn) Step3； Step3:令 這里 轉(zhuǎn) Step2。 njiccbbB ijjiijijnnij ,2,1,m i n,)( , ????? ?B bij n n? ?( )njibbbbbijijbjiijijijij,2,1,0,mi n0,00,????????????若若 Step4： 進行試指派，以尋求最優(yōu)解，具體按以下步驟進行 1. 從只有一個 0元素的行（或列）開始，給這個 0元素加圈，記作 ?，然后劃去 ?所在列和行上的其它 0元素，記作 0； 2. 重復進行 ，直到所有零元素都被圈出或劃掉為止； 3. 若仍有沒有劃掉的 0元素，且同行（列）的 0元素至少有兩個，則從剩有 0元素最少的行（或列）開始，比較這行（或列）各 0元素所在列（行）中 0元素的數(shù)目，選擇 0元素少的那列（行）的這個 0元素加圈，然后劃掉同行同列的其它 0元素，如此反復進行，直到所有 0元素都已圈出或劃掉為止； 4. 若 ?元素的數(shù)目 m等于矩陣的階數(shù) n， 則指派問題（ P） 的最優(yōu)解已得到，若 mn， 則轉(zhuǎn) Step3； 最短工期指派問題舉例 例 某公司準備將 5項工作分派給其下屬的 5家企業(yè) ， 已知各企業(yè)完成每項任務(wù)所需時間如下表 ， 若要求每家企業(yè)只能接受一項生產(chǎn)任務(wù) ， 而每項生產(chǎn)任務(wù)也只能由一家企業(yè)來完成 ， 那么該公司應(yīng)如何安排生產(chǎn)任務(wù) ， 使工期最短 ？ B1 B2 B3 B4 B5 A1 A2 A3 A4 A5 12 8 6 15 3 6 9 17 14 10 9 6 12 6 7 7 6 14 7 10 9 6 9 10 9 企業(yè) 任務(wù) 解： ????????????????9107103107614159141217666698979612????????????????67470743111261191433336564639????????????????34140410893861100003231306(cij) = cij3 bij3 ????????????????23030300782751000002120205bij0 ??????????????????0010001000000011000000010)(*nnijx最短工期為 max{6, 6, 6, 7, 7}=7個月 ， 同時可知完成所有任務(wù)所需總時間為 32個月 。 最優(yōu)解矩陣為： 如果以完成所有生產(chǎn)任務(wù)所需總時間最少為目標，利用前面的常規(guī)指派問題的算法可得到最優(yōu)解矩陣為： ??????????????????0000100100100000100000010)( nnijx所需的總時間為 30個月 ， 但其相應(yīng)工期為 max{6, 6, 9, 6, 3}=9個月 。
教學課件相關(guān)推薦
鄂ICP備17016276號-1