孫 祥 凱

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

運(yùn)籌學(xué)課程中單純形法教學(xué)的幾點(diǎn)思考*

孫 祥 凱

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

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

線性規(guī)劃；單純形法；運(yùn)輸問題；目標(biāo)規(guī)劃；教學(xué)改革

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

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

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

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

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

2 單純形法的求解步驟及注意事項(xiàng)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 初始單純形表

表2 最終單純形表

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

5 結(jié)束語

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

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

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

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

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

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

[6] 陳修素，丁宣浩，陳義安. 基于創(chuàng)新能力培養(yǎng)的《運(yùn)籌學(xué)》課程改革與數(shù)學(xué)建模實(shí)踐[J]. 計(jì)算數(shù)學(xué)，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.

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

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

G521

A

責(zé)任編輯：代小紅