教案_整數(shù)規(guī)劃

1、第一節(jié)第一節(jié) 問題的提出問題的提出 例子：某廠擬采用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲利潤以及托運(yùn)所受限制如下表貨物體積每箱（m3）重量每箱（噸）利潤每箱（百元）甲424乙513托運(yùn)限制206問兩種貨物托運(yùn)多少箱，可使獲得利潤為最大？第五章 整數(shù)規(guī)劃（Integer Programming)分類：1. 純整數(shù)線性規(guī)劃（Pure Integer Linear Programming） 2. 混合整數(shù)線性規(guī)劃（Mixed Integer Linear Programming） 3. 0-1型整數(shù)線性規(guī)劃（Zero-One Integer Linear Programming）解：設(shè)x1

2、，x2分別表示兩種貨物托運(yùn)的箱數(shù)，那么其線性規(guī)劃為取整數(shù),0,622054.34max2121212121xxxxxxxxtsxxZ0,622054.34max21212121xxxxxxtsxxZ可得最優(yōu)解為x*=（5/3，8/3)T。 如果選用“向上湊整”的方法可得到x(1)=(2,3)T, 則此時(shí)已破壞了體積約束, 超出可行域的范圍; 如果“舍去小數(shù)”可得x(2)=(1,2)T, 則此時(shí)雖是可行解, 值為10，不是最優(yōu)解, 因?yàn)楫?dāng)x*=(2,2)T是, 其利潤為14.由于托運(yùn)的箱數(shù)不能為分?jǐn)?shù)，故上述規(guī)劃問題是整數(shù)規(guī)劃問題。若不考慮整數(shù)約束，其相應(yīng)的線性規(guī)劃問題為LP-1：第二節(jié)第二節(jié) 分

3、枝定界法分枝定界法(Branch and Bound method)引言：窮舉法對小規(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)

4、的整數(shù)解。 算法的依據(jù)算法的依據(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ù)值將是其下界。二、具體步驟（以例子說明）取整數(shù),0,702075679.9040max2121212121xxxxxxxxtsxxZ 解： 第一步：先不考慮整數(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

5、是可行解，從而其整數(shù)規(guī)劃問題目標(biāo)函數(shù)的下界應(yīng)為0，即0 Z* 3569x1+7x2=567x1+20 x2=70Z=40 x1+90 x2LP-1LP-2第二步：分枝與定界過程。 將其中一個(gè)非整數(shù)變量的解，比如x1, 進(jìn)行分枝，即x14.81=4, x14.81+1=5并分別加入LP問題的約束條件中, 得兩個(gè)子LP規(guī)劃問題LP-1, LP-2, 分別求解此兩個(gè)子線性規(guī)劃問題, 其最優(yōu)解分別是LP-1: x1=4, x2=2.1, Z1=349 LP-2: x1=5, x2=1.57, Z2=341沒有得到全部決策變量均是整數(shù)的解。再次定出上下界0 Z* 349 繼續(xù)對問題LP-1，LP-2進(jìn)行

6、分枝。先對目標(biāo)函數(shù)值大的進(jìn)行分枝，即分別將 x22.1=2, x22.1+1=3加入到約束條件中去, 得子問題LP-3, LP-4, 分別求解得問題LP-3的所有解均是整數(shù)解, 而問題LP-4還有非整數(shù)解, 但由于 Z3Z4, 對LP-4分枝已沒有必要，剪掉。 LP-3: x1=4, x2=2, Z3=340 （ 是整數(shù)解，定下界） LP-4: x1=1.42, x2=3, Z4=327（剪掉）上下界為 340 Z* 349 在對問題LP-2進(jìn)行分枝, x2 1.57=1， x21.57+1=2, 得子問題LP-5, LP-6, 求解得LP-5: x1=5.44, x2=1, Z5=308 (

7、下界340, 剪掉) LP-6: 無可行解（剪掉）于是得到原整數(shù)規(guī)劃問題的最優(yōu)解為LP: x1=4, x2=2, Z3=340 x1=4.81LP: x2=1.82 Z=356LP-1: x1=4x1 4 x2=2.1 Z=349LP-2: x1=5x15 x2=1.57 Z=341LP-3: x1=4x1 4 x2=2x2 2 Z=340LP-6 x15 無可行解 剪掉 x22LP-4: x1=1.42x1 4 x2=3 剪掉x2 3 Z=327LP-5: x1=5.44x15 x2=1 剪掉x2 1 Z=308整個(gè)過程如下:步驟: 1 求解相應(yīng)的線性規(guī)劃問題的最優(yōu)解和最優(yōu)值, 如果a) 沒

