管理運籌學(xué)自學(xué)指導(dǎo)大綱.doc

管理運籌學(xué)自學(xué)指導(dǎo)大綱1. 課程性質(zhì)本課程為交通運輸學(xué)院本、?？粕幕A(chǔ)課。學(xué)生通過學(xué)習(xí)該課程，應(yīng)了解管理運籌學(xué)對優(yōu)化決策問題進(jìn)行定量研究的特點，理解線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃、圖與網(wǎng)絡(luò)、排隊論等分支的基本優(yōu)化原理，掌握其中常用的模型和算法，具有一定的建模能力。先修課程主要為線性代數(shù)和概率統(tǒng)計，學(xué)生對它們的掌握程度直接影響本課程的學(xué)習(xí)，所以要求學(xué)生課前要做必要的復(fù)習(xí)。2主要內(nèi)容2.1 線性規(guī)劃2.1.1線性規(guī)劃的基本概念（1）線性規(guī)劃的含義、標(biāo)準(zhǔn)型、松弛變量、多余變量、自由變量（2）可行解、基、基解、基可行解、可行基、最優(yōu)解（3）凸集、凸組合2.1.2線性規(guī)劃的圖解法（1）可行域的確定（2）目標(biāo)函數(shù)值的變化（3）解的幾種情況2.1.3線性規(guī)劃的單純形法（1）單純形法的步驟（2）解的判斷方法（解唯一性、多重解、無界解及無解的判斷定理）（3）大M法和兩階段法（增加人工變量的目的？）2.1.4單純形法的矩陣表示（1）、各符號的含義、解的最優(yōu)性判斷方法（2） 給定部分單純形表可以計算其他參數(shù) 利用（1）中的表達(dá)式可以計算參數(shù)值2.1.5對偶問題及對偶理論（1）對偶問題的含義（2）原問題和對偶問題的轉(zhuǎn)化方法（3）對偶問題的基本性質(zhì)對稱性、弱對偶形（）、無界性（無界則對偶無可行）、可行解是最優(yōu)解的性質(zhì)（，均為最優(yōu)解）、對偶定理（有最優(yōu)解，則）、互補松弛性（和）、檢驗數(shù)和解的關(guān)系2.1.6影子價格 （1）影子價格的含義（2）利用 對影子價格計算 （3）對影子價格的影響因素，分析參數(shù)變化時影子價格對應(yīng)的變化2.1.7對偶單純形法（1）對偶單純形法的思想（2）對偶單純形法的步驟解不可行（單純形表最優(yōu)，對偶問題解可行）、換出變量的確定、換入變量的確定（3）對偶單純形法的一個應(yīng)用增加一個約束條件2.1.8靈敏度分析(1)靈敏度分析的含義和分析的目的(2)資源數(shù)量的靈敏度分析 即 (3)目標(biāo)函數(shù)系數(shù)的靈敏度分析a. 非基變量系數(shù) ；b. 基變量系數(shù) (4)技術(shù)系數(shù)的變化a新增加一種產(chǎn)品原始消耗系數(shù)、單純形表中的消耗系數(shù)（）、檢驗數(shù)（判斷是否有利）b.產(chǎn)品結(jié)構(gòu)進(jìn)行調(diào)整 原始消耗系數(shù)、用代替原消耗系數(shù)、判斷解的性質(zhì)（原問題和對偶問題均為非可行解時增加人工變量）2.1.9 作業(yè)1.1(1)(2);1.2(1);1.3(1);1.4(1);1.6(2);1.72.3(1)(2);2.4;2.6;2.7;2.82.2運輸問題2.2.1運輸問題的概念模型、基變量的個數(shù)、m+n個變量是基變量的條件、運輸問題和線性規(guī)劃問題的關(guān)系2.2.2運輸問題的求解（1）初始解的求法：西北角法、最小元素法、伏格爾法(2) 解的檢驗：閉回路法、位勢法（引進(jìn)m+n個參數(shù)，對于基變量，其它變量） （3）解的改進(jìn)閉回路調(diào)整法調(diào)整量的確定：閉回路上偶數(shù)點變量取值的最小值，取最小值的變量為換出變量（多個取任意一個）調(diào)整方法：奇數(shù)點上加調(diào)整量，偶數(shù)點上減調(diào)整量（4）解的退化和無窮多最優(yōu)解基變量取值為0；非基變量的檢驗數(shù)為02.2.3產(chǎn)銷不平衡的運輸問題產(chǎn)大于銷：增加虛銷點，相應(yīng)的運費為0；銷大于產(chǎn)：增加需產(chǎn)點，相應(yīng)的運費為0。其它情況：不能調(diào)運時費用為無窮大2.2.4 作業(yè)3.1;3.2;3.3(1);3.62.3整數(shù)規(guī)劃2.3.1整數(shù)規(guī)劃的概念整數(shù)規(guī)劃、全整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、0-1規(guī)劃、整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系2.3.2整數(shù)規(guī)劃的求解方法（1）圖解法（2）分枝定界法分枝定界法的思想、分枝（對任何一個不滿足整數(shù)條件的變量分枝）、定界；若目標(biāo)求最大值，先對目標(biāo)函數(shù)大的枝求解）；（3）割平面法割平面法的思想、建立割平面方程 2.3.3 0-1規(guī)劃（1）一般0-1規(guī)劃問題：隱梅舉法（2）指派問題：匈牙利算法（3）非標(biāo)準(zhǔn)指派問題：最大值問題、任務(wù)數(shù)和人數(shù)不匹配問題等2.3.4規(guī)劃問題的建模規(guī)劃模型：決策變量、目標(biāo)函數(shù)、約束方程根據(jù)自己的想法，對變量的含義、約束方程的含義最好解釋2.3.5 作業(yè)5.2;5.3;5.72.4動態(tài)規(guī)劃2.4.1基本要求動態(tài)規(guī)劃基本概念、最優(yōu)化原理和基本方程，通過資源分配和生產(chǎn)與存儲等問題,學(xué)習(xí)應(yīng)用動態(tài)規(guī)劃解決多階段決策問題。2.4.1.1 理解和記憶的內(nèi)容階段狀態(tài)（狀態(tài)變量）決策變量（允許決策集合）狀態(tài)轉(zhuǎn)移方程指標(biāo)函數(shù)（階段指標(biāo)函數(shù)、后部子過程）動態(tài)規(guī)劃的基本思想2.4.1.2掌握和靈活應(yīng)用的內(nèi)容動態(tài)規(guī)劃問題的逆序解法實際問題轉(zhuǎn)化為動態(tài)規(guī)劃問題2.4.2重點、難點重點：掌握動態(tài)規(guī)劃模型結(jié)構(gòu)、逆序法算法原理、資源分配、設(shè)備更新、生產(chǎn)于存貯等問題。難點：動態(tài)規(guī)劃中狀態(tài)變量等的確定2.4.3 內(nèi)容輔導(dǎo)2.4.3.1 動態(tài)規(guī)劃的基本理論(1)階段、階段變量把所給問題，適當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系的階段；階段的劃分，一般是按時間和空間的自然特征來劃分；但要便于把問題的過程能轉(zhuǎn)化為多階段決策的過程。(2)狀態(tài)、狀態(tài)變量每個階段開始所處的自然狀態(tài)或客觀條件。通常一個階段有若干個狀態(tài)。描述過程狀態(tài)的變量稱為狀態(tài)變量，常用sk表示第k階段的狀態(tài)。狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為狀態(tài)允許集合。(3)決策、決策變量過程的某一階段、某個狀態(tài)，可以做出不同的決定(選擇)，決定下一階段的狀態(tài)，這種決定稱為決策。描述決策的變量，稱為決策變量。決策變量是狀態(tài)變量的函數(shù)，常用uk(sk)表示第k階段當(dāng)狀態(tài)為sk時的決策變量。在實際問題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為允許決策集合。常用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合，顯然有 uk(sk)Dk(sk)(4)狀態(tài)轉(zhuǎn)移方程多階段決策過程可以在各個階段進(jìn)行決策，去控制過程發(fā)展的多段過程；其發(fā)展是通過一系列的狀態(tài)轉(zhuǎn)移來實現(xiàn)的；系統(tǒng)在某一階段的狀態(tài)轉(zhuǎn)移不但與系統(tǒng)的當(dāng)前的狀態(tài)和決策有關(guān)，而且還與系統(tǒng)過去的歷史狀態(tài)和決策有關(guān)。其狀態(tài)轉(zhuǎn)移方程如下（一般形式）能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即具有無后效性的多階段決策過程。(5) 策略策略是一個按順序排列的決策組成的集合。由過程的第k階段開始到終止?fàn)顟B(tài)為止的過程，稱為問題的后部子過程（或稱為k子過程）。由每段的決策按順序排列組成的決策函數(shù)序列稱為k子過程策略，簡稱子策略，記為，即當(dāng)k=1時，此決策函數(shù)序列成為全過程的一個策略，簡稱策略，記為即在實際問題中，可供選擇的策略有一定范圍，此范圍稱為允許策略集合，用p表示。從允許策略集合中找出達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略。（6）函數(shù)和最優(yōu)值函數(shù)用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標(biāo)，稱為指標(biāo)函數(shù)，它是定義在全過程或所有后部子過程上確定的數(shù)量函數(shù)。Vk, n表示之。即動態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分離性，并滿足遞推關(guān)系。即Vk,n可以表示為sk,uk,Vk+1,n的函數(shù)。常見的指標(biāo)函數(shù)的形式是：過程和它的任一子過程的指標(biāo)是它所包含的各階段的指標(biāo)和。即其中vj(sj,uj)表示第j階段的階段指標(biāo)。這時上式可寫成過程和它的任意子過程的指標(biāo)是它所包含的各階段的指標(biāo)的乘積。即則可改寫成最優(yōu)值函數(shù)：表示從第k階段的狀態(tài)sk開始到第n階段的終止?fàn)顟B(tài)的過程，采取最優(yōu)策略所得到的指標(biāo)函數(shù)值。即(7)多階段決策過程的數(shù)學(xué)模型具有無后效性的多階段決策過程所謂求解多階段決策過程問題，就是要求出 最優(yōu)策略，即最優(yōu)決策序列最優(yōu)軌線，即執(zhí)行最優(yōu)策略時的狀態(tài)序列最優(yōu)目標(biāo)函數(shù)值 2.4.3.2 動態(tài)規(guī)劃的應(yīng)用資源分配問題（1）理論部分uk:分配給生產(chǎn)第k種產(chǎn)品的原料數(shù)量，即uk=xk；sk:分配給用于生產(chǎn)第k種至第n種產(chǎn)品的原料數(shù)量；狀態(tài)轉(zhuǎn)移方程： sk+1=sk-uk=sk-xk決策集合：Dk(sk)=uk|0uk=xksk最優(yōu)值函數(shù)fk(sk):數(shù)量為sk的原料分配給第k種產(chǎn)品至第n種產(chǎn)品所得到的最大總收益，動態(tài)規(guī)劃的遞推關(guān)系為：（2）計算部分將具體數(shù)據(jù)代入上述理論部分，可以得到優(yōu)化方案生產(chǎn)與存貯問題（1） 理論部分（2） 計算部分3.1.4 作業(yè)8.1、9.1、9.2、9.92.5圖與網(wǎng)絡(luò)分析2.5.1基本要求了解圖的基本概念，掌握最小支撐樹、最短路徑、最大流以及最小費用最大流的算法。2.5.1.1 理解和記憶的內(nèi)容圖、點集、邊集、有向圖、無向圖；相鄰、相關(guān)、簡單圖、多重圖、偶點、奇點、鏈、路、簡單鏈、初等鏈、回路；樹、支撐樹、割集、網(wǎng)絡(luò)；鄰接矩陣、關(guān)聯(lián)矩陣；圖的同構(gòu)；2.5.2.2掌握和靈活應(yīng)用的內(nèi)容掌握最小支撐樹最短路徑的算法最大流的算法最小費用最大流的算法2.5.2重點、難點重點：網(wǎng)絡(luò)優(yōu)化問題，即最短路徑的算法、最大流的算法、最小費用最大流的算法。難點：各種算法的思想及算法的實現(xiàn)2.5.3內(nèi)容輔導(dǎo)2.5.3.1圖的基本概念 圖、邊、有向圖、無向圖、端點、相鄰、多重邊、簡單圖、多重圖、點的次、懸掛點、懸掛邊、孤立點、奇點、偶點、鏈、初等鏈、路 概念參見教材及任何圖論書籍2.5.3.2樹及支撐樹（1）定義：無圈的連通圖稱為樹。樹一般用T表示。（2）圖的支撐樹:設(shè)圖T=V，E是圖G=（V，E）的支撐子圖，如果T是一個樹，則稱T是G的一個支撐樹。圖的支撐樹的生成方法：破圈法和避圈法（3）最小支撐樹設(shè)有連通圖G=（V，E），G的任一邊ek=vi，vj，有一個非負(fù)權(quán)w（ek）=wij（wij0）,T=（V，E）是G的一個支撐樹，稱為樹T的權(quán)。如果支撐樹T*的權(quán)w（T*）是G的所有支撐樹的權(quán)中最小的，則稱T*是G的最小支撐樹（簡稱最小樹）。即最小支撐樹問題，即求網(wǎng)絡(luò)G的最小支撐樹。（4）最小支撐樹的生成方法避圈法：在圖中取一條最小權(quán)的邊，以后每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈（每一步中，如果有兩條或兩條以上的邊都是最小權(quán)的邊，則從中任選一條）。破圈法：任取一個圈，從圈中去掉一條權(quán)最大的邊（如果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條）。在余下的圖中，重復(fù)這個步驟，直到得到一個不含圈的圖為止，這時的圖便是最小樹。2.5.3.3 最短路經(jīng)（1）定義給定有向網(wǎng)絡(luò)D=（V，A，W），任意弧aijA，有權(quán)w（aij）=wij，給定D中的兩個頂點vs，vt。設(shè)P是D中從vs到vt的一條路，定義路P的權(quán)（長度）是P中所有弧的權(quán)之和，記為w（P）。最短路問題就是要在所有從vs到vt的路中，求一條路P0 ，使稱P0是從vs到vt的最短路。路P0的權(quán)稱為從vs到vt的路長。（2）最短路算法Dijkstra算法，算法思想：將D=（V，A，W）中vs到所有其它頂點的最短路按其路長從小到大排列為：u0 u1 u2 unu0表示vs到自身的長度，相應(yīng)最短路記為：P0，P1，P2，Pn，P1一定只有一條弧。取最小值的點為v1， P1=P（vs，v1）。假定 u0，u1，uk的值已求出，對應(yīng)的最短路分別為P1=P（vs，v1）， P2=P（vs，v2）， Pk=P（vs，vk），記則使上式達(dá)到最小值的點v 可取為vk+1。計算過程中可采用標(biāo)號方法。Xk中的點，ui 值是vs 到vi 的最短路長度，相應(yīng)的點記“永久”標(biāo)號；XK中的點，ui值是vs到vi的最短路長度的上界，相應(yīng)的點記“臨時”標(biāo)號，供進(jìn)一步計算使用。前點標(biāo)號li : 表示點vs到vj的最短路上vj的前一點。如li=m，表示vs到vj的最短路上vj前一點是vm。2.5.3.4 最大流(1) 基本概念及定理(2)給定一個有向圖D=（V，A），在V中指定一點vs稱為發(fā)點，指定另一點vt稱為收點，其余點稱中間點。任意弧(vi，vj )A，有cij0，稱為弧的容量。稱D為一個容量網(wǎng)絡(luò)。記為D=（V，A，C）。流:定義在弧集A上的一個函數(shù)f=f(vi,vj )，并稱f(vi,vj)為弧(vi ,vj )上的流量。簡記 f = fi ,j 。滿足下述條件的流f稱為可行流:容量限制條件: 對每一弧(vi , vj )A0fij cij平衡條件: 對中間點vi (is,t ),有 V( f ) 稱為可行流 f 的流量,即發(fā)點的凈輸出量。對可行流 f = fij ：如果fij 0為非零流弧；鏈的方向：若是聯(lián)結(jié)vs和vt的一條鏈，定義鏈的方向是從vs到vt 。前向?。夯〉姆较蚺c鏈的方向一致，記為+。后向弧：弧的方向與鏈的方向相反，記為-。設(shè) f 是一個可行流, 是從vs 到vt 的一條鏈,若 滿足下列條件,稱之為(關(guān)于可行流 f 的)一條增廣鏈。(vi , vj ) + 0 fij cij 前向弧是非飽和弧，(vi , vj ) - 0 fij cij 后向弧是非零流弧。網(wǎng)絡(luò)D=(V,A,C）,若點集V被剖分為兩個非空集合V1和V1,使vsV1，vt V1，則把弧集(V1，V1)稱為是分離vs和vt的截集。給一截集（V1，V1），把截集（V1，V1）中所有弧的容量之和稱為這個截集的容量（簡稱為截量），記為C （V1，V1），即 定理1 可行流 f *是最大流，當(dāng)且僅當(dāng)不存在關(guān)于 f *的增廣鏈。定理2 最大流最小截定理。任一個網(wǎng)絡(luò)D中，從vs 到vt 的最大流的流量等于分離vs，vt 的最小截集的容量。(2) 尋求最大流的標(biāo)號法從任一個可行流 f 出發(fā)（若網(wǎng)絡(luò)中沒有給定 f ，則從零流開始），經(jīng)過標(biāo)號過程與調(diào)整過程。標(biāo)號過程標(biāo)號：（前點標(biāo)記，前點到該點的弧流量可調(diào)整量）開始，vs 標(biāo)上（0，），vs 是標(biāo)號未檢查的點，其余點都是未標(biāo)號點，一般地，取一個標(biāo)號未檢查的點vi ，對一切未標(biāo)號的點vj 。a. 若?。╲i，vj）上，fij0，則給vj 標(biāo)號(-i， l (vj)，l (vj)=minl (vi), fji, vj 成為標(biāo)號而未檢查的點。重復(fù)上述步驟，一旦vt被標(biāo)號，則得到一條vs到vt的增廣鏈。若所有標(biāo)號都已檢查過，而vt尚未標(biāo)號，結(jié)束，這時可行流，即最大流。調(diào)整過程從vt 開始，反向追蹤，找出增廣鏈 ，并在上進(jìn)行流量調(diào)整。a.找增廣鏈如vt 的第一個標(biāo)號為k（或-k），則?。╲k，vt）（或弧（vt，vk) )。檢查vk 的第一個標(biāo)號，若為i（或-i），則(vi,vk) (或(vk,vi) )。再檢查vi 的第一個標(biāo)號,依此下去,直到vs 。被找出的弧構(gòu)成了增廣鏈 。b.流量調(diào)整令調(diào)整量q是 l(vt)，構(gòu)造新的可行流 f ，去掉所有的標(biāo)號,對新的可行流 f = fij,重新進(jìn)入標(biāo)號過程。2.5.3.5最小費用最大流(1)問題網(wǎng)絡(luò)D=（V，A，C）,每一?。╲i，vj）A，給出（vi，vj）上單位流的費用b(vi，vj)0，（簡記bij）。最小費用最大流問題：求一個最大流 f，使流的總費用取最小值。(2)最小費用最大流算法步驟第1步：確定初始可行流f 0 =0，令k=0；第2步：記經(jīng) k 次調(diào)整得到的最小費用流為f k，構(gòu)造增量網(wǎng)絡(luò)W（f k）；第3步：在W（f k）中，尋找vs到vt的最短路。若不存在最短路（即最短路路長是），則f k 就是最小費用最大流，若存在最短路，則此最短路即為原網(wǎng)絡(luò)D中相應(yīng)的可增廣鏈，轉(zhuǎn)入第4步。 第4步：在增廣鏈上對f k 按下式進(jìn)行調(diào)整，調(diào)整量為令得新的可行流f k+1 , 返回第2步。2.5.4作業(yè)10.1、10.3、10.4、10.6、10.11、10.122.6排隊論2.6.1.基本要求掌握排隊論的基本概念、常見的到達(dá)時間間隔分布和服務(wù)時間分布特性，生滅過程及穩(wěn)態(tài)概率。單服務(wù)臺負(fù)指數(shù)分布排隊模型；多服務(wù)臺負(fù)指數(shù)排隊模型；排隊系統(tǒng)設(shè)計的最優(yōu)化2.6.1.1 理解和記憶的內(nèi)容三個基本組成部分：輸入過程、排隊規(guī)則、服務(wù)機構(gòu)；最主要的、影響最大的三個因素：顧客到達(dá)間隔分布、服務(wù)時間分布、服務(wù)臺個數(shù)；Kendall記號：X/Y/Z/A/B/C，符號的含義；單服務(wù)臺負(fù)指數(shù)排隊系統(tǒng)；各種指標(biāo)的公式狀態(tài)間轉(zhuǎn)移圖 狀態(tài)概率的方程多服務(wù)臺負(fù)指數(shù)排隊系統(tǒng)；狀態(tài)間轉(zhuǎn)移圖狀態(tài)概率的方程一般服務(wù)時間M/G/1模型；P-K公式2.6.1.2掌握和靈活應(yīng)用的內(nèi)容單服務(wù)臺負(fù)指數(shù)排隊系統(tǒng)；各種指標(biāo)的公式狀態(tài)間轉(zhuǎn)移圖 狀態(tài)概率的方程多服務(wù)臺負(fù)指數(shù)排隊系統(tǒng)；狀態(tài)間轉(zhuǎn)移圖狀態(tài)概率的方程一般服務(wù)時間M/G/1模型；P-K公式排隊系統(tǒng)的經(jīng)濟分析2.6.2重點、難點重點：掌握M/M/1模型及其應(yīng)用。難點：到達(dá)流的穩(wěn)態(tài)概率和系統(tǒng)狀態(tài)轉(zhuǎn)移圖2.6.3內(nèi)容輔導(dǎo)2.6.3.1排隊系統(tǒng)的組成與特征排隊系統(tǒng)一般有三個基本組成部分：1.輸入過程；2.排隊規(guī)則；3.服務(wù)機構(gòu)。顧客的到達(dá)，可有下列情況：1）顧客源可能是有限的，也可能是無限的。2）顧客是成批到達(dá)或是單個到達(dá)。3）顧客到達(dá)的間隔時間可能是隨機的或確定的。4）顧客到達(dá)可能是相互獨立的或關(guān)聯(lián)的。所謂獨立就是以前顧客的到達(dá)對以后顧客的到達(dá)無影響。5）輸入過程可以是平穩(wěn)的（stationary）或說是對時間齊次的（Homogeneous in time），也可以是非平穩(wěn)的。輸入過程是平穩(wěn)的是指顧客相繼到達(dá)的間隔時間分布和參數(shù)（均值、方差）與時間無關(guān)；非平穩(wěn)的則是與時間相關(guān)，非平穩(wěn)的處理比較困難。排隊規(guī)則1）顧客到達(dá)后接受服務(wù)分為即時制（損失制）和等待制。即時制不形成隊列，而對于等待制將會形成隊列，顧客可以按下規(guī)則接收服務(wù)： 先到先服務(wù) FCFS后到先服務(wù) LCFS隨機服務(wù)RAND有優(yōu)先權(quán)服務(wù)。2）從隊列的空間可分為有容量限制和無容量限制。3）從隊列數(shù)可分為單列和多列。服務(wù)機構(gòu)1）服務(wù)機構(gòu)可以是單服