運(yùn)籌學(xué)-4整數(shù)規(guī)劃

引言在線性規(guī)劃問題中，所有的解都假設(shè)為具有連續(xù)型的數(shù)值，即解可以是整數(shù)、分?jǐn)?shù)或帶有小數(shù)點(diǎn)的實(shí)數(shù)。但對(duì)于某些具體的問題，常要求最優(yōu)解是整數(shù)的情形。例如，所求的解是機(jī)器臺(tái)數(shù)，完成工作的人數(shù)或裝貨的車數(shù)等，這時(shí)，分?jǐn)?shù)或小數(shù)的解答就不符合要求。為了滿足整數(shù)解的要求，初看起來，似乎只要把已求得的解經(jīng)過“舍入化整”就可以，但這常常是不可行的。因?yàn)榛蟛灰姷檬强尚薪狻；螂m然是可行解，但不一定是最優(yōu)解。因此，對(duì)求最優(yōu)整數(shù)解的問題，有必要另行研究。本章內(nèi)容分支定界法0－1型整數(shù)規(guī)劃3整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)124指派問題第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型

及解的特點(diǎn)一、整數(shù)規(guī)劃的數(shù)學(xué)模型的一般形式依照決策變量取整要求的不同，整數(shù)規(guī)劃可分為純整數(shù)規(guī)劃（全整數(shù)規(guī)劃）、混合整數(shù)規(guī)劃、0－1整數(shù)規(guī)劃。

本章僅討論整數(shù)線性規(guī)劃。

純整數(shù)規(guī)劃：所有決策變量要求取非負(fù)整數(shù)（這時(shí)引進(jìn)的松弛變量和剩余變量可以不要求取整數(shù)）。

混合整數(shù)規(guī)劃：只有一部分的決策變量要求取非負(fù)整數(shù)，另一部分可以取非負(fù)實(shí)數(shù)。

0－1整數(shù)規(guī)劃：所有決策變量只能取0或1兩個(gè)整數(shù)。整數(shù)規(guī)劃問題類型二、整數(shù)規(guī)劃的例子

例2

某服務(wù)部門各時(shí)段（每2h為一時(shí)段）需要的服務(wù)員人數(shù)見下表。按規(guī)定，服務(wù)員連續(xù)工作8h為一班?，F(xiàn)要求安排服務(wù)員的工作時(shí)間，使服務(wù)部門服務(wù)員總數(shù)最少。時(shí)段12345678服務(wù)員最少數(shù)量10891113853

解：設(shè)在j時(shí)段開始上班的服務(wù)員人數(shù)為xj。由于第j時(shí)段開始時(shí)上班的服務(wù)員將在第（j+3）時(shí)段結(jié)束下班，所以決策變量只需考慮x1,x2,x3,x4,x5。

