運籌學 ( 對偶問題及性質).ppt

1、Chapter2 對偶理論 ( Duality Theory ),線性規(guī)劃的對偶模型 對偶性質 對偶問題的經(jīng)濟解釋影子價格 對偶單純形法 靈敏性分析,本章主要內容：,線性規(guī)劃的對偶模型,設某工廠生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)中需4種設備按A，B，C，D順序加工，每件產(chǎn)品加工所需的機時數(shù)、每件產(chǎn)品的利潤值及每種設備的可利用機時數(shù)列于下表 ：,產(chǎn)品數(shù)據(jù)表,問：充分利用設備機時，工廠應生產(chǎn)甲和乙型產(chǎn)品各多少件才能獲得最大利潤？,1. 對偶問題的現(xiàn)實來源,解：設甲、乙型產(chǎn)品各生產(chǎn)x1及x2件，則數(shù)學模型為：,反過來問：若廠長決定不生產(chǎn)甲和乙型產(chǎn)品，決定出租機器用于接受外加工，只收加工費，那么種機器的機時如何

2、定價才是最佳決策？,在市場競爭的時代，廠長的最佳決策顯然應符合兩條： （1）不吃虧原則。即機時定價所賺利潤不能低于加工甲、乙型產(chǎn)品所獲利潤。由此原則，便構成了新規(guī)劃的不等式約束條件。 （2）競爭性原則。即在上述不吃虧原則下，盡量降低機時總收費，以便爭取更多用戶。,設A、B、C、D設備的機時價分別為y1、y2、y3、y4，則新的線性規(guī)劃數(shù)學模型為：,2. 原問題與對偶問題的對應關系,原問題 （對偶問題）,對偶問題 （原問題）,線性規(guī)劃的對偶模型,（1）對稱形式,特點：目標函數(shù)求極大值時，所有約束條件為號，變量非負;目標函數(shù)求極小值時，所有約束條件為號，變量非負.,已知 (LP)，寫出 (DP),

3、單純形法計算的矩陣描述(nm),若初始矩陣中變量 xj的系數(shù)向量為Pj, 迭代后為Pj, 則有 Pj=B-1 Pj 當B為最優(yōu)基時，應有 令Y=CBB-1, 則,例2.1 寫出線性規(guī)劃問題的對偶問題,解：首先將原問題變形為對稱形式,(2) 非對稱形式的對偶規(guī)劃 一般稱不具有對稱形式的一對線性規(guī)劃為非對稱形式的對偶規(guī)劃。 對于非對稱形式的規(guī)劃，可以按照下面 的對應關系直接給出其對偶規(guī)劃。 （1）將模型統(tǒng)一為“max，”或“min，” 的形式，對于其中的等式約束按下面（2）、（3）中的方法處理； （2）若原規(guī)劃的某個約束條件為等式約束，則在對偶規(guī)劃中與此約束對應的那個變量取值沒有非負限制；,（3）

4、若原規(guī)劃的某個變量的值沒有非負限制，則在對偶問題中與此變量對應的那個約束為等式。,1.線性規(guī)劃對偶問題,線性規(guī)劃的對偶模型,例2.2 寫出下列線性規(guī)劃問題的對偶問題.,解：原問題的對偶問題為,對偶性質,例2.3 分別求解下列2個互為對偶關系的線性規(guī)劃問題,分別用單純形法求解上述2個規(guī)劃問題，得到最終單純形表如下表：,對偶性質,原問題最優(yōu)表,對偶問題最優(yōu)表,對偶性質,原問題與其對偶問題的變量與解的對應關系： 在單純形表中，原問題的松弛變量對應對偶問題的變量，對偶問題的剩余變量對應原問題的變量。,對偶問題的基本性質,(1) 對稱性：對偶問題的對偶是原問題 ; (2)弱對偶性：若X是原問題的可行解，

5、Y是對偶問題的可行解。則存在CXYb; (3) 無界性：若原問題(對偶問題)為無界解，則其對偶問題(原問題)無可行解; (4) 可行解是最優(yōu)解時的性質 ; (5) 對偶定理：若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解；且目標函數(shù)值相等; (6) 互補松弛性 ; (7) 原問題檢驗數(shù)與對偶問題解的關系。,對偶性質,性質1 (對稱性)：對偶問題的對偶是原問題,對偶性質,性質2 (弱對偶性) 設 和 分別是問題(LP)和(DP)的可行解，則必有,推論1: 原問題任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值的下界；反之，對偶問題任意可行解的目標函數(shù)值是其原問題目標函數(shù)值的上界。,性質3 (無界性): 在

6、一對對偶問題（P）和（D）中，若其中一個問題可行但目標函數(shù)無界，則另一個問題無可行解；反之不成立。這也是對偶問題的無界性。,從兩圖對比可明顯看到原問題無界，其對偶問題無可行解,對偶性質,性質4 (最優(yōu)性定理) 如果 是原問題的可行解， 是其對偶問題的可行解，并且:,則 是原問題的最優(yōu)解， 是其對偶問題的最優(yōu)解。,對偶性質,性質5 (強對偶性)：若原問題具有最優(yōu)解，則對偶問題也具有最優(yōu)解，且它們最優(yōu)解的目標函數(shù)值相等。,性質6 (互補松弛性)：在線性規(guī)劃問題的最優(yōu)解中，如果對應某一約束條件的對偶變量值為非零，則該約束條件取嚴格等式；反之如果約束條件取嚴格不等式，則其對應的對偶變量一定為零. 即Y*XS=0，YSX*=0,對偶性質,例2.4 已知線性規(guī)劃,的最優(yōu)解是X=(6,2,0)T,求其對偶問題的最優(yōu)解Y。,解：寫出原問題的對偶問題，即,標準化,設對偶問題最優(yōu)解為Y(y1，y2),因為X10，X20，所以由互補松弛性定理可知， 對偶問題的第一、二個約束的松弛變量等于零，即