范 靜

（上海第二工業(yè)大學(xué)理學(xué)院，上海 201209）

高等代數(shù)在線性規(guī)劃問題求解中的應(yīng)用

范 靜

（上海第二工業(yè)大學(xué)理學(xué)院，上海 201209）

高等代數(shù)課程是數(shù)學(xué)類本科階段最基本的核心課程之一，不僅是初等代數(shù)的延拓，也是后續(xù)課程——運籌學(xué)，尤其是線性規(guī)劃部分的基礎(chǔ)。運用高等代數(shù)知識求解了線性規(guī)劃問題：利用線性規(guī)劃問題標準型的線性約束條件是線性方程組的特點，從線性方程組的角度分析了可行解與最優(yōu)解；利用線性規(guī)劃問題標準型的矩陣形式，根據(jù)矩陣的知識推出基可行解與目標函數(shù)值的表達式，以及最優(yōu)解的判別準則，并討論了矩陣初等變換與單純形法的聯(lián)系。同時通過一個典型實例說明了以上各分析的正確性。

高等代數(shù)；線性規(guī)劃；矩陣；線性方程組

0 引言

高等代數(shù)是用嚴密的邏輯推理方法來建立代數(shù)系統(tǒng)的理論體系，用公理化方法來統(tǒng)領(lǐng)不同的代數(shù)系統(tǒng)，用結(jié)構(gòu)化方法來研究代數(shù)系統(tǒng)的內(nèi)部結(jié)構(gòu)的一門課程[1-2]，其概念具有高度的抽象性，定理具有高度的概括性。它與其他科目的關(guān)聯(lián)也十分緊密，文獻[3-5]分別研究了高等代數(shù)與數(shù)學(xué)分析、概率論以及數(shù)學(xué)建模課程的內(nèi)在聯(lián)系。這里，本文研究高等代數(shù)與運籌學(xué)，特別是線性規(guī)劃問題的密切聯(lián)系。運籌學(xué)課程的主要任務(wù)是使學(xué)生理解優(yōu)化決策的思想，在掌握基本理論的基礎(chǔ)上，具備解決優(yōu)化問題的能力。高等代數(shù)是運籌學(xué)的先修課程，雖然表面上兩者是獨立的知識體系，解題方法也有差異，但在很多方面兩者卻是相互滲透、彼此相通的。本文對高等代數(shù)方法在線性規(guī)劃問題求解中的應(yīng)用進行了探討，希望能提高高等代數(shù)與運籌學(xué)的教學(xué)與研究水平。

線性規(guī)劃的數(shù)學(xué)模型的標準形式[6]為

利用向量符號可表述為

利用矩陣符號可表達為

其中，

向量Pj對應(yīng)的決策變量為。一般情況下，m

本文僅討論線性規(guī)劃問題可行域有界，即最優(yōu)解存在的情況。由于線性規(guī)劃問題的可行解是滿足所有約束條件的解，且最優(yōu)解必是可行解，因此，有必要從線性規(guī)劃問題可行解入手，研究它的最優(yōu)解。

1 利用線性方程組的知識求解線性規(guī)劃問題

根據(jù)高等代數(shù)的知識，(1)式或(2)式中的等式約束即為線性方程組。因而，滿足非負條件的線性方程組的解均為線性規(guī)劃問題的可行解。

1.1 線性規(guī)劃問題的可行解

根據(jù)m=r( A)≤r( A, b)≤min{m, n+1}=m ，可得r( A, b)=r( A)=m

為了表示線性規(guī)劃問題的可行解，需要先表示約束方程組的解。由(2)式得

將約束方程組的增廣矩陣經(jīng)過有限次的初等行變換，將Pj轉(zhuǎn)化為ej(j=1,2,…,m)，這里，

1.2 線性規(guī)劃問題的最優(yōu)解

