運籌學課程中線性規(guī)劃問題解的概念教學探討

收稿日期：2015-11-10

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

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

運籌學課程是經(jīng)管類本科生的必修課程，而線性規(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

下面首先簡單回顧一下相關概念。課本中相關概念雖然表達十分嚴謹，但是對經(jīng)管類文科生來說理解起來相對困難。為便于理解，本文用最直白的語言來重新描述這些概念。[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.