8、有可行解, 停止; 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*的下界，則剪掉此枝，即以后不在考慮此枝三、算法需要注意的幾點(diǎn)（以極大化問題為例） 1 在計(jì)算過程中，若以得到一個(gè)整數(shù)可行解x(0)，其相應(yīng)的目標(biāo)函數(shù)值為Z0，那么在計(jì)算其它分枝過程中，如果解某一線性規(guī)劃所得的目標(biāo)函數(shù)值ZZ0，即可停止計(jì)算。因?yàn)?/p>

9、進(jìn)一步的分枝結(jié)果的最優(yōu)值只能比Z更差。2 若有若干個(gè)待求解的分枝，先選那一個(gè)待求解的分枝呢？選取目標(biāo)函數(shù)值最大的那一枝。 例 求下列整數(shù)規(guī)劃問題的解取整數(shù),0,721342.46max2121212121xxxxxxxxtsxxZ cj 6 4 0 0 CB XB b x1 x2 x3 x4 4 6 x2 x1 2 5/2 0 1 1 0 1/3 -1/6 -1/3 2/3 初始表 0 0 0 -1/3 8/3 不考慮整數(shù)約束X1=5/2X2=2Z=23x1 2x1 3LP1LP2cj 6 4 0 0 0 CB XB b x1 x2 x3 x4 x5 4 6 0 X2 X1 X5 2 5/2

10、-1/2 0 1 0 1 0 0 1/3 -1/6 1/6 -1/3 2/3 -2/3 0 0 1 0 0 -1/3 -8/3 0 cj 6 4 0 0 0 CB XB b x1 x2 x3 x4 x5 4 6 0 X2 X1 X4 9/4 2 3/4 0 1 0 1 0 0 1/4 0 -1/4 0 0 1 -1/2 1 -3/2 0 0 -1 0 -4 Z=21cj 6 4 0 0 0 CB XB b x1 x2 x3 x4 x5 4 6 0 X2 X1 X5 2 5/2 -1/2 0 1 0 1 0 0 1/3 -1/6 -1/6 -1/3 2/3 2/3 0 0 1 0 0 -1/3

11、-8/3 0 cj 6 4 0 0 0 CB XB b x1 x2 x3 x4 x5 4 6 0 X2 X1 X5 1 3 3 0 1 0 1 0 0 0 0 1 1 0 -4 2 -1 -6 0 0 0 -4 -2 Z=22不考慮整數(shù)約束X1=5/2X2=2Z=23第1個(gè)子問題X1=2X2=9/4Z=21第2個(gè)子問題X1=3X2=1Z=22x1 2x1 3練習(xí)：用分支定界法求解下述整數(shù)規(guī)劃問題取整數(shù),0,622054.34max2121212121xxxxxxxxtsxxZ x1=5/3LP: x2=8/3 Z=44/3LP-1: x1=1x1 1 x2=16/5 剪掉 Z=68/5LP-2

12、: x1=2x12 x2=2 Z=14第三節(jié)第三節(jié) 割平面解法割平面解法(Cutting Plane Approach) 割平面法是1958年美國學(xué)者R. E. Gomory提出的。 基本思想是：先不考慮變量的取整數(shù)約束，求解相應(yīng)的線性規(guī)劃，然后不斷增加線性約束條件（即割平面），將原可行域割掉不含整數(shù)可行解的一部分，最終得到一個(gè)具有整數(shù)坐標(biāo)頂點(diǎn)的可行域，而該頂點(diǎn)恰好是原整數(shù)規(guī)劃問題的最優(yōu)解。 例：求解取整數(shù),0,431.max2121212121xxxxxxxxtsxxZ加松弛變量x3、x4，使其變成標(biāo)準(zhǔn)形（如有非整數(shù)的系數(shù)，則將其所在的方程乘以某一常數(shù)，變成具有整數(shù)系數(shù)的約束方程），用單純形

