基本最優解

基本最優解(basic optimal solution)是線性規劃的重要概念，指線性規劃問題中使目標函式達到最優值的基可行解。

基本介紹

• 中文名：基本最優解
• 外文名：basic optimal solution
• 所屬學科：數學
• 所屬問題：線性規劃
• 簡介：使目標函式達到最優值的基可行解

基本介紹

考慮標準型LP問題

設A是階矩陣，，且A的秩為m。

可行解：滿足上述約束條件(2)、(3)的向量x稱為可行解(feasible solution)。

最優解：滿足式(1)的可行解稱為最優解(optimal solution)。

基：A中任何一組m個線性無關的列向量構成的子矩陣B，稱為該問題的一個基(basis)，即B為A的m×m階非奇異子矩陣。

基向量：基B中的一列即為B的一個基向量。基B中共有m個基向量。

非基向量：矩陣A中基B之外的一列即為B的一個非基向量。A中共有個非基向量。

基變數：與基B的基向量相應的變數稱為B的基變數。基變數共有m個。

非基變數：與基B的非基向量相應的變數稱為B的非基變數，非基變數共有個。

基本解：對於基B，令所有非基變數為零，求得滿足式(2)的解，稱為B對應的基本解(basic solution)。

基本可行解：滿足式(3)的基本解稱為基本可行解，其對應的基稱為可行基。

基本最優解：滿足式(1)的基本可行解稱為基本最優解，其對應的基稱為最優基。

退化的基本解：若基本解中有基變數為零者，則稱之為退化的基本解。類似地，有退化的基本可行解和退化的基本最優解。

求解方法

單純形方法是求解線性規劃問題的一個主要方法，構成了線性規劃理論的一個重要內容，其計算主要是由單純形表來實現的。

設線性規劃目標函式為：

約束條件為：

其矩陣形式為：

令，其中B是秩為m的m階方陣，

那么稱，

基B對應的單純形表。

表中第1列第1分量是對應於B基礎解即的目標函式值，其他m個分量就是對應於B的基礎解中基變數的值。表中第1行除第1分量外，其餘n個分量為檢驗數CBB^-1A—C。對於可行基B(即)的表，如果所有檢驗數非正，那么這一基礎可行解就是最優解。第1個可行基一般取單位矩陣，這隻要在約束方程兩邊同乘以+1或-1，並引入和方程個數相同的人工變數，那么這m個人工變數對應的係數矩陣就是單位矩陣I_m，且滿足。

如果有一個檢驗數大於零，那么就需要換基疊代，其步驟是：(1)求主元素。在所有中，選最靠左的一個，記為b_0s，其對應的非基變數x_s，對應於向量，用P'_s列正的各分量b_is分別去除b_i0，，稱b_rs為主元素。(2)對B的單純形表進行變換使P'_s變為單位向量(第r個分量為1，其餘為0)，將P'_s與第r列對調，即將一個新基的單純形表。那么換基後目標函式值不會增加，只有在下述情形原問題無最優解：檢驗數b_0j中有正數，且無對應的列向量是負向量。