2023/6/7管理運籌學課程組391第一節問題的提出例5-1：某工廠有資金13萬元用于購置新機器，可在兩種機器中任意選購。已知機器A每臺購置費2萬元，B為4萬元。該廠維修能力只能維修7臺機器B；若維修機器A，1臺折算機器B2臺。已知一臺A可增加年產值6萬元，1臺B可增加年產值4萬元，問應購置A和B各多少臺才能使年產值增加最多？

第五章整數規劃（IntegerProgramming)分類：1.純整數線性規劃（PureIntegerLinearProgramming）

2.混合整數線性規劃（MixedIntegerLinearProgramming）

3.0-1型整數線性規劃（Zero-OneIntegerLinearProgramming）2023/6/7管理運籌學課程組392解：設x1，x2分別表示兩種A、B兩種機器的購置臺數，根據實際機器臺數應為整數，故該問題的優化模型為上述規劃問題是整數規劃問題。放松整數約束的整數規劃就成為線性規劃，此線性規劃被稱之為整數規劃的線性規劃松弛問題。這樣，任何一個整數規劃可以看成是一個線性規劃再加上整數約束構成的。2023/6/7管理運籌學課程組393整數規劃問題的求解以例5-1為例，圖解法最優解為可行解2023/6/7管理運籌學課程組394

整數規劃的所有可行解包含在線性規劃松弛問題的可行域內。因此，整數規劃可行解的數量大大小于線性規劃松弛問題可行解的數量，這一事實也給出了整數規劃最優解和線性規劃松弛問題最優解的下述關系：松弛問題的最優解值≥整數規劃最優解值（對max問題）松弛問題的最優解值≤整數規劃最優解值（對min問題）如果線性規劃松弛問題的可行域有界的話，整數規劃可行解的數量是有限的。理論上講，這樣的整數規劃問題可以通過計算和比較所有整數點的目標函數值來求解，這種方法稱為窮舉法。缺點：窮舉法的計算量很大無法用來求解實際問題2023/6/7管理運籌學課程組395第二節分枝定界法(BranchandBoundmethod)引言：窮舉法對小規模的問題可以。大規模問題則不行，如指派問題

n個人指派n件事，共有n！中指派方案。一、基本思想和算法依據

基本思想是：先求出相應的線性規劃最優解，若此解不符合整數條件，那么其目標函數的值就是整數規劃問題最優值的上界，而任意滿足整數條件的可行解的目標函數值將是其下界（定界），然后將相應的線性規劃問題進行分枝，分別求解后續的分枝問題。如果后續分枝問題的最優值小于上述下界,則剪掉此枝;如果后續某一分枝問題的最優解滿足整數條件，且其最優值大于上述下界，則用其取代上述下界，繼續考慮其它分枝，直到最終求得最優的整數解。

算法的依據在于：“整數規劃的最優解不會優于相應的線性規劃問題的最優解”。具體說就是，對極大化問題，與整數規劃問題相應的線性規劃問題的目標函數值，是該整數規劃問題目標函數的上界；任何滿足整數條件的可行解的目標函數值將是其下界。2023/6/7管理運籌學課程組396二、具體步驟（以例子說明）

解：第一步：先不考慮整數約束條件，求解相應的線性規劃問題，得最優解和最優值如下x1=4.81,x2=1.82,Z=356

此解不滿足整數解條件。定出整數規劃問題目標函數的上下界。上界為Z=356；用觀察法可知x1=0，x2=0是可行解，從而其整數規劃問題目標函數的下界應為0，即0Z*356例5-22023/6/7管理運籌學課程組3979x1+7x2=567x1+20x2=70Z=40x1+90x2LP-1LP-2第二步：分枝與定界過程。將其中一個非整數變量的解，比如x1,進行分枝，即x1[4.81]=4,x1[4.81]+1=5并分別加入LP問題的約束條件中,得兩個子LP規劃問題LP-1,LP-2,分別求解此兩個子線性規劃問題,其最優解分別是LP-1:x1=4,x2=2.1,Z1=349LP-2:x1=5,x2=1.57,Z2=3412023/6/7管理運籌學課程組398沒有得到全部決策變量均是整數的解。再次定出上下界0Z*349

