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

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