[科普中國]-基可行解

基可行解即基本可行解的簡稱，是處理線性規(guī)劃的基本概念。滿足非負條件的基本解稱為基可行解。1

基可行解(basic feasible solution)是指，在線性規(guī)劃問題中滿足非負約束條件的基解。線性規(guī)劃問題如果有可行解，則必有基可行解。2

定義LP問題（線性規(guī)劃問題）：或

V: （1）

s.t. （2）

（3）

若rank(A,b)=rank(A)=m,且,則,其中rank(B)=m.

這樣Ax=b可化為 （2）’

其中滿足（2）（3）的x稱為可行解，（2）’中稱B為LP的一個基，其列向量稱為基向量

（2）中稱xB為基變元，xN為非基變元（關(guān)于基B的）

則滿足的基本解稱為基可行解（關(guān)于基B的）

其中基本解是指由（2）’，有,此時。若,則稱x為LP的基本解。

由于基本解,則當(dāng)且僅當(dāng)時，此基本解為基可行解（它對應(yīng)可行域的頂點）

此時，基本解中基變元皆取正值者此解為非退化的；否則（基變元有0者）稱為退化的，顯然當(dāng)，此基可行解是非退化的，否則為退化的。3

性質(zhì)可行解是基可行解的充要條件是它的正分量所對應(yīng)的A中列向量線性無。

x是基可行解的充要條件是x是可行域D的頂點。

一個標(biāo)準形式的LP問題，若有可行解，則至少有一個基可行解。

若標(biāo)準形式的LP問題有有限的最優(yōu)值，則一定存在一個基可行解是最優(yōu)解。

或敘述為：若標(biāo)準形式的LP問題的目標(biāo)函數(shù)有有限的最優(yōu)值，則必可在某個基可行解處達到4

應(yīng)用3. 4.兩個定理具有重要意義，這兩個定理一起被稱為線性規(guī)劃的基本定理。它告訴我們，求解標(biāo)準形式的LP問題，只需在基可行解的集合中進行搜索（如果其目標(biāo)函數(shù)有最優(yōu)值的話），而基可行解的個數(shù)是有限的。單純形法就是根據(jù)線性規(guī)劃的基本定理，給出一定的規(guī)律和步驟，在基可行解的一個子集合中逐步搜索，最終求得最優(yōu)解或判別問題無最優(yōu)解。4

本詞條內(nèi)容貢獻者為:

胡建平 - 副教授 - 西北工業(yè)大學(xué)