運(yùn)籌學(xué)復(fù)習(xí)資料

1、. .運(yùn)籌學(xué)復(fù)習(xí)一、單純形方法表格、人工變量、根底知識(shí)線性規(guī)劃解的情況：唯一最優(yōu)解、多重最優(yōu)解、無(wú)界解、無(wú)解。其中，可行域無(wú)界，并不意味著目標(biāo)函數(shù)值無(wú)界。無(wú)界可行域?qū)?yīng)著解的情況有：唯一最優(yōu)解、多重最優(yōu)解、無(wú)界解。有界可行域?qū)?yīng)唯一最優(yōu)解和多重最優(yōu)解兩種情況。線性規(guī)劃解得根本性質(zhì)有：滿足線性規(guī)劃約束條件的可行解集可行域構(gòu)成一個(gè)凸多邊形；凸多邊形的頂點(diǎn)極點(diǎn)與根本可行解一一對(duì)應(yīng)即一個(gè)根本可行解對(duì)應(yīng)一個(gè)頂點(diǎn)；線性規(guī)劃問(wèn)題假設(shè)有最優(yōu)解，那么最優(yōu)解一定在凸多邊形的某個(gè)頂點(diǎn)上取得。單純形法解決線性規(guī)劃問(wèn)題時(shí)，在換基迭代過(guò)程中，進(jìn)基的非基變量的選擇要利用比值法，這個(gè)方法是保證進(jìn)基后的單純型依然在解上可行。換

2、基迭代要求除了進(jìn)基的非基變量外，其余非基變量全為零。檢驗(yàn)最優(yōu)性的一個(gè)方法是在目標(biāo)函數(shù)中，用非基變量表示基變量。要求檢驗(yàn)數(shù)全部小于等于零?！爱?dāng)x1由0變到45/2時(shí)，x3首先變?yōu)?，故x3為退出基變量。這句話是最小比值法的一種通俗的說(shuō)法，但是很有意義。這里，x1為進(jìn)基變量，x3為出基變量。將約束方程化為每個(gè)方程只含一個(gè)基變量，目標(biāo)函數(shù)表示成非基變量的函數(shù)。單純型原理的矩陣描述。在單純型原理的表格解法中，有一個(gè)有趣的現(xiàn)象就是，單純型表中的某一列的組成的列向量等于它所在的單純型矩陣的最初的基矩陣的m*m矩陣與其最初的那一列向量的乘積。最初基變量對(duì)應(yīng)的基矩陣的逆矩陣。這個(gè)樣子：所有的檢驗(yàn)數(shù)均小于或等于

3、零，有最優(yōu)解。但是如果出現(xiàn)非基變量的檢驗(yàn)數(shù)為0，那么有無(wú)窮多的最優(yōu)解，這時(shí)應(yīng)該繼續(xù)迭代。解的結(jié)果應(yīng)該是：X*= aX1*+(1-a)X2*0<=a<=1說(shuō)明：最優(yōu)解有時(shí)不唯一，但最優(yōu)值唯一；在實(shí)際應(yīng)用中，有多種方案可供選擇；當(dāng)問(wèn)題有兩個(gè)不同的最優(yōu)解時(shí)，問(wèn)題有無(wú)窮多個(gè)最優(yōu)解。無(wú)最優(yōu)解的情況就是：應(yīng)該進(jìn)基的變量所對(duì)應(yīng)的列的系數(shù)全部小于零。假設(shè)存在某個(gè)j>0,且所有的aij <0，那么不存在有界最優(yōu)解。人為地構(gòu)造一個(gè)單位矩陣來(lái)充當(dāng)初始可行基，再通過(guò)單純形迭代將它們逐個(gè)地從基變量中替換出來(lái)。假設(shè)經(jīng)過(guò)基的變換，基變量中不再含有非零的人工變量，這表示原問(wèn)題有解。假設(shè)在最終表中當(dāng)所有

