管理運(yùn)籌學(xué)-單純形法的靈敏度分析與對(duì)偶

1、1,第六章 單純形法的靈敏度分析與對(duì)偶,§1　單純形表的靈敏度分析§2　線性規(guī)劃的對(duì)偶問(wèn)題§3　對(duì)偶規(guī)劃的基本性質(zhì)§4　對(duì)偶單純形法,2,§1　單純形表的靈敏度分析,一、目標(biāo)函數(shù)中變量Ck系數(shù)靈敏度分析1.在最終的單純形表里，X k是非基變量 由于約束方程系數(shù)增廣矩陣在迭代中只是其本身的行的初等變換與Ck沒(méi)有任何關(guān)系，所以當(dāng)Ck變成Ck+ Ck時(shí)，在最終單純形表中其系數(shù)

2、的增廣矩陣不變，又因?yàn)閄k是非基變量，所以基變量的目標(biāo)函數(shù)的系數(shù)不變，即CB不變，可知Zk也不變，只是Ck變成了Ck+ Ck。這時(shí) K= Ck-Zk就變成了Ck+ Ck- Zk= K+ Ck。要使原來(lái)的最優(yōu)解仍為最優(yōu)解，只要 K+ Ck≤0即可，也就是Ck的增量 Ck≤- K。2.在最終的單純形表中， X k是基變量 當(dāng)Ck變成Ck+ Ck時(shí)，最終單純形表

3、中約束方程的增廣矩陣不變，但是基變量的目標(biāo)函數(shù)的系數(shù)CB變了，則ZJ(J=1,2,…..,N)一般也變了，不妨設(shè)CB=(CB1, CB2。。。, Ck,…， CBm),當(dāng)CB變成=(CB1, CB2。。。,Ck+ Ck,…,CBm),則： ZJ=(CB1, CB2。。。, Ck,…，CBm)(a’1j , a’2j ,…, a’Kj ,…, a’mj) Z’J=(CB1, CB2。。。, Ck+

4、 Ck,…，CBm)(a’1j , a’2j ,…, a’Kj ,…, a’mj) = ZJ + Ck a’Kj,3,§1　單純形表的靈敏度分析,根據(jù)上式可知 檢驗(yàn)數(shù) J (J=1,2,…..,M)變成了 ’J,有 ’ J=CJ-Z’J= J+ CK a’Kj 。要使最優(yōu)解不變，只要當(dāng)J K時(shí)， ’J <=0,4,§1　單純形表

5、的靈敏度分析,例： 目標(biāo)函數(shù)：Max z=50X1+100X2 約束條件：X1+X2≤300 2X1+X2≤400 X2≤250 X1，X2≥0最優(yōu)單純形表如下,5,§1　單純形表的靈敏度分析,我們先對(duì)非基變量S1的目標(biāo)函數(shù)的系數(shù)C3進(jìn)行靈敏度分析。

6、 這里δ3=-50，所以當(dāng)c3的增量Δc3≤50，最優(yōu)解不變。 再對(duì)基變量x1的目標(biāo)函數(shù)的系數(shù)c1進(jìn)行靈敏度分析。 在a11’,a12’,a13’,a14’,a15’中，除了知道a11’和 a13’大于0， a15’小于0，可知 ，有 。同樣有 。這樣可以知道當(dāng)-50≤Δc1≤50時(shí)，

7、也就是x1的目標(biāo)函數(shù)c1’在0≤c1’≤100時(shí)最優(yōu)解不變。 在最終的單純形表中，用C’1代替原來(lái)的C1=50,計(jì)算得表,6,§1　單純形表的靈敏度分析,,從δ3≤0，得到-c1’≤0,即c1’≥0，并且從δ5≤0，得到c1’≤100。 那么如果c1’取值超出這個(gè)范圍，必然存在一個(gè)檢驗(yàn)數(shù)大于0，我們可以通過(guò)迭代來(lái)得到新的最優(yōu)解。,7,§1　單純形表的靈敏度分析,二、約束方程中常數(shù)項(xiàng)的靈敏度分

