2016運(yùn)籌學(xué)總復(fù)習(xí)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、j點(diǎn)的后向弧。,,,,,,,,,,,,,v0,vn,v2,v1,定義（道路或通路）在任意一網(wǎng)絡(luò)中，凡從始點(diǎn)v0（發(fā)點(diǎn)）開始到終點(diǎn)vn（收點(diǎn)）結(jié)束的一系列前向弧集合稱為道路。,如果N表示某網(wǎng)絡(luò)中所有點(diǎn)的集合，將N分成兩個(gè)子集A與A，使得發(fā)點(diǎn)v0在A內(nèi)，收點(diǎn)vn在A 內(nèi)，則稱（A，A）為分離發(fā)點(diǎn)與收點(diǎn)的截集。,截集定義,從 A 中各頂點(diǎn)到 A中各頂點(diǎn)全部容量之和稱為截集的容量（截量）。,截集的容量,,,,,,,,,,,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)絡(luò)分成發(fā)集與收集的所有分法中，容量最小的截集稱為最小截集。,如果鏈μ滿足以下條件：（1）在?。╲i,vj）∈μ+上，有0≤fij<cij， 即μ+中的每一條弧是非飽和弧。（2）在?。╲i,vj）∈μ-上，有0<fij ≤ cij， 即μ-中的每一條弧是非零流弧。則稱這樣的鏈為增廣鏈 。,增廣鏈,,,,練習(xí)題,1、最早運(yùn)用運(yùn)籌學(xué)理論的是（ ）A 二次世界大戰(zhàn)期間，英國軍事部

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

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

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

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

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

26、 個(gè)；,m+n-1,建立線性規(guī)劃模型（利潤最大或者成本最?。┚€性規(guī)劃化為標(biāo)準(zhǔn)型寫出問題的對偶規(guī)劃,建立模型,某人每天食用甲、乙兩種食物（如豬肉、雞蛋），如表。問兩種食物各食用多少，才能既滿足需要、又使總費(fèi)用最??？,設(shè)：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個(gè)村莊要在他們之間架設(shè)電話線，要求任何兩個(gè)村莊都可以互相通電話(允許中轉(zhuǎn))，并且電話線根數(shù)最少？,村莊2,,,,,,,,,,,,,村莊1,村莊4,村莊3,村莊6,村莊5,村莊7,類似的問題都是求最小支撐樹,用動(dòng)態(tài)規(guī)劃逆序法解非線性規(guī)劃：,解：設(shè)決策變量為x1, x2, x3，階段K=3，狀態(tài)變量Sk，K=1，2，3采用逆向遞推，狀態(tài)轉(zhuǎn)移方程 sK

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