運籌學(xué)課程總結(jié)

1、xxxx運 籌 學(xué) 課姓名：xxx學(xué)號：xxxxxx班級：xxxxxxxxx古人云 “運籌帷幄之中， 決勝千里之外”運籌學(xué)是 20 世紀(jì)三四十年代發(fā)展起來的一門新興交叉學(xué)科， 它主要研究人類對各種資源的運用及籌劃活動， 以期通過了解和發(fā)展這種運用及籌劃活動的基本規(guī)律， 發(fā)揮有限資源的最大效益， 達(dá)到總體最優(yōu)的目標(biāo)。經(jīng)過這一個學(xué)期的學(xué)習(xí)， 我們應(yīng)該熟練地掌握、 運用運籌學(xué)的精髓， 用運籌學(xué)的思維思考問題，即：應(yīng)用分析、試驗、量化的方法，對實際生活中的人力、財力、 物力等有限資源進(jìn)行合理的統(tǒng)籌安排。 本著這樣的心態(tài)， 在本學(xué)期運籌學(xué)課程將結(jié)束之際，我對本學(xué)期所學(xué)知識作出如下總結(jié)。一、線性規(guī)劃線性規(guī)

2、劃解決的是： 在資源有限的條件下， 為達(dá)到預(yù)期目標(biāo)最優(yōu)， 而尋找資源消耗最少的方案。而線性規(guī)劃問題指的是在一組線性等式或不等式的約束下，求解一個線性函數(shù)的最大或最小值的問題。 其數(shù)學(xué)模型有目標(biāo)函數(shù)和約束條件組成。解決線性規(guī)劃問題的關(guān)鍵是找出他的目標(biāo)函數(shù)和約束方程， 并將它們轉(zhuǎn)化為標(biāo)準(zhǔn)形式。 目前解決線性規(guī)劃問題的主要方法有： 圖解法、 單純型法、 兩階段法、對偶單純型法等方法。自 1939 年蘇聯(lián)數(shù)學(xué)家康托羅維奇提出線性規(guī)劃問題和1947年美國數(shù)學(xué)家丹齊格求解線性規(guī)劃問題的通用方法單純形法以來，線性規(guī)劃可以說是研究得最為透徹的一個研究方向。 單純形法統(tǒng)治線性規(guī)劃領(lǐng)域達(dá)40 年之久，而且至今仍是

3、最好的應(yīng)用最廣泛的算法之一。簡單的設(shè)計2 個變量的線性規(guī)劃問題可以直接運用圖解法得到。 但是往往在現(xiàn)實生活中， 線性規(guī)劃問題涉及到的變量很多， 很難用作圖法實現(xiàn)， 但是運用單純形法記比較方便。 在運用單純形法時，需要先將問題化為標(biāo)準(zhǔn)形式，求出基可行解，列出單純形表，進(jìn)行單純形迭代， 當(dāng)所有的變量檢驗數(shù)不大于零， 且基變量中不含人工變量， 計算結(jié)束。將所得的量的值代入目標(biāo)函數(shù)，得出最優(yōu)值。線性規(guī)劃是這門課程第一章的教學(xué)內(nèi)容， 作為運籌學(xué)的基礎(chǔ)學(xué)習(xí)， 因此對于這個知識點的學(xué)習(xí)還是比較認(rèn)真的。初步學(xué)會如何從實際問題中提煉數(shù)學(xué)模型，以及解答， 理解了單純形法的思想并會運用單純形法解答線性方程組， 但是

4、在學(xué)習(xí)過程中一些定理比較難以理解。 對此， 需要在課后好好復(fù)習(xí)， 認(rèn)真消化課程內(nèi)容，才能真正理解，熟練應(yīng)用。二、整數(shù)規(guī)劃整數(shù)規(guī)劃是解決決策變量只能取整數(shù)的規(guī)劃問題， 一個規(guī)劃問題中要求部分或全部決策變量是整數(shù)， 則這個規(guī)劃稱為整數(shù)規(guī)劃； 當(dāng)要求全部變量取整數(shù)值的，稱為純整數(shù)規(guī)劃；只要求一部分變量取整數(shù)值的，稱為混合整數(shù)規(guī)劃。很多實際規(guī)劃問題都屬于整數(shù)規(guī)劃問題。例如 1. 變量是人數(shù)、機(jī)器設(shè)備臺數(shù)或產(chǎn)品件數(shù)等都要求是整數(shù)。 2. 人員的合理安排問題，當(dāng)變量xij =1 表示安排第 i 人去做 j 工作，xij =0 表示不安排第 i 人去做 j 工作。整數(shù)規(guī)劃的解法有割平面法和分支定界法。 其中

