1、一 線性規(guī)劃1.問題背景：線性規(guī)劃是運籌學中研究較早、發(fā)展較快、應用廣泛、方法較成熟的一個重要分支,它是輔助人們進行科學管理的一種數(shù)學方法.在經(jīng)濟管理、交通運輸、工農(nóng)業(yè)生產(chǎn)等經(jīng)濟活動中，提高經(jīng)濟效果是人們不可缺少的要求，而提高經(jīng)濟效果一般通過兩種途徑：一是技術方面的改進，例如改善生產(chǎn)工藝，使用新設備和新型原材料.二是生產(chǎn)組織與計劃的改進，即合理安排人力物力資源.線性規(guī)劃所研究的是：在一定條件下，合理安排人力物力等資源，使經(jīng)濟效果達到最好.一般地，求線性目標函數(shù)在線性約束條件下的最大值或最小值的問題2.求解方法： a.單純形法：適用的問題：約束條件全部為，右邊常數(shù)全部為非負，對目標函數(shù)的系數(shù)沒有

2、要求。min z=3x1-2x2s.t. x1+2x212 2x1+ x218 x1,x20求解步驟：STEP 0 將線性規(guī)劃問題標準化STEP 1 是否有明顯的初始基礎可行解，如果有，轉STEP 3，否則，轉STEP 2。STEP 2 構造輔助問題，用兩階段法求解輔助問題。如果輔助問題最優(yōu)解的目標函數(shù)值大于0，原問題無可行解，算法終止。否則轉STEP 3。STEP 3 寫出單純形表，將基變量在約束條件中的系數(shù)消為單位矩陣，將基變量在目標函數(shù)中的系數(shù)消為0。轉STEP 4。STEP 4 如果所有非基變量的檢驗數(shù)全為負數(shù)或0，則已獲得最優(yōu)解，算法終止。否則， 選擇檢驗數(shù)為正數(shù)并且絕對值最大的非基

3、變量為進基變量。轉STEP 5。STEP 5 如果進基變量在約束條件中的系數(shù)全為負數(shù)或0，目標函數(shù)無界，算法終止。否則根據(jù)右邊常數(shù)和正的系數(shù)的最小比值，確定離基變量。轉STEP 6。STEP 6 進基變量列和離基變量行交叉的元素稱為主元。對單純形表進行行變換，將主元變?yōu)?，將主元所在列的其他元素變?yōu)?。轉STEP 4。b.對偶單純形法：適用的問題:約束條件中至少有一個是，相應的右邊常數(shù)為非負，目標函數(shù)系數(shù)全部為非負。min z=3x1+2x2s.t. x1+2x212 2x1+ x218 x1,x20求解步驟：步驟1 確定原問題（L）的初始基B，使所有檢驗數(shù) ，即是對偶可行解，建立初始單純形表

4、。步驟2 檢查基變量的取值，若0，則已得最優(yōu)解，計算停；否則求確定單純形表第L行對應的基變量為旋出變量。 步驟3 若所有,則原問題無可行解，計算停；否則，計算確定對應的為旋入變量。 步驟4 以為主元作（L，K）旋轉變換，得新的單純形表，轉步驟2?？梢宰C明，按上述方法進行迭代，所得解始終是對偶可行解。二 運輸問題1.問題背景：一般的運輸問題就是要解決把某種產(chǎn)品從若干個產(chǎn)地調(diào)運到若干個銷地，在每個產(chǎn)地的供應量與每個銷地的需求量已知，并知道各地之間的運輸單價的前提下，如何確定一個使得總的運輸費用最小的方案。2.求解方法:a. 表上作業(yè)法:方法描述：表上作業(yè)法是一種求解運輸問題的特殊的方法，其實質(zhì)是單

5、純形法，它針對運輸問題變量多,結構獨特的情況，大大簡化了計算過程的求解方法求解步驟：1 找出初始基本可行解2. 求各非基變量的檢驗數(shù)，即在表上計算除了上述的m+n-1個數(shù)字格以外的空格的檢驗數(shù)判別是否達到最優(yōu)解,如已是最優(yōu)解，則停止計算,否則轉到下一步。在運輸問題中都存在最優(yōu)解。3. 確定入基變量與出基變量，找出新的基本可行解。在表上用閉回路法調(diào)整。4. 重復2、3直至得到最優(yōu)解。三 目標規(guī)劃1. 問題背景：目標規(guī)劃（Goal programming） 目標規(guī)劃是線性規(guī)劃的一種特殊應用，能夠處理單個主目標與多個目標并存，以及多個主目標與多個次目標并存的問題。2. 求解方法：a. 約束法：方法描

6、述：在多個目標函數(shù)中選擇一個主要目標作為 基本思想： 基本思想 目標函數(shù)，其它目標處理為適當?shù)募s束。 目標函數(shù)，其它目標處理為適當?shù)募s束。求解步驟：min f1 ( x) ( P)s.t. g i ( x) 0, i = 1,2, L, m f j ( x) f j ( x ( 0 ) ), j = 2,3, L, p 第一步： （1）對 j = 1,2, L, p，min f j ( x) (VPj ) s.t. x S，求解單目標問題第二步：選擇整數(shù)r1，確定0 jt，f j0的r個不同閥值第三步：對 t = 0,1,L, r 1 ，分別求解問題：min f k ( x) ( Pt j )