4、Cj-zj 0 ，而在其中還有某個(gè)非零人工變量，這表示無(wú)可行解。大M法原理核心：打破原來(lái)的約束，再設(shè)法恢復(fù)。大M法根本思想：假定人工變量在基變量中的價(jià)值系數(shù)為一個(gè)絕對(duì)值很大的-M (M>>0,對(duì)于極小化問(wèn)題用+M),這樣只要基變量中還存在人工變量,目標(biāo)函數(shù)就不可能實(shí)現(xiàn)極值。兩階段法原理：第一階段是據(jù)給定的問(wèn)題構(gòu)造其輔助問(wèn)題，為原問(wèn)題求初始根本可行解。加上人工變量后，要求的就是人工變量退出，輔助問(wèn)題是人工變量之和的最小值必須為零。第二階段是將第一階段求出的最優(yōu)解，作為第二階段的初始根本可行解，然后在原問(wèn)題的目標(biāo)函數(shù)下進(jìn)展優(yōu)化，以決定原問(wèn)題的最優(yōu)解。注意：?jiǎn)渭冃畏ㄖ?每一步運(yùn)算只能用矩

5、陣初等行變換；2表中第3列(b列)的數(shù)總應(yīng)保持非負(fù)0；3當(dāng)所有檢驗(yàn)數(shù)均非正0時(shí)，得到最優(yōu)單純形表。假設(shè)直接對(duì)目標(biāo)求最h，要求所有檢驗(yàn)數(shù)均非負(fù)；4當(dāng)最優(yōu)單純形表存在非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)為零時(shí)，可能存在無(wú)窮多解；5關(guān)于退化和循環(huán)。如果在一個(gè)根本可行解的基變量中至少有一個(gè)分量xBi=0 (i=1,2,m)，那么稱此根本可行解是退化的根本可行解。一般情況下，退化的根本可行解極點(diǎn)是由假設(shè)干個(gè)不同的根本可行解極點(diǎn)在特殊情況下合并成一個(gè)根本可行解極點(diǎn)而形成的。退化的構(gòu)造對(duì)單純形迭代會(huì)造成不利的影響?？赡艹霈F(xiàn)以下情況：進(jìn)展進(jìn)基、出基變換后，雖然改變了基，但沒(méi)有改變根本可行解極點(diǎn)，目標(biāo)函數(shù)當(dāng)然也不會(huì)改進(jìn)。進(jìn)展假

6、設(shè)干次基變換后，才脫離退化根本可行解極點(diǎn)，進(jìn)入其他根本可行解極點(diǎn)。這種情況會(huì)增加迭代次數(shù)，使單純形法收斂的速度減慢。在特殊情況下，退化會(huì)出現(xiàn)基的循環(huán)，一旦出現(xiàn)這樣的情況，單純形迭代將永遠(yuǎn)停留在同一極點(diǎn)上，因而無(wú)法求得最優(yōu)解。二、對(duì)偶問(wèn)題和靈敏度分析對(duì)偶問(wèn)題的根本性質(zhì)：對(duì)偶問(wèn)題(D)的對(duì)偶問(wèn)題，是原問(wèn)題(P)；假設(shè)X/是問(wèn)題(P)的一可行解， Y/是問(wèn)題(D)的一個(gè)可行解，那么有:CX/Y/b。假設(shè)X*,Y*分別為問(wèn)題(P)和問(wèn)題(D)的可行解，且CX*=Y*b；那么X*和Y*分別為問(wèn)題(P)和問(wèn)題(D)的最優(yōu)解。假設(shè)問(wèn)題(P)的目標(biāo)函數(shù)值Z無(wú)上界，那么問(wèn)題(D)無(wú)可行解；假設(shè)問(wèn)題(D)的目標(biāo)函

