清華大學(xué)-《運(yùn)籌學(xué)》課程教學(xué)大綱

1、運(yùn)籌學(xué)課程教學(xué)大綱 課程名稱：運(yùn)籌學(xué) 編號(hào).20345144： 學(xué)時(shí)：72編者姓名：曾鴻能 單位：中山大學(xué) 職稱：副教授主審姓名： 單位： 職稱：教授對(duì)象：本科生 專業(yè)：資源與環(huán)境規(guī)劃 年級(jí)：三年級(jí)編寫日期：2001年9月課程目的與教學(xué)基本要求學(xué)習(xí)本課程后，使學(xué)生掌握運(yùn)籌學(xué)有關(guān)分支的基本理論和方法，牢固掌握解題算法步驟，培養(yǎng)學(xué)生應(yīng)用規(guī)劃論、優(yōu)化技術(shù)解決實(shí)際問題能力。為專業(yè)課在系統(tǒng)規(guī)劃、最優(yōu)設(shè)計(jì)、參數(shù)優(yōu)選、最優(yōu)管理與運(yùn)行等數(shù)學(xué)方法及計(jì)算機(jī)算法打下必要的基礎(chǔ)。在已學(xué)過微積分、初等集合論和線性代數(shù)基礎(chǔ)上學(xué)習(xí)本課程，通過教授、自學(xué)、復(fù)習(xí)、作業(yè)練習(xí)、輔導(dǎo)、編程上機(jī)等教學(xué)環(huán)節(jié)達(dá)到上述目的。學(xué)習(xí)中要注意到學(xué)

2、科系統(tǒng)性，數(shù)學(xué)概念和邏輯的嚴(yán)密性、準(zhǔn)確性和完整性，但不偏重純數(shù)學(xué)方法論證。著重基本概念、基本思路、基本方法、算法步驟、幾何直觀解析。了解各種方法特點(diǎn)和實(shí)用價(jià)值，提高建立模型、分析求解能力和技巧。應(yīng)注重實(shí)際應(yīng)用中建立模型，選擇可行求解的理論方法，編制算法的計(jì)算機(jī)程序這三方面訓(xùn)練的有機(jī)結(jié)合。課程內(nèi)容（含學(xué)時(shí)分配）緒言：運(yùn)籌學(xué)簡(jiǎn)史、性質(zhì)和特點(diǎn)、工作步驟、模型、分支及應(yīng)用、運(yùn)籌學(xué)展望（1學(xué)時(shí)）線性規(guī)劃與目標(biāo)規(guī)劃（共30學(xué)時(shí)）1-1 線性規(guī)劃問題及其數(shù)學(xué)模型 （2學(xué)時(shí)）一、應(yīng)用實(shí)例 二、線性規(guī)劃的數(shù)學(xué)模型 三、標(biāo)準(zhǔn)形式1-2 線性規(guī)劃問題的圖解法 （1學(xué)時(shí)）教學(xué)要求：1初步掌握建立線性規(guī)劃模型方法 2掌

3、握線性規(guī)劃模型特征；如何化線性規(guī)劃模型為標(biāo)準(zhǔn)型 3掌握兩個(gè)變量線性規(guī)劃問題的圖解法重點(diǎn)：通過圖解法初步了解基本概念和求解思路1-3 線性規(guī)劃的基本概念和基本定理 （4學(xué)時(shí)）教學(xué)要求：1掌握可行解、基、凸集、凸組合、頂點(diǎn)的概念 2了解線性規(guī)劃理論依據(jù)-幾個(gè)基本定理、求解線性規(guī)劃問題基本思路重點(diǎn)：三個(gè)基本定理難點(diǎn)：基本定理的證明1-4 單純形法 （4學(xué)時(shí)）單純形法求解過程說明單純形表單純形表的結(jié)構(gòu)和原理換基 確定換入變量 確定換出變量 旋轉(zhuǎn)迭代教學(xué)要求：牢固掌握線性規(guī)劃的單純形求解方法重點(diǎn)：?jiǎn)渭冃畏椒ㄇ蠼獠襟E和公式難點(diǎn)：?jiǎn)渭冃伪順?gòu)成原理，換基迭代公式推導(dǎo)1-5 單純形法進(jìn)一步討論 （2學(xué)時(shí)）（一）

