[管理學(xué)]整數(shù)規(guī)劃與分配問題(編輯修改稿)
2024-11-15 01:40 本頁面
【文章內(nèi)容簡介】 分配問題的最優(yōu)解有這樣的性質(zhì)，若從系數(shù)矩陣 C的一行（列）各元素中分別減去該行（列）的最小元素得到的新矩陣 B，那么 B為系數(shù)矩陣求得的最優(yōu)解和用原來的系數(shù)矩陣 C求得的最優(yōu)解相同。 匈牙利算法： 若系數(shù)矩陣中的元素可分為 ” 0”與非 “ 0”兩部分，則覆蓋 “ 0”元素的最少直線數(shù)等于位于不同行不同列的 “ 0”元素的最大個(gè)數(shù)。 甲 乙 丙 丁 譯成英文 譯成日文 譯成德文 譯成俄文 2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9 匈牙利算法的步驟： 第一步：使分配問題的系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn) 0元素： ?從系數(shù)矩陣的每行元素減去該行的最小元素。 ?再從所得系數(shù)矩陣的每列元素減去該列的最小元素。 若某行已經(jīng)有 0元素，就不必再減了。 (cij)= 2 4 11 4 0 8 7 5 11 0 10 4 2 3 5 0 0 11 9 5 5 2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9 0 8 2 5 11 0 5 4 2 3 0 0 0 11 4 5 第二步：進(jìn)行試分配，以尋找最優(yōu)解。 ?從只有一個(gè) 0元素的行（或列）開始，給這個(gè) 0元素加圈，記 ?，然后劃去 ?所在的列（或行）的其他 0元素，記作 216。 ?給只有一個(gè) 0元素的列（或行）的 0元素加圈，記 ?，然后劃去 ?所在的 行（或列）的其他 0元素，記作 216。 ?反復(fù)進(jìn)行上述兩步，直到所有的 0元素都被圈出和劃掉為止。 ?若還有沒有劃 圈的 0元素，且同 行（或列） 的 0元素 至少有二個(gè)，從剩有0元素最少的 行（或列）開始，比較這行各 0元素
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1