楊依晨，柏 旭，李厚彪

（電子科技大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，四川 成都 611731）

優(yōu)化模型在數(shù)學(xué)建模中的應(yīng)用

楊依晨，柏 旭，李厚彪

（電子科技大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，四川 成都 611731）

在當(dāng)今社會(huì)，數(shù)學(xué)建模因其應(yīng)用的廣泛性，受到人們越來越多的關(guān)注，而優(yōu)化模型是其中最常用的模型之一。該文首先簡要介紹了優(yōu)化模型的3要素、一般建立步驟及分類；然后根據(jù)分類標(biāo)準(zhǔn)，整理了2000年至今的數(shù)學(xué)建模國賽中應(yīng)用優(yōu)化模型的題目；重點(diǎn)根據(jù)決策變量、目標(biāo)函數(shù)的分類標(biāo)準(zhǔn)，分析了應(yīng)用整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃及多目標(biāo)規(guī)劃的部分國賽題目，并給出了具體的優(yōu)化模型范例。該文還介紹了最優(yōu)化模型的解法，并總結(jié)了優(yōu)化模型在數(shù)學(xué)建模中應(yīng)用的重要性。

優(yōu)化模型；數(shù)學(xué)建模；動(dòng)態(tài)規(guī)劃；整數(shù)規(guī)劃；多目標(biāo)規(guī)劃

數(shù)學(xué)建模是聯(lián)系數(shù)學(xué)與實(shí)際問題的橋梁，是數(shù)學(xué)在各個(gè)領(lǐng)域廣泛應(yīng)用的媒介，是數(shù)學(xué)科學(xué)技術(shù)轉(zhuǎn)化的主要途徑。數(shù)學(xué)建模在科學(xué)技術(shù)發(fā)展中的重要作用越來越受到數(shù)學(xué)界和工程界的普遍重視，已成為現(xiàn)代科技工作者必備的重要能力之一。數(shù)學(xué)建模的關(guān)鍵在于建立合理的數(shù)學(xué)模型，而建立數(shù)學(xué)模型的方法有很多，其中，最優(yōu)化思想作為解決數(shù)學(xué)問題的重要思想之一，在解決實(shí)際問題中具有指導(dǎo)意義［1］。

1 優(yōu)化模型

1.1 優(yōu)化模型三要素及一般建立步驟

優(yōu)化模型［2－4］是數(shù)學(xué)建模中最常用的模型之一。建立優(yōu)化模型有以下3要素。

1）決策變量和參數(shù)

決策變量是由數(shù)學(xué)模型的解確定的未知數(shù)。參數(shù)表示系統(tǒng)的控制變量，有確定性的也有隨機(jī)性的。

2）約束或限制條件

由于現(xiàn)實(shí)系統(tǒng)的客觀物質(zhì)條件限制，模型必須包括把決策變量限制在其可行值之內(nèi)的約束條件，而這通常是用約束的數(shù)學(xué)函數(shù)形式來表示的。

3）目標(biāo)函數(shù)

這是作為系統(tǒng)決策變量的一個(gè)數(shù)學(xué)函數(shù)來衡量系統(tǒng)的效率，即系統(tǒng)追求的目標(biāo)。

建立優(yōu)化模型處理實(shí)際問題的一般步驟是：1）將實(shí)際問題抽象成數(shù)學(xué)問題，收集有關(guān)數(shù)據(jù)和資料；2）建立優(yōu)化問題的數(shù)學(xué)模型，確定變量，列出目標(biāo)函數(shù)和約束條件；3）求解，一般通過編制程序，用計(jì)算機(jī)求最優(yōu)解；4）最優(yōu)解的檢驗(yàn)和實(shí)施，將結(jié)果運(yùn)用到實(shí)際中，得到該問題的優(yōu)化解決方案。

1.2 優(yōu)化模型分類

優(yōu)化方法涉及的應(yīng)用領(lǐng)域很廣，問題種類與性質(zhì)繁多，根據(jù)不同的原則可以給出不同的分類。按照有無約束條件可分為無約束最優(yōu)化和有約束最優(yōu)化；按照函數(shù)是否線性可分為線性規(guī)劃和非線性規(guī)劃；根據(jù)決策變量、目標(biāo)函數(shù)的不同要求可分為整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃、網(wǎng)絡(luò)規(guī)劃、隨機(jī)規(guī)劃、幾何規(guī)劃以及多目標(biāo)規(guī)劃；根據(jù)問題的連續(xù)性可分為決策最優(yōu)化和組合最優(yōu)化，等等。

2 歷年數(shù)學(xué)建模國賽中應(yīng)用優(yōu)化模型的題目

