2016運籌學總復習

1、運籌學,復習,第1章 緒論,用科學方法分析管理及工程問題，為決策提供依據(jù)。目標：在企業(yè)經營內外環(huán)境的限制下，實現(xiàn)資源效用最大。,第2章線性規(guī)劃及單純形法,一般線性規(guī)劃的數(shù)學模型圖解法單純形法,線性規(guī)劃的一般模型,標準形式,可行解可行域最優(yōu)解基基向量非基向量基變量非基變量基解基可行解,建立坐標系找出可行域繪出目標函數(shù)圖形求出最優(yōu)解,圖解法步驟,唯一最優(yōu)解無窮多最優(yōu)解無界解（或無最優(yōu)解）無可行解,

2、線性規(guī)劃問題解的情況,凸集和頂點線性規(guī)劃問題的基可行解X對應線性規(guī)劃問題可行域（凸集）的頂點。若線性規(guī)劃問題有最優(yōu)解，一定在一某個頂點得到。,單純形法步驟：確定初始基可行解；從初始基可行解轉換為另一基可行解；最優(yōu)性檢驗和判別。,1、線性規(guī)劃的標準形式,目標函數(shù)：約束條件：,,目標系數(shù),,決策變量,技術系數(shù),右端項,,,,1、min Z=CX —> max Z= -CX 2、約束條件為“≤” 轉換為“=”方法：

3、 在s.t.中左端加上一個“松弛變量”，使“≤”變?yōu)椤?”。同時，在目標函數(shù)中，令松弛變量的目標系數(shù)為0。 3、約束條件為“≥”轉換為“=”方法： 在s.t.中左端減去一個“剩余變量”，使“≥”變?yōu)椤?”。同時，在目標函數(shù)中，令剩余變量的目標系數(shù)為0。,2、非標準形式的標準化方法,4、決策變量xi≤0 —> xj = - xi 5、決策變量的符號不受限制 xj = xj’- xj’’， xj’，xj’’ ≥

4、0.,,2024/3/18,14,3、圖解法,對于只含有兩個變量的線性規(guī)劃問題，可通過在平面上作圖的方法求解。其步驟如下：,,,,①建立平面直角坐標系；②圖示約束條件，找出可行域；③圖示目標函數(shù)，即為一條直線；④將目標函數(shù)直線沿其法線方向在可行域邊界平移直至函數(shù)達到最優(yōu)值為止，目標函數(shù)達到最優(yōu)值的點就為最優(yōu)點。,4、單純形法的計算步驟,（1）將問題化為標準型；（2）求出線性規(guī)劃的初始基可行解，列出初始單純形表；（3）進行最優(yōu)性

5、檢驗： 如果表中所有檢驗數(shù) ，則表中的基可行解就是問題的最優(yōu)解，計算停止。否則繼續(xù)下一步。,,（4）從一個基可行解轉換到另一個目標值更大的基可行解，列出新的單純形表。,確定換入基的變量。選擇 ，對應的變量xj作為換入變量，當有一個以上檢驗數(shù)大于0時，一般選擇最大的一個檢驗數(shù)，即： 其對應的xk作為換入變量。確定

6、換出變量。根據(jù)下式計算并選擇θ，選最小的θ對應基變量作為換出變量。,用換入變量xk替換基變量中的換出變量，得到一個新的基。對應新的基可以找出一個新的基可行解，并相應地可以畫出一個新的單純形表。（5）重復（3）、（4）步直到計算結束為止。,對偶規(guī)則表,對偶理論：,則其對偶問題的一般形式為,對稱形式的線性規(guī)劃原問題的一般形式為,對稱形式對偶問題,一對對偶問題的關系，只能有下面三種情況之一： 1. 都有最優(yōu)解； 2.一個問題無

7、界，則另一個問題無可行解； 3. 兩個都無可行解.,對偶規(guī)劃可以用線性規(guī)劃的單純形法求解。由對偶原理可見，原問題與對偶問題之間有緊密聯(lián)系，因此我們能夠通過求解原問題來找出對偶問題的解，反之依然?；パa松弛條件就可以解決由原問題的最優(yōu)解直接求出對偶問題的最優(yōu)解。,對偶問題解的求法,,對偶單純形法是求解線性規(guī)劃的另一個基本方法，它是根據(jù)對偶原理和單純形法的原理而設計出來的，因此稱為對偶單純形法。不要簡單地將對偶單純形法理解為求解對