7、數(shù)值W無(wú)下界，那么問(wèn)題(P) 無(wú)可行解。對(duì)偶定理：假設(shè)問(wèn)題(P)和問(wèn)題D之一有最優(yōu)解，那么另一個(gè)問(wèn)題也一定有最優(yōu)解，且目標(biāo)函數(shù)值相等。由對(duì)偶定理可知，從原問(wèn)題的最終單純表中可直接得到其對(duì)偶問(wèn)題的最優(yōu)解。在兩個(gè)互為對(duì)偶的線性規(guī)劃中，可任選一個(gè)進(jìn)展求解。假設(shè)X*,Y*分別為問(wèn)題(P)和問(wèn)題(D)的可行解，且CX*=Y*b；那么，X*和Y*分別為問(wèn)題(P)和問(wèn)題(D)的最優(yōu)解。用對(duì)偶性質(zhì)重新解釋單純形法。單純形法：在整個(gè)迭代過(guò)程中，始終保持該問(wèn)題解的可行性即滿足，而其對(duì)偶問(wèn)題的互補(bǔ)解初始時(shí)并不滿足可行性條件即檢驗(yàn)數(shù)不完全部小于等于0；當(dāng)不可行性完全消失即滿足0時(shí)，原問(wèn)題和對(duì)偶問(wèn)題同時(shí)到達(dá)最優(yōu)。對(duì)偶單

8、純形法：在整個(gè)迭代過(guò)程中，始終保持其對(duì)偶問(wèn)題解的可行性即0，而該問(wèn)題的初始解并不滿足可行性條件即不完全部大于等于0；當(dāng)不可行性完全消失即滿足時(shí)，原問(wèn)題和對(duì)偶問(wèn)題同時(shí)到達(dá)最優(yōu)。對(duì)偶單純形法步驟：列出初始單純形表，保證所有的檢驗(yàn)數(shù);檢驗(yàn)：假設(shè)滿足，那么獲得最優(yōu)解，否那么下一步;基變換首先確定退出基變量，其次決定進(jìn)入基變量，然后求新的根本可行解。返回到2。影子價(jià)格對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋三種資源A、B、C，價(jià)格為Y*=(7/2,0,1/2)，三種資源剩余量分別為0,25/2,0，目標(biāo)函數(shù)：W =7/2×45 +0×80 +1/2×90 = 405/2。經(jīng)濟(jì)意義：反映了資源與總

9、收益之間的關(guān)系，即當(dāng)?shù)趇種資源每增加一個(gè)單位時(shí)，在其他條件不變的情況下，該資源對(duì)目標(biāo)值的奉獻(xiàn)就是yi。靈敏度分析研究線性規(guī)劃中，的變化對(duì)最優(yōu)解的影響。目標(biāo)函數(shù)系數(shù)C價(jià)格變化的靈敏度分析：C的變化導(dǎo)致檢驗(yàn)數(shù)的變化，如果新的檢驗(yàn)數(shù)小于等于零，那么原來(lái)的解依然是最優(yōu)解；如果新的檢驗(yàn)數(shù)大于零，那么新的問(wèn)題還沒(méi)有取到最優(yōu)解，還需要進(jìn)一步運(yùn)算才行。是判斷是否繼續(xù)的標(biāo)準(zhǔn)。對(duì)于基變量的變化，變化值如果小于檢驗(yàn)數(shù)的相反數(shù)，那么最優(yōu)解不變?；懔肯禂?shù)發(fā)生改變將改變所有變量檢驗(yàn)數(shù)。增加一個(gè)新變量的靈敏度分析：如果該行的檢驗(yàn)數(shù)為小于等于零，那么新變量為非基變量，此表到達(dá)最優(yōu)。反之，就要迭代求解。如何求檢驗(yàn)數(shù)很重要，要