問題的數(shù)學(xué)模型為：純整數(shù)規(guī)劃問題40－1整數(shù)規(guī)劃問題三、整數(shù)規(guī)劃解特點(diǎn)整數(shù)線性規(guī)劃及其松馳問題，從解的特點(diǎn)來看，二者之間既有密切的聯(lián)系，又有本質(zhì)的區(qū)別。整數(shù)規(guī)劃放松的線性規(guī)劃∩≤松弛問題的最優(yōu)值是原整數(shù)規(guī)劃的目標(biāo)函數(shù)值的上界整數(shù)規(guī)劃解的特點(diǎn)最優(yōu)解不一定在頂點(diǎn)上達(dá)到最優(yōu)解不一定是放松問題最優(yōu)解的鄰近整數(shù)解整數(shù)可行解遠(yuǎn)多于頂點(diǎn)，枚舉法不可取注釋從數(shù)學(xué)模型上看整數(shù)規(guī)劃似乎是線性規(guī)劃的一種特殊形式，求解只需在線性規(guī)劃的基礎(chǔ)上，通過舍入取整，尋求滿足整數(shù)要求的解即可。但實(shí)際上兩者卻有很大的不同，通過舍入得到的解（整數(shù)）也不一定就是最優(yōu)解，有時(shí)甚至不能保證所得到的解是整數(shù)可行解。整數(shù)規(guī)劃=相關(guān)的線性規(guī)劃+整數(shù)約束整數(shù)規(guī)劃是約束得更緊的問題,它的可行域是其相關(guān)線性規(guī)劃問題可行域的一個(gè)子集；整數(shù)解的數(shù)目遠(yuǎn)少于線性規(guī)劃的解，只要可行域有界，整數(shù)解的數(shù)目有限；整數(shù)規(guī)劃的求解難度遠(yuǎn)大于線性規(guī)劃?？偨Y(jié)：整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系例：設(shè)整數(shù)規(guī)劃問題如下首先不考慮整數(shù)約束，得到線性規(guī)劃問題。用圖解法求出最優(yōu)解x1＝3/2,x2=10/3且有Z=29/6現(xiàn)求整數(shù)解（最優(yōu)解）：如用“舍入取整法”可得到4個(gè)點(diǎn)即(1，3)(2，3)(1，4)(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。x1x2⑴⑵33(3/2,10/3)

因此，可將集合內(nèi)的整數(shù)點(diǎn)一一找出，其最大目標(biāo)函數(shù)的值為最優(yōu)解，此法為完全枚舉法。其中（2，2）（3，1）點(diǎn)為最大值，Z=4。按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問題的可行解集是一個(gè)有限集，如圖所示。x1x2⑴⑵33(3/2,10/3)求解整數(shù)規(guī)劃方法窮舉法：方法簡(jiǎn)單，只可解小問題，計(jì)算量很大；對(duì)0-1整數(shù)規(guī)劃，計(jì)算量為2n，按指數(shù)增長(zhǎng)；四舍五入法：解的質(zhì)量差，有時(shí)無法得到可行解分枝定界:

計(jì)算效率高,應(yīng)用廣泛;割平面法:

有理論意義,但計(jì)算效率較低；啟發(fā)算法:

效率高,但不能保證找到最優(yōu)解,可解大規(guī)模問題。第二節(jié)分支定界法一、基本思想

分支定界法可用于解純整數(shù)或混合的整數(shù)線性規(guī)劃問題。由于此方法靈活且便于用計(jì)算機(jī)求解，所以現(xiàn)在它已是解整數(shù)線性規(guī)劃的重要方法。

設(shè)有最大化的整數(shù)線性規(guī)劃問題A，與它相應(yīng)的線性規(guī)劃為問題B，從解問題B開始，若其最優(yōu)解不符合A的整數(shù)條件，那么B的最優(yōu)目標(biāo)函數(shù)必是A的最優(yōu)目標(biāo)函數(shù)z*的上界；而A的任意可行解的目標(biāo)函數(shù)值將是z*的一個(gè)下界。分支定界法就是將B的可行域分成子區(qū)域(稱為分支)的方法，不斷降低上界，提高下界，最后使得上下界相等，即求得最優(yōu)解z*。定界基本思想檢查所有分支的解及目標(biāo)函數(shù)值，若某分支的解是整數(shù)并且目標(biāo)函數(shù)值大于（max)其他分支的目標(biāo)函數(shù)值，則將其他減去不再計(jì)算；若還存在非整數(shù)解并且目標(biāo)函數(shù)值大于（max)整數(shù)解的目標(biāo)值，需要繼續(xù)分支，再檢查，直到得到最優(yōu)解。隱枚舉法求解放松問題最優(yōu)解為整數(shù)最優(yōu)值比界差最優(yōu)解為非整數(shù)

最優(yōu)值比界好分支邊界分支定界舍棄二、具體解題步驟1.先不考慮整數(shù)約束，解(IP)的松弛問題(LP)，可能得到以下情況之一：

⑴.若(LP)沒有可行解，則(IP)也沒有可行解，停止計(jì)算。

⑵.若(LP)有最優(yōu)解，并符合(IP)的整數(shù)條件，則(LP)的最優(yōu)解即為(IP)的最優(yōu)解，停止計(jì)算。

⑶.若(LP)有最優(yōu)解，但不符合(IP)的整數(shù)條件，轉(zhuǎn)入下一步。為討論方便，設(shè)(LP)的最優(yōu)解為：若(LP)的最優(yōu)解不符合整數(shù)要求，假設(shè)xi=

（不為整數(shù)），以[]表示不超過的最大整數(shù)。構(gòu)造兩個(gè)約束條件

xr≤[]

和xr≥[]

＋1將這兩個(gè)約束條件分別加入問題(IP)，形成兩個(gè)子問題(IP1)和(IP2)，再解這兩個(gè)問題的松弛問題(LP1)和(LP2),從而形成兩個(gè)分支。2.分支3.定界（修改上下界）

