第4章：整數(shù)規(guī)劃

第五章整數(shù)規(guī)劃(IntegerProgramming)整數(shù)規(guī)劃的基本問題及其數(shù)學模型割平面法分支定界法0-1整數(shù)規(guī)劃指派問題WinQSB軟件應用第一節(jié)整數(shù)規(guī)劃的基本問題

及其數(shù)學模型一、問題的提出

實際工作中的某些規(guī)劃問題要求部分變量或全部變量取整數(shù)值，我們稱這樣的問題為整數(shù)規(guī)劃問題(IntegerProgramming，IP)。不考慮整數(shù)要求，由其他約束條件和目標函數(shù)構(gòu)成的規(guī)劃問題稱為該整數(shù)規(guī)劃問題的松弛問題(SlackProblem)。若松弛問題是一個線性規(guī)劃問題，我們稱該整數(shù)規(guī)劃問題為整數(shù)線性規(guī)劃(IntegerLinearProgramming—ILP)?！纠?-1】某工地需要長度不同、直徑相同的成套鋼筋，每套鋼筋由兩根7米長和七根2米長的鋼筋組成?，F(xiàn)有長15米的圓鋼毛坯150根，應如何下料，使廢料最少？

解：本題中沒有說明15米長的圓鋼毛坯有哪些下料方式，故需要首先找出下料方式。將15米長的圓鋼毛坯切割為7米和2米兩種長度的鋼筋有三種方式，如表5-1所示。表5-1170304121021廢料(米)2米長的鋼筋(根)7米長的鋼筋(根)下料方式設(shè)分別表示采用第1、2、3種下料方式所切割的圓鋼毛坯數(shù)目。則廢料可表示為下列形式：看約束條件。首先，工地需要的是成套鋼筋，故7米長和2米長的鋼筋數(shù)之比應滿足2：7，用線性方程來表示，即：整理得：另外，圓鋼毛坯總數(shù)為150根，故還應滿足下面這個條件，即：綜合分析，問題的數(shù)學模型為：【例5-2】現(xiàn)有資金總額為B，可供投資項目有n個，項目j所需投資額和預期收益分別為aj和cj(j＝1,2，…，n)。同時，由于種種原因，有三個附加條件：第一，若選擇項目1，就必須同時選擇項目2，反之則不一定；第二，項目3和項目4中至少選擇一個；第三，項目5、項目6和項目7中恰好選擇兩個。應當怎樣選擇投資項目，才能使總預期收益最大？解：每一個投資項目都有被選擇和不被選擇兩種可能，為此令：則問題可表示為：【例5-3】工廠A1和A2生產(chǎn)某種物資，由于該種物資供不應求，故需要再建一家工廠，相應的建廠方案有A3和A4兩個。這種物資的需求地有B1、B2、B3、B4四個。各工廠年生產(chǎn)能力、各地年需求量、各廠至各需求地的單位物資運費cij(j=1,2,3,4)見表5-2。表5-2150300400350需求量(千噸/年)2005254A42002167A36007538A24004392A1生產(chǎn)能力(千噸/年)B4B3B2B1cijBjAi工廠A3或A4開工后，每年的生產(chǎn)費用估計分別為1200萬元或1500萬元?，F(xiàn)要決定應該建設(shè)工廠A3還是A4，才能使今后每年的總費用(即全部物資運費和新工廠生產(chǎn)費用之和)最少。

解：這是一個物資運輸問題，其特點是事先不能確定應該建A3和A4中的哪一個，因而不知道新廠投產(chǎn)后的實際生產(chǎn)費用。為此，引入0-1變量：設(shè)xij為由Ai運往Bj的物資數(shù)量(千噸)，(i，j＝1,2,3,4)。則問題的數(shù)學模型為：二、整數(shù)規(guī)劃模型的一般形式及解的特點整數(shù)線性規(guī)劃數(shù)學模型的一般形式為：一般來說，整數(shù)線性規(guī)劃可分為以下幾種類型：1.純整數(shù)線性規(guī)劃(PureIntegerLinearProgramming)：指全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃，也稱為全整數(shù)規(guī)劃。2.混合整數(shù)線性規(guī)劃(MixedIntegerLinearProgramming)：指決策變量中一部分必須取整數(shù)值，而另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃。3.0-1整數(shù)線性規(guī)劃(Zero-oneIntegerLinearProgramming)：指決策變量只能取0或1兩個值的整數(shù)線性規(guī)劃。（三）整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系