13、法求解得cj1100CBXBbx1x2x3x400 x3x414-13111001初始表0110011x1x23/47/41001-1/43/41/41/4最終表-2/500-1/2-1/2最優(yōu)解x1=3/4，x2=7/4，x3=x4=0，最優(yōu)值為Z=5/2，是非整數(shù)解。 尋求割平面：由最終表得x1 - 1/4x3 + 1/4x4 = 3/4x2 + 3/4x3 + 1/4x4 = 7/4任選一取分?jǐn)?shù)值的基變量，比如x1，將該式中所有變量的系數(shù)、右端常數(shù)項(xiàng)均改寫成整數(shù)與非負(fù)真分?jǐn)?shù)之和的形式，并移項(xiàng)得x1 - x3 = 3/4 -（3/4x3 + 1/4x4）（注（注：所有的x均是整數(shù)。x3、x

14、4可通過在原約束條件中乘以某一常數(shù)變成整數(shù)。）則整數(shù)約束條件可由下式替代 3/4 -（3/4x3 + 1/4x4）0 即得割平面方程-3x3 - x4 -3引入松弛變量x5，將其加入到原規(guī)劃的約束條件中，利用上述最終表得左邊項(xiàng)必是整數(shù)；0(3/4x3+1/4x4) 3/4內(nèi)不包含任何整數(shù)-1+3/4cj11000CBXBbx1x2x3x4x500 x3x414-13111001初始表01100110 x1x2x53/47/4-3100010-1/43/4-31/41/4-1001最終表-5/200-1/2-1/20用對偶單純形算法進(jìn)行計(jì)算。x5作換出變量，x3換入變量，迭代得cj11000CB

15、XBbx1x2x3x4x5110 x1x2x31111000100011/301/31/121/4-1/3-2000-1/3-1/6已得到整數(shù)解，最優(yōu)解為x1=1，x2=1，最優(yōu)值為2。注：新約束-3x3-x4 -3的幾何意義。 用x1，x2表示上述約束，得 x2 1，其圖形見下圖。3x1+x2=4-x1+x2=1x2 1求切平面的基本步驟： 1 令xi是相應(yīng)線性規(guī)劃問題最優(yōu)解中為分?jǐn)?shù)解的一個(gè)基變量，由單純形最終表得到 xi+aikxk=bi，其中i為基變量的標(biāo)號；k為非基變量的標(biāo)號。 2 將bi和aik都分解成整數(shù)部分N與非負(fù)分?jǐn)?shù)部分f之和，即 bi=Ni+fi， 其中0fi1 aik=Ni

16、k+fik, 其中0fik00 xj =0Min Z=(K1y1+c1x1 )+ （K2y2+c2x2 ）+（K3y3+c2x2 ）xj yjM 若有n個(gè)決策變量, 則可以產(chǎn)生2n個(gè)可能變量的組合, 故完全枚舉是不可能的. 求解0-1整數(shù)規(guī)劃問題的解法均是部分枚舉法或稱為隱枚舉法(Implicit enumeration) 基本思想基本思想是: 在2n個(gè)可能的變量組合中, 往往只有一部分是可行解. 只要發(fā)現(xiàn)某個(gè)變量組合不滿足其中的某一約束條件時(shí), 就不必要檢驗(yàn)其它的約束條件是否可行。 若發(fā)現(xiàn)一個(gè)可行解, 則根據(jù)它的目標(biāo)函數(shù)值可以產(chǎn)生一個(gè)過濾條件(Filtering constraint), 對