繼續對問題LP-1，LP-2進行分枝。先對目標函數值大的進行分枝，即分別將

x2[2.1]=2,x2[2.1]+1=3加入到約束條件中去,得子問題LP-3,LP-4,分別求解得問題LP-3的所有解均是整數解,而問題LP-4還有非整數解,但由于Z3>Z4,對LP-4分枝已沒有必要，剪掉。LP-3:x1=4,x2=2,Z3=340（是整數解，定下界）

LP-4:x1=1.42,x2=3,Z4=327（剪掉）上下界為340Z*349

在對問題LP-2進行分枝,x2[1.57]=1，x2[1.57]+1=2,得子問題LP-5,LP-6,求解得LP-5:x1=5.44,x2=1,Z5=308(下界340,剪掉)LP-6:無可行解（剪掉）2023/6/7管理運籌學課程組399于是得到原整數規劃問題的最優解為LP:x1=4,x2=2,Z3=340x1=4.81LP:x2=1.82Z=356LP-1:x1=4x1

4x2=2.1Z=349LP-2:x1=5x15x2=1.57Z=341LP-3:x1=4x1

4x2=2x2

2Z=340LP-6x15無可行解剪掉

x22LP-4:x1=1.42x1

4x2=3剪掉x2

3Z=327LP-5:x1=5.44x15x2=1剪掉x2

1Z=308整個過程如下:2023/6/7管理運籌學課程組3910步驟:1求解相應的線性規劃問題的最優解和最優值,如果a)沒有可行解,停止;b)若有滿足整數條件的最優解,則已得到整數規劃問題的最優解,停止;c)若有最優解,但不滿足整數條件,記此最優值為原整數規劃問題Z*的上界,然后,用觀察法求出下界.2分枝、定界，直到得到最優解為止。

a）在以后的各枝中，若某一子規劃問題的最優解滿足整數條件，則用其最優值置換Z*的下界。b）若某一分枝的最優值小于Z*的下界，則剪掉此枝，即以后不在考慮此枝2023/6/7管理運籌學課程組3911三、算法需要注意的幾點（以極大化問題為例）

1在計算過程中，若已得到一個整數可行解x(0)，其相應的目標函數值為Z0，那么在計算其它分枝過程中，如果解某一線性規劃所得的目標函數值Z<Z0，即可停止計算。因為進一步的分枝結果的最優值只能比Z更差。

2若有若干個待求解的分枝，先選哪一個待求解的分枝呢？選取目標函數值最大的那一枝。

2023/6/7管理運籌學課程組3912例求下列整數規劃問題的解2023/6/7管理運籌學課程組3913不考慮整數約束X1=5/2X2=2Z=23x12x13LP1LP22023/6/7管理運籌學課程組3914Z=212023/6/7管理運籌學課程組3915Z=222023/6/7管理運籌學課程組3916不考慮整數約束X1=5/2X2=2Z=23第1個子問題X1=2X2=9/4Z=21第2個子問題X1=3X2=1Z=22x12x132023/6/7管理運籌學課程組3917練習：用分支定界法求解下述整數規劃問題x1=5/3LP:x2=8/3Z=44/3LP-1:x1=1x1

1x2=16/5剪掉

Z=68/5LP-2:x1=2x12x2=2Z=142023/6/7管理運籌學課程組3918第三節割平面解法(CuttingPlaneApproach)

