運籌學資料4整數(shù)規(guī)劃-展示頁
2024-10-26 01:00本頁面
【正文】 (0,0,1) 5 1 1 0 1 yes 5 改進過濾性條件 Z ? 5 (0’) 循環(huán) (X2,X1,X3) .0’ .1 .2 .3 .4 滿足 Z值 3 (0,1,0) 3 no 4 (0,1,1) 8 0 2 1 1 yes 8 改進過濾性條件 Z ? 8 (0’’) 循環(huán) (X2,X1,X3) .0’’ .1 .2 .3 .4 滿足 Z值 5 (1,0,0) 2 no 6 (1,0,1) 3 no 7 (1,1,0) 1 no 8 (1,1,1) 6 no 最優(yōu)解 (X2,X1,X3) =（ 0， 1， 1） Z=8 實際只計算了 16次 例 510 求下列問題： Max Z=3x1+ 4x2 + 5x3 + 6x4 . 2x1+ 3x2 + 4x3 + 5x4 ? 15 xj ? 0且為整數(shù) 解：先變換 xj為 01變量 x=y0+2y1+22y2+….2 kyk 解： 先變換 xj為 01變量 x=y0+2y1+22y2+….2 kyk x1 ? 7 x1=y01+2y11+22y21 x2 ? 5 x2=y02+2y12+22y22 x3 ? 3 x3=y03+2y13 x4 ? 3 x4=y04+2y14 代入原問題，得到： Max Z= 3 y01+6y11+12y21 + 4y02+8y12+16y22 + 5 y03+10y13 + 6 y04+12y14 . 2y01+4y11+8y21 +3y02+6y12 +12y22 + 4 y03+8y13 + 5 y04 +10y14 ? 15 yij=0或 =1 用隱枚舉法可得到： y11=y21 =y02 =1 其他全為零 最優(yōu)解 （ 6， 1， 0， 0） Z=22 01規(guī)劃應用 華美公司有 5個項目被列入投資計劃，各項目的投資額和期望的投資收益見下表： 項目 投資額 (萬元 ) 投資收益 (萬元 ) 1 210 150 2 300 210 3 100 60 4 130 80 5 260 180 該公司只有 600萬元資金可用于投資，由于技術原因，投資受到以下約束： ?在項目 2和 3中必須有一項被選中； ?項目 3和 4只能選中一項； ?項目 5被選中的前提是項目 1必須被選中。 ?價值系數(shù)按遞增排列。 循環(huán) (X1,X2,X3) .0 .1 .2 .3 .4 滿足 Z值 1 (0,0,0) 0 no 2 (0,0,1) 5 1 1 0 1 yes 5 3 (0,1,0) 2 no 4 (0,1,1) 3 1 5 no 5 (1,0,0) 3 1 1 1 0 yes 3 6 (1,0,1) 8 0 2 1 1 yes 8 7 (1,1,0) 1 no 8 (1,1,1) 6 2 6 no 最優(yōu)解（ 1， 0， 1） Z=8 增加約束條件（ 0）（ Z ? 3)后實際做了 24次運算，而原問題需要計算23*4=32次運算（ 3個變量， 4個約束條件 ）。 例 59 求下列問題： Max Z=3x1 2x2 + 5x3 . x1+2x2 x3 ? 2 (1) x1+4x2 + x3 ? 4 (2) x1 + x2 ? 3 (3) 4x2 + x3 ? 6 (4) xj ? 0或 1 (5) 解： 容易看出 (1,0,0)滿足約束條件，對應 Z=3，對 Max Z來說，希望 Z ? 3,所以增加約束條件： Z=3x1 2x2 + 5x3 ? 3 (0)
教學課件相關推薦
鄂ICP備17016276號-1