基本最優解

基本最優解

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

基本介紹

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

基本介紹

考慮標準型LP問題
A
階矩陣,
,且A的秩為m。
可行解:滿足上述約束條件(2)、(3)的向量x稱為可行解(feasible solution)。
最優解:滿足式(1)的可行解稱為最優解(optimal solution)。
基:A中任何一組m個線性無關列向量構成的子矩陣B,稱為該問題的一個基(basis),即BA的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個分量為檢驗數CBBA—C。對於可行基B(即
)的表,如果所有檢驗數非正,那么這一基礎可行解就是最優解。第1個可行基一般取單位矩陣,這隻要在約束方程兩邊同乘以+1或-1,並引入和方程個數相同的人工變數,那么這m個人工變數對應的係數矩陣就是單位矩陣Im,且滿足
如果有一個檢驗數大於零,那么就需要換基疊代,其步驟是:(1)求主元素。在所有
中,選最靠左的一個,記為b0s,其對應的非基變數xs,對應於向量
,用P's列正的各分量bis分別去除bi0
,稱brs為主元素。(2)對B的單純形表進行變換使P's變為單位向量(第r個分量為1,其餘為0),將P's與第r列對調,即將一個新基的單純形表。那么換基後目標函式值不會增加,只有在下述情形原問題無最優解:檢驗數b0j中有正數,且無對應的列向量是負向量。

相關詞條

熱門詞條

聯絡我們