1、3.5.5 靈敏度分析,一、靈敏度分析的含義和內(nèi)容 1、什么是靈敏度分析？ 研究線性規(guī)劃模型某些參數(shù)（A,b,c）或限制量(x,約束條件)的變化對(duì)最優(yōu)解的影響及其程度的分析過程稱為靈敏度分析或（優(yōu)化后分析）。,2、靈敏度分析的內(nèi)容： 目標(biāo)函數(shù)的系數(shù)c變化對(duì)最優(yōu)解的影響； 約束方程右端系數(shù)b變化對(duì)最優(yōu)解的影響； 約束方程組系數(shù)陣A變化對(duì)最優(yōu)解的影響 ；,回答兩個(gè)問題：,這些系數(shù)在什么范圍內(nèi)發(fā)生變化時(shí)，最優(yōu)基不變（即最優(yōu)解或最優(yōu)解結(jié)構(gòu)不變）？ 系數(shù)變化超出上述范圍時(shí)，如何用最簡便的方法求出新的最優(yōu)解？,兩個(gè)問題,初始單純形表,最優(yōu)單純形表,二、 進(jìn)行靈敏度分析的基本原則 1、在最優(yōu)表格的基礎(chǔ)上進(jìn)行

2、； 2、盡量減少附加計(jì)算工作量；,三、 靈敏度分析的步驟: 將參數(shù)的改變通過計(jì)算反映到最終單純形表上來. 檢查是否仍為原問題的可行解. 檢查是否仍為對(duì)偶問題的可行解. 4.依據(jù)不同情況決定繼續(xù)計(jì)算或得到結(jié)論.,原問題和對(duì)偶問題同時(shí)可行時(shí)，同時(shí)達(dá)到最優(yōu),主要內(nèi)容,一.分析 cj 的變化,二.分析 bj 的變化,一. 分析 cj 的變化,c,仍為最優(yōu)解，但最優(yōu)值可能已變,不是最優(yōu)解，用單純形法繼續(xù)迭代,解這n-m個(gè)不等式，可算出保持最優(yōu)解不變時(shí)cj的變化范圍 ！,（1）當(dāng)cj是非基變量的價(jià)值系數(shù) 它的變化只影響一個(gè)檢驗(yàn)數(shù),（2）當(dāng)cj是基變量的價(jià)值系數(shù) 它的變化將影響所有非基變量的檢驗(yàn)數(shù),例3.2

3、0 給定線性規(guī)劃問題,試討論c1,c2,c3分別在什么范圍內(nèi)變化時(shí)，最優(yōu)解不變？,最優(yōu)表,x5,x1,x3,二. 分析 bj 的變化,b,仍為最優(yōu)解，但最優(yōu)解、最優(yōu)值可能已變,是正則解，用對(duì)偶單純形法繼續(xù)迭代,保持B-1b0,當(dāng)前的基仍為最優(yōu)基，最優(yōu)解的結(jié)構(gòu)不變（取值改變）； （B-1b）i0,當(dāng)前基為非可行基,但是仍保持為對(duì)偶可行基，可用對(duì)偶單純形法求出新的最優(yōu)解； 如何求出保持最優(yōu)基不變的bi的范圍? 把bi看作待定參數(shù),令B-1b0,求解該不等式組即可；,例3.21 給定線性規(guī)劃問題,試討論b1,b2在什么范圍內(nèi)變化時(shí)，最優(yōu)基保持不變？,x2,x5,最優(yōu)表,作 業(yè)P148,20,3.5.

4、3 退化與循環(huán),例：,退化與循環(huán)的問題,在非退化情形下，用單純形方法經(jīng)過有限次迭代一定可達(dá)到最優(yōu)解。,在退化情形下，用單純形方法進(jìn)行迭代可能得不到最優(yōu)解。,基迭代經(jīng)過若干次后又回到先前的可行基,循環(huán),為避免循環(huán)，伯蘭特(Bland)規(guī)則：,1. 當(dāng)存在多個(gè) ，始終選取下標(biāo)值為最小的變量作為進(jìn)基變量。,2.當(dāng) 出現(xiàn)兩個(gè)以上相同的最小比值時(shí)，始終選取下標(biāo)值為最小的變量為離基變量,3.3.2 攝動(dòng)法,四個(gè)定理,利用單純形法求解攝動(dòng)問題時(shí)， 不會(huì)出現(xiàn)循環(huán)現(xiàn)象。,判別數(shù)相同,通過求解攝動(dòng)問題，能給出原問題的解。,兩個(gè)問題： 怎樣找到攝動(dòng)問題的初始基本可行解? 如何處理 ?,基列下標(biāo)小于非基列下標(biāo),進(jìn)行列調(diào)換，把基列排在非基列的左邊，并相應(yīng)地改變變量的下標(biāo)，使