割平面法是1958年美國學者R.E.Gomory提出的。基本思想是：先不考慮變量的取整數約束，求解相應的線性規劃，然后不斷增加線性約束條件（即割平面），將原可行域割掉不含整數可行解的一部分，最終得到一個具有整數坐標頂點的可行域，而該頂點恰好是原整數規劃問題的最優解。例5-3：求解2023/6/7管理運籌學課程組3919解：最優單純形表如下cj8500CBXBx1x2x3x45x21.5010.25-0.258x13.75100.1250.37500-2.25-1.75z=37.5最優解兩個基變量都不滿足整數要求。為加入一個新的割約束，從非整數基變量對應的約束中任選一個。假定選上表中第二個約束，該約束可表為2023/6/7管理運籌學課程組3920即割平面方程85000CBXBx1x2x3x4x55x21.5010.25-0.2508x13.75100.1250.37500x5-600-1-3100-2.25-1.7505x22011/30-1/128x1310001/80x42001/31-1/300-1.6670-7/122023/6/7管理運籌學課程組3921經過一次迭代后得到最優整數解將松弛變量代入割平面方程得等價的切割方程割平面方程2023/6/7管理運籌學課程組3922割平面方程的特征：新加入的約束不會割去任何整數解，也即，原問題的所有整數解滿足新的割約束。線性規劃松弛問題的最優解不滿足新的割約束。以上例說明。割約束的作用也可從上圖中看出：所有的整數解滿足新加入的割約束，而松弛問題的最優解和臨近的一部分可行域被排除在新的可行域之外。這樣不斷迭代下去，總可以在有限的迭代內找到最優整數解。應用較少。2023/6/7管理運籌學課程組3923第四節0-1型整數規劃0－1型整數規劃是整數規劃中的特殊情形，它的變量xi僅取值0或1。這時xi稱為0－1變量，或稱二進制變量。xi僅取值0或1這個條件可由下述約束條件所代替。整數4.1.引入0-1變量的實際問題1．投資場所的選定——相互排斥的計劃例5-4某公司擬在市東、西、南三區建立門市部。擬議7個位置（點）Ai

可供選擇。規定：在東區，由A1，A2，A3三個點中至多選兩個；在西區，由A4，A5兩個點中至少選一個；在南區，由A6，A7兩個點中至少選一個。如選用Ai點，設備投資估計為bi元，每年可獲利潤估計為ci元，但投資總額不能超過B元。問應選擇哪幾個點可使年利潤為最大？2023/6/7管理運籌學課程組3924解題時先引入0－1變量令問題可列成2023/6/7管理運籌學課程組39252．相互排斥的約束條件

如果有m個互相排斥的約束條件（<=型）：為了保證這個約束條件只有一個起作用，我們引入m個0－1變量和一個充分大的常數M，而下面這一組m+1個約束條件符合要求2023/6/7管理運籌學課程組39263．關于固定費用的問題（fixedcostproblem）

例5-5某工廠為了生產某種產品，有幾種不同的生產方式可供選擇，如選定投資高的生產方式（選購自動化程度高的設備），由于產量大，因而分配到每件產品的變動成本就降低；反之，如選定投資低的生產方式，將來分配到每件產品的變動成本可能增加，所以必須全面考慮。今設有三種方式可供選擇，令xj表示采用第j種方式時的產量；cj表示采用第j種方式時每件產品的變動成本；kj表示采用第j種方式時的固定成本。采用各種生產方式的總成本分別為j=1,2,32023/6/7管理運籌學課程組3927引入0-1變量yi，令（5-13）（5-14）式（5-13）可由（5-14）表示，M是個充分大的常數。（5-14）說明當時，yj必須為1，當時，只有yj為0才有意義。2023/6/7管理運籌學課程組39284.2.0-1整數規劃的解法全枚舉法：檢查每個變量等于0或1的所有組合，滿足所有約束條件并使目標函數值最優的組合就是0-1規劃的最優解。如0-1變量有n個，需要檢查個變量組合。當n>15時，這幾乎是不可能的。隱枚舉法：0-1規劃模型必須是下述標準型：2023/6/7管理運籌學課程組3929如果0-1規劃模型不是標準型式，則可作下述變換，使其成為標準型式：1．如目標函數是求最大，可將目標函數乘-1并求最小；2．如約束條件方程是“≥”型式，可將不等式兩端乘-1，變換為“≤”型式；3．如約束條件是“＝”型式，則將它變換為一個“≤”型式和一個“≥”型式的約束條件方程，并對后一方程兩端乘-1，使其成為“≤”型式；4．如果有一個變量的目標函數系數<0，則可用1-替換。例如：2023/6/7管理運籌學課程組3930

