第14次課--第五章整數(shù)規(guī)劃

1、1溫故知新溫故知新2第五章 整數(shù)規(guī)劃3第五章 整數(shù)規(guī)劃 整數(shù)規(guī)劃問題的提出 分支定界法 割平面法 0-1型整數(shù)規(guī)劃 指派問題4純整數(shù)線性規(guī)劃純整數(shù)線性規(guī)劃（全整數(shù)規(guī)劃）（全整數(shù)規(guī)劃）混合整數(shù)線性規(guī)劃混合整數(shù)線性規(guī)劃0-10-1型線性規(guī)劃問題型線性規(guī)劃問題 整數(shù)規(guī)劃（整數(shù)規(guī)劃（Integer Programming, IPInteger Programming, IP） 要求一部分或全部決策變量必須取整數(shù)值的規(guī)劃問題稱為要求一部分或全部決策變量必須取整數(shù)值的規(guī)劃問題稱為整數(shù)規(guī)劃整數(shù)規(guī)劃。 不考慮整數(shù)條件，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)不考慮整數(shù)條件，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問題稱

2、為該劃問題稱為該整數(shù)規(guī)劃問題的松弛問題整數(shù)規(guī)劃問題的松弛問題（slack problemslack problem） 。 若松弛問題是一個(gè)線性規(guī)劃，則稱該整數(shù)規(guī)劃為若松弛問題是一個(gè)線性規(guī)劃，則稱該整數(shù)規(guī)劃為整數(shù)線性整數(shù)線性規(guī)劃規(guī)劃（Integer Linear ProgrammingInteger Linear Programming）。）。一. 整數(shù)規(guī)劃問題的提出5整數(shù)線性規(guī)劃的數(shù)學(xué)模型整數(shù)線性規(guī)劃的數(shù)學(xué)模型112(1,2,.,)01,2,.,.,nijjjjna ximxjnx xxj=, )b中部分或全部取整數(shù)1max(min)njjjzc x或一. 整數(shù)規(guī)劃問題的提出6求解整數(shù)規(guī)劃數(shù)學(xué)

3、模型：求解整數(shù)規(guī)劃數(shù)學(xué)模型：分支定界法分支定界法割平面法割平面法一. 整數(shù)規(guī)劃問題的提出7例：求解整數(shù)規(guī)劃問題例：求解整數(shù)規(guī)劃問題(記作記作問題問題A) 1212121212max114951 (2)6313,0(4),zxxxxxxxxxx為整數(shù) (5)記作記作問題問題B二. 分支定界法10二. 分支定界法算法思路算法思路11n 步驟一：求解問題B二. 分支定界法12n 步驟二：求解問題A二. 分支定界法13第1步：分支定界 二. 分支定界法14第1步：分支定界 二. 分支定界法15第二步：比較與剪支 二. 分支定界法16二. 分支定界法例：求解例：求解 1212121212max40901

4、97562720703,04,5zxxxxxxx xx x為整數(shù)17解解 先不考慮條件，即解相應(yīng)的線性規(guī)劃B,(見圖5-2)，得最優(yōu)解x1=4.81，x2=1.82，z0=356 不符合整數(shù)條件。18 這時(shí)z0 356是問題A的最優(yōu)目標(biāo)函數(shù)值z*的上界，記作z0= 。 而在x1=0，x2=0時(shí)，顯然是問題A的一個(gè)整數(shù)可行解，這時(shí)z=0，是z*的一個(gè)下界，記作 =0，即0z*356。zz二. 分支定界法19 首先注意其中一個(gè)非整數(shù)變量的解，如首先注意其中一個(gè)非整數(shù)變量的解，如x x1 1，在問題，在問題B B的解中的解中x x1 1=4.81=4.81。 對原問題增加兩個(gè)約束條件對原問題增加兩個(gè)

5、約束條件x x1 144，x x1 155。可將。可將原問題分解為兩個(gè)子問題原問題分解為兩個(gè)子問題B B1 1和和B B2 2( (即兩支即兩支) )。 這并不影響問題這并不影響問題A A的可行域。的可行域。二. 分支定界法20 x x1 144，x x1 155二. 分支定界法21 不考慮整數(shù)條件解問題不考慮整數(shù)條件解問題B B1 1和和B B2 2，稱此為第一次迭代。得到最，稱此為第一次迭代。得到最優(yōu)解為：優(yōu)解為： 顯然沒有得到全部變量是整數(shù)的解。因顯然沒有得到全部變量是整數(shù)的解。因z1z1z2z2，故將，故將 改為改為349349，那么必存在最優(yōu)整數(shù)解，得到，那么必存在最優(yōu)整數(shù)解，得到z

