韓伯棠教授管理運(yùn)籌學(xué)第三習(xí)總復(fù)習(xí)

1、一、管理運(yùn)籌學(xué)的定義運(yùn)籌學(xué)（Operational Research，簡(jiǎn)稱(chēng)OR) ，英文直譯為“運(yùn)作研究”。 管理運(yùn)籌學(xué)是應(yīng)用分析、試驗(yàn)、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中的人力、物力、財(cái)力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。 中國(guó)企業(yè)管理百科全書(shū)緒論二、管理運(yùn)籌學(xué)的主要分支線(xiàn)性規(guī)劃(Linear Programming，簡(jiǎn)稱(chēng)LP)整數(shù)規(guī)劃(Integral Programming，簡(jiǎn)稱(chēng)IP)目標(biāo)規(guī)劃(Objective Programming，簡(jiǎn)稱(chēng)OP)動(dòng)態(tài)規(guī)劃(Dynamic Programming，簡(jiǎn)稱(chēng)DP)圖與網(wǎng)絡(luò)(Graph and Network)三、管

2、理運(yùn)籌學(xué)的工作步驟 提出問(wèn)題、分析問(wèn)題 建立模型 求解 解的檢驗(yàn)、控制、實(shí)施四、運(yùn)籌學(xué)方法的特點(diǎn)1. 最優(yōu)化方法 2. 定量的方法 線(xiàn)性規(guī)劃(LP)一、問(wèn)題的提出1.生產(chǎn)計(jì)劃安排問(wèn)題： 合理利用人力、物力、財(cái)力等，在資源有限的約束條件下,尋求使得獲利最大的最優(yōu)生產(chǎn)計(jì)劃方案。2.人力資源分配的問(wèn)題： 在滿(mǎn)足工作的需要的條件下，尋求使用最少的勞動(dòng)力的最優(yōu)分配方案。3.套裁下料問(wèn)題： 在保證正常生產(chǎn)，完成生產(chǎn)任務(wù)的條件下，尋求使用原料最省的最優(yōu)下料方案。4.投資問(wèn)題：在投資額限制的條件下，從多個(gè)投資項(xiàng)目中選取使得投資回報(bào)最大的最優(yōu)投資方案。5.運(yùn)輸問(wèn)題：尋求使得總運(yùn)費(fèi)最小的最優(yōu)調(diào)運(yùn)方案。二、建模1.

3、一般步驟:分析問(wèn)題，設(shè)出決策變量 根據(jù)所提問(wèn)題列出目標(biāo)函數(shù)根據(jù)已知條件列出所有約束條件2.LP數(shù)學(xué)模型的一般形式矩陣形式：假設(shè)有n個(gè)決策變量，m個(gè)約束條件。目標(biāo)函數(shù)：Max （Min） z = CX約束條件： AX （ =, ）b s.t. X 0其中，C=(c1 , c2 , , cn )(價(jià)值向量) X= (x1 , x2 , , xn )T(決策變量向量) b=(b1 , b2 , , bm )T (限定向量) a11 a12 a1n a21 a22 a2n (約束條件系數(shù)矩陣) Am×n = am1 am2 amn 3.LP數(shù)學(xué)模型的特點(diǎn)（1）由目標(biāo)函數(shù)和約束條件構(gòu)成；（2）

4、目標(biāo)函數(shù)只有兩種情況：求極小或求極大。（3）雙線(xiàn)性 目標(biāo)函數(shù)是關(guān)于決策變量的線(xiàn)性函數(shù); 所有約束條件是關(guān)于決策變量的線(xiàn)性函數(shù)。三、求解1.方法一：圖解法（1）適用條件 有且僅有兩個(gè)決策變量X1，X2。（2）基本概念 可行解；可行域；最優(yōu)解（3）基本思路：先求出可行解（即找出可行域），再在可行解的基礎(chǔ)上（即在可行域內(nèi)）求出最優(yōu)解。（4） 基本步驟 作圖找出可行域 作出目標(biāo)函數(shù)等值線(xiàn)，判斷其平移的方向平移目標(biāo)函數(shù)等值線(xiàn)，在可行域內(nèi)找出最優(yōu)點(diǎn)，計(jì)算最優(yōu)解。（5）圖解法解的情況唯一最優(yōu)解 無(wú)窮多最優(yōu)解 無(wú)可行解 無(wú)界解注意：能夠區(qū)分無(wú)可行解和無(wú)界解的情況。（6）圖解法的靈敏度分析靈敏度分析的含義；目標(biāo)