8、偶問題的單純形法。,,第4章 運輸問題,1、運輸問題的數(shù)學模型的建立；2、產銷平衡下運輸問題的基變量個數(shù)與產地、銷地之間的關系（m+n-1），即（m+n-1）個獨立約束方程；3、約束方程都是等式。,,一、確定初始基可行解,運輸問題的初始方案的確定主要有：,最小元素法,伏格爾法,運輸問題,找出初始基可行解，即在產銷平衡表上有（m+n-1）個數(shù)字格。,1、最小元素法的精髓（就近供應，從單位運價表中最小的運價開始確定供銷關系，依次類推，

9、只到給出全部方案為止）；2、Vogel法的核心（最大差額處，優(yōu)先按最小運價進行調整）；3、位勢法求檢驗數(shù)、閉回路法進行調整；4、產銷不平衡時的調整方法。,第5章 目標規(guī)劃,1、目標規(guī)劃的組成與特點；2、目標規(guī)劃的模型（如何建立目標函數(shù)、目標約束建立等）；3、目標函數(shù)中偏差變量的取舍（利潤型目標、成本型目標和合同型目標中偏差變量的取舍）；4、掌握目標規(guī)劃應用方法（不用求解）。,1、目標規(guī)劃的特點,約束一般包括目標約束、系統(tǒng)約

10、束、非負約束三個部分； 最終目標轉換為求偏離多個期望目標值的偏差和最??； 目標及約束仍為線性。,（1）對于利潤型目標，要求是可能實現(xiàn)值超過目標值越多越好，即d+越大越好，則在目標函數(shù)中，不能對d+求最小；（2）對于成本型目標，要求可能實現(xiàn)值低于目標值越多越好，即d-越大越好，則在目標函數(shù)中不能對d-求最?。唬?）對于合同型目標，要求跟目標保持一致，不超過也不短缺，即要求d+和d-都最小，則在目標函數(shù)中應將兩者綜合考慮。,2、目標

11、函數(shù)中偏差變量的優(yōu)化,第6章 整數(shù)規(guī)劃,分支定界法割平面法指派問題及匈牙利法,分枝定界法：將原整數(shù)規(guī)劃問題分枝—分為兩個子規(guī)劃,再解子規(guī)劃的伴隨規(guī)劃……通過求解一系列子規(guī)劃的伴隨規(guī)劃及不斷地定界。最后得到原整數(shù)規(guī)劃問題的整數(shù)最優(yōu)解。,從(LP)的最優(yōu)解中，任選一個不為整數(shù)的分量xr,,將最優(yōu)單純形表中該行的系數(shù)arj′和 br′分解為整數(shù)部分和非負真分數(shù)部分之和， 并以該行為源行，按作割平面方程。,將所得的割平面方程，作

12、為一個新的約束條件置于最優(yōu)單純形表中同時增加一個單位列向量），用對偶單純形法求出新的最優(yōu)解。,割平面法,匈牙利算法。算法主要依據(jù)以下事實：如果將系數(shù)矩陣C=（Cij）中一行（或一列）的每一元素都加上或減去同一個數(shù)，得到一個新矩陣B=（bij），則以C和B為系數(shù)矩陣的指派問題具有相同的最優(yōu)指派。系數(shù)矩陣中獨立 0 元素的最多個數(shù)等于能覆蓋所有 0 元素的最少直線數(shù)。,指派問題,Step 1、先對效率矩陣進行列變換，使其各行各列中都出現(xiàn)

13、 0 元素。,效率矩陣變換方法為：從效率矩陣 C 的每行元素中減去該行的最小元素,得矩陣 B ；從矩陣 B 中每列元素中減去該列的最小元素得矩陣 C1 。,,min 0 0 5 0,,Step 2、確定C1中線性獨立的0元素.,從第一行開始，若該行只有一個0元素，就對這個0元素加圈，然后劃去其所在列的其它0元素;若該行沒有其它0元素或有兩個以上0元素（已劃去的不計），轉下一行；直到最后一行為止。,然后，

14、從第一列開始，若該列只有一個0元素，就對這個0元素加圈（同樣不考慮已劃的）,再劃去其所在行的其它0元素；若該列沒有0元素或有兩個以上0元素，則轉下列直到最后一列為止。,,,,重復上述步驟。,,,上述步驟可能出現(xiàn)三種情況,情況一：矩陣每行都有一個打圈的 0 元素。此時得到問題的最優(yōu)解。,情況二：有多于兩行或兩列存在兩個以上的未處理的 0 元素，即出現(xiàn) 0 元素的閉回路。此時，可從中任選一個 0元素加圈，劃掉其同行同列的 0 元素，再重復上