4、大M單純形法 （二）兩階段法 （三）退化問題 （四）檢驗(yàn)數(shù)的幾種表示法（五）單純形法小結(jié)教學(xué)要求：1了解引入工人變量目的 2牢固掌握大M法和兩階段法求解過程、判別什么情況下無解 3牢固掌握單純形法計(jì)算框圖重點(diǎn)：兩階段法及單純形法計(jì)算框圖1-6 改進(jìn)單純形法 （2學(xué)時(shí)）教學(xué)要求：1了解改進(jìn)單純形方法的思想 2掌握改進(jìn)單純形法計(jì)算步驟重點(diǎn)：改進(jìn)單純形法計(jì)算步驟（主要用于計(jì)算機(jī)計(jì)算）難點(diǎn)：新基逆矩陣求解公式及其實(shí)質(zhì)1-7 線性對(duì)偶規(guī)劃 （4學(xué)時(shí)）一、對(duì)偶問題提出 二、對(duì)偶規(guī)則 三、線性對(duì)偶理論四、對(duì)偶問題的經(jīng)濟(jì)學(xué)解釋影子價(jià)格 五、對(duì)偶單純形法教學(xué)要求：1掌握對(duì)偶規(guī)則 2了解線性對(duì)偶理論、影子價(jià)格的意

5、義 3牢固掌握對(duì)偶單純形法重點(diǎn)：對(duì)偶單純形法計(jì)算步驟及對(duì)偶單純形法應(yīng)用范圍難點(diǎn)：線性對(duì)偶理論的證明1-8 靈敏度分析與參數(shù)線性規(guī)劃 （3學(xué)時(shí)）教學(xué)要求：1掌握系數(shù)變化范圍的確定及增加新變量、新約束靈敏度分析 2掌握參數(shù)連續(xù)變化對(duì)最優(yōu)解及最優(yōu)值的影響重點(diǎn)：靈敏度分析與參數(shù)線性規(guī)劃的應(yīng)用。關(guān)鍵是判斷最優(yōu)方案的可行性和最優(yōu)性是否被破壞，從而確定變化范圍。1-9 運(yùn)輸問題 （4學(xué)時(shí)）一、運(yùn)輸問題的數(shù)學(xué)模型 二、初始基可行解的確定三、換基迭代，確定最優(yōu)解 四、應(yīng)用舉例（包括習(xí)題課）教學(xué)要求：1掌握運(yùn)輸問題的數(shù)學(xué)模型、系數(shù)矩陣特殊形式 2掌握用西北角法、最小元素法求初始基可行解 3掌握位勢(shì)法求解、牢固掌握

6、三合一表格求解運(yùn)輸問題過程重點(diǎn)：運(yùn)輸問題的求解過程。熟悉運(yùn)輸、作物布局、轉(zhuǎn)運(yùn)等問題的應(yīng)用1-10 目標(biāo)規(guī)劃 （4學(xué)時(shí)）基本概念及數(shù)學(xué)模型目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的單純形法應(yīng)用舉例教學(xué)要求：1熟悉目標(biāo)規(guī)劃有關(guān)的概念，正確建立目標(biāo)規(guī)劃數(shù)學(xué)模型 2牢固掌握目標(biāo)規(guī)劃的單純形求解方法重點(diǎn)：對(duì)實(shí)際問題如何建立目標(biāo)規(guī)劃的數(shù)學(xué)模型，如何用目標(biāo)規(guī)劃的單純形法求解，對(duì)各種滿意解的分析。 整數(shù)規(guī)劃 （共8學(xué)時(shí)）2-1 整數(shù)規(guī)劃問題的提出 （2學(xué)時(shí)）2-2 割平面法2-3 分枝定界法 （2學(xué)時(shí)）2-4 0-1型整數(shù)規(guī)劃 （2學(xué)時(shí)）2-5 指派問題 （2學(xué)時(shí)）教學(xué)要求：1了解割平面法的基本思路，掌握割平面約束的生成、割

7、平面法的求解步驟 2了解分枝定界法的基本思路，掌握兩個(gè)分枝的求法、定界與剪枝的原則，掌握分枝定界法解題過程 3掌握0-1型整數(shù)規(guī)劃求解過程 4掌握指派問題的匈牙利解法重點(diǎn)：分枝定界法求解，定界與剪枝原則難點(diǎn)：0-1型整數(shù)規(guī)劃變量的不可行性指標(biāo)計(jì)算 非線性規(guī)劃 （全部授完需36學(xué)時(shí)）3-1 非線性規(guī)劃的數(shù)學(xué)模型和基本概念 （4學(xué)時(shí)）教學(xué)要求：1了解非線性規(guī)劃數(shù)學(xué)模型一般形式及其與線性規(guī)劃的區(qū)別 2掌握基本概念：局部極值和全局極值、梯度、海賽矩陣、正定、負(fù)定、半正定、半負(fù)定矩陣、不定矩陣 3掌握凸函數(shù)的定義和性質(zhì)，凸函數(shù)的判別（一階條件和二階條件定理） 4掌握凸規(guī)劃的定義極其重要特性重點(diǎn)：凸函數(shù)、

