孫 祥 凱

(重慶工商大學 數(shù)學與統(tǒng)計學院，重慶 400067)

運籌學課程中單純形法教學的幾點思考*

孫 祥 凱

(重慶工商大學 數(shù)學與統(tǒng)計學院，重慶 400067)

線性規(guī)劃問題的單純形法一直是運籌學課程教學的重點和難點，通過對線性規(guī)劃問題單純形法計算原理的分析和研究，指出了線性規(guī)劃問題的單純形法思想與運輸問題的表上作業(yè)法以及目標規(guī)劃問題的單純形法之間的區(qū)別與聯(lián)系，給出了一種求解目標規(guī)劃問題的更簡便方法；教學實踐證明這些方法更能夠加深學生對單純形法的算法邏輯的認識和理解。

線性規(guī)劃；單純形法；運輸問題；目標規(guī)劃；教學改革

運籌學是20世紀新興的一門應用學科，它能夠幫助決策者解決那些可以用定量方法和相關(guān)理論方法來處理的問題。它在諸如經(jīng)濟規(guī)劃、計劃管理、金融決策、能源開發(fā)、工程設(shè)計、農(nóng)業(yè)種植、衛(wèi)生保健以及軍事科學等領(lǐng)域有著重要的應用。不僅如此，運籌學問題也常常涉及經(jīng)濟學、對策論、系統(tǒng)工程和控制論等學科的研究領(lǐng)域[1-6]。作為運籌學的一個重要分支，線性規(guī)劃的應用極其廣泛，其作用已為越來越多的人所重視。特別是美國數(shù)學家G.B. Dantzig在1947年提出了求解一般線性規(guī)劃問題的求解方法，即單純形法之后，線性規(guī)劃在理論上更進一步趨于成熟。至今，單純形法仍然是行之有效且被廣泛應用的求解線性規(guī)劃問題的方法。除此之外，單純形法在運籌學中的運輸問題以及目標規(guī)劃問題中也有著十分重要的作用。因此深入理解單純形法的基本思想以及求解步驟，對運籌學后續(xù)學習有著十分重要的作用。

本文主要從單純形法的基本思想出發(fā)，進一步闡述單純形法的求解步驟，同時分別比較求解運輸問題的表上作業(yè)法以及求解目標規(guī)劃問題的單純形法與線性規(guī)劃問題的單純形法之間的區(qū)別與聯(lián)系。不僅加深了學生對單純形法的理解和認識，而且增強了學生對運籌學學習的興趣。

1 單純形法的基本思想及其直觀理解

線性規(guī)劃問題的所有可行解構(gòu)成的集合(即可行域)是凸集，它們有有限個頂點，并且其最優(yōu)值如果存在必在該凸集的某頂點處達到。這里頂點所對應的可行解，稱為基本可行解。單純形法是解線性規(guī)劃的一種傳統(tǒng)而且有效的方法，其基本思想[1，2]：先找出一個基本可行解，對它進行判斷，看是否是最優(yōu)解；若不是，則按照一定法則轉(zhuǎn)換到另一個使目標函數(shù)能增加的基本可行解，重復這一迭代過程，直到求得問題最優(yōu)解。因基本可行解的個數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問題的最優(yōu)解。

在學習單純形法求解線性規(guī)劃時，我們首先需要十分清楚單純形表中的相關(guān)概念及其直觀的圖形解釋。例如，線性規(guī)劃問題的基可行解實際上就是其可行域的頂點，所謂的單純形實際上指的是一維空間中的線段、二維空間中的三角形，三維空間中的四面體以及n維空間中的含有n+1頂點的多面體。其次，也要善于將單純形法每一步所得結(jié)果與線性規(guī)劃問題的圖解法做一個比較，進一步的理解其幾何意義。這樣，學生不僅可以很容易的理解單純形法的含義，而且對單純形法的后續(xù)學習也有一個良好的鋪墊。

2 單純形法的求解步驟及注意事項

由上一節(jié)所介紹的單純形法基本思想可知，首先在線性規(guī)劃問題的系數(shù)矩陣中構(gòu)造一個單位矩陣作為初始可行基，然后逐步進行迭代，進而判斷解的類型以及解的存在與否，最終找到最優(yōu)解。為了學生在學習中能夠?qū)渭冃畏ㄓ幸粋€更加簡潔明了、深刻的理解，下面進一步闡述單純形法的求解步驟。給定一個線性規(guī)劃問題(此處假定是對目標函數(shù)求最大的線性規(guī)劃問題)，用單純形法對其求解，具體步驟如下：

