1、5.4 01型整數(shù)規(guī)劃模型1、 01型整數(shù)規(guī)劃模型概述整數(shù)規(guī)劃指的是決策變量為非負整數(shù)值的一類線性規(guī)劃，在實際問題的應用中，整數(shù)規(guī)劃模型對應著大量的生產(chǎn)計劃或活動安排等決策問題，整數(shù)規(guī)劃的解法主要有分枝定界解法及割平面解法（這里不作介紹，感興趣的讀者可參考相關(guān)書籍）。在整數(shù)規(guī)劃問題中，01型整數(shù)規(guī)劃則是其中較為特殊的一類情況，它要求決策變量的取值僅為0或1，在實際問題的討論中，01型整數(shù)規(guī)劃模型也對應著大量的最優(yōu)決策的活動與安排討論，我們將列舉一些模型范例，以說明這個事實。01型整數(shù)規(guī)劃的的數(shù)學模型為：目標函數(shù) 約束條件為：這里，0 | 1表示0或1。2、01型整數(shù)規(guī)劃模型的解法 01型整數(shù)規(guī)

2、劃模型的解法一般為窮舉法或隱枚舉法，窮舉法指的是對決策變量的每一個0或1值，均比較其目標函數(shù)值的大小，以從中求出最優(yōu)解。這種方法一般適用于決策變量個數(shù)較小的情況，當較大時，由于個0、1的可能組合數(shù)為，故此時即便用計算機進行窮舉來求最優(yōu)解，也幾乎是不可能的。隱枚舉法是增加了過濾條件的一類窮舉法，該法雖能減少運算次數(shù)，但有的問題并不使用。此時，就只能用窮舉法了。3. 應用實例例1 工程上馬的決策問題1）問題的提出 某部門三年內(nèi)有四項工程可以考慮上馬，每項工程的期望收益和年度費用（千元）如下表所示：假定每一項已選定的工程要在三年內(nèi)完成，是確定應該上馬哪些工程，方能使該部門可能的期望收益最大。工 程費

3、 用期望收益第1年第2年第3年15 1 84 7 103 9 28 6 1020402030234可用資金1822242）模型分析與變量的假設 這是工程上馬的決策問題，對任一給定的工程而言，它只有兩種可能，要么上馬，要么不上馬，這兩種情況分別對應二進制數(shù)中的1、0，大凡這樣的實際背景所對應的工程問題，大都可考慮用01型整數(shù)規(guī)劃模型建立其相應的模型。設因每一年的投資不超過所能提供的可用資金數(shù)25千元，故該01型整數(shù)規(guī)劃問題的約束條件為：由于期望收益盡可能大，故目標函數(shù)為：3）模型的建立與求解至此，我們得到該問題的01型整數(shù)規(guī)劃模型為：約束條件為：下面用隱枚舉法求其最優(yōu)解。易知，該01型整數(shù)規(guī)劃模

4、型有一可行解（0，0，0，1），它對應的目標函數(shù)值為：。自然，該模型的最優(yōu)解所對應的目標函數(shù)值應不小于30，于是，我們增加一過濾條件為： （4）在此過濾條件（過濾條件可不唯一）下，用隱枚舉法求01型整數(shù)規(guī)劃模型的最優(yōu)解的步驟為：（1）先判斷第一枚舉點所對應的目標函數(shù)值是否滿足過濾條件，若不滿足，則轉(zhuǎn)下一步；若滿足，再判斷該枚舉點是否滿足各約束條件，若有一個約束條件不滿足，則轉(zhuǎn)下一步，若均滿足，則將該枚舉點所對應的目標函數(shù)值z1（本例中，z1）作為新的目標值，并修改過濾條件為： ，再轉(zhuǎn)下一步；(2) 再判斷第二枚舉點所對應的目標函數(shù)值是否滿足新的過濾條件，若不滿足，則轉(zhuǎn)下一步；若滿足，接著判斷該

5、枚舉點是否滿足各約束條件，若有一個約束條件不滿足，則轉(zhuǎn)下一步，若均滿足，則將該枚舉點所對應的目標函數(shù)值z2（z2 z1）作為新的目標值，并修改過濾條件為： ，再轉(zhuǎn)下一步；(3) 重復步驟（2），直至所有的枚舉點均比較結(jié)束為止。由隱枚舉法的求解步驟，我們可給出該問題的求解過程如下表所示，并得到最優(yōu)解為：，相應的目標值為90（千元）。故應上馬的工程為2號、3號、4號工程。枚舉點當前目標值滿足約束條件（含過濾條件）？新目標值（4）（1）（2）（3）（0，0，0，0）（0，0，0，1）（0，0，1，0）（0，0，1，1）（0，1，0，0）（0，1，0，1）（0，1，1，0）（0，1，1，1）（1，0，

6、0，0）（1，0，0，1）（1，0，1，0）（1，0，1，1）（1，1，0，0）（1，1，0，1）（1，1，1，0）（1，1，1，1）3030303050507070909090909090909030303050507070909090909090909090注：在該表中，表示滿足相應條件，表示不滿足相應條件。例2 工序的流程安排問題1）問題的提出 一條裝配線由一系列工作站組成，被裝配或制造的產(chǎn)品在裝配線上流動的過程中，每站都要完成一道或幾道工序，假定一共有六道工序，這些工序按先后次序在各工作站上完成，關(guān)于這些工序有如下的數(shù)據(jù)：工序所需時間（分）前驅(qū)工序13無25無322461，358263

7、4另外工藝流程特別要求，在任一給定的工作站上，不管完成哪些工序，可用的總時間不能超過10分鐘，如何將這些工序分配給各工作站，以使所需的工作站數(shù)為最少？2）模型分析與變量的假設下面，我們先討論工序與工作站的關(guān)系，并試圖建立起該問題的01型整數(shù)規(guī)劃模型。對任一工序而言，它要么屬于工作站，要么不屬于工作站，故決策變量可定義為：這種定義，使我們能根據(jù)最優(yōu)解中的值來很快確定工序與工作站之間的隸屬關(guān)系。 又因工序1，2，3所需的工作時間不超過10分鐘，故工序1，2，3的工作可以在一個工作站上完成，此時，工序4，5，6只能分別在各自的工作站上工作，該可行解對應的工作站數(shù)為4個。也就是說，對最優(yōu)解而言，該裝配

8、線上所需的工作站個數(shù)不會多于4個。因此，我們再定義變量如下：至此，我們得到所需的目標函數(shù)為：再考慮該模型的約束條件：（1） 每道工序均隸屬于一個工作站，且每一工序都必須完成，故有以下六個約束：（2）在任一工作站上完成隸屬工序所用的時間不能超過10分鐘，故有以下四個約束：（3）最后，我們再考慮各道工序所受的先后次序約束的條件。先考察工序2與工序3的關(guān)系，因工序2在工序3之前運行，故若工序3隸屬于工作站4，則工序2無論屬于那個工作站均可；若工序3隸屬于工作站3，則工序2可屬于工作站1或2或3；此時，變量應滿足的約束條件為：；同理，若工序3隸屬于工作站2或1，則變量應 滿足的約束條件為：同理，根據(jù)其它工序的優(yōu)先關(guān)系，可仿此法給出其相應的約束條件，由上圖知，六個工序之間有五個優(yōu)先關(guān)系，故這類約束條件共有15個。另外，在最優(yōu)解中，若有一個工作站不用（即=0），則隸屬于該工作站的全部必須為0，于是，有以下四個約束條件：3）模型的建立與求解 至此，我們得到了該問題的01