8、凸規(guī)劃的定義極其判別3-2 無約束問題最優(yōu)性條件與下降迭代算法 （2學(xué)時(shí)）教學(xué)要求：1掌握用海賽矩陣判斷駐點(diǎn)的性質(zhì) 2掌握一階必要條件，二階必要條件，二階充分條件和充要條件四個(gè)定理，了解定理的證明 3了解下降迭代算法的概念及下降迭代算法的一般步驟，了解收斂性及收斂速度（用收斂的階或二次收斂性判別），掌握迭代終止判別準(zhǔn)則3-3 一維搜索 （6學(xué)時(shí)）一進(jìn)退法 二斐波那契法 三0618法（黃金分割法）四拋物線插值法 五三次插值法（作一般介紹）教學(xué)要求：1掌握各種方法的特點(diǎn)、優(yōu)點(diǎn)與不足 2掌握各種方法計(jì)算步驟與算法框圖重點(diǎn)：0618法，拋物線插值法3-4 無約束極值問題的解析法 （8學(xué)時(shí)）最速下降法牛

9、頓法共軛梯度法（F-R法）變尺度法（DFP、BFGS算法）教學(xué)要求：1掌握幾種方法的基本原理和計(jì)算步驟 2掌握幾種方法搜索方向構(gòu)成：如負(fù)梯度方向、牛頓方向、共軛方向、擬牛頓方向 3了解各種方法優(yōu)缺點(diǎn)重點(diǎn)：熟悉幾種方法算法步驟。特別是目前認(rèn)為較好的DFP、BFGS算法難點(diǎn)：DFP方法中變尺度矩陣的推導(dǎo)3-5 無約束極值問題的直接法 （6學(xué)時(shí)）一坐標(biāo)輪換法 二步長(zhǎng)加速法 三powell法 四單純形調(diào)優(yōu)法教學(xué)要求：1掌握幾種方法的算法步驟 2了解幾種方法的優(yōu)缺點(diǎn)重點(diǎn)：powell方法及目前生產(chǎn)中常用的單純形調(diào)優(yōu)法3-6 等式約束條件下的非線性規(guī)劃 （2學(xué)時(shí)）一等式約束下的消元法 二拉格朗日乘子法 三

10、罰函數(shù)法（外點(diǎn)法）教學(xué)要求：了解拉格朗日乘子法，掌握外點(diǎn)法3-7 不等式約束條件下的非線性規(guī)劃 （8學(xué)時(shí)）可行方向和起作用的約束的概念庫恩塔克條件非線性約束條件下的可行方向法罰函數(shù)法 1外罰函數(shù)法 2內(nèi)罰函數(shù)法 3混合法（只作簡(jiǎn)單介紹）4乘子法（簡(jiǎn)單介紹）復(fù)合形法教學(xué)要求：1了解庫恩塔克條件 2掌握Zoutendijk可行方向法以及Topkis-Veinott修正方法。了解下降可行方向滿足條件。了解廣義既約梯度法（GRG算法） 3了解化約束為無約束的懲罰法中最基本的兩種方法：外罰函數(shù)法和內(nèi)罰函數(shù)法。了解這兩種方法適用范圍及其優(yōu)缺點(diǎn)。針對(duì)兩種方法不足而改進(jìn)的乘子法作一般的了解。 4掌握復(fù)合形法基

11、本思路及計(jì)算步驟重點(diǎn)：懲罰法，工程中常用的復(fù)合形法難點(diǎn)：方法定理的證明3-8 非線性規(guī)劃問題的線性化 （6學(xué)時(shí)）用線性逼近法求解線性約束條件下的非線性規(guī)劃（Frank-Wolfe方法）用線性逼近法求解非線性約束條件下的非線性規(guī)劃（近似規(guī)劃法，即MAP法）變量分割法可分規(guī)劃法教學(xué)要求：1掌握幾種方法適用范圍及特點(diǎn) 2掌握非線性規(guī)劃如何線性化 3掌握各種方法求解過程重點(diǎn)：近似規(guī)劃法（MAP法）3-9 應(yīng)用舉例 （2學(xué)時(shí)）了解水資源規(guī)劃中非線性規(guī)劃如何作線性化求解動(dòng)態(tài)規(guī)劃 （共16學(xué)時(shí)）4-1 動(dòng)態(tài)規(guī)劃的基本方法與原理 （5學(xué)時(shí)）多階段決策過程及實(shí)例動(dòng)態(tài)規(guī)劃的基本概念最優(yōu)性原理動(dòng)態(tài)規(guī)劃的基本思想和基