定界：是在分支過程中，若某個(gè)后繼問題恰巧獲得整數(shù)規(guī)劃問題的一個(gè)可行解，那么，它的目標(biāo)函數(shù)值就是一個(gè)“界限”，可作為衡量處理其他分支的一個(gè)依據(jù)。按照以下兩點(diǎn)規(guī)則進(jìn)行：⑴.在各分枝問題中，找出目標(biāo)函數(shù)值最大者作為新的上界；⑵.從已符合整數(shù)條件的分枝中，找出目標(biāo)函數(shù)值最大者作為新的下界。4.比較與剪支各分枝的目標(biāo)函數(shù)值中，若有小于下界者，則剪掉此分支，表明此子問題已經(jīng)探清，不必再分支了;否則繼續(xù)分枝。如此反復(fù)進(jìn)行，直到得到下界等于上界為止，即得最優(yōu)解X*

。補(bǔ)充例子：用分枝定界法求解整數(shù)規(guī)劃問題（用圖解法計(jì)算）記為（IP）解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題記為（LP）用圖解法求（LP）的最優(yōu)解，如圖所示。x1x2⑴⑵33(18/11,40/11)⑶對(duì)于x1＝18/11≈1.64，取值x1≤1，x1≥2對(duì)于x2=40/11≈3.64，取值x2

≤3，x2

≥4先將（LP）劃分為（LP1）和（LP2）,取x1≤1,x1≥2

x1＝18/11,x2=40/11Z(0)=－218/11≈(－19.8)即Z也是（IP）最小值的下限。12有下式：現(xiàn)在只要求出（LP1）和（LP2）的最優(yōu)解即可。

先求（LP1）,如圖所示。此時(shí)B

在點(diǎn)取得最優(yōu)解。x1＝1,x2=3,Z(1)＝－16找到整數(shù)解，問題已探明，此枝停止計(jì)算。同理求（LP2）

,如圖所示。在C

點(diǎn)取得最優(yōu)解。即x1＝2,x2=10/3,Z(2)

＝－56/3≈－18.7∵Z2<Z1＝－16∴原問題有比（－16）更小的最優(yōu)解，但x2不是整數(shù)，故利用

3≥10/3≥4

加入條件。x1x2⑴⑵33(18/11,40/11)⑶11BAC加入條件：x2≤3,x2≥4有下式：只要求出（LP3）和（LP4）的最優(yōu)解即可。x1x2⑴⑵33(18/11,40/11)⑶11BAC先求（LP3）,如圖所示。此時(shí)D在點(diǎn)取得最優(yōu)解。即x1＝12/5≈2.4,x2=3,Z(3)＝-87/5≈-17.4>Z≈-19.8但x1＝12/5不是整數(shù)，可繼續(xù)分枝。即3≤x1≤2。D求（LP4），如圖所示。無可行解，不再分枝。在（LP3）的基礎(chǔ)上繼續(xù)分枝。加入條件3≤x1≤2有下式：只要求出（LP5）和（LP6）的最優(yōu)解即可。x1x2⑴⑵33(18/11,40/11)⑶11BACD先求（LP5）,如圖所示。此時(shí)E

在點(diǎn)取得最優(yōu)解。即x1＝2,x2=3,Z(5)＝－17找到整數(shù)解，問題已探明，此支停止計(jì)算。E求（LP6），如圖所示。此時(shí)F在點(diǎn)取得最優(yōu)解。x1＝3,x2=2.5,Z(6)＝－31/2≈－15.5>Z(5)

F如對(duì)Z(6)

繼續(xù)分解，其最小值也不會(huì)低于－15.5

，問題探明,剪支。至此，原問題（IP）的最優(yōu)解為：

x1=2，

x2=3,

Z*=Z(5)

＝－17以上的求解過程可以用一個(gè)樹形圖表示如右：例（p132)用分枝定界法求解整數(shù)規(guī)劃問題LP1x1=1,x2=7/3Z(1)

＝10/3LPx1=3/2,x2=10/3Z(0)

＝29/6LP2x1=2,x2=23/9Z(2)

＝41/9x1≤1x1≥2LP5x1=1,x2=2Z(5)

＝3LP6無可行解＃＃x2≤2x2≥3LP3x1=33/14,x2=2Z(3)

＝61/14LP4無可行解x2≤2x2≥3＃LP7x1=2,x2=2Z(7)

＝4LP8x1=3,x2=1Z(8)

＝4x1≤2x1≥3＃＃LP1x1=1,x2=7/3Z(1)

＝10/3LPx1=2/3,x2=10/3Z(0)

＝29/6LP2x1=2,x2=23/9Z(2)

＝41/9LP3x1=33/14,x2=2Z(3)

