[科普中國]-基本最優(yōu)解

基本最優(yōu)解(basic optimal solution)是線性規(guī)劃的重要概念，指線性規(guī)劃問題中使目標(biāo)函數(shù)達(dá)到最優(yōu)值的基可行解。

基本介紹考慮標(biāo)準(zhǔn)型LP問題

設(shè)A是階矩陣，，且A的秩為m。

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

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

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

基向量：基B中的一列即為B的一個(gè)基向量?；?strong>B中共有m個(gè)基向量。

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

基變量：與基B的基向量相應(yīng)的變量稱為B的基變量?；兞抗灿衜個(gè)。

非基變量：與基B的非基向量相應(yīng)的變量稱為B的非基變量，非基變量共有個(gè)。

基本解：對(duì)于基B，令所有非基變量為零，求得滿足式(2)的解，稱為B對(duì)應(yīng)的基本解(basic solution)。

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

基本最優(yōu)解：滿足式(1)的基本可行解稱為基本最優(yōu)解，其對(duì)應(yīng)的基稱為最優(yōu)基。

退化的基本解：若基本解中有基變量為零者，則稱之為退化的基本解。類似地，有退化的基本可行解和退化的基本最優(yōu)解1。

求解方法單純形方法是求解線性規(guī)劃問題的一個(gè)主要方法，構(gòu)成了線性規(guī)劃理論的一個(gè)重要內(nèi)容，其計(jì)算主要是由單純形表來實(shí)現(xiàn)的。

設(shè)線性規(guī)劃目標(biāo)函數(shù)為：

約束條件為：

其矩陣形式為：

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

那么稱，

基B對(duì)應(yīng)的單純形表。

表中第1列第1分量是對(duì)應(yīng)于B基礎(chǔ)解即的目標(biāo)函數(shù)值，其他m個(gè)分量就是對(duì)應(yīng)于B的基礎(chǔ)解中基變量的值。表中第1行除第1分量外，其余n個(gè)分量為檢驗(yàn)數(shù)CBB-1A—C。對(duì)于可行基B(即)的表，如果所有檢驗(yàn)數(shù)非正，那么這一基礎(chǔ)可行解就是最優(yōu)解。第1個(gè)可行基一般取單位矩陣，這只要在約束方程兩邊同乘以+1或-1，并引入和方程個(gè)數(shù)相同的人工變量，那么這m個(gè)人工變量對(duì)應(yīng)的系數(shù)矩陣就是單位矩陣Im，且滿足。

如果有一個(gè)檢驗(yàn)數(shù)大于零，那么就需要換基迭代，其步驟是：(1)求主元素。在所有中，選最靠左的一個(gè)，記為b0s，其對(duì)應(yīng)的非基變量xs，對(duì)應(yīng)于向量，用P's列正的各分量bis分別去除bi0，，稱brs為主元素。(2)對(duì)B的單純形表進(jìn)行變換使P's變?yōu)閱挝幌蛄?第r個(gè)分量為1，其余為0)，將P's與第r列對(duì)調(diào)，即將一個(gè)新基的單純形表。那么換基后目標(biāo)函數(shù)值不會(huì)增加，只有在下述情形原問題無最優(yōu)解：檢驗(yàn)數(shù)b0j中有正數(shù)，且無對(duì)應(yīng)的列向量是負(fù)向量2。

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

王沛 - 副教授、副研究員 - 中國科學(xué)院工程熱物理研究所