6、 z* *，并且，并且00z z* *349349二. 分支定界法z22繼續(xù)對問題B1和B2進(jìn)行分解 因z1z2，故先分解B1為兩支。增加條件x22者，稱為問題B3；增加條件x23者稱為問題B4。 在圖中再舍去 x22與x33 之間的可行域， 進(jìn)行第二次迭代。二. 分支定界法23繼續(xù)對問題B2進(jìn)行分解二. 分支定界法25分支定界法是求解整數(shù)規(guī)劃的較好方法，有著廣泛分支定界法是求解整數(shù)規(guī)劃的較好方法，有著廣泛的適用性，便于編程實(shí)現(xiàn)。的適用性，便于編程實(shí)現(xiàn)。分支定界法適用于求解混合整數(shù)規(guī)劃問題。分支定界法適用于求解混合整數(shù)規(guī)劃問題。分支定界法關(guān)鍵在于有效地分支定界。分支定界法關(guān)鍵在于有效地分支定界

7、。n分支定界法總結(jié)二. 分支定界法26第五章 整數(shù)規(guī)劃 整數(shù)規(guī)劃問題的提出 分支定界法 割平面法 0-1型整數(shù)規(guī)劃 指派問題27割平面解法的思路： 首先不考慮決策變量為整數(shù)的條件，增加線性約束條件（幾何術(shù)語稱為割平面），使得由原可行域中切割掉一部分，這部分只包含非整數(shù)解，沒有切割掉任何整數(shù)可行解。 割平面法就是找到適當(dāng)?shù)母钇矫妫ú灰姷靡淮尉驼业剑?，使切割后最終得到這樣的可行域，它的切割后最終得到這樣的可行域，它的一個(gè)有整數(shù)坐標(biāo)的頂點(diǎn)恰好是問題的最優(yōu)解一個(gè)有整數(shù)坐標(biāo)的頂點(diǎn)恰好是問題的最優(yōu)解。一. 整數(shù)規(guī)劃問題的提出28n 割平面需要滿足割平面需要滿足分割有效：即真正割去可行域中一部分。最終要能夠

8、恰好割出這樣的可行域：符合整數(shù)條件的最優(yōu)解正好在它的頂點(diǎn)上。沒有割去任何整數(shù)可行解。三. 割平面法 這個(gè)方法是這個(gè)方法是R.E.GomoryR.E.Gomory提出來的，所以又稱為提出來的，所以又稱為GomoryGomory的割平面法。的割平面法。 以下只討論純整數(shù)線性規(guī)劃的情形，現(xiàn)舉例說明。以下只討論純整數(shù)線性規(guī)劃的情形，現(xiàn)舉例說明。29例：求解純整數(shù)規(guī)劃問題例：求解純整數(shù)規(guī)劃問題 1212121212max112343,04,zxxxxxxx xx x是整數(shù)5三.割平面法 得到非整數(shù)的最優(yōu)解為：得到非整數(shù)的最優(yōu)解為：1234375,0, m ax244xxxxz31331133444433

9、12344441xxxxxxx311134444371234444xxxxxx由最終表得到：將有關(guān)系數(shù)和常數(shù)項(xiàng)分成整數(shù)與正的小數(shù)部分得到：三.割平面法32現(xiàn)考慮整數(shù)條件，可知上面兩式右側(cè)必須非正，得到現(xiàn)考慮整數(shù)條件，可知上面兩式右側(cè)必須非正，得到：331344440 xx 將此作為增加的約束條件，加入到上面的最終計(jì)算表中。將此作為增加的約束條件，加入到上面的最終計(jì)算表中。34533xxx 化簡并引入松弛變量得到：化簡并引入松弛變量得到：三.割平面法33三.割平面法34 得到得到x1 =1, x2 =1為符合整數(shù)條件的最優(yōu)解，解題完成。為符合整數(shù)條件的最優(yōu)解，解題完成。三.割平面法353433x

