康永輝，王寶紅

（廣西水利電力勘測(cè)設(shè)計(jì)研究院，廣西 南寧 530023）

1 線(xiàn)性規(guī)劃簡(jiǎn)介

線(xiàn)性規(guī)劃是運(yùn)籌學(xué)中應(yīng)用最為廣泛的一個(gè)分支，也是運(yùn)籌學(xué)最基本的部分。線(xiàn)性規(guī)劃是研究在現(xiàn)有人力、物力等資源條件下，合理調(diào)配和有效使用資源，以達(dá)到最優(yōu)目標(biāo)（產(chǎn)量最高、利潤(rùn)最大、成本最小、資源消耗最少等）的一種數(shù)學(xué)方法。目前已廣泛應(yīng)用于生產(chǎn)管理、資源分配、運(yùn)輸問(wèn)題、生產(chǎn)計(jì)劃問(wèn)題、環(huán)境保護(hù)、軍事等眾多領(lǐng)域。線(xiàn)性規(guī)劃的數(shù)學(xué)理論成熟、建模簡(jiǎn)單，有通用算法和計(jì)算機(jī)軟件進(jìn)行計(jì)算。一般首先根據(jù)研究問(wèn)題的性質(zhì)確定決策變量；根據(jù)問(wèn)題的目標(biāo)，列出與決策變量有關(guān)的目標(biāo)函數(shù)；根據(jù)問(wèn)題的限制條件，列出與決策變量有關(guān)的約束條件來(lái)建立數(shù)學(xué)模型。線(xiàn)性規(guī)劃的求解有圖解法和單純形法，在實(shí)際應(yīng)用中一般采用單純形法進(jìn)行求解。

2 線(xiàn)性規(guī)劃模型及求解

線(xiàn)性規(guī)劃模型一般由3個(gè)要素組成：①變量，或稱(chēng)決策變量，是問(wèn)題中要確定的未知量，它用以表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制；②目標(biāo)函數(shù)，它是決策變量的函數(shù)，按優(yōu)化目標(biāo)分別在這個(gè)函數(shù)前加上 max或min；③約束條件，指決策變量取值時(shí)受到的各種資源條件的限制，通常表達(dá)為含決策變量的等式或不等式。

線(xiàn)性規(guī)劃模型可以表示為：

（1）求和形式：

（2）矩陣形式：

（3）集合形式：

其中：“s.t”（subject to的縮寫(xiě)）表示約束于；“opt”表示最優(yōu)的意思，一般是max或min。

求解一般線(xiàn)性規(guī)劃問(wèn)題有圖解法和單純形法。圖解法是求解線(xiàn)性規(guī)劃的一種直觀方法，可用于解決含有兩個(gè)決策變量的線(xiàn)性規(guī)劃問(wèn)題，其目的是判別線(xiàn)性規(guī)劃問(wèn)題的求解結(jié)局和存在最有解的條件下，把問(wèn)題的最有解找出來(lái)。圖解法的步驟可概括為：在平面上建立直角坐標(biāo)系，兩個(gè)坐標(biāo)軸對(duì)應(yīng)于兩個(gè)決策變量；圖示約束條件，找出可行域；圖示目標(biāo)函數(shù)和尋找最優(yōu)解。

根據(jù)線(xiàn)性規(guī)劃解的基本定理，線(xiàn)性規(guī)劃問(wèn)題的可行域?yàn)橥辜驘o(wú)界域（如果可行域不為空集）；凸集有有限個(gè)頂點(diǎn)，每個(gè)基可行解對(duì)應(yīng)于一個(gè)頂點(diǎn)；若線(xiàn)性規(guī)劃模型有最優(yōu)解，必定在某個(gè)頂點(diǎn)上取得。對(duì)于決策變量數(shù)n、約束方程數(shù)m比較小的情況，可以采取枚舉法，通過(guò)比較有限個(gè)基可行解的目標(biāo)函數(shù)值來(lái)確定最優(yōu)解與最優(yōu)值。但對(duì)于 n、m比較大的情況，完全枚舉法的計(jì)算量較大，這就需要采用更有效的方法——單純形法（simplex method）來(lái)求解線(xiàn)性規(guī)劃模型。

單純形法的求解思路是：對(duì)于給定的 LP模型，從某個(gè)基可行解（可行域的一個(gè)頂點(diǎn)）開(kāi)始，按照一定的規(guī)則轉(zhuǎn)換到另一個(gè)基可行解（頂點(diǎn)），使新頂點(diǎn)的目標(biāo)函數(shù)值優(yōu)于原目標(biāo)函數(shù)值，經(jīng)過(guò)有限次迭代直至目標(biāo)函數(shù)達(dá)到最優(yōu)。需要解決3個(gè)關(guān)鍵問(wèn)題：初始基可行解（頂點(diǎn)）的確定；基可行解的轉(zhuǎn)換規(guī)則；最優(yōu)行判斷準(zhǔn)則。單純形法的計(jì)算步驟主要包括：①將 LP模型轉(zhuǎn)換為標(biāo)準(zhǔn)型；②求初始基可行解，列出初始單純形表；③求得初始基可行解后進(jìn)入迭代過(guò)程，在每一次迭代過(guò)程中還包括根據(jù)最優(yōu)性條件確定最優(yōu)解或換入變量和根據(jù)可行性條件確定換出變量?jī)刹?。確定新的基可行解后繼續(xù)進(jìn)行迭代，經(jīng)過(guò)有限次迭代后就可以找到最優(yōu)解。