8、析 從上表我們可以發(fā)現(xiàn)各個(gè)松弛變量的值，正好等于相應(yīng)變量的對(duì)偶價(jià)格。在最優(yōu)解中S2 =50是基變量，即為，原料A有50千克沒(méi)用完，再增加A原料是不會(huì)增加利潤(rùn)的， A的對(duì)偶價(jià)格為0。對(duì)于任何為基變量的松弛變量所對(duì)應(yīng)的約束條件的對(duì)偶價(jià)格為0。,8,§1　單純形表的靈敏度分析,可以看出，上題中對(duì)于設(shè)備臺(tái)時(shí)數(shù)約束來(lái)說(shuō)，當(dāng)其松弛變量在目標(biāo)函數(shù)中從0變到Z3=50時(shí)，也就是只要當(dāng)前余下一臺(tái)時(shí)數(shù)設(shè)備從

9、不能獲利變成獲利50元時(shí)，譬如有人愿意出50元買一個(gè)設(shè)備時(shí)，我們就不必為生產(chǎn)Ι、П產(chǎn)品而使用完所有的設(shè)備臺(tái)時(shí)了，這說(shuō)明了設(shè)備臺(tái)時(shí)數(shù)的對(duì)偶價(jià)格就是Z3=50元。 對(duì)于含有大于等于號(hào)的約束條件，添加剩余變量化為標(biāo)準(zhǔn)型。這時(shí)這個(gè)約束條件的對(duì)偶價(jià)格就和這個(gè)剩余變量的 有關(guān)了。這將使得最優(yōu)目標(biāo)值特別“惡化”而不是改進(jìn)，故這時(shí)約束條件的對(duì)偶價(jià)格應(yīng)取 值的相反數(shù)- 。 對(duì)于含有等于號(hào)

10、的約束條件，其約束條件的對(duì)偶價(jià)格就和該約束方程的人工變量有關(guān)了。其約束條件的對(duì)偶價(jià)格就等于此約束方程的人工變量的 值。,9,下表給出了一個(gè)由最終單純形表對(duì)于不同約束類型的對(duì)偶價(jià)格的取值。 從對(duì)偶價(jià)格的定義,可以知道當(dāng)對(duì)偶價(jià)格為正時(shí)它將改進(jìn)目標(biāo)函數(shù)的值，當(dāng)對(duì)偶價(jià)格為負(fù)時(shí)它將使得目標(biāo)函數(shù)朝著與最優(yōu)化相反的方向前進(jìn)。 下面我們研究當(dāng)右端項(xiàng)bj發(fā)

11、生變化時(shí)，在什么范圍內(nèi)其對(duì)偶價(jià)格不變。由于bj的變化并不影響系數(shù)矩陣的迭代，故其最終單純形表中的系數(shù)矩陣沒(méi)有變化。由此可見(jiàn)當(dāng)bj變化時(shí)，要使原來(lái)的基不變得到的基本可行解仍然是可行解，也就是所求的基變量的值一定要大于0。所謂使其對(duì)偶價(jià)格不變的bj的變化范圍，也就是使其最優(yōu)解的所有基變量不變，且所得的最優(yōu)解仍然是可行的bj的變化范圍。,,§1　單純形表的靈敏度分析,10,§1　單純形表的靈敏度分析,當(dāng)bj中的第k

12、項(xiàng)bK 變成 時(shí)，也就是原來(lái)的初始單純形表中的b向量變成了b’向量,11,§1　單純形表的靈敏度分析,這樣在最終單純形表中基變量XB的解就變成了 如要使XB成為可行解，只要使上述等式的右邊>0，就可求出 的取值范圍，也就是使得第K個(gè)約束條件的對(duì)偶價(jià)格不變的bk的變化范圍。