15、述兩個步驟。,情況三：矩陣中所有 0 元素或被加圈，或被劃去，而已加圈的 0 元素m小于矩陣的行數(shù)n。即矩陣中至少存在有一行不含加圈的 0 元素。轉步驟三。,,,,,,Step 3 尋找能覆蓋C1中所有0元素的最小直線數(shù),(1)按照從上到下、從左到右的順序對C1沒有加圈的0元行打√號；(2)對已打√號的行中未加圈0元的列打√號；(3)對已打√號的列中加圈0元的行打√號；(4)重復下去，直到找不出打√號的行、列為止。,√,(5)對

16、沒打√號的行劃一橫線，對打√號的列劃一縱線，這就是覆蓋矩陣C1中所有0元素的最小直線數(shù).,,,,,,√,√,,,,Step 4、改進C1,(1)尋找 C1 沒有被直線覆蓋的所有元素中的最小元素θ；例中θ= 2。(2)在已打√號的行中減去θ；(3)在已打√號的列中加上θ；得到一個新矩陣 C2。,√,,,,,,√,√,,,,用 C2 代替 C1，返回步驟 2。,即最優(yōu)分配方案：,確定C2中線性獨立的0元素.,,,,,,,第7章 動

17、態(tài)規(guī)劃,1、熟悉關于動態(tài)規(guī)劃的一些基本概念；2、狀態(tài)轉移方程的建立方法；3、動態(tài)規(guī)劃的解題步驟；4、動態(tài)規(guī)劃的求解方法（確定型、逆序法，P169例7-3之類）；,第8章 圖與網(wǎng)絡,圖的基本概念樹和圖的最小支撐樹最短路問題網(wǎng)絡最大流問題最小費用最大流問題,概念定義（前向弧和后向弧）:在任意一頂點之處，凡離開vi的有向弧稱為vi的前向弧，凡進入vi的有向弧稱為vi的后向弧。,,vi,vj,a,稱有向弧a為vi點的前向弧， v

18、j點的后向弧。,,,,,,,,,,,,,v0,vn,v2,v1,定義（道路或通路）在任意一網(wǎng)絡中，凡從始點v0（發(fā)點）開始到終點vn（收點）結束的一系列前向弧集合稱為道路。,如果N表示某網(wǎng)絡中所有點的集合，將N分成兩個子集A與A，使得發(fā)點v0在A內，收點vn在A 內，則稱（A，A）為分離發(fā)點與收點的截集。,截集定義,從 A 中各頂點到 A中各頂點全部容量之和稱為截集的容量（截量）。,截集的容量,,,,,,,,,,,v0,vn,v2,v1

19、,,a,,截集a：v0v1，v0v2，v0vn,截量: Ca=C01+C02+C0n,,,,,,,,,,,v0,vn,v2,v1,,,截集v1vn，v2vn，v0vn,截量: Cb=C1n+C2n+C0n,,,,,,,,,,,v0,vn,v2,v1,,d,S,S,在截集d中邊v1v2是反向的，其容量視為零。,,,,,,截集：v0v1，v1v2，v2v1，v2vn，v0vn,截量： Cd=C01+C21+ C2n+ C0

20、n,在將網(wǎng)絡分成發(fā)集與收集的所有分法中，容量最小的截集稱為最小截集。,如果鏈μ滿足以下條件：（1）在?。╲i,vj）∈μ+上，有0≤fij<cij， 即μ+中的每一條弧是非飽和弧。（2）在弧（vi,vj）∈μ-上，有0<fij ≤ cij， 即μ-中的每一條弧是非零流弧。則稱這樣的鏈為增廣鏈 。,增廣鏈,,,,練習題,1、最早運用運籌學理論的是（ ）A 二次世界大戰(zhàn)期間，英國軍事部

21、門將運籌學運用到軍事戰(zhàn)略部署；B 美國最早將運籌學運用到農業(yè)和人口規(guī)劃問題上；C 二次世界大戰(zhàn)期間，英國政府將運籌學運用到政府制定計劃；D 50年代，運籌學運用到研究人口，能源，糧食，第三世界經濟發(fā)展等問題上。,單項選擇題,2、在產銷平衡運輸問題中，設產地為個，銷地為個，那么基可行解中非零變量的個數(shù)（ ）A. 不能大于(m+n-1)； B. 不能小于(m+n-1)； C. 等于(m+n-1)； D. 不

