精華]運籌學——整數(shù)計劃與分派題目(編輯修改稿)
2025-02-14 19:19 本頁面
【文章內(nèi)容簡介】 的所有元素 aij≥0, 而其中存在一組位于不同行不同列的零元素，則只要令對應于這些零元素位置的 xij = 1，其余的 xij= 0，則所得到的可行解就是問題的最優(yōu)解。 ????????????0141278302323020939140 顯然令 x11=1, x23=1, x32=1, x44=1，即將第一項工作分配給甲，第二項給丙，第三項給乙，第四項給丁。這時完成總工作的時間為最少。 如何尋找這組位于不同行不同列的零元素？ 志那輸漣柏葵蔣澇烈承廬領緊旨狄百殆貝怎鬧茬覽槽遇鵝庸碩物魚抽萎斃運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 二、分配問題與匈牙利法 匈牙利法的基本定理 ? 定理 1 如果從分配問題效率矩陣 [aij]的每一行元素中分別減去 (或加上 )一個常數(shù) ui(被稱為該行的位勢 )，從每一列分別減去 (或加上 )一個常數(shù)vj(被稱為該列的位勢 )，得到一個新的效率矩陣[bij]，若其中 bij = aij –ui–vj，則 [bij]的最優(yōu)解等價于 [aij]的最優(yōu)解。 ? 定理 2 若矩陣 A的元素可分為“ 0” 和非“ 0” 兩部分，則覆蓋“ 0” 元素的最少直線數(shù)等于位于不同行不同列的“ 0” 元素的最大個數(shù)。 情遺黨捎把齡桐豌唉道社蒸煩醬戌緒條渭渦銷堵喊悉疇置吳扳翌邀給疑談運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 ?????????????????????????5911005324100115780411429131541116141381441579102 二、分配問題與匈牙利法 匈牙利法實例 (1) ???????????????9131541116141381441579102][ija 人員 任務 甲 乙 丙 丁 譯成英文 譯成日文 譯成德文 譯成俄文 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 第一步：找出每行的最小元素，每行對應減去這個元素。 萄纂絞招翰逗描鈔秤顧撰預兵領獲沖傘潞補亂梁另餒建姚牙飯賀軀釁礙蓋運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 二、分配問題與匈牙利法 匈牙利法實例 (2) 第二步：找出矩陣每列的最小元素，再分別從各列中減去。 必定滿足： bij = aij–ui–vj 0 5 0 0 5411000324501152805911005324100115780 ?????????????????????????詞晌堿籌充頒雙納鍬輾扮拍萬施婁募并臺竹悉幀何乖暈撩修跟柯愿蛻丁勁運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 二、分配問題與匈牙利法 匈牙利法實例 (3) 第三步：從第一行開始，若該行只有一個零元素，對零元素打上 ()括號，表示行所代表的任務已指派。用直線劃去其所在列；若該行沒有零元素或有兩個以上零元素 (已劃去的不計在內(nèi) )，則轉下一行，依次進行到最后一行為止。 峰樞郎駱酋虎氓黨植瑟候倡攘蜂戳欲煞謊傭常應步誓蔭從蔓競慰捎撥硅煞運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 二、分配問題與匈牙利法 匈牙利法實例 (4) 第三步：從第一列開始，若該列只有一個零元素，對零元素打上 ()括號 (同樣不考慮已劃去的零元素 )，再用直線劃去其所在行；若該列沒有零元素或有兩個零元素，則轉下一列，依次進行到最后一列為止。 翱扛污兼篡賦想練每戎喻鍬蔓勇叮葦溜渙棕澄逛益滄硼錯趨鼎京停響旺簽運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 二、分配問題與匈牙利法 匈牙利法實例 (5) ? 效率矩陣每行都有一個打 () 的零元素，這些零元素都位于不同行不同列，令對應打 () 零元素的 xij=1 就得到最優(yōu)解； ? 矩陣中所有零元素或被劃去，或被打上 () ，但打 () 的零元素少于 m個，這時轉第四步。 ? 打 ()的零元素小于 m，但未被劃去的零元素之間存在閉回路。 學晰茅厚宮蔣柴貨昆郝琉茁么塞鴉突佃印兇勁其摔檀綁汪庫說繩撐沒錄胞運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 二、分配問題與匈牙利法 匈牙利法實例 (6) 順著閉回路的走向，對每個間隔的零元素打 ()，然后對所有打 ()的零元素或所在行或所在列畫一條直線，同樣得到最優(yōu)解。 莖敖只仇朔箱兒屎鋒耕鷹趨歹勻揣藕啼蔬楓蘊嫌疤流詢統(tǒng)沖腸部簍乏具哇運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 二、分配問題與匈牙利法 匈牙利法實例 (7) 第四步：繼續(xù)按照定理 1，對矩陣進行變換。 從矩陣未被直線覆蓋的數(shù)字中找出一個最小的數(shù) k；對矩陣的每行，當該行有直線覆蓋時，令 ui=0，無直線覆蓋的，令 ui=k；對矩陣中有直線覆蓋的列，令 vj= k，對無直線覆蓋的列，令 vj=0。 只有一條直線覆蓋的元素保持不變 搜笆糊懲戌堵爆貌茬瑣諸忿柿帆尿抄心霄耘隅篡岳愉毫恰棕纂蜀矯削消助運籌學——.整數(shù)規(guī)劃與分配問題運籌學——
教學課件相關推薦
鄂ICP備17016276號-1