運(yùn)籌學(xué)中關(guān)于幾類規(guī)劃問題的教學(xué)研究

徐 鑫

（安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥 230601）

1 引言

在經(jīng)典的運(yùn)籌學(xué)教材中線性規(guī)劃、目標(biāo)規(guī)劃以及多目標(biāo)規(guī)劃是分為三個獨(dú)立的章節(jié)進(jìn)行教學(xué)的，教材中所給出的例題也都是針對這三種規(guī)劃問題按照各自章節(jié)介紹的方法進(jìn)行優(yōu)化和計(jì)算，如清華大學(xué)版運(yùn)籌學(xué)教材[1]中第一章“線性規(guī)劃及單純形法”與第四章“目標(biāo)規(guī)劃”中涉及了許多應(yīng)用的例子，有生產(chǎn)安排的、有合理利用材料的以及人員分配等例子；而文獻(xiàn)[2-3]也僅僅對目標(biāo)規(guī)劃問題提出不同的優(yōu)化方法；上述這些文獻(xiàn)僅僅對所研究的規(guī)劃問題進(jìn)行研究，都沒有從這三種規(guī)劃的關(guān)系角度就探究它們的本質(zhì)聯(lián)系和區(qū)別，不具備一定靈活性、系統(tǒng)性；在教學(xué)過程中發(fā)現(xiàn)學(xué)生也只是機(jī)械的、單純的會去了解這三種規(guī)劃各自概念，然后按照書上給出的例題依葫蘆畫瓢地對相應(yīng)的規(guī)劃問題進(jìn)行求解，學(xué)習(xí)過程很刻板，且學(xué)習(xí)之后也不能很好地將相關(guān)章節(jié)內(nèi)容靈活地聯(lián)系在一起，達(dá)到融會貫通；久而久之，學(xué)生不僅對所學(xué)內(nèi)容理解不深刻，而且對相關(guān)章節(jié)聯(lián)系的理解脫節(jié)，從而不易提升學(xué)生自己對學(xué)習(xí)新知的能動性、創(chuàng)造性和方法論。因?yàn)楸疚囊晕墨I(xiàn)[1]中例題為引例，結(jié)合多年教學(xué)過程的經(jīng)驗(yàn)和心得來分析三種規(guī)劃問題的聯(lián)系，并得到有效的結(jié)論，為以后的教學(xué)創(chuàng)新提供綿薄之力。

2 可化為多目標(biāo)規(guī)劃問題的分析

2.1 線性規(guī)劃（LP）與目標(biāo)規(guī)劃（LGP）的研究

2.1.1 引例

以[1]中P102例1為例，題為：某工廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知有關(guān)數(shù)據(jù)見下表：

?

求獲利最大的生產(chǎn)方案。

由例中討論可用如下線性規(guī)劃描述

其中X1，X2表示生產(chǎn)產(chǎn)品Ⅰ、Ⅱ的件數(shù)。

該工廠的目的是要在不超過所有資源限量的條件下，如何確定X1，X2以得到最大利潤；所以上描述可轉(zhuǎn)化為目標(biāo)規(guī)劃問題，其描述如下：

其中a為任一常數(shù)。

2.1.2 歸納及分析

我們通過上例得如下歸納：

對標(biāo)準(zhǔn)LP問題：

我們可以將（1）轉(zhuǎn)化為LGP問題：

其中 a為任一常數(shù) i=1，2，…，m

也就是說從LGP角度來看（4）式是除去一個目標(biāo)外，把其余所有目標(biāo)（在LP里的約束條件）放在等同的優(yōu)先位置，要求它們必須盡可能地滿足，在此前提條件下，把剩下的一個目標(biāo)（在LP里稱為目標(biāo)函數(shù)）作為一級考慮因素予以最小化，顯然對于（4）與（3）式并不等價(jià)，但作為 LGP模型，（4）敘述更為靈活。事實(shí)上LP問題（3）有可行解當(dāng)且僅當(dāng)問題（4）第一級目標(biāo)值為零[4]，這時(shí)兩問題的含義是相同的；若問題（3）無可行解，則（4）可以在其特定的算法中找到近似的可行點(diǎn)。

2.1.3 兩種規(guī)劃方法比較

一般來說LGP問題比LP問題更具有靈活性，也往往更切合實(shí)際。在應(yīng)用型問題中，經(jīng)常存在多個目標(biāo)，這些目標(biāo)之間可能沖突，可能相互聯(lián)系，則此時(shí)滿意解往往比最優(yōu)解更具有現(xiàn)實(shí)意義。因?yàn)楦髂繕?biāo)優(yōu)先級、同級中權(quán)系統(tǒng)以及指標(biāo)值可由決策者提供。所以LGP與LP計(jì)算差別不大，同時(shí)LGP比LP更易求得結(jié)果。不過一旦數(shù)據(jù)改變，LGP問題也就隨之改變，就得重新計(jì)算。

2.2 目標(biāo)規(guī)劃與多目標(biāo)規(guī)劃的研究

上述的引例在實(shí)際作決策的時(shí)候，要考慮到市場等一系列其它條件，如：引例的決策在原材料供應(yīng)受嚴(yán)格限制的基礎(chǔ)上考慮：首先是產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量；其次是充分利用設(shè)備有效臺時(shí)，不加班；再次是利潤不小于56元；求決策方案。

由分析可列得目標(biāo)規(guī)劃為：

（5）中第一個條件是絕對約束條件，其余的是目標(biāo)約束；（5）式可轉(zhuǎn)化為多目標(biāo)規(guī)劃：