7、s.t. g i ( x) 0, i = 1,2, L, m f j ( x) f jt j 0, j = 1, L, k 1, k + 1,L, p ) 各目標函數(shù) f ( j k ) 可對應不同的 t (t = 0,1,L, r 1（共 有 r p 1 個約束問題）。求解后可得到(VP)的一有 效解集合，是(VP)有效解集合的一個子集。為主目標。b. 分層序列法：求解步驟：1. 把(VP)中的p個目標 f ( x ), L , f ( x ) 按其重 要程度排一次序。依次求單目標規(guī)劃的最優(yōu)解。 22. 過程：無妨設其次序為 f1 , f 2 , L , f p 先求解 四整數(shù)規(guī)劃問題背景：

8、規(guī)劃中的變量（部分或全部）限制為整 數(shù)時，稱為整數(shù)規(guī)劃。若在線性規(guī)劃模 型中，變量限制為整數(shù)，則稱為整數(shù)線 性規(guī)劃求解方法：a.割平面法：方法描述：通過增加新的約束來切割可原問題伴隨規(guī)劃的可行域，使它在不斷縮小的過程中，將原問題的整數(shù)最優(yōu)解逐漸暴露且趨于可行域極點的位置，這樣就有可能用單純形法求出。求解步驟：第一步：用單純形法解松弛問題，得到最優(yōu)單純形表。第二步：求一個割平面方程，加到最優(yōu)單純形表中，用對偶單純形法繼續(xù)求解。第三步：若沒有得到整數(shù)最優(yōu)解，則繼續(xù)作割平面方程，轉第二步。b.匈牙利法：方法描述：在現(xiàn)實生活中，有各種性質(zhì)的指派問題(assignment problem)。指派問題也是

9、整數(shù)規(guī)劃的一類重要問題。例如：有n項工作需要分配給n個人(或部門)來完成；有n項合同需要選擇n個投標者來承包；有n個班級需要安排在各教室上課等。諸如此類問題，它們的基本要求是在滿足特定的指派要求條件下，使指派方案的總體效果最佳。求解步驟：第一步：變換效率矩陣，使指派問題的系數(shù)矩陣經(jīng)過變換，在各行各列中都出現(xiàn)0元素。具體作法是：先將效率矩陣的各行減去該行的最小非0元素，再從所得系數(shù)矩陣中減去該列的最小非0元素。這樣得到的新矩陣中，每行每列都必然出現(xiàn)零元素。 第二步：用圈0法求出矩陣C1中的獨立零元素。經(jīng)第一步變換后，系數(shù)矩陣中每行每列都已有了獨立零元素；但需要找出n個獨立的0元素。若能找出，就以

10、這些獨立0元素對應的決策變量矩陣中的元素為1，其余為0，就得到了最優(yōu)解。當n較小時，可用觀察法、試探法去找出n個獨立0元素；若n較大時，就必須按照一定的步驟去找，常用的步驟為：(1) 從只有一個0元素的行(或列)開始，給這個0元素加圈，記作。這表示對這行所代表的人，只有一種任務可指派，然后劃去所在列(行)的其他元素，記作，這表示這列所代表的任務已指派完，不必再考慮別人了。(2) 給只有一個0元素列(行的) 0元素加圈，記作。然后劃去所在行(列)的其他元素，記作。(3) 反復進行(1),(2)兩步，直到每一列都沒有未被標記的0元素或至少有兩個未被標記的0元素時止。第三步：進行試指派若情況(1)出

11、現(xiàn)，則可進行指派：令圈0位置的決策變量取值為1，其它決策變量的取值均為0，得到一個最優(yōu)指派方案，停止計算。本例中得到C2后，出現(xiàn)了情況(1)，可令x14=x22=x31=x43=1,其余xij=0。即為最佳指派方案。若情況(2)出現(xiàn)，則再對每行，每列中有兩個未被標記過的0元素任選一個，加上標記，即圈上該0元素。然后給同行、同列的其他未被標記的0元素加標記“”。然后再進行行、列檢驗，可能出現(xiàn)(1)或(3)。若出現(xiàn)(3)，則要轉入下一步。 第四步：作最少直線覆蓋當前所有的0元素（以例題說明）五動態(tài)規(guī)劃問題背景：動態(tài)規(guī)劃問世以來，在經(jīng)濟管理、生產(chǎn)調(diào)度、工程技術和最優(yōu)控制等方面得到了廣泛的應用。例如最

12、短路線、庫存管理、資源分配、設備更新、排序、裝載等問題，用動態(tài)規(guī)劃方法比用其它方法求解更為方便。求解方法：a.分支定界法：方法描述：對有約束條件的最優(yōu)化問題（其可行解為有限數(shù)）的可行解空 間恰當?shù)剡M行系統(tǒng)搜索，這就是分枝與定界內(nèi)容。通常，把全 部可行解空間反復地分割為越來越小的子集，稱為分枝；并且 對每個子集內(nèi)的解集計算一個目標下界（對于最小值問題）， 這稱為定界。在每次分枝后，凡是界限不優(yōu)于已知可行解集目 標值的那些子集不再進一步分枝，這樣，許多子集可不予考慮， 這稱剪枝。這就是分枝定界法的主要思路。 分枝定界法可用于解純整數(shù)或混合的整數(shù)規(guī)劃問題。在二 十世紀六十年代初由Land Doig和

