基本可行解

基本介紹

線性規劃中的約束條件除變數非負性限制外都採用等式約束，線性規劃問題的一般形式為

式中

AX=B稱為約束方程，A為係數矩陣，B為常數向量，

稱為變數非負約束。一般情況下，應有m<n。此時約束方程有無窮多組解。線性規劃就是從這無窮多組解中尋找一組使目標函式值最小的最優解。

線性規劃問題的約束條件包括約束方程和變數非負約束兩部分，對應的解也分基本解、基本可行解和最優解。其中基本解是只滿足約束方程的解；基本可行解是同時滿足約束方程和變數非負約束的解。基本可行解中能使目標函式值最小的稱為最優解。

約束方程實際上是一個包含n個變數和m個方程的線性方程組，若令變數中的n—m個等於零，求解方程組得到的解稱為線性規劃的基本解。

在一個基本解中，稱這

個為零的變數為非基本變數，稱另外的m個變數為基本變數。

係數矩陣A和常數向量B合併組成增廣矩陣：

對此增廣矩陣進行一系列初等行變換，並進行m次消元，可將上述的增廣矩陣和約束方程變為

由此不難看出，線性規劃問題的一個基本解為

若變換後的常數項均為非負值，即

，則此基本解也是一個基本可行解。

基本可行解是同時滿足約束方程和變數非負約束的解。

根據線性規劃問題的不同特徵，一個初始基本可行解的獲得可分為下列兩種情況：

(1)如果除變數非負約束之外的約束條件全部是“≤”的不等式約束，而且對應的常數向量中的元素均為正數，此時只要引入鬆弛變數，並以鬆弛變數為基本變數，得到的解自然就是一個基本可行解。

(2)如果除變數非負約束之外的約束條件中還包含等式約束，此時可以在各個等式約束中分別引入一個與鬆弛變數類似的變數，稱為人工變數，然後建立一個輔助規劃問題，求解此輔助規劃問題，就可以得到一個基本可行解。

基本可行解之間的相互轉換採用消元法，轉換時注意以下幾個問題：

(1)變換後所得解的目標函式值必須下降。若下降量最大，此條件稱為最最佳化條件。

(2)變換後仍然是一個基本可行解，即常數項的值大於等於零，此條件稱為非負性條件。

(3)最優解的判斷。

滿足上述條件的變換，從根本上說就是要在非基本變數所對應的矩陣元素中找到一個合適的變換主元

。