運(yùn)籌學(xué)第11講靈敏度分析(已修改)
2025-05-12 12:05 本頁面
【正文】 第 1頁 ? 對偶問題的經(jīng)濟(jì)解釋 —— 影子價(jià)格 Duality Theory ? 線性規(guī)劃的對偶問題 ? 對偶單純形法 ? 靈敏度分析 ? 對偶問題的基本性質(zhì) 第二章 線性規(guī)劃的對偶理論 第 2頁 什么是靈敏度分析 ？ 是指研究線性規(guī)劃模型的某些參數(shù) (bi, cj, aij）或限制量 （ xj, 約束條件 ） 的變化對 最優(yōu)解 的影響及其程度的分析過程 也稱為優(yōu)化后分析 。 一、含義和研究對象 ???njjj xcz1m a x1 1 , ,0 1 , ,ni j j ijja x b i mx j n??????? ???? （ ）（ ）. 第 3頁 回答兩個(gè)問題： ① 這些系數(shù)在什么范圍內(nèi)發(fā)生變化時(shí) ， 最優(yōu)解不變 ？ ② 系數(shù)變化超出上述范圍 ， 如何用最簡便的方法求出新的最優(yōu)解 ？ 靈敏度分析的研究對象： ? 目標(biāo)函數(shù)的系數(shù) cj 變化對最優(yōu)解的影響； ? 約束方程右端系數(shù) bi 變化對最優(yōu)解的影響； ? 約束方程組系數(shù)矩陣 A 變化對最優(yōu)解的影響 ； 一、含義和研究對象 第 4頁 在 最終單純形表 的基礎(chǔ)上進(jìn)行； 盡量減少附加的計(jì)算工作量； 二、進(jìn)行靈敏度分析的基本原則 第 5頁 1. 將參數(shù)的改變通過計(jì)算反映到 最終單純形表 上來 . 2. 檢查 是否仍為原問題的可行解 . 3. 檢查 是否仍為對偶問題的可行解 . 4. 依據(jù) 不同情況 決定繼續(xù)計(jì)算或得到結(jié)論 . 三、靈敏度分析的步驟 原問題 對偶問題 結(jié)論或繼續(xù)計(jì)算的步驟 可行解 可行解 非可行解 非可行解 可行解 非可行解 可行解 非可行解 問題的最優(yōu)解或最優(yōu)基不變 用 單純形法 繼續(xù)迭代求最優(yōu)解 用 對偶單純形法 繼續(xù)迭代求最優(yōu)解 引進(jìn)人工變量，編制新的單純形表重新計(jì)算 第 6頁 4. 分析增加一個(gè) 約束條件 的變化 四、靈敏度分析的主要內(nèi)容 1. 分析 cj 的變化 2. 分析 bi 的變化 3. 分析增加一個(gè)變量 xj 的變化 5. 分析系數(shù) aij 的變化 系數(shù)矩陣 A ???njjj xcz1m a x1 1 , ,0 1 , ,ni j j ijja x b i mx j n??????? ???? （ ）（ ）. 第 7頁 對偶問題決策變量的最優(yōu)解 影子價(jià)格 ： 初始單純形表 最優(yōu)單純形表 X*=B1b CBCNB NXBXN非基變量 基變量XsIjjcz ?0基變量 基變量 基可系數(shù) 行解0 Xs b非基變量 基變量基變量 基變量XBI0基變量 非基變量XBjjcz ?基變量 基變量 基可系數(shù) 行解CN－ CBB 1 N B 1 N B 1XNXsB 1 bC B－ CBB 1基變量 非基變量基變量 基變量 基可－基變量 非基變量基變量 基變量 基可基變量 基變量 基可基變量 基變量 基可－ －CN－ CBB1N ≤0 － CBB1 ≤0 原問題基變量的最優(yōu)解： Z*=CBB1b 最優(yōu)值： Y*T= CBB1 第 8頁 Y*T= CBB1 XB I 0 基變量 非基變量 XB jjcz?基變量 基變量 基可 系數(shù) 行解 CN－ CBB1N B1N B1 XN Xs B1b CB － CBB1 Z*=CBB1b 39。?jj j jc c c? ? ?分析 cj 的變化 原問題 對偶問題 結(jié)論或繼續(xù)計(jì)算的步驟 可行解 可行解 非可行解 非可行解 可行解 非可行解 可行解 非可行解 問題的最優(yōu)解或最優(yōu)基不變 用 單純形法 繼續(xù)迭代求最優(yōu)解 用 對偶單純形法 繼續(xù)迭代求最優(yōu)解 引進(jìn)人工變量，編制新的單純形表重新計(jì)算 0?0?最優(yōu)值可能已變 第 9頁 x1, x2 ≥ 0 max . 2x1 + 2x2 ≤ 12 z = 2x1 + 3x2 4x1 ≤ 16 5x2 ≤ 15 變化 x1, x2 ≥ 0 max . 2x1 + 2x2 ≤ 12 z = (2 +λ1) x1 + (3 +λ2) x2 4x1 ≤ 16 5x2 ≤ 15 jc ?BC 基 b2 3 0 0 0 q i 1xjjcz?4x2x203 3 0 1 0 0 1/53 1 0 1/2 0 1/5?4 0 0 2? 1 4/50 0 1? 0 1/5?1x 2x 3x 4x 5x分析 λ1和 λ2分別在什么范圍變化時(shí) ，最優(yōu)解不變？ 例 11 第 10頁 x1, x2 ≥ 0 max . 2x1 + 2x2 ≤ 12 z = 2x1 + 3x2 4x1 ≤ 16 5x2 ≤ 15 變化 x1, x2 ≥ 0 max . 2x1 + 2x2 ≤ 12 z = (2 +λ1) x1 + (3 +λ2)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1