正文內容

4線性規劃對偶問題-文庫吧

2026-07-07 19:07 本頁面

【正文】 5對偶性與最優性l 研究一對相互對偶的線性規劃問題它們最優解之間的關系。l 先考慮對稱形式的對偶問題，再考慮標準形式的對偶問題。16弱對偶性：弱對偶性：17最優性l 若 X＊， Y＊分別是（ LP）和（ LD）的可行解，且 CTX＊＝ bTY＊，則 X＊， Y＊分別是（ LP）和（ LD）的最優解。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）有最優解 X * ，則（ LD）也有最優解Y * ，且有 X * TV * ＝ 0， Y * TU * ＝ 0l 其中 V * ＝ ATY * － C ， U * ＝ b － AX * 。l 証：若 y＊， Y＊分別是（ LP）和（ LD）的最優解，則 CTX*=bTY*.23將它們化成標準形式，并求出最優解。2425(LD)的剩余變量：(LP)的松弛變量：它們的最優解滿足互補松弛性質 !26對偶問題最優解的性質l 對稱形式：l 若（ LP）有最優解 X＊，則對偶問題（ LD）也有最優解 Y＊，且 y＊是（ LP）最優單純形表中松弛變量 V下的檢驗數的負值； X＊是（ LD）最優單純形表中剩余變量 U下的檢驗數的負值。27用對偶單純形法求解 (LD),列出初始單純形表如下：28最優解：剩余變量 y3,y4下的檢驗數： 24, 8最優單純形表可求得最優解如下：對偶問題的最優解：y1=24 ,y2=829對偶問題（ LP）的初始單純形表如下：30最優解：松弛變量的檢驗數：2 , 231標準形式的對偶問題最優解的性質若標準形式（ LP）有基本最優解 y＊，且：則 (LD)的最優解為：標準形式的對偶問題：（ LP）中基本最優解y*的檢驗數？32標準形

點擊復制文檔內容

研究報告相關推薦

4線性規劃對偶問題-文庫吧

線性規劃二-資料下載頁

eqxaaa線性規劃-資料下載頁

第4章非線性規劃-資料下載頁

面粉采購問題線性規劃-資料下載頁

簡單的線性規劃問題-資料下載頁

線性規劃二一-資料下載頁

lttaaa線性規劃-資料下載頁

auvaaa線性規劃-資料下載頁

ctnaaa線性規劃-資料下載頁

[ppt模板]線性規劃-資料下載頁

線性規劃ppt課件-資料下載頁

線性規劃ppt課件-資料下載頁

線性規劃問題解的概念和性質-資料下載頁

利用excel求解線性規劃問題-資料下載頁

高三數學簡單的線性規劃問題-資料下載頁

4線性規劃對偶問題(專業版)

4線性規劃對偶問題(留存版)

4線性規劃對偶問題-文庫吧

4線性規劃對偶問題-wenkub