10、x三.割平面法(1,1)C(1,1)C36第一步：求解相應(yīng)的松弛問題，列出最終單純形表。 三. 割平面法37第二步：分解系數(shù)為整數(shù)和非負(fù)真分?jǐn)?shù)兩個(gè)部分。 三.割平面法38第三步：利用分?jǐn)?shù)部分得到切割方程。 滿足割平面的滿足割平面的要求嗎？要求嗎？三.割平面法39思考：思考： 切割方程式真正進(jìn)行了切割，至少把不滿切割方程式真正進(jìn)行了切割，至少把不滿足整數(shù)條件的最優(yōu)基可行解割掉了。足整數(shù)條件的最優(yōu)基可行解割掉了。 沒有割掉任何整數(shù)可行解。沒有割掉任何整數(shù)可行解。三.割平面法40第四步：將得到的切割方程作為約束條件加到原線性規(guī)劃問題中，并求解。第五步：如果得到的解滿足整數(shù)條件，停止，否則返回到第一步

11、三.割平面法41割平面法較少單獨(dú)使用。割平面法較少單獨(dú)使用。割平面法實(shí)質(zhì)是一種排除法。割平面法實(shí)質(zhì)是一種排除法。割平面法若和其他方法（如分枝定界法）配合使用，割平面法若和其他方法（如分枝定界法）配合使用，是有效的。是有效的。割平面法經(jīng)常會(huì)碰到收斂很慢的情況，效率不高。割平面法經(jīng)常會(huì)碰到收斂很慢的情況，效率不高。n割平面法總結(jié)三.割平面法42nP152 6.3（1）課后作業(yè)課后作業(yè)43第五章 整數(shù)規(guī)劃 整數(shù)規(guī)劃問題的提出 分支定界法 割平面法 0-1型整數(shù)規(guī)劃 指派問題44四. 0-1型整數(shù)規(guī)劃0 01 1型整數(shù)規(guī)劃的概念型整數(shù)規(guī)劃的概念 0101變量作為變量作為邏輯變量邏輯變量(logical

12、 variable)(logical variable)，常被用來，常被用來表示表示系統(tǒng)系統(tǒng)是否處于某個(gè)是否處于某個(gè)特定狀態(tài)特定狀態(tài)，或者決策時(shí)是否取某，或者決策時(shí)是否取某個(gè)特定方案。個(gè)特定方案。若問題含有多項(xiàng)若問題含有多項(xiàng)要素要素，而每項(xiàng)要素皆有兩種選擇時(shí)，可，而每項(xiàng)要素皆有兩種選擇時(shí)，可用用一組一組0-10-1變量來描述。變量來描述。應(yīng)用中，決策變量取多個(gè)整數(shù)值的問題，可以應(yīng)用中，決策變量取多個(gè)整數(shù)值的問題，可以轉(zhuǎn)化轉(zhuǎn)化為為0-10-1型問題。型問題。 決策變量僅取值決策變量僅取值0或或1的整數(shù)規(guī)劃問題稱為的整數(shù)規(guī)劃問題稱為01型整數(shù)規(guī)劃型整數(shù)規(guī)劃。這時(shí)決策變量稱為。這時(shí)決策變量稱為01變

13、量。變量。45例 引入0-1變量的實(shí)際問題投資場所的選定投資場所的選定相互排斥的計(jì)劃相互排斥的計(jì)劃 某公司擬在市東、西、南三區(qū)建立門市部。擬議中有某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個(gè)個(gè)位置位置(點(diǎn)點(diǎn))Ai (i=1，2，7)可供選擇。規(guī)定：可供選擇。規(guī)定： 在東區(qū)，由在東區(qū)，由A1，A2，A3三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)； 在西區(qū)，由在西區(qū)，由A4，A5兩個(gè)點(diǎn)中至少選一個(gè)；兩個(gè)點(diǎn)中至少選一個(gè)； 在南區(qū)，由在南區(qū)，由A6，A7兩個(gè)點(diǎn)中至少選一個(gè)。兩個(gè)點(diǎn)中至少選一個(gè)。 如選用如選用Ai點(diǎn)，設(shè)備投資估計(jì)為點(diǎn)，設(shè)備投資估計(jì)為bi元，每年可獲利潤估計(jì)為元，每年可獲利潤估計(jì)為ci元

