線性規(guī)劃問題解的概念和性質(zhì)-資料下載頁
2025-08-05 10:49本頁面
【正文】 設 Xi∈ En, 實數(shù) μi ≥0,i = 1,2,… , s,且 ∑μi = 1， 則稱 X = μ1X1 + μ2X2 +…+ μsXs 為點 X1， X2， … ， Xs 的一個 凸組合 。 第五節(jié) 線性規(guī)劃問題解的概念和性質(zhì) 線性規(guī)劃的解的性質(zhì) 性質(zhì) 1： LP問題標準型的可行域 R = { X︱ AX=b, X ≥0 } 是凸集。 性質(zhì) 2： LP問題 標準型 的一個基本可行解與可行域 R 的一個極點 互相對應。 性質(zhì) 3： 線性規(guī)劃的基本定理 對于一個給定的標準型 LP問題 標準型 來說： ⑴ 若 標準型 有可行解，則必有基本可行解； ⑵ 若 標準型 有最優(yōu)解，則必有最優(yōu)基本解。 性質(zhì) 4：若 LP問題的可行域 R≠216。, 則 R 至少有一極點。 性質(zhì) 5： LP問題可行域 R 的極點數(shù)目必為有限個。 第五節(jié) 線性規(guī)劃問題解的概念和性質(zhì) 僅就標準形 LP問題說明其合理性。 因 標準型 是一個 m階 n維的 LP問題，則從其系數(shù)陣的n列中取出 m列，所構(gòu)成其 基 的個數(shù)不超過 C m n = n！ m！ (nm)！ ∞ ≤ C m n 基本可行解 的個數(shù) ≤ 基本解 的個數(shù) 而 標準型 問題的 枚舉法 : 當 m=50， n=100時 ，此 時需要求解的 50元 50 階的線性方程組的個數(shù)為 C 50 100 = 100！ 50！ 50！ ≈ 1029 這是一個天文數(shù)字！故需另尋其他有效方法。 13
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1