13、Dakin等人提出。由于這方 法靈活且便于用計算機求解，所以現(xiàn)在它已是解整數(shù)規(guī)劃的 重要方法。目前已成功地應用于求解生產(chǎn)進度問題、旅行推 銷員問題、工廠選址問題、背包問題及分配問題等。求解步驟：（i）先不考慮整數(shù)限制，即解相應的線性規(guī)劃（ii）記作 z, 即 0 z * 356. （ii）因為 x1 , x2 當前均為非整數(shù)，故不滿足整數(shù)要求， 任選一個進行分枝。設選 x1 進行分枝，把可行集分成 2個子集（iii）對問題B1再進行分枝得問題B11和B12（iv）對問題B2再進行分枝得問題 B21和B22,它們的最優(yōu)解為（v） 將 B22 無可行解。 B21 , B22 剪枝。 于是可以斷定原

14、問題的最優(yōu)解六最短路徑問題背景：最短路問題就是在一個網(wǎng)絡圖中，給定一個起點，要求其到另一頂點的權數(shù)最小的距 離。最短路問題在實際生活中具有廣泛的應用，如管道鋪設、線路選擇等問題，還有些如設 備更新、投資等問題也都可以歸結為求最短路問題。a. 最短路的矩陣算法：方法描述：最短路的矩陣算法（適用于所有權非負的情況） 最短路的矩陣算法是將圖表示成是矩陣形式， 然后利用矩陣表計算出最短路。 矩陣算法 的原理與 Dijkstra 算法標號算法完全相同，只是它采用了矩陣形式，顯得更為簡潔，有利于 計算機計算。下面先介紹圖的矩陣表示。 （1） 圖的矩陣表示 無權圖矩陣表示：兩頂點之間有邊相連的記為“1” ，

15、無邊相連的記為“0” ，對角線上 記為“0” 。所得到的矩陣一定是對陣矩陣。 賦權無向圖矩陣表示：兩頂點之間有邊相連的，寫上它們的權數(shù)，無邊相連的記為 “” ，對角線上記為 0。所得到的矩陣也一定是對陣矩陣。方法步驟：第一步： 在已標號的第一行中找最小的元素 a13=1,將其圈起來， 將其所在的第三列劃去， 給第三行標號第二步:類似的第二步，第三步，第四步均可由算法的步驟得矩陣 B、C、D。由于終點 v4 已 得到標號 5，故知 v1 到 v4 的最短路是 5。第三步:下面再找出 v1 到 v4 的最短路走法。用逆推的方法。第四步：若迭代到某一步 k 時，有 d(k)(j)=d(k-1)(j)

16、 則運算結束，且 d(j)=d(k)(j) (j=1,2,3,n)中 v1 到其它各點的最短路b. Dijkstra算法（適用于所有權非負的情況）方法描述： Dijkstra 算法 Dijkstra 算法是 E.W. Dijkstra 于 1959 年提出的， 是目前公認的對所有權非負的情況的最 好算法。它給出從指定頂點到圖中每個頂點的最短路。方法步驟：令 u1=0,ujwij(若不存在點 1 到點 j 的路則記 w1j=),p=1,T=2,3,n(p 為以確定的點之集，T 為未確定的點之集)；（指出永久標號）在 T 中找出一點 k 使得 uk= min uj。令 p:=pk,T=Tk,若 T

17、=空集算法結束，并令 di=ui(I=1,2,n),否則進入(3)； （修改臨時標號）對 T 中每一個點 j，令 uj=minuj,uk+wij，然后返回。 對于無向圖也可以有最短路問題。實際上可以把賦權無向圖看成賦權有向圖，只需把 一條邊u,v看成兩條弧(u,v)和(v,u)，并且他們的權都等于u,v的權。顯然，所有的權必須 非負。 。 例 6.2.1 求圖 6-2-1 中點 v1 到其它各點的最短路（弧旁的數(shù)字表示距離）七最大流問題問題背景：流量問題在實際中是一種常見的問題。如公路系統(tǒng)中有車輛流量問題，供電系統(tǒng)中有 電流量問題等等。 最大流問題是在單位時間內(nèi)安排一個運送方案， 將發(fā)點的物質(zhì)沿著弧的方 向運送到收點，使總運輸量最大。求解方法：a.標號法：方法描述：標號法是一種圖上迭代計算方法，該算法首先給出一個初始可行流，通過標號找出一 條增廣鏈，然后調(diào)整增廣鏈上的流量，得到更大的流量。再用標號找出一條新的增廣鏈，再 調(diào)整直到標號過程不能進行下去為止，這時的可行流就是最大流。 方法步驟：第一步 找出一個初始可行