0-1規劃

　　決策變數僅取值0或1的一類特殊的整數規劃。在處理經濟管理中某些規劃問題時，若決策變數採用 0-1變數即邏輯變數，可把本來需要分別各種情況加以討論的問題統一在一個問題中討論。

　　應用範圍　0-1規劃主要用於求解互斥的計畫問題、約束條件互斥問題、固定費用問題和分派問題等方面。

　　互斥計畫問題　如確定定投資項目，選定投資場所，決定投產產品等。設有幾種產品，各產品投產後獲得的利潤為c_j，投資限額為B，規定決策變量x_j的取值為

則此0-1規劃的數學模型為

　

　

式中max表示求極大值；s.t.表示“受約束於”；_z是目標函數；a_j 是各種產品的投資額。

　　約束條件互斥問題　設有 m個互相排斥的約束條件（≤型）　a_i1x₁＋a_i2x₂＋…＋a_inx_n≤b_i　(i＝1，2，…，m)為瞭保證這m個約束條件中隻有一個起作用,引入m個0-1變量y_i和一個足夠大的常數M，構造m＋1個約束條件

　a_i1x₁＋a_i2x₂＋…＋a_inx_n≤b_i＋y_iM

y₁＋y₂＋…＋y_m＝m－1

因為m個y_i中隻有一個能取0值，所以隻有一個約束條件能起作用。

　　如運送兩種貨物，其數量分別為 x₁和x₂，車運時貨物體積不得超過b₁，船運時貨物重量不得超過b₂，即

　 a₁₁x₁＋a₁₂x₂≤b₁（車運），

a₂₁x₁＋a₂₂x₂≤b₂（船運）。

若隻能采用一種運送方式，這兩個約束條件是互相排斥的。為瞭統一在一個問題中，引用0-1變量y_i，設

把上述約束條件改造成為下面一組約束條件：

a₁₁x₁＋a₁₂x₂≤b₁＋y₁M

a₂₁x₁＋a₂₂x₂≤b₂＋y₂M

y₁＋y₂＝2-1

式中M是足夠大的數，采用車運時y₁＝0，由第1式即得到車運約束條件，采用船運時y₂＝0，由第2式即得到船運約束條件。因此上述互相排斥的約束條件被一組聯立約束條件所代替。

　　固定費用問題　采用一般線性規劃不能解決固定費用問題，需要用0-1規劃。設有n種生產方式可供選擇，x_i為采用第_i種方式時的產量,c_i為采用第_i種方式時每件產品的變動成本，k_i為采用第 i種方式時的固定成本，采用各種生產方式的總成本分別為

　( i＝1,2,…, n)

在構成目標函數時，為瞭統一在一個問題中討論，引入0-1變量y_i，即

則此0-1規劃的數學模型為

式中min表示求極小值，M是充分大的常數。

　　分派問題　由幾個人去完成幾項任務，但由於任務性質和各人專長不同，應分派哪個人去完成哪項任務，以使總效率最高或耗費的總時間最小，這類問題稱為分派問題，又稱指派問題。

　　分派問題必須給出系數矩陣（又稱效率矩陣），矩陣的元素 c_ij(>0)(i，j＝1，2，…，n)表示派第i人去完成第j項任務時的效率（或時間、成本等）。引用0-1變量x_ij，設

分派問題的數學模型為

第1個約束條件說明第j項任務隻能由1人去完成，第2個約束條件說明第i人隻能完成1項任務。分派問題的解可寫成矩陣形式(x_ij)，其各行各列的元素之和都是1。

　　隱枚舉法　0-1規劃問題一般有三種解法,即變換法、窮舉法和隱枚舉法。上述方法即為變換法，用於解特殊的0-1規劃問題。窮舉法就是檢查變量取值為0或 1的每一種組合，比較目標函數值來求最優解，這就需要檢查變量取值的2ⁿ個組合。對於n>10的情況，這幾乎是辦不到的。因此常設計一些方法，隻檢查變量取值組合的一部分，就能得到問題的最優解。這樣的方法稱為隱枚舉法。

　　采用隱枚舉法解 0-1規劃問題時要根據目標函數的性質增加一個相應的不等式作為附加約束條件，稱為過濾條件，以減少運算次數。一般還要按目標函數中x_i的系數遞增的順序，重新排列目標函數和約束條件中x_i的次序，以簡化計算。

　　

參考書目

　S.P.勃雷達蘭等著，翟立林等譯：《應用數學規劃》，機械工業出版社，北京，1983。(Stephen P.Bradley,Arnoldo C.Hax,Thomas L.Magnanti, Applied Mathematical Programming, Addison-Wesley Publ.Co.,1977.)