第七章整數(shù)規(guī)劃模型第1頁，課件共68頁，創(chuàng)作于2023年2月第七章整數(shù)規(guī)劃模型整數(shù)規(guī)劃模型在實踐中有廣泛的應用背景，例如著名的指派模型、背包模型、旅行售貨員模型、排序模型以及地理六章中的截料模型等都是整數(shù)規(guī)劃模型。整數(shù)規(guī)劃模型（IntegerProgramming，簡記IP）是一類要求變量為整數(shù)的規(guī)劃模型。自從高莫瑞（R.E.Gomory）在1958年提出割平面法以后，整數(shù)規(guī)劃才逐步成為一個獨立的理論分支。將目標函數(shù)為線性函數(shù)，約束條件均為線性等式或不等式的整數(shù)規(guī)劃模型稱為整數(shù)線性規(guī)劃模型（ILP），否則稱為整數(shù)非線性規(guī)劃模型（INLP）兩類。若要求全部變量都去整數(shù)值，則稱為純整數(shù)規(guī)劃模型（PureIP）或全整數(shù)規(guī)劃模型（AllIP）；若只要求一部分變量取整數(shù)值，則稱為混合整數(shù)規(guī)劃模型（MixedIP）；若要求全部或部分變量只取0或1值。則稱為0-1規(guī)劃。由于整數(shù)非線性規(guī)劃尚無一般解法，因此本文僅考慮整數(shù)線性規(guī)劃模型及其解法，下文所提及的整數(shù)規(guī)劃專指整數(shù)線性規(guī)劃。第2頁，課件共68頁，創(chuàng)作于2023年2月§1整數(shù)規(guī)劃模型及窮舉法一、整數(shù)規(guī)劃模型建立整數(shù)規(guī)劃模型的過程也與建立線性規(guī)劃模型一樣，有“設立決策變量”、“明確決策目標函數(shù)”和“尋找限制條件”三個過程。例一（投資模型）某工廠有資金13萬元，用于購置新機器，可在A、B兩種機器中任意選購。已知機器A、B的購置費每臺分別為2萬元和4萬元。該廠維修能力只能修7臺機器B；若維修機器A，1臺折算B為2臺。已知1臺機器A可增加產(chǎn)值6萬元，1臺B可增加產(chǎn)值4萬元，問應購置機器A和B各多少臺，才能使產(chǎn)值增加最多？解設購買機器A和B的臺數(shù)分別為臺，則模型為：第3頁，課件共68頁，創(chuàng)作于2023年2月用LINDO軟件解的程序為：第4頁，課件共68頁，創(chuàng)作于2023年2月答案為：最優(yōu)決策變量目標函數(shù)最優(yōu)值為22。（跳躍式成本模型）設兩種產(chǎn)品A和B每公斤價格為10元和7元，每公斤需要的加工工時為6小時和4小時，成本和工時的關系如圖7.1所示，要求建立一整數(shù)規(guī)劃模型，是利潤最大。解設兩種產(chǎn)品的產(chǎn)量分別為公斤，設工時在2000以內(nèi)為第一范圍，2000到3000小時為第二范圍，3000到5000小時為第三范圍。再設當工時在第j范圍內(nèi)時，（j=1，2，3）。則模型為：第5頁，課件共68頁，創(chuàng)作于2023年2月圖7.1第6頁，課件共68頁，創(chuàng)作于2023年2月用LINDO軟件解的程序為：第7頁，課件共68頁，創(chuàng)作于2023年2月二、窮舉法

窮舉法盡管往往不是有效的和常用的方法，但卻是最自然想到和直觀的方法，而對有些模型卻是無可奈何的方法。有時通過對窮舉法的研究，往往能夠得到啟發(fā)而產(chǎn)生新的方法。滿足整數(shù)規(guī)劃模型所有約束條件的可行解的集合，很多情況下是有限集合，這為窮舉法的應用提供了可能。下面用窮舉法求一個只有兩個變量的整數(shù)規(guī)劃模型的最優(yōu)解。第8頁，課件共68頁，創(chuàng)作于2023年2月

