許 寧

（南京政治學(xué)院 基礎(chǔ)部，江蘇 南京 21003）

單純形的代數(shù)思維

許 寧

（南京政治學(xué)院 基礎(chǔ)部，江蘇 南京 21003）

以單純形的代數(shù)特征為切入點，建立基于矩陣的單純形手工計算方法，揭示了單純形及其各種計算技巧之間的內(nèi)部聯(lián)系，理清了單純形由解特殊問題到解一般問題發(fā)展路徑.

單純形；單純形矩陣；兩階段法；大M法

美國運籌學(xué)家Frederick S. Hillier 認為：線性規(guī)劃理論是20世紀中葉最重要的科學(xué)進步之一［1］，線性規(guī)劃的一個有效的求解方法是單純形. 目前對單純形處理通常是從幾何直觀開始，借助于單純形表來展開，或者直接借助于MATLAB軟件的linprog函數(shù)來求解等等，這些沒有體現(xiàn)單純形思想的精髓，沒能體現(xiàn)在一堆數(shù)據(jù)中通過什么角度的觀察，找到最優(yōu)解的思維過程，不利于培養(yǎng)運用大數(shù)據(jù)的能力. 本文力圖設(shè)計一種模式，充分揭示單純形的代數(shù)思維過程，真正理解單純形的本質(zhì).

1 單純形是什么

現(xiàn)今大部分書籍是通過兩個變量線性規(guī)劃問題的圖解法來說明最優(yōu)值是在凸集的頂點上取得，因而只要比較凸集頂點的目標函數(shù)值的大小即可得最優(yōu)解與最優(yōu)值，這不能揭示單純形是什么. 事實上，單純形本質(zhì)上是一個迭代算法，我們可以通過下面的例子［2］來考察單純形是如何工作的. 設(shè)

單純形是這樣開始工作的，首先它從方程（2）的一個解(x1, x2, x3, x4, x5, x6)出發(fā)，尋找一個滿足重復(fù)這一過程，直到不能改變目標函數(shù)值為止，這最后的解即為最優(yōu)解.

為此，需要一個初始解(x1,L,x6). 一個簡便的方法是令方程（2）中原變量x1=0,x2=0,x3=0,則得松弛變量x4=5,x5=11,x6=8, 目標函數(shù)值為 0. 由目標函數(shù)

知，當(dāng)變量x1, x2, x3中至少有一個從零遞增時，目標函數(shù)值 z 將增加，故解(x1, x2, x3, x4, x5, x6)= (0,0,0,5,11,8)不是最優(yōu)解. 又（3）中x1, x2, x3前面的系數(shù)分別為 5，4，3，故當(dāng)x1增長時，目標函數(shù)值 z 增長較快，為計算簡單，只考慮x1增大時情形（x2=x3=0）， 此時松弛變量將改變，由松弛變量的非負性知，x1的增長將有一個限制.事實上，把x2=0,x3=0代入方程（2），結(jié)合x4, x5, x6的非負性得即x增長1的上界為從而得新解為

對應(yīng)的目標函數(shù)值為25/2，于是（4）是我們需要的新解，但如何在此基礎(chǔ)上進一步尋找新解呢？這召喚我們需要一個標準的求新解的方法，回想剛開始我們是利用(x1, x2, x3)=(0,0,0)代入方程（2）得到初始解的，即用為零的變量x1, x2, x3來表示其它的變量，現(xiàn)在新解中(x2, x3, x4)=(0,0,0), 因而要用變量x2, x3, x4來表示目標函數(shù)z和變量x1, x5, x6. 事實上，由于為零的量只是x1換成了x4，于是在方程（2）中，由x4=5?2x1?3x2?x3得

把（5）式代入（2）中的z, x5, x6,則方程（2）轉(zhuǎn)化為

顯然，目前的解（4）是令(x2, x3, x4)=(0,0,0),代入方程（7）得到的. 由目標函數(shù)（6）知，當(dāng)增加x2, x4時，z值會減少，若僅x3增加時，z 值會變大，故解（4）不是最優(yōu)解. 類似地，x3不能無限制地增加，因為由方程（7）知，當(dāng)x3增加時，會導(dǎo)致變量x1, x6值減小，把x2=0,x4=0代入（7），結(jié)合x1, x6的非負性有0≤x3≤1.故x3增長的上界為x3=1. 于是把(x2, x3, x4)=(0,1,0)代入方程（7）得新解