5、函數(shù)中的系數(shù) ci 的靈敏度分析；約束條件右端常數(shù)項(xiàng) bj 的靈敏度分析； 對(duì)偶價(jià)格：約束條件右端常數(shù)b增加一個(gè)單位而使目標(biāo)函數(shù)最優(yōu)值得到改進(jìn)的數(shù)量，稱(chēng)之為該約束條件的對(duì)偶價(jià)格。 對(duì)偶價(jià)格=z/b2.方法二：?jiǎn)渭冃头?1)基本概念 基；基向量,非基向量；基變量,非基變量；基本解,基本可行解,基本最優(yōu)解；可行基，最優(yōu)基(2)重要定理及性質(zhì)若LP的可行域存在，則可行域?yàn)橥苟噙呅巍Ｈ鬖P存在最優(yōu)解，則最優(yōu)解一定可在可行域凸多邊形的頂點(diǎn)上取得。LP問(wèn)題的一個(gè)基本可行解對(duì)應(yīng)于可行域的一個(gè)頂點(diǎn)。 可行域的一個(gè)頂點(diǎn) 一個(gè)基本可行解 以單位矩陣Im×m做基，其基本解的特點(diǎn)是：所有非基變量xj =0，

6、所有基變量xi =bi（標(biāo)準(zhǔn)型中規(guī)定b 0 ），故單位矩陣可做可行基。規(guī)定:LP數(shù)學(xué)模型的標(biāo)準(zhǔn)型 : 目標(biāo)函數(shù)：MaxZ = CX約束條件： AX =b s.t. X 0要求:能夠?qū)⑷我饽Ｐ蜆?biāo)準(zhǔn)化。3.方法三：對(duì)偶單純型法（1）原問(wèn)題與對(duì)偶問(wèn)題的數(shù)學(xué)模型 對(duì)稱(chēng)形式的對(duì)偶(對(duì)偶定義) 設(shè)有原問(wèn)題：LP:則對(duì)偶問(wèn)題為：DP: 要求：掌握二者模型之間的對(duì)應(yīng)關(guān)系。非對(duì)稱(chēng)形式的對(duì)偶 方法：先將原問(wèn)題化為對(duì)稱(chēng)形式(注:無(wú)需處理等式約束及自由變量)，再由對(duì)偶定義直接寫(xiě)出對(duì)偶問(wèn)題即可。 等式約束 自由變量要求：能夠根據(jù)任意模型（原問(wèn)題）寫(xiě)出其對(duì)偶問(wèn)題模型。（2）對(duì)偶規(guī)劃的基本性質(zhì) 對(duì)稱(chēng)性 弱對(duì)偶性 最優(yōu)性 強(qiáng)

7、對(duì)偶性（3）對(duì)偶單純型法適用條件（極大化問(wèn)題）：a.初始單純形表中，檢驗(yàn)數(shù)行所有 j 0 ；b.初始單純形表中，常數(shù)列中至少存在一個(gè)負(fù)值(bk<0)基本步驟： 從與單純型法的比較中掌握此方法。4. 求解運(yùn)輸問(wèn)題的表上作業(yè)法（1）適用條件：產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題。（2）基本步驟注意：假設(shè)有m個(gè)產(chǎn)地，n個(gè)銷(xiāo)地，則運(yùn)輸問(wèn)題有m+n-1個(gè)基變量。 （3）解的情況唯一最優(yōu)解；有限多最優(yōu)解整數(shù)規(guī)劃（IP）一、問(wèn)題的提出1.投資場(chǎng)所的選擇2.指派問(wèn)題3.分布系統(tǒng)設(shè)計(jì)4.投資問(wèn)題二、建模1.純整數(shù)規(guī)劃問(wèn)題Max(min)Z=CX AX(,=)b X 0 X1, X2 ,Xn 均為整數(shù)2.混合整數(shù)規(guī)劃問(wèn)題Ma