例3用窮舉法求例1中的整數(shù)規(guī)劃模型的最優(yōu)解：maxZ=s.t.為整數(shù)解圖7.2給出了可行解的集合，共有十二個整數(shù)點（即對應到可行解），得整數(shù)規(guī)劃的最優(yōu)解最優(yōu)值。即A，B兩種機器分別購買3臺和1臺，產(chǎn)值最多增加22萬元。第9頁，課件共68頁，創(chuàng)作于2023年2月11

0223345（2.5，2）圖7.2整數(shù)規(guī)劃模型與線性規(guī)劃模型不同之處只在于增加了整數(shù)約束。不考慮整數(shù)約束得到的線性規(guī)劃稱為整數(shù)規(guī)劃的線性松弛。第六章講述了用圖解法球線性規(guī)劃模型的解，能否用它的線性松弛模型的最優(yōu)解痙過去整或四舍五入第10頁，課件共68頁，創(chuàng)作于2023年2月得到整數(shù)規(guī)劃模型的最優(yōu)解呢？在上例中整數(shù)規(guī)劃模型的最優(yōu)解，線性松弛模型的最優(yōu)解為，四舍五入得，不是不是可行解，自然也不是最優(yōu)解；若將取整得，雖然是可行解，但它不是最優(yōu)解。由此可見，剛剛的設想是行不通的，事實上整數(shù)規(guī)劃模型的求解是難題，至今還沒有有效的算法（即多項式算法）。

§割平面法和分支定界法一、割平面法

整數(shù)規(guī)劃模型的割平面法由高莫瑞首創(chuàng)，稱為高莫瑞割平面法（GomoryCuttingPlaneAlgorithm），以區(qū)別于后來其他割平面法。在整數(shù)規(guī)劃模型中，去掉了第11頁，課件共68頁，創(chuàng)作于2023年2月變量為整數(shù)的約束條件之后的模型稱為原整數(shù)規(guī)劃得像性松弛模型。高莫瑞割平面法的基本思想是在整數(shù)規(guī)劃的線性松弛模型中逐次增加一個新約束（即割平面），它能割去圓松弛可行域中一塊不含整數(shù)解的區(qū)域。逐次切割下去，直到切割最終得到松弛可行域的一個最優(yōu)頂點即整數(shù)解為止。我們用例4結合圖形來說明高莫瑞割平面法的思想及過程：例4用割平面法求下面的整數(shù)規(guī)劃模型的最優(yōu)解：

為整數(shù)第12頁，課件共68頁，創(chuàng)作于2023年2月解圖7.3作出了整數(shù)規(guī)劃的線性松弛模型（記為）的可行解，其最優(yōu)解為，增加新的約束條件：

得新模型，圖7.4給出了的最優(yōu)解為。第13頁，課件共68頁，創(chuàng)作于2023年2月011223345011223345圖7.3圖7.4第14頁，課件共68頁，創(chuàng)作于2023年2月此時，已經(jīng)滿足整數(shù)要求，但還不是整數(shù)，還需要增加新的約束條件：得新模型（），圖7.5給出了的最優(yōu)解為，已得原整數(shù)規(guī)劃模型的最優(yōu)解，易計算出最優(yōu)值為55。第15頁，課件共68頁，創(chuàng)作于2023年2月11223345圖7.50新增加的約束條件必須滿足下列兩個條件：（1）不能割去滿足條件的整數(shù)點（即整數(shù)可行解）。新的割平面的加入，使得可行解區(qū)域逐漸減小，割去的區(qū)域不能有整數(shù)可行解。（2）必須將前一次的最優(yōu)解割去。將原整數(shù)規(guī)劃模型的第16頁，課件共68頁，創(chuàng)作于2023年2月最優(yōu)解逐步暴露在可行解區(qū)域的頂點上。

割平面構造原理涉及到對偶單純形法，在此不多加介紹。割平面法有很重要的理論意義，但在實際計算中沒有分支定界效率高，且涉及到對分數(shù)的處理，因此幾乎沒有給予割平面法的軟件。

