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