OR6靈敏度分析與對偶

1、OR6靈敏度分析與對偶 第六章第六章 單純形法的靈敏度分析與對偶單純形法的靈敏度分析與對偶 OR6靈敏度分析與對偶 本章內(nèi)容：本章內(nèi)容： o6.16.1單純形表的靈敏度分析單純形表的靈敏度分析 o6.26.2線性規(guī)劃的對偶問題線性規(guī)劃的對偶問題 o6.36.3對偶規(guī)劃的基本性質(zhì)對偶規(guī)劃的基本性質(zhì) o6.46.4對偶單純形法對偶單純形法 OR6靈敏度分析與對偶 本章重點(diǎn)：本章重點(diǎn)： o利用最優(yōu)單純形表進(jìn)行靈敏度分析利用最優(yōu)單純形表進(jìn)行靈敏度分析 o線性規(guī)劃問題的對偶問題線性規(guī)劃問題的對偶問題 o對偶問題的經(jīng)濟(jì)解釋對偶問題的經(jīng)濟(jì)解釋 OR6靈敏度分析與對偶 6.16.1單純形表的靈敏度分析單純形表

2、的靈敏度分析 o一、目標(biāo)函數(shù)中變量系數(shù)一、目標(biāo)函數(shù)中變量系數(shù)Ck靈敏度分析靈敏度分析 o1.在最終的單純形表里，在最終的單純形表里，X k是非基變量是非基變量 由于約束方程系數(shù)增廣矩陣在迭代中只是其本身的行由于約束方程系數(shù)增廣矩陣在迭代中只是其本身的行 的初等變換與的初等變換與Ck沒有任何關(guān)系，所以當(dāng)沒有任何關(guān)系，所以當(dāng)Ck變成變成 Ck+Ck時，在最終單純形表中其系數(shù)的增廣矩陣不時，在最終單純形表中其系數(shù)的增廣矩陣不 變，又因?yàn)樽儯忠驗(yàn)閄k是非基變量，所以基變量的目標(biāo)函數(shù)是非基變量，所以基變量的目標(biāo)函數(shù) 的系數(shù)不變，即的系數(shù)不變，即CB不變，可知不變，可知Zk也不變，只是也不變，只是Ck變

3、變 成了成了Ck+ Ck。這時。這時K= Ck-Zk就變成了就變成了 K Ck+Ck- Zk= K+ Ck。 要使原來的最優(yōu)解仍為最優(yōu)解，只要要使原來的最優(yōu)解仍為最優(yōu)解，只要K+ Ck0 即可，也就是即可，也就是Ck的增量的增量 Ck- K。 OR6靈敏度分析與對偶 2.在最終的單純形表中，在最終的單純形表中， X k是基變量是基變量 當(dāng)當(dāng)Ck變成變成Ck+Ck時，最終單純形表時，最終單純形表 中約束方程的增廣矩陣不變，但是基中約束方程的增廣矩陣不變，但是基 變量的目標(biāo)函數(shù)的系數(shù)變量的目標(biāo)函數(shù)的系數(shù)CB變了，則變了，則 Zj(j=1,2,.,n)也變了。也變了。 OR6靈敏度分析與對偶 Zj=

4、 Zj +Ck aKj j=Cj-Z j= j Ck a Kj 。要使最。要使最 優(yōu)解不變，優(yōu)解不變， 只要當(dāng)只要當(dāng)j k時，時， j0，也就說，也就說 Ck aKj j oa Kj 0，Ck j/ aKj oa Kj 0,則有則有 若若 ，則有，則有yi*=0 X X Y X Y n j ijij bxa 1 * n j ijij bxa 1 * Y OR6靈敏度分析與對偶 6.46.4對偶單純形法對偶單純形法 對偶單純形法也是解決線性規(guī)劃問題的一種對偶單純形法也是解決線性規(guī)劃問題的一種 方法。對偶單純形法是在保持原有問題的所方法。對偶單純形法是在保持原有問題的所 有檢驗(yàn)數(shù)都小于有檢驗(yàn)數(shù)都小

5、于0的情況下，通過迭代使得的情況下，通過迭代使得 所有的約束都大于等于所有的約束都大于等于0，最后求得最優(yōu)解。，最后求得最優(yōu)解。 OR6靈敏度分析與對偶 簡化計(jì)算是對偶單純形法的優(yōu)點(diǎn)，但是它在使用上有很簡化計(jì)算是對偶單純形法的優(yōu)點(diǎn)，但是它在使用上有很 大的局限，這主要是大多數(shù)線性規(guī)劃問題很難找到初始大的局限，這主要是大多數(shù)線性規(guī)劃問題很難找到初始 解使得其所有檢驗(yàn)數(shù)都小于解使得其所有檢驗(yàn)數(shù)都小于0。但是在靈敏度分析中，。但是在靈敏度分析中， 有時需要對偶單純形法，這樣可以簡化處理。下面以第有時需要對偶單純形法，這樣可以簡化處理。下面以第 二節(jié)例一為例。二節(jié)例一為例。 上節(jié)分析中已知當(dāng)上節(jié)分析中

6、已知當(dāng)250b1325時第一個約束條件時第一個約束條件 的對偶價(jià)格不變，現(xiàn)在的對偶價(jià)格不變，現(xiàn)在b1=300變成變成b1=350，請問，請問 這時第一個約束方程的對偶價(jià)格應(yīng)為多少呢？這時第一個約束方程的對偶價(jià)格應(yīng)為多少呢？ OR6靈敏度分析與對偶 解：求出在第二次迭代表上的常數(shù)列 。 250 50 100 0 2 250 50 50 XX 1 1 1 b b b b bB OR6靈敏度分析與對偶 1.確定出基變量，在常數(shù)列中找一個最小的負(fù)常量，把這個常量所在確定出基變量，在常數(shù)列中找一個最小的負(fù)常量，把這個常量所在 行作為出基變量行作為出基變量 迭代 次數(shù) 基變量CBX1 X2 S1 S2 S3b 50 100 0 0 0 2 X1501 0 1 0 -1100 S200 0 -2 1 1-50 X21000 1 0 0 1250 ZJ50 100 0 50 50 CJ -ZJ0 0 -50 0 -50 OR6靈敏度分析與對偶 OR6靈敏度分析與對偶 4.檢查常數(shù)列值，若已經(jīng)都非負(fù)，結(jié)束迭代，即為最優(yōu)，如果還有負(fù)檢查常數(shù)列值，若已經(jīng)都非負(fù)，結(jié)束迭代，即為最優(yōu)，如果還有負(fù) 數(shù)重復(fù)數(shù)重復(fù)1-4步步 迭代次 數(shù) 基變量CBX1 X2 S1 S2 S3b 50 100 0 0