12、本方程動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型及構(gòu)成模型的條件動(dòng)態(tài)規(guī)劃的逆序解法和順序解法4-2 動(dòng)態(tài)規(guī)劃的最優(yōu)性定理 （1學(xué)時(shí)）4-3 不定期多階段決策過程 （2學(xué)時(shí)）一函數(shù)迭代法 二策略迭代法4-4 多維動(dòng)態(tài)規(guī)劃 （3學(xué)時(shí)）拉格朗日乘數(shù)法逐次逼近法粗格子點(diǎn)法（疏密法）離散微分動(dòng)態(tài)規(guī)劃法（DDDP法）4-5 確定性動(dòng)態(tài)規(guī)劃應(yīng)用舉例 （2學(xué)時(shí)）4-6 隨機(jī)性問題的動(dòng)態(tài)規(guī)劃法 （3學(xué)時(shí)）各階段的隨機(jī)狀態(tài)變量相互獨(dú)立時(shí)的動(dòng)態(tài)規(guī)劃問題相鄰兩階段的隨機(jī)狀態(tài)變量具有簡(jiǎn)單的馬爾可夫鏈關(guān)系時(shí)的動(dòng)態(tài)規(guī)劃問題教學(xué)要求：1掌握動(dòng)態(tài)規(guī)劃的基本概念：階段、狀態(tài)、決策、策略、狀態(tài)轉(zhuǎn)移方程、指標(biāo)函數(shù)和最優(yōu)值函數(shù)、最優(yōu)策略、最優(yōu)軌線2了解動(dòng)態(tài)規(guī)

13、劃的基本理論：最優(yōu)性定理和最優(yōu)性原理3掌握動(dòng)態(tài)規(guī)劃基本思想和基本方程4牢固掌握動(dòng)態(tài)規(guī)劃的順序解法和逆序解法。會(huì)處理動(dòng)態(tài)與靜態(tài)規(guī)劃的關(guān)系5了解和掌握若干典型問題的動(dòng)態(tài)規(guī)劃模型及求解技巧：如最短路線、資源分配、生產(chǎn)計(jì)劃、貨物存儲(chǔ)、設(shè)備更新與系統(tǒng)可靠性問題、背包問題、推銷商問題等6了解多維動(dòng)態(tài)規(guī)劃降維方法和減少離散狀態(tài)點(diǎn)數(shù)方法7了解隨機(jī)性問題的動(dòng)態(tài)規(guī)劃求解方法重點(diǎn)：動(dòng)態(tài)規(guī)劃順序解法和逆序解法；若干典型問題動(dòng)態(tài)規(guī)劃模型及求解技巧；離散微分動(dòng)態(tài)規(guī)劃法難點(diǎn)：最優(yōu)性定理的證明，隨機(jī)性問題的動(dòng)態(tài)規(guī)劃（3）使用說明每講完一種方法，至少布置一道作業(yè)，作為基本訓(xùn)練、鞏固和加深對(duì)方法的基本原理，算法的步驟的理解。 計(jì)劃講授兩次習(xí)題課，介紹難懂和技巧性強(qiáng)或教材沒有詳細(xì)提到的問題。 每講完一章，結(jié)合資源與環(huán)境專業(yè)的實(shí)際，介紹方法的應(yīng)用。 每講完一章，作個(gè)小結(jié)，并介紹新方法，發(fā)展動(dòng)向，以及教材還沒有涉及到的內(nèi)容。 在時(shí)間和條件許可下，可適當(dāng)選擇一些方法的計(jì)算程序作介紹，學(xué)生自己上機(jī)實(shí)習(xí)。 按學(xué)時(shí)的多少，適當(dāng)增減內(nèi)容。（4）主要參考書目錢頌迪主編， 運(yùn)籌學(xué)（增訂版）， 清華大學(xué)出版社， 1990年管梅谷、鄭漢鼎， 線性規(guī)劃， 山東科學(xué)技術(shù)出版社， 1983張建中、許紹吉著，