4線性規(guī)劃對偶問題-文庫吧
2025-07-21 19:07 本頁面
【正文】 5對偶性與最優(yōu)性l 研究一對相互對偶的線性規(guī)劃問題它們最優(yōu)解之間的關系。l 先考慮對稱形式的對偶問題，再考慮標準形式的對偶問題。16弱對偶性：弱對偶性：17最優(yōu)性l 若 X＊ ， Y＊ 分別是（ LP）和（ LD）的可行解，且 CTX＊ ＝ bTY＊ ，則 X＊ ， Y＊ 分別是（ LP）和（ LD）的最優(yōu)解。l 證：對（ LP）的任一可行解 X， bTY＊ ? CTX， ∴ bTY＊ ? CTX＊ 這說明 CTX＊ 是 bTY的一個下界?！‘敗?bTY＊ ＝ CTX＊ 時，目標函數 CTX達到最大值。18無界性l 若（ LP）的目標函數 (求 Max)在可行域內無上界，則對偶問題（ LD）是不可行的。l 若對偶問題（ LD）的目標函數 (求 Min)在可行域內無下界，則原問題（ LP）是不可行的。l 反證法：若（ LD）是可行的，即存在可行解Y，由弱對偶性， CTX? bTY此即說明（ LP）的目標函數有上界。19無界性l 該定理的逆定理不成立。l 有可能（ LP）和（ LD）都是不可行的。(LP)無界， (LD)不可行。20(LP)和 (LD)都是不可行的。無界性的逆定理不成立21互補松弛性質22互補松弛性質l 若（ LP）有最優(yōu)解 X * ，則（ LD）也有最優(yōu)解Y * ，且有 X * TV * ＝ 0， Y * TU * ＝ 0l 其中 V * ＝ ATY * － C ， U * ＝ b － AX * 。l 証：若 y＊ ， Y＊ 分別是（ LP）和（ LD）的最優(yōu)解，則 CTX*=bTY*.23將它們化成標準形式，并求出最優(yōu)解。2425(LD)的剩余變量：(LP)的松弛變量：它們的最優(yōu)解滿足互補松弛性質 !26對偶問題最優(yōu)解的性質l 對稱形式：l 若（ LP）有最優(yōu)解 X＊ ， 則對偶問題（ LD）也有最優(yōu)解 Y＊ ， 且 y＊ 是（ LP）最優(yōu)單純形表中松弛變量 V下的檢驗數的負值； X＊ 是（ LD）最優(yōu)單純形表中剩余變量 U下的檢驗數的負值。27用對偶單純形法求解 (LD),列出初始單純形表如下：28最優(yōu)解：剩余變量 y3,y4下的檢驗數： 24, 8最優(yōu)單純形表可求得最優(yōu)解如下：對偶問題的最優(yōu)解 ：y1=24 ,y2=829對偶問題（ LP）的初始單純形表如下：30最優(yōu)解：松弛變量的檢驗數：2 , 231標準形式的對偶問題最優(yōu)解的性質若標準形式（ LP）有基本最優(yōu)解 y＊ ，且：則 (LD)的最優(yōu)解為：標準形式的對偶問題：（ LP）中基本最優(yōu)解y*的檢驗數？32標準形
研究報告相關推薦
鄂ICP備17016276號-1