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

許 寧

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

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

許 寧

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

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

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

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

1 單純形是什么

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

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

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

知，當(dāng)變量x1, x2, x3中至少有一個(gè)從零遞增時(shí)，目標(biāo)函數(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增長(zhǎng)時(shí)，目標(biāo)函數(shù)值 z 增長(zhǎng)較快，為計(jì)算簡(jiǎn)單，只考慮x1增大時(shí)情形（x2=x3=0）， 此時(shí)松弛變量將改變，由松弛變量的非負(fù)性知，x1的增長(zhǎng)將有一個(gè)限制.事實(shí)上，把x2=0,x3=0代入方程（2），結(jié)合x4, x5, x6的非負(fù)性得即x增長(zhǎng)1的上界為從而得新解為

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

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

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

此時(shí)的目標(biāo)函數(shù)值為13. 因?yàn)樾陆猓?）中(x2, x4, x6)=(0,0,0),故要用變量x2, x4, x6來(lái)表示z, x1, x3, x5.又(x2, x4, x6)=(0,0,0)是由(x2, x3, x4)=(0,0,0)中把x3換為x6得到的，于是在方程（7）中，由

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

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

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

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

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

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

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

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

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

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

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

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

3 單純形運(yùn)用中的技巧

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

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

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

（16），（17）是典型的線性規(guī)劃標(biāo)準(zhǔn)形，顯然，(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）的一個(gè)可行解. 事實(shí)上，（16），（17）的規(guī)劃問(wèn)題的初始單純形矩陣為

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

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

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

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

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

4 單純形的智能化

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

5 結(jié)語(yǔ)

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

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

［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

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