《運(yùn)籌學(xué)》學(xué)習(xí)指南

PAGEPAGE5《運(yùn)籌學(xué)》學(xué)習(xí)指南一、課程基本情況、性質(zhì)、研究對(duì)象和任務(wù)本課程教學(xué)學(xué)時(shí)：72學(xué)時(shí)，上機(jī)9學(xué)識(shí)。運(yùn)籌學(xué)是一門廣泛應(yīng)用現(xiàn)有的科學(xué)技術(shù)知識(shí)和數(shù)學(xué)工具，以定性與定量相結(jié)合的方法研究和解決管理、經(jīng)濟(jì)和工程技術(shù)中提出的實(shí)際問題，為決策者選擇最優(yōu)決策提供定量依據(jù)的一門決策科學(xué)?！哆\(yùn)籌學(xué)》課程是數(shù)學(xué)學(xué)院的專業(yè)課，授課對(duì)象為信息與計(jì)算科學(xué)專業(yè)、數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)、統(tǒng)計(jì)學(xué)專業(yè)的本科生。本課程的主要任務(wù)是使學(xué)生學(xué)習(xí)運(yùn)籌學(xué)主要分支的基本模型及其相關(guān)理論、求解方法，掌握運(yùn)籌學(xué)整體優(yōu)化的思想和若干定量分析的優(yōu)化技術(shù)，同時(shí)能夠運(yùn)用常用軟件（如LINGO,Excel,Matlab等）求解運(yùn)籌學(xué)問題，從而使學(xué)生具備較系統(tǒng)完善的專業(yè)基礎(chǔ)知識(shí)和正確應(yīng)用各類模型分析來解決實(shí)際優(yōu)化問題的能力。本課程主要包括線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、圖論與網(wǎng)絡(luò)分析、排對(duì)論、決策分析、對(duì)策論等內(nèi)容。要求學(xué)生具備的基礎(chǔ)為數(shù)學(xué)分析（或高等數(shù)學(xué)）、高等代數(shù)（或線性代數(shù)）、概率論。二、基本學(xué)習(xí)方法本課程理論、實(shí)踐性均強(qiáng)，學(xué)習(xí)時(shí)注意理論聯(lián)系實(shí)際，要完成一定數(shù)量作業(yè)，加強(qiáng)上機(jī)練習(xí)。通過教學(xué)的各個(gè)環(huán)節(jié)使學(xué)生達(dá)到各章中所提到的基本要求。三、教材處理及多媒體課件說明1.教材處理本課程使用教材為：《運(yùn)籌學(xué)（第3版）》刁在筠，劉桂真，宿潔，馬建華編，高等教育出版社，2007?！哆\(yùn)籌學(xué)（第一版）》是通過教育部組織的全國(guó)競(jìng)標(biāo)獲得的編寫權(quán)，在全國(guó)廣泛應(yīng)用并多次獲獎(jiǎng)，曾獲教育部科技進(jìn)步二等獎(jiǎng)?！哆\(yùn)籌學(xué)（第二版）》作為面向二十一世紀(jì)教材出版，2007年《運(yùn)籌學(xué)》第三版作為“十一五”國(guó)家規(guī)劃教材出版并被評(píng)為國(guó)家級(jí)精品教材。教材內(nèi)容均全面、結(jié)構(gòu)嚴(yán)謹(jǐn)、理論性強(qiáng)。體現(xiàn)了厚理論、寬口徑，理論聯(lián)系實(shí)際的特點(diǎn)。每章后的習(xí)題也編排為理論與應(yīng)用兩部分，并配有相關(guān)的教學(xué)計(jì)算軟件和電子版課件及運(yùn)籌學(xué)習(xí)題解答。輔助教材為：戎曉霞，宿潔，劉桂真編，《運(yùn)籌學(xué)（第3版）學(xué)習(xí)輔導(dǎo)與習(xí)題解析》，高等教育出版社，2009。參考教材請(qǐng)見《運(yùn)籌學(xué)》教材后各節(jié)所附。2.多媒體課件運(yùn)籌學(xué)教學(xué)課件基于教材內(nèi)容，清晰完整，教材中所有章節(jié)的定理及證明、算法及推導(dǎo)、例題求解都有詳細(xì)演示，利于自學(xué)。對(duì)學(xué)生開闊視野、擴(kuò)展思路、增強(qiáng)實(shí)踐意識(shí)以及提高分析問題、解決問題的能力和創(chuàng)造能力都具有非常重要的作用。但是，應(yīng)該提醒的是，在利用多媒體課件進(jìn)行學(xué)習(xí)時(shí)，同學(xué)們不能將注意力只集中在畫面上，而忽視對(duì)課程內(nèi)容的關(guān)注和理解。課堂學(xué)習(xí)中，由于信息量較大，課堂進(jìn)度較快，應(yīng)注意對(duì)重要內(nèi)容作記錄，并在課下及時(shí)復(fù)習(xí)和總結(jié)。四、關(guān)于考試的說明本課程的考核成績(jī)由以下幾部分構(gòu)成：閉卷為主，結(jié)合部分開卷。平時(shí)成績(jī)占40%，期末成績(jī)占60%。五、各章基本內(nèi)容、重點(diǎn)難點(diǎn)、教學(xué)要求及作業(yè)第1章緒論基本內(nèi)容本章首先介紹運(yùn)籌學(xué)的概況，包括運(yùn)籌學(xué)的由來和發(fā)展、運(yùn)籌學(xué)的性質(zhì)與特點(diǎn)、運(yùn)籌學(xué)的主要內(nèi)容和運(yùn)籌學(xué)的發(fā)展趨勢(shì)。然后，通過幾個(gè)例子分別介紹運(yùn)籌學(xué)中線性規(guī)劃、隨機(jī)規(guī)劃和網(wǎng)絡(luò)分析的數(shù)學(xué)模型。重點(diǎn)難點(diǎn)重點(diǎn)：運(yùn)籌學(xué)的實(shí)際應(yīng)用情況難點(diǎn)：引入計(jì)算機(jī)軟件Lingo\Excel\Matlab.教學(xué)要求了解運(yùn)籌學(xué)的內(nèi)容、目的、發(fā)展與現(xiàn)況。作業(yè)查閱運(yùn)籌學(xué)的典型應(yīng)用第2章線性規(guī)劃基本內(nèi)容線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，其應(yīng)用極其廣泛，其作用已為越來越多的人所重視。從線性規(guī)劃誕生至今的幾十年中，隨著計(jì)算機(jī)的逐漸普及，它越來越急速地滲透于農(nóng)業(yè)生產(chǎn)、商業(yè)活動(dòng)、軍事行動(dòng)和科學(xué)研究的各個(gè)方面，為社會(huì)節(jié)省的財(cái)富、創(chuàng)造的價(jià)值無法估量。最近十多年來，線性規(guī)劃無論是在深度還是在廣度方面都取得了重大進(jìn)展。本章先通過例子歸納線性規(guī)劃數(shù)學(xué)模型的一般形式，然后著重介紹有關(guān)線性規(guī)劃的一些基本概念、基本理論及解線性規(guī)劃問題的若干方法。重點(diǎn)難點(diǎn)重點(diǎn)：線性規(guī)劃數(shù)學(xué)模型的基本特征和標(biāo)準(zhǔn)形式圖解法(3)線性規(guī)劃問題的基本可行解的概念，線性規(guī)劃的基本理論。(4)單純形法(5)兩階段法(6)線性規(guī)劃的對(duì)偶理論(7)對(duì)偶單純形法(8)靈敏度分析難點(diǎn)：?jiǎn)渭冃畏ǎ€性規(guī)劃的對(duì)偶理論，靈敏度分析教學(xué)要求(1)掌握線性規(guī)劃數(shù)學(xué)模型的基本特征和標(biāo)準(zhǔn)形式，以及線性規(guī)劃問題數(shù)學(xué)模型的建立方法，學(xué)會(huì)用圖解法求解簡(jiǎn)單的線性規(guī)劃問題。(2)理解線性規(guī)劃問題的解的概念，掌握線性規(guī)劃的基本理論。(3)了解單純形表的構(gòu)成，熟練掌握運(yùn)用單純形法求解線性規(guī)劃問題。(4)掌握兩階段法的計(jì)算步驟。(5)理解原問題與對(duì)偶問題的關(guān)系，掌握線性規(guī)劃的對(duì)偶理論。(6)熟悉對(duì)偶單純形法的計(jì)算步驟，掌握運(yùn)用對(duì)偶單純形法求解線性規(guī)劃問題。(7)理解當(dāng)線性規(guī)劃問題中的某些數(shù)據(jù)發(fā)生改變時(shí)對(duì)已求出的最優(yōu)解的影響，掌握調(diào)整的方法。作業(yè)第2章習(xí)題：1,3,5(1),9,14,16(1),17(1),18,20,22(1),23(1)(3).B(1)思考：線性規(guī)劃的退化問題。第3章整數(shù)線性規(guī)劃基本內(nèi)容整數(shù)線性規(guī)劃與線性規(guī)劃有著密不可分的關(guān)系，它的一些基本算法的設(shè)計(jì)都是以相應(yīng)的線性規(guī)劃的最優(yōu)解為出發(fā)點(diǎn)的。但是變量取整數(shù)值的要求本質(zhì)上是一種非線性約束。因此解整數(shù)線性規(guī)劃的“困難度”大大超過線性規(guī)劃，一些著名的“困難”問題都是整數(shù)線性規(guī)劃問題。本章主要介紹整數(shù)線性規(guī)劃的一些實(shí)際背景及常用算法。重點(diǎn)難點(diǎn)重點(diǎn)：(1)割平面法的原理和計(jì)算步驟。(2)分枝定界法的原理計(jì)算步驟。難點(diǎn)：割平面法的原理和計(jì)算步驟，分枝定界法的原理計(jì)算步驟。教學(xué)要求(1)了解求解整數(shù)規(guī)劃的困難性。(2)掌握割平面法的原理和計(jì)算步驟。(3)掌握分枝定界法的原理計(jì)算步驟(4)了解隱枚舉法。作業(yè)第3章2,3,6(1).B(1)思考：整數(shù)線性規(guī)劃的求解困難性第4章非線性規(guī)劃基本內(nèi)容非線性規(guī)劃研究的對(duì)象是非線性函數(shù)的數(shù)值最優(yōu)化問題。它的理論和方法滲透到許多方面，特別是在軍事、經(jīng)濟(jì)、管理、生產(chǎn)過程自動(dòng)化、工程設(shè)計(jì)和產(chǎn)品優(yōu)化設(shè)計(jì)等方面都有著重要的應(yīng)用。處理非線性的優(yōu)化問題并非易事，它沒有一個(gè)像線性規(guī)劃中單純形法那樣的通用算法，而是根據(jù)問題的不同特點(diǎn)給出不同的解法，因而這些解法均有各自的適用范圍。本章將簡(jiǎn)潔地介紹有關(guān)非線性規(guī)劃的基本概念和理論、某些重要算法以及相應(yīng)的流行軟件。重點(diǎn)難點(diǎn)重點(diǎn)：(1)非線性規(guī)劃求解模式。(2)凸規(guī)劃(3)0.618法、Newton法，Goldstein法，Armijo法。(4)無約束優(yōu)化問題的最優(yōu)性質(zhì)，最速下降法和共軛方向法。(5)約束優(yōu)化問題的最優(yōu)性質(zhì)，簡(jiǎn)約梯度法和懲罰函數(shù)法。難點(diǎn)：0.618法、Newton法，Goldstein法的基本思想；共軛方向法；約束優(yōu)化問題的K-T條件；懲罰函數(shù)法的理論依據(jù)。教學(xué)要求掌握非線性規(guī)劃的基本形式和求解模式。(2)掌握凸函數(shù)和凸規(guī)劃的概念及性質(zhì)。(3)掌握0.618法、Newton，了解Goldstein法，Armijo法。(4)掌握無約束優(yōu)化問題的最優(yōu)性質(zhì)，熟練運(yùn)用最速下降法和共軛方向法。(5)掌握約束優(yōu)化問題的最優(yōu)性質(zhì)，熟練運(yùn)用簡(jiǎn)約梯度法和懲罰函數(shù)法。作業(yè)第4章習(xí)題2,5(1)(2),7,9,10,14(1),16(1),20,22,26,B(1)查閱：非線性規(guī)劃的對(duì)偶和新算法第5章動(dòng)態(tài)規(guī)劃基本內(nèi)容動(dòng)態(tài)規(guī)劃所研究的對(duì)象是多階段決策問題。所謂多階段決策問題是指一類活動(dòng)過程，它可以分為若干個(gè)互相聯(lián)系的階段，在每個(gè)階段都需要作出決策。這個(gè)決策不僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)。每個(gè)階段的決策確定以后，就得到一個(gè)決策序列，稱為策略。多階段決策問題就是求一個(gè)策略，使各階段的效益的總和達(dá)到最優(yōu)。重點(diǎn)難點(diǎn)重點(diǎn)：(1)動(dòng)態(tài)規(guī)劃的基本概念和基本原理。(2)最短路問題、資源分配問題的動(dòng)態(tài)規(guī)劃模型。難點(diǎn)：動(dòng)態(tài)規(guī)劃的基本原理；動(dòng)態(tài)規(guī)劃模型的建立；求解方法。教學(xué)要求(1)理解動(dòng)態(tài)規(guī)劃的基本概念和基本原理。(2)掌握動(dòng)態(tài)規(guī)劃模型的建立與求解方法。作業(yè)第5章習(xí)題：2,5,6,B(1)查閱：不確定情況下的多階段決策問題處理第6章圖與網(wǎng)絡(luò)分析基本內(nèi)容解決某些大型系統(tǒng)問題時(shí)，為了尋找效率更高的出路，引入了網(wǎng)絡(luò)分析。網(wǎng)絡(luò)模型既具有線性規(guī)劃的一般性，又具有網(wǎng)絡(luò)自身的特殊結(jié)構(gòu)。因此，解決這一類問題時(shí)，可以運(yùn)用線性規(guī)劃的對(duì)偶理論進(jìn)行分析，并結(jié)合網(wǎng)絡(luò)的特點(diǎn)得到一些相當(dāng)有效的算法。這一章我們將考察幾個(gè)網(wǎng)絡(luò)模型的特征，并給出它們的求解方法。這些方法非常有效，可以解一些大型系統(tǒng)的問題。重點(diǎn)難點(diǎn)重點(diǎn)：(1)圖論基本概念。(2)樹、支撐樹、最小樹的基本性質(zhì)，求解最小樹問題的Kruskal和Dijkstra算法。(3)求解最短路問題的Dijkstra算法。(4)求解最大流問題的Ford-Fulkerson算法。(5)求最小費(fèi)用流問題和運(yùn)輸問題的對(duì)偶算法。(6)二分圖對(duì)集的基本定理，二分圖的最大基數(shù)對(duì)集和分派問題的求解算法。難點(diǎn)：Kruskal和Dijkstra算法的原理；最短有向路方程基本原理和Dijkstra算法；最大流問題的基本原理和Ford-Fulkerson算法；求最小費(fèi)用流問題和運(yùn)輸問題的原-對(duì)偶算法；最大基數(shù)對(duì)集和分派問題的原-對(duì)偶算法。教學(xué)要求(1)掌握?qǐng)D論基本概念。(2)掌握樹、支撐樹、最小樹的基本性質(zhì)，熟悉Kruskal和Dijkstra算法的原理，并熟練運(yùn)用之求解最小樹問題(3)掌握最短有向路方程基本原理，熟練運(yùn)用Dijkstra算法求解最短路問題。(4)掌握最大流問題的基本原理，熟練運(yùn)用Ford-Fulkerson算法求解最大流問題。(5)理解最小費(fèi)用流問題的有關(guān)概念，掌握求最小費(fèi)用流問題和運(yùn)輸問題的對(duì)偶算法。(6)掌握二分圖對(duì)集的基本定理，熟練運(yùn)用求解二分圖的最大基數(shù)對(duì)集和分派問題。作業(yè)第6章習(xí)題1,2,67,9,10,B(3)B(4)思考：結(jié)合教材關(guān)于最小費(fèi)用流、最大權(quán)對(duì)集算法深入理解原-對(duì)偶算法第7章網(wǎng)絡(luò)計(jì)劃技術(shù)基本內(nèi)容網(wǎng)絡(luò)計(jì)劃技術(shù)主要指關(guān)鍵路線法和計(jì)劃評(píng)審技術(shù)，在現(xiàn)代管理中被認(rèn)為是最行之有效的管理方法之一。本章首先介紹網(wǎng)絡(luò)計(jì)劃圖的編制方法，然后給出計(jì)算時(shí)間參數(shù)和關(guān)鍵路線的方法，最后考慮網(wǎng)絡(luò)計(jì)劃中的優(yōu)化問題。重點(diǎn)難點(diǎn)重點(diǎn)：(1)箭線圖的繪制。(2)網(wǎng)絡(luò)圖中時(shí)間參數(shù)的計(jì)算方法和關(guān)鍵路線(3)網(wǎng)絡(luò)圖工期優(yōu)化問題的數(shù)學(xué)規(guī)劃方法難點(diǎn)：網(wǎng)絡(luò)圖中時(shí)間參數(shù)的計(jì)算方法；網(wǎng)絡(luò)圖時(shí)間-資源優(yōu)化問題的求解方法。教學(xué)要求(1)掌握節(jié)點(diǎn)圖和箭線圖的繪制方法(2)掌握網(wǎng)絡(luò)圖中時(shí)間參數(shù)的計(jì)算方法(3)掌握關(guān)鍵路線確定的方法。(4)掌握網(wǎng)絡(luò)圖工期優(yōu)化問題的數(shù)學(xué)規(guī)劃方法。作業(yè)第7章習(xí)題3,B(1)查閱：項(xiàng)目管理第8章排隊(duì)論基本內(nèi)容排隊(duì)論是專門研究由于隨機(jī)因素的影響而產(chǎn)生的擁擠現(xiàn)象的科學(xué)，也稱為隨機(jī)服務(wù)系統(tǒng)理論。它所研究的問題有強(qiáng)烈的實(shí)際背景，其所得的結(jié)果有廣泛的應(yīng)用。本章介紹了排隊(duì)論的基本理論，以及若干類排隊(duì)系統(tǒng)的處理方法。重點(diǎn)難點(diǎn)重點(diǎn)：(1)最簡(jiǎn)單流、生滅過程的基本特征。(2)常見有限源排隊(duì)系統(tǒng)中各項(xiàng)指標(biāo)的推導(dǎo)和計(jì)算。難點(diǎn)：最簡(jiǎn)單流；生滅過程；有限源排隊(duì)系統(tǒng)各項(xiàng)指標(biāo)的推導(dǎo)和計(jì)算。教學(xué)要求(1)熟練掌握最簡(jiǎn)單流合生滅過程的基本特征。(2)熟練掌握常見排隊(duì)系統(tǒng)中各項(xiàng)指標(biāo)的推導(dǎo)和計(jì)算。(3)了解有限源排隊(duì)系統(tǒng)及指標(biāo)。作業(yè)第8章習(xí)題：4,8,9,B(1)(無lingo計(jì)算）查閱：其他形式的排隊(duì)系統(tǒng)第9章決策分析基本內(nèi)容決策分析研究從多種可供選擇的行動(dòng)方案中選擇最優(yōu)化方案的方法。本章主要介紹決策分析的基本概念和基本方法；重點(diǎn)介紹確定型決策分析、風(fēng)險(xiǎn)型決策分析和不確定型決策分析；結(jié)合實(shí)際例子給出各種決策問題的解法并對(duì)各種方法進(jìn)行分析和比較。另外還介紹效用函數(shù)和信息價(jià)值的應(yīng)用。重點(diǎn)難點(diǎn)重點(diǎn)：(1)風(fēng)險(xiǎn)型決策及決策樹求解方法。(2)不確定型決策求解方法。(3)信息價(jià)值的計(jì)算方法。難點(diǎn)：決策樹建立方法；不確定型決策中信息價(jià)值的計(jì)算方法；效用函數(shù)的表示和應(yīng)用。教學(xué)要求(1)了解決策的類