14、，但投資總額不能超過元，但投資總額不能超過B元。問應(yīng)選擇哪幾個(gè)點(diǎn)可使元。問應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤為最大年利潤為最大?四. 0-1型整數(shù)規(guī)劃467 , 2 , 1, 0, 1iAAxiii點(diǎn)沒有被選用當(dāng)點(diǎn)被選用當(dāng)令于是問題可列成： 71711234567m ax21101 (1,., 7)iiiiiiizc xb xBxxxxxxxxi目 標(biāo) 函 數(shù) ：約 束 條 件或四. 0-1型整數(shù)規(guī)劃470-1型整數(shù)規(guī)劃的數(shù)學(xué)模型型整數(shù)規(guī)劃的數(shù)學(xué)模型四. 0-1型整數(shù)規(guī)劃48求解求解0-1型整數(shù)規(guī)劃數(shù)學(xué)模型的方法型整數(shù)規(guī)劃數(shù)學(xué)模型的方法 窮舉法（完全枚舉法）窮舉法（完全枚舉法） 隱枚舉法（部分枚舉法）隱

15、枚舉法（部分枚舉法）四. 0-1型整數(shù)規(guī)劃49舉例說明隱枚舉法舉例說明隱枚舉法 1231231231223123max3252214423346(4),015zxxxxxxxxxxxxxx x x或四. 0-1型整數(shù)規(guī)劃50n第一步 找到一個(gè)可行解，增加約束條件。 四. 0-1型整數(shù)規(guī)劃51n第二步第二步 在表中列出所有約束條件，并逐次計(jì)算所有解在表中列出所有約束條件，并逐次計(jì)算所有解。 計(jì)算過程中如某一條件不滿足約束條件，同行以后各種計(jì)算過程中如某一條件不滿足約束條件，同行以后各種條件就不必再檢查。條件就不必再檢查。 在計(jì)算過程中，若遇到值以超過條件在計(jì)算過程中，若遇到值以超過條件右邊的值，

16、應(yīng)改右邊的值，應(yīng)改變條件變條件，使右邊為迄今為止最大者，然后繼續(xù)作。，使右邊為迄今為止最大者，然后繼續(xù)作。四. 0-1型整數(shù)規(guī)劃52改變改變約束條件，繼續(xù)實(shí)施，直至得到最優(yōu)解約束條件，繼續(xù)實(shí)施，直至得到最優(yōu)解。 四. 0-1型整數(shù)規(guī)劃53四. 0-1型整數(shù)規(guī)劃54隱枚舉法改進(jìn)： 重新排列xi的順序使目標(biāo)函數(shù)中xi的系數(shù)是遞增(不減)的，在上例中， 改寫 z=3x1-2x2+5x3=-2x2+3x1+5x3 因?yàn)?2，3，5是遞增的序，變量(x2，x1，x3)也按下述順序取值：(0，0，0)，(0，0，1)，(0，1，0)，(0，1，1)，。這樣，最優(yōu)解容易比較早的發(fā)現(xiàn)。 四. 0-1型整數(shù)規(guī)劃

17、55重新排列決策變量在目標(biāo)函數(shù)中的順序使之在目標(biāo)函數(shù)中的系數(shù)是遞增（不減）的，可以改進(jìn)計(jì)算效率。隱枚舉法的計(jì)算量比窮舉法要少得多。n隱枚舉法總結(jié)隱枚舉法處理的點(diǎn)的個(gè)數(shù)為2n。四. 0-1型整數(shù)規(guī)劃56nP154 6.8（2）課后作業(yè)課后作業(yè)57第五章 整數(shù)規(guī)劃 整數(shù)規(guī)劃問題的提出 分支定界法 割平面法 0-1型整數(shù)規(guī)劃 指派問題58 生活中經(jīng)常遇到這樣的問題：完成生活中經(jīng)常遇到這樣的問題：完成若干項(xiàng)任務(wù)若干項(xiàng)任務(wù)，恰好，恰好若干若干個(gè)人個(gè)人可以承擔(dān)這些任務(wù)。由于每人的專長不同，各人完成任務(wù)可以承擔(dān)這些任務(wù)。由于每人的專長不同，各人完成任務(wù)的能力、花費(fèi)和效率不同。于是產(chǎn)生應(yīng)指派哪個(gè)人去完成哪項(xiàng)的