二、分支定界法分支定界法的基本思想是根據(jù)某種規(guī)則將原整數(shù)規(guī)劃模型的可行域分解為越來越小的子區(qū)域，并檢查某各子區(qū)域內(nèi)整數(shù)解的情況，直到找到最優(yōu)的整數(shù)解或證明整數(shù)解不存在。根據(jù)整數(shù)規(guī)劃模型性質(zhì)的不同，存在許多的分支界定法以及分支界定的技巧，在此只對分支界定的一般原理作一簡單的介紹。在介紹具體算法之前，以下幾個重要的實事是容易理解的：第17頁，課件共68頁，創(chuàng)作于2023年2月（1）如果求解一個整數(shù)規(guī)劃的線性松弛模型時得到一個整數(shù)解，這個解一定也是整數(shù)規(guī)劃模型的最優(yōu)解。然而，求解實際模型時這種概率很小。（2）如果得到的解不是一個整數(shù)解，則最優(yōu)整數(shù)解的目標值一定不會好于得到的線性松弛模型的最優(yōu)解。因此線性松弛模型的最優(yōu)解是整數(shù)規(guī)劃模型最優(yōu)值的一個界（對最大化模型為上界，對最小化模型為下界）。（3）如果在求解過程中已經(jīng)找到一個整數(shù)解，則最優(yōu)整數(shù)解一定不會劣于該整數(shù)解。因此它也是最優(yōu)整數(shù)解的一個界（對最大化模型為下界，對最小化模型為上界）。如果用表示線性松弛模型的最優(yōu)值，用表示已找到的最好整數(shù)解的目標值，為原整數(shù)規(guī)劃第18頁，課件共68頁，創(chuàng)作于2023年2月模型的最優(yōu)值，表示下界，表示上界，則最優(yōu)值一定滿足以下關系：（對最大化模型）(對最小化模型)分支定界法定界法思想就是不斷降低上界，提高下界最后使得下界等于上界，就可以搜索到最優(yōu)整數(shù)解。分支定界法從求解線性松弛模型開始，將線性松弛模型的可行分成許多小的子區(qū)域，這一過程稱為分支；通過分支和找到更好的整數(shù)解來不斷修改模型的上下界，這一過程稱為定界，這就是分支定界法的由來。以下對分支定界法的基本步驟進行簡單的討論（假定模型求極大值）。1.對給定的整數(shù)規(guī)劃模型，放松整數(shù)約束，求解它的線性松弛模型的最優(yōu)解，如果得到解釋整數(shù)解，該解即為整數(shù)規(guī)劃模型的最優(yōu)解。否則，所得到的最優(yōu)值可作為該第19頁，課件共68頁，創(chuàng)作于2023年2月模型最優(yōu)值的初始上界。最初下界一般認為負無窮。2.從任何一個模型或子模型中不滿足整數(shù)要求的變量中選出一個進行分支處理。分支通過假如一對互斥的約束將一個（子）模型分解為兩個受到更多約束的子模型，并強迫不為整數(shù)的變量進一步逼近整數(shù)值。例如，如果選中的變量=q，q的整數(shù)部分為k，則在一個子模型中增加約束為，在另一個子模型中增加的約束為。分支過程砍掉了在和之間的非整數(shù)區(qū)域，縮小了搜索的區(qū)域。每個子模型都是一個線性規(guī)劃模型，如果它的最優(yōu)解不滿足整數(shù)要求，對該模型還必須繼續(xù)向下進行分支，所有分支可以形成一個樹形圖。樹形圖上面為線性松弛模型，它有兩個分支，每個分支又會有兩個分支，焚之可以繼續(xù)進行下去，直到找到一個有整數(shù)第20頁，課件共68頁，創(chuàng)作于2023年2月