13、 ，,12,§1　單純形表的靈敏度分析,下面我們?nèi)砸缘诙吕?在最終單純形表上對(duì)bj 進(jìn)行靈敏度分析。最終單純形表如下所示：,13,§1　單純形表的靈敏度分析,我們對(duì)b1進(jìn)行靈敏度分析，因?yàn)樵诘谝粋€(gè)約束方程中含有松弛變量S1, 實(shí)際意義可以描述為：當(dāng)設(shè)備臺(tái)時(shí)數(shù)的對(duì)偶價(jià)格不變，都為每設(shè)備臺(tái)時(shí)數(shù)在250與325之間變化，則設(shè)備臺(tái)時(shí)數(shù)的對(duì)偶價(jià)格不變，都為每臺(tái)設(shè)備臺(tái)時(shí)50元。,

14、14,§1　單純形表的靈敏度分析,三、約束方程系數(shù)矩陣A靈敏度分析下面分兩種情況討論 1.在初始單純形表上的變量Xk的系數(shù)列Pk改變?yōu)镻’k經(jīng)過(guò)迭代后，在最終單純形表上Xk是非基變量。由于單純形表的迭代是約束方程的增廣矩陣的行變換，Pk變成Pk’僅僅影響最終單純形表上第k列數(shù)據(jù)，包括Xk的系數(shù)列、Zk以及 k，這時(shí)最終單純形表上的Xk的系數(shù)列就變成了B-1Pj’,而Zk就變成CBB-1Pk’，新的檢驗(yàn)數(shù)

15、 k=Ck-CBB-1Pk’。若 k≤0，則原最優(yōu)解仍然為最優(yōu)解。若 k 〉0，則繼續(xù)進(jìn)行迭代以求出最優(yōu)。 例 以第二章例1為基礎(chǔ)，設(shè)該廠除了生產(chǎn)Ι，Ⅱ種產(chǎn)品外，現(xiàn)在試制成一個(gè)新產(chǎn)品Ⅲ，已知生產(chǎn)產(chǎn)品Ⅲ,每件需要設(shè)備2臺(tái)時(shí)，并消耗A原料0.5公斤。B原料1.5公斤，獲利150元，問(wèn)該廠應(yīng)該生產(chǎn)該產(chǎn)品多少？解：這是一個(gè)增加新變量的問(wèn)題。我們可以把它認(rèn)為是一個(gè)改變變量X3在初始表上的系數(shù)列的問(wèn)題，,15,§1　單純形表的靈敏

16、度分析,接上頁(yè),16,§1　單純形表的靈敏度分析,例 假設(shè)上例題中產(chǎn)品Ш的工藝結(jié)構(gòu)有了改進(jìn)，這時(shí)生產(chǎn)1件Ш產(chǎn)品需要使用1.5臺(tái)設(shè)備 ，消耗原料A為2千克，原料B為1千克，每件Ш產(chǎn)品的利潤(rùn)為160元，問(wèn)該廠的生產(chǎn)計(jì)劃是否要修改。 解：首先求出X3在最終表上的系數(shù)列,,17,§1　單純形表的靈敏度分析,接下來(lái)又可以有新的迭代S3進(jìn)基，,,18,§1　單純形表的靈敏度分析,接上頁(yè)

17、 可知此規(guī)模的最優(yōu)解X1=0, X2=0, S1=0, S2=0, S3=50, X3=200,此時(shí)，最大目標(biāo)函數(shù)為32000元。也就是說(shuō)，該廠的新的生產(chǎn)計(jì)劃為不生產(chǎn)Ι、П產(chǎn)品，生產(chǎn)Ш產(chǎn)品200件, 可獲得最大利潤(rùn)32000元。,19,§1　單純形表的靈敏度分析,2.在初始表上的變量XK的系數(shù)PK改變?yōu)镻’K，經(jīng)過(guò)迭代后，在最終表上XK是基變量，在這種情況下原最優(yōu)解的可行性和最優(yōu)解都可能被破

