《暨南大學(xué)運(yùn)籌學(xué)》課件

暨南大學(xué)運(yùn)籌學(xué)課程簡(jiǎn)介目標(biāo)本課程旨在幫助學(xué)生掌握運(yùn)籌學(xué)的基本理論和方法，并能夠運(yùn)用這些方法解決實(shí)際問(wèn)題。內(nèi)容課程內(nèi)容涵蓋線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃、運(yùn)輸問(wèn)題、指派問(wèn)題、決策論、博弈論等。什么是運(yùn)籌學(xué)？?jī)?yōu)化決策運(yùn)籌學(xué)通過(guò)數(shù)學(xué)模型和算法來(lái)尋找最佳決策方案。資源分配運(yùn)籌學(xué)幫助企業(yè)有效地分配有限的資源，以最大化效益。運(yùn)籌學(xué)的歷史1古代起源運(yùn)籌學(xué)起源于古代，人們?cè)缇烷_始運(yùn)用數(shù)學(xué)方法來(lái)解決資源分配和決策問(wèn)題。2近代發(fā)展在二戰(zhàn)期間，運(yùn)籌學(xué)得到了快速發(fā)展，用于優(yōu)化軍事行動(dòng)和資源分配。3現(xiàn)代應(yīng)用如今，運(yùn)籌學(xué)廣泛應(yīng)用于各個(gè)領(lǐng)域，例如生產(chǎn)管理、金融投資、物流運(yùn)輸?shù)?。運(yùn)籌學(xué)的分類1線性規(guī)劃處理線性約束條件下的優(yōu)化問(wèn)題。2非線性規(guī)劃處理非線性約束條件下的優(yōu)化問(wèn)題。3整數(shù)規(guī)劃變量取值為整數(shù)的優(yōu)化問(wèn)題。4動(dòng)態(tài)規(guī)劃將復(fù)雜問(wèn)題分解成一系列簡(jiǎn)單的子問(wèn)題，逐個(gè)解決。線性規(guī)劃線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，它研究如何在有限資源的約束下，優(yōu)化目標(biāo)函數(shù)，從而找到最優(yōu)的方案。線性規(guī)劃在現(xiàn)實(shí)生活中有著廣泛的應(yīng)用，例如：生產(chǎn)計(jì)劃、運(yùn)輸規(guī)劃、投資決策等等。線性規(guī)劃的基本概念線性規(guī)劃是運(yùn)籌學(xué)中的一種重要方法，用于在一定約束條件下，對(duì)線性目標(biāo)函數(shù)進(jìn)行優(yōu)化，以求得最優(yōu)解。線性規(guī)劃中的目標(biāo)函數(shù)和約束條件都是線性的，這意味著變量之間是線性關(guān)系。線性規(guī)劃的目標(biāo)是找到使目標(biāo)函數(shù)達(dá)到最大值或最小值的變量取值。線性規(guī)劃的幾何解法線性規(guī)劃的幾何解法是指通過(guò)圖形的方式來(lái)求解線性規(guī)劃問(wèn)題。這種方法適用于變量數(shù)量較少(通常是兩個(gè)變量)的線性規(guī)劃問(wèn)題。首先，需要將線性規(guī)劃問(wèn)題的約束條件轉(zhuǎn)化為直線方程。然后，將這些直線方程畫在二維坐標(biāo)系中，并找出可行域?？尚杏蚴侵笣M足所有約束條件的區(qū)域。最后，目標(biāo)函數(shù)的等值線在可行域內(nèi)移動(dòng)，找到目標(biāo)函數(shù)取最大值或最小值的點(diǎn)，即為線性規(guī)劃問(wèn)題的最優(yōu)解。線性規(guī)劃的圖形解法圖形解法是一種直觀、簡(jiǎn)單的方法，適用于二維或三維空間中的線性規(guī)劃問(wèn)題。通過(guò)繪制約束條件所形成的可行域，并找到目標(biāo)函數(shù)在可行域上的最大值或最小值點(diǎn)，即可求解線性規(guī)劃問(wèn)題。單純形法1最優(yōu)解找到最優(yōu)解，滿足約束條件并最大化目標(biāo)函數(shù)2可行解滿足約束條件的解3基本可行解可行解，對(duì)應(yīng)于線性規(guī)劃問(wèn)題的頂點(diǎn)單純形法的步驟1建立初始單純形表將線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式，并建立初始單純形表，其中包含目標(biāo)函數(shù)系數(shù)、約束條件系數(shù)和初始基變量值。2選擇入基變量在非基變量中，選擇目標(biāo)函數(shù)系數(shù)最小的變量作為入基變量，即進(jìn)入基變量。3選擇出基變量根據(jù)約束條件，選擇系數(shù)為正且比值最小的基變量作為出基變量，即離開基變量。4更新單純形表利用入基變量和出基變量，對(duì)單純形表進(jìn)行更新，得到新的單純形表。5判斷最優(yōu)解檢查目標(biāo)函數(shù)系數(shù)是否全部為非負(fù)數(shù)，如果是，則當(dāng)前解為最優(yōu)解；否則，重復(fù)步驟2-4，直到找到最優(yōu)解。單純形法案例分析資源分配公司需要分配有限的資源，如人力、設(shè)備和資金，以最大限度地提高利潤(rùn)或生產(chǎn)效率。生產(chǎn)計(jì)劃決定生產(chǎn)多少種產(chǎn)品，以滿足客戶需求，并同時(shí)保持成本效益。投資組合優(yōu)化投資組合管理，旨在最大限度地提高收益并最小化風(fēng)險(xiǎn)，在不同的投資選擇之間進(jìn)行分配。對(duì)偶理論原始問(wèn)題對(duì)偶理論的核心在于將原始線性規(guī)劃問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題，并利用對(duì)偶問(wèn)題求解原始問(wèn)題。對(duì)偶問(wèn)題對(duì)偶問(wèn)題與原始問(wèn)題有著密切的聯(lián)系，其最優(yōu)解可以用來(lái)推斷原始問(wèn)題的最優(yōu)解。對(duì)偶關(guān)系對(duì)偶理論揭示了原始問(wèn)題和對(duì)偶問(wèn)題之間的關(guān)系，以及最優(yōu)解之間的聯(lián)系。對(duì)偶問(wèn)題的解決對(duì)偶問(wèn)題的轉(zhuǎn)化將原始問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題。單純形法求解利用單純形法求解對(duì)偶問(wèn)題的最優(yōu)解。對(duì)偶解的解釋解釋對(duì)偶解的含義，并將其與原始問(wèn)題的解聯(lián)系起來(lái)。靈敏度分析目標(biāo)函數(shù)系數(shù)的變化分析目標(biāo)函數(shù)系數(shù)的變化對(duì)最優(yōu)解的影響，例如，產(chǎn)品售價(jià)的變化對(duì)利潤(rùn)的影響。約束條件的變化分析約束條件的變化對(duì)最優(yōu)解的影響，例如，原材料供應(yīng)量的變化對(duì)生產(chǎn)計(jì)劃的影響。參數(shù)的范圍確定參數(shù)變化的范圍，以確保分析結(jié)果的可靠性。運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題是運(yùn)籌學(xué)中一個(gè)重要的模型，用于解決貨物從多個(gè)供貨點(diǎn)到多個(gè)需求點(diǎn)的最佳運(yùn)輸方案。運(yùn)輸問(wèn)題通?？梢赞D(zhuǎn)化為線性規(guī)劃問(wèn)題，并使用單純形法等方法求解。指派問(wèn)題指派問(wèn)題是指將一組任務(wù)分配給一組人員，使得總成本最小化或總效率最大化的問(wèn)題。指派問(wèn)題通常用矩陣表示，其中行代表人員，列代表任務(wù)，矩陣元素表示人員完成該任務(wù)的成本或效率。指派問(wèn)題可以用匈牙利算法等方法解決。決策論決策論是運(yùn)籌學(xué)的一個(gè)分支，它研究在不確定條件下如何做出最佳決策。決策論的目標(biāo)是幫助人們?cè)诿鎸?duì)各種選擇時(shí)，做出最優(yōu)選擇。決策環(huán)境決策環(huán)境包括決策者面臨的各種因素，如目標(biāo)、選擇、結(jié)果和不確定性。決策模型決策模型是對(duì)決策問(wèn)題的簡(jiǎn)化描述，它可以幫助決策者分析問(wèn)題，做出合理的決策。決策樹決策樹是一種用于解決決策問(wèn)題的圖形化工具。它將決策問(wèn)題分解成一系列步驟，每個(gè)步驟都代表一個(gè)可能的決策或事件。每個(gè)節(jié)點(diǎn)代表一個(gè)決策點(diǎn)或事件，分支代表可能的決策或事件的結(jié)果。決策樹的構(gòu)建過(guò)程通常涉及以下步驟：定義問(wèn)題確定可能的決策評(píng)估每個(gè)決策的可能結(jié)果根據(jù)結(jié)果的概率和價(jià)值，選擇最佳決策效用理論主觀價(jià)值效用理論將決策者對(duì)結(jié)果的偏好量化為效用值，反映主觀價(jià)值而非客觀價(jià)值。風(fēng)險(xiǎn)偏好不同決策者對(duì)風(fēng)險(xiǎn)的接受程度不同，效用函數(shù)可以反映風(fēng)險(xiǎn)厭惡、風(fēng)險(xiǎn)中立或風(fēng)險(xiǎn)偏愛(ài)。決策分析通過(guò)效用函數(shù)，決策者可以比較不同方案的預(yù)期效用，選擇最優(yōu)方案。馬爾可夫決策過(guò)程狀態(tài)轉(zhuǎn)移決策過(guò)程中的每個(gè)狀態(tài)都與下一個(gè)狀態(tài)相關(guān)聯(lián)，形成一個(gè)狀態(tài)轉(zhuǎn)移鏈。獎(jiǎng)勵(lì)函數(shù)根據(jù)決策選擇，每個(gè)狀態(tài)轉(zhuǎn)移都會(huì)帶來(lái)相應(yīng)的獎(jiǎng)勵(lì)或懲罰。策略在每個(gè)狀態(tài)下選擇最佳行動(dòng)的規(guī)則，以最大化長(zhǎng)期獎(jiǎng)勵(lì)。非線性規(guī)劃非線性規(guī)劃是指目標(biāo)函數(shù)或約束條件中至少有一個(gè)是非線性的優(yōu)化問(wèn)題。目標(biāo)函數(shù)目標(biāo)函數(shù)可以是凸函數(shù)、凹函數(shù)或其他類型的非線性函數(shù)。約束條件約束條件可以是非線性不等式、等式或其他類型的非線性條件。非線性規(guī)劃的分類1無(wú)約束非線性規(guī)劃目標(biāo)函數(shù)和約束條件均為非線性函數(shù)。2約束非線性規(guī)劃目標(biāo)函數(shù)或約束條件中至少有一個(gè)非線性函數(shù)。3凸規(guī)劃目標(biāo)函數(shù)和約束條件均為凸函數(shù)。4非凸規(guī)劃目標(biāo)函數(shù)或約束條件中至少有一個(gè)非凸函數(shù)。求解非線性規(guī)劃的方法1梯度下降法從一個(gè)初始點(diǎn)開始，沿著目標(biāo)函數(shù)梯度的反方向迭代下降，直到找到最優(yōu)解。2牛頓法利用目標(biāo)函數(shù)的海森矩陣和梯度信息，構(gòu)建一個(gè)二次函數(shù)來(lái)近似目標(biāo)函數(shù)，并求解該二次函數(shù)的最優(yōu)解。3罰函數(shù)法將約束條件轉(zhuǎn)化為罰函數(shù)，并加入到目標(biāo)函數(shù)中，通過(guò)求解無(wú)約束優(yōu)化問(wèn)題來(lái)求解非線性規(guī)劃問(wèn)題。4內(nèi)點(diǎn)法從可行域的內(nèi)部點(diǎn)開始，沿著一個(gè)可行方向迭代，直到找到最優(yōu)解。整數(shù)規(guī)劃整數(shù)規(guī)劃是運(yùn)籌學(xué)中的一類重要問(wèn)題，其決策變量必須取整數(shù)值。生產(chǎn)計(jì)劃生產(chǎn)多少件產(chǎn)品才能使利潤(rùn)最大化，同時(shí)又要滿足原材料、人力、設(shè)備等資源的限制。投資組合如何將資金投資于不同的項(xiàng)目，以獲得最佳的收益率，同時(shí)又要考慮風(fēng)險(xiǎn)和投資的限制。人員分配如何將有限的人員分配到不同的任務(wù)，以最大限度地提高工作效率，同時(shí)又要滿足任務(wù)的限制。整數(shù)規(guī)劃的特點(diǎn)決策變量取值只能是整數(shù)處理離散決策問(wèn)題求解難度較大整數(shù)規(guī)劃的求解方法1分支定界法逐步將可行解空間劃分為更小的子問(wèn)題，并對(duì)每個(gè)子問(wèn)題進(jìn)行評(píng)估，直到找到最優(yōu)解或證明不存在可行解。2割平面法在單純形法的基礎(chǔ)上，通過(guò)添加新的約束條件（割平面）來(lái)排除非整數(shù)解，逼近整數(shù)最優(yōu)解。3隱枚舉法適用于0-1整數(shù)規(guī)劃，通過(guò)系統(tǒng)地枚舉所有可能的解，并通過(guò)剪枝技術(shù)來(lái)減少搜索空間。博弈論基本概念博弈論是研究多個(gè)個(gè)體在相互影響的條件下如何做出決策的理論應(yīng)用廣泛應(yīng)用于經(jīng)濟(jì)學(xué)、政治學(xué)、軍事、社會(huì)學(xué)等領(lǐng)域博弈論的基本概念理性決策博弈論假設(shè)參與者都是理性的，他們會(huì)選擇對(duì)自己最有利的策略。策略選擇博弈論研究的是參與者在特定環(huán)境下如何選擇策略，以及這些策略會(huì)產(chǎn)生什么結(jié)果。利益