系統(tǒng)工程---第四章整數(shù)規(guī)劃-wenkub
2022-11-02 18:55:34 本頁(yè)面
【正文】 ijijxnjxnixxcf??模型中： cij 為第 i 個(gè)工人完成第 j 項(xiàng)任務(wù)的時(shí) 間 (成本、費(fèi)用 )； {cij}n?n 稱(chēng)為 效率矩陣 ????項(xiàng)任務(wù)時(shí)個(gè)工人去完成第當(dāng)不指派第項(xiàng)任務(wù)時(shí)個(gè)工人去完成第當(dāng)指派第jijixij 01? 指派問(wèn)題不但是整數(shù)規(guī)劃，而且是 0?1規(guī)劃 ? 指派問(wèn)題 也 是運(yùn)輸問(wèn)題的特例，即 m=n , ai=bj=1。 松弛問(wèn)題 B x1= x2= f= 問(wèn)題 B3 x1=3 x2=3 f3=270 問(wèn)題 B1 x1= x2=3 f1=285 問(wèn)題 B2 x1= x2=4 f2= 問(wèn)題 B4 x1=4 x2=2 f4=280 x2≤3 x1≥4 x1≤3 x2≥4 * ?? f28590 * ?? f285280 * ?? f 2. 01規(guī)劃的解法 m ax, ,f x x xx x xx x xx xx xx x x? ? ?? ? ?? ? ?? ?? ???????????? ? ?? ?? ??? ?? ?? ? ?? ? ?? ? ?? ?? ?? ? ?或枚舉法 即檢查變量取值為 0或 1的每一個(gè)組合 ， 比較目標(biāo)函數(shù)值的大小以求得最優(yōu)解。 各分枝的最優(yōu)目標(biāo)函數(shù)中若有小于 者，則剪掉這枝，即以后不再考慮了。 修改 A的最優(yōu)目標(biāo)函數(shù)值的上下界 。 否則 ， 進(jìn)行 Step4。 若 B有最優(yōu)解 ， 且符合問(wèn)題 A的整數(shù)條件 ， 則 B的最優(yōu)解也是 A的最優(yōu)解 ， 則停止 。這種方法有很強(qiáng)的適應(yīng)能力，是目前較為成功的求解整數(shù)規(guī)劃問(wèn)題的一種方法。一、 整數(shù)規(guī)劃簡(jiǎn)介 ?整數(shù)規(guī)劃 是數(shù)學(xué)規(guī)劃的一個(gè)重要分支，它研究的是一類(lèi)要求其部分或全部變量取整數(shù)的最優(yōu)化問(wèn)題。 基本思想： 分枝定界法是通過(guò)有系統(tǒng)的“分枝”和“定界”步驟來(lái)尋求最優(yōu)解的。 若 B有最優(yōu)解 ， 但不符合 A的整數(shù)條件 ， 記其目標(biāo)函數(shù)值為 f1。 1ff ?fff ?? *f f ff ?fStep4 分枝 ， 在 B的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量xj=bj， 以 [bj]表示小于 bj的最大整數(shù)。 在各分枝問(wèn)題的最優(yōu)解中，找出最優(yōu)目標(biāo)函數(shù)值最大者作為新的上界。若大于 ，且不符合整數(shù)條件，則重復(fù) Step4至 Step6,直至 ，求出整數(shù)最優(yōu)解為止。 例 3 求解 01規(guī)劃 解 （ x1， x2， x3） 共有 23=8種不同的組合，各種組合下目標(biāo)函數(shù)及各約束條件左端的值列于下表： ① ② ③ ④ 枚舉法表 ① ② ③ ④ 滿足約 束條件 ？ 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 0 0 0 1 1 0 1 2 4 1 4 1 5 1 5 1 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） 隱枚舉法 所謂 隱枚舉法 就是只檢查變量取值組合的一部分就能求得問(wèn)題最優(yōu)解的方法。 ? 指派問(wèn)題有 2n個(gè)約束條件，但有且只有 n個(gè)非零解，是自然高度退化的 ? 指派問(wèn)題的可行解矩陣中，各行各列的元素之和都是 1。若矩陣中存在 n個(gè)不同行不同列的零，就找到了最優(yōu)解。 ⑵ 從只有一個(gè) 0元素的列開(kāi)始，給這個(gè) 0元素加圈，記作 ◎， 然后劃去 ◎ 所在行的其它 0元素，記作 0 。 第三步：做能覆蓋所有 0元素的最少直線集合 。 ⑷ 重復(fù) ⑵ 、 ⑶ 直到得不出新的 打 ?號(hào)的行 、 列為止 。為此轉(zhuǎn)入第四步。 例 3有 A、 B、 C、 D四項(xiàng)工作 ， 需要甲 、 已 、 丙 、 丁四人完成 ，每人只能完成其中的一項(xiàng) 。 規(guī)定每項(xiàng)工作只能由一人去完成 ， 每人最多承擔(dān)一項(xiàng)工作 ， 又假定 A必須分配到一項(xiàng)工作 ，D因某種原因決定不承擔(dān)第 4項(xiàng)工作 。 定理 2 若矩陣 B中的所有零元素構(gòu)不成 n個(gè)位于不同行不同列的零元素 ， 此時(shí)令 ， 其中 則以 D為效率矩陣的問(wèn)題 （ P） 有最優(yōu)解的充分必要條件是以B為效率矩陣的問(wèn)題 （ P） 有最優(yōu)解 ， 且最優(yōu)解相同 。 。 njiccbbB ijjiijijnnij ,2,1,m i n,)( , ????? ?B bij n n? ?( )njibbbbbijijbjiijijijij,2,1,0,mi n0,00,??????
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1