§5.4 0—1型整數規劃模型
1、 0—1型整數規劃模型概述
整數規劃指的是決策變數為非負整數值的一類線性規劃，在實際問題的應用中，整數規劃模型對應著大量的生產計畫或活動安排等決策問題，整數規劃的解法主要有分枝定界解法及割平面解法（這裡不作介紹，感興趣的讀者可參考相關書籍）。在整數規劃問題中，0—1型整數規劃則是其中較為特殊的一類情況，它要求決策變數的取值僅為0或1，在實際問題的討論中，0—1型整數規劃模型也對應著大量的最優決策的活動與安排討論，我們將列舉一些模型範例，以說明這個事實。
0—1型整數規劃的的數學模型為：
目標函式
約束條件為：
這裡，0 | 1表示0或1。
2、0—1型整數規劃模型的解法
0—1型整數規劃模型的解法一般為窮舉法或隱列舉法，窮舉法指的是對決策變數的每乙個0或1值，均比較其目標函式值的大小，以從中求出最優解。這種方法一般適用於決策變數個數較小的情況，當較大時，由於個0、1的可能組合數為，故此時即便用計算機進行窮舉來求最優解，也幾乎是不可能的。隱列舉法是增加了過濾條件的一類窮舉法，該法雖能減少運算次數，但有的問題並不使用。
此時，就只能用窮舉法了。
3. 應用例項
例1 工程上馬的決策問題
1）問題的提出
某部門三年內有四項工程可以考慮上馬，每項工程的期望收益和年度費用（千元）如下表所示：假定每一項已選定的工程要在三年內完成，是確定應該上馬哪些工程，方能使該部門可能的期望收益最大。
2）模型分析與變數的假設
這是工程上馬的決策問題，對任一給定的工程而言，它只有兩種可能，要麼上馬，要麼不上馬，這兩種情況分別對應二進位制數中的1、0，大凡這樣的實際背景所對應的工程問題，大都可考慮用0—1型整數規劃模型建立其相應的模型。
設因每一年的投資不超過所能提供的可用資金數25千元，故該0—1型整數規劃問題的約束條件為：
由於期望收益盡可能大，故目標函式為：
3）模型的建立與求解
至此，我們得到該問題的0—1型整數規劃模型為：
約束條件為：
下面用隱列舉法求其最優解。易知，該0—1型整數規劃模型有一可行解（0，0，0，1），它對應的目標函式值為：。自然，該模型的最優解所對應的目標函式值應不小於30，於是，我們增加一過濾條件為：
4）在此過濾條件（過濾條件可不唯一）下，用隱列舉法求0—1型整數規劃模型的最優解的步驟為：
（1）先判斷第一枚舉點所對應的目標函式值是否滿足過濾條件，若不滿足，則轉下一步；若滿足，再判斷該列舉點是否滿足各約束條件，若有乙個約束條件不滿足，則轉下一步，若均滿足，則將該列舉點所對應的目標函式值z1（本例中，z1）作為新的目標值，並修改過濾條件為： ，再轉下一步；
(2) 再判斷第二列舉點所對應的目標函式值是否滿足新的過濾條件，若不滿足，則轉下一步；若滿足，接著判斷該列舉點是否滿足各約束條件，若有乙個約束條件不滿足，則轉下一步，若均滿足，則將該列舉點所對應的目標函式值z2（z2 z1）作為新的目標值，並修改過濾條件為： ，再轉下一步；
(3) 重複步驟（2），直至所有的列舉點均比較結束為止。
由隱列舉法的求解步驟，我們可給出該問題的求解過程如下表所示，並得到最優解為：，相應的目標值為90（千元）。故應上馬的工程為2號、3號、4號工程。
注：在該表中，√表示滿足相應條件，×表示不滿足相應條件。
例2 工序的流程安排問題
1）問題的提出
一條裝配線由一系列工作站組成，被裝配或製造的產品在裝配線上流動的過程中，每站都要完成一道或幾道工序，假定一共有六道工序，這些工序按先後次序在各工作站上完成，關於這些工序有如下的資料：
另外工藝流程特別要求，在任一給定的工作站上，不管完成哪些工序，可用的總時間不能超過10分鐘，如何將這些工序分配給各工作站，以使所需的工作站數為最少？
2）模型分析與變數的假設
下面，我們先討論工序與工作站的關係，並試圖建立起該問題的0—1型整數規劃模型。
對任一工序而言，它要麼屬於工作站，要麼不屬於工作站，故決策變數可定義為：
這種定義，使我們能根據最優解中的值來很快確定工序與工作站之間的隸屬關係。
又因工序1，2，3所需的工作時間不超過10分鐘，故工序1，2，3的工作可以在乙個工作站上完成，此時，工序4，5，6只能分別在各自的工作站上工作，該可行解對應的工作站數為4個。也就是說，對最優解而言，該裝配線上所需的工作站個數不會多於4個。因此，我們再定義變數如下：
至此，我們得到所需的目標函式為：
再考慮該模型的約束條件：
（1） 每道工序均隸屬於乙個工作站，且每一工序都必須完成，故有以下六個約束：
（2）在任一工作站上完成隸屬工序所用的時間不能超過10分鐘，故有以下四個約束：
（3）最後，我們再考慮各道工序所受的先後次序約束的條件。
先考察工序2與工序3的關係，因工序2在工序3之前執行，故若工序3隸屬於工作站4，則工序2無論屬於那個工作站均可；若工序3隸屬於工作站3，則工序2可屬於工作站1或2或3；此時，變數應滿足的約束條件為：
；同理，若工序3隸屬於工作站2或1，則變數應
滿足的約束條件為：
同理，根據其它工序的優先關係，可仿此法給出其相應的約束條件，由上圖知，六個工序之間有五個優先關係，故這類約束條件共有15個。
另外，在最優解中，若有乙個工作站不用（即=0），則隸屬於該工作站的全部必須為0，於是，有以下四個約束條件：
3）模型的建立與求解
至此，我們得到了該問題的0—1型整數規劃模型，它共包含28個變數，29個約束條件，這樣的模型用列舉法求解，人工計算是很難勝任的，這時，只能求助於計算機求解了。我們給出該問題的模型如下，求解的過程望感興趣的讀者自己完成之。
該問題的目標函式為：
約束條件為：
； ；
； ； ；
； ； ；
； ； ；
； ； ；
01型整數規劃模型
甲乙公司不合作即競爭下所爭取到的不同名專業推廣者所建立的不同動態規劃模 型的組合方案如下 其中x 為可能競爭到的專業推廣者人數，即動態規劃模型中第一天的專業推廣者推 廣能力的份數，y 為第二天需要的專業推廣者推廣能力的份數，即第三天安排從事推廣 工作的專業推廣者的人數 z 為第三天需要的專業推廣者推...
實驗三 求解線性規劃和整數規劃模型
數學建模 實驗指導 姓名 吳家猛 班號 ap08055 學號 ap0805530 五邑大學資訊工程學院 二 一o年十一月 實驗3 指導書 實驗專案名稱 求解線性規劃和整數規劃模型 所屬課程名稱 數學建模 實驗計畫學時 2學時 一 實驗目的 掌握使用數學軟體lingo或matlab等軟體求解線性規劃和...
數學建模作業實驗4整數規劃和對策論模型
數學建模作業 實驗4整數規劃和對策論模型 基本實驗 乙個行為古怪的阿拉伯酋長留下了乙份遺囑，遺囑中將他的駱駝群分給他的三個兒子 長子至少得到駝群的1 2，次子至少得到駝群的1 3，三子至少得到駝群的1 9，剩餘的捐獻給慈善機構。遺囑中沒有指出到底駝群的數目是多少，只是告訴了這個駝群的數目是奇數，並且...