＝61/14LP4無可行解LP7x1=2,x2=2Z(7)

＝4LP8x1=3,x2=1Z(8)

＝4x1≤1x1≥2x2≤2x2≥3x1≤2x1≥3＃＃＃＃分枝定界法計(jì)算過程總結(jié)：上界x1≤[x*01]x1≥[x*01]+1用分枝定界法求解下題【解】先求對(duì)應(yīng)的松弛問題（記為L(zhǎng)P0）：用圖解法得到最優(yōu)解X＝（3.57,7.14）,Z0=35.7,如下圖所示。課后練習(xí)：分支定界法8.3310松弛問題LP0的最優(yōu)解X=(3.57,7.14),Z0=35.7x1x2oABC101010x1x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.5①②1010x1x2oABCLP1LP334LP3:X=(4.33,6),Z3=35.336①②LP1:X=(3,7.6),Z1=34.81010x1x2oACLP1346①②LP4:X=(4,6),Z4=34LP5:X=(5,5),Z5=355LP1:X=(3,7.6),Z1=34.8LP3LP5

盡管LP1的解中x1不為整數(shù)，但Z5>Z因此LP5的最優(yōu)解就是原整數(shù)規(guī)劃的最優(yōu)解。上述分枝過程可用下圖表示LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x1≤3x1≥4LP3:X=(4.33,6)Z3=35.33x2≤6LP4:X=(4,6)Z4=34LP5:X=(5,5)Z5=35x1≤4x1≥5無可行解x2≥7從分支定界法的原理和步驟可知，它也適用于求解混合整數(shù)規(guī)劃問題。補(bǔ)充說明：第三節(jié)0－1型整數(shù)規(guī)劃0-1變量作為邏輯變量，可以數(shù)量化地描述開與關(guān)、取與棄、有與無等邏輯現(xiàn)象。一些其它非0-1規(guī)劃可以化為0-1規(guī)劃來處理。0－1整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，這時(shí)的決策變量xi

只取兩個(gè)值0或1。一、0－1變量及其應(yīng)用邏輯變量邏輯（0-1）變量在建立數(shù)學(xué)模型中的作用（1）m個(gè)約束條件中只有k

個(gè)起作用設(shè)

m

個(gè)約束條件可以表示為：定義邏輯變量又設(shè)

M

為任意大的正數(shù)，則約束條件可以改寫為：定義邏輯變量：此時(shí)約束條件可以改寫為：（2）約束條件的右端項(xiàng)可能是r個(gè)值中的某一個(gè)即（3）兩組條件滿足其中一組若x1≤4，則x2≥1（第一組條件）；否則當(dāng)x1>4時(shí)，x2≤3（第二組條件）.定義邏輯變量：又設(shè)M

為任意大正數(shù)，則問題可表達(dá)為：需注意，當(dāng)約束為大于時(shí)，右端項(xiàng)中用減號(hào)。10做第i件事不做第i件事n件事中必須做k件并只做k件事n件事中最多做k件事n件事中至少做k件事做第i件事的充要條件是做第j件事做第i件事的充要條件是不做第j件事只在做了第i件事前提下才考慮是否做第j件事

0-1規(guī)劃的實(shí)例－例1某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個(gè)位置（點(diǎn)）A1,A2,…,A7

可供選擇。規(guī)定

在東區(qū)：由A1,A2,A3三個(gè)點(diǎn)中至多選兩個(gè)；

在西區(qū)：由A4,A5兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)：由A6,A7兩個(gè)點(diǎn)中至少選一個(gè)。

如選用Ai點(diǎn)，設(shè)備投資估計(jì)為bi元，每年可獲利潤(rùn)估計(jì)為ci元，但投資總額不能超過B元。問應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤(rùn)為最大？解：解題時(shí)先引入0－1變量Xi(i=1,2,…,7)令

數(shù)學(xué)模型為：該公司只有600萬資金可用于投資，由于技術(shù)上的原因，投資受到以下約束：

1、在項(xiàng)目1、2和3中必須有一項(xiàng)被選中

2、項(xiàng)目3和4只能選中一項(xiàng)且必須選中一項(xiàng)；