2000年至今的數(shù)學(xué)建模國賽中用到典型的最優(yōu)化方法的題目［5］在表1中列出。根據(jù)1.2節(jié)的分類標(biāo)準(zhǔn)可對(duì)每個(gè)問題進(jìn)行分類。例如，2008年的高等教育學(xué)費(fèi)探討問題，其中就用到了最優(yōu)化方法中的多目標(biāo)規(guī)劃；2001和2007年的公交車優(yōu)化調(diào)度問題不僅用到了最優(yōu)化方法，也用到了圖論的思想；2013年的碎紙片拼接問題用到了整數(shù)規(guī)劃；2014年的嫦娥三號(hào)軟著陸軌道確定和最優(yōu)控制研究是一個(gè)典型的連續(xù)性最優(yōu)化問題。

表1 歷年數(shù)學(xué)建模國賽中應(yīng)用優(yōu)化模型的問題

3 優(yōu)化模型在數(shù)學(xué)建模國賽中的應(yīng)用分析

在實(shí)際問題的應(yīng)用中，優(yōu)化模型通常解決非線性規(guī)劃與有約束條件的問題［6］。因此，本文主要根據(jù)決策變量、目標(biāo)函數(shù)要求不同的分類方式，將優(yōu)化問題分為建模中最常見的整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃及多目標(biāo)規(guī)劃3種形式進(jìn)行舉例分析。以2012年太陽能小屋問題、2013年碎紙片的拼接問題及2014年創(chuàng)意平板折疊桌問題的國賽題目為例，給出建立模型的全過程。

3.1 動(dòng)態(tài)規(guī)劃——?jiǎng)?chuàng)意平板折疊桌問題

動(dòng)態(tài)規(guī)劃是通過把原問題分解為相對(duì)簡單的子問題來求解復(fù)雜問題的方法，主要適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題［7］。下面以數(shù)學(xué)建模國賽題（2014B）為例來說明動(dòng)態(tài)規(guī)劃的應(yīng)用。

題目1：某公司生產(chǎn)一種可折疊的桌子，桌面呈圓形，桌腿隨著鉸鏈的活動(dòng)可以平攤成一張平板。桌腿由若干根木條組成，分成兩組，每組各用一根鋼筋將木條連接，鋼筋兩端分別固定在桌腿各組最外側(cè)的兩根木條上，并且沿木條有空槽以保證滑動(dòng)的自由度。試建立模型描述此折疊桌的動(dòng)態(tài)變化過程。

分析：題目要求建立數(shù)學(xué)模型來描述此折疊桌的動(dòng)態(tài)變化過程，也就是將折疊桌的變化過程分成若干步驟，再對(duì)每一步進(jìn)行求解。為了分析折疊桌的動(dòng)態(tài)變化過程，結(jié)合折疊桌的對(duì)稱性，可將1／4的圓形桌面作為研究對(duì)象，考慮當(dāng)折疊桌最外側(cè)木條與地面夾角一定時(shí)內(nèi)部各木條所在直線與地面的夾角大小。

解答：假設(shè)折疊桌面半徑為R，第i根木條的長度為li（i＝1，2，…，10），折疊桌最外側(cè)木條與地面夾角為β，則當(dāng)折疊桌成型立在地面時(shí)β達(dá)到最大值，有

式中：H為折疊桌面高度，單位為cm；h為長方形平板的高度，單位為cm；l10為折疊桌最外側(cè)木條的長度，單位為cm。

當(dāng)折疊桌最外側(cè)木條與地面夾角為β時(shí)，設(shè)各木條與桌面連接處的頂點(diǎn)坐標(biāo)為Pi（i＝1，2，…，10），鋼筋在各木條中的坐標(biāo)為Qi（i＝1，2，…，10），根據(jù)Pi和Qi，可得第i根木條所在直線的方向向量ei。

由式（2）得到第i根木條所在直線的方向向量ei，結(jié)合幾何關(guān)系，第i根木條與地面的夾角βi等于ei與y軸方向向量的夾角，即

綜合式（1）～式（3），可得當(dāng)β一定時(shí)，第i根木條與地面的夾角：

通過木條與地面的夾角βi，可以得到此折疊桌在展開過程中的動(dòng)態(tài)變化過程。

3.2 整數(shù)規(guī)劃——碎紙片的拼接

將規(guī)劃中的變量（全部或部分）限制為整數(shù)，稱為整數(shù)規(guī)劃。整數(shù)規(guī)劃的一種特殊情形是0－1規(guī)劃，它的變數(shù)僅限于0或1［8］。下面以2013年B題碎紙片的拼接為例說明0－1規(guī)劃的應(yīng)用。

題目2：對(duì)于給定的來自同一頁印刷文字文件的碎紙機(jī)破碎紙片建立碎紙片拼接復(fù)原模型。