其中

而目標(biāo)規(guī)劃中 P1，P2，P3相當(dāng)于多目標(biāo)規(guī)劃中的權(quán)重，而權(quán)重是依實(shí)際情況由決策者而定；

我們可將上模型歸納為：

可將（6）式轉(zhuǎn)化為：

（7）中目標(biāo)函數(shù)中的權(quán)重 ω=（ω1，ω2，…，ωm）是由實(shí)際因數(shù)加上決策者的偏好而定。

2.3 單目標(biāo)規(guī)劃與多目標(biāo)規(guī)劃的關(guān)系

線性規(guī)劃是屬于單目標(biāo)規(guī)劃問題，但單目標(biāo)規(guī)劃有其自身優(yōu)點(diǎn)，在解決實(shí)際問題中也顯出了其不足之處。在現(xiàn)實(shí)生活和實(shí)際工作中遇到更為普遍的問題常常含有多個目標(biāo)，如生產(chǎn)問題中，又想使利潤達(dá)到最大，又想使耗電量達(dá)到最小等。該問題只用有限個約束條件的單目標(biāo)規(guī)劃是解決不了的，就得依靠多目標(biāo)規(guī)劃進(jìn)行求解，這就涉及到一個求解多目標(biāo)規(guī)劃問題。多目標(biāo)解法很多，有TOPSIS法、夾角向量法、層次分析法等等[5]。但要找一種方法把單目標(biāo)規(guī)劃與多目標(biāo)規(guī)劃有機(jī)結(jié)合在一起的方法——加權(quán)和法，見如下定理：

定理 已知多目標(biāo)決策問題：

當(dāng)各目標(biāo)權(quán)重 ω=（ω1，ω2，…，ωp）＞0 時(shí)，下列單目標(biāo)規(guī)劃決策問題

的最優(yōu)解必為多目標(biāo)決策的非劣解。

該定理可用K—T條件證明 。

該定理是將多目標(biāo)規(guī)劃轉(zhuǎn)化為單目標(biāo)規(guī)劃后，用圖象或單純形方法求解，但也有一定的局限性，對于多維情況則很難求解。

3 小結(jié)

本文通過對了運(yùn)籌學(xué)中一個經(jīng)典的線性規(guī)劃例子作為引例進(jìn)行研究，從教學(xué)角度對線性規(guī)劃（LP）、目標(biāo)規(guī)劃（LGP）及多目標(biāo)規(guī)劃（MLP）這三種常見的規(guī)劃的概念、內(nèi)在關(guān)系進(jìn)行研究，發(fā)現(xiàn)在實(shí)際中線性規(guī)劃和目標(biāo)規(guī)劃都可以轉(zhuǎn)化為多目標(biāo)規(guī)劃來進(jìn)行優(yōu)化，不僅能將這三種規(guī)劃融匯貫通理解本質(zhì)和含義，也為其它規(guī)劃問題的拓展研究提供理論和方法上教學(xué)借鑒。

從理論上看：線性規(guī)劃（LP）、目標(biāo)規(guī)劃（LGP）以及多目標(biāo)規(guī)劃（MLP）三者有著聯(lián)系，LGP是LP的推廣，顯然包括LP作為其特殊情況；在LGP中的優(yōu)先級就相當(dāng)于MLP中的權(quán)重，所以在某種意義上來說，MLP是LGP問題的推廣；所以LP、LGP都可以轉(zhuǎn)化為MLP來進(jìn)行求解。

從實(shí)踐上看：在日常生活中所遇到的實(shí)踐問題中，大多數(shù)都涉及到多個目標(biāo)和要求的，雖然有的可直接用LP和LGP去求解，但LP與LGP所解決的問題多限于一定變量個數(shù)，如遇大規(guī)模優(yōu)化問題，LP與LGP解決起來不太靈活；而對于MLP問題求解，我們大多可用軟件來實(shí)現(xiàn)，但對MLP求解中，由于權(quán)重取的不同，則結(jié)果也不盡相同，所以我們可以多取一些權(quán)重的形式多進(jìn)行幾次計(jì)算，找一個切合實(shí)際的滿意解即可。（因?yàn)樵诮鉀Q實(shí)際問題中，滿意解往往比最優(yōu)解更具有現(xiàn)實(shí)意義）。

了解的這三種規(guī)劃的概念、聯(lián)系，也為以后進(jìn)一步學(xué)習(xí)隨機(jī)規(guī)劃、模糊規(guī)劃做了鋪墊作用，這些規(guī)劃在理論上、方法上都是同出一轍，只是用不同的研究工具對規(guī)劃問題進(jìn)行研究，是的對實(shí)際問題的優(yōu)化問題的研究和討論更加與實(shí)際問題跟貼切。

[1] 運(yùn)籌學(xué)教材遍寫組.運(yùn)籌學(xué)（修改版）[M].北京：清華大學(xué)出版社，1990.

[2] 錢偉懿，楊菊，等.求解多目標(biāo)規(guī)劃問題的一種新的群體搜索算法[J].遼寧師范大學(xué)學(xué)報(bào)，2007，（2）：141-143.

[3] 劉旺梅，韓旭里.一種求解多目標(biāo)規(guī)劃的新方法[J].系統(tǒng)工程與電子技術(shù)，2001，（8）：15-17.

[4] 張建中，許紹吉.線性規(guī)劃[M].北京：科學(xué)出版社，1999.

[5] 邱箢華.管理決策與應(yīng)用熵學(xué)[M].機(jī)械工業(yè)出版社，2000.