第三章整數規(guī)劃運籌學

第三章整數規(guī)劃用單純形法求解線性規(guī)劃問題，其最優(yōu)解往往是分數或小數．但對于某些實際問題，常要求全部或部分變量的最優(yōu)解必須是整數．例如，所求的解是人數，機器臺數或工廠個數等，若用分數或小數表示答案就顯得不夠合理．

在一個線性規(guī)劃問題中，若要求全部變量取整數值，稱為純整數規(guī)劃問題．若要求部分變量取整數值，稱為混合整數規(guī)劃問題．這兩類問題簡稱為整數規(guī)劃．

求解整數規(guī)劃問題，初看起來好像很簡單，比如把帶有分數或小數的解進行“收尾”或“去尾”處理就可以了．事實上，這樣處理有時行得通，有時卻行不通．例如，某公司根據市場需要，用線性規(guī)劃的方法得到一個方案是；增加甲產品的工廠3.7個，乙產品的工廠1.5個．如果用湊整方法求其解，則有四個近似方案：（4，1），（4，2），（3，1），（3，2），顯然，這四個方案相互差別很大．對原線性規(guī)劃問題來說，它們有的是可行解，有的則不是可行解；或雖是可行解，但不一定是最優(yōu)解．因此，對求最優(yōu)整數解的問題，有必要另行研究．然而時至今日，求解整數規(guī)劃還沒有一個很滿意的有效的解法．下面介紹幾種較為常用的方法

§3.1分枝定界法

設有整數規(guī)劃問題（A）為：

與它對應的線性規(guī)劃問題（B）（亦稱為松弛問題）為：

顯然，問題（A）的可行解集是問題（B）的可行解集的子集．因而，（A）的最優(yōu)值（B）的最優(yōu)值．第一步

對線性規(guī)劃（B）求解，其結果有下列三種情形：（1）（B）無可行解，這時（A）也無可行解，停止計算；（2）（B）有整數最優(yōu)解，且符合（A）的整數條件，這時（B）的最優(yōu)解就是（A）的最優(yōu)解，停止計算；（3）（B）有最優(yōu)解，而其解不全為整數．這時（B）的最優(yōu)解不是（A）的可行解．但是，（B）的目標函數最優(yōu)值（設為），是（A）的最優(yōu)目標函數值S*的上界（求最小值時，為其下界）．

第二步

分枝與定界．設線性規(guī)劃問題（B）的最優(yōu)解為

且其中xj*（j=1，2，…，n）不是整數，則必有

其中[xj*]表示小于xj*的最大整數．由此構造兩個約束條件：

將其分別加入問題（B），從而得到(B)的兩枝子線性規(guī)劃問題（B1）和（B2），即

對問題（Bl）和（B2）求解．如果子問題有最優(yōu)解，但其解不全為整數，則選取最優(yōu)目標函數值的最大者（若目標函數求最小時，選最小者）作為新的上界；如果子問題中有最優(yōu)整數解，且其目標函數值小于新的上界，則其值可作為新的下界，（原問題(A)的下界可看作0）記作S．

第三步

剪枝．在繼續(xù)分枝的過程中，各分枝的最優(yōu)目標函數值如果有小于S，則稱這個分枝已被“查清”，將該枝剪掉，不再計算．因為再算下去不會得到更好的目標函數值．若有目標函數值大于下界S，且不符合整數條件，則重復第二步驟，直到找到S*．

例

求解問題（A）：

解

（1）設（A）的松弛問題為（B0），不受整數約束，利用單純形法求解（B0），得最優(yōu)解為：x1=2.25，x2=3.75，且S0=41.25．其可行解域如圖所示．顯然原問題（A）的可行域是問題（B0）的可行域的一個子集，整數最優(yōu)解應出現在可行域的整數點上，S0=41.25為其上界．

（2）分枝與定界

因x1，x2都是小數，可任選一個進行分枝．今選x2=3.75，對問題（B0）增加約束條件：x2[3.75]=3和x2[3.75]+1=4,則問題（B0）分解為兩個子問題（B1）和（B2）（即兩枝）．

求解線性規(guī)劃問題（B1）和（B2），得到如下最優(yōu)解：問題（B1）

x1=3，x2=3且s1=39．

問題（B2）x1=1.8，x2=4且s2=41．問題（B1）都是整數解，該問題已經查清．然而（B1）雖都是整數解，但s1<s2．這里s1=39可作為新的下界，s2=41可作為新的上界．值得指出的是，增加了約束條件x2≤3和x2≥4之后，雖然縮小了可行解的范圍，但原問題（A）的整數可行解沒有變，這是因為在3<x2<4內沒有整數解，見2圖．

(3)重復步驟（2），繼續(xù)對問題（B2）進行分解．因為在（B2）中x1=1.8，對問題（B2）增加約束條件：x1[1.8]=1和x1[1.8]+1=2,將問題（B2）再分解為兩個子問題（B3）和（B4）：

求解問題（B3）和（B4），得問題（B3）的最優(yōu)解為：

問題（B4）無可行解，這個子問題也已查清．因為在問題（B3）中有

