尼邁耶，O.

[拼音]：0-1 guihua

[英文]：0-1 programming

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

應用範圍

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

互斥計劃問題

如確定投資專案，選定投資場所，決定投產產品等。設有幾種產品，各產品投產後獲得的利潤為cj，投資限額為B，規定決策變數xj的取值為

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

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

約束條件互斥問題

設有 m個互相排斥的約束條件（≤型）ai1x1＋ai2x2＋…＋ainxn≤bi(i＝1，2，…，m)為了保證這m個約束條件中只有一個起作用,引入m個0-1變數yi和一個足夠大的常數M，構造m＋1個約束條件

ai1x1＋ai2x2＋…＋ainxn≤bi＋yiM

y1＋y2＋…＋ym＝m－1

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

如運送兩種貨物，其數量分別為 x1和x2，車運時貨物體積不得超過b1，船運時貨物重量不得超過b2，即

a11x1＋a12x2≤b1 （車運），

a21x1＋a22x2≤b2 （船運）。

若只能採用一種運送方式，這兩個約束條件是互相排斥的。為了統一在一個問題中，引用0-1變數yi，設

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

a11x1＋a12x2≤b1＋y1M

a21x1＋a22x2≤b2＋y2M

y1＋y2＝2-1

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

固定費用問題

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

(i＝1,2,…,n)

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

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

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

分派問題

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

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

分派問題的數學模型為

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

隱列舉法

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

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

參考書目

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