1、. .運籌學復習一、單純形方法表格、人工變量、根底知識線性規劃解的情況：唯一最優解、多重最優解、無界解、無解。其中，可行域無界，并不意味著目標函數值無界。無界可行域對應著解的情況有：唯一最優解、多重最優解、無界解。有界可行域對應唯一最優解和多重最優解兩種情況。線性規劃解得根本性質有：滿足線性規劃約束條件的可行解集可行域構成一個凸多邊形；凸多邊形的頂點極點與根本可行解一一對應即一個根本可行解對應一個頂點；線性規劃問題假設有最優解，那么最優解一定在凸多邊形的某個頂點上取得。單純形法解決線性規劃問題時，在換基迭代過程中，進基的非基變量的選擇要利用比值法，這個方法是保證進基后的單純型依然在解上可行。換

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

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

4、Cj-zj 0 ，而在其中還有某個非零人工變量，這表示無可行解。大M法原理核心：打破原來的約束，再設法恢復。大M法根本思想：假定人工變量在基變量中的價值系數為一個絕對值很大的-M (M>>0,對于極小化問題用+M),這樣只要基變量中還存在人工變量,目標函數就不可能實現極值。兩階段法原理：第一階段是據給定的問題構造其輔助問題，為原問題求初始根本可行解。加上人工變量后，要求的就是人工變量退出，輔助問題是人工變量之和的最小值必須為零。第二階段是將第一階段求出的最優解，作為第二階段的初始根本可行解，然后在原問題的目標函數下進展優化，以決定原問題的最優解。注意：單純形法中1每一步運算只能用矩

5、陣初等行變換；2表中第3列(b列)的數總應保持非負0；3當所有檢驗數均非正0時，得到最優單純形表。假設直接對目標求最h，要求所有檢驗數均非負；4當最優單純形表存在非基變量對應的檢驗數為零時，可能存在無窮多解；5關于退化和循環。如果在一個根本可行解的基變量中至少有一個分量xBi=0 (i=1,2,m)，那么稱此根本可行解是退化的根本可行解。一般情況下，退化的根本可行解極點是由假設干個不同的根本可行解極點在特殊情況下合并成一個根本可行解極點而形成的。退化的構造對單純形迭代會造成不利的影響。可能出現以下情況：進展進基、出基變換后，雖然改變了基，但沒有改變根本可行解極點，目標函數當然也不會改進。進展假

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

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

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

9、收益之間的關系，即當第i種資源每增加一個單位時，在其他條件不變的情況下，該資源對目標值的奉獻就是yi。靈敏度分析研究線性規劃中，的變化對最優解的影響。目標函數系數C價格變化的靈敏度分析：C的變化導致檢驗數的變化，如果新的檢驗數小于等于零，那么原來的解依然是最優解；如果新的檢驗數大于零，那么新的問題還沒有取到最優解，還需要進一步運算才行。是判斷是否繼續的標準。對于基變量的變化，變化值如果小于檢驗數的相反數，那么最優解不變。基便量系數發生改變將改變所有變量檢驗數。增加一個新變量的靈敏度分析：如果該行的檢驗數為小于等于零，那么新變量為非基變量，此表到達最優。反之，就要迭代求解。如何求檢驗數很重要，要

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

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

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

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

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

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

16、為超過目標值的局部，及未完成目標值的局部。目標函數是minZ=d1-+d2+目標約束是：8x1 + 6x2+d1- d1+=122和x1+d2-d2+=10。這里，分析一下語句，實現目標利潤為122百元，但是有可能達不到這個數，所以，盡量達不到的負偏差變量要小。A的產量不多于10，即便多于10，也沒關系，但是正偏差變量要盡量小。因此，得目標函數。多目標規劃求解中具有優先級的多目標規劃數學模型：P1:充分利用設備有效臺時，不加班；P2:產品B的產量不多于4；P3:實現利潤130百元。最重要的是1號，在2號和3號完不成的情況下，也要優先保證1號完成。但是，并不是說，1號完成之后，2號和3號才能完成

17、。在實際生活中，也有1號未完成但是2號和3號完成的情況。模型約束：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目標函數：MIN Z(x)= P1d1- + d1+ P2 d2+ P3d3-在這里，1號目標是正負偏差量之和，就是取要恰好到達之意。圖解法求解目標規劃：按照上面的規劃，可以有以下步驟：1根據系統約束，確定可行域；2不考慮偏差，即：di+=di-=0i=1,2,3)，然后按順序作出目標約束相應的直線，并標出di+>0,di-&g

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

19、x1，x2均不滿足整數條件，故可由x1或x2進展分枝，使x1滿足：x13 或 x14，將3< x1<4 的非整數局部割掉，于是問題B0分成了兩個子問題B1,B2，然后分別求出其最優解，B1最優解:X1*=3，8/3，Z1=141/3，B2最優解X2*=4，1，Z2=14；定界：問題B2已獲得整數最優解，可將Z2=14作為問題A的下界，同時將Z0=143/4作為問題A的上界。可以斷定Z2=14 Z < Z0=143/4；返回到2繼續對B1中的x2進展分枝，使x2滿足：x22或x23將2< x2< 3之間的非整數局部割掉。于是問題B2又分成了兩個子問題B3和B4再分別

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

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

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