S1<S3<S2，則作為新的上界．繼續(xù)對（B3）進行分解，使問題（B3）增加約束條件：x24和x25，則問題（B3）又分解為兩個子問題（B5）和（B6）：

求解線性規(guī)劃問題（B5）和（B6），得到如下最優(yōu)解：問題（B5）

x1=1，x2=4且S5=37；問題（B6）x1=0，x2=5且S6=40．問題（B5）和（B6）都是整數解，均屬查清．但S5<S1（下界），故將該枝剪去；又S1<S6<S3（上界），所以S6為原問題（A）的最優(yōu)值，它對應的解為其最優(yōu)解．計算終止．綜上所述，求解的全過程可用如下圖所示的樹形圖表示．

§3.2割

平

面

法

割平面法是求解整數規(guī)劃問題最早提出的一種方法．它的基本思想是：首先不考慮變量是整數的條件，但增加特定的約束條件（稱為割平面），使得在原凸可行域中切掉一部分，被切割掉的這部分不包含任何的整數可行解．這樣經過有限次的切割，最終可得到某個頂點的坐標恰好是整數，并且是問題的最優(yōu)解．割平面算法的基本類型有純整數型和混合型．本節(jié)僅討論純整數型的割平面算法，它的基本要求是：每一個約束條件的所有系數及右端常數項都必須是整數．下面先討論線性規(guī)劃問題存在整數解的必要條件．

§3.30一1規(guī)劃

在整數規(guī)劃中，如果所有決策變量xi只限于取0和1兩個值，則稱它為0一1規(guī)劃問題．0一1規(guī)劃的一個典型例子就是所謂“背包問題”：

一個旅行者，為了準備旅行的必備物品，要在背包里裝一些最有用的東西．但他最多只能攜帶b公斤的物品．而每件物品都只能整件攜帶，于是他給每件物品規(guī)定了一定的“價值”，以表示其有用程度．如果共有m件物品，第i件物品重ai公斤，其價值為ci．問題就變成：在攜帶的物品總重不超過b公斤的條件下，攜帶哪些物品，可使總價值最大．

首先引進變量xi規(guī)定

問題的數學形式可寫成

求

(m為正整數)，

滿足

這是一個0—1規(guī)劃問題．

解0—1規(guī)劃問題的一種明顯方法就是窮舉法（顯枚舉法），即檢查變量取值0或1的每一種組合，看其是否滿足給定的約束條件，然后再比較目標函數值的大小，從而求得最優(yōu)解．如果變量個數是n，就需要檢查2n個所有可能的變量組合．對于變量個數n相當大時，利用窮舉法幾乎是不可能的．因此希望設計一種方法，使在達到最優(yōu)解之前，只須檢查所有可能的變量組合的一部分即可．這就是隱枚舉法（或部分枚舉法）．下面舉例說明．

這是一個0—1規(guī)劃問題．

例

求解

解

因為變量x1,x2,x3只取0或1，所以利用二進制加法運算，可得這三個變量的所有可能的組合數組．即（0，0，0），（0，0，1），（0，1，0），（0，l，1），…，（l，1，1）．從中任選一組（一般先取較小的），如：(x1,x2,x3)=（0，0，1），代入目標函數，得S=3．由于我們求的是最大化問題，當然希望S≥3（3是S的下界）．于是，很自然地可增加一個約束條件：4x1-2x2+3x33,

(0)這個條件稱為過濾性約束條件．這樣原問題的約束條件就變成4個．若用顯枚舉法，3個變量共有23=8個解，原來3個約束條件，共需24次運算．現在增加了過濾性條件(0)，似乎要增加運算次數，但按下述方法進行，就可減少運算次數．具體計算見表3-7．表3-7x1

x2

x3

目標函數值

是否滿足約束

最優(yōu)值下界

S（0）是否下界

(1)(2)(3)0000

0013

3010-2

0111

1004

41017

1102

1115

于是得最優(yōu)解：(x1,x2,x3)=（1，0，0）且maxS=4．注意：（1）表中第2列對應著變量X的目標函數值，若以后的約束條件均被滿足，則應及時改變最優(yōu)值的下界，即過濾性條件，然后繼續(xù)做下去．當某檢驗條件通不過時，即畫“”，以后各列都不必計算．在變量X的所有可能的值都檢驗過之后，計算表就算完成．表中最后一列最下面那個下界，就是所求的最優(yōu)值，它所在行對應的X就是所求的最優(yōu)解．(2)為了簡化計算，常把目標函數的系數按遞增（不減）的次序排列．如在上例中，改寫S為：S=4x1-2x2+3x3=-2x2+3x3+4x1，因為系數-2，3，4遞增，變量(x2,x3,x1)也按下述順序取值：（0，0，0），（0，0，1），（0，1，0）…（1，1，1）．這樣，將會使目標函數的最優(yōu)值較早出現，使以后的計算量得到減少．按此法計算例1，其過程見表3-8．表3-8x2x

3x1

目標函數值

是否滿足約束

最優(yōu)值下界

S（0）

是否下界

(1)(2)(3)0000

00014

40103

0117

100-2

1012

1101

1115

顯然，最優(yōu)解仍是x1=1，