10、用到第一章中的知識(shí)。這里要了解各項(xiàng)的含義。增加一個(gè)新約束的靈敏度分析，將最優(yōu)解代入新的約束中，假設(shè)滿足新約束，那么原最優(yōu)解不變；假設(shè)不滿足新約束，那么原最優(yōu)解改變，將新增的約束條件添入最終的單純形表中，并增加一個(gè)基變量，繼續(xù)迭代。添加新約束后，有時(shí)要對(duì)原問(wèn)題所對(duì)偶單純形法，并且要消元構(gòu)造單位陣，基矩陣。新約束條件的常數(shù)項(xiàng)至少為多少時(shí)不影響原最優(yōu)解？對(duì)偶單純形法非常重要！三.運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題的一般描述：設(shè)某種物資有m個(gè)產(chǎn)地 A1 A2,Am ,其產(chǎn)量分別為 a1 a2,am ,另外有n個(gè)銷(xiāo)地 B1 B2,Bn ,其銷(xiāo)量分別為 b1 b2,bn ,從Ai到Bj的單位運(yùn)費(fèi)為Cij(i=1,2,m;j

11、=1,2,n)，試問(wèn)應(yīng)如何組織調(diào)運(yùn)才能使總運(yùn)費(fèi)最低。產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題模型特點(diǎn)：由平衡條件易知：m+n個(gè)方程線性相關(guān)，而任意m+n 1個(gè)方程線性無(wú)關(guān)；基變量的個(gè)數(shù)為m+n 1，非基變量的個(gè)數(shù)為mn-m+n1=m1n 11，有無(wú)限多方案；系數(shù)矩陣只包括1和0。有產(chǎn)銷(xiāo)不平衡問(wèn)題，a的和大于b的和，為產(chǎn)大于銷(xiāo)的問(wèn)題。解決運(yùn)輸問(wèn)題應(yīng)該運(yùn)用運(yùn)輸單純型法，步驟是：1確定初始根本可行解初始方案，這里有最小元素法和元素差額法。最小元素法：列出運(yùn)輸表，表中xij位置暫先空著，在表中找出單位運(yùn)價(jià)最小者Ckt，取xkt=minak，bt把xkt的值填在相應(yīng)的格內(nèi)(假設(shè)有幾個(gè)單位運(yùn)價(jià)同時(shí)到達(dá)最小，就任取其中之一；如果a

12、k>bt劃去第t列，第k行的產(chǎn)量調(diào)整為ak-bt；如果 ak<bt劃去第k行，第t列的銷(xiāo)量調(diào)整為bt-ak；如果 ak=bt劃去第t列，第k行的產(chǎn)量調(diào)整為0，或劃去第k行，第t列的銷(xiāo)量調(diào)整為0。2檢驗(yàn)計(jì)算所有非基變量xij的檢驗(yàn)數(shù)位勢(shì)法。位勢(shì)法：首先將數(shù)字格基變量的單價(jià)Cij分解為行位ui和列位vj即：ui+vj=Cij數(shù)字格。根據(jù)方程組解出ui和vj；然后通過(guò)ui和vj計(jì)算出非基變量的檢驗(yàn)數(shù)。通常令u1=0解方程組，得行列的位勢(shì)值。其中，非基變量檢驗(yàn)數(shù)為Cij-ui+vj。最優(yōu)性條件：所有的非基變量檢驗(yàn)數(shù)均大于等于0，假設(shè)不滿足此條件轉(zhuǎn)入3。3基變換方案改進(jìn)。閉回路幾何法：從空格

13、非基變量所在格出發(fā)，沿垂直或水平方向前進(jìn)；在前進(jìn)的過(guò)程中可穿過(guò)數(shù)字格、也可穿過(guò)空格，在某個(gè)適當(dāng)?shù)臄?shù)字格內(nèi)轉(zhuǎn)彎900，經(jīng)過(guò)這樣假設(shè)干次轉(zhuǎn)向后回到出發(fā)點(diǎn)，形成一個(gè)閉回路?？梢宰C明*：每一個(gè)空格都有并且只有一條閉回路存在且唯一，其形狀可能是矩形、也可能是曲折的多邊形。然后確定進(jìn)基變量和退基變量，進(jìn)基變量就是檢驗(yàn)數(shù)小于0的空格，退基變量是從該進(jìn)基變量出發(fā)，運(yùn)用閉回路法，在轉(zhuǎn)角處，從起點(diǎn)開(kāi)場(chǎng)標(biāo)“+、“-、“+、“-，標(biāo)“-的量中，最小的一個(gè)退基，減去運(yùn)輸量值，其余的標(biāo)“+的加上該運(yùn)輸量值，標(biāo)“-的減去該運(yùn)輸量值。產(chǎn)銷(xiāo)不平衡問(wèn)題：要虛設(shè)一個(gè)行或列，這里，(1)有數(shù)字格基變量的個(gè)數(shù)為m+n-1,如果缺少數(shù)字