(1) 確定初始基可行解。首先找出初始基矩陣，通常選取系數(shù)矩陣中的單位方陣為初始基矩陣。然后選取初始基矩陣對應的變量為初始基變量，剩余的變量為非基變量。最后只需令非基變量為零，則就可以得到一組初始基可行解。

(2) 最優(yōu)檢驗。首先求解非基變量的檢驗數(shù)(基變量的檢驗數(shù)無需求解，都為零)。若非基變量的檢驗數(shù)全為負數(shù)，則達到最優(yōu)解，停止計算。若存在某個檢驗數(shù)為正數(shù)，并且其對應的列向量為負，則此問題無界，停止計算。否則進行下一步。

(3) 迭代。確定換入變量以及換出變量，重新建立新的基矩陣，基變量以及非基變量，從而得到新的基可行解。按照上述步驟重新計算，直到找到最優(yōu)解為止。

單純形法的求解步驟思想十分簡單，然而由于在求解過程中，需要列大量的單純形表，計算量很大。若一個地方出錯，整個計算就前功盡棄。所以在實際操作中，我們需要加強學生對單純形法表的計算。這樣不僅可以加深學生對單純形法的理解，而且可以使得學生對單純形表中的相關(guān)概念有更準確的把握。

3 運輸問題的表上作業(yè)法

運輸問題作為一類特殊的線性規(guī)劃問題，其在現(xiàn)實世界中有著廣泛的應用。目前求解運輸問題的一種常用方法是表上作業(yè)法。表上作業(yè)法是單純形法在求解運輸問題的一種簡化方法，其實質(zhì)是單純形法。但是兩者之間在具體的計算和術(shù)語上有一定的差別。為了讓讀者對表上作業(yè)法有更清晰的認識和理解。將表上作業(yè)法的幾點注意事項歸納如下：

(1) 確定運輸問題的初始基可行解，求出運輸問題的初始調(diào)運方案。運輸問題的初始基可行解是在(m×n)產(chǎn)銷平衡表上給出m+n-1個數(shù)字格。通常的方法有最小元素法和伏格爾法。

(2) 求解運輸問題非基變量的檢驗數(shù)，就是求解產(chǎn)銷平衡表上空格的檢驗數(shù)。然后進行最優(yōu)判定。通常求解檢驗數(shù)的方法有閉回路法和位勢法。此處要特別的注意，前面所闡述的線性規(guī)劃問題都假定目標函數(shù)實現(xiàn)最大化，而運輸問題的目標函數(shù)是要求實現(xiàn)最小化，故此時我們要保證所有的檢驗數(shù)不小于零。

(3) 在利用表上作業(yè)法求解計算時，一定要區(qū)分好何處利用表格中運量的數(shù)據(jù)、何處利用表格中運價的數(shù)據(jù)。例如在利用閉回路法求解檢驗數(shù)時，利用的是空格處的運價進行計算。而在利用閉回路調(diào)整法確定換入變量以及換出變量時，考慮的是相應基變量(數(shù)字格)處的運量。所有這些就需要我們深刻理解表上作業(yè)法的本質(zhì)含義。

4 目標規(guī)劃問題的單純形法及其直接求解方法

目標規(guī)劃是目前處理多個目標決策的一種方法。它是針對線性規(guī)劃目標單一的局限性而提出的，是線性規(guī)劃的應用的進一步拓展，也是解決現(xiàn)實實際問題的一種行之有效的方法。由于目標規(guī)劃的多個目標之間不僅有主次先后之分，而且有時會互相矛盾，相互制約。因此求解目標規(guī)劃所用的單純形法主要是利用了分層的思想，即在建立單純形表時，需要對檢驗數(shù)行按照優(yōu)先因子的個數(shù)分別列成多行，然后首先考慮第一個優(yōu)先因子系數(shù)的正負，以此類推，直到求出最優(yōu)解(滿意解)為止。具體計算步驟可參考清華大學出版社出版的《運籌學》(本科版)教材[1]。

目前針對目標規(guī)劃的單純形法的計算過程，大多數(shù)教材是直接給出相應例題的單純形表中檢驗數(shù)的取值，而具體的求解過程卻沒有。這對初學者就會造成一定的困惑，不知檢驗數(shù)是如何求出的。針對這一問題，借助一個例子給出求解目標規(guī)劃問題的一種直接單純形求解方法，并闡述了教材中檢驗數(shù)的求解過程。

