純形法的靈敏度分析.ppt

第六章 單純形法的靈敏度分析,一、問題的提出 二、目標(biāo)函數(shù)系數(shù)的變化 三、右端項的變化 四、技術(shù)系數(shù)的變化 五、增加約束條件,一、問題的提出,假設(shè)范例 目標(biāo)函數(shù)：Max z= 50x1+100 x2 約束條件：1x1+1x2300 2x1+1 x2400 0x1+1 x2250 x1 0， x2 0 中x2的目標(biāo)函數(shù)系數(shù)由100變?yōu)?5，求新問題的解。,一、問題的提出,解：經(jīng)過單純形迭代得到最優(yōu)表,一、問題的提出,比較范例的最優(yōu)表：,一、問題的提出,事實上，系數(shù)的改變并未改變LP問題的解。 思考： 1、如果C2變?yōu)?5，最優(yōu)解會變嗎？為保證最優(yōu)解不變， C2的取值范圍？ 2、參數(shù)變化時，可否利用原問題的最優(yōu)表求解，而不必從頭進(jìn)行單純形迭代，以簡化計算？,一、問題的提出,要解決以上問題，需要探討初始單純形表與最優(yōu)單純形表的關(guān)系。 觀察范例的單純形求解過程：,一、問題的提出,事實上，在單純形表的迭代過程中，最核心的變化是系數(shù)矩陣的行變換，其它值如cj在每次迭代中不變，zj和檢驗數(shù)則是根據(jù)其它元素計算得出。,一、問題的提出,初始矩陣,最優(yōu)矩陣,行變換,初始基,初始矩陣變最優(yōu)矩陣的過程可以表示為：,如，b2變?yōu)?00，則最優(yōu)矩陣可計算出：,單純形法的靈敏度分析基本思路：,1、將某個參數(shù)的變化反映在最終表中； 2、看最終表是否還滿足最優(yōu)表的要求：基是否為單位排列陣，檢驗數(shù)是否都非正，b列是否都為非負(fù)的數(shù)； 3、若滿足上述要求則最優(yōu)基沒有改變，若不滿足則在新的最終表上繼續(xù)進(jìn)行迭代，直到找到新的最優(yōu)基為止。,二、目標(biāo)函數(shù)系數(shù)ck的變化,1、在最終單純形表中，xk是非基變量 除了xk的檢驗數(shù)外， ck的變化不會影響到最終單純形表中其它任何數(shù)值。 只要xk的檢驗數(shù)仍然非正，最優(yōu)解和最優(yōu)值都會保持不變。,如范例，使最優(yōu)解不變的cj值變化范圍？,要使最優(yōu)解不變，須c3-50 0求得c3 50,二、目標(biāo)函數(shù)系數(shù)ck的變化,二、目標(biāo)函數(shù)系數(shù)ck的變化,2、在最終單純形表中， xk是基變量 此時各非基變量的檢驗數(shù)均有可能受到影響，同時還會影響到最優(yōu)值。 要最優(yōu)解不變，必須保證所有的檢驗數(shù)非正。,要使最優(yōu)解不變，須- c10且c1 -100 0 求得0 c1 100,二、目標(biāo)函數(shù)系數(shù)ck的變化,要使最優(yōu)解不變，須50-c2 0求得c2 50,二、目標(biāo)函數(shù)系數(shù)ck的變化,要使最優(yōu)解不變，須2c4-50 0且- c4 -50 0 求得-50 c4 25,二、目標(biāo)函數(shù)系數(shù)ck的變化,課堂練習(xí),有下列線性規(guī)劃問題： Max z = -2x1 - 3x2 - 4x3 S.t. -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 0 分別分析目標(biāo)函數(shù)中x1和x3的系數(shù)在什么范圍內(nèi)變動時，最優(yōu)解不變。,課堂練習(xí),解：最優(yōu)表為,課堂練習(xí),所有j0時，原最優(yōu)解不變 從表中可得到： -17/7 c1 -3/2 。,課堂練習(xí),從表中看到3= c3 +11/5 0 可得到c3 -11/5 時，原最優(yōu)解不變。,三、右端項的變化,右端項發(fā)生變化時，最優(yōu)解中變量的取值總會隨之變化。 討論右端項的取值范圍時，考慮的是使最優(yōu)基和對偶價格不變。,三、右端項的變化,例：范例中b1為300，使最優(yōu)基不變的b1取值范圍？ 解：最優(yōu)表中的b列可表示為Bb0,三、右端項的變化,最優(yōu)表可表示為：,三、右端項的變化,最優(yōu)值z* 50b1 +12500 可見b1的對偶價格50。 由b1 -2500推出b1 250 由-2 b1 +650 0推出 325 b1 只要最優(yōu)基不變，對偶價格也不會變。 即325 b1 250時對偶價格不變。,三、右端項的變化,練習(xí)：分析范例b2的變化范圍。,對偶價格在單純形表中的表示,根據(jù)對偶價格定義，如果最優(yōu)目標(biāo)函數(shù)值Z*可以表示為右端項bi的函數(shù)，則對于目標(biāo)函數(shù)最大化的LP問題， bi的對偶價格可以表示為數(shù)學(xué)表達(dá)式： 關(guān)鍵是：如何將目標(biāo)函數(shù)表示為bi的函數(shù)？,B,CB*,對偶價格在單純形表中的表示,觀察范例最優(yōu)表：,對偶價格在單純形表中的表示,由于 故，,最終表中第i個初始基變量的z值,對偶價格在單純形表中的表示,結(jié)論： 各右端項的對偶價格就是其所在方程中初始基變量在最優(yōu)表中的zj值。 相關(guān)概念： 影子價格右端項增加一單位，使最優(yōu)目標(biāo)函數(shù)值增加的數(shù)量。,四、技術(shù)矩陣的變化,1、最終單純形表中非基變量對應(yīng)的系數(shù)列向量由pk pk時，最優(yōu)表中發(fā)生變化的有： 最優(yōu)矩陣中的第k列，變?yōu)?B0pk 最終表中檢驗數(shù)k=ck-CB*T B0pk 若仍有k0，則最優(yōu)解不變，否則繼續(xù)迭代，直到找到新的最優(yōu)解。,四、技術(shù)系數(shù)的變化,2、對于增加一個變量，從而使得系數(shù)矩陣增加一列pn+1的情況： 技術(shù)矩陣由mn階變?yōu)閙(n+1)階 在最終表中加入一列pn+1B0 pn+1 然后計算檢驗數(shù)。若n+10，則進(jìn)行迭代，直到找到新的最優(yōu)解。,四、技術(shù)系數(shù)的變化,如范例，新增產(chǎn)品3，價值系數(shù)為150，相應(yīng)增加一個技術(shù)列向量p6(2,0.5,1.5)T 則最優(yōu)矩陣中p6 B 檢驗數(shù)6150-(50,0,100) -25。,四、技術(shù)系數(shù)的變化,所有檢驗數(shù)仍然小于0，故最優(yōu)基和最優(yōu)解不變。 說明增加了產(chǎn)品3并不改變原生產(chǎn)計劃。,四、技術(shù)系數(shù)的變化,假如產(chǎn)品3的工藝改進(jìn)，價值系數(shù)變?yōu)?60，技術(shù)列向量變?yōu)?1.5，2，1)T 則最優(yōu)矩陣中p6 B 檢驗數(shù)6160-(50,0,100) 35。,四、技術(shù)系數(shù)的變化,檢驗數(shù)635，還需迭代。,四、技術(shù)系數(shù)的變化,3、最終單純形表中基變量對應(yīng)的系數(shù)列向量由pk pk時，原最優(yōu)解的可行性和最優(yōu)解都可能遭到破壞，情況比較復(fù)雜，一般重新求解。,五、增加約束條件,在原線性規(guī)劃中增加一個約束條件時，先將原問題的最優(yōu)解的變量值代入新增的約束條件。 如果滿足，則說明新增的條件沒有起到限制作用，故最優(yōu)解不變； 如果不滿足，則將新增的約束添入原最終單純形表中進(jìn)一步求解。,五、增加約束條件,如范例，新增約束條件電量限制5000度，生產(chǎn)一個產(chǎn)品1需要用電10度，生產(chǎn)一個產(chǎn)品2需要用電30度。 即，10x1+30x25000 原最優(yōu)解（50，250，0，50，0）代入， 10x1+30x280005000，不滿足，須迭代。,五、增加約束條件,引入松弛變量x6， 10x1+30x2 + x65000,五、增加約束條件,用行變換將基變量對應(yīng)的系數(shù)列向量化為單位列向量：,課堂練習(xí),對于LP問題： Max z = 2x1 + 3x2 s.t. x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1 , x2 , x3 , x4 , x5 0,課堂練習(xí),分析： 1、使最優(yōu)解不變的系數(shù)c2的取值范圍； 2、使最優(yōu)基不變的b1的取值范圍； 3、若增加x6 , p6=( 2, 6, 3 )T, c6=5，最優(yōu)解如何？ 4、若增加3x1+ 2x215，最優(yōu)解如何？,課堂練習(xí),解：原問題最優(yōu)表為,課堂練習(xí),1、由-c2 /2 0， c2/8-1/2 0 ， 得c2的取值范圍：（0，4）,課堂練習(xí),2、用b1表示最優(yōu)表中的右端項：,初始基在最優(yōu) 表中的形式,課堂練習(xí),由于最優(yōu)表右端項有非負(fù)要求，即 解得b1的取值范圍：（4，10）,0,課堂練習(xí),3、增加p6=( 2, 6, 3 )T ，最優(yōu)表中增加列：,初始基在最優(yōu) 表中的形式,課堂練習(xí),最優(yōu)表變?yōu)椋?課堂練習(xí),用單純形法進(jìn)一步求解，可得： X* = ( 1,1.5,0,0