系統(tǒng)工程---第四章整數(shù)規(guī)劃(編輯修改稿)
2024-11-14 18:55 本頁面
【文章內容簡介】 1 1 0 0 2 1 1 3 5 2 4 2 6 2 5 √ √ √ √ √ 0 5 2 3 8 （ x1， x2， x3） 約束條件 最優(yōu)解為 X*= （ 1， 0， 1） 隱枚舉法 所謂 隱枚舉法 就是只檢查變量取值組合的一部分就能求得問題最優(yōu)解的方法。其基本思路是：先找到一組可行解，增加一個過濾條件，然后改進過濾值，直至不能改進為止。 m ax, ,f x x xx x xx x xx xx xx x x? ? ?? ? ?? ? ?? ?? ???????????? ? ?? ?? ??? ?? ?? ? ?? ? ?? ? ?? ?? ?? ? ?或① ② ③ ④ 例 3 求解 01規(guī)劃 解 用觀察法找一個可行解 （ x1， x2， x3） = （ 1， 0， 0）， 其目標函數(shù)值為 3。 于是增加過濾條件 ： 3x12x2+5x3≥3 ◎ 隱枚舉法表 ◎ ① ② ③ ④ 滿足約 束條件 ？ f值 （ 0， 0， 0） （ 0， 0， 1） （ 0， 1， 0） （ 0， 1， 1） （ 1， 0， 0） （ 1， 0， 1） （ 1， 1， 0） （ 1， 1， 1） 0 5 1 1 0 1 2 3 3 8 0 2 1 1 1 6 √ √ 5 8 （ x1， x2， x3） 約束條件 最優(yōu)解為 X*= （ 1， 0， 1） （ 1） 指派問題的數(shù)學模型 : 引入 01變量 xij (i,j=1,2,…, n) ?????????????????? ???? ?1,0,2,1 1,2,1 1m in111 1ijniijnjijninjijijxnjxnixxcf??模型中： cij 為第 i 個工人完成第 j 項任務的時 間 (成本、費用 )； {cij}n?n 稱為 效率矩陣 ????項任務時個工人去完成第當不指派第項任務時個工人去完成第當指派第jijixij 01? 指派問題不但是整數(shù)規(guī)劃，而且是 0?1規(guī)劃 ? 指派問題 也 是運輸問題的特例，即 m=n , ai=bj=1。 ? 指派問題有 2n個約束條件，但有且只有 n個非零解，是自然高度退化的 ? 指派問題的可行解矩陣中，各行各列的元素之和都是 1。如： ? 指派 問題，有著名的匈牙利算法 指派問題的特點： ???????????????1000000101000010)( ijx指派問題實例 例 1 有四個熟練工人，他們都是多面手，有四項任務要他們完成。若規(guī)定每人必須完成且只完成一項任務，而每人完成每項任務的工時耗費如下表，問如何分配任務使完成四項任務的總工時耗費最少？ A B C D 任務 人員 甲 10 9 7 8 乙 5 8 7 7 丙 5 4 6 5 丁 2 3 4 5 （ 2）指派問題的算法 匈牙利算法 定理 2 若效率矩陣中一部分元素為零，一部分元素非零，則覆蓋矩陣內所有零元素的最少直線數(shù)等于位于不同行、不同列的零元素的最多個數(shù)。 匈牙利算法的 基本思路 ： ? 根據(jù)定理 1變換效率矩陣，使矩陣中有足夠多的零。若矩陣中存在 n個不同行不同列的零，就找到了最優(yōu)解。 ? 若覆蓋變換后的效率矩陣零元素的直線少于 n條，就尚未找到最優(yōu)解，設法進一步變換矩陣，增加新的零。 匈牙利算法的 理論基礎 定理 1如果從效率矩陣 (cij)的某一行 (列 )各元素中分別減去一個常數(shù) k， 得到一個新的矩陣 (bij)， 那么 ， 以 (bij)為效率矩陣的指派問題的最優(yōu)解和原問題的最優(yōu)解相同 。 匈牙利算法的步驟：例 1 第一步：變換效率矩陣，使每行每列至少有一個零 ? 行變換：找出每行最小元素，從該行各元素中減去之 ? 列變換：找出每列最小元素，從該列各元素中減去之 ??????????????54325645778587910第二步：進行試指派，以尋求最優(yōu)解 * ?????????????? 1023* * * 223012013210? ?? 換變列? ?? 換變行??????????????* 2102012300232010⑴ 從只有一個 0
教學課件相關推薦
鄂ICP備17016276號-1