眾所周知，線性方程組若有無窮多解，其自由未知量的組合至多有種，按照如上方法可得到個基解。除去不滿足非負條件的解，即得到基可行解。進一步地，線性規(guī)劃問題的可行域?qū)嵸|(zhì)上是由基可行解的連線構(gòu)成的凸集。

根據(jù)運籌學(xué)知識，若線性規(guī)劃問題存在最優(yōu)解，則一定可以在某基可行解處得到。因而，只需比較所有基可行解的目標函數(shù)值即可得到最優(yōu)解。

1.3 實例說明

由于含有2個決策變量的線性規(guī)劃問題可以通過平面圖形直觀地觀察其可行域，因此，本文選用以下線性規(guī)劃問題進行具體說明。

對于線性規(guī)劃問題（P）

其標準型記為（SP）

表1 6組不同的基解Tab. 1 Six different basic solutions

由圖1可得，基可行解對應(yīng)點O，A，B及C連線形成的四邊形區(qū)域即為可行域。這也將高等代數(shù)問題中線性方程組的無窮多解進行了圖形化表示。進而，比較四個點O，A，B及C的目標函數(shù)值，即得B點對應(yīng)的解為最優(yōu)解，最優(yōu)值為46/3。

圖1 問題（P）的可行域及基解Fig. 1 The feasible region and the fundamental solutions of problem (P)

2 利用矩陣的知識求解線性規(guī)劃問題

根據(jù)高等代數(shù)中分塊矩陣的知識，由線性規(guī)劃問題的矩陣表達式(3)可直接得到基可行解及目標函數(shù)值的計算表達式。

2.1 線性規(guī)劃問題的基可行解及目標函數(shù)值

將約束方程組的系數(shù)矩陣A中除B之外的子矩陣記為N，則A=(B, N)，且N是非基變量的系數(shù)矩陣。將變量矩陣X相應(yīng)地劃分為 (XB, XN)T，同時將目標函數(shù)的系數(shù)C劃分為(CB,CN)，分別對應(yīng)基變量與非基變量。此時，線性規(guī)劃問題的矩陣形式(3)可進一步地表示為

將其中的等式約束移項后，得到BXB=b?NXN。由于B非奇異，可將等式兩邊左乘B?1，故得到基可行解的表達式(6)：

帶入(5)式中的目標函數(shù)，得到目標函數(shù)值的計算表達式(7)：

若非基變量X=O，可得到一個可行解X = (XB, XN)T= (B?1b, O)T，這時目標函數(shù)z=C B?1b。若C?C B?1N

N

B NB的某些分量大于零，則可通過增加XN相應(yīng)分量的取值而得到更大的目標函數(shù)值。因此，若取恰當?shù)幕仃嘊，使得CN?CBB?1N的所有分量均小于等于零，則對應(yīng)可行解為最優(yōu)解。這個結(jié)論與運籌學(xué)的最優(yōu)解的判別準則不謀而合。在運籌學(xué)中，CN?CBB?1N的各分量稱為對應(yīng)非基變量的檢驗數(shù)。當檢驗數(shù)存在正數(shù)時，可行解不是最優(yōu)解，目標函數(shù)值還可以增加； 而當所有檢驗數(shù)均小于等于零時，可行解必為最優(yōu)解，目標函數(shù)值為最優(yōu)值。

2.2 實例說明

2.3 矩陣運算與單純形法的聯(lián)系

實際上，2.2中所有計算都可以通過矩陣的初等行變換求得。將目標函數(shù)行（也即檢驗數(shù)行）放置在增廣矩陣的下一行，進行初等行變換，使基矩陣B（見實線框）變換為E，并使目標函數(shù)行的對應(yīng)部分（見虛線框）變換為O?？傻媚繕撕瘮?shù)行右端常數(shù)的相反數(shù)即為最優(yōu)目標函數(shù)值。

根據(jù)高等代數(shù)的知識，矩陣的初等行變換相當于矩陣左乘一個初等矩陣。于是，將矩陣的初等行變換利用表格的形式來呈現(xiàn)，即為單純形表。初始單純形表（見表2）為