3、項(xiàng)目5被選中的前提是項(xiàng)目1被選中;如何在滿足上述條件下選擇一個(gè)最好的投資方案，使投資收益最大？例2（投資問題）華美公司有5個(gè)項(xiàng)目被列入投資計(jì)劃，每個(gè)項(xiàng)目的投資額和期望的投資收益見下表：項(xiàng)目投資額（萬元）投資收益（萬元）12101502300210310060413080526018010投資第i個(gè)項(xiàng)目不投資第i個(gè)項(xiàng)目Z表示投資效益投資項(xiàng)目模型：試引入0－1變量將下列各題分別表達(dá)為一般線性約束條件（1）x1+x2≤6或4x1+6x2≥10或2x1+4x2≤20（2）若x1≤5，則x2≥0，否則x2≤8（3）x2取值0，1，3，5，7【解】（1）3個(gè)約束只有1個(gè)起作用

0-1規(guī)劃的實(shí)例－例3（3）右端常數(shù)是5個(gè)值中的1個(gè)（2）兩組約束只有一組起作用例4（布點(diǎn)問題）某城市共有6個(gè)區(qū)，每個(gè)區(qū)都可以建消防站。市政府希望設(shè)置的消防站最少，但必須滿足在城市任何地區(qū)發(fā)生火火警時(shí)，消防車要在15分鐘內(nèi)趕到現(xiàn)場(chǎng)。據(jù)實(shí)地測(cè)定，各區(qū)之間消防車行駛的時(shí)間見右表。地區(qū)123456101016282720210024321710316240122721428321201525527172715014620102125140

請(qǐng)為該市制定一個(gè)最節(jié)省的計(jì)劃在第i個(gè)地區(qū)建站Z表示全區(qū)消防站總數(shù)不在第i個(gè)地區(qū)建站i=1,2,…,6布點(diǎn)問題模型：例5.固定費(fèi)用問題（FixedCostProblem）

在討論線性規(guī)劃時(shí)，有些問題是要求使成本為最小。那時(shí)總設(shè)固定成本為常數(shù)，并在線性規(guī)劃的模型中不必明顯列出。但有些固定費(fèi)用（固定成本）的問題不能用一般線性規(guī)劃來描述，但可改變?yōu)榛旌险麛?shù)規(guī)劃來解決，見下例。

有三種資源被用于生產(chǎn)三種產(chǎn)品，資源約束、產(chǎn)品單件可變費(fèi)用及售價(jià)、資源單耗量及組織三種產(chǎn)品生產(chǎn)的固定費(fèi)用見下表，要求制定一個(gè)生產(chǎn)計(jì)劃，使總收益最大。IIIII資源量A248500B234300C123100單件可變費(fèi)用456固定費(fèi)用100150200單件售價(jià)81012解：總收益＝銷售輸入－（固定費(fèi)用＋可變費(fèi)用）建模的困難：事先不能確切知道某種產(chǎn)品是否生產(chǎn)，因而不能確定相應(yīng)的固定費(fèi)用是否發(fā)生？其中Mj為對(duì)應(yīng)xj的某個(gè)上界;這是處理xj與yj一對(duì)變量之間邏輯關(guān)系的特殊約束當(dāng)xj>0時(shí)，yj＝1，當(dāng)xj＝0時(shí),為使得Z具有最大值，有yj＝0。解0-1型整數(shù)規(guī)劃最容易想到的方法，和一般整數(shù)規(guī)劃的情形一樣，就是窮舉法，即檢查變量取值為0或1的每一種組合，比較目標(biāo)函數(shù)值以求得最優(yōu)解，這就需要檢查變量取值的2n個(gè)組合。對(duì)于變量個(gè)數(shù)n較大（例如n>10），這幾乎是不可能的。

因此常設(shè)計(jì)一些方法，只檢查變量取值的組合的一部分，就能求到問題的最優(yōu)解。這樣的方法稱為隱枚舉法（ImplicitEnumeration）。?0－1型整數(shù)規(guī)劃的求解二、0－1型整數(shù)規(guī)劃的解法在2n個(gè)可能的變量組合中，往往只有一部分是可行解。只要發(fā)現(xiàn)某個(gè)變量組合不滿足其中一個(gè)約束條件時(shí)，就不必再去檢驗(yàn)其他約束條件是否可行。對(duì)于可行解，其目標(biāo)函數(shù)值也有優(yōu)劣之分，若已發(fā)現(xiàn)一個(gè)可行解，則根據(jù)它的目標(biāo)函數(shù)值可以產(chǎn)生一個(gè)“過濾條件”。對(duì)于目標(biāo)函數(shù)值比它差的變量組合就不必再去檢驗(yàn)它的可行性，在以后的求解過程中，每當(dāng)發(fā)現(xiàn)比原來更好的可行解，則以此替換原來的過濾條件。例、求解下列0－1規(guī)劃問題