解問題的思路與解整數規劃的分枝定界法有相似之處，利用變量只能取0或1兩個值的特性，進行分枝。首先令全部變量取0值，檢驗解是否可行。若可行，z=0,已得最優解；若不可行，則令一個變量取值為0或1（此變量稱為固定變量），將問題分成兩個子域，其余未被指定取值的變量稱為自由變量。由于這些自由變量在目標函數中的系數都是正數，因此令自由變量為0與固定變量組成的子域的解使目標函數值最小。經過幾次檢驗，或者停止分枝，或者將第二個自由變量轉為固定變量，令其值為0或1，將此子域再分成兩個子域。如此繼續進行，直至沒有自由變量或全部子域停止分枝為止，就求出最優解。

具體步驟參考課本。2023/6/7管理運籌學課程組3931例5-6解：枚舉樹如下2023/6/7管理運籌學課程組39322023/6/7管理運籌學課程組39332023/6/7管理運籌學課程組3934第五節指派問題1指派問題的數學模型

在生活中經常遇到這樣的問題，某單位需完成項任務，恰好有個人可以承擔這些任務。由于每人的專長不同，各人完成任務不同（或所費時間），效率也不同。于是產生應指派哪個人去完成哪項任務，使完成項任務的總效率最高（或所需總時間最小）。這類問題稱為指派問題或分派問題（assignmentproblem）。

例5-7有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作E、J、G、R。現有甲、乙、丙、丁四人，他們將中文說明書翻譯成不同語種的說明書所需時間如下表所示。問應指派何人去完成何工作，能使所需總時間最少？

2023/6/7管理運籌學課程組3935

任務人員EJGR甲215134乙1041415丙9141613丁78119類似有：有n項加工任務，怎樣指派到n臺機床上分別完成的問題：有n條航線，怎樣指定n艘船去航行的問題……效率矩陣或系數矩陣效率矩陣的元素表示指派第i人去完成第j項任務時的效率（或時間、成本等）。引入變量；其取值只能是1或0。并令2023/6/7管理運籌學課程組3936數學模型可行解矩陣第j項任務只能由1人完成第i人只能完成1項任務解矩陣中各行各列的元素之和都是1

指派問題是0-1規劃的特例，也是運輸問題的特例2023/6/7管理運籌學課程組39372匈牙利算法

指派問題最優解的性質：若從系數矩陣的一行（列）各元素中分別減去該行（列）的最小元素，得到新矩陣，那么以為系數矩陣求得的最優解和用原系數矩陣求解的最優解相同。庫恩（W.W.Kuhn）于1955年提出了指派問題的解法，他引用了匈牙利數學家康尼格（D.Konig）一個關于矩陣中0元素的定理：系數矩陣中獨立0元素的最多個數等于能覆蓋所有0元素的最少直線數。這解法稱為匈牙利法。以例5-7為例說明指派問題的解法2023/6/7管理運籌學課程組39382023/6/7管理運籌學課程組3939第二步：進行試指派，以尋求最優解。按以下步驟進行。經第一步變換后，系數矩陣中每行每列都已有了0元素；但需找出n個獨立的0元素。若能找出，就以這些獨立0元素對應解矩陣中的元素為1，其余為0，這就得到最優解。當n較小時，可用觀察法、試探法去找出n個獨立0元素；若n較大時，就必須按一定的步驟去找，常用的步驟為：（1）從只有一個0元素的行（列）開始，給這個0元素加圈，記作。這表示對這行所代表的人，只有一種任務可指派。然后劃去所在列（行）的其他0元素，記作。這表示這列所代表的任務已指派完，不必再考慮別人了。（2）給只有一個0元素列（行）的0元素加圈，記作；然后劃去所在行（列）的0元素，記作。2023/6/7管理運籌學課程組3940（3）反復進行（1），（2）兩步，直到所有0元素都被圈出和劃掉為止。（4）若仍有沒有劃圈的0元素，且同行（列）的0元素至少有兩個（表示對這個可以從兩項任務中指派其一）。這可用不同的方案去試探。從剩有0元素最少的行（列）開始，比較這行各0元素所在列中0元素的數目，選擇0元素少的那列的這個0元素加圈（表示選擇性多的要“禮讓”選擇性少的），然后劃掉同行同列的其他0元素。可反復進行，直到所有0元素都已圈出和劃掉為止。（5）若元素的數目m等于矩陣的階數n，那么這指派問題的最優解已得到，若，則轉入下一步。2023/6/7管理運籌學課程組3941現用例5-7的矩陣，按上述步驟進行運算，得到可見，所以得最優解為這表示：指定甲譯出俄文，乙譯出日文，丙譯出英文，丁譯出德文。所需總時間最少2023/6/7管理運籌學課程組3942例5-8求下表所示效率矩陣的指派問題的最小解。