3 用線(xiàn)性規(guī)劃模型優(yōu)化配置水資源

某供水工程年供水能力為6 500萬(wàn)m3，主要用于工業(yè)、農(nóng)業(yè)以及生活用水，有關(guān)需水量、水價(jià)、供水成本、供水要求見(jiàn)表 1。由于向不同部門(mén)供水的水價(jià)以及供水成本不一樣，因此利潤(rùn)也不樣，在滿(mǎn)足供水要求的情況，就需確定最優(yōu)配水方案，才能使供水效益最大。

3.1 決策變量的確立

主要向工業(yè)、農(nóng)業(yè)、生活三部門(mén)供水，因而可確定工業(yè)、農(nóng)業(yè)、生活用水量為決策變量，分別為X1、X2、X3。

表1 需水量、水價(jià)、供水成本、供水要求表

3.2 目標(biāo)函數(shù)的建立

根據(jù)有關(guān)部門(mén)的用水量要求，以及水價(jià)和成本來(lái)確定最優(yōu)分配方案，使供水效益最大，即Max Z＝（2.8－1.5）X1＋（0.6－0.25）X2＋（2.0－0.6）X3。

3.3 約束方程

（1）三部門(mén)的總用水量小于供水工程總供水量，即：

X1＋X2＋X3≤6 500

（2）三部門(mén)的最大用水量限制

X1≤3 000，X2≤5 000，X3≤1 000。

（3）三部門(mén)的最小用水量限制

X1≥0，X2≥3 000，X3≥0。

3.4 求解

由于該模型含有3個(gè)決策變量，不便于用圖解法來(lái)求解，可采用單純形法來(lái)求解，按照單純形法的求解步驟及要求可求得目標(biāo)值為5 700萬(wàn)元，達(dá)到最優(yōu)解時(shí)的各變量值分別為：X1＝2 500萬(wàn)m3、X2＝3 000 萬(wàn) m3、X3＝1 000 萬(wàn) m3。也可以利用 Microsoft Excel 規(guī)劃求解工具進(jìn)行規(guī)劃求解，Microsoft Excel 規(guī)劃求解工具可用于求解一定限制條件下目標(biāo)單元的最大值、最小值及相應(yīng)的可變單元（決策變量）值，規(guī)劃求解工具具有數(shù)據(jù)輸入直觀、簡(jiǎn)單、計(jì)算快捷，并可生成完整的求解報(bào)告等特點(diǎn)。

4 結(jié)論及建議

水資源規(guī)劃目的是根據(jù)經(jīng)濟(jì)社會(huì)可持續(xù)發(fā)展和環(huán)境保護(hù)對(duì)水資源的要求，提出水資源合理開(kāi)發(fā)、優(yōu)化配置、高效利用、有效保護(hù)和綜合治理的總體布局及實(shí)施方案，促進(jìn)我國(guó)人口、資源、環(huán)境和經(jīng)濟(jì)的協(xié)調(diào)發(fā)展，以水資源的可持續(xù)利用支持經(jīng)濟(jì)社會(huì)的可持續(xù)發(fā)展。

水資源規(guī)劃是全面落實(shí)國(guó)家或地區(qū)實(shí)施可持續(xù)發(fā)展戰(zhàn)略的要求，適應(yīng)經(jīng)濟(jì)社會(huì)發(fā)展和水資源的時(shí)空動(dòng)態(tài)變化，著力緩解水資源短缺、水環(huán)境惡化等水問(wèn)題的一項(xiàng)重要工作。它是根據(jù)國(guó)家或地區(qū)的社會(huì)、經(jīng)濟(jì)、資源和環(huán)境總體發(fā)展規(guī)劃，以區(qū)域水文特征及水資源狀況為基礎(chǔ)來(lái)進(jìn)行的。

通過(guò)對(duì)線(xiàn)性規(guī)劃的介紹與實(shí)例分析，線(xiàn)性規(guī)劃的建模過(guò)程簡(jiǎn)單，首先是明確模型的目標(biāo)函數(shù)和約束方程，然后根據(jù)線(xiàn)性規(guī)劃解的求解方法和過(guò)程，很容易得到模型的全局最優(yōu)解。從結(jié)果可以看出，在滿(mǎn)足供水要求的前提下，供水效益最大，從而為水資源的合理配置提供了理論依據(jù)和基礎(chǔ)。但在生產(chǎn)實(shí)踐中，目標(biāo)函數(shù)與約束條件往往不是決策變量的線(xiàn)性函數(shù)，為了解決生產(chǎn)實(shí)際中的問(wèn)題，往往還需要用到非線(xiàn)性規(guī)劃法、動(dòng)態(tài)規(guī)劃法以及人工神經(jīng)網(wǎng)絡(luò)的應(yīng)用，滿(mǎn)足水資源優(yōu)化配置的更高要求。