5、分枝定界法的思路是： 首先，不考慮解為整數(shù)的要求， 用單純法求最優(yōu)解， 以此作為目標(biāo)函數(shù)值的上限或下限；其次， 選擇其中一個非整數(shù)的變量， 根據(jù)與兩側(cè)相近的整數(shù)劃分可行域， 在縮小的可行域 （ 子域 ） 內(nèi)尋求最優(yōu)整數(shù)解，以此作為目標(biāo)函數(shù)值的上限或下限；最后，不斷重復(fù)以上過程，直到每一個可能進(jìn)一步分解的非整數(shù)都找到整數(shù)解時為止。具體步驟：1. 求整數(shù)規(guī)劃的松弛問題最優(yōu)解；2. 若松弛問題的最優(yōu)解滿足整數(shù)要求， 得到整數(shù)規(guī)劃的最優(yōu)解， 否則轉(zhuǎn)下一步；3. 任意選一個非整數(shù)解的變量xi ,在松弛問題中加上約束xi < xi及xixi+1 組成兩個新的松弛問題，稱為分枝。新的松弛問題具有特征：

6、當(dāng)原問題是求最大值時， 目標(biāo)值是分枝問題的上界； 當(dāng)原問題是求最小值時， 目標(biāo)值是分枝問題的下界；4. 檢查所有分枝的解及目標(biāo)函數(shù)值， 若某分枝的解是整數(shù)并且目標(biāo)函數(shù)值大于（ max） 等于其它分枝的目標(biāo)值， 則將其它分枝剪去不再計算, 若還存在非整數(shù)解并且目標(biāo)值大于（ma%整數(shù)解的目標(biāo)值，需要繼續(xù)分枝，再檢查，直到得到最優(yōu)解。整數(shù)規(guī)劃中決策變量全部取0 或 1 的規(guī)劃稱為 0 1 整數(shù)規(guī)劃。在實際問題中，該方法能夠解決很多問題，例如，對某一個項目要不要投資的決策問題，可選用一個邏輯變量x ，當(dāng) x=1 表示投資， x=0 表，示不投資。此外指派問題就是0-1能糊劃嘴闋廠個特例。&1（

7、第數(shù)嶗的解2f法有枚舉法和隱枚舉法。完全枚舉法是將每個變量都只取0 或 1 兩個值， 變量可能取值的 0-1 組合是有限的，并且個數(shù)為2n。然后列出各變量分別取0或1的每種組合，然后在滿足約束條件變量的 0-1 組合中找出使目標(biāo)函數(shù)達(dá)到最優(yōu)值的組合即是該0-1 規(guī)劃的最優(yōu)解。 用這種方法求解變量個數(shù)為 n 的 0-1 規(guī)劃， 通常需要檢查2n 個組合。計算量大，隨變量數(shù)量的增加呈幾何級數(shù)增長。隱枚舉法的步驟：1. 找出任意一可行解，目標(biāo)函數(shù)值為z0。2. 原問題求最大值時，則增加一個約束（過濾條件）當(dāng)求最小值時，上式改為小于等于約束3. 列出所有可能解，對每個可能解先檢驗式（ * ） ，若滿足

8、再檢驗其它約束，若不滿足式（ * ） ，則認(rèn)為不可行，若所有約束都滿足，則認(rèn)為此解是可行解，求出目標(biāo)值4. 目標(biāo)函數(shù)值最大（最小）的解就是最優(yōu)解通過本章學(xué)習(xí)，認(rèn)識并理解了線性整數(shù)規(guī)劃模型的特征，明白純整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、 0 1 整數(shù)規(guī)劃之間的區(qū)別，學(xué)會如何從實際問題中提煉出合理的數(shù)學(xué)模型。 此外理解了分枝定界的思想含義并掌握分枝定界的方法， 知道如何選擇合適的“ 枝”生“ 枝” ，掌握何時停止生“ 枝” 。三、運輸與指派問題人們在從事生產(chǎn)活動中， 不可避免地要進(jìn)行物資調(diào)運工作。 如某時期內(nèi)將生產(chǎn)基地的煤、鋼鐵、糧食等各類物資，分別運到需要這些物資的地區(qū)，根據(jù)各地的生產(chǎn)量和需要量及各地之間

9、的運輸費用， 如何制定一個運輸方案， 使總的運輸費用最小。這樣的問題稱為運輸問題。運輸單純形法也稱為表上作業(yè)法， 是直接在產(chǎn)銷平衡運價表上求最優(yōu)解的一種方法。它的步驟是：首先確定一個初始調(diào)運方案，主要方法有最小元素法、元素差額法、 左上角法； 然后通過非基變量的檢驗數(shù)檢驗是否為最優(yōu)方案， 不是就調(diào)整運量， 直到選出最優(yōu)方案停止， 求檢驗數(shù)的常用方法有兩種， 閉回路法和位勢法。指派問題也稱分配或配置問題， 是資源合理配置或最優(yōu)匹配問題。 例如， 假設(shè)m個人恰好做m項工作，第i個人做第j項工作，如何分配工作使效率最佳。解指派問題的有效方法是匈牙利算法， 但是匈牙利法要一定的條件條件： 問題求最小值