最優(yōu)解的分支或該分支不可行時為止。3.通過不斷的分支和求解各個子模型的最最優(yōu)解，不斷修正最優(yōu)值的上下界。上界通常由各分支最優(yōu)值的最小值決定，下屆則由已經(jīng)能夠找到的最好的整數(shù)解的目標值決定。求解任何一個子模型都有以下四種可能的結果：（1）子模型無可行解，此時無續(xù)向下繼續(xù)分支。（2）子模型的最優(yōu)解滿足原整數(shù)規(guī)劃模型變量整數(shù)約束，則不必向下繼續(xù)分支。如果該整數(shù)解是目前得到的最好的整數(shù)解，則被記錄下來，并用它的值作為新的下屆。（3）子模型的最優(yōu)值介于目前所得到的上下界之外，則無需繼續(xù)向下進行分支。（4）最優(yōu)解不滿足原整數(shù)規(guī)劃模型變量整數(shù)約束，最優(yōu)值介于所得到的上下界之間，則該模型才有第21頁，課件共68頁，創(chuàng)作于2023年2月繼續(xù)向下搜索的必要。4.直到每一個子模型均無需繼續(xù)向下分支時，整數(shù)規(guī)劃模型的最優(yōu)解才找到。下面以例5用分支定界法求整數(shù)規(guī)劃模型最優(yōu)解的過程。例5用分支定界法求下列整數(shù)規(guī)劃模型：為整數(shù)第22頁，課件共68頁，創(chuàng)作于2023年2月解求解該模型的線性松弛模型（記為），得到最優(yōu)值=5.545，最優(yōu)解為=1.477，=4.068（該模型可用線性規(guī)劃的圖解法，若多于兩個變量，可用LINDO或MATLAB求解）。因為該模型失球最大化模型，整數(shù)規(guī)劃模型的最優(yōu)值不可能大于，也不可能小于負無窮，所以可令上界=5.545，下屆。第23頁，課件共68頁，創(chuàng)作于2023年2月由于兩個變量都不是整數(shù)，我們可以從中選擇一個變量進行分支，假定選，要求變?yōu)檎麛?shù)，因此希望或者小于等于1，或者大于等于2。分支后形成兩個子模型，子模型1增加約束，子模型2增加約束。（子模型1）第24頁，課件共68頁，創(chuàng)作于2023年2月(子模型2)子模型1的最優(yōu)值為=5.333，最優(yōu)解為=1，=4.333。該解還不是整數(shù)解，還應繼續(xù)分支。由于子模型1中只有取值不是整數(shù)，應對進行分支。分支后又形成兩個子模型3和4。子模型3是由子模型1架上約束形成的，子模型4頁是由子模型1加上約束構成的。第25頁，課件共68頁，創(chuàng)作于2023年2月(子模型3)(子模型4)第26頁，課件共68頁，創(chuàng)作于2023年2月子模型3的最優(yōu)值為=5，最優(yōu)解為=1，=4，該解已經(jīng)是整數(shù)解。所以子模型3無需向下繼續(xù)分支，且新的下屆可以計算如下：子模型4無可行解，所以子模型4也無需繼續(xù)向下分支。子模型2的最優(yōu)值為=4.5，最優(yōu)解為=2，=2.5。此時最優(yōu)值已小于下屆5，故也無需繼續(xù)向下分支。整數(shù)規(guī)劃模型的最優(yōu)解已經(jīng)找到，=1，=4，最優(yōu)值為5。為了清晰的描述求解的全過程，我們作出個子模型關系的樹形圖（圖7.6）第27頁，課件共68頁，創(chuàng)作于2023年2月松弛模型子模型1子模型2子模型3子模型4無可行解第28頁，課件共68頁，創(chuàng)作于2023年2月三、兩輛鐵路平板車的裝貨問題這是1988年美國數(shù)模競賽的B題，問題如下：有七種規(guī)格的包裝箱要裝到兩輛平板車上去。包裝箱的寬和高是一樣的，但厚度t（以厘米計）及重量w(以千克計）是不同的。下表給出了每種包裝箱的厚度，重量以及數(shù)量。每輛平板車有10.2米長的地方可用來裝包裝箱（像面包片一樣），載重為40噸。由于地區(qū)貨運的限制，對類包裝箱的總數(shù)有一個特別的限制：這三類箱子所占的總空間（厚度）不能超過302.7厘米。包裝箱類型t（厘米）48.752.061.372.048.752.064.0w（千克）200030001000500400020001000件數(shù)8796648

第29頁，課件共68頁，創(chuàng)作于2023年2月問題要求：設計一種裝車方案，使剩余的空間最小。下面介紹一種解法。1.問題的假設。⑴包裝箱不能能分割成較小的部分。10.2m圖7.7第30頁，課件共68頁，創(chuàng)作于2023年2月⑵所有的數(shù)據(jù)均是精確值，無任何測量誤差。⑶給出的解，均可進行實際操作（裝卸）。2.模型的建立以表示裝到第j（j=1，2）輛鐵路平板車上的類包裝箱的個數(shù)（1≤i≤7）；表示類型為的包裝箱的總件數(shù)；表示類型為的包裝箱每件重量；表示類型為的包裝箱每件厚度；S表示剩余的空間。我們的目的是使裝車剩下的空間最小。為此我們的模型為

第31頁，課件共68頁，創(chuàng)作于2023年2月s．t．(平板車1的長度限制)(平板車2的長度限制)(平板車1的載重量限制)(平板車2的載重量限制)(類包裝箱的件數(shù)限制)

（對、、三種型號包裝箱長度的特別限制）為整數(shù)第32頁，課件共68頁，創(chuàng)作于2023年2月對上述整數(shù)線性規(guī)劃問題，用分支定界法可以求得30個不同的解如下（沒有利用的空間為0.6cm）箱子類型1234567123456743533004443030429120045051304253310454302041912104605120415332046430104091220470511040533304743000平板車1平板車2第33頁，課件共68頁，創(chuàng)作于2023年2月箱子類型1234567123456737431005053230370521050911203643110515322036052205191110354312052532103505230529110034431305353200329130055050303191310560502030913205705010平板車1平板車2第34頁，課件共68頁，創(chuàng)作于2023年2月平板車1平板車2箱子類型1234567123456727432006053130264321061531202543220625311025053306291000244323063531001643310715302015433207253010144333073530000790020800631007640008032330069003081063000664010813232005640208232310第35頁，課件共68頁，創(chuàng)作于2023年2月3.模型的分析現(xiàn)在，我們分析求得的解是否是最優(yōu)解？考慮、、三種類型的箱子，它們有如下特別限制：、、類箱子的件數(shù)限制為（），記，，，并把已知的與（）代入，我們有

為整數(shù)

第36頁，課件共68頁，創(chuàng)作于2023年2月這個問題的解共有315個，其中使的最小值介于[292.2，302.7]的解有6個，列表如下：330302.1cm420298.8cm023296.0cm510295.5cm113292.7cm600292.2cm第37頁，課件共68頁，創(chuàng)作于2023年2月

可以看出對類型為、、三種類型的包裝箱，在所占空間（厚度）不能超過320.7cm的限制下，兩輛平板車只能裝運302.1cm寬度的包裝箱。此時類型和類型的包裝箱各裝3只，不裝類型的包裝箱。由

兩輛平板車裝運、、、四種類型的包裝箱的空間厚度為1737.3cm。從而總的裝運空間的厚度最多為302.1+1737.3=2039.4（cm）因此，裝運的剩余空間至少為2040-2039.4=0.6（cm）因此，我們求得的30個解均為最優(yōu)解。如果我們進一步要求這兩輛車裝運包裝箱后，使得剩余空間相同，此時的解即為如下兩個解：第38頁，課件共68頁，創(chuàng)作于2023年2月

注意到，最優(yōu)解不裝運類箱子?，F(xiàn)在，如果我們進一步要求每一種類型的包裝箱都必須裝運一部分，從表中可以看出此時兩輛平板車裝運的~類型包裝箱的只數(shù)分別為8、7、9、6、1、1、3。此時裝完兩輛平板車后，剩余的空間至少為2024-（292.7+1737.3）=10（cm）。平板車厚度重量第一輛10119.7340000790020第二輛10119.7330008006310第一輛10119.7330000690030第二輛10119.7340008106300第39頁，課件共68頁，創(chuàng)作于2023年2月

我們現(xiàn)在的目標函數(shù)是使平板車上沒有利用的空間最少，當然也可以把目標函數(shù)定義為兩輛平板車裝運的包裝箱的總重量最大，此時得到的解也將不同?！?0-1規(guī)劃及隱枚舉法

只取0或1值的變量稱為0-1變量。在實際生活中許多情況下的狀態(tài)僅有兩種，比如“開、關”，“上、下”，“投資該項目與不投資該項目”等等，通常要用到這種形式的變量來表示。將含有0-1變量的線性規(guī)劃稱為0-1規(guī)劃。首先建立兩個0-1規(guī)劃模型。例6（裝箱模型）某運輸公司打算用一個在重30噸重的貨物集裝箱裝運一批貨物。這些貨物的有關數(shù)據(jù)由下表給出。試問硬裝哪幾件貨物，才能使獲利最多？第40頁，課件共68頁，創(chuàng)作于2023年2月

解當集裝箱不裝第i件貨物時，令=0，否則令=1（i=1、2、3、4、5）。于是該模型為：貨物編號12345重量（噸）20181654利潤（百元）303520105s.t.

=0或1（j=1、2、3、4、5）第41頁，課件共68頁，創(chuàng)作于2023年2月

例7(投資模型)某公司擬在市東、西、南三區(qū)建立市部。擬議中7個位置（i=1~7）可供選擇：在東區(qū)，由，，三個點中至多選兩個；在西區(qū)，由，兩個點中之少選一個；在南區(qū)，由，兩個點中之少選一個；如果選用點，設備投資估計為元，每年可獲利潤為元，但投資總額不能超過B元。問應該選哪幾個點可使年利潤為最大？解當選點時，令，否則令（i=1~7）。則模型為：

第42頁，課件共68頁，創(chuàng)作于2023年2月

0-1規(guī)劃是整數(shù)規(guī)劃的特殊情況，可用前面介紹的方法求解，但有其變量取值的特性，它另有一種特殊的分值定界法——隱枚舉法，它也是通過求解線性松弛模型來獲得原整數(shù)規(guī)劃模型的最優(yōu)解的，不過這里恰好跟一般分值定界相反，是由放棄所有線性約束、只保留變量0-1約束而得到的。下面具體說明這種方法。隱枚舉法要求0-1規(guī)劃為下述標準形式：或第43頁，課件共68頁，創(chuàng)作于2023年2月其中，，約束條件必須為“”。當某一時，令，則

再令，原目標函數(shù)變?yōu)?/p>