此時的目標函數(shù)值為13. 因為新解（8）中(x2, x4, x6)=(0,0,0),故要用變量x2, x4, x6來表示z, x1, x3, x5.又(x2, x4, x6)=(0,0,0)是由(x2, x3, x4)=(0,0,0)中把x3換為x6得到的，于是在方程（7）中，由

把（9）代入方程（7）中的其他式子，消去x3得

由于目標函數(shù)（10）中變量x2, x4, x6的系數(shù)皆為負數(shù)，于是當(dāng)它們至少有一個變量增加時，目標函數(shù)值將會減少，故(x1, x2, x3, x4, x5, x6)=(2,0,1,0,1,0)是最優(yōu)解，其最優(yōu)值為z=13.

剛才在求新解的過程中，有些變量令他為零，另一些變量自由增長，這就需要把這些決策變量進行分類，由此引入所謂的線性規(guī)劃標準形、基變量、非基變量、入基變量、出基變量等概念.

上述分析知，單純形是從初始點X0=(0,0,0,5,11,8)走到了新的點接著從X1出發(fā)，繼續(xù)尋找使的新解X2，其方法與求解X1類似，即在原基變量指標集B與非基變量指標集N基礎(chǔ)上，結(jié)合目標函數(shù)（6）確定入基變量和出基變量，形成新的基變量與非基變量的指標集B，N，利用新的非基變量，結(jié)合方程（9）來改寫目標函數(shù)方程（6）與方程（7），得到新的方程（10），（11），令非基變量為 0 代入新方程，可得新解X2, 如始重復(fù)，直到新的目標函數(shù)表達式中，決策變量的系皆為非正數(shù)，終止，則最后得到的解即為最優(yōu)解. 這就是單純形法.

2 單純形的手工計算技術(shù)

要進一步把單純形從感性認識提升到理性認識，需要一個簡潔的方法來展現(xiàn)單純形的計算過程. 現(xiàn)有的材料中，單純形計算是通過所謂的單純形表來展現(xiàn)的，這不利于大眾掌握單純形的實質(zhì)，造成理解的困難，一個重要原因是計算手段不自然，不能充分體現(xiàn)單純形的迭代思想，為此，需開發(fā)新的計算表現(xiàn)工具.事實上，由于單純形的迭代本質(zhì)上是解線性方程組，于是借助于方程組的矩陣表示方法能很好地展現(xiàn)單純形的計算過程，我們把單純形表用單純形矩陣來表示. 下面借助問題（1）的求解過程來說明這一單純形求解技術(shù). 為表述方便，我們作如下規(guī)定：單純形矩陣由變量行、基變量列、方程的增廣矩陣組成，增廣矩陣的上邊一行為變量行，按z, x1, x2,L,x6, b順序書寫，其中 b 表示常數(shù)項，z 表示目標函數(shù)值，x1,L,x6為決策變量. 增廣矩陣的左側(cè)列為基變量列，該列中第一個分量寫z，其位置對應(yīng)目標函數(shù)方程的系數(shù)行，第2至第4個分量為基變量，其位置分別對應(yīng)于它們所在方程的系數(shù)行. 增廣矩陣中，除去第一行（目標函數(shù)系數(shù)行）、最后一列（常數(shù)項列），子單位陣的列向量所對應(yīng)的變量為基變量. 增廣矩陣的右側(cè)列是計算比值列.

事實上，若把規(guī)劃問題（ 2）改寫為

則結(jié)合方程（12）式知，規(guī)劃問題（2）的初始單純形矩陣為

其中子單位陣每列所對應(yīng)的變量為x4, x5, x6（稱為基變量），放在增廣矩陣的左側(cè)列.

下面的計算中，按單純形的迭代步驟，從一個矩陣到下一個矩陣，之間用箭線連接，箭線上的“a×(i)+(j )”表示把第i行乘數(shù)a后加到第j 行，“a×(i)” 表示把第i行乘數(shù)a，[b]表示數(shù)b是主元. 單純形的迭代步驟是：（1）入基變量： 在單純形矩陣的第1行中，選擇決策變量負系數(shù)中最小的數(shù)的列所對應(yīng)的變量作為入基變量. 稱這個系數(shù)所在的列為樞軸列；（2）出基變量： 首先找出樞軸列中每一個嚴格為正的系數(shù)，用這些系數(shù)除以同一行的常數(shù)項，寫到同一行常數(shù)項的右側(cè)，其次找出比值最小的行，該行稱為樞軸行，該行上的基變量即為出基變量；（3）主元：同時在樞軸行與樞軸列的數(shù)字稱為主元；（4）換基：在基變量列中，把出基變量換為入基變量，同時將主元化為1；（5）消元：主元的同列其他元素化為0. 具體表述如下

