[數學模型]整數規劃(一)

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

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

(ii)割平面法—可求純或混合整數線性規劃。
(iii)隱列舉法—求解“0-1”整數規劃:
    ①過濾隱列舉法;
    ②分枝隱列舉法。
(iv)匈牙利法—解決指派問題(“0-1”規劃特殊情形)。

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

分支定界法branch and bound

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

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

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

0-1規劃的拓展應用

如果有M個約束條件 只有一個能起作用, 那麼可以這樣寫

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