運(yùn)籌學(xué)資料4整數(shù)規(guī)劃(編輯修改稿)
2024-11-13 01:00 本頁面
【文章內(nèi)容簡(jiǎn)介】 的新矩陣 B，那么 B為系數(shù)矩陣求得的最優(yōu)解和用原來的系數(shù)矩陣 C求得的最優(yōu)解相同。 匈牙利算法： 系數(shù)矩陣中獨(dú)立 0元素的最多個(gè)數(shù)等于能覆蓋所有 0元素的最少直線數(shù)。 例 511 有一份中文說明書，需翻譯成英、日、德、俄四種文字，分別記作 E、 J、 G、 R，現(xiàn)有甲、乙、丙、丁四人，他們將中文說明書翻譯成英、日、德、俄四種文字所需時(shí)間如下，問應(yīng)該如何分配工作，使所需總時(shí)間最少？ 任務(wù)人員 E J G R 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9 匈牙利算法的步驟： 第一步：使分配問題的系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn) 0元素： ?從系數(shù)矩陣的每行元素減去該行的最小元素。 ?再從所得系數(shù)矩陣的每列元素減去該列的最小元素。 若某行已經(jīng)有 0元素，就不必再減了。 (cij)= 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 2 4 9 7 0 13 11 2 6 0 10 11 0 5 7 4 0 1 4 2 4 2 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0 第二步：進(jìn)行試分配，以尋找最優(yōu)解。 ?從只有一個(gè) 0元素的行（或列）開始，給這個(gè) 0元素加圈，記 ?， 然后劃去 ?所在的列（或行）的其他 0元素，記作 216。 ?給只有一個(gè) 0元素的列（或行）的 0元素 加圈，記 ?，然后劃去 ?所在的行（或列） 的其他 0元素，記作 216。 ?反復(fù)進(jìn)行上述兩步，直到所有的 0元素都被圈出和劃掉為止。 ?若還有沒有劃 圈的 0元素，且同 行（或列） 的 0元素 至少有二個(gè)，從剩有0元素最少的 行（或列）開始，比較這行各 0元素所在列中 0元素的數(shù)目，選擇 0元素少的那列的 0元素加圈，然后劃掉同行同列的其他 0元素，可反復(fù)進(jìn)行， 直到所有的 0元素都被圈出和劃掉為止。 ?若 ?元素的數(shù)目 m等于 矩陣階數(shù) n，那么這分配問題的最優(yōu)解已得到。若mn，則轉(zhuǎn)下一步。 0 13 7 0 6 ? 6 9 0 5 3 2 0 1 0 0 ?從只有一個(gè) 0元素的行（或列）開始，給這個(gè) 0元素加圈，記 ?。 0 13 7 0 6 ? 6 9 ? 5 3 2 0 1 0 0 ?從只有一個(gè) 0元素的行（或列）開始，給這個(gè) 0元素加圈，記 ?， 216。 13 7 0 6 ? 6 9 ? 5 3 2 216。 1 0 0 然后劃去 ?所在的列的其他 0元素，記作 216。 216。 13 7 0 6 ? 6 9 ? 5 3 2 216。 1 ? 0 ?給只有一個(gè) 0元素的列的 0元素 加圈，記 ?。 216。 13 7 0 6 ? 6 9 ? 5 3 2 216。 1 ? 216。 然后劃去 ?所在的 行 的其他 0元素，記作 216。 216。 13 7 ? 6 ? 6 9 ? 5 3 2 216。 1 ? 216。 ?給最后一個(gè) 0元素 加圈，記 ?。 0 0 0
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1