從而使目標函數(shù)中個變量的系數(shù)變?yōu)榉秦摂?shù)?；虻?4頁，課件共68頁，創(chuàng)作于2023年2月

隱枚舉的解法思路與分值定界法有相似之處。利用變量只能取0或1進行分支。首先令全部變量取0值（當求最大值時，令全部變量取1值），檢驗解是否滿足約束條件。若均滿足，已得最優(yōu)解；若不全滿足，則令一個變量取值為0或1（此變量稱為固定變量），將模型分成兩個子模型，其余未被指定取值的變量稱為自由變量。由于，因此自由變量為0與固定變量組成的子模型的解使目標值最小。經(jīng)過幾次檢驗后，或停止分支，或者將另一個自由變量轉為固定變量，令其值為0或1，繼續(xù)分支。如此繼續(xù)進行，直至沒有自由變量或全部子模型停止分支為止，就求出最優(yōu)解。具體算法過程：第一步，將模型化為標準形式。第二步，令全部都是自由變量，且均取0值，第45頁，課件共68頁，創(chuàng)作于2023年2月檢驗解是否為可行解（即滿足所有約束條件）。若是可行解，則一定為最優(yōu)解；若不可行，進行第三步。第三步，將某一變量轉為固定變量，令其取值為0或1，使該模型（子模型）分成兩個子模型。其它變量均為自由變量，仍取0值。第四步，檢查已有的子模型，若子模型滿足下列條件之一，該子模型停止向下分支，繼續(xù)檢查其它子模型，直到所有子模型均檢查完畢，轉第五步；若有某一個子模型不滿足下列四個條件，則轉第三步。1.將自由變量均取0值與固定變量的值一起代入約束方程中，滿足所有約束條件，則為可行解，該模型停止向下分支。

