整數(shù)規(guī)劃的難度遠大于一般線性規(guī)劃-文庫吧
2025-01-19 19:32 本頁面
【正文】 ????????????且為整數(shù)問題 0,3 7 21342II46)(max211212121xxxxxxxxxxf5 表 分枝問題的松弛解 問題 I 問題 IIx 1 2 3x 2 9 / 4 1f ( x ) 21 22問題 II的解即原整數(shù)問題的最優(yōu)解 可能存在兩個分枝都是非整數(shù)解的情況，則需要兩邊同時繼續(xù)分枝，直到有整數(shù)解出現(xiàn)，就可以進行定界過程 當有很多變量有整數(shù)約束時，分枝即廣又深，在最壞情況下相當于組合所有可能的整數(shù)解 一般整數(shù)規(guī)劃問題屬于一類未解決的難題， NPplete，只有少數(shù)特殊問題有好的算法，如 任務(wù)分配問題 、 匹配問題 6 任務(wù)分配問題 例 有四個熟練工人，他們都是多面手，有四項任務(wù)要他們完成。若規(guī)定每人必須完成且只完成一項任務(wù)，而每人完成每項任務(wù)的工時耗費如表 ，問如何分配任務(wù)使完成四項任務(wù)的總工時耗費最少？ ???????????????? ???? ?1,0,2,1 1,2,1 1)(min111 1ijmiijmjijmimjijijxmjxmixxaxf??任務(wù) 工時 A B C D 人員人員甲 10 9 7 8 1乙 5 8 7 7 1丙 5 4 6 5 1丁 2 3 4 5 1任務(wù) 1 1 1 17 任務(wù)分配問題的數(shù)學模型 模型中： xij 為第 i 個工人分配去做第 j 項任務(wù)； aij 為第 i 個工人為完成第 j 項任務(wù)時的工時消耗； {aij}m?m 稱為 效率矩陣 ???????mjijijix ij,2,1,01?項任務(wù)個工人未分配去做第當?shù)陧椚蝿?wù)個工人分配去做第當?shù)谶\輸問題是任務(wù)分配問題的松弛問題 任務(wù)分配問題不但是整數(shù)規(guī)劃，而且是 0?1規(guī)劃 任務(wù)分配問題有 2m個約束條件，但有且只有 m個非零解，是自然 高度退化 的 任務(wù)分配是 兩部圖 的 匹配問題 ，有著名的 匈牙利算法 下面介紹一種適合手算的算法 (出自清華教科書 ) 8 清華算法 定理 1 如果從效率矩陣 {aij}m?m中每行元素分別減去一個常數(shù) ui，從每列元素分別減去一個常數(shù) vj ， 所得新的效率矩陣 {bij}m?m的任務(wù)分配問題的最優(yōu)解等價于原問題的最優(yōu)解。 證明：略 定理 2 若方陣中一部分元素為零，一部分元素非零，則覆蓋方
教學課件相關(guān)推薦
鄂ICP備17016276號-1