例：試用單純形法求解下述目標規(guī)劃問題：

分析：由于目標規(guī)劃問題的數(shù)學模型結(jié)構(gòu)和線性規(guī)劃問題的數(shù)學模型結(jié)構(gòu)沒有本質(zhì)區(qū)別，所以按照求解線性規(guī)劃問題的單純形法進行求解。在求解過程中只需假設(shè)P1?P2?P3即可。當然如果目標函數(shù)中含有K個優(yōu)先因子，只需假設(shè)P1?P2?…?PK即可。只有這樣假設(shè)，才能保證在計算過程中按照優(yōu)先因子的先后順序來考慮。

表1 初始單純形表

表2 最終單純形表

表2的檢驗數(shù)全為正數(shù)，所以目標規(guī)劃問題達到滿意解。滿意解為(2，4，3)。通過上述解法不難發(fā)現(xiàn)：由于目標規(guī)劃問題的數(shù)學模型結(jié)構(gòu)和線性規(guī)劃問題的數(shù)學模型結(jié)構(gòu)沒有本質(zhì)區(qū)別，所以可以完全按照求解線性規(guī)劃問題的單純形法進行求解目標規(guī)劃問題，并且求解更加方便易懂。通過觀察教材上關(guān)于目標規(guī)劃單純形表中的檢驗數(shù)行，容易發(fā)現(xiàn)其檢驗數(shù)行P1，P2，P3對應的數(shù)字實際上就是表1以及表2中所得檢驗數(shù)行的P1，P2，P3的系數(shù)。

5 結(jié)束語

作為運籌學的一個重要分支，線性規(guī)劃問題已經(jīng)廣泛應用到工業(yè)、商業(yè)、農(nóng)業(yè)、交通運輸業(yè)等各個領(lǐng)域。而單純形法作為求解線性規(guī)劃問題模型的一種行之有效的方法，其可以廣泛應用到求解運輸問題以及目標規(guī)劃問題等模型中。因此深刻理解線性規(guī)劃問題單純形法的基本原理以及解題思路對運籌學相關(guān)問題模型的求解，特別是運輸問題以及目標規(guī)劃問題的求解有著十分重要的作用。本文通過對線性規(guī)劃單純形法的進一步闡述，闡明了單純形法在運籌學課程中各種問題模型求解術(shù)語的區(qū)別與聯(lián)系，加深了學生對運籌學相關(guān)問題的的求解方法和原理，消除了學生對各種問題模型中單純形法求解的困惑。

[1] 《運籌學》教材編寫組．運籌學[M]．本科版．北京：清華大學出版社，2005

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

[3] 楊盛昌. 目標規(guī)劃問題的建模方法探析[J]. 云南民族學院學報：自然科學版，2001，10(2)： 351-355

[4] 褚淑貞. 運籌學課程教學模式確定[J]. 教學教育，2003(3)： 38-39

[5] 張杰，郭麗杰. 運籌學課程的改革與數(shù)學建模教育[J]. 高等數(shù)學研究，2007(1)： 103-105

[6] 陳修素，丁宣浩，陳義安. 基于創(chuàng)新能力培養(yǎng)的《運籌學》課程改革與數(shù)學建模實踐[J]. 計算數(shù)學，2012，22(2)： 109-113

Keywords：linear programming；simplex method；transportation problem；objective programming；teaching reform

Several Ideas on Simplex Method Teaching in Operational Research Courses

SUNXiang-kai

(School of Mathematics and Statistics, Chongqing Technology and Business University, Chongqing 400067, China)

The simplex method of linear programming problem has been the important point and the difficult point in the teaching of operational research courses, through the analysis and study of calculation principle of simplex method of linear programming problem, the difference and association between the table dispatching method of simplex method ideas and transportation issue of linear programming problem and the simplex method of objective programming problem are pointed out, especially a kind of more simple method for solving objective programming problem is given. Teaching practice verifies that these methods can better deepen the understanding of calculation logic of the simplex method by the students.

1672-058X(2013)10-0091-05

2013-03-13；

2013-04-25.

國家自然科學基金(11171362和11201509)；重慶市自然科學基金(cstc2012jjA00033).

孫祥凱(1984-)，男，山東青州人，在站博士后，講師，從事最優(yōu)化理論與應用的研究.

G521

A

責任編輯：代小紅