14、必須添0補(bǔ)救；(2)當(dāng)最終表中某個(gè)非基變量檢驗(yàn)數(shù)為0時(shí)，說(shuō)明該問(wèn)題有兩個(gè)根本可行解均為最優(yōu)解。四.目標(biāo)規(guī)劃和整數(shù)規(guī)劃目標(biāo)規(guī)劃分為單目標(biāo)規(guī)劃、多目標(biāo)規(guī)劃。多目標(biāo)規(guī)劃中有級(jí)別一樣的目標(biāo)規(guī)劃和具有優(yōu)先級(jí)目標(biāo)規(guī)劃。假設(shè)利潤(rùn)目標(biāo)為140百元，此目標(biāo)稱之為預(yù)定目標(biāo)，實(shí)際完成的量與預(yù)定目標(biāo)之間可能出現(xiàn)偏差，通常用d+、d-d+、d-0表示，稱為偏差變量。其中：d+表示超過(guò)預(yù)定指標(biāo)的局部，d-表示未到達(dá)預(yù)定指標(biāo)的局部。在客觀條件下，最終完成的結(jié)果可能出現(xiàn)以下三種情況：d+>0,d-=0說(shuō)明超額完成預(yù)定指標(biāo)；d->0,d+=0說(shuō)明未到達(dá)預(yù)定指標(biāo)；d+ =d- =0說(shuō)明恰好完成預(yù)定指標(biāo)。在新的規(guī)劃問(wèn)題

15、中，需要添加一個(gè)目標(biāo)約束，目標(biāo)約束的形式由其具體要完成的目標(biāo)表示，比方，原來(lái)的線性規(guī)劃的目標(biāo)函數(shù)是MaxZ=8x1 + 6x2，現(xiàn)在的新的線性規(guī)劃中就要添加這樣的目標(biāo)約束：8x1 + 6x2+d-d+=140。意思就是：盡量到達(dá)這個(gè)目標(biāo)，如果達(dá)不到，加上一個(gè)便可以到達(dá)了。目標(biāo)規(guī)劃中，重要特征如下：增加了目標(biāo)約束；目標(biāo)中只出現(xiàn)偏差變量且為求極小化問(wèn)題；d+×d-=0。單目標(biāo)規(guī)劃求解：用單純形法求滿意解,注意求極小化問(wèn)題最優(yōu)性條件是檢驗(yàn)數(shù)全部大于等于零。多目標(biāo)規(guī)劃求解中級(jí)別一樣的多目標(biāo)規(guī)劃的數(shù)學(xué)模型：實(shí)現(xiàn)利潤(rùn)目標(biāo)122百元，產(chǎn)品A的產(chǎn)量不多于10，這時(shí)設(shè)：di+,di-(i=1,2)分別

16、為超過(guò)目標(biāo)值的局部，及未完成目標(biāo)值的局部。目標(biāo)函數(shù)是minZ=d1-+d2+目標(biāo)約束是：8x1 + 6x2+d1- d1+=122和x1+d2-d2+=10。這里，分析一下語(yǔ)句，實(shí)現(xiàn)目標(biāo)利潤(rùn)為122百元，但是有可能達(dá)不到這個(gè)數(shù)，所以，盡量達(dá)不到的負(fù)偏差變量要小。A的產(chǎn)量不多于10，即便多于10，也沒(méi)關(guān)系，但是正偏差變量要盡量小。因此，得目標(biāo)函數(shù)。多目標(biāo)規(guī)劃求解中具有優(yōu)先級(jí)的多目標(biāo)規(guī)劃數(shù)學(xué)模型：P1:充分利用設(shè)備有效臺(tái)時(shí)，不加班；P2:產(chǎn)品B的產(chǎn)量不多于4；P3:實(shí)現(xiàn)利潤(rùn)130百元。最重要的是1號(hào)，在2號(hào)和3號(hào)完不成的情況下，也要優(yōu)先保證1號(hào)完成。但是，并不是說(shuō)，1號(hào)完成之后，2號(hào)和3號(hào)才能完成