解：完全枚舉法由上表可知，問題的最優(yōu)解為X*=(x1=1x2=0x3=1)由上表可知：x1=0x2=0x3=1

是一個(gè)可行解，為盡快找到最優(yōu)解，可將3

x1－2x2＋5x3≥5作為一個(gè)約束，凡是目標(biāo)函數(shù)值小于5的組合不必討論，如下表。隱枚舉法Z過濾條件Z≥Z≥6改進(jìn)的算法：為減少運(yùn)算量，常按目標(biāo)函數(shù)中各變量系數(shù)的大小順序重新排列各變量，以使最優(yōu)解有可能較早出現(xiàn)。對(duì)于最大化問題，可按由小到大的順序排列；對(duì)于最小化問題，則相反。72

0-1規(guī)劃的隱枚舉法是一種特殊的分枝定界法，其基本思想是利用變量只能為0或1兩個(gè)值的特性，進(jìn)行分枝定界，以減少枚舉而達(dá)到求出最優(yōu)解之目的。該法適用于任何0-1規(guī)劃問題的求解，包括指派問題。了解內(nèi)容：0-1規(guī)劃的隱枚舉法

隱枚舉法首先要將問題化為規(guī)范形。（1）0-1規(guī)劃的規(guī)范形為73（2）化規(guī)范形的方法：1）如果目標(biāo)函數(shù)為求極小值，則對(duì)目標(biāo)函數(shù)兩邊乘以-1，化為求極大值；2）若目標(biāo)函數(shù)中某變量xj的系數(shù)cj>0，則令xj=1-yj3）如果約束條件是“”形，則可兩邊乘-1，改為“”形；4）若某個(gè)約束條件為“=”形，則化為兩個(gè)“”的不等式,如74例、用隱枚舉法求解下列0-1規(guī)劃解：令x1=1-y1,x3=1-y3,x5=1-y5,x2=y2,x4=y4化為規(guī)范形得：75其求解過程如下圖所示：y4=0y5=101234567810911121314Z=11y3=1y3=0y4=1y5=1y5=0y2=1y2=0y4=0y4=1y5=0y1=0y1=1可行解z=3可行解z=1可行解z=2不可行子域不可行子域可行解z=6可行解z=2不可行子域由此可知，最優(yōu)解為x3=x4=x5=1,x1=x2=0,maxz=6用隱枚舉法求解下列問題【解】（1）不難看出，當(dāng)所有變量等于0或1的任意組合時(shí)，第一個(gè)約束滿足，說明第一個(gè)約束沒有約束力，是多余的，從約束條件中去掉。還能通過觀察得到X0＝(1，0，0，1)是一個(gè)可行解，目標(biāo)值Z0＝11是該問題的下界，構(gòu)造一個(gè)約束：

，原問題變?yōu)檎n后練習(xí)：0－1規(guī)劃求解(2)列出變量取值0和1的組合，共24＝16個(gè)，分別代入約束條件判斷是否可行。首先判斷式（3.9）是否滿足，如果滿足，接下來判斷其它約束，否則認(rèn)為不可行，計(jì)算過程見下表所示。jXj3.9a3.9b3.9c3.9dZjjXj3.9a3.9b3.9c3.9dZj1(0,0,0,0)×

9(1,0,0,0)×

2(0,0,0,1)×

10(1,0,0,1)√√√√113(0,0,1,0)×

11(1,0,1,0)×

4(0,0,1,1)×

12(1,0,1,1)√√√√145(0,1,0,0)×

13(1,1,0,0)×

6(0,1,0,1)×

14(1,1,0,1)√√√√137(0,1,1,0)×

15(1,1,1,0)√×

8(0,1,1,1)×

16(1,1,1,1)√√√×

(3)由上表知，問題的最優(yōu)解：X＝（1，0，1，1），最優(yōu)值Z＝14第五節(jié)指派問題如何分配合適的事情給合適的人，是領(lǐng)導(dǎo)才能有的事情沒有人做有的人沒有事情做如何人盡其才？？？原理：從人的角度思考……..考慮人最適合的工作從工作的角度思考…….考慮工作最適合的人一、指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型（一）、指派問題的數(shù)學(xué)模型設(shè)n個(gè)人被分配去做n件工作，規(guī)定每個(gè)人只做一件工作，每件工作只有一個(gè)人去做。已知第i個(gè)人去做第j件工作的的效率（時(shí)間或費(fèi)用）為Cij(i=1.2…n;j=1.2…n)并假設(shè)Cij≥0。問應(yīng)如何分配才能使總效率（或時(shí)間、費(fèi)用最少）最高？

