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

一、 管理運(yùn)籌學(xué)的定義運(yùn)籌學(xué)（OperationalResearch,簡稱OR），英文直譯為“運(yùn)作研究”。管理運(yùn)籌學(xué)是應(yīng)用分析、試驗(yàn)、量化的方法，對經(jīng)濟(jì)管理系統(tǒng)中的人力、物力、財(cái)力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理?！吨袊髽I(yè)管理百科全書》緒論二、 管理運(yùn)籌學(xué)I的主要分支線性規(guī)劃（LinearProgramming，簡稱LP）整數(shù)規(guī)劃（IntegralProgramming,簡稱IP）目標(biāo)規(guī)劃（ObjectiveProgramming，簡稱OP）動(dòng)態(tài)規(guī)劃（DynamicProgramming，簡稱DP）圖與網(wǎng)絡(luò)（GraphandNetwork）三、 管理運(yùn)籌學(xué)的工作步驟提出問題、分析問題建立模型求解解的檢驗(yàn)、控制、實(shí)施四、 運(yùn)籌學(xué)方法的特點(diǎn)最優(yōu)化方法定量的方法線性規(guī)劃（LP）一、問題的提出生產(chǎn)計(jì)劃安排問題：合理利用人力、物力、財(cái)力等，在資源有限的約束條件下，尋求使得獲利最大的最優(yōu)生產(chǎn)計(jì)劃方案。人力資源分配的問題：在滿足工作的需要的條件下，尋求使用最少的勞動(dòng)力的最優(yōu)分配方案。套裁下料問題：在保證正常生產(chǎn)，完成生產(chǎn)任務(wù)的條件下，尋求使用原料最省的最優(yōu)下料方案。投資問題：在投資額限制的條件下，從多個(gè)投資項(xiàng)目中選取使得投資回報(bào)最大的最優(yōu)投資方案。運(yùn)輸問題：尋求使得總運(yùn)費(fèi)最小的最優(yōu)調(diào)運(yùn)方案。二、建模1?一般步驟:分析問題，設(shè)出決策變量根據(jù)所提問題列出目標(biāo)函數(shù)根據(jù)已知條件列出所有約束條件數(shù)學(xué)模型的一般形式★矩陣形式：假設(shè)有n個(gè)決策變量，m個(gè)約束條件。目標(biāo)函數(shù)：Max(Min)z=CX約束條件：AXW(=,N)bXN0其中，C=(c1,c2,…，cn)(價(jià)值向量)X=(x1,x2,…，xn)T(決策變量向量)b=(b1,b2,…，bm)T(限定向量)alla12 …aln(約束條件系數(shù)矩陣)a21 a22 (約束條件系數(shù)矩陣)AmXn= am1am2…amn數(shù)學(xué)模型的特點(diǎn)由目標(biāo)函數(shù)和約束條件構(gòu)成；目標(biāo)函數(shù)只有兩種情況：求極小或求極大。雙線性目標(biāo)函數(shù)是關(guān)于決策變量的線性函數(shù)所有約束條件是關(guān)于決策變量的線性函數(shù)。三、求解方法一：圖解法適用條件有且僅有兩個(gè)決策變量X1,X2。基本概念可行解；可行域；最優(yōu)解基本思路：先求出可行解(即找出可行域)再在可行解的基礎(chǔ)上(即在可行域內(nèi))求出最優(yōu)解。基本步驟 作圖找出可行域作出目標(biāo)函數(shù)等值線，判斷其平移的方向平移目標(biāo)函數(shù)等值線，在可行域內(nèi)找出最優(yōu)點(diǎn)，計(jì)算最優(yōu)解。圖解法解的情況唯一最優(yōu)解 ②無窮多最優(yōu)解無可行解 ④無界解注意：能夠區(qū)分無可行解和無界解的情況。圖解法的靈敏度分析靈敏度分析的含義；目標(biāo)函數(shù)中的系數(shù)ci的靈敏度分析；約束條件右端常數(shù)項(xiàng)bj的靈敏度分析；對偶價(jià)格：約束條件右端常數(shù)b增加一個(gè)單位而使目標(biāo)函數(shù)最優(yōu)值得到改進(jìn)的數(shù)量，稱之為該約束條件的對偶價(jià)格。對偶價(jià)格=Az/Ab方法二：單純型法(1)基本概念基；基向量，非基向量；基變量，非基變量；基本解，基本可行解，基本最優(yōu)解；可行基，最優(yōu)基⑵重要定理及性質(zhì)若LP的可行域存在，則可行域?yàn)橥苟噙呅巍Ｈ鬖P存在最優(yōu)解，則最優(yōu)解一定可在可行域凸多邊形的頂點(diǎn)上取得。LP問題的一個(gè)基本可行解對應(yīng)于可行域的一個(gè)頂點(diǎn)?？尚杏虻囊粋€(gè)頂點(diǎn) 一個(gè)基本可行解以單位矩陣ImXm做基，其基本解的特點(diǎn)是：所有非基變量xj=0，所有基變量xi=bi(標(biāo)準(zhǔn)型中規(guī)定bN0)，故單位矩陣可做可行基。(3)基本思路尋我初始基本可行解方春標(biāo)準(zhǔn)化并構(gòu)造初始可彳亍基(3)基本思路尋我初始基本可行解方春標(biāo)準(zhǔn)化并構(gòu)造初始可彳亍基stop迭代，尋找另一組基本可行解(4)表上作業(yè)法基本步驟彳鐳祖是*規(guī)定(4)表上作業(yè)法基本步驟彳鐳祖是*規(guī)定：LP數(shù)學(xué)模型的標(biāo)準(zhǔn)型:目標(biāo)函數(shù)：MaxZ=CX約束條件：XN0要求:能夠?qū)⑷我饽Ｐ蜆?biāo)準(zhǔn)化。(5)解的情況及判別定理(以極大化問題為例)判別定理解的情況所有bjW0,且所有人工變量=0唯一最優(yōu)解對于某個(gè)基本最優(yōu)解，所有crW0,又存在某個(gè)非基變量檢驗(yàn)數(shù)9村。無窮多最優(yōu)解所有qw。，但人工變量尹。無可行解在某次迭代表中，有一個(gè)非基變量的檢驗(yàn)數(shù)g>0,但Pk列中沒有正元素(HikEO)無界解方法三：對偶單純型法原問題與對偶問題的數(shù)學(xué)模型