矩陣（14）稱為最優(yōu)單純形矩陣（增廣矩陣的第一行決策變量的系數(shù)皆非負），由（14）知，該規(guī)劃問題的最優(yōu)值為13，最優(yōu)解為(x1, x2, x3, x4, x5, x6)=(2,0,1,0,1,0).故原問題的最優(yōu)值為13，最優(yōu)解為(x1, x2, x3)=(2,0,1).這就是單純形的手工計算方法.

上述表明，單純形是一迭代運算，它從初始單純形的矩陣開始，找主元、換基、消元，完成第一次迭代，然后從新的單純形矩陣開始，找主元、換基、消元，完成第二次迭代，如此反復(fù)直到得出最優(yōu)矩陣結(jié)束. 那么，為什么用單純形得到的結(jié)論一定是規(guī)劃問題的最優(yōu)值和最優(yōu)解？這就要探索單純形的數(shù)學(xué)原理. 事實上，若線性規(guī)劃標準形有可行解，則一定有基可行解；若線性規(guī)劃標準形有最優(yōu)解，則一定有最優(yōu)基可行解［3］. 若單純形矩陣中第一行決策變量的系皆非負，則由該矩陣表示的線性方程組決定的基可行解是最優(yōu)解［4］.

3 單純形運用中的技巧

單純形是在給出一個初始的基可行解的基礎(chǔ)上，按照一定的規(guī)則進行迭代，求出最優(yōu)解. 實際操作中，要使單純形發(fā)揮作用，約束條件（m個）構(gòu)成的方程組中要有一個明顯的子單位矩陣（m×m階）. 拿約束條件為小于等于的線性規(guī)劃問題來說，我們引入松弛變量，從而在單純形初始矩陣中有一個子單位矩陣，故可把松弛變量作為初始基變量，令所有非基變量為零，則每個基變量等于它所在方程的非負常數(shù)項，這就確定了初始基可行解. 但現(xiàn)實中的線性規(guī)劃問題通常不具備這樣的標準形式，從而導(dǎo)致初始基可行解不容易確定. 為此需要做特別的處理，其中一個標準的方法是人工變量法. 該方法是通過對每個需要的約束條件引入一個虛擬變量（稱為人工變量），構(gòu)建一個更為簡便的人工問題. 引進這個變量只是為了使該方程出現(xiàn)初始基變量. 比如一個線性規(guī)劃問題的約束條件為

為了求（15）的一個可行解，引入人工變量x4≥0,x5≥0,考察如下的極小化問題

顯然，若（15）有可行解，則（16），（17）的極小值為0，此時(x4, x5)=(0,0). 若（15）無可行解，則（16），（17）的極小值大于0.

（16），（17）是典型的線性規(guī)劃標準形，顯然，(x1, x2, x3, x4, x5)=(0,0,0,4,3)是一基本可行解，故可用單純形求最優(yōu)解. 若（16），（17）的極小值是0，則最優(yōu)解中(x4, x5)=(0,0),從而最優(yōu)解中的(x1, x2, x3)的值是（15）的一個可行解. 事實上，（16），（17）的規(guī)劃問題的初始單純形矩陣為

由于單純形的搜索路徑是從目標函數(shù)非基變量的系數(shù)大小的比較開始的，且目標函數(shù)中沒有基變量，于是在矩陣（18）中運用初等行變換，把第一行的基變量對應(yīng)的系數(shù)化為零，即

矩陣（19）中的第一行具備了單純形開始搜索的條件. 此時單純形開始了找主元、換基、消元的搜索過程.如此反復(fù)直到得到最優(yōu)矩陣為止. （19）的最優(yōu)矩陣為

在（20）中去掉人工變量x4, x5對應(yīng)的兩列元素，同時把第一行的目標函數(shù)的系數(shù)換用（21）的目標函數(shù)系數(shù)代替（注意要把min z轉(zhuǎn)化為max（-z）），則得（21），（15）的初始單純形矩陣由于（22）第一行中基變量x1, x3的系數(shù)非零，于是要把第一行中的基變量的系數(shù)化為零，這樣單純形才能發(fā)揮作用. 事實上