任務人員ABCDE甲127979乙89666丙71712149丁15146610戊4107109將系數矩陣進行變換min2023/6/7管理運籌學課程組3943經依次運算即得每行每列都有0元素得系數矩陣，再按上述步驟運算，得到的個數m=4，而n=5，所以解題沒有完成，這時應按以下步驟繼續進行。①2023/6/7管理運籌學課程組3944第3步：作最少的直線覆蓋所有0元素，以確定該系數矩陣中能找到最多的獨立元素數。（1）對沒有的行打√號；（2）對已打√號的行中所有含元素的列打√號；（3）再對打有√號的列中含元素的行打√號；（4）重復（2），（3）直到得不出新得打√號的行、列為止；（5）對沒有打√號的行畫一橫線，有打√號的列畫一縱線，這就得到覆蓋所有0元素的最少直線數。令此直線數為l。若，說明必須再變換當前的系數矩陣，才能找到n個獨立的0元素，為此轉第4步；若，而，應回到第2步（4），另行試探。2023/6/7管理運籌學課程組3945對本例：先在第5行旁打√，接著可判斷應在第1列下打√，接著在第3行旁打√。經檢查不能再打√了。對沒有打√行，畫一直線以覆蓋0元素，已打√的列畫一直線以覆蓋0元素，得由此可見，所以應繼續對②矩陣進行變換，轉第3步。②2023/6/7管理運籌學課程組3946第4步：對②矩陣進行變換的目的是增加0元素。為此在沒有被直線覆蓋的部分中找出最小元素，然后在打√行各元素中都減去這最小元素，而在打√列的各元素都加上這最小元素，以保證原來0元素不變。這樣得到新系數矩陣（它的最優解和原問題相同），若得到n個獨立的0元素，則已得最優解，否則回到第2步重復進行。在例5-8的矩陣②中，在沒有被覆蓋部分（第3、5行）中找出最小元素為2，然后在第3、5行各元素分別減去2，給第1列各元素加2，得到新矩陣③。按第2步，找出所有獨立的0元素，得到矩陣④。③④2023/6/7管理運籌學課程組3947它具有n個獨立0元素。此時得到了最優解，相應的解矩陣為由解矩陣得最優指派方案甲－B，乙－D，丙－E，丁－C，戊－A本例還可以得到另一最優指派方案甲－B，乙－C，丙－E，丁－D，戊－A所需總時間為當指派問題的系數矩陣，經過變換得到了同行和同列中都有兩個或兩個以上0元素時，這時可以任選一行（列）中某一個0元素，再劃去同行（列）的其他0元素，這時會出現多重解。

2023/6/7管理運籌學課程組39483非標準的指派問題

標準的指派問題:“任務”數目和“人員”數目相等的極小化指派問題對于非標準指派問題，通常先將其轉化成標準的指派問題，然后再用匈牙利算法求解。對于“任務”和“人員”數目不等的指派問題，若“人員”數N1小于“任務”數N2，則添上N2-N1個虛擬的“人員”，這些虛擬“人員”完成每一項“任務”的費用為0。如果指派方案中某項目“任務”由虛擬人員來完成，則實際上選擇該項目未執行。若“人員”數N1大于“任務”數N2

，則添上N1-N2個虛擬“任務”，這些虛擬“任務”被各“人員”完成的費用也取0。同樣，如果指派方案中某人員去完成虛擬任務，則說明該人員是空閑的。在指派問題中，如果某“人員”可以承擔多項“任務”，則相應將該“人員”看作相同的多個“人員”，這幾個“人員”完成同一項“任務”的費用是相同的。如果某一“人員”一定不能承擔某一“任務”，則相應的費用取值為足夠大的正數M