第46頁，課件共68頁，創(chuàng)作于2023年2月2.若自由變量取任意值時，都不滿足某一約束條件，則該子模型無可行解，也停止向下分支。即將子模型固定變量的值代入約束條件方程中，令不等式左端的自由變量當系數(shù)為負時取值為1，系數(shù)為正時取值為0，得到左端所能取得的最小值，若此最小值大于右端值，說明此子模型無可行解。3.將自由變量均取0值與固定變量的值一起代入目標函數(shù)，得到的目標值大于已求得的可行解的目標值，則該子模型一定無更好的可行解，也停止向下分支。4.所有變量均為固定變量，則該子模型停止向下分支。第五步，在所有可行解中目標值最小的解，即為最優(yōu)解。第47頁，課件共68頁，創(chuàng)作于2023年2月例8求下列0-1規(guī)劃最優(yōu)解解將原模型記為，目標值，自由變量全取0值，顯然不是可行解。不妨取作為固定變量，在中增加約束條件記為，增加記為。模型中，其它為自由變量，均取0值，此時為可行解，停止分支。目標或第48頁，課件共68頁，創(chuàng)作于2023年2月

值，因此，原模型的最優(yōu)值的上界為8。模型不滿足算法中停止的條件，需繼續(xù)分支。將變?yōu)楣潭ㄗ兞?，于是模型分為兩個分支和，繼續(xù)考慮和。為了清晰的表達求解的過程，我們類似分值定界法，作出樹形圖（圖7.8），圖中黑體數(shù)字表示該變量為固定變量。

