型整數(shù)規(guī)劃模型

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

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

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

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

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

6、，0，1，1）（0，1，0，0）（0，1，0，1）（0，1，1，0）（0，1，1，1）（1，0，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）30303030505070709090909090909090×3030×3050×5070×7090×90×90×90×90×90×90×90×90注：在該表中，表示滿足相應(yīng)條件，×表示不滿足相應(yīng)條件。例2   工序

7、的流程安排問題1）問題的提出 一條裝配線由一系列工作站組成，被裝配或制造的產(chǎn)品在裝配線上流動的過程中，每站都要完成一道或幾道工序，假定一共有六道工序，這些工序按先后次序在各工作站上完成，關(guān)于這些工序有如下的數(shù)據(jù)：工序所需時(shí)間（分）前驅(qū)工序13無25無322461，3582634另外工藝流程特別要求，在任一給定的工作站上，不管完成哪些工序，可用的總時(shí)間不能超過10分鐘，如何將這些工序分配給各工作站，以使所需的工作站數(shù)為最少？2）模型分析與變量的假設(shè)下面，我們先討論工序與工作站的關(guān)系，并試圖建立起該問題的01型整數(shù)規(guī)劃模型。對任一工序而言，它要么屬于工作站，要么不屬于工作站，故決策變量可定義為：這

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