18、能力、花費(fèi)和效率不同。于是產(chǎn)生應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成任務(wù)的任務(wù)，使完成任務(wù)的總體效果總體效果最好（花費(fèi)最小，時(shí)間最少或者最好（花費(fèi)最小，時(shí)間最少或者完成程度最好等）。完成程度最好等）。 五. 指派問題 這類問題稱為這類問題稱為指派問題指派問題或或分派問題分派問題，它是特殊，它是特殊的的0-10-1整數(shù)規(guī)劃問題。整數(shù)規(guī)劃問題。59例：有一份中文說明書，要譯成英、日、德、俄四種文字，例：有一份中文說明書，要譯成英、日、德、俄四種文字，記作記作E、J、G、R?，F(xiàn)有甲、乙、丙、丁四人。他們將中文。現(xiàn)有甲、乙、丙、丁四人。他們將中文說明書譯成不同語種的說明書所需時(shí)間如表所示。問應(yīng)指說明書譯成

19、不同語種的說明書所需時(shí)間如表所示。問應(yīng)指派每人去完成何工作，使所需總時(shí)間最少？派每人去完成何工作，使所需總時(shí)間最少？五. 指派問題60 類似有：有n項(xiàng)加工任務(wù)，怎樣指派到n臺機(jī)床上分別完成的問題；有n條航線，怎樣指定n艘船去航行。 對應(yīng)每個(gè)指派問題，需有效率矩陣或系數(shù)矩陣，其元素cij0(i,j=1,2，n)表示指派第i人去完成第j項(xiàng)任務(wù)時(shí)的效率(或時(shí)間、成本等)。 建模時(shí)需引入變量xij；其取值只能是1或0。并令 項(xiàng)任務(wù)人去完成第當(dāng)不指派第項(xiàng)任務(wù)人去完成第當(dāng)指派第jijixij, 0, 1五. 指派問題61指派問題數(shù)學(xué)模型的標(biāo)準(zhǔn)形式指派問題數(shù)學(xué)模型的標(biāo)準(zhǔn)形式1111min1,1,2,1,1,

20、2,10nnijijijnijjnijiijzc xxinxjnx或五. 指派問題這些約束條件代這些約束條件代表什么含義呢？表什么含義呢？目標(biāo)函數(shù)代表什目標(biāo)函數(shù)代表什么含義？么含義？62 滿足約束條件的可行解滿足約束條件的可行解x xijij也可寫成表格或矩陣形式，稱為也可寫成表格或矩陣形式，稱為解矩陣解矩陣(xij)nn 。 如前例的一個(gè)可行解矩陣如前例的一個(gè)可行解矩陣 目標(biāo)函數(shù)的目標(biāo)函數(shù)的價(jià)值系數(shù)矩陣價(jià)值系數(shù)矩陣(cij)nn01000010()10000001ijxl結(jié)構(gòu)松散，且矩陣元結(jié)構(gòu)松散，且矩陣元素等于素等于1 1或者或者0 0；l每一行、每一列只有每一行、每一列只有一個(gè)一個(gè)1元素

21、。元素。五. 指派問題63指派問題模型的特點(diǎn)指派問題模型的特點(diǎn) 變量個(gè)數(shù)多（變量個(gè)數(shù)多（n n2 2個(gè)）個(gè)） 約束（約束（2n2n個(gè)）簡單個(gè)）簡單 約束系數(shù)矩陣稀疏約束系數(shù)矩陣稀疏五. 指派問題 變量取值特殊（僅取變量取值特殊（僅取0 0或或1 1）64指派問題的求解指派問題的求解 整數(shù)規(guī)劃的一般求解方法整數(shù)規(guī)劃的一般求解方法 求解求解0-10-1型整數(shù)規(guī)劃的隱枚舉法型整數(shù)規(guī)劃的隱枚舉法 運(yùn)輸問題的表上作業(yè)法運(yùn)輸問題的表上作業(yè)法五. 指派問題 指派問題是指派問題是0-10-1規(guī)劃的特例，也是運(yùn)輸問題的規(guī)劃的特例，也是運(yùn)輸問題的特例，即特例，即n=m, ai=bj=1，當(dāng)然可用以下方法求解：，當(dāng)

22、然可用以下方法求解：65指派問題的求解指派問題的求解五. 指派問題 針對指派問題特點(diǎn)的匈牙利解法針對指派問題特點(diǎn)的匈牙利解法 以上方法就如同用單純形法求解運(yùn)輸問題一樣以上方法就如同用單純形法求解運(yùn)輸問題一樣是不合算的。利用指派問題特點(diǎn)有更簡便的解法。是不合算的。利用指派問題特點(diǎn)有更簡便的解法。 1955 1955年庫恩年庫恩KuhnKuhn給出了一種解法，是基于匈牙給出了一種解法，是基于匈牙利數(shù)學(xué)家康尼格利數(shù)學(xué)家康尼格KonigKonig給出的定理，故又稱給出的定理，故又稱“匈牙匈牙利方法利方法”66指派問題的求解指派問題的求解五. 指派問題 定理定理1 1 從效率矩陣從效率矩陣(cij )m