17、于目標(biāo)函數(shù)值比它差的的變量組合就不必再去檢驗(yàn)它的可行性（類似分支定界法中的定界。實(shí)際上，隱枚舉法是一種特殊的分支定界法）。 在以后求解過程中, 每當(dāng)發(fā)現(xiàn)比原來更好的可行解, 則依次替代原來的過濾條件 (可減少運(yùn)算次數(shù), 較快地發(fā)現(xiàn)最優(yōu)解)。0-1整數(shù)規(guī)劃問題的解法整數(shù)規(guī)劃問題的解法10,6434422.523max3213221321321321orxxxxxxxxxxxxxtsxxxZ以例子說明上述求解方法例1: 求解下述0-1整數(shù)規(guī)劃問題解：求解過程見下表(x1,x2,x3)Z 值約束條件 過濾條件（0,0,0）0 Z0(0,0,1)5 Z5(0,1,0)-2 (0,1,1)3(1,0,0

18、)3(1,0,1)8 Z8(1,1,0)1(1,1,1)6所以，最優(yōu)解為（x1，x2，x3)T=(1,0,1)T, 最優(yōu)值為8. 注： 當(dāng)決策變量(x1, x2 , x3)按(0,0,0), (0,0,1), (0,1,0), (0,1,1),.方式取值時(shí), 為了減少計(jì)算次數(shù), 通常將目標(biāo)函數(shù)中的決策變量的順序按其系數(shù)的大小重新排序, 以使最優(yōu)解能較早出現(xiàn)。對最大化問題, 按從小到大的順序排列；對極小化問題, 則相反。例2：求解下述0-1整數(shù)規(guī)劃問題10,53584612.73min4321421432143214321orxxxxxxxxxxxxxxxtsxxxxZ解：重新排序?yàn)?0,553

19、86412.37min4321412341234123412orxxxxxxxxxxxxxxxtsxxxxZ(x2,x1,x4 ,x3)Z 值約束條件 過濾條件（0,0,0,0）0 (0,0,0,1)-1 (0,0,1,0)1 (0,0,1,1)0(0,1,0,0)3(0,1,0,1)2 (0,1,1,0)4(0,1,1,1)3 Z3(1,0,0,0)7(1,0,0,1)6(1,0,1,0)8(1,0,1,1)7(1,1,0,0)10(1,1,0,1)9(1,1,1,0)11(1,1,1,1)10練習(xí)：求解下述整數(shù)規(guī)劃問題02245 , 2 , 1103-2253. .31075min5432

20、1432154321Ljorxxx6xxx5xxxxtsxxxxxZj1 25432xxx-x第五節(jié)第五節(jié) 指派問題（指派問題（Assignment Problem）1. 標(biāo)準(zhǔn)指派問題的提法及模型 指派問題的標(biāo)準(zhǔn)形式是：有n個(gè)人和n件事，已知第i個(gè)人做第j件事的費(fèi)用為cij（i，j=1，2，n），要求確定人和事之間的一一對應(yīng)的指派方案，使完成這n件事的總費(fèi)用最小。 njiorxxxtsxcZijnjijniijninjijij,2,1,1011.min1111L數(shù)學(xué)模型為:01ijx若指派第i個(gè)人做第j件事若不指派第i個(gè)人做第j件事(i,j=1,2, n) 設(shè)n2個(gè)0-1變量其中矩陣C稱為是效

21、率矩陣或系數(shù)矩陣。 其解的形式可用0-1矩陣的形式來描述，即 (xij)nn。 標(biāo)準(zhǔn)的指派問題是一類特殊的整數(shù)規(guī)劃問題，又是特殊的0-1規(guī)劃問題和特殊的運(yùn)輸問題。1955年W. W. Kuhn利用匈牙利數(shù)學(xué)家D. Konig關(guān)于矩陣中獨(dú)立零元素的定理, 提出了解指派問題的一種算法, 習(xí)慣上稱之為匈牙利解法。2. 匈牙利解法 匈牙利解法的關(guān)鍵是指派問題最優(yōu)解的以下性質(zhì)：若從指派若從指派問題的系數(shù)矩陣問題的系數(shù)矩陣C=（cij）的某行（或某列）各元素分別減去一個(gè)）的某行（或某列）各元素分別減去一個(gè)常數(shù)常數(shù)k，得到一個(gè)新的矩陣，得到一個(gè)新的矩陣C=（cij)，則以，則以C和和C為系數(shù)矩陣的兩為系數(shù)矩