17、。在實(shí)際生活中，也有1號(hào)未完成但是2號(hào)和3號(hào)完成的情況。模型約束：4x1 + 2x2+ d1- d1+= 60 x2 + d2- d2+= 4 8x1 + 6x2+ d3- d3+= 130 2x1 + 4x248 x1，x2，di+,di-(i=1,2,3) 0目標(biāo)函數(shù)：MIN Z(x)= P1d1- + d1+ P2 d2+ P3d3-在這里，1號(hào)目標(biāo)是正負(fù)偏差量之和，就是取要恰好到達(dá)之意。圖解法求解目標(biāo)規(guī)劃：按照上面的規(guī)劃，可以有以下步驟：1根據(jù)系統(tǒng)約束，確定可行域；2不考慮偏差，即：di+=di-=0i=1,2,3)，然后按順序作出目標(biāo)約束相應(yīng)的直線，并標(biāo)出di+>0,di-&g

18、t;0的方向；3按優(yōu)先順序找出該目標(biāo)的滿意解。目標(biāo)規(guī)劃的目標(biāo)：1決策人希望恰好實(shí)現(xiàn)預(yù)定的第i個(gè)目標(biāo)，MinZ= di+ di-；2決策人不希望超過(guò)預(yù)定的第i個(gè)目標(biāo)，MinZ= di+；3決策人希望超過(guò)預(yù)定的第i個(gè)目標(biāo)，minZ=di-。整數(shù)規(guī)劃：線性規(guī)劃中要求決策變量全部或局部為整數(shù)。分為以下，純整數(shù)規(guī)劃:所有決策變量xj(j=1,2,n)均取整數(shù)；混合整數(shù)規(guī)劃:局部決策變量取整數(shù)；0-1整數(shù)規(guī)劃:所有決策變量只取0或1，這類(lèi)變量又稱為邏輯變量。經(jīng)典方法是分支定界法和割平面法。分支定界法步驟：先不考慮變量的整數(shù)約束，求解相應(yīng)的線性規(guī)劃；分支：如果求解某一個(gè)值并非整數(shù)，那么就予以分支，比方，由于

19、x1，x2均不滿足整數(shù)條件，故可由x1或x2進(jìn)展分枝，使x1滿足：x13 或 x14，將3< x1<4 的非整數(shù)局部割掉，于是問(wèn)題B0分成了兩個(gè)子問(wèn)題B1,B2，然后分別求出其最優(yōu)解，B1最優(yōu)解:X1*=3，8/3，Z1=141/3，B2最優(yōu)解X2*=4，1，Z2=14；定界：?jiǎn)栴}B2已獲得整數(shù)最優(yōu)解，可將Z2=14作為問(wèn)題A的下界，同時(shí)將Z0=143/4作為問(wèn)題A的上界?？梢詳喽╖2=14 Z < Z0=143/4；返回到2繼續(xù)對(duì)B1中的x2進(jìn)展分枝，使x2滿足：x22或x23將2< x2< 3之間的非整數(shù)局部割掉。于是問(wèn)題B2又分成了兩個(gè)子問(wèn)題B3和B4再分別