（23）是最優(yōu)單純形矩陣，因而問題（21）（15）的最優(yōu)解為的極小值為這就是所謂的兩階段法.

從上面分析知：兩階段法的第一階段是解決約束條件含有“=,≥或常數(shù)項為負”等形式帶來的如何確定初始的基可行解的問題，第二階段是在基可行解的基礎(chǔ)上結(jié)合原問題的目標函數(shù)再次運用單純形迭代可得結(jié)論. 對于這樣類似的約束條件的線性規(guī)劃問題，我們也可以用統(tǒng)一的方法來進行處理，這就是大M法，限于篇幅，這里略去.

4 單純形的智能化

單純形法可用來解決大型的線性規(guī)劃問題，這些問題通常有上千個約束條件和更多的決策變量，實踐表明，它已成功解決的問題有幾十萬個約束條件和幾百萬個決策變量. 顯然，手工計算是不能解決這樣大型的問題，這必然要求把單純形用計算機編碼來實現(xiàn)，事實上，人們已開發(fā)了許多包含單純形的規(guī)劃軟件包，如Excel Solver，LINDO（LINGO），CPLEX，MATLAB等. 目前CPLEX11已成功地求解了工業(yè)中產(chǎn)生的有幾千萬個約束條件和決策變量的線性規(guī)劃問題［5］. 在實際工作中，人們常用MATLAB來解決問題. MATLAB的單純形的求解工具是 linprog函數(shù). 只要按照linprog的語言規(guī)則輸入，即可得到結(jié)論. 比如問題（1）的MATLAB代碼如下：

5 結(jié)語

隨著計算機的廣泛應(yīng)用，人們可能永遠不再需要用手工去求解線性規(guī)劃模型，從而導(dǎo)致只需學(xué)會輸入數(shù)據(jù)的機械模式.這種模式回避了在模型求解時，計算技術(shù)遇到哪些困難，人們是如何克服的種種認識.沒有對前人在困難面前如何尋找突破口的感悟，后人的創(chuàng)新就很難實現(xiàn)，這不利于人才的培養(yǎng). 同時，單純形的表格式的計算技術(shù)，沒有融入人的思維過程，也不利于接收，再者，單純形計算中的多種技術(shù)的展現(xiàn)，擾亂了人們的眼界，沒有反映出思維的主線是什么，以及各種計算技術(shù)之間的內(nèi)在聯(lián)系.

針對這一現(xiàn)象，我們首先給出單純形是什么，讓人們有一個初步的映象，接著開發(fā)一種融入人的思維習(xí)慣的單純形的求解技術(shù)，避免煩瑣的計算淹沒對單純形本質(zhì)的人識，在此基礎(chǔ)上，指出單純形的代數(shù)特征，即在初始單純形矩陣中含有與約束條件個數(shù)一致階數(shù)的子單位矩陣，然后尋找解決一般問題中如何構(gòu)建這樣的子單位矩陣，這樣很自然地引入兩階段法和大 M 法，這就是所謂單純形的技巧. 最后，介紹如何利用計算機來展現(xiàn)單純形的操作過程. 從而在實際工作中，提升了自覺地應(yīng)用單純形來解決實際問題的能力.

［1］HILLIER F S. Introduction to Operations Research ［M］.9th ed. 北京：清華大學(xué)出版社， 2010：25-46.

［2］VANDERBEI R J. Linear Programming： Foundations and Extensions ［M］.2th ed. New York： Springer， 2002： 13.

［3］LUENBERGER D G. Linear and Nonlinear Programming ［M］. 3th ed. New York： Springer，2008： 20-22.

［4］DANTZIG G B. Linear Programming and Extensions ［M］. California： The Rand Corparation，1963： 94-100.

［5］ BIXBY R E. Solving Real-World Linear Programs： A Decade and More of Progress［J］. Operations Research， 2002，50（1）：3-15.

Abstract:According to an algebraic characteristic for simplex, in this paper, a new method is established based on matrix for manual calculation of simplex, and the internal connection between the simplex and its computational techniques is revealed, elaborating the development path from special to general for simplex.

Key words:simplex; simplex matrix; two-phase methods; big-M method

On the Simplex Algebraic Thinking

XU Ning
(Department of Basic Courses, Nanjing Political College, Nanjing 21003, China)

O221.1

A

1008-2794（2017）04-00114-08

2017-02-24

許寧，教授，博士，研究方向：偏微分方程、軍事運籌學(xué)，E-mail： xuningnj@163.com.