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

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

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

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

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

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

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

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

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

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

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

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

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

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