整數(shù)線性規(guī)劃ppt課件-文庫吧資料
2025-01-27 23:17本頁面
【正文】 這種方法直至所有零都被標記，或出現(xiàn) 情況 a，或 情況 c 。若該列有二個以上未標記的零，暫不標記，轉(zhuǎn)下一列檢查，直到所有列檢查完；重復 2后，可能出現(xiàn)三種情況：a. 每行都有一個 (0)，顯然已找到最優(yōu)解，令對應 (0)位置的 xij=1；b. 仍有零元素未標記，此時，一定存在某些行和列同時有多個零，稱為 僵局狀態(tài) ，因為無法采用 2 中的方法繼續(xù)標記。若矩陣中存在 m 個不同行不同列的零，就找到了最優(yōu)解n 若覆蓋變換后的效率矩陣零元素的直線少于 m 條，就尚未找到最優(yōu)解，設法進一步變換矩陣，增加新的零75 清華算法的步驟：例 第一步 ：變換效率矩陣，使每行每列至少有一個零q 行變換 ：找出每行最小元素，從該行各元素中減去之q 列變換 ：找出每列最小元素，從該列各元素中減去之第二步 ：檢查覆蓋所有零元素的直線是否為 m條劃線規(guī)則逐行檢查 ，若該行只有一個未標記的零，對其加 ( )標記，將 ( )標記元素同行同列上其它的零打上 *標記。 證明：略定理 2 若方陣中一部分元素為零，一部分元素非零，則覆蓋方陣內(nèi)所有零元素的最少直線數(shù)等于位于不同行、不同列的零元素的最多個數(shù)。n 算例71算 例 max 3 x1+5 x2+4 x3 subject to 2 x1+3 x2=1500 2 x2+4 x3=800 3 x1+2 x2 +5 x3=2022endgin x1gin x372 任務分配問題例 有四個熟練工人，他們都是多面手，有四項任務要他們完成。48n 對 01整數(shù)規(guī)劃分支時49分枝問題解可能出現(xiàn)的情況情況 2, 4, 5 找到最優(yōu)解情況 3 在縮減的域上繼續(xù)分枝定界法情況 6 問題 1 的整數(shù)解作為 界 被保留，用于以后與問題 2 的后續(xù)分枝所得到的解進行比較，結(jié)論如情況 4 或 550分枝定界法舉例 例 4解 ：松弛問題的最優(yōu)解為 x1=, x2=2, OBJ=23 由 x1= 得到兩個分枝如下：51 表 分枝問題的松弛解問題 II的解即原整數(shù)問題的最優(yōu)解 可能存在兩個分枝都是非整數(shù)解的情況，則需要兩邊同時繼續(xù)分枝，直到有整數(shù)解出現(xiàn)，就可以進行定界過程 當存在很多變量有整數(shù)約束時，分枝即廣又深，在最壞情況下相當于組合所有可能的整數(shù)解 一般整數(shù)規(guī)劃問題屬于一類未解決的難題， NPplete，只有少數(shù)特殊問題有好的算法，如 任務分配問題 、 匹配問題52n 算法思想n 算法步驟n 算例割平面算法53算 法 思 想n 由放松問題的可行域向整數(shù)規(guī)劃的可行域逼近n 方法 — 利用超平面切除n 要求 整數(shù)解保留 放松問題最優(yōu)值增加54割平面生成方法n 條件 保留整數(shù)
教學課件相關推薦
鄂ICP備17016276號-1