23、m每行（或列）減去每行（或列）減去一個(gè)常數(shù)一個(gè)常數(shù)ui（或（或vj），所得新的矩陣），所得新的矩陣(bij)mm，其中，其中bijcij ui (或或 cij vj ）的指派問題與原問題的最的指派問題與原問題的最優(yōu)指派相同。優(yōu)指派相同。67由定理一得指派問題最優(yōu)解的性質(zhì)：由定理一得指派問題最優(yōu)解的性質(zhì)： 從價(jià)值系數(shù)矩陣從價(jià)值系數(shù)矩陣( cij )的一行（列）各元的一行（列）各元素中分別減去行（列）的最小元素，得到新素中分別減去行（列）的最小元素，得到新矩陣矩陣( bij ) 。那么以。那么以( bij )為系數(shù)矩陣求得的最為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩陣求得的最優(yōu)解相同。優(yōu)解和用原系數(shù)矩陣

24、求得的最優(yōu)解相同。 五. 指派問題68 利用這個(gè)性質(zhì)，可使原系數(shù)矩陣變換為含利用這個(gè)性質(zhì)，可使原系數(shù)矩陣變換為含有很多有很多0 0元素的新系數(shù)矩陣，而最優(yōu)解保持不元素的新系數(shù)矩陣，而最優(yōu)解保持不變。變。 在系數(shù)矩陣在系數(shù)矩陣( ( bij ) )中，我們關(guān)心位于不同中，我們關(guān)心位于不同行不同列的行不同列的0 0元素，以下簡稱為元素，以下簡稱為獨(dú)立的獨(dú)立的0 0元素元素。五. 指派問題69獨(dú)立的獨(dú)立的0 0元素元素位于不同行不同列的位于不同行不同列的0 0元素。元素。 若能在系數(shù)矩陣若能在系數(shù)矩陣(b(bijij) )中找出中找出n n個(gè)獨(dú)立的個(gè)獨(dú)立的0 0元元素，則令解矩陣素，則令解矩陣(x(

25、xijij) )中對應(yīng)這個(gè)獨(dú)立的中對應(yīng)這個(gè)獨(dú)立的0 0元素的元素的元素取值為元素取值為1 1，其他元素取值為，其他元素取值為0 0。將其代入目。將其代入目標(biāo)函數(shù)中，標(biāo)函數(shù)中，z zb b=b=bijijx xijij得得z zb b=0=0。它一定是最小。它一定是最小。 這就是以這就是以(b(bijij) )為系數(shù)矩陣的指派問題的最為系數(shù)矩陣的指派問題的最優(yōu)解。也就得到了原問題的最優(yōu)解。優(yōu)解。也就得到了原問題的最優(yōu)解。五. 指派問題70指派問題的求解指派問題的求解五. 指派問題 定理定理2 2 矩陣中覆蓋所有矩陣中覆蓋所有0 0元素的最少直線數(shù)，元素的最少直線數(shù)，等于位于不同行且不同列的等于位

26、于不同行且不同列的0 0元素最大個(gè)數(shù)。元素最大個(gè)數(shù)。71例：有一份中文說明書，要譯成英、日、德、俄四種文字，例：有一份中文說明書，要譯成英、日、德、俄四種文字，記作記作E、J、G、R。現(xiàn)有甲、乙、丙、丁四人。他們將中文。現(xiàn)有甲、乙、丙、丁四人。他們將中文說明書譯成不同語種的說明書所需時(shí)間如表所示。問應(yīng)指說明書譯成不同語種的說明書所需時(shí)間如表所示。問應(yīng)指派每人去完成何工作，使所需總時(shí)間最少？派每人去完成何工作，使所需總時(shí)間最少？五. 指派問題72指派問題的解法：指派問題的解法：第一步：第一步：使指派問題的系數(shù)矩陣經(jīng)變換，在各行各列使指派問題的系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)中都出現(xiàn)0 0元素。