從數(shù)學模型上看整數(shù)規(guī)劃似乎是線性規(guī)劃的一種特殊形式，求解只需在線性規(guī)劃的基礎(chǔ)上，通過舍入取整，尋求滿足整數(shù)要求的解即可。但實際上兩者卻有很大的不同，通過舍入得到的解（整數(shù)）也不一定就是最優(yōu)解，有時甚至不能保證所得倒的解是整數(shù)可行解。舉例說明。例：設(shè)整數(shù)規(guī)劃問題如下首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。用解法求出最優(yōu)解x1＝3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)現(xiàn)求整數(shù)解（最優(yōu)解）：如用“舍入取整法”可得到4個點即(1，3)(2，3)(1，4)(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點。故整數(shù)規(guī)劃問題的可行解集是一個有限集，如圖所示。圖

因此，可將集合內(nèi)的整數(shù)點一一找出，其最大目標函數(shù)的值為最優(yōu)解，此法為完全枚舉法。如上例：其中（2，2）（3，1）點為最大值，Z=4。⑴.若(LP)沒有可行解，則(ILP)也沒有可行解，停止計算。⑵.若(LP)有最優(yōu)解，并符合(ILP)的整數(shù)條件，則(LP)的最優(yōu)解即為(IP)的最優(yōu)解，停止計算。⑶.若(LP)有最優(yōu)解，但不符合(ILP)的整數(shù)條件，可用相應方法求解。整數(shù)規(guī)劃與其松馳問題解的關(guān)系：

目前，常用的求解整數(shù)規(guī)劃的方法有：

分支定界法和割平面法；對于特別的0－1規(guī)劃問題采用隱枚舉法和匈牙利法。第二節(jié)割平面法割平面法由高莫瑞(Gomory)于1958年提出。其基本思想是放寬變量的整數(shù)約束，首先求對應的松弛問題最優(yōu)解，當某個變量xi不滿足整數(shù)約束時，尋找一個約束方程并添加到松弛問題中，其作用是割掉非整數(shù)部分，縮小原松弛問題的可行域，最后逼近整數(shù)問題的最優(yōu)解。一、割平面法的基本思想考慮松弛問題為標準形線性規(guī)劃問題的純整數(shù)規(guī)劃問題(ILP)：假設(shè)約束條件中aij(i＝1,2,…,m；j＝1,2，…,n)和bi(i＝1,2,…,m)均為整數(shù)(若不為整數(shù)，可令等式兩邊同乘一個倍數(shù)化為整數(shù))。下面先通過一個例子來說明割平面法的基本思想?！纠?-5】將該問題圖示如下圖：從圖(a)中可以看出，松弛問題的最優(yōu)解為X*=(5/3，5/2)T，它不是一個整數(shù)解。因此我們設(shè)法給原線性規(guī)劃問題增加一個約束條件，從而把包括X*在內(nèi)的一部分不含整數(shù)點的可行域從原可行域中分割出去。再求增加了這個約束條件后的新的線性規(guī)劃問題的最優(yōu)解。從圖5-1(b)中可以看出，當我們增加了約束條件“”后，得到新的最優(yōu)解X*=(2，2)T，它便是整數(shù)規(guī)劃問題最優(yōu)解。因此，割平面法的關(guān)鍵就在于如何尋找這類新的約束條件。二、Gomory約束假設(shè)用單純形法求得的線性規(guī)劃問題最優(yōu)解不是整數(shù)解，其中必然有某個或某幾個基變量不為整數(shù)。記B為松弛問題的最優(yōu)基，則問題的基最優(yōu)解為：不妨設(shè)第r個分量不為整數(shù)，根據(jù)最優(yōu)單純形表可得：(5.1)代入上式得：(5.2)(5.3)(5.4)移項，得：(5.5)將和分成整數(shù)部分和非負真分數(shù)之和，即：rrrfNb+=￠因為變量必須取整數(shù)，即上式左邊必須是整數(shù)，從上式右邊看，因為0<fi<1，所以不能為正，即：割平面方程(5.6)即:(5.7)割平面的兩個性質(zhì)：(1)割平面(5.7)式割去了(ILP)的松弛問題(LP)的基最優(yōu)解。(2)割平面(5.7)式未割去原問題(ILP)的任一(整數(shù))可行解。三、割平面法的算法步驟

步驟1：將約束條件系數(shù)及右端項化為整數(shù)，用單純形法求解整數(shù)規(guī)劃問題(ILP)的松弛問題(LP)。設(shè)得到最優(yōu)基B，相應的基最優(yōu)解為X*。步驟2：判別X*的所有分量是否全為整數(shù)？如是，則X*即為(ILP)的最優(yōu)解，算法終止；若否，則取X*中分數(shù)最大的分量，引入割平面(5.7)。

步驟3：將式(5.7)引入松弛變量后加入原最終單純形表，用對偶單純形法繼續(xù)求解。轉(zhuǎn)步驟2?！纠?-6】用割平面法求解例5-5。首先，將整數(shù)約束去掉，將松弛問題化為標準形，并用單純形法求解，結(jié)果見下表:-1/6-1/300σj-1/31/21/3001105/35/2x1x211x4x3x2x1bxBcB0011cj因基變量x1＝5/3，x2＝5/2，均為非整數(shù)，故該最優(yōu)解不是整數(shù)規(guī)劃的可行解。若以變量x1所在的行為源行，得到相應的割平面為：(5.8)對式(5.8)左端加入松弛變量，得到：(5.9)將式(5.9)加入上表中，用對偶單純形法繼續(xù)求解如下表：因基變量x1＝5/3，x2＝5/2，均為非整數(shù)，故該最優(yōu)解不是整數(shù)規(guī)劃的可行解。若以分數(shù)部分最大的變量x1所在的行為源行，得到相應的割平面為：-1/40-1/400σj-1/23/4-3/20011/2-1/41/2010100221x1x2x41100-1/6-1/300σj001-1/31/21/30-1/30101005/35/2-2/3x1x2x5110x5x4x3x2x1bxBcB00011cj-2/3由上表可知，增加約束條件后的線性規(guī)劃問題最優(yōu)解為X*=(2，2，0，1，0)T，因此，原整數(shù)規(guī)劃問題的最優(yōu)解為X*=(2，2)T，其最優(yōu)值z*=4。如果將式(5.8)中的變量用原問題的決策變量來表示，就得到：

整理后得到：例：用割平面法求解數(shù)規(guī)劃問題Cj1100CBXBbx1x2x3x40x3621100x42045011100CBXBbx1x2x3x41x15/3105/6－1/61x28/301－2/31/300－1/6－1/6初始表最終表在松弛問題最優(yōu)解中，x1,x2

均為非整數(shù)解，由上表有：將系數(shù)和常數(shù)都分解成整數(shù)和非負真分數(shù)之和:以上式子只須考慮一個即可，解題經(jīng)驗表明，考慮式子右端最大真分數(shù)的式子，往往會較快地找到所需割平面約束條件。以上兩個式子右端真分數(shù)相等，可任選一個考慮。現(xiàn)選第二個式子，并將真分數(shù)移到右邊得：引入松弛變量s1后得到下式，將此約束條件加到上表中，繼續(xù)求解。Cj11000CBXBbx1x2x3x4s11x15/3105/6－1/601x28/301－2/31/300s1－2/300－1/3－1/3100－1/6－1/60Cj11000CBXBbx1x2x3x4s11x10100－101x240101－20x320011－30000－1/2得到整數(shù)最優(yōu)解，即為整數(shù)規(guī)劃的最優(yōu)解，而且此整數(shù)規(guī)劃有兩個最優(yōu)解：X＊=(0,4),z=4,或X＊=(2,2),z=4。

CBXBbx1x2x3x4x50x34001-1/34/34x24/30102/9-5/911x18/31001/92/9－Z000-19/9-2/9CBXBbx1x2x3x4x5s10x30001-1064x230101/20-5/211x121000010x530001/21-9/2－Z000-20-1（2，3）第三節(jié)分枝定界法分枝定界法是在20世紀60年代初由LandDoing和Dakin等人提出的適合于解純整數(shù)或混合正數(shù)規(guī)劃問題。通過分枝枚舉來尋找最優(yōu)解。首先不考慮對變量的整數(shù)要求，求解相應的線性規(guī)劃模型，如求得最優(yōu)解不符合整數(shù)要求，則把原模型分解為兩部分，每一部分都增加新的約束條件以減少相應線性規(guī)劃模型的可行域。通過不斷分解，逐步逼近滿足要求的整數(shù)最優(yōu)解，在這個過程中包括了“分枝”和“定界”兩個關(guān)鍵步驟。一、分支定界法的基本思想基本思想：先求出整數(shù)規(guī)劃相應的線性規(guī)劃(即不考慮整數(shù)限制)的最優(yōu)解，若求得的最優(yōu)解符合整數(shù)要求，則這個解就是原整數(shù)規(guī)劃的最優(yōu)解；若不滿足整數(shù)條件，則任選一個不滿足整數(shù)條件的變量來構(gòu)造新的約束，在原可行域中剔除部分非整數(shù)解。然后，再在縮小的可行域中求解新構(gòu)造的線性規(guī)劃的最優(yōu)解，這樣通過求解一系列線性規(guī)劃問題，最終得到原整數(shù)規(guī)劃的最優(yōu)解。定界的含義：整數(shù)規(guī)劃是在相應的線性規(guī)劃的基礎(chǔ)上增加變量為整數(shù)的約束條件，整數(shù)規(guī)劃的最優(yōu)解不會優(yōu)于相應線性規(guī)劃的最優(yōu)解。對極大化問題來說，相應線性規(guī)劃的目標函數(shù)最優(yōu)值是原整數(shù)規(guī)劃函數(shù)值的上界；對極小化問題來說，相應線性規(guī)劃的目標函數(shù)的最優(yōu)值是原整數(shù)規(guī)劃目標函數(shù)值的下界。下面我們用一例說明求解步驟例maxZ=

6x1+5x22x1+x2≤95x1+7x2≤35x1,x2≥0x1,x2取整數(shù)第一步，不考慮變量的整數(shù)約束，求相應的LP(問題1)的最優(yōu)解：x1=28/9，x2=25/9，Z1=293/9第二步，定界過程這個解不是原整數(shù)規(guī)劃的最優(yōu)解，這時目標函值Z1=293/9是原整數(shù)規(guī)劃目標函數(shù)的上界；因為x1=x2=0是整數(shù)規(guī)劃問題的可行解，所以下界為0。界限一（0，293/9）第三步，分枝過程將不滿足整數(shù)約束的變量x1進行分枝，x1稱為分枝變量，構(gòu)造兩個新的約束條件

x1≤[28/9]=3，x1≥[28/9]+1=4并將新約束添加到原問題當中去：問題2：maxZ=

6x1+5x2問題3：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≥4x1,x2≥0x1,x2≥0x1,x2取整數(shù)x1,x2取整數(shù)這樣就把相應的線性規(guī)劃的可行域分成兩個部分，如下圖所示。??????????5x1+7x2=352x1+x2=9x1x2123125344求解問題2相應的線性規(guī)劃的最優(yōu)解：x1=3，x2=20/7，Z2=226/7≈33.2求解問題3相應的線性規(guī)劃的最優(yōu)解：x1=4，x2=1，Z3=29第四步，定界過程LP3的解滿足整數(shù)約束，不必再分枝，它的目標函數(shù)值是29，大于原有下界0，則新的下界為29；現(xiàn)有上界為未分枝子問題中目標函數(shù)最大值，即為226/7≈33.2。界限二（29，226/7）LP2的解仍不滿足整數(shù)約束的要求，它的目標函數(shù)值226/7大于現(xiàn)有下界，則應繼續(xù)分枝。第五步，分枝過程將不滿足整數(shù)約束的變量x2進行分枝，構(gòu)造兩個新的約束條件：

x2≤[20/7]=2，x2≥[20/7]+1=3

問題4：maxZ=

6x1+5x2問題5：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≤2x2≥3x1,x2≥0x1,x2≥0x1,x2取整數(shù)x1,x2取整數(shù)x2=2

x2=3??????????5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3求解問題4相應的線性規(guī)劃的最優(yōu)解：x1=3，x2=2，Z4=28求解問題5相應的線性規(guī)劃的最優(yōu)解：x1=14/5，x2=3，Z5=159/5≈31.8第六步，定界過程LP4的解滿足整數(shù)約束，不必再分枝，它的目標函數(shù)值是28，小于原有下界29，則下界仍為29；現(xiàn)有上界為未分枝子問題中目標函數(shù)最大值，即為159/5。界限三（29，159/5）LP5的解仍不滿足整數(shù)約束的要求，它的目標函數(shù)值159/5大于現(xiàn)有下界29，則應繼續(xù)分枝。第七步，分枝過程將不滿足整數(shù)約束的變量x1進行分枝，構(gòu)造兩個新的約束條件：x1≤[14/5]=2，x1≥[14/5]+1=3

問題6：maxZ=

6x1+5x2問題7：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≥3x2≥3x1≤2x1≥3x1,x2≥0x1,x2≥0x1,x2取整數(shù)x1,x2取整數(shù)x2=2

x2=3??????????5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3x1=2求解問題6相應的線性規(guī)劃的最優(yōu)解：x1=2，x2=25/7，Z6=209/7≈29.8求解問題7相應的線性規(guī)劃的最優(yōu)解：問題7的可行域是一個空集，所以無最優(yōu)解。第八步，定界過程LP7的無最優(yōu)解，不必再分枝，下界仍為29；現(xiàn)有上界為未分枝子問題中目標函數(shù)最大值，即為209/7。界限四（29，29.8）LP6的解仍不滿足整數(shù)約束的要求，它的目標函數(shù)值209/7大于現(xiàn)有下界29，則應繼續(xù)分枝。第九步，分枝過程將不滿足整數(shù)約束的變量x2進行分枝，構(gòu)造兩個新的約束條件：x2≤3，x2≥4

問題8：maxZ=

6x1+5x2問題9：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≥3x2≥3x1≤2x1≤2x2≤3x2≥4x1,x2≥0x1,x2≥0x1,x2取整數(shù)x1,x2取整數(shù)x2=3??????????5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3x1=2x2=2

x2=4求解問題8相應的線性規(guī)劃的最優(yōu)解：x1=2，x2=3，Z8=27求解問題9相應的線性規(guī)劃的最優(yōu)解：x1=7/5，x2=4，Z9=142/5≈28.4第十步，定界過程LP8的最優(yōu)解，滿足整數(shù)約束，不必再分枝，下界仍為29；現(xiàn)有上界為未分枝子問題中目標函數(shù)最大值，即為142/5。界限五（29，142/5）雖然LP9的解仍不滿足整數(shù)約束的要求，它的目標函數(shù)值142/5小于現(xiàn)有下界29，則不再繼續(xù)分枝。上界<=下界，得整數(shù)規(guī)劃問題的最優(yōu)解為下界：x1=4，x2=1，Z=29分枝定界過程x1≤3x1≥4x2≤2x2≥3x1≤2x1≥3x2≤3x2≥41.先求解ILP總是所對應的松馳問題。若問題(LP)不可行，則(ILP)也不可行，算法終止；若問題(LP)的最優(yōu)解X*為(ILP)的可行解，則它就是(ILP)的最優(yōu)解，算法終止。若問題(LP)的最優(yōu)解存在，但不滿足(ILP)的整數(shù)要求，轉(zhuǎn)步驟2。2、對當前問題進行分枝和定界：

分技：不妨設(shè)當前問題為(A)，其松弛問題(B)的最優(yōu)解不符合整數(shù)約束，任取非整數(shù)的分量xr。構(gòu)造兩個附加約束：xr≤[xr]和xr≥[xr]+1，對(A)分別加入這兩個約束，可得到兩個子問題(A1)和(A2)，顯然這兩個子問題的可行解集的并是(A)的可行解集；定界：根據(jù)前面分析，對每個當前問題(A)可以通過求解松弛問題(B)，以及找(A)的可行解得到當前問題的上、下界zˉ和z。

3、比較與剪枝：

對當前子問題進行考察，若不需再進行計算，則稱之為剪枝。一般遇到下列情況就需剪枝：①(B)無可行解；②(B)的最優(yōu)解符合整數(shù)約束；③(B)的最優(yōu)值z≥zˉ。通過比較，若子問題不剪枝則返回2。

分枝定界法當所有子問題都剪枝了，即沒有需要處理的子問題時，達到當前上界zˉ的可行解即原問題的最優(yōu)解，算法結(jié)束。

分枝定界法是求整數(shù)規(guī)劃的一種常用的有效的方法，既能解決純整數(shù)規(guī)劃的問題，也能解決混合整數(shù)規(guī)劃的問題。例2求解Amaxz=40x1+90x2①9x1+7x2≤56②7x1+20x2≤70③x1，x2≥0④x1，x2整數(shù)⑤解為：X1＝4，X2＝2，Z=340

解

先不考慮條件⑤，即解相應的線性規(guī)劃B,①～④(見圖)，得最優(yōu)解x1=4.81，x2=1.82，z0=356

可見它不符合整數(shù)條件⑤。這時z0是問題A的最優(yōu)目標函數(shù)值z*的上界，記作z0=。而在x1=0，x2=0時，顯然是問題A的一個整數(shù)可行解，這時z=0，是z*的一個下界，記作=0，即0≤z*≤356。分支定界法的解法首先注意其中一個非整數(shù)變量的解，如x1，在問題B的解中x1=4.81。于是對原問題增加兩個約束條件x1≤4，x1≥5可將原問題分解為兩個子問題B1和B2(即兩支)，給每支增加一個約束條件，如圖5-3所示。這并不影響問題A的可行域，不考慮整數(shù)條件解問題B1和B2，稱此為第一次迭代。得到最優(yōu)解為：

圖5-3x1≤4，x1≥5顯然沒有得到全部變量是整數(shù)的解。因z1＞z2，故將改為349，那么必存在最優(yōu)整數(shù)解，得到z*，并且0≤z*≤349繼續(xù)對問題B1和B2進行分解因z1＞z2，故先分解B1為兩支。增加條件x2≤2者，稱為問題B3；增加條件x2≥3者稱為問題B4。在圖5-3中再舍去x2＞2與x3＜3之間的可行域，再進行第二次迭代。繼續(xù)對問題B2進行分解

解題的過程都列在圖5-4中。

圖5-4割平面法與分枝定界法的比較

這兩種方法的共同特點：通過增加附加約束，使整數(shù)最優(yōu)解最終成為線性規(guī)劃的一個頂點，于是整個問題就可使用單純形法找到這個整數(shù)最優(yōu)解；它們的相異之處是附加約束條件的選取原則及方法不同。第四節(jié)0－1整數(shù)規(guī)劃一、0-1變量的應用第一節(jié)中我們討論過0-1變量，即只能取0或1的變量，它是邏輯變量，通常用來表示在是與否之間二選一的問題，如某個方案A是否被選中，可用下面的0-1變量來表示：當采取方案A時當不采取方案A時【例5-8】含有相互排斥的約束條件的問題。設(shè)某廠生產(chǎn)第j種產(chǎn)品的數(shù)量為xj(j=1，2，3)，其材料可在甲或乙中選擇一種，當選擇甲或乙時，相應的材料消耗的約束條件分別為：和(5.12a)(5.12a)試問這類相互排斥的約束條件如何體現(xiàn)在模型中？解：引入0-1變量：和因而，兩個相互排斥的約束條件可用下列線性約束條件統(tǒng)一起來：其中M是一個充分大的數(shù)。若y1=1，而y2=0，即選用材料乙，由(5.12d)式得：式(5.12c)自然成立；若y1=0，而y2=1，即選用材料甲，由(5.12c)式得：式(5.12d)自然成立.【例5-9】固定費用問題。有一種自然資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件可變費用及售價、資源單位消耗量及組織三種產(chǎn)品生產(chǎn)的固定費用見表5-5。要求制訂一個生產(chǎn)計劃，使總收益最大。－12108單位售價－200150100固定費用－654單位可變費用100321C300432B500842A資源量IIIIII單耗量資源產(chǎn)品解：設(shè)xj表示三種產(chǎn)品的產(chǎn)量(j=1，2，3)。引入0-1變量：則問題的數(shù)學模型可歸結(jié)如下：如果生產(chǎn)第j種產(chǎn)品，則其產(chǎn)量xj＞0，由xj≤Mjyj知，yj＝1。因此，相應的固定費用在目標函數(shù)中將被考慮。同理，如果不生產(chǎn)第j種產(chǎn)品，則其產(chǎn)量xj=0，由xj≤Mjyj知，yj可以取0或1。因此，相應的固定費用不應在目標函數(shù)中將被考慮。二、0-1型整數(shù)規(guī)劃的解法0-1型規(guī)劃是一類特殊的整數(shù)規(guī)劃，因為變量只有0或1兩個可能的取值，故最多有2n個可行解，理論上可以用枚舉法進行求解。但當n較大時，采用完全枚舉法求解幾乎是不可能的。隱枚舉法是求解0-1整數(shù)規(guī)劃問題的一種比較簡便的方法。其實質(zhì)也是一種分支定界法。隱枚舉法是是在2n個可能的變量組合中，只有一部分是可行解。只要發(fā)現(xiàn)某個變量組合不滿足其中一個約束條件，就不必再檢驗是否滿足其它約束。如所有約束條件都滿足，就是0-1規(guī)劃的一個可行解，可根據(jù)相應的目標函數(shù)值產(chǎn)生一個過濾條件，對于目標函數(shù)值劣于該可行解的變量組合不必再去檢驗其可行性。在以后的求解過程中，如發(fā)現(xiàn)某個可行解比原來保留的可行解更優(yōu)，則用它替換原來的過濾條件。【例5-11】求解0-1整數(shù)規(guī)劃(5.13a)(5.13b)(5.13c)(5.13d)解：求解過程可以用表5-7表示。(1，1，1)(1，1，0)√(1，0，1)(1，0，0)(0，1，1)(0，1，0)(0，0，1)(0，0，0)dcba過濾條件約束條件z值(x1，x2，x3)√0√√√z≥0√5√√√z≥5-233√8√√√z≥816所以，最優(yōu)解(x1，x2，x3)T=(1，0，1)T，maxz=8。為了使最優(yōu)解盡可能早出現(xiàn)，可先將目標函數(shù)中各變量的順序按其系數(shù)大小重新排列，這樣可進一步減少計算量。例5-12給出了用隱枚舉法求解0-1整數(shù)規(guī)劃問題的一般步驟。【例5-12】求解0-1整數(shù)規(guī)劃步驟1：將問題轉(zhuǎn)化為如下標準形式：

⑴如目標函數(shù)為maxz，令，可化為。如某個變量的系數(shù)為負，令，使系數(shù)變正。其中cj≥0，且c1≤c2≤…≤cn。⑵如約束條件為≤，兩邊同乘(-1)；如約束條件為等式，可令變量，代入目標函數(shù)和其它約束條件中，將xn消掉。⑶按目標函數(shù)中系數(shù)由小到大的順序重新排列變量，并將約束條件中的排列順序做相應改變。調(diào)整后的0-1規(guī)劃問題變?yōu)椋?5.14a)(5.14b)步驟2：令所有變量取0，求出目標函數(shù)值，并代入約束條件中檢查是否可行，如果可行即為問題的最優(yōu)解；否則轉(zhuǎn)下一步。令，得＝-10，但不滿足兩個約束條件。步驟3：分支和定界。依次令各變量分別取0或1，將問題劃分為兩個子問題，分別檢查是否可行，如不可行繼續(xù)對邊界值較小的子問題分支，直到找出一個可行解為止，這時得到值的一個上界。分支過程見下圖5-5所示：步驟4：考察所有子問題，有以下四種情況：