22、陣的兩個(gè)指派問題有相同的最優(yōu)解。個(gè)指派問題有相同的最優(yōu)解。（這種變化不影響約束方程組，而只是使目標(biāo)函數(shù)值減少了常數(shù)k，所以，最優(yōu)解并不改變。）作變換，其不變性是最優(yōu)解對于指派問題，由于系數(shù)矩陣均非負(fù)，故若能在在系數(shù)矩陣中找到n個(gè)位于不同行和不同列的零元素（獨(dú)立的0元素），則對應(yīng)的指派方案總費(fèi)用為零，從而一定是最優(yōu)的。匈牙利法匈牙利法的步驟如下： 步1：變換系數(shù)矩陣。對系數(shù)矩陣中的每行元素分別減去該行的最小元素；再對系數(shù)矩陣中的每列元素分別減去該列中的最小元素。若某行或某列已有0元素，就不必要在減了（不能出現(xiàn)負(fù)元素）。 步2：在變換后的系數(shù)矩陣中確定獨(dú)立0元素（試指派）。若獨(dú)立0元素已有n個(gè)，則

23、已得出最優(yōu)解；若獨(dú)立0元素的個(gè)數(shù)少于n個(gè)，轉(zhuǎn)步3。 確定獨(dú)立0元素的方法：當(dāng)n較小時(shí)，可用觀察法、或試探法；當(dāng)n較大時(shí)，可按下列順序進(jìn)行 從只有一個(gè)0元素的行（列）開始，給這個(gè)0元素加圈，記作，然后劃去所在的列（行）的其它0元素，記作。給只有一個(gè)0元素的列（行）的0加圈，記作，然后劃去所在行的0元素，記作。反復(fù)進(jìn)行，直到系數(shù)矩陣中的所有0元素都被圈去或劃去為止。 如遇到行或列中0元素都不只一個(gè)（存在0元素的閉回路），可任選其中一個(gè)0元素加圈，同時(shí)劃去同行和同列中的其它0元素。被劃圈的0元素即是獨(dú)立的0元素。 步3：作最少數(shù)目的直線，覆蓋所有0元素（目的是確定系數(shù)矩陣的下一個(gè)變換），可按下述方法

24、進(jìn)行1） 對沒有的行打“”號；2） 在已打“”號的行中，對 所在列打“”3）在已打“”號的列中，對所在的行打“”號；4）重復(fù)2）3），直到再也找不到可以打“”號的行或列為止；5）對沒有打“”的行劃一橫線，對打“”的列劃一縱線，這樣就得到覆蓋所有0元素的最少直線數(shù)。 步4：繼續(xù)變換系數(shù)矩陣，目的是增加獨(dú)立0元素的個(gè)數(shù)。方法是在未被直線覆蓋的元素中找出一個(gè)最小元素，然后在打“”行各元素中都減去這一元素，而在打“”列的各元素都加上這一最小元素，以保持原來0元素不變（為了消除負(fù)元素）。得到新的系數(shù)矩陣，返回步2。 以例說明匈牙利法的應(yīng)用。91071041066141591412177666989797

25、12例1：求解效率矩陣為如下的指派問題的最優(yōu)指派方案。解：第一步：系數(shù)矩陣的變換（目的是得到某行或列均有0元素）910710410661415914121776669897971256360400892751000003220205第二步：確定獨(dú)立0元素56360400892751000003220205元素的個(gè)數(shù)m=4，而n=5，進(jìn)行第三步。第三步：作最少的直線覆蓋所有的0元素，目的是確定系數(shù)矩陣的下一個(gè)變換。第四步：對上述矩陣進(jìn)行變換，目的是增加獨(dú)立0元素的個(gè)數(shù)。方法是在未被直線覆蓋的元素中找出一個(gè)最小元素，然后在打“”行各元素中都減去這一元素，而在打“”列的各元素都加上這一最小元素，以保