18、壞，問(wèn)題十分復(fù)雜，一般不去修改原表而是直接計(jì)算。,20,§1　單純形表的靈敏度分析,四、增加一個(gè)約束條件的靈敏度分析,在原線性規(guī)劃中增加一個(gè)約束條件時(shí),先將原問(wèn)題的最優(yōu)解的變量值代入新增的約束條件，如滿足則說(shuō)明新增的條件沒(méi)有起到限制作用，故原最優(yōu)解不變，否則將新增的約束添入原最終單純形表上進(jìn)一步求解。 下面仍以第三章例1為例來(lái)加以說(shuō)明。 例：假如該工廠除了在設(shè)備臺(tái)時(shí)，原材料A、B上對(duì)該廠的生產(chǎn)有限制外，還有電

19、力供應(yīng)上的限制。最高供應(yīng)電量為5000度，而生產(chǎn)一個(gè)Ⅰ產(chǎn)品需要用電10度，而生產(chǎn)一個(gè)Ⅱ產(chǎn)品需要用電30度。試分析此時(shí)該廠獲得最大利潤(rùn)的生產(chǎn)計(jì)劃？,21,§1　單純形表的靈敏度分析,,解：先將原問(wèn)題的最優(yōu)解,=50，,=250代入用電量的約束條件,得：10×50+30×250=500+7500>5000,所以原題的最優(yōu)解不是本題的最優(yōu)解。在用電量的約束條件中加入松馳變量S4后得：,,把這個(gè)約束條件加入

20、到原最終單純形表上，其中S4為基變量，得表如下：,,22,§1　單純形表的靈敏度分析,,在上表中的X1，X2不是單位向量，故進(jìn)行行的線性變換，得,把上表中的S4行的約束可以寫為：,上式兩邊乘以（-1），再加上人工變量a1得：,用上式替換上表中的S4行，得下表：,23,§1　單純形表的靈敏度分析,,24,§1　單純形表的靈敏度分析,,由上表可知，最優(yōu)解為：,即該工廠在添加了用電限量以后的最優(yōu)生產(chǎn)計(jì)劃為Ⅰ產(chǎn)品生

21、產(chǎn)140件，Ⅱ產(chǎn)品生產(chǎn)120件。,25,每一個(gè)線性規(guī)劃問(wèn)題，都存在每一個(gè)與它密切相關(guān)的線性規(guī)劃的問(wèn)題，我們稱其為原問(wèn)題，另一個(gè)為對(duì)偶問(wèn)題。例題1 某工廠在計(jì)劃期內(nèi)安排Ⅰ、Ⅱ兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需設(shè)備A、B、C臺(tái)時(shí)如表所示 該工廠每生產(chǎn)一單位產(chǎn)品 可獲利50元，每生產(chǎn)一單位產(chǎn)品Ⅱ可獲利100元，問(wèn)工廠應(yīng)分別生產(chǎn)多少 產(chǎn)品和Ⅱ產(chǎn)品，才能使工廠獲利最多？解：設(shè) 為產(chǎn)品 的計(jì)劃產(chǎn)量， 為產(chǎn)品

22、Ⅱ的計(jì)劃產(chǎn)量，則有目標(biāo)函數(shù)： Max z=50 +100約束條件： ，,§2 線性規(guī)劃的對(duì)偶問(wèn)題,26,現(xiàn)在我們從另一個(gè)角度來(lái)考慮這個(gè)問(wèn)題。假如有另外一個(gè)工廠要求租用該廠的設(shè)備A、B、C，那么該廠的廠長(zhǎng)應(yīng)該如何來(lái)確定合理的租金呢？ 設(shè)