①對稱形式的對偶（對偶定義）設(shè)有原問題：LP:則對偶問題為：DP:要求：掌握二者模型之間的對應(yīng)關(guān)系。原問題LP對偶問題DP決策變量個(gè)數(shù)nm約束條件個(gè)數(shù)mn價(jià)值向量CbT限定向量bCT約束條件系數(shù)矩陣AAT目標(biāo)函數(shù)maxmin約束條件W非對稱形式的對偶方法：先將原問題化為對稱形式（注:無需處理等式約束及自由變量），再由對偶定義直接寫出對偶問題即可。等式約束 自由變量要求：能夠根據(jù)任意模型（原問題）寫出其對偶問題模型。（2） 對偶規(guī)劃的基本性質(zhì)對稱性弱對偶性最優(yōu)性強(qiáng)對偶性（3） 對偶單純型法適用條件（極大化問題）：初始單純形表中，檢驗(yàn)數(shù)行所有ojW0；初始單純形表中，常數(shù)列中至少存在一個(gè)負(fù)值（bk<0）基本步驟：從與單純型法的比較中掌握此方法。

單純形法、’對偶單純形法構(gòu)造初始可行基需引入人工變量無需引入人工變量入基變量和出基變量確定順序先入后出先出后入入基變量確定原則檢驗(yàn)數(shù)大中取大最小負(fù)中比值原則出基變量確定原則最小非負(fù)比值原則常數(shù)項(xiàng)負(fù)中最小原則最優(yōu)性檢驗(yàn)1◎。餌所有勺＜0且所有人工變量=化所有常數(shù)項(xiàng)bj尋q264.求解運(yùn)輸問題的表上作業(yè)法適用條件：產(chǎn)銷平衡的運(yùn)輸問題?；静襟E注意：假設(shè)有m個(gè)產(chǎn)地，n個(gè)銷地，則運(yùn)輸問題有m+n-1個(gè)基變量。(3)解的情況唯一最優(yōu)解；有限多最優(yōu)解整數(shù)規(guī)劃(IP)一、 問題的提出投資場所的選擇指派問題分布系統(tǒng)設(shè)計(jì)投資問題二、 建模純整數(shù)規(guī)劃問題Max(min)Z=CXAXN(W,=)bXN0X1,X2，…Xn均為整數(shù)混合整數(shù)規(guī)劃問題Max(min)Z=CXAXN(W=)bXN0X1,X2，…Xk均為整數(shù)(k<n)求解方法：分枝定界法，割平面法整數(shù)規(guī)劃問題Max(min)Z=CXAXN(W=)bX=0或1求解方法：隱枚舉法，匈牙利法三、 模型求解分枝定界法求解指派問題的匈牙利法。目標(biāo)規(guī)劃(OP)一、 問題的提出多目標(biāo)決策問題二、 建模基本概念決策變量偏差變量；絕對約束，目標(biāo)約束；優(yōu)先因子，權(quán)系數(shù)基本步驟設(shè)出決策變量根據(jù)各個(gè)目標(biāo)列出絕對約束將絕對約束轉(zhuǎn)化為目標(biāo)約束和目標(biāo)函數(shù)并根據(jù)實(shí)際問題對各個(gè)目標(biāo)賦予優(yōu)先因子或權(quán)系數(shù)數(shù)學(xué)模型一般形式minZ=f（P,w,d+,d-）Fi（x）+ - =biX,d+,d-N0注：OP數(shù)學(xué)模型中可能存在絕對約束。三、模型求解圖解法^（1） 適用條件有且僅有兩個(gè)決策變量。（2） 基本步驟注意：①準(zhǔn)確判斷各偏差變量增加的方向。②從優(yōu)先權(quán)最高的目標(biāo)開始求解，清楚寫出每一優(yōu)先級目標(biāo)的滿意解。動(dòng)態(tài)規(guī)劃（DP）一、 問題的提出多階段決策問題：★1.最短路問題 ★2.資源分配問題背包問題 4.生產(chǎn)與存貯問題 5.系統(tǒng)可靠性問題二、 建模注意：動(dòng)態(tài)規(guī)劃沒有統(tǒng)一確定的數(shù)學(xué)模型。1.基本概念階段；狀態(tài)；決策；策略；指標(biāo)函數(shù)（包括階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)）；狀態(tài)轉(zhuǎn)移方程；基本方程（遞推公式）2.基本步驟|分析問題，劃分階段設(shè)出決策變量和狀態(tài)變量、寫出狀態(tài)轉(zhuǎn)移方程、最優(yōu)指標(biāo)函數(shù)及遞推公式依據(jù)最優(yōu)化原理，運(yùn)用逆序算法，逆向?qū)?yōu)，列表計(jì)算每個(gè)階段的最優(yōu)指標(biāo)函數(shù)值及決策變量最優(yōu)值，最后逆向查表求得整個(gè)過程上的最優(yōu)策略三、模型求解逆序算法（根據(jù)最優(yōu)化原理）★1.求解最短路問題的逆推法；★2.求解最短路問題的順推法。圖與網(wǎng)絡(luò)一、 基本概念圖;無向圖;有向圖；簡單圖;多重圖；連通圖;頂點(diǎn)的次網(wǎng)絡(luò)樹;生成子圖;生成樹；最小生成樹二、 問題的提出1.最短路問題2.最小生成樹問題最大流問題最小費(fèi)用最大流問題三、 求解方法1.求解最短路問題的雙標(biāo)號法；2.求解最小生成樹問題的破圈法和避圈法；求解最大流問題的線性規(guī)劃法和圖論解法；求解最小費(fèi)用最大流問題的線性規(guī)劃法和圖論解法。考試形式：閉卷考試考試時(shí)間：120分鐘考試題型：填空題，判斷題，計(jì)算題，應(yīng)用題計(jì)算題