天天看點

[數學模型]整數規劃(一)分支定界法branch and bound0-1規劃的拓展應用

整數規劃問題比較簡單,  主要解法分為這幾種:

(i)分枝定界法—可求純或混合整數線性規劃。

(ii)割平面法—可求純或混合整數線性規劃。

(iii)隐枚舉法—求解“0-1”整數規劃:

    ①過濾隐枚舉法;

    ②分枝隐枚舉法。

(iv)匈牙利法—解決指派問題(“0-1”規劃特殊情形)。

(v)蒙特卡洛法—求解各種類型規劃。

分支定界法branch and bound

[數學模型]整數規劃(一)分支定界法branch and bound0-1規劃的拓展應用
[數學模型]整數規劃(一)分支定界法branch and bound0-1規劃的拓展應用
[數學模型]整數規劃(一)分支定界法branch and bound0-1規劃的拓展應用

看問題大家大概都明白了,  說一下上下界确定的問題,

每一次分支的函數值最大的解就是上界

如果有整數解,  那麼函數值最大的整數解就是下界

0-1規劃的拓展應用

如果有M個限制條件 隻有一個能起作用, 那麼可以這樣寫

[數學模型]整數規劃(一)分支定界法branch and bound0-1規劃的拓展應用

0-1規劃問題接下來會講,  這涉及圖論方面, 

繼續閱讀