分析：對(duì)于碎紙片的拼接與復(fù)原問題，追求復(fù)原圖與原圖誤差最小，因而拼接時(shí)應(yīng)考慮任意兩片碎紙片邊緣相似度最大為拼接原則。自然，所建模型為優(yōu)化模型。

解答：

1）目標(biāo)

對(duì)碎紙片進(jìn)行左右拼接時(shí)，以邊緣相似度最大為目標(biāo)，即：

式中，定義Cpq為任兩張紙片p與q之間的邊緣相似度，表示兩碎紙片之間左右邊緣0－1值相同的格點(diǎn)占總格點(diǎn)個(gè)數(shù)的百分比。將紙片的圖像像素設(shè)為1 980×72，設(shè)紙片個(gè)數(shù)n＝19，bijk為第k個(gè)紙片對(duì)應(yīng)的0－1矩陣；矩陣bijk的行數(shù)l＝1 980，列數(shù)為m＝72，其中bijk＝1表示白色，bijk＝0表示黑色。

式中，1≤p≤19，1≤q≤19并且p≠q。

2）約束條件

每個(gè)碎紙片由左邊進(jìn)入拼接的時(shí)候，表示由碎紙片左邊緣為入口來拼接，則有：

式（7）對(duì)所有q成立。

每個(gè)圖只能從右邊出去進(jìn)行拼接，表示由碎紙片右邊緣為出口進(jìn)行拼接，則有

式（7）中，xpq為0－1變量，（1－bilq）≠0表示左邊緣不是全為白色，即碎紙片不在最左邊的，它的左邊仍存在紙片與其相連，反之則該碎紙片為最左端，不存在紙片位于其左端；式（8）中，（1－bi72p）≠0表示右邊緣不是全白色，即碎紙片的位置不在最右端。它的右邊仍有紙片與其相連，反之右邊沒有紙片與其相連。此外，還需

式（9）～式（11）表示碎紙片拼接時(shí)除最左端和最右端外，各碎紙片不構(gòu)成圈。

綜上所述，將圖像復(fù)原的問題類比轉(zhuǎn)化為圖論問題，建立優(yōu)化模型為：目標(biāo)函數(shù)為式（5）；約束條件為式（8）～式（11）。

3.3 多目標(biāo)規(guī)劃——太陽能小屋

多目標(biāo)規(guī)劃主要用于解決多于一個(gè)目標(biāo)在給定區(qū)域上的最優(yōu)化問題［9］。

題目3：對(duì)于太陽能小屋設(shè)計(jì)問題建立優(yōu)化模型，解決貼附、架空兩種安裝方式下，小屋外表面光伏電池陣列最優(yōu)鋪設(shè)的問題。

分析：該問題是典型的優(yōu)化問題，要求解決在房屋表面太陽能的最優(yōu)鋪設(shè)與設(shè)計(jì)問題?？紤]貼附鋪設(shè)方案關(guān)鍵在于選定光伏電池組件、逆變器及確定鋪設(shè)方式，而結(jié)合房屋各個(gè)立面的尺寸的鋪設(shè)（避開窗戶和門）限制了光伏電池組和逆變器的選擇。光伏組件的電壓和功率限制了逆變器的選擇?；谏鲜鰲l件限制，可以考慮將房屋立面切割為矩形塊，并在矩形塊中放置光伏組件與逆變器捆綁成的電池組件分組陣列（矩形）。下面給出雙目標(biāo)規(guī)劃模型進(jìn)行參考。

解答：

1）目標(biāo)

全年太陽能光伏電池轉(zhuǎn)化的交流電總電量最多；單位發(fā)電量的成本費(fèi)用最少，即

式中：E為交流總電量，單位為J；Q為太陽光照一年總輻射強(qiáng)度，單位為W／m2；P為總成本，單位為元。

2）約束條件

A.房屋墻面（或屋頂面）長度的約束，即所有橫鋪的矩形的長與豎鋪的矩形的寬之和需小于墻面的長度，即

B.房屋墻面（或屋頂面）寬度的約束，即所有橫鋪的矩形的寬與豎鋪的矩形的長之和需小于墻面的寬度，即

C.第i種矩形豎放個(gè)數(shù)不超過總數(shù)，即

D.第i種矩形豎放個(gè)數(shù)不超過總數(shù)，即

E.第i類矩陣中型號(hào)為j的電池的約束

首先約定矩陣中電池、逆變器只能橫鋪放置，且一個(gè)矩形中只能放置一個(gè)逆變器電池組件長度的最大值＋逆變器長度＝矩形的長，即：

F.電池組件寬度與逆變器寬度的最大值等于矩形的寬，即：

G.電壓要求

由題目要求，多個(gè)光伏組件串聯(lián)后可以再進(jìn)行并聯(lián)，并聯(lián)的光伏組件端電壓相差不應(yīng)超過10，可以得到

H.功率要求

