複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/基本可行解/7150250
複製
複製成功

基本可行解

鎖定
基本可行解(basic feasible solution)亦稱可行點或允許解，是線性規劃的重要概念。在線性規劃問題中，滿足非負約束條件的基本解，稱基本可行解，簡稱基可行解。線性規劃問題如果有可行解，則必有基可行解，可行解是基可行解的充分必要條件為：它的非零分量所對應的係數矩陣列向量是線性無關的。基本可行解與可行域中的極點相對應，為有限個。若存在有界最優解，則至少有一個基本可行解為最優解 [1]  。
中文名
基本可行解
外文名
basic feasible solution
所屬領域
運籌學（線性規劃問題）
相關概念
基本解、非負約束、線性無關等
別    名
可行點或允許解
定    義
在線性規劃問題中，滿足非負約束條件的基本解

目錄

  1. 1 基本介紹
  2. 2 基本解的產生和轉換
  1. 3 基本可行解的產生與轉換條件
  2. 4 基本可行解轉換的最優性條件
  1. 5 基本可行解轉換的非負性條件

基本可行解基本介紹

線性規劃中的約束條件除變量非負性限制外都採用等式約束，線性規劃問題的一般形式為
式中
AX=B稱為約束方程，A為係數矩陣，B為常數向量，
稱為變量非負約束。一般情況下，應有m<n。此時約束方程有無窮多組解。線性規劃就是從這無窮多組解中尋找一組使目標函數值最小的最優解。
線性規劃問題的約束條件包括約束方程和變量非負約束兩部分，對應的解也分基本解、基本可行解和最優解。其中基本解是隻滿足約束方程的解；基本可行解是同時滿足約束方程和變量非負約束的解。基本可行解中能使目標函數值最小的稱為最優解。 [2] 

基本可行解基本解的產生和轉換

約束方程實際上是一個包含n個變量和m個方程的線性方程組，若令變量中的（n—m）個變量等於零 [3]  ，求解方程組得到的解稱為線性規劃的基本解。
在一個基本解中，稱這
個為零的變量為非基本變量，稱另外的m個變量為基本變量。
係數矩陣A和常數向量B合併組成增廣矩陣：
對此增廣矩陣進行一系列初等行變換，並進行m次消元，可將上述的增廣矩陣和約束方程變為
由此不難看出，線性規劃問題的一個基本解為
若變換後的常數項均為非負值，即
，則此基本解也是一個基本可行解。 [2] 

基本可行解基本可行解的產生與轉換條件

基本可行解是同時滿足約束方程和變量非負約束的解。
根據線性規劃問題的不同特徵，一個初始基本可行解的獲得可分為下列兩種情況：
(1)如果除變量非負約束之外的約束條件全部是“≤”的不等式約束，而且對應的常數向量中的元素均為正數，此時只要引入鬆弛變量，並以鬆弛變量為基本變量，得到的解自然就是一個基本可行解。
(2)如果除變量非負約束之外的約束條件中還包含等式約束，此時可以在各個等式約束中分別引入一個與鬆弛變量類似的變量，稱為人工變量，然後建立一個輔助規劃問題，求解此輔助規劃問題，就可以得到一個基本可行解。
基本可行解之間的相互轉換採用消元法，轉換時注意以下幾個問題：
(1)變換後所得解的目標函數值必須下降。若下降量最大，此條件稱為最優化條件。
(2)變換後仍然是一個基本可行解，即常數項的值大於等於零，此條件稱為非負性條件。
(3)最優解的判斷。
滿足上述條件的變換，從根本上説就是要在非基本變量所對應的矩陣元素中找到一個合適的變換主元
。 [2] 

基本可行解基本可行解轉換的最優性條件

選定主元列的方法可概括為
式中，
稱為第
列的判別數。
如果
，對應的基本可行解就是要找的最優解。 [2] 

基本可行解基本可行解轉換的非負性條件

按下式選取主元，並進行消元變換：
這樣，就可以保證變換後的常數項仍為非負，保證由一個基本可行解變換得到的解仍然是一個基本可行解。 [2] 
參考資料
  • 1.    《數學辭海》編輯委員會．數學辭海·第五卷：中國科學技術出版社，2002
  • 2.    金全意．優化設計學習與典型題輔導：清華大學出版社，2013.07
  • 3.    趙興仁主編；孫景武等著. 建築安裝工程經營學[M]. 北京：科學技術文獻出版社, 1993.12.P196.