22、確定。,3、在求解運輸問題的過程中運用到下列哪些方法（ ）A 最小元素法B 位勢法C 閉回路法D 伏格爾法E 以上都是,53,圖解法同單純形法雖然求解的形式不同，但從幾何上理解，兩者是一致的。LP模型中增加一個約束條件，可行域的范圍一般將縮小，減少一個約束條件，可行域的范圍一般將擴大。 LP問題的每一個基解對應可行域的一個頂點。如LP問題存在最優(yōu)解，則最優(yōu)解一定對應可行域邊界上的一個點。,√,×

23、;,√,√,判斷下列說法是否正確,54,6. 任何LP問題存在并具有唯一的對偶問題。 7. 對偶問題的對偶問題一定是原問題。8. 根據(jù)對偶問題的性質，當原問題為無界解時，其對偶問題無可行解，反之，當對偶問題無可行解時，其原問題具有無界解。,×,√,√,5. 線性規(guī)劃問題的可行解如為最優(yōu)解，則該可行解一定是基可行解；,因為基可行解≠可行解。,×,9.運輸問題數(shù)學模型的（m+n）個約束中 最多只有（m+n-1）個

24、是獨立的。,√,10.產銷平衡的運輸問題解的情況有四種：無可行解；無界解；唯一最優(yōu)解；無窮多最優(yōu)解。,錯 P102,11.運輸問題的所有結構約束條件都是等式約束。,對,填空題,1、用大M法求解Max型線性規(guī)劃時，人工變量在目標中的系數(shù)均為 ,若最優(yōu)解的 中含有人工變量，則原問題無可行解。,（-M）基變量,2、若某種資源的影子價格為零，則表明該種資源 （應該或不應該）被買進；又當資源的影子價格不為

25、零時，說明該種資源消耗 （完畢或剩余）,不應該 完畢,3、線性規(guī)劃原問題中的變量個數(shù)與其對偶問題中的 個數(shù)相等。因此，當原問題增加一個變量時，對偶問題就增加一個 ，從而對偶可行域將可能變 (小還是大)。,小,約束條件,約束條件,4、用表上作業(yè)法求解m個產地n個銷地的平衡運輸問題，其方案表上數(shù)字格的個數(shù)為

26、 個；,m+n-1,建立線性規(guī)劃模型（利潤最大或者成本最?。┚€性規(guī)劃化為標準型寫出問題的對偶規(guī)劃,建立模型,某人每天食用甲、乙兩種食物（如豬肉、雞蛋），如表。問兩種食物各食用多少，才能既滿足需要、又使總費用最省？,設：X1 、X2 表示甲、乙種食物的用量。,甲 乙,,初始表,最終表,原問題的變量,原問題的松弛變量,對偶問題的剩余變量,對偶問題的變量,由表可知，原問題最優(yōu)解： X*=（50/7，2

27、00/7，0，0，0），Z=4100/7對偶問題的最優(yōu)解： Y*=（0，32/7，6/7，0，0），W=4100/7,B-1,8,3,2,2,v1,v6,用避圈法或破圈法求下圖所示最小支撐樹。,,4,v4,5,4,3,3,v7,v8,v3,v5,,,,,,,,,,,,,,v2,2,4,2,2,2,2,2,8,3,,,,,,,,解法一：用避圈法W(T*)=2+2+2+2+2+2+3=15,解法二：用破圈法,v1,v6,4,v4,5,

28、4,3,3,v7,v8,v3,v5,,,,,,,,,,,,,,2,4,2,2,2,7個村莊要在他們之間架設電話線，要求任何兩個村莊都可以互相通電話(允許中轉)，并且電話線根數(shù)最少？,村莊2,,,,,,,,,,,,,村莊1,村莊4,村莊3,村莊6,村莊5,村莊7,類似的問題都是求最小支撐樹,用動態(tài)規(guī)劃逆序法解非線性規(guī)劃：,解：設決策變量為x1, x2, x3，階段K=3，狀態(tài)變量Sk，K=1，2，3采用逆向遞推，狀態(tài)轉移方程 sK

29、+1=sk?xk s4=s3?x3=0 ， s3=s2?x2 ， s2=s1?x1 邊界條件 s1=27， s4=0,第三階段：k=3，（求解x3）,由邊界條件和狀態(tài)轉移方程有：s4=s3?x3=0 即 x3*=s3；因此有：,第二階段：k=2，（求解x2）,由狀態(tài)轉移方程有：s3=s2?x2，代入上式得：,第一階段：k=1,（求解x1）,由狀態(tài)轉移方程有：s2=s1?x1=27?x1，代入上式得：,,,本學期運籌學