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

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

2.混合整數(shù)線性規(guī)劃（MixedIntegerLinearProgramming）

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

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

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

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

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

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

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

繼續(xù)對問題LP-1，LP-2進(jìn)行分枝。先對目標(biāo)函數(shù)值大的進(jìn)行分枝，即分別將

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

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

在對問題LP-2進(jìn)行分枝,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管理運(yùn)籌學(xué)課程組399于是得到原整數(shù)規(guī)劃問題的最優(yōu)解為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整個(gè)過程如下:2023/6/7管理運(yùn)籌學(xué)課程組3910步驟:1求解相應(yīng)的線性規(guī)劃問題的最優(yōu)解和最優(yōu)值,如果a)沒有可行解,停止;b)若有滿足整數(shù)條件的最優(yōu)解,則已得到整數(shù)規(guī)劃問題的最優(yōu)解,停止;c)若有最優(yōu)解,但不滿足整數(shù)條件,記此最優(yōu)值為原整數(shù)規(guī)劃問題Z*的上界,然后,用觀察法求出下界.2分枝、定界，直到得到最優(yōu)解為止。

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

1在計(jì)算過程中，若已得到一個(gè)整數(shù)可行解x(0)，其相應(yīng)的目標(biāo)函數(shù)值為Z0，那么在計(jì)算其它分枝過程中，如果解某一線性規(guī)劃所得的目標(biāo)函數(shù)值Z<Z0，即可停止計(jì)算。因?yàn)檫M(jìn)一步的分枝結(jié)果的最優(yōu)值只能比Z更差。

2若有若干個(gè)待求解的分枝，先選哪一個(gè)待求解的分枝呢？選取目標(biāo)函數(shù)值最大的那一枝。

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

1x2=16/5剪掉

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

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

可供選擇。規(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元，每年可獲利潤估計(jì)為ci元，但投資總額不能超過B元。問應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤為最大？2023/6/7管理運(yùn)籌學(xué)課程組3924解題時(shí)先引入0－1變量令問題可列成2023/6/7管理運(yùn)籌學(xué)課程組39252．相互排斥的約束條件

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

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

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

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

在生活中經(jīng)常遇到這樣的問題，某單位需完成項(xiàng)任務(wù)，恰好有個(gè)人可以承擔(dān)這些任務(wù)。由于每人的專長不同，各人完成任務(wù)不同（或所費(fèi)時(shí)間），效率也不同。于是產(chǎn)生應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成項(xiàng)任務(wù)的總效率最高（或所需總時(shí)間最小）。這類問題稱為指派問題或分派問題（assignmentproblem）。

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

2023/6/7管理運(yùn)籌學(xué)課程組3935

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

指派問題是0-1規(guī)劃的特例，也是運(yùn)輸問題的特例2023/6/7管理運(yùn)籌學(xué)課程組39372匈牙利算法

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

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

2023/6/7管理運(yùn)籌學(xué)課程組39483非標(biāo)準(zhǔn)的指派問題

標(biāo)準(zhǔn)的指派問題:“任務(wù)”數(shù)目和“人員”數(shù)目相等的極小化指派問題對于非標(biāo)準(zhǔn)指派問題，通常先將其轉(zhuǎn)化成標(biāo)準(zhǔn)的指派問題，然后再用匈牙利算法求解。對于“任務(wù)”和“人員”數(shù)目不等的指派問題，若“人員”數(shù)N1小于“任務(wù)”數(shù)N2，則添上N2-N1個(gè)虛擬的“人員”，這些虛擬“人員”完成每一項(xiàng)“任務(wù)”的費(fèi)用為0。如果指派方案中某項(xiàng)目“任務(wù)”由虛擬人員來完成，則實(shí)際上選擇該項(xiàng)目未執(zhí)行。若“人員”數(shù)N1大于“任務(wù)”數(shù)N2

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