孫祥凱+唐莉萍

收稿日期：2015-11-10

基金項目：重慶市教委研究項目（KJ1500626）。

作者簡介：孫祥凱 （1984— ），男，山東青州人，副教授，博士后，主要從事最優(yōu)化理論與方法以及教學方法的研究。

運籌學課程是經管類本科生的必修課程，而線性規(guī)劃是運籌學中的一個重要分支。為了讓初學者對線性規(guī)劃問題的解概念有更清晰的認識和理解，本文將通過實例對解概念進行講解。因為可行解、可行域、最優(yōu)解以及最優(yōu)值這幾個概念理解相對比較容易，所以本文將重點通過實例講解線性規(guī)劃問題的基、基向量、基變量、非基變量、基解、基可行解以及可行基矩陣這幾個概念。

1.線性規(guī)劃問題模型及相關概念

線性規(guī)劃問題的標準形式為

max（min）Z=CX

AX=B

X≥0

其中價值系數(shù)C=（c1c2…cn）， 系數(shù)矩陣：

a11 ? … ? a1n ? ? ? ? ? ? ? ? ? ? ? ? x1 ? ? ? ? ? ? ? ? ? ? ? ? ?b1

A= ? ? ? ? ? ? ? ? ? ?，X = ? ? ? ?，B = ? ? ? ? 。

am1 ?… ? amn ? ? ? ? ? ? ? ? ? ? ? ?xn ? ? ? ? ? ? ? ? ? ? ? ? ?bm

下面首先簡單回顧一下相關概念。課本中相關概念雖然表達十分嚴謹，但是對經管類文科生來說理解起來相對困難。為便于理解，本文用最直白的語言來重新描述這些概念。[1][2]

（1）基矩陣的概念。教材中第22頁中描述的是系數(shù)矩陣A中的非奇異子矩陣，稱為線性規(guī)劃問題的一個基矩陣，簡稱基。實際上，基矩陣就是系數(shù)矩陣中行列式不等于零的子陣。

（2）基向量的概念。將基矩陣按列分塊， 每一列稱為基向量。通俗地來說，基向量就是系數(shù)矩陣中行列式不等于零的子陣的每一列。特別的、不同的基矩陣對應不同的基向量。

（3）基變量與非基變量的概念。與基向量所對應的變量稱為基變量，剩下的變量稱為非基變量。通俗地來講，基變量就是系數(shù)矩陣中行列式不等于零的子陣的每一列所對應的變量。剩下的變量當然是非基變量。此處大家也要注意，由于不同的基矩陣對應不同的基向量，所以基變量與基矩陣也是一一對應的。因此一個變量在不同的基矩陣里有可能是基變量，也有可能是非基變量。

（4）基解的概念。令非基變量等于0，所得到的解，稱為基解。通俗地來講，基解就是在約束條件中令非基變量等于0，對其求解所得解。

（5）基可行解的概念。若基解還是可行的，即滿足非負性條件，則稱為基可行解。通俗地來講，基可行解就是要保證每一個變量都要不小于零。

（6）可行基矩陣的概念。與基可行解所對應的基矩陣，稱為可行基矩陣。

2.實例分析

例，已知某線性規(guī)劃問題約束條件

x1+2x2+3x3=1

2x1+x2+3x4=3

x1，…，x4≥0

試列舉出其基矩陣、基向量、基變量、非基變量、基解、基可行解以及可行基矩陣。

解：按照線性規(guī)劃標準形式可得

1 ? ?2 ? ?3 ? ?0

2 ? ?1 ? ?0 ? ?3

由于該系數(shù)矩陣的任意二階子矩陣均是可逆的，即行列式不等于零，所以該線性規(guī)劃問題的基矩陣共有六個，分別是：

1 ? 2

2 ? 1 ? ， ? ? ? ? ， ? ? ? ? ?。

1 ? 0

2 ? 3 ? ， ? ? ? ? ， ? ? ? ? ?。

本文僅對第一個基矩陣進行詳細分析。

對于基矩陣 ? ? ? ? ?， 將該矩陣按列分塊，所以基向量為 ? ? ?與 ? ? 。因為基向量 ?和 ? ? ?在約束條件中對應的變量分別為x1與x2，所以基變量為x1與x2，從而非基變量為x3和x4。令非基變量x3=x4=0，并將其代入約束條件中易得x1= ? ?，x2=- ? 。從而基解為 ? ? ? ? ? ? ? ? ? ? 。由于x2=- ? ? ? ?< 0 ? ?不滿足非負性條件，所以 ? ? ? ? ? ? ? ? ? ? ? ? 不是基可行解。從而此基矩陣不是可行基矩陣。

通過上述例子，不僅能夠很容易地理解線性規(guī)劃問題的解的這幾個概念，而且可以得到這些概念之間的如下關系：①系數(shù)矩陣中可找出若干個基矩陣;②每個基矩陣都對應于一個基解;③非負的基解就是基可行解;④基可行解所對應的基矩陣就是可行基矩陣。

本文對線性規(guī)劃問題的解的相關概念以及它們之間的相互關系進行了分析和講解，以消除初學者對這些概念之間的困惑，加深初學者對線性規(guī)劃問題解概念的深入認識。

參考文獻：

[1]《運籌學》教材編寫組.運籌學[M].北京：清華大學出版社，2012.

[2]胡運權. 運籌學基礎及運用[M]. 北京： 高等教育出版社， 2008.