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

孫祥凱+唐莉萍

收稿日期：2015-11-10

基金項(xiàng)目：重慶市教委研究項(xiàng)目（KJ1500626）。

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

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

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

線性規(guī)劃問題的標(biāo)準(zhǔn)形式為

max（min）Z=CX

AX=B

X≥0

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

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

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

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

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

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

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

（3）基變量與非基變量的概念。與基向量所對應(yīng)的變量稱為基變量，剩下的變量稱為非基變量。通俗地來講，基變量就是系數(shù)矩陣中行列式不等于零的子陣的每一列所對應(yīng)的變量。剩下的變量當(dāng)然是非基變量。此處大家也要注意，由于不同的基矩陣對應(yīng)不同的基向量，所以基變量與基矩陣也是一一對應(yīng)的。因此一個變量在不同的基矩陣?yán)镉锌赡苁腔兞?，也有可能是非基變量?/p>

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

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

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

2.實(shí)例分析

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

x1+2x2+3x3=1

2x1+x2+3x4=3

x1，…，x4≥0

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

解：按照線性規(guī)劃標(biāo)準(zhǔn)形式可得

1 ? ?2 ? ?3 ? ?0

2 ? ?1 ? ?0 ? ?3

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

1 ? 2

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

1 ? 0

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

本文僅對第一個基矩陣進(jìn)行詳細(xì)分析。

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

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

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

參考文獻(xiàn)：

[1]《運(yùn)籌學(xué)》教材編寫組.運(yùn)籌學(xué)[M].北京：清華大學(xué)出版社，2012.

[2]胡運(yùn)權(quán). 運(yùn)籌學(xué)基礎(chǔ)及運(yùn)用[M]. 北京： 高等教育出版社， 2008.