⑴若某個子問題的邊界值對應原問題的可行解，則將它的邊界值與保留的值作比較，并取較優(yōu)的一個作為新的值。如所有子問題都已考察完畢，則保留下來的值及其對應的解即為0-1整數(shù)規(guī)劃問題的最優(yōu)解。⑵若某個子問題的邊界值大于保留下來的值，不管其是否可行，則將這一分支剪掉。⑶若某個子問題不可行，則將這一分支剪掉。⑷若某個子問題可行且邊界值優(yōu)于值，但該邊界值對應的解不是可行解，則該問題待考察。如有多個問題待考察，優(yōu)先對其中最優(yōu)值最大的一個子問題進行考察，轉(zhuǎn)步驟3。分支③邊界值=-6＜-4，但相應的解不可行，需繼續(xù)分支。過程見下圖5-6所示。上述求解過程也可用表格表示：(0，1，0，1，0)(0，1，1，0，0)(0，0，1，0，0)(1，0，1，0，0)(1，1，0，0，0)(0，1，0，0，0)(1，0，0，0，0)(0，0，0，0，0)＞-4，剪枝1⑨＞-4，剪枝-1⑧不可行，剪枝×-5⑦＞-4，剪枝-3⑤可行≤-4√√-4④×-6③×√-8②×-10①ba備注約束條件z值序號所以，最優(yōu)解：即原問題的最優(yōu)解為：第五節(jié)指派問題一、指派問題的數(shù)學模型指派問題又稱分配問題，是指將m項工作分配n個工人去完成(通常m＝n)，應如何分工使總工時或總費用最少的一類問題。這類問題一般有兩個要求：一是每項工作只能由一個工人去完成；二是每個工人只能完成一項工作。這類問題的標準提法如下：現(xiàn)有n項工作分配n個工人去完成，已知工人j完成工作i需要花費時間cij。要求每項工作只能由一個工人去完成，每個工人只能完成一項工作。應如何分工，使總工時最少？在實際中經(jīng)常會遇到這樣的問題，有n項不同的任務，需要n個人分別完成其中的一項，但由于任務的性質(zhì)和各人的專長不同，因此各人去完成不同的任務的效率（或花費的時間或費用）也就不同。于是產(chǎn)生了一個問題，應指派哪個人去完成哪項任務，使完成n項任務的總效率最高（或所需時間最少），這類問題稱為指派問題或分派問題。建立該問題的數(shù)學模型，需引入n2個0-1變量。設(shè)：則該問題的數(shù)學模型可寫為：【例5-13】某工廠要生產(chǎn)四種產(chǎn)品，該工廠有四個車間都可以生產(chǎn)這四種產(chǎn)品。但由于設(shè)備情況與技術(shù)情況不同，所以生產(chǎn)成本不同，其單位產(chǎn)品的生產(chǎn)成本如表5-9所示。問應當怎樣分配這四種產(chǎn)品到各車間，才能使總的生產(chǎn)成本最??？試建立該問題的數(shù)學模型。解：這是一個標準形式的指派問題。引入0-1變量：6443462333541521045414321