8、x(min)Z=CXAX(,=)bX 0X1, X2 ,Xk 均為整數(shù)(k<n)求解方法：分枝定界法，割平面法3.0-1整數(shù)規(guī)劃問(wèn)題 Max(min)Z=CXAX(,=)bX =0或1求解方法：隱枚舉法，匈牙利法三、模型求解 1.分枝定界法 2.求解指派問(wèn)題的匈牙利法。目標(biāo)規(guī)劃（OP）一、問(wèn)題的提出 多目標(biāo)決策問(wèn)題 二、建模1. 基本概念 決策變量 偏差變量 ； 絕對(duì)約束，目標(biāo)約束； 優(yōu)先因子，權(quán)系數(shù)2.基本步驟設(shè)出決策變量根據(jù)各個(gè)目標(biāo)列出絕對(duì)約束 將絕對(duì)約束轉(zhuǎn)化為目標(biāo)約束和目標(biāo)函數(shù),并根據(jù)實(shí)際問(wèn)題對(duì)各個(gè)目標(biāo)賦予優(yōu)先因子或權(quán)系數(shù)3.OP數(shù)學(xué)模型一般形式minZ=f(P,w,d+,d-)F

9、i(x)+ - =biX, d+,d-0注：OP數(shù)學(xué)模型中可能存在絕對(duì)約束。三、模型求解1.圖解法（1）適用條件 有且僅有兩個(gè)決策變量。（2）基本步驟注意：準(zhǔn)確判斷各偏差變量增加的方向。從優(yōu)先權(quán)最高的目標(biāo)開(kāi)始求解，清楚寫(xiě)出每一優(yōu)先級(jí)目標(biāo)的滿(mǎn)意解。動(dòng)態(tài)規(guī)劃(DP)一、問(wèn)題的提出多階段決策問(wèn)題： 1.最短路問(wèn)題 2.資源分配問(wèn)題 3.背包問(wèn)題 4.生產(chǎn)與存貯問(wèn)題 5.系統(tǒng)可靠性問(wèn)題二、建模注意：動(dòng)態(tài)規(guī)劃沒(méi)有統(tǒng)一確定的數(shù)學(xué)模型。1.基本概念 階段；狀態(tài)；決策；策略；指標(biāo)函數(shù)（包括階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)）；狀態(tài)轉(zhuǎn)移方程；基本方程（遞推公式）三、模型求解逆序算法（根據(jù)最優(yōu)化原理）1.求解最短路問(wèn)題的逆推法；2.求解最短路問(wèn)題的順推法。圖與網(wǎng)絡(luò)一、基本概念1.圖;無(wú)向圖;有向圖; 簡(jiǎn)單圖;多重圖; 連通圖;頂點(diǎn)的次2. 網(wǎng)絡(luò)3. 樹(shù);生成子圖;生成樹(shù); 最小生成樹(shù)二、問(wèn)題的提出 1.最短路問(wèn)題 2.最小生成樹(shù)問(wèn)題 3.最大流問(wèn)題 4.最小費(fèi)用最大流問(wèn)題三、求解方法 1.求解最短路問(wèn)題的雙標(biāo)號(hào)法； 2.求解最小生成樹(shù)問(wèn)題的破圈法和避圈法； 3. 求解最大流問(wèn)題的線(xiàn)性規(guī)劃法和圖論解法； 4.求解最小費(fèi)用最大流問(wèn)題的線(xiàn)性規(guī)劃法和圖論解法?？荚囆问剑洪]卷考試考試時(shí)間：120分鐘考試題型 ：填空題，判斷題，計(jì)算題，應(yīng)用題 計(jì)算題、應(yīng)用題：LP: 圖解法、單純形法； 根據(jù)原問(wèn)題寫(xiě)出對(duì)偶問(wèn)題； 運(yùn)輸