系統(tǒng)工程---第四章整數(shù)規(guī)劃-在線瀏覽
2024-12-05 18:55本頁(yè)面
【正文】 ???????????? 0,16 2 329544050m a x21212121xxxxxxxxf松弛問(wèn)題 B 求解各分枝問(wèn)題 問(wèn)題 B1 問(wèn)題 B2 x1= x2=3 f1=285 x1= x2=4 f2= 因 f1 f2， 故有 28590 * ?? f繼續(xù)對(duì)問(wèn)題 B1和 B2進(jìn)行分解， ???????????????? 0,3316 2 329544050m a x21122121321xxxxxxxxBxxf問(wèn)題???????????????? 0,4316 2 329544050m a x21122121421xxxxxxxxBxxf問(wèn)題因 f1 f2， 先分解 B1為 B3和 B4 求解各分枝問(wèn)題 問(wèn)題 B3 問(wèn)題 B4 x1=3 x2=3 f3=270 x1=4 x2=2 f4=280 因 f4 f3， 故有 285280 * ?? f因 f2=280， 所以再分解 B2已無(wú)必要，剪去該分枝。 松弛問(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)解。其基本思路是：先找到一組可行解，增加一個(gè)過(guò)濾條件，然后改進(jìn)過(guò)濾值，直至不能改進(jìn)為止。 于是增加過(guò)濾條件 ： 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） 指派問(wèn)題的數(shù)學(xué)模型 : 引入 01變量 xij (i,j=1,2,…, n) ?????????????????? ???? ?1,0,2,1 1,2,1 1m in111 1ijniijnjijninjijijxnjxnixxcf??模型中： cij 為第 i 個(gè)工人完成第 j 項(xiàng)任務(wù)的時(shí) 間 (成本、費(fèi)用 )； {cij}n?n 稱為 效率矩陣 ????項(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)題，有著名的匈牙利算法 指派問(wèn)題的特點(diǎn)： ???????????????1000000101000010)( ijx指派問(wèn)題實(shí)例 例 1 有四個(gè)熟練工人，他們都是多面手，有四項(xiàng)任務(wù)要他們完成。 匈牙利算法的 基本思路 ： ? 根據(jù)定理 1變換效率矩陣，使矩陣中有足夠多的零。 ? 若覆蓋變換后的效率矩陣零元素的直線少于 n條，就尚未找到最優(yōu)解，設(shè)法進(jìn)一步變換矩陣，增加新的零。 匈牙利算法的步驟：例 1 第一步：變換效率矩陣，使每行每列至少有一個(gè)零 ? 行變換：找出每行最小元素，從該行各元素中減去之 ? 列變換：找出每列最小元素，從該列各元素中減去之 ??????????????54325645778587910第二步：進(jìn)行試指派，以尋求最優(yōu)解 * ?????????????? 1023
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1