23、 分別為設(shè)備A、B、C的每臺(tái)時(shí)的租金。為了敘述方便，這里把租金定義為扣除成本后的利潤(rùn)。作為出租者來(lái)說(shuō)，把生產(chǎn)單位 產(chǎn)品所需各設(shè)備的臺(tái)時(shí)各總租金不應(yīng)低于原利潤(rùn)50元，即 ，否則就不出租還是用于生產(chǎn) 產(chǎn)品以獲利50元；同樣把 生產(chǎn)一單位 產(chǎn)品所需各設(shè)備的臺(tái)時(shí)的總租金也不應(yīng)當(dāng)?shù)陀谠麧?rùn)100元， 即，否則這些設(shè)備臺(tái)時(shí)就不出租，還是用于生產(chǎn) 產(chǎn)品以獲利100元

24、。但對(duì)于租用者來(lái)說(shuō)，他要求在滿足上述要求的前提下，也就是在出租者愿意出租的前提下盡量要求全部設(shè)備臺(tái)時(shí)的總租金越低越好，即min ，這樣我們得到了該問(wèn)題的數(shù)學(xué)模型： 目標(biāo)函數(shù)： 約束條件： 這樣從兩個(gè)不同的角度來(lái)考慮同一個(gè)工廠的最大利潤(rùn)（最小租金）的問(wèn)題，所建立起來(lái)的兩個(gè)線性模

25、型就是一對(duì)對(duì)偶問(wèn)題，其中一個(gè)叫做原問(wèn)題，而另外一個(gè)叫對(duì)偶問(wèn)題。,§2 線性規(guī)劃的對(duì)偶問(wèn)題,27,如果我們把求目標(biāo)函數(shù)最大值的線性規(guī)劃問(wèn)題看成原問(wèn)題，則求目標(biāo)函數(shù)最小值的線性規(guī)劃問(wèn)題看成對(duì)偶問(wèn)題。下面來(lái)研究這兩個(gè)問(wèn)題在數(shù)學(xué)模型上的關(guān)系。 1 求目標(biāo)函數(shù)最大值的線性規(guī)劃問(wèn)題中有n 個(gè)變量 m個(gè)約束條件，它的約束條件都是小于等于不等式。而其對(duì)偶則是求目標(biāo)函數(shù)為最小值的線性規(guī)劃問(wèn)題，有m個(gè)變量n個(gè)約束

26、條件，其約束條件都為大于等于不等式。 2 原問(wèn)題的目標(biāo)函數(shù)中的變量系數(shù)為對(duì)偶問(wèn)題中的約束條件的右邊常數(shù)項(xiàng)，并且原問(wèn)題的目標(biāo)函數(shù)中的第i個(gè)變量的系數(shù)就等于對(duì)偶問(wèn)題中的第i個(gè)約束條件的右邊常數(shù)項(xiàng)。 3 原問(wèn)題的約束條件的右邊常數(shù)項(xiàng)為對(duì)偶問(wèn)題的目標(biāo)函數(shù)中的變量的系數(shù)。并且原問(wèn)題的第i個(gè)約束條件的右邊常數(shù)項(xiàng)就等于零對(duì)偶問(wèn)題的目標(biāo)函數(shù)中的第i個(gè)變量的系數(shù)。 4 對(duì)偶問(wèn)題的約束條件的系數(shù)矩陣A是原問(wèn)題約束

27、矩陣的轉(zhuǎn)置。 設(shè) A=則,§2 線性規(guī)劃的對(duì)偶問(wèn)題,28,如果我們用矩陣形式來(lái)表示，則有原問(wèn)題： 其中A是 矩陣m*n，該問(wèn)題有m個(gè)約束條件n個(gè)變量，x= ,b= , c=

28、 對(duì)偶問(wèn)題： 其中 是A的轉(zhuǎn)置， 是b的轉(zhuǎn)置, 是c的轉(zhuǎn)置, y= 現(xiàn)在我們用單純形法求對(duì)偶問(wèn)題的解。,§2 線性規(guī)劃的對(duì)偶問(wèn)題,29,加上剩余變量 和人工變量 ，把此問(wèn)題化成標(biāo)準(zhǔn)型如下：把上述數(shù)據(jù)