表2 初始單純形表Tab. 2 Initial simplex tableau

用B?1左乘表2的第二行，用左乘表2的第三行，可得到新的單純形表（見表3）。

表3 新單純形表Tab. 3 New simplex tableau

若此表的解不是最優(yōu)解，可重新選基矩陣以得到改進解，直至得到最優(yōu)解。但從形式上來看，不論是改進單純形表還是最優(yōu)解對應(yīng)的最優(yōu)表，它們的形式與表3完全相同。因此，單純形法的計算實質(zhì)上就是矩陣的初等行變換。

3 總結(jié)

本文從高等代數(shù)的角度研究了可行域有界的線性規(guī)劃問題的可行解及最優(yōu)解，并通過實例進行了具體分析說明。本文分別從線性方程組以及矩陣兩個方面進行了研究。一方面，利用線性方程組的知識表示了可行解以及基解，進而比較所有基可行解的目標函數(shù)值以得到最優(yōu)解與最優(yōu)值；另一方面，利用矩陣的知識得到基可行解與目標函數(shù)值的計算表達式，并分析了運籌學(xué)中最優(yōu)準則的合理性，進一步地討論了矩陣初等行變換與單純形法的關(guān)系。前者的優(yōu)勢在于可行解的表示，而后者的優(yōu)勢在于最優(yōu)解的分析與判別。將兩者相結(jié)合，則可達到對線性規(guī)劃問題的更深層的理解。

[1] 劉娟, 馬寶林. 淺談高等代數(shù)的“縱觀”與“橫聯(lián)”[J]. 長沙大學(xué)學(xué)報, 2010, 24(5): 97-98.

[2] 王萼芳, 石生明. 高等代數(shù)[M]. 北京: 高等教育出版社, 2003.

[3] 凌征球, 龔國勇, 龔文振. 高等代數(shù)在數(shù)學(xué)分析解題中的某些應(yīng)用[J]. 玉林師范學(xué)院學(xué)報, 2010, 31(5): 34-37.

[4] 翟富菊, 吳海燕. 概率論與高等代數(shù)的相互滲透[J]. 中國科教創(chuàng)新導(dǎo)刊, 2010(1): 94-94.

[5] 程國, 劉亞亞, 趙鵬軍. 基于數(shù)學(xué)建模思想的高等代數(shù)課程教學(xué)研究[J]. 商洛學(xué)院學(xué)報, 2011, 25(6): 15-18.

[6] 《運籌學(xué)》教材編委會. 運籌學(xué)[M]. 北京: 清華大學(xué)出版社, 2005.

The Applications of Advanced Algebra in Linear Programming

FAN Jing
( School of Science, Shanghai Second Polytechnic University, Shanghai 201209, P. R. China )

Advanced Algebra is one of the basic core courses for all undergraduates in the department of mathematics. It is not only the extension of elementary mathematics, but also the foundation of Operations Research, especially of the Linear Programming. The knowledge of advanced algebra is used to solve the linear programming problem. Because the linear constraints of the standard format of the linear programming problem are the linear equations, the feasible solutions and the optimal solution are deduced from the point of view of the linear equations. According to the matrix form of the standard format of the linear programming problem, the expressions of the basic feasible solutions and the corresponding objective function value can be obtained, in addition to the criteria for the optimal solution. Moreover, the close relationship between the elementary transformation of the matrix and the simplex method is analyzed by the knowledge of the matrix. The correction of the above analysis can be illustrated by one typical example.

advanced algebra; linear programming; matrix; linear equations

O15

A

1001-4543(2012)03-0214-05

2012-07-07;

2012-08-03

范靜（1979－），女，山西長治人，講師，在讀博士，主要研究方向為運籌學(xué)，電子郵箱fanjing@sf.sspu.cn。

上海第二工業(yè)大學(xué)重點課程建設(shè)項目（No. A20KC110002）