27、元素。（1 1）從系數(shù)矩陣的每行元素減去該行的最小元素；）從系數(shù)矩陣的每行元素減去該行的最小元素；（2 2）再從所得的系數(shù)矩陣的每列元素中減去該列的最）再從所得的系數(shù)矩陣的每列元素中減去該列的最 小元素。小元素。 若該行（列）已有若該行（列）已有0 0元素，那就不必再減了。元素，那就不必再減了。五. 指派問題73第二步：第二步：進(jìn)行試指派，以尋求最優(yōu)解進(jìn)行試指派，以尋求最優(yōu)解 經(jīng)第一步變換后，系數(shù)矩陣中每行每列都有了經(jīng)第一步變換后，系數(shù)矩陣中每行每列都有了0 0元素，但需找出元素，但需找出n n個(gè)獨(dú)立的個(gè)獨(dú)立的0 0元素。若能找出，就以元素。若能找出，就以這些獨(dú)立這些獨(dú)立0 0元素對應(yīng)解矩陣元

28、素對應(yīng)解矩陣(x(xijij) )中元素為中元素為1 1，其余為，其余為0 0。這就得到最優(yōu)解。這就得到最優(yōu)解。 當(dāng)當(dāng)n n較小時(shí)，可用較小時(shí)，可用觀察法、試探法觀察法、試探法去找出去找出n n個(gè)獨(dú)個(gè)獨(dú)立立0 0元素。若元素。若n n較大時(shí)，就必須按一定的步驟去找。較大時(shí)，就必須按一定的步驟去找。五. 指派問題74試指派步驟試指派步驟：（1 1）從只有一個(gè)）從只有一個(gè)0 0元素的行（列）開始，給這個(gè)元素的行（列）開始，給這個(gè)0 0元素元素加圈，記作：加圈，記作：。這表示對這行所代表的人，只這表示對這行所代表的人，只有一種任務(wù)可指派，或這列所代表的任務(wù)，只有有一種任務(wù)可指派，或這列所代表的任務(wù)，

29、只有一人可指派一人可指派。然后劃去。然后劃去所在列（行）的其他所在列（行）的其他0 0元元素，記作：素，記作：。這表示這列所代表的任務(wù)已指派這表示這列所代表的任務(wù)已指派完，或這行所代表的人已指派完，或這行所代表的人已指派。（2 2）給只有一個(gè)）給只有一個(gè)0 0元素的列（行）的元素的列（行）的0 0元素加圈，記作：元素加圈，記作：，然后劃去，然后劃去所行（列）的所行（列）的0 0元素，記作：元素，記作： 。（3 3）重復(fù)（）重復(fù)（1 1）（）（2 2）步驟，直到所有）步驟，直到所有0 0元素都被圈出和元素都被圈出和劃掉。劃掉。五. 指派問題75例：有一份中文說明書，要譯成英、日、德、俄四種文字，

30、例：有一份中文說明書，要譯成英、日、德、俄四種文字，記作記作E、J、G、R?，F(xiàn)有甲、乙、丙、丁四人。他們將中文?，F(xiàn)有甲、乙、丙、丁四人。他們將中文說明書譯成不同語種的說明書所需時(shí)間如表所示。問應(yīng)指說明書譯成不同語種的說明書所需時(shí)間如表所示。問應(yīng)指派每人去完成何工作，使所需總時(shí)間最少？派每人去完成何工作，使所需總時(shí)間最少？五. 指派問題76解：將系數(shù)矩陣進(jìn)行變換解：將系數(shù)矩陣進(jìn)行變換 min01311221513426010111041415 405749141613 9014278119742 minijc01370606905320100ijb按步驟進(jìn)行指派，得到：按步驟進(jìn)行指派，得到： 1

31、376695321五. 指派問題77可見找到了4個(gè)獨(dú)立的0元素，所以得最優(yōu)解為： 0001010010000010ijx 這表示：指定甲譯出俄文，乙譯出日文，丙譯出英文，丁譯出德文所需總時(shí)間最少minz = cijxij= 4 + 4 + 9 + 11 = 28 (小時(shí)小時(shí)) i j五. 指派問題78（4 4） 若仍有沒有加圈的若仍有沒有加圈的0 0元素，且同行（列）的元素，且同行（列）的0 0元素至少元素至少有兩個(gè)（表示對這人可以從兩項(xiàng)任務(wù)中指派其一），這可用有兩個(gè)（表示對這人可以從兩項(xiàng)任務(wù)中指派其一），這可用不同的方案去試探。不同的方案去試探。 從剩有從剩有0 0元素的最少行（列）開始，比

