運(yùn)籌學(xué)期末復(fù)習(xí)目錄CONTENCT運(yùn)籌學(xué)概述線性規(guī)劃整數(shù)規(guī)劃動(dòng)態(tài)規(guī)劃圖論與網(wǎng)絡(luò)優(yōu)化決策分析01運(yùn)籌學(xué)概述定義特點(diǎn)定義與特點(diǎn)運(yùn)籌學(xué)是一門(mén)應(yīng)用數(shù)學(xué)學(xué)科，通過(guò)數(shù)學(xué)方法和計(jì)算機(jī)技術(shù)解決實(shí)際優(yōu)化問(wèn)題。運(yùn)籌學(xué)強(qiáng)調(diào)數(shù)學(xué)建模、量化分析和優(yōu)化決策，具有很強(qiáng)的應(yīng)用性和跨學(xué)科性。80%80%100%運(yùn)籌學(xué)的重要性運(yùn)籌學(xué)在生產(chǎn)、管理、交通、物流等領(lǐng)域有廣泛應(yīng)用，能夠提高效率和降低成本。運(yùn)籌學(xué)為決策者提供科學(xué)依據(jù)，幫助其做出更合理、更有效的決策。運(yùn)籌學(xué)的發(fā)展推動(dòng)相關(guān)領(lǐng)域的技術(shù)創(chuàng)新和管理變革，促進(jìn)社會(huì)進(jìn)步。實(shí)際應(yīng)用決策支持創(chuàng)新發(fā)展起源發(fā)展現(xiàn)狀運(yùn)籌學(xué)的發(fā)展歷程隨著計(jì)算機(jī)技術(shù)的進(jìn)步，運(yùn)籌學(xué)在20世紀(jì)50年代得到迅速發(fā)展。現(xiàn)代運(yùn)籌學(xué)已經(jīng)滲透到各個(gè)領(lǐng)域，成為解決實(shí)際問(wèn)題的重要工具。運(yùn)籌學(xué)起源于二戰(zhàn)時(shí)期的軍事戰(zhàn)略和資源優(yōu)化問(wèn)題。02線性規(guī)劃線性規(guī)劃是運(yùn)籌學(xué)中一種求解最優(yōu)化問(wèn)題的數(shù)學(xué)方法，其目標(biāo)是在一系列線性不等式約束下，最大化或最小化一個(gè)線性目標(biāo)函數(shù)。定義線性規(guī)劃模型由決策變量、目標(biāo)函數(shù)和約束條件三部分組成。決策變量是問(wèn)題中需要求解的未知數(shù)；目標(biāo)函數(shù)是要求最大或最小的函數(shù)；約束條件是一組限制決策變量取值的線性不等式或等式。模型線性規(guī)劃的定義與模型單純形法單純形法是線性規(guī)劃中最常用的一種求解方法，通過(guò)不斷迭代和轉(zhuǎn)換，將問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式并找到最優(yōu)解。對(duì)偶算法對(duì)偶算法是利用線性規(guī)劃的對(duì)偶性來(lái)求解問(wèn)題的一種方法，通過(guò)對(duì)原問(wèn)題進(jìn)行轉(zhuǎn)換，可以簡(jiǎn)化問(wèn)題并提高求解效率。內(nèi)點(diǎn)法內(nèi)點(diǎn)法是一種基于迭代思想的求解方法，通過(guò)迭代計(jì)算逐步逼近最優(yōu)解。線性規(guī)劃的求解方法物流與運(yùn)輸線性規(guī)劃在物流和運(yùn)輸領(lǐng)域中有著廣泛應(yīng)用，如車(chē)輛路徑規(guī)劃、貨物配載等問(wèn)題都可以通過(guò)線性規(guī)劃進(jìn)行優(yōu)化。金融投資組合金融投資組合優(yōu)化問(wèn)題也可以通過(guò)線性規(guī)劃進(jìn)行求解，以實(shí)現(xiàn)投資收益的最大化或風(fēng)險(xiǎn)的最小化。生產(chǎn)計(jì)劃優(yōu)化線性規(guī)劃可以用于生產(chǎn)計(jì)劃優(yōu)化，通過(guò)合理安排生產(chǎn)任務(wù)和資源分配，降低生產(chǎn)成本并提高生產(chǎn)效率。線性規(guī)劃的應(yīng)用場(chǎng)景03整數(shù)規(guī)劃整數(shù)規(guī)劃的定義與模型定義整數(shù)規(guī)劃是線性規(guī)劃的一種特殊形式，要求決策變量取整數(shù)值。模型整數(shù)規(guī)劃的數(shù)學(xué)模型由目標(biāo)函數(shù)和約束條件組成，目標(biāo)函數(shù)通常是最小化或最大化一個(gè)線性函數(shù)，約束條件可以是等式或不等式，要求決策變量取整數(shù)值。整數(shù)規(guī)劃的求解方法分支定界法是一種常用的求解整數(shù)規(guī)劃的方法，通過(guò)不斷將問(wèn)題分解為更小的子問(wèn)題，并確定子問(wèn)題的最優(yōu)解，最終得到原問(wèn)題的最優(yōu)解。割平面法割平面法也是一種求解整數(shù)規(guī)劃的方法，通過(guò)添加割平面方程來(lái)限制決策變量的取值范圍，從而得到整數(shù)最優(yōu)解。回溯法回溯法是一種基于搜索的求解整數(shù)規(guī)劃的方法，通過(guò)深度優(yōu)先搜索或廣度優(yōu)先搜索來(lái)尋找所有可能的整數(shù)解，并從中選擇最優(yōu)解。分支定界法物流優(yōu)化整數(shù)規(guī)劃可以用于物流優(yōu)化問(wèn)題，如車(chē)輛路徑問(wèn)題、貨物配載問(wèn)題等，通過(guò)優(yōu)化運(yùn)輸和配送過(guò)程，降低物流成本。資源分配整數(shù)規(guī)劃可以用于資源分配問(wèn)題，如任務(wù)調(diào)度、人員排班等，通過(guò)合理分配資源，提高工作效率。生產(chǎn)計(jì)劃整數(shù)規(guī)劃可以用于生產(chǎn)計(jì)劃問(wèn)題，通過(guò)優(yōu)化生產(chǎn)過(guò)程，提高生產(chǎn)效率、降低成本。整數(shù)規(guī)劃的應(yīng)用場(chǎng)景04動(dòng)態(tài)規(guī)劃定義動(dòng)態(tài)規(guī)劃是一種通過(guò)將原問(wèn)題分解為若干個(gè)子問(wèn)題，并從子問(wèn)題的最優(yōu)解逐步構(gòu)造出原問(wèn)題的最優(yōu)解的方法。模型動(dòng)態(tài)規(guī)劃問(wèn)題通常由狀態(tài)轉(zhuǎn)移方程、狀態(tài)轉(zhuǎn)移矩陣和目標(biāo)函數(shù)組成，其中狀態(tài)轉(zhuǎn)移方程描述了狀態(tài)之間的轉(zhuǎn)移關(guān)系，狀態(tài)轉(zhuǎn)移矩陣表示了狀態(tài)之間的轉(zhuǎn)移概率，而目標(biāo)函數(shù)則是需要優(yōu)化的性能指標(biāo)。動(dòng)態(tài)規(guī)劃的定義與模型自底向上求解從子問(wèn)題的最優(yōu)解開(kāi)始，逐步求解更大規(guī)模的子問(wèn)題，最終得到原問(wèn)題的最優(yōu)解。這種方法需要預(yù)先計(jì)算所有子問(wèn)題的最優(yōu)解并存儲(chǔ)起來(lái)，以便后續(xù)使用。自頂向下求解從原問(wèn)題開(kāi)始，逐步將問(wèn)題分解為更小的子問(wèn)題，并在求解子問(wèn)題的過(guò)程中記錄最優(yōu)解。這種方法需要在每一步都進(jìn)行最優(yōu)解的判斷和選擇，因此需要更多的計(jì)算和存儲(chǔ)資源。迭代法求解通過(guò)迭代的方式不斷逼近最優(yōu)解，每次迭代中根據(jù)當(dāng)前最優(yōu)解和狀態(tài)轉(zhuǎn)移方程更新?tīng)顟B(tài)，直到達(dá)到終止條件。這種方法需要設(shè)計(jì)合適的迭代算法和終止條件。動(dòng)態(tài)規(guī)劃的求解方法最短路徑問(wèn)題如旅行商問(wèn)題、車(chē)輛路徑問(wèn)題等，通過(guò)動(dòng)態(tài)規(guī)劃可以找到從起點(diǎn)到終點(diǎn)的最短路徑。資源分配問(wèn)題如背包問(wèn)題、任務(wù)調(diào)度問(wèn)題等，通過(guò)動(dòng)態(tài)規(guī)劃可以?xún)?yōu)化資源分配，使得目標(biāo)函數(shù)達(dá)到最優(yōu)。決策優(yōu)化問(wèn)題如排班問(wèn)題、生產(chǎn)計(jì)劃問(wèn)題等，通過(guò)動(dòng)態(tài)規(guī)劃可以確定最優(yōu)的決策序列。動(dòng)態(tài)規(guī)劃的應(yīng)用場(chǎng)景03020105圖論與網(wǎng)絡(luò)優(yōu)化01020304圖路徑連通性歐拉路徑和歐拉回路圖論的基本概念圖中的兩個(gè)節(jié)點(diǎn)之間是否存在路徑。圖中的一系列節(jié)點(diǎn)，表示從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的移動(dòng)。由節(jié)點(diǎn)和邊構(gòu)成的數(shù)據(jù)結(jié)構(gòu)，用于表示事物之間的相互關(guān)系。路徑的起點(diǎn)和終點(diǎn)是同一點(diǎn)，且路徑上所有邊都不重復(fù)。0102030405最短路徑問(wèn)題尋找圖中兩個(gè)節(jié)點(diǎn)之間的最短路徑。最小生成樹(shù)問(wèn)題在連通圖中選擇一些邊，使得這些邊構(gòu)成的子圖包含所有節(jié)點(diǎn)且無(wú)環(huán)，且總權(quán)重最小。旅行商問(wèn)題給定一系列城市和每對(duì)城市之間的距離，求最短的可能路線，使得每個(gè)城市恰好經(jīng)過(guò)一次并回到原點(diǎn)。最大流問(wèn)題在有向圖中尋找最大的流，使得從源點(diǎn)到匯點(diǎn)的總流量最大。最小割問(wèn)題在有向圖中尋找最小的割，使得從源點(diǎn)所在的連通分量到匯點(diǎn)所在的連通分量的總權(quán)重最小。網(wǎng)絡(luò)優(yōu)化問(wèn)題的類(lèi)型與求解方法交通規(guī)劃如最短路徑問(wèn)題用于計(jì)算最佳路線，最小生成樹(shù)問(wèn)題用于構(gòu)建道路網(wǎng)絡(luò)。物流配送如旅行商問(wèn)題用于規(guī)劃最佳配送路線，最大流問(wèn)題用于優(yōu)化物流運(yùn)輸。社交網(wǎng)絡(luò)分析如最小割問(wèn)題用于識(shí)別社交網(wǎng)絡(luò)中的核心群體和邊緣群體。網(wǎng)絡(luò)優(yōu)化問(wèn)題的應(yīng)用場(chǎng)景06決策分析VS決策分析是運(yùn)籌學(xué)的一個(gè)重要分支，它研究在不確定或風(fēng)險(xiǎn)情況下如何做出最優(yōu)選擇。決策分析涉及的要素包括決策者、決策目標(biāo)、決策方案、自然狀態(tài)和決策準(zhǔn)則。基本模型決策分析的基本模型包括風(fēng)險(xiǎn)型決策、不確定型決策和風(fēng)險(xiǎn)偏好型決策。風(fēng)險(xiǎn)型決策考慮了自然狀態(tài)發(fā)生的概率，不確定型決策則沒(méi)有給出概率信息，而風(fēng)險(xiǎn)偏好型決策則考慮了決策者的風(fēng)險(xiǎn)偏好。基本概念決策分析的基本概念與模型期望值法期望損益值法最大可能法效用函數(shù)法決策分析的求解方法通過(guò)計(jì)算每個(gè)方案在不同自然狀態(tài)下的預(yù)期收益，選擇期望值最大的方案。與期望值法類(lèi)似，但考慮了收益和損失，用于更全面地評(píng)估方案的風(fēng)險(xiǎn)和收益。在沒(méi)有概率信息的情況下，選擇最有可能帶來(lái)最好結(jié)果的方案。根據(jù)決策者的風(fēng)險(xiǎn)偏好，通過(guò)效用函數(shù)將收益轉(zhuǎn)化為效用值，再選擇效用值最大的方案。在股票、基金等投資中，投資者需要根據(jù)市場(chǎng)情況和自身風(fēng)險(xiǎn)承受能力進(jìn)行最優(yōu)投資決策。金融投資生產(chǎn)計(jì)劃物流與供應(yīng)鏈管理醫(yī)療決策