被指派的人數(shù)與任務(wù)的數(shù)目相等。每個(gè)被指派的人員只完成一項(xiàng)任務(wù)，而且每項(xiàng)任務(wù)必有一人去完成。第i個(gè)被指派的人去完成第j項(xiàng)任務(wù)的費(fèi)為cij

。指派問題的要解決的問題是：如何指派任務(wù)，可以使總費(fèi)用最少？

在指派問題中假設(shè):

設(shè)決策變量

1分配第i個(gè)人去做第j件工作

xij=0相反(I,j=1.2.…n)其數(shù)學(xué)模型為：表明每件事必有且只有一個(gè)人去做表明每個(gè)人必做且只做一件事例：紅旗超市計(jì)劃開辦5家新商店。為了盡早建成營(yíng)業(yè)，商業(yè)公司決定由5家建筑公司分別承建。請(qǐng)問應(yīng)當(dāng)對(duì)5家建筑公司怎樣分配建造任務(wù)，才能使總的建造費(fèi)用最少？B1B2B3B4B5

A14871512A279171410A3691287

A46714610

A56912106已知數(shù)據(jù)應(yīng)為什么？建筑公司Ai(i＝1,2,…,5)對(duì)新商店Bj(j=1,2,…,5)的建造費(fèi)用的報(bào)價(jià)（萬元）為cij(I,j=1,2,…,5),解：

設(shè)決策變量

1當(dāng)Ai承建Bj時(shí)

xij=0當(dāng)Ai不承建Bj時(shí)(i,j=1.2.…n)商店公司B1B2B3B4B5任務(wù)A1（4）（8）（7）（15）（12）1A2（7）(9)(17)(14)(10)1A3(6)(9)(12)(8)(7)1A4(6)(7)(14)(6)(10)1A5(6)(9)(12)(10)(6)1所選的公司數(shù)111115例：有一份中文說明書，需譯成英、日、德、俄四種文字（記作E、J、G、R）?，F(xiàn)有甲、乙、丙、丁四人，他們將說明書翻譯成不同文字所需要的時(shí)間如表一所示。問應(yīng)指派何人去完成哪一項(xiàng)工作，使所需總時(shí)間最少？效率矩陣

任務(wù)人員ABCD甲67112乙4598丙31104丁5982二、指派問題的解法——匈牙利解法問題是：把這n個(gè)1放到X的個(gè)位置的什么地方可使耗費(fèi)的總資源最少？（解最優(yōu)）匈牙利解法成立的基礎(chǔ)【定理1】如果從分配問題效率矩陣[cij]的每一行元素中分別減去（或加上）一個(gè)常數(shù)ui（被稱為該行的位勢(shì)），從每一列分別減去（或加上）一個(gè)常數(shù)vj（稱為該列的位勢(shì)），得到一個(gè)新的效率矩陣[bij]，其中bij=cij－ui－vj,則[bij]的最優(yōu)解等價(jià)于[cij]的最優(yōu)解，這里cij、bij均非負(fù)．【證】?jī)蓚€(gè)目標(biāo)函數(shù)相差一個(gè)常數(shù)u+v,約束條件不變,因此最優(yōu)解不變。原理：對(duì)C的行和列減去某個(gè)常數(shù)，將C化的盡可能簡(jiǎn)單，簡(jiǎn)單到可一眼看出該問題的最優(yōu)解當(dāng)將效率矩陣的每一行都減去各行的最小元素，將所得的矩陣的每一列在減去當(dāng)前列中最小元素，則最后得到新效率矩陣中必然出現(xiàn)一些零元素。設(shè)=0，從第i行來看，它表示第i個(gè)人去干第j項(xiàng)工作效率（相對(duì)）最好。而從第j列來看，這個(gè)0表示第j項(xiàng)工作以第i人來干效率(相對(duì))最高。也是一個(gè)獨(dú)立零元素組。不是一個(gè)獨(dú)立零元素組。問題是：能否找到位于不同行、不同列的n個(gè)0元素？定義在效率矩陣C中，有一組處于不同行、不同列的零元素，稱為獨(dú)立零元素組，此時(shí)其中每個(gè)元素稱為獨(dú)立零元素。例已知?jiǎng)t是一個(gè)獨(dú)立零元素組，但有的效率矩陣獨(dú)立零元素的個(gè)數(shù)不到n,很難找到最優(yōu)指派方案。已知效率矩陣怎么辦？【定理2】若矩陣A的元素可分成“0”與非“0”兩部分，則覆蓋“0”元素的最少直線數(shù)等于位于不同行不同列的“0”元素（稱為獨(dú)立0元素）的最大個(gè)數(shù)．如果最少直線數(shù)等于m，則存在m個(gè)獨(dú)立的“0”元素，令這些零元素對(duì)應(yīng)的xij等于1，其余變量等于0，這時(shí)目標(biāo)函數(shù)值為0，得到最優(yōu)解．匈牙利解法的步驟