產(chǎn)品車間這個問題的約束條件如下：(1)每個車間只能生產(chǎn)一種產(chǎn)品，即：簡寫為：（i=1,2,3,4）則問題的數(shù)學模型可歸結(jié)為：(2)一種產(chǎn)品只能由一個車間生產(chǎn)，即：簡寫為：（j=1,2,3,4）(3)變量工xij必須等于0或1，即xij=0或1。二、匈牙利算法分配問題是0-1規(guī)劃的特例，也是運輸問題的特例，當然可用整數(shù)規(guī)劃，0-1規(guī)劃或運輸問題的解法去求解，這就如同用單純型法求解運輸問題一樣是不合算的。庫恩(W.W.Kuhn)于1955年提出了指派問題的解法，他引用了匈牙利數(shù)學家康尼格(D.Konig)的關(guān)于矩陣中獨立零元素的定理：系數(shù)矩陣中獨立0元素的最多個數(shù)等于能覆蓋所有零元素的最小直線數(shù)，習慣上稱之為匈牙利解法。分配問題最優(yōu)解的以下性質(zhì)：若從系數(shù)矩陣(cij)的某行(或某列)各元素分別減去該行（列）的最小元素，得到新矩陣(cij'),那么以(cij')為系數(shù)矩陣求得的最優(yōu)解和利用原系數(shù)矩陣求得的最優(yōu)解相同。匈牙利算法的一般步驟可以表述如下：