29、填入單純形表計(jì)算。,§2 線性規(guī)劃的對(duì)偶問(wèn)題,30,§2 線性規(guī)劃的對(duì)偶問(wèn)題,,31,由上表，最優(yōu)解： =50， -f 的最大值為-27500，即目標(biāo)函數(shù)f的最大值為f=27500元。 從上面可知租金：A設(shè)備為50元，B設(shè)備為0元，C設(shè)備為5

30、0元。這樣把工廠的所有設(shè)備出租可共得租金27500元。對(duì)出租者來(lái)說(shuō)這租金是出租者愿意出租設(shè)備的最小費(fèi)用，因?yàn)檫@是目 標(biāo)函數(shù)的最小值。 通過(guò)比較，我們發(fā)現(xiàn)：對(duì)偶問(wèn)題的最優(yōu)解即最佳租金恰好等于原問(wèn)題各種設(shè)備的對(duì)偶價(jià)格，這在道理上也能講得通。 對(duì)于兩個(gè)有對(duì)偶關(guān)系的線性規(guī)劃的問(wèn)題，我們只要求得了其中一個(gè)最優(yōu)解，就可以從這個(gè)問(wèn)題的對(duì)偶價(jià)格而求得其對(duì)偶問(wèn)題的最優(yōu)解，知道其中一個(gè)最優(yōu)值也就找到了其對(duì)偶問(wèn)題的最優(yōu)值，因?yàn)檫@兩

31、個(gè)最優(yōu)值相等。,§2 線性規(guī)劃的對(duì)偶問(wèn)題,32,下面來(lái)闡述如何寫出一個(gè)線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題。為了便于闡述，我們不妨以下面的線性規(guī)劃為例，寫出它的對(duì)偶問(wèn)題。 S.T.,§2 線性規(guī)劃的對(duì)偶問(wèn)題,33,這是一個(gè)求最大值的線性規(guī)劃問(wèn)題，為了寫出它的對(duì)偶問(wèn)題，我們不妨把它的約束條件都變換成取小于號(hào)

32、的不等式。顯然第一個(gè)約束條件已符合要求，不要做任何變動(dòng)，而第二個(gè)約束條件，我們只要兩邊都乘以（-1），使不等號(hào)方向改變即可，得 這樣第二個(gè)約束條件也就符合要求。對(duì)于第三個(gè)約束條件，我們可以用小于等于和大于等于兩個(gè)約束條件來(lái)替代它。即有 顯然，這兩個(gè)約束條件與原來(lái)第三個(gè)約束條件是等價(jià)的，我們?cè)侔哑渲械膬蛇叾汲艘裕?1），得,§2 線性規(guī)劃的對(duì)偶問(wèn)

33、題,34,通過(guò)上面的一些變換，我們得到了一個(gè)和原線性規(guī)劃等價(jià)的線性規(guī)劃問(wèn)題： s.t.,§2 線性規(guī)劃的對(duì)偶問(wèn)題,35,這個(gè)求最大值的線性規(guī)劃問(wèn)題的約束條件都取小于等于號(hào)，我們馬上可以寫出其對(duì)偶問(wèn)題： s.t.,§2 線性規(guī)劃的對(duì)偶問(wèn)題,36,這里

34、 和 一樣都是不同的決策變量，為了表示這兩個(gè)決策變量都來(lái)源于原問(wèn)題的第三個(gè)約束條件，記為 。 因?yàn)樵谠搶?duì)偶問(wèn)題中 和 的系數(shù)只相差一個(gè)符號(hào)，我們可以把上面的對(duì)偶問(wèn)題化為： s.t.,§2 線性規(guī)劃的對(duì)偶問(wèn)題,37,,進(jìn)一步，我們可以令