32、較這行（列）各元素的最少行（列）開始，比較這行（列）各0 0元素所在列（行）中元素所在列（行）中0 0元素的數(shù)目，選擇元素的數(shù)目，選擇0 0元素少的那列（行）元素少的那列（行）的這個(gè)的這個(gè)0 0元素加圈（表示選擇性多的要元素加圈（表示選擇性多的要“禮讓禮讓”選擇性小選擇性小的。），然后劃掉同行同列的其它的。），然后劃掉同行同列的其它0 0元素。元素。 可以反復(fù)進(jìn)行。直到所有的可以反復(fù)進(jìn)行。直到所有的0 0元素都已圈出和劃掉為止。元素都已圈出和劃掉為止。五. 指派問題79（5 5）若）若元素的數(shù)目元素的數(shù)目m m等于矩陣的階數(shù)等于矩陣的階數(shù) n n，則，則這指派問題的最優(yōu)解已得到。這指派問題的最

33、優(yōu)解已得到。 若若 m nm n，則轉(zhuǎn)入下一步，進(jìn)一步處理。，則轉(zhuǎn)入下一步，進(jìn)一步處理。五. 指派問題80例：求下表所示效率矩陣的指派問題的最小解。五. 指派問題81min12797975020289666623000717121497010572151466106980044107109406365解：將系數(shù)矩陣進(jìn)行變換 五. 指派問題82按步驟進(jìn)行試指派，得矩陣 ： 52223105729846365這里的的個(gè)數(shù)m=4，而n=5；故解題沒有完成，應(yīng)按以下步驟繼續(xù)進(jìn)行。五. 指派問題83五. 指派問題第三步：第三步：作最少的直線覆蓋所有作最少的直線覆蓋所有0 0元素。（元素。（以確定該以確定

34、該系數(shù)矩陣中能找到最多的獨(dú)立系數(shù)矩陣中能找到最多的獨(dú)立0 0元素個(gè)數(shù)元素個(gè)數(shù)）。）。84五. 指派問題 定理定理2 2 矩陣中覆蓋矩陣中覆蓋0 0元素的最少直元素的最少直線數(shù)，等于位于不同行且不同列的線數(shù)，等于位于不同行且不同列的0 0元素元素最大個(gè)數(shù)。最大個(gè)數(shù)。85五. 指派問題第三步：第三步：作最少的直線覆蓋所有作最少的直線覆蓋所有0 0元素。（元素。（以確定該以確定該系數(shù)矩陣中能找到最多的獨(dú)立系數(shù)矩陣中能找到最多的獨(dú)立0 0元素個(gè)數(shù)元素個(gè)數(shù)）。）。為此按以下步驟進(jìn)行：為此按以下步驟進(jìn)行：（1 1）對沒有）對沒有的行打的行打號；號；（2 2）對已打）對已打號的行中所含號的行中所含 元素的列

35、打元素的列打號；號；（3 3）再對打有）再對打有號的列中所含號的列中所含元素的行打元素的行打號；號；（4 4）重復(fù)）重復(fù)(2)(3)(2)(3)直到不能得到新打直到不能得到新打行、列為止；行、列為止；（5 5）對沒有打?qū)]有打號的行劃一橫線，有打號的行劃一橫線，有打號的列劃號的列劃一縱線。一縱線。86這就得到了覆蓋所有0元素的最少直線數(shù)，設(shè)為l。若ln 說明必須再變換當(dāng)前的系數(shù)矩陣，才能找到 n 個(gè)獨(dú)立的0元素，為此轉(zhuǎn)第四步。若l = n而 m n 應(yīng)回到第二步（4），另行試探。（說明還能找到更多的獨(dú)立0元素）。五. 指派問題87對上例的矩陣按以上次序進(jìn)行。五. 指派問題可知 l=4n=5，所以對矩陣進(jìn)行變換，轉(zhuǎn)第四步。88第四步：第四步：對矩陣對矩陣進(jìn)行變換，目的是增加進(jìn)行變換，目的是增加0 0元素。元素。 （1 1）在沒有被直線覆蓋的部分中找出最小元素；）在沒有被直線覆蓋的部分中找出最小元素； （2 2）打）打的行中各元素都減去這最小元素；的行中各元素都減去這最小元素； （3 3）打）打的列中各元素都加上這最小元素的列中各元素都加上這最小元素 這樣在保證原來這樣在保證原來0 0元素不變的情況下