步驟1：變換系數(shù)矩陣。先把系數(shù)矩陣各行分別減去本行的最小元素，再把各列分別減去本列的最小元素，使系數(shù)矩陣中各行各列都至少有一個零元素，且不出現(xiàn)負數(shù)。轉(zhuǎn)步驟2。在新矩陣中找盡可能多的獨立0元素，若能找出n個獨立0元素，就以這n個獨立0元素對應解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。找獨立0元素，常用的步驟為：

⑴從只有一個0元素的行(列)開始，給這個0元素加△。然后劃去△所在列(行)的其它0元素，記作?；這表示這列所代表的任務已指派完。

⑵給只有一個0元素的列(行)中的0元素加；然后劃去△所在行的0元素，記作?。

⑶反復進行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止。步驟2：確定獨立零元素。若某行(某列)只有一個零元素，將該零元素加一個三角符號(△)，同時將該零元素所在列(行)的其它零元素劃去。如此反復進行，直到系數(shù)矩陣中所有零元素都被標注△或被劃去。

⑷若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個，則從剩有0元素最少的行(列)開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個0元素加△。⑸若△元素的數(shù)目m等于矩陣的階數(shù)n，那么這指派問題的最優(yōu)解已得到。若m<n,則轉(zhuǎn)入下一步。若獨立零元素有n個，則令獨立零元素位置對應的變量取1，其它變量取0，這樣得到的矩陣X即為最優(yōu)分配方案。若獨立零元素不足n個，轉(zhuǎn)步驟3。步驟3：做能覆蓋所有零元素的最少直線組合。

⑴對沒有標△的行打“√”；⑵對打“√”行中被劃掉的零元素所在列打“√”；⑶對打“√”列中標△的零元素所在行打“√”；⑷重復⑵和⑶，直到再也不能找到可打“√”行或列為止。⑸對未打“√”的行畫一直線，對打“√”的列畫一直線，這樣就