26、持原來0元素不變（消除負(fù)元素）。得到新的系數(shù)矩陣。（它的最優(yōu)解和原問題相同，為什么？）563604008927510000032202050000100100100000100000010由解矩陣可得指派方案和最優(yōu)值為32。34140400811053800003420207 例2 某大型工程有五個(gè)工程項(xiàng)目，決定向社會(huì)公開招標(biāo)，有五家建筑能力相當(dāng)?shù)慕ㄖ痉謩e獲得中標(biāo)承建。已知建筑公司Ai（I=1，2，3，4，5）的報(bào)價(jià)cij（百萬元）見表，問該部門應(yīng)該怎樣分配建造任務(wù)，才能使總的建造費(fèi)用最?。?工程公司B1B2B3B4B5A14871512A279171410A3691287A4671461

27、0A569121065 ,2, 1,105 ,2, 115 ,2, 11.61084min515155541211LLLLjiorxixjxtsxxxxZijjijiij61012961061476781296101417971215784解：第一步：系數(shù)矩陣的變換（目的是得到某行或列均有0元素）04320405001232037710811030第二步：確定獨(dú)立0元素, 即加圈元素的個(gè)數(shù)m=4，而n=5，進(jìn)行第三步。04320405001232037710811030第三步：作最少的直線覆蓋所有的0元素，目的是確定系數(shù)矩陣的下一個(gè)變換。第四步：對上述矩陣進(jìn)行變換，目的是增加獨(dú)立0元素個(gè)數(shù)。方

28、法是在未被直線覆蓋的元素中找出一個(gè)最小元素，然后在打“”行各元素中都減去這一元素，而在打“”列的各元素都加上這一最小元素，以保持原來0元素不變（消除負(fù)元素）。得到新的系數(shù)矩陣。（它的最優(yōu)解和原問題相同，為什么？因?yàn)閮H在目標(biāo)函數(shù)系數(shù)中進(jìn)行操作）04320405001232037710811030043204050001211266018110300432140501012102660081103104321405010121026600811031此矩陣中已有5個(gè)獨(dú)立的0元素，故可得指派問題的最優(yōu)指派方案為：1000001000000010001000100也就是說，最優(yōu)指派方案為：讓A1承建B

29、3， A2承建B2，A3承建B1，A4承建B4，A5承建B5。這樣安排建造費(fèi)用為最小，即7+9+6+6+6=34（百萬元）3. 一般的指派問題 在實(shí)際應(yīng)用中，常會(huì)遇到各種非標(biāo)準(zhǔn)形式的指派問題。通常的處理方法是先將它們轉(zhuǎn)化為標(biāo)準(zhǔn)形式，然后用匈牙利解法求解。 最大化指派問題 設(shè)最大化指派問題系數(shù)矩陣C中最大元素為m。令矩陣B=(bij)=(m-cij), 則以B為系數(shù)矩陣的最小化指派問題和以C為系數(shù)矩陣的原最大化指派問題有相同的最優(yōu)解。 人數(shù)和事數(shù)不等的指派問題 若人少事多，則添上一些虛擬的“人”。這些虛擬的人作各事的費(fèi)用系數(shù)可取0，理解為這些費(fèi)用實(shí)際上不會(huì)發(fā)生。若人多事少，則添上一些虛擬的“事”。這些虛擬的事被各人做的費(fèi)用系數(shù)同樣也取0。 一個(gè)人可做幾件事的指派問題 若某個(gè)人可做幾件事，則可將該人看做相同的幾個(gè)人來接受指派。這幾個(gè)人作同一件事的費(fèi)用系數(shù)當(dāng)然都一樣。 某事一定不能由某人作的指派問題 若某事一定不能由某個(gè)人做，則可將相應(yīng)的費(fèi)用系數(shù)取做足夠大的數(shù)M。 例3：對于例2的指派問題，為了保證工程質(zhì)量，經(jīng)研究決定，舍棄建筑公司A4和A5，而讓技術(shù)力量較強(qiáng)的建設(shè)公司A1，A2，A3參加招標(biāo)承建，