第一步：變換指派問題的系數(shù)矩陣（cij）為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，具體進(jìn)行兩步操作：

(1)從（cij）的每行元素都減去該行的最小元素；

2497得到的0表示：這個(gè)0所在的行對(duì)應(yīng)的人最適合的工作是這個(gè)0所在的列對(duì)應(yīng)的事這一列有三個(gè)0，表示這一列的事有三個(gè)人適合作(2)再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。42第二步：試分派n較小時(shí)，可用觀察法、試探法找n個(gè)獨(dú)立元素，n較大時(shí)，用下面方法：(1)從只有一個(gè)0元素的行(列)開始，對(duì)0元素加框，化去0所在列（行)的其它0元素，記作×(2)反復(fù)進(jìn)行(1)，直到不再有0元素可圈和劃去。(3)當(dāng)同行(列)有兩個(gè)或兩個(gè)以上0元素時(shí)，試探法(4)若加框0元素的數(shù)目m=n，已得最優(yōu)解，即令這些加框0元素對(duì)應(yīng)xij=1,其它0元素xij=0◎?◎??◎◎這時(shí)已經(jīng)找到了4個(gè)位于不同行不同列上的0元素，所以，該問題的最優(yōu)解矩陣是：3、以最少的直線劃去所有0元素n較小時(shí)，可用觀察法，n較大時(shí)，用下面方法(1)對(duì)沒有加框的0所在的行打√(2)對(duì)已打√的行中所有含0元素列打√(3)再對(duì)打有√的列中含框的0元素行打√(4)重復(fù)（2）和（3）直到得不出新的打√號(hào)的行，列為止.(5)對(duì)沒有打√號(hào)的行畫一橫線,有打√號(hào)的列畫一縱線,這就得到覆蓋所有0元素的最少直線數(shù).若m<n，轉(zhuǎn)下步。某汽車公司擬將四種新產(chǎn)品配置到四個(gè)工廠生產(chǎn)，四個(gè)工廠的單位產(chǎn)品成本（元/件）如表5-35所示．求最優(yōu)生產(chǎn)配置方案．表5-35產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4工廠27550150230工廠36570170250工廠48255200280【解】問題求最小值。第一步：找出效率矩陣每行的最小元素，并分別從每行中減去最小元素，有例：指派問題第二步：找出矩陣每列的最小元素，再分別從每列中減去，有第三步：找獨(dú)立零元素，用最少的直線覆蓋所有“0”，得第四步：這里直線數(shù)等于3（等于4時(shí)停止運(yùn)算），要進(jìn)行下一輪計(jì)算．從矩陣未被直線覆蓋的數(shù)字中找出一個(gè)最小數(shù)k并且減去k，矩陣中k＝5．直線相交處的元素加上k，被直線覆蓋而沒有相交的元素不變，得到下列矩陣第四步等價(jià)于第2、3行減去5，同時(shí)第1列加上5得到的結(jié)果第五步：覆蓋所有零最少需要4條直線，表明矩陣中存在4個(gè)不同行不同列的零元素．容易看出4個(gè)“0”的位置()××()×()()或()××()×()()得到兩個(gè)最優(yōu)解有兩個(gè)最優(yōu)方案第一種方案：第一個(gè)工廠加工產(chǎn)品1，第二工廠加工產(chǎn)品3，第三個(gè)工廠加工產(chǎn)品4，第四個(gè)工廠加工產(chǎn)品2；第二種方案：第一個(gè)工廠加工產(chǎn)品1，第二工廠加工產(chǎn)品4，第三個(gè)工廠加工產(chǎn)品3，第四個(gè)工廠加工產(chǎn)品2；單件產(chǎn)品總成本Z＝58＋150＋250＋55＝513有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D。現(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時(shí)間如下表所示，問如何分派任務(wù)，可使總時(shí)間最少？

任務(wù)人員ABCD甲67112乙4598丙31104丁598