最優(yōu)解為，最優(yōu)值為。第49頁，課件共68頁，創(chuàng)作于2023年2月可行解，停止分支不可行，停止分支圖7.8第50頁，課件共68頁，創(chuàng)作于2023年2月可行解，停止分支不可行，停止分支目標值大于上界6，停止分支圖7.8第51頁，課件共68頁，創(chuàng)作于2023年2月§4指派模型及匈牙利法一、指派模型

許多管理部門可能經(jīng)常面臨這樣的問題：有若干項任務需要完成，又有若干對象能夠完成其中的每項任務。由于每個對象的特點與能力不同，完成各項任務的效益也各不相同。又因任務性質(zhì)的要求和管理上的要求等，應如何分配人員去完成所有任務，能使完成各項任務的總效益最佳或費用最??？這類問題就稱之為指派問題或分配問題。在指派問題中，作如下假設：1.被指派的人數(shù)與任務的數(shù)目相等，為n。2.每個被指派的人員只完成一個任務，而且每一個任務必有一個人去完成。第52頁，課件共68頁，創(chuàng)作于2023年2月

3.第i個被指派的人去完成第j項任務的費用為。指派問題的模型為C=（）為n階方陣，稱為指派模型（P）的效益矩陣；若為（P）的最優(yōu)解，則n階方陣稱為（P）的最優(yōu)解方陣。事實上方陣X為一置換方陣，即該矩陣中的每一行、每一列只有一個“1”。第53頁，課件共68頁，創(chuàng)作于2023年2月

二、匈牙利法

