第三章整數(shù)規(guī)劃運(yùn)籌學(xué)

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

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

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

§3.1分枝定界法

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

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

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

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

第二步

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

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

其中[xj*]表示小于xj*的最大整數(shù)．由此構(gòu)造兩個(gè)約束條件：

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

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

第三步

剪枝．在繼續(xù)分枝的過程中，各分枝的最優(yōu)目標(biāo)函數(shù)值如果有小于S，則稱這個(gè)分枝已被“查清”，將該枝剪掉，不再計(jì)算．因?yàn)樵偎阆氯ゲ粫?huì)得到更好的目標(biāo)函數(shù)值．若有目標(biāo)函數(shù)值大于下界S，且不符合整數(shù)條件，則重復(fù)第二步驟，直到找到S*．

例

求解問題（A）：

解

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

（2）分枝與定界

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

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

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

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

(3)重復(fù)步驟（2），繼續(xù)對(duì)問題（B2）進(jìn)行分解．因?yàn)樵冢˙2）中x1=1.8，對(duì)問題（B2）增加約束條件：x1[1.8]=1和x1[1.8]+1=2,將問題（B2）再分解為兩個(gè)子問題（B3）和（B4）：

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

問題（B4）無可行解，這個(gè)子問題也已查清．因?yàn)樵趩栴}（B3）中有

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

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

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

§3.2割

平

面

法

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

§3.30一1規(guī)劃

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

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

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

問題的數(shù)學(xué)形式可寫成

求

(m為正整數(shù))，

滿足

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

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

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

例

求解

解

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

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

x2

x3

目標(biāo)函數(shù)值

是否滿足約束

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

3x1

目標(biāo)函數(shù)值

是否滿足約束

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

派

問

題

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

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

時(shí)間任務(wù)B1B2B3B4人員A1215134A21041415A39141613A478119解

設(shè)

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

按照每個(gè)人僅承擔(dān)一項(xiàng)任務(wù)的要求，則有約束：

再依每項(xiàng)任務(wù)只能有一人承擔(dān)的要求，則有約束：

問題的目標(biāo)函數(shù)是：

一般地，指派問題的數(shù)學(xué)模型為：

其中，目標(biāo)函數(shù)的系數(shù)

通常，把這些數(shù)寫成矩陣形式：

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

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

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

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

證

事實(shí)上，新的目標(biāo)函數(shù)為

上式表明，新目標(biāo)函數(shù)等于原目標(biāo)函數(shù)減去（或加上）兩個(gè)常數(shù)．因此，當(dāng)新目標(biāo)函數(shù)達(dá)到最小值時(shí)，相應(yīng)地原目標(biāo)函數(shù)也達(dá)到最小值．

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

第一步

從效益矩陣的每行減去各行中的最小元素，再?gòu)拿苛兄袦p去各列的最小元素，得

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

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

第二步

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

（2）再?gòu)牡谝涣虚_始檢查，若某列只有一個(gè)零元素，就對(duì)這個(gè)零元素打上號(hào)，（不考慮已劃去的零元素）．然后再劃去所在行的其他零元素，記作．（3）重（l），（2）兩步，直到所有零元素打上號(hào)或被劃去．

現(xiàn)用例1得到的（cij’）矩陣按上述步驟運(yùn)算，最后得：

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

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

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

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

第三步

作復(fù)蓋所有零元素的最少數(shù)量的直線，以確定系數(shù)矩陣中最多的獨(dú)立元素?cái)?shù)．具體方法步驟如下：

（1）對(duì)沒有