x2=x3=0.且S=4，但計算已得到簡化．例題：《公司財務學》齊寅峰，經濟科學出版社某公司2000年有六個項目通過了單個項目評估，都是大型項目，投資分兩期進行，按照公司長期財務計劃，這兩期的總投資限額分別為8.5億和6億，每個項目的凈現值已估算完畢（折現率不盡相同）。另外，由于技術工藝和市場原因，項目ABC為三擇一項目，項目B為D的預備項目，項目EF為互斥項目，問該公司如何選擇一是投資總凈現值最大化？項目投資額凈現值2000年2001年A100100150B18050100C200150260D150180200E160120130F500100280資本限額850600建模某城市消防總部將全市劃分為11個防火區(qū)，設有四個消防站。已知消防站代號及可以覆蓋的放火區(qū)如表所示。問為保證全市消防的前提下，是否可以減少消防站的個數？消防站覆蓋的消防區(qū)A1、2、3、4、7、8B1、2、8、9C4、5、6、11D6、7、8、9、10、11§3.4指

派

問

題

1．指派問題的數學模型所謂指派問題是指這樣一類問題：有n項任務，恰好有n個人可以分別去完成其中任何一項，但由于任務的性質和每個人的技術專長各不相同，因此，各個人去完成各項不同任務的效率也不一樣．于是提出如下問題：應當分派哪個人去完成哪項任務，才能使總的效率最高？先看一個具體例子．

例1某公司有Bl，B2，B3，B4四項不同任務，恰有Al，A2，A3，A4四個人去完成各項不同的任務．由于任務性質及每人的技術水平不同，他們完成各項任務所需時間如表，問怎樣才能使這項工程花費的總時數最少？

時間任務B1B2B3B4人員A1215134A21041415A39141613A478119解

設

其中i，j=1，2，3，4．

按照每個人僅承擔一項任務的要求，則有約束：

再依每項任務只能有一人承擔的要求，則有約束：

問題的目標函數是：

一般地，指派問題的數學模型為：

其中，目標函數的系數

通常，把這些數寫成矩陣形式：

C稱為系數矩陣或效益矩陣．滿足約束條件的可行解也可寫成矩陣形式，稱為解矩陣．如例1的系數矩陣和解矩陣分別為：

解矩陣中各行各列的元素之和都是12．匈牙利法

基本思想是在效益矩陣的任何行或列中，加上或減去一個常數，使得在不同行不同列中至少有一個為零的元素，從而得到與這些零元素相對應的一個最優(yōu)分配方案．該方法的理論基礎是下述定理．定理如果從效益矩陣C=（cij）的每一行元素中分別減去（或加上）一個常數ai，從每一列分別減去（或加上）一個常數bj，得到一個新的效益矩陣C’=（cij’），其中每個元素cij’=cij-ai-bj

，則以（cij’）為系數矩陣的最優(yōu)解與以（cij）為系數矩陣的最優(yōu)解相同．

證

事實上，新的目標函數為

上式表明，新目標函數等于原目標函數減去（或加上）兩個常數．因此，當新目標函數達到最小值時，相應地原目標函數也達到最小值．

下面用例1來具體說明匈牙利法的計算步驟．

第一步

從效益矩陣的每行減去各行中的最小元素，再從每列中減去各列的最小元素，得

這里（cij’）稱為初始縮減矩陣．把各行各列所減去的數之總和稱為縮減量，本題的縮減量為

S=2＋4＋9＋7＋4＋2=28．注意：如果某行（或列）有零元素，就不必再減．

第二步

試制一個指派方案，以尋求最優(yōu)解．經過第一步變換后，系數矩陣中每行每列都已有了零元素，但需要找出n個獨立的零元素，即找出n個位于不同行不同列的零元素來．若能找出，則以這些零元素對應的元素為1，其余為零，便得到一個解矩陣，從而得到最優(yōu)解．尋找n個獨立零元素的方法如下：（1）從第一行開始檢查．若某一行只有一個零元素，就對這個零元素打上號，然后劃去所在列的其他零元素，記作．

（2）再從第一列開始檢查，若某列只有一個零元素，就對這個零元素打上號，（不考慮已劃去的零元素）．然后再劃去所在行的其他零元素，記作．（3）重（l），（2）兩步，直到所有零元素打上號或被劃去．

現用例1得到的（cij’）矩陣按上述步驟運算，最后得：

從而得最優(yōu)解為

這表示A1去完成B4，A2去完成B2，A3去完成B1，A4去完成B3所需總時間最少，這時，minS=c14+c22+c31+c43=28．

注意：（1）如果在矩陣中能得到位于不同行不同列的n(=4)個，那么就完成了求最優(yōu)解的過程；

（2）如果矩陣中的所有零元素或打上號，或被劃去（），而不是每一行都有打號的零元素，那么解題過程還沒有完成．如下述例2，這時應轉下面第三步．例2求縮減矩陣為（cij’）的分配問題的最優(yōu)解．

第三步

作復蓋所有零元素的最少數量的直線，以確定系數矩陣中最多的獨立元素數．具體方法步驟如下：

（1）對沒有