解決指派模型的方法是匈牙利數(shù)學家考尼格提出的。因此得名匈牙利法。1.匈牙利法基本原理。匈牙利法基于下面兩個基本性質(zhì)：性質(zhì)1設一個指派模型的效益矩陣為（）。若（）的第i行元素減去一個常數(shù)（i=1，2，…，n），第j列元素均減去一個常數(shù)（j=1，2，…，n），得到一個新的效益矩陣（），其中每一元素，則以（）為效益矩陣的最優(yōu)解也是以（）為效益矩陣的指派模型的最優(yōu)解。如果?。╥=1，2，…，n）為第i行元素的最小值，（j=1，2，…，n）為第j列元素的最小值，則第54頁，課件共68頁，創(chuàng)作于2023年2月得到一個新的效益矩陣（）為非負矩陣（即所有元素均為非負數(shù)）。性質(zhì)1說明可以通過求以（）為效益矩陣的指派模型的最優(yōu)解得到原指派模型的最優(yōu)解。直觀地講，求指派模型的最優(yōu)解方陣就是在效益矩陣中找到n個元素，要求在不同行、不同列上，使這些元素之和最小。江、將這n個元素所在位置賦值為“1”，其它元素均為“0”，就得到最優(yōu)解方陣。效益矩陣（）中最小元素為“0”，因此邱指派模型（P）的最優(yōu)解又轉化為在矩陣（）中找出n個在不同行、不同列上的“0”元素，就很容易的、構造出最優(yōu)解矩陣。性質(zhì)2若一方陣中的一部分元素為0，一部分元素為非0，則覆蓋方陣內(nèi)所有0元素的最少直線恰好等于那些位于不同行、不同列上的0元素的最多個數(shù)。第55頁，課件共68頁，創(chuàng)作于2023年2月此時存在兩個問題：第一，當效益矩陣階數(shù)n較大時，如何得知不存在n個位于不同行、不同列上的0元素，即如何得知覆蓋方陣內(nèi)所有0元素的最少直線數(shù)需要幾條？第二，賦予實際背景的指派模型，總存在最優(yōu)解。事實上任意一個指派模型均有最優(yōu)解。當確切得知不存在n個位于不同行、不同列上的0元素時，如何進一步按性質(zhì)1構造出新的效益矩陣，其中位于不同行、不同列上的0元素不斷增加，直至達到幾個？要解決第一個問題，我們需要引入兩個定義和一些性質(zhì)：定義1矩陣的積和式perA定義為：

第56頁，課件共68頁，創(chuàng)作于2023年2月其中（）取遍（1、2、…、n）的所有排列。積和式是矩陣的一個重要參數(shù)，在組合理論中經(jīng)常將積和式與其他參數(shù)建立聯(lián)系，它類似于矩陣的行列式，但又有很大的區(qū)別。行列式的計算方法有許多，但積和式的計算主要用拉普拉斯展開法，按某行（列）展開，直至到2階。例如計算下列3階矩陣的積和式時，按第一行展開，則轉化為計算三個2階矩陣的積和式。第57頁，課件共68頁，創(chuàng)作于2023年2月定義2稱D為C的補矩陣。若，滿足

性質(zhì)3設C為指派模型（P）的效益矩陣，D為C的補矩陣，覆蓋C中0元素所需要最小直線數(shù)為n的充要條件為。由性質(zhì)3得知，當指派模型（P）的效益矩陣或由性質(zhì)1所得效益矩陣對應的補矩陣D的積和式時，覆蓋效益矩陣內(nèi)0元素的最小直線數(shù)需要n條。因此性質(zhì)3也可以稱為效益矩陣迭代的終止條件。特別要指出的是當?shù)K止時，，且性質(zhì)4指派模型（P）最優(yōu)解的個數(shù)等于perD。第58頁，課件共68頁，創(chuàng)作于2023年2月對于第二個問題，我們可以按如下的方法處理。當確切得知效益矩陣中不存在n個位于不同行、不同列上的0元素時，一定可以用少于n條直線將所有“0”元素覆蓋。在未被直線覆蓋的所有元素中，找出最小元素，記為△；所有未被直線覆蓋的元素都減去△；覆蓋線十字交叉處元素即同時被兩條直線覆蓋的元素都加上△，其余元素不變。這一過程相當于將效益矩陣的每一行的所有元素均減去△，同時將被直線覆蓋的行（或列）上的所有元素均加上△。由性質(zhì)1保證最優(yōu)解矩陣不發(fā)生改變，同時在新的效益矩陣中位于不同行、不同列上的0元素個數(shù)得到增加。2.匈牙利方法步驟第一步