20、求出其最優(yōu)解。割平面法步驟：不考慮其整數(shù)條件,用單純形法求解相應(yīng)的線性規(guī)劃問(wèn)題，求出最終單純形表；構(gòu)造Gomory約束割平面：在最終單純形表中，任意選擇一個(gè)非整數(shù)變量如x2，寫(xiě)出該變量所在行的方程式：x2 + 1/2x31/2x4=5/2，將各變量的系數(shù)及常數(shù)項(xiàng)分解為整數(shù)與非負(fù)真分?jǐn)?shù)之和；再將系數(shù)為整數(shù)的變量移到方程式左端，系數(shù)為分?jǐn)?shù)的變量移到方程式右端，x2x4-2=1/2-1/2x3+1/2x4。求得Gomory約束為：1/2-1/2x3+1/2x40將Gomory約束化為方程，填入到最終單純形表中，繼續(xù)求問(wèn)題的最優(yōu)解。用對(duì)偶單純性法求解。分派問(wèn)題使用0-1整數(shù)規(guī)劃的一種特殊類(lèi)型，但是由于

21、它的形式比較特殊，所以有自己特殊的解法。有n項(xiàng)任務(wù),指派n個(gè)人(廣義)去完成,第i個(gè)人完成第j項(xiàng)任務(wù)的效率為Cij(i=1,2,n;j=1,2,n)；要求每個(gè)人只能承擔(dān)一項(xiàng)任務(wù),并且每一項(xiàng)任務(wù)都有一個(gè)人個(gè)來(lái)承擔(dān)；問(wèn)如何分派可以使總的效率到達(dá)最高。Cij為效率矩陣。建立數(shù)學(xué)模型：1，分派第i個(gè)人去承擔(dān)第j項(xiàng)任務(wù)；0，不分派第i個(gè)人去承擔(dān)第j項(xiàng)任務(wù)。要求每人只能承擔(dān)一項(xiàng)工作，每項(xiàng)工作只能由一個(gè)人來(lái)承擔(dān)。它是特殊的0-1規(guī)劃；它是m=n，ai=bj=1的特殊運(yùn)輸問(wèn)題；它的所有可行解的個(gè)數(shù)為n！。同解性原理：如果在效率矩陣Cij的第ii=1,2,n行列加減一個(gè)常數(shù)ki，那么新效率矩陣與原效率矩陣有一樣

22、的最優(yōu)解。匈牙利解法：化簡(jiǎn)效率矩陣：使其每行、每列至少有一個(gè)零元素；檢驗(yàn)：用盡可能少的直線去覆蓋所有的零元素，當(dāng)覆蓋線的條數(shù)n0=n 時(shí),可轉(zhuǎn)入4確定最優(yōu)方案,當(dāng) n0<n 時(shí)轉(zhuǎn)入下一步(3)繼續(xù)化簡(jiǎn)；移動(dòng)零元素：在未被直線覆蓋的元素中找出最小元，對(duì)不在覆蓋線上的元素減去這個(gè)最小元，在兩覆蓋線交點(diǎn)上加上這個(gè)最小元，其他元素不變。具體步驟：變換指派問(wèn)題的費(fèi)用矩陣，使其在各行各列都出現(xiàn)0元素，首先每行元素減去該行的最小元素，然后每列減去該列的最小元素；進(jìn)展試指派畫(huà)，從含0元素最少的行或列開(kāi)場(chǎng)，圈出一個(gè)0元素，用表示，然后劃去該所在的行和列中的其余0元素，用×表示，依次類(lèi)推。假設(shè)矩陣中的的個(gè)數(shù)等于n，那么得最優(yōu)解，假設(shè)矩陣中的的個(gè)數(shù)<n，那么進(jìn)展第三步；做能復(fù)蓋所有0元素的最小直線集合：對(duì)沒(méi)有的行打號(hào)、對(duì)打號(hào)的行上所有0元素的列打號(hào)、再對(duì)打號(hào)的列上所有的行打號(hào)、重復(fù)以上步驟直到得不出新的打號(hào)為止，對(duì)沒(méi)有打號(hào)的行畫(huà)橫線，所有打號(hào)的列畫(huà)縱線，所得到的直線既是復(fù)蓋所有0元素的最小直線集合；在沒(méi)有被直線復(fù)蓋的元素中找出最小元素，讓打號(hào)的列加上這個(gè)元素，打號(hào)的行減去這個(gè)元素。求最大效率的問(wèn)題，求最小效率的問(wèn)題，都很重要。五.矩陣對(duì)策我們稱具