10、、人數(shù)與工作數(shù)相等、效率非負(fù)。運輸與指問題實質(zhì)就是整數(shù)規(guī)劃中的特例。 在這一章中我主要學(xué)習(xí)到了對整數(shù)規(guī)劃中的特例方便解決的方法， 運輸單純形法和匈牙利法， 掌握如何求初始運輸方案、求檢驗數(shù)、整運量，理解檢驗數(shù)的經(jīng)濟(jì)意義。在運輸問題中學(xué)會延伸，對于不平衡運輸問題學(xué)會轉(zhuǎn)化為平衡問題， 極大值問題轉(zhuǎn)化為極小值問題。 對于指派問題掌握匈牙利法的步驟， 了解他的使用條件， 此外掌握解決指派問題的其它變異問題的方法， 如最大化指派問題、 人數(shù)和工作數(shù)不等的指派問題、 一個人可做幾項工作的指派問題、某項工作一定不能由某人做的指派問題。四、網(wǎng)絡(luò)模型圖論是交通系統(tǒng)分析中的重要工具， 在交通系統(tǒng)規(guī)劃、 管理中作用

11、巨大， 也是對實際交通網(wǎng)絡(luò)進(jìn)行抽象分析的重要手段。 在網(wǎng)絡(luò)模型這一章中我們主要學(xué)習(xí)了圖論有關(guān)知識， 學(xué)習(xí)了如何利用圖來解決最小數(shù)問題、 最短有向路問題、 最大流問題與最小費用流問題。一個無圈并且連通的無向圖稱為樹圖或簡稱樹， 將網(wǎng)絡(luò)圖邊上的權(quán)看作兩點間的長度（距離、費用、時間） , 定義圖的部分樹的長度等于其中每條邊的長度之和， 則圖中所有部分樹中長度最小的部分樹稱為最小部分樹。 最小部分樹可以直接用作圖的方法求解。常用的有破圈法和加邊法（避圈法） 。最短路問題， 就是從給定的網(wǎng)絡(luò)圖中找出一點到各點或任意兩點之間距離最短的一條路。 最短路問題是重要的優(yōu)化問題之一， 在實際中具有廣泛的應(yīng)用， 如

12、管道鋪設(shè)、線路選擇等問題，設(shè)備更新、投資等。最短路問題可以作為解決其它優(yōu)化問題的一種基本工具。 常見的求最短路的兩種算法有狄克斯屈拉（dijkstra）標(biāo)號算法和 floyd（ 弗洛伊德 ） 矩陣算法。標(biāo)號算法是求兩個固定點之間的最短路，矩陣算法則可以求任意點之間的最短路。最大流問題的應(yīng)用十分廣泛， 例如使交通網(wǎng)絡(luò)的道路通行能力 （車流量） 最大、 使溝渠系統(tǒng)的水流量最大、 使石油管道系統(tǒng)的石油流量最大等等， 解決最大流問題的方法有ford-fulkerson 標(biāo)號算法，其中關(guān)鍵是找尋找增廣鏈，當(dāng)且僅當(dāng)不存在增廣鏈時，可行流為最大流。在這章的學(xué)習(xí)中， 我們將生活中的實際問題化成簡單的圖， 利用

13、圖的方法進(jìn)行求解， 找出合理方案， 例如利用最大流解決最大匹配問題和勞動力合理配置問題。 本章節(jié)還有兩個經(jīng)典問題旅行售貨員問題和中國郵遞員問題， 經(jīng)過本章的學(xué)習(xí)，我體會到了數(shù)學(xué)的神奇與強大應(yīng)用性。五、網(wǎng)絡(luò)計劃網(wǎng)絡(luò)計劃即網(wǎng)絡(luò)計劃技術(shù)，是指用于工程項目的計劃與控制的一項管理技術(shù)，一般項目管理中應(yīng)用較多。它主要包括計劃協(xié)調(diào)技術(shù)（pert與關(guān)鍵路線法（cpm組成。pertfc要針對完成工作的時間不能確定而是一個隨機(jī)變量時的計劃編制方法，活動的完成時間通常用三點估計法，注重計劃的評價和審查。 cpm以經(jīng)驗數(shù)據(jù)確定工作時間， 工作時間是確定的數(shù)值， 主要研究項目的費用與工期的相互關(guān)系。兩種方法融為一體，統(tǒng)稱為網(wǎng)絡(luò)計劃、網(wǎng)絡(luò)計劃技術(shù)。網(wǎng)絡(luò)計劃工作過程就是先編制項目工序， 然后根據(jù)工序繪制網(wǎng)絡(luò)圖， 通常分為： 箭線網(wǎng)絡(luò)圖和節(jié)點網(wǎng)絡(luò)圖， 接著通過對網(wǎng)絡(luò)時間參數(shù)計算找出關(guān)鍵路線， 主要方法有枚舉法、 0-1 規(guī)劃模型和關(guān)鍵工序法，最后計劃時間進(jìn)行網(wǎng)絡(luò)優(yōu)化。在本章節(jié)中，我們主要學(xué)習(xí)了如何利用圖來解決生產(chǎn)生活中的人力、物力、財力等資源以及工作時間限制下的生產(chǎn)加工流程的統(tǒng)籌規(guī)劃。 通過做網(wǎng)絡(luò)圖， 我們可以清晰地求解出每個問題的