由題目要求，逆變器的選配容量應(yīng)不小于光伏電池組件分組安裝的容量，可以得到

最終的優(yōu)化模型：目標(biāo)函數(shù)為式（12）；約束條件為式（14）～式（21）。

4 解法簡介

在求解最優(yōu)化問題時(shí)，最常用的方法是單純形法和對(duì)偶理論。而在實(shí)際中常見的是非線性規(guī)劃問題，其求解的總體思想是進(jìn)行局部線性化使問題簡化，可以用最速下降法、共軛方向法、牛頓法或擬牛頓法等方法求解。目前，非線性規(guī)劃問題還沒有一個(gè)統(tǒng)一的解法，在數(shù)學(xué)建模的求解中，也是對(duì)某一類問題給出特定的算法，如遺傳算法、模擬退火算法、蟻群算法等。這些算法可以通過MAT LAB［10］、LINGO［11］、Mathematic等相應(yīng)專業(yè)軟件來實(shí)現(xiàn)。

5 結(jié)束語

優(yōu)化方法的應(yīng)用非常廣泛，主要有以下7個(gè)方面：1）微分學(xué)中求極限；2）無約束最優(yōu)化問題；3）常用微分公式；4）凸集與凸函數(shù)；5）等式約束最優(yōu)化問題；6）不等式約束最優(yōu)化問題；7）變分學(xué)中求極限。在求解這些數(shù)學(xué)問題時(shí)，我們會(huì)大量地用到最優(yōu)化模型，而在解決實(shí)際問題時(shí)，我們也常會(huì)用到最優(yōu)化理論。

［1］姜啟源，謝金星，葉俊.數(shù)學(xué)建模［M］.4版.北京：高等教育出版社，2011.

［2］陳寶林.最優(yōu)化理論與算法［M］.北京：清華大學(xué)出版社，2005.

［3］郭科，陳聆，魏友華.最優(yōu)化方法及其應(yīng)用［M］.北京：高等教育出版社，2007.

［4］高曉夢，賀祖國.最優(yōu)化方法與數(shù)學(xué)建模［EB／OL］.北京：中國科技論文在線［2010－01－26］.http：／／www.paper.edu.cn／releasepaper／content／201001－1097.

［5］劉來福，曾文藝.數(shù)學(xué)模型與數(shù)學(xué)建模［M］.3版.北京：北京師范大學(xué)出版社，2003

［6］胡運(yùn)紅.非線性最優(yōu)化問題及其算法研究［J］.運(yùn)城學(xué)院學(xué)報(bào)，2003，21（3）：9－10.

［7］胡運(yùn)權(quán).運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用［M］.6版.武漢：武漢大學(xué)出版社，2014.

［8］VASERSTEIN L N，BYRNE C C.線性規(guī)劃導(dǎo)論［M］.謝金星，姜啟源，張立平，譯.北京：機(jī)械工業(yè)出版社，2006.

［9］傅家良.運(yùn)籌學(xué)方法與模型［M］.上海：復(fù)旦大學(xué)出版社，2014.

［10］董文永.最優(yōu)化技術(shù)與數(shù)學(xué)建模［M］.北京：清華大學(xué)出版社，2010.

［11］卓金武.MATLAB在數(shù)學(xué)建模中的應(yīng)用［M］.北京：北京航空航天大學(xué)出版社，2014.

［12］謝金星.優(yōu)化建模與LINDO／LINGO軟件［M］.北京：清華大學(xué)出版社，2005.

The App lication of Optim ization M odel in M athematical M odeling

YANG Yichen，BAIXu，LIHoubiao
（School of Mathematics Sciences，University of Electronic Science and Technology of China，Chengdu 611731，China）

Mathematicalmodeling is gainingmore and more attention because of its extensive application.The optimizationmodel is one of themost commonly used models.Firstly，this paper introduces the three elements of the optimization model，the general es tablishment of steps and classifications.Then，according to the classification criteria，this paper lists several subjects using the optimi zation model from Contemporary Undergraduate Mathematical Contest in Modeling since 2000.According to the classification standard of decision variables and objective functions，the subject of application of integer programming，dynamic programming and multi－objec tive programming are analyzed and a specific example of them is given.At the same time，the solution of the optimizationmodel is sim ply introduced.Finally，we summarized up the application of optimization model in mathematicalmodeling．

optimization model；mathematical modeling；dynamic programming；integer programming；multi－objective pro gramming

O151.2

A

10.3969／j.issn.1672－4550.2017.03.006

2015－11－25；修改日期：2017－04－15

電子科技大學(xué)教學(xué)研究（Y03003023901002010）。

楊依晨（1995－），女，本科，學(xué)生，主要從事數(shù)學(xué)建模和應(yīng)用數(shù)學(xué)方面的研究。

李厚彪（1976－），副教授，lihoubiao0189＠163.com