35、 ，這時(shí)當(dāng) 時(shí)， ，當(dāng) 時(shí)， 。這也就是說(shuō)，盡管 但 的取值可以為正，可以為0，可以為負(fù)，即 沒(méi)有非負(fù)限制。 這樣我們把原規(guī)劃的對(duì)偶問(wèn)題化為

36、 s.t. 沒(méi)有限制。 對(duì)照原線性規(guī)劃問(wèn)題，我們可以知

37、道： 當(dāng)原線性規(guī)劃問(wèn)題的第i個(gè)約束條件取等號(hào)時(shí)，則其對(duì)偶問(wèn)題的 i個(gè)決策變量沒(méi)有非負(fù)限制。 如果當(dāng)原線性規(guī)劃問(wèn)題中的第 i個(gè)決策變量 沒(méi)有非負(fù)限制時(shí)，我們也可以用 進(jìn)行替換，這里 ， ，用類似的方法知道其對(duì)偶問(wèn)題中第 i個(gè)約束條件取等號(hào)。,

38、7;2 線性規(guī)劃的對(duì)偶問(wèn)題,38,另外，用大于等于0的兩個(gè)決策變量之差來(lái)代替無(wú)非負(fù)限制的決策變量也是求解含有無(wú)非負(fù)限制的決策變量的線性規(guī)劃問(wèn)題的一種方法。 原線性規(guī)劃問(wèn)題為： s.t. 無(wú)非負(fù)限制。,§2 線性規(guī)劃的對(duì)偶問(wèn)題,39,§3　對(duì)偶規(guī)劃的基本性質(zhì),對(duì)偶規(guī)劃的基本性質(zhì)1．對(duì)稱性

39、。即對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。2．弱對(duì)偶性。即對(duì)于原問(wèn)題（Ⅰ）和對(duì)偶問(wèn)題（Ⅱ）的可行解 都有C ≤bT 。 由弱對(duì)偶性，可得出以下推論：（1）原問(wèn)題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下界；反之對(duì)偶問(wèn)題任一可行解的目標(biāo)函數(shù)值是其原問(wèn)題目標(biāo)函數(shù)值的上界。（2）如原問(wèn)題有可行解且目標(biāo)函數(shù)值無(wú)界（或具有無(wú)界解），則其對(duì)偶問(wèn)題無(wú)可行解；反之對(duì)偶問(wèn)題有可行解且目標(biāo)函數(shù)值無(wú)界，則其原問(wèn)題無(wú)可行解（注意：本

40、點(diǎn)性質(zhì)的逆不成立，當(dāng)對(duì)偶問(wèn)題無(wú)可行解時(shí)，其原問(wèn)題或具有無(wú)界解或無(wú)可行解，反之亦然）。（3）若原問(wèn)題有可行解而其對(duì)偶問(wèn)題無(wú)可行解，則原問(wèn)題目標(biāo)函數(shù)值無(wú)界；反之對(duì)偶問(wèn)題有可行解而其原問(wèn)題無(wú)可行解，則對(duì)偶問(wèn)題的目標(biāo)函數(shù)值無(wú)界。,,,,40,§3　對(duì)偶規(guī)劃的基本性質(zhì),3．最優(yōu)性。如果 是原問(wèn)題(Ⅰ)的可行解， 是對(duì)偶問(wèn)題(Ⅱ)的可行解，并且 C = bT ，則 和 分別為原問(wèn)題(Ⅰ)和對(duì)偶問(wèn)題(

41、Ⅱ)的最優(yōu)解。4．強(qiáng)對(duì)偶性。即若原問(wèn)題(Ⅰ)及其對(duì)偶問(wèn)題(Ⅱ)都有可行解，則兩者都有最優(yōu)解；且它們的最優(yōu)解的目標(biāo)函數(shù)都相等。5．互補(bǔ)松弛性。在線性規(guī)劃問(wèn)題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件取嚴(yán)格等式；反之，如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變量一定為零也即 若yi*>0,則有 若 ，則有yi*=0,,,,,4

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