R語言在幾類優(yōu)化問題中的應(yīng)用

摘要：R語言以其免費(fèi)、開源、靈活、擴(kuò)展程序包豐富等優(yōu)點(diǎn)，在工程及科研領(lǐng)域得到越來越廣泛的應(yīng)用。本文介紹了R語言的基本功能，并利用R語言的lpSolve、Rglpk、igraph擴(kuò)展程序包來解決運(yùn)籌學(xué)中的線性規(guī)劃、整數(shù)規(guī)劃、運(yùn)輸問題、最短路問題、最小生成樹問題五類典型優(yōu)化問題。

Abstract： R language is widely used in engineering and scientific research with its advantages of free， open source， flexible， and rich package. This paper introduces the basic functions of R language， and uses extended program package of lpSolve， Rglpk and igraph to solve four typical optimization problems in operations research， which are linear programming， integer programming， transportation problem， shortest path problem and minimum spanning tree problem.

關(guān)鍵詞：R語言;優(yōu)化問題;程序包

Key words： R language;optimization problems;program package

中圖分類號(hào)：TP311.1? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)：1006-4311（2019）17-0238-03

0? 引言

當(dāng)前，在優(yōu)化問題的科學(xué)計(jì)算中，使用較多的是商業(yè)軟件如Matlab、Mathematica等，這類軟件功能強(qiáng)大、應(yīng)用方便，但也存在著價(jià)格昂貴、體積龐大等缺點(diǎn)。而R作為一款免費(fèi)的開源軟件，具有編程簡(jiǎn)單、體積小巧、數(shù)據(jù)分析功能強(qiáng)大、擴(kuò)展性能好等特點(diǎn)，在很多應(yīng)用場(chǎng)合可以替代商業(yè)軟件。

1? R語言簡(jiǎn)介

R語言是一種自由軟件編程語言與操作環(huán)境，主要用于統(tǒng)計(jì)分析、繪圖、數(shù)據(jù)挖掘等。最初是由新西蘭奧克蘭大學(xué)的Ross Ihaka和Robert Gentleman開發(fā)，因此稱為R，現(xiàn)在由“R開發(fā)核心團(tuán)隊(duì)”負(fù)責(zé)開發(fā)和維護(hù)[1]。

R是一個(gè)統(tǒng)計(jì)分析的環(huán)境，由于很多統(tǒng)計(jì)方法在估計(jì)和求解的過程中都需要用到大量的優(yōu)化算法，因此R環(huán)境中自帶了一些優(yōu)化求解的函數(shù)，比如optim和constrOptim。此外，由于R是開源工具，因此可以借助很多第三方R包甚至其他的開源項(xiàng)目來實(shí)現(xiàn)很多優(yōu)化問題的求解[2]。用戶可以根據(jù)自己的需求編寫腳本、R包，即便是沒有任何編程功底，僅僅想使用也可以在CRAN社區(qū)（Comprehensive R Archive Network）上找到相對(duì)應(yīng)的R包[3]。

2? 幾類優(yōu)化問題的求解示例

由于R的基本庫功能有限，優(yōu)化問題的求解一般要使用擴(kuò)展程序包，需要到R的CRAN社區(qū)下載程序包來擴(kuò)展R的求解功能[4]。程序包的下載地址為：http：//cran.r-project.org。

本文示例中所用到的程序包有l(wèi)pSolve、Rglpk、igraph。

2.1 線性規(guī)劃問題

例1：有一砌塊生產(chǎn)廠家生產(chǎn)兩種砌塊，其中一種是有顏色的。每生產(chǎn)有色砌塊1m3，需要2h機(jī)器時(shí)間、3h人工和2mm3顏料，利潤(rùn)是150元/m3;每生產(chǎn)無色砌塊1m3，需要1h機(jī)器時(shí)間和4h人工，利潤(rùn)是90元/m3?，F(xiàn)共有10h機(jī)器時(shí)間、24h人工和8mm3顏料，問每一種砌塊生產(chǎn)多少，廠家所得利潤(rùn)最大[5]。

求解此問題，可設(shè)生產(chǎn)有色砌塊x1 m3，生產(chǎn)無色砌塊x2 m3，則此問題的優(yōu)化模型為：

可使用lpSolve程序包中的lp（ ）函數(shù)進(jìn)行求解，函數(shù)的語法可以參閱lpSolve文件。

求解此問題的R代碼為：

目標(biāo)函數(shù)z取得最大值即當(dāng)有色砌塊和無色砌塊分別生產(chǎn)3.2m3和3.6m3時(shí)，廠家所得利潤(rùn)最大，最大值為804元。

對(duì)于無可行解的線性規(guī)劃問題，lp（ ）函數(shù)也會(huì)給出提示。例如線性規(guī)劃模型：

程序會(huì)給出結(jié)果Error： no feasible solution found，即認(rèn)為模型有誤，同時(shí)也說明線性規(guī)劃問題無可行解。

2.2 整數(shù)規(guī)劃問題

例2：某商場(chǎng)對(duì)售貨員的需求經(jīng)過統(tǒng)計(jì)分析如表1所示。

為了保證售貨員休息時(shí)間，要求售貨員每周工作5天，休息2天，且休息的2天是連續(xù)的，問應(yīng)該如何安排售貨員的休息時(shí)間，既能夠滿足工作需要，又使售貨員的人數(shù)最少[6]

2.3 運(yùn)輸問題

例3：某食品公司有A1，A2，A3三個(gè)面包生產(chǎn)廠，每月產(chǎn)量分別為7t，4t，9t;有B1，B2，B3，B4四個(gè)銷售公司，每月銷量分別為3t，6t，5t，6t。從第i個(gè)面包生產(chǎn)廠到第j個(gè)銷售公司的單位運(yùn)價(jià)（百元/t）如表2所示，問：該公司應(yīng)如何調(diào)運(yùn)，在滿足各銷售點(diǎn)需求量的前提下，使總運(yùn)費(fèi)最少[7]？

此問題為運(yùn)輸問題中的產(chǎn)銷平衡問題。運(yùn)輸問題的本質(zhì)也是一類線性規(guī)劃問題，可以利用lpSolve包中的lp.transport（ ）函數(shù)進(jìn)行求解。求解此問題的R代碼為：

即A1向B1，B3分別調(diào)運(yùn)2t，5t，A2向B1，B4分別調(diào)運(yùn)1t，3t，A3向B2，B4分別調(diào)運(yùn)6t，3t，此時(shí)總運(yùn)費(fèi)為85百元。需要說明的是，此問題的最優(yōu)解不唯一。

對(duì)于產(chǎn)銷不平衡問題，也可以利用lp.transport（ ）函數(shù)進(jìn)行求解。

例4：某公司從兩個(gè)產(chǎn)地A1，A2將物品運(yùn)往三個(gè)銷地B1，B2，B3，各銷地的銷量以及從產(chǎn)地到銷地的每件物品的運(yùn)輸單價(jià)（元/件）如表3所示。問：應(yīng)如何組織運(yùn)輸，使總運(yùn)輸費(fèi)用最小？

此問題的求解與前述產(chǎn)銷平衡問題類似，但需要注意的是row.signs和col.signs約束條件的選取，row.signs表示按行（產(chǎn)地）的約束條件，row.signs表示按列（銷地）的約束條件。此問題中，row.signs = rep（"="， 2），col.signs = rep（"<="， 3）。

2.4 最短路問題

例5：里特城是一個(gè)農(nóng)村的小鎮(zhèn)，它的消防隊(duì)要為包括許多農(nóng)場(chǎng)社區(qū)在內(nèi)的大片地區(qū)提供服務(wù)。這個(gè)地區(qū)有很多條路，從消防站到任何一個(gè)社區(qū)都有很多條路線。因?yàn)闀r(shí)間是到達(dá)火災(zāi)發(fā)生點(diǎn)的主要因素，所以消防隊(duì)隊(duì)長(zhǎng)希望事先能夠確定從消防站到每一個(gè)農(nóng)場(chǎng)社區(qū)的最短路。

圖1示意了連接消防站和其中一個(gè)農(nóng)場(chǎng)社區(qū)的道路系統(tǒng)（長(zhǎng)度單位為km），O為消防站所在地，T為農(nóng)場(chǎng)社區(qū)所在地，求O到T的最短路徑[8]。

此問題中，O為出發(fā)點(diǎn)，T為終點(diǎn)，最短路問題可使用igraph程序包進(jìn)行求解，首先根據(jù)點(diǎn)、邊、權(quán)，在程序中構(gòu)建出網(wǎng)絡(luò)，然后利用shortest.paths（ ）函數(shù)和get.shortest.paths（ ）函數(shù)求解最短路徑。

2.5 最小生成樹問題

例6：某單位準(zhǔn)備對(duì)其所屬的7個(gè)值班室聯(lián)接局域網(wǎng)，這個(gè)網(wǎng)絡(luò)可能聯(lián)通的途徑如圖2所示，圖中v1、v2，…，v7表示7個(gè)分隊(duì)值班室，圖中的邊為可能聯(lián)網(wǎng)的途徑，邊上的所賦的權(quán)數(shù)為這條路線的長(zhǎng)度，單位為百米。請(qǐng)?jiān)O(shè)計(jì)一個(gè)網(wǎng)絡(luò)能聯(lián)通7個(gè)分隊(duì)值班室，并使總的線路長(zhǎng)度為最短。

此問題為最小生成樹問題，常規(guī)的解法一般為破圈法或避圈法[6]。此問題可使用igraph程序包中的minimum.spanning.tree（ ）函數(shù)求解。

與例5類似，構(gòu)建出網(wǎng)絡(luò)后，求最小生成樹的代碼如下：

程序運(yùn)行結(jié)果如下：

即找到了組成最小生成樹的6條邊，總長(zhǎng)度為1900米。

3? 結(jié)束語

R語言最初只是一個(gè)統(tǒng)計(jì)分析軟件包，在統(tǒng)計(jì)學(xué)和數(shù)據(jù)處理方面應(yīng)用廣泛。近年來，隨著版本的升級(jí)和擴(kuò)展程序包的日益豐富，在優(yōu)化問題處理方面的應(yīng)用也逐漸增多。本文示例了R語言及擴(kuò)展程序包在優(yōu)化問題中最基本的應(yīng)用，隨著進(jìn)一步的開發(fā)，R語言在解決優(yōu)化問題方面的優(yōu)勢(shì)將更加明顯。

參考文獻(xiàn)：

[1]薛毅，陳立萍.R語言實(shí)用教程[M].北京：清華大學(xué)出版社， 2014.

[2]李艦，肖凱.數(shù)據(jù)科學(xué)中的R語言[M].西安：西安交通大學(xué)出版社，2015.

[3]藍(lán)洋，何秀，朱誠勖，張玉娟.R語言在生物科學(xué)研究繪圖中的應(yīng)用[J].華東師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2019（1）：124-135.

[4]薛毅.數(shù)學(xué)建模：基于R[M].北京：機(jī)械工業(yè)出版社，2017.

[5]朱杰江.建筑結(jié)構(gòu)優(yōu)化及應(yīng)用[M].北京：北京大學(xué)出版社， 2011.

[6]韓伯棠.管理運(yùn)籌學(xué)[M].北京：高等教育出版社， 2015.

[7]孟麗莎.管理運(yùn)籌學(xué)[M].北京：清華大學(xué)出版社，2011.

[8]弗雷德里克 S.希利爾.數(shù)據(jù)、模型與決策[M].李勇建譯，北京：機(jī)械工業(yè)出版社，2015.

作者簡(jiǎn)介：高成強(qiáng)（1981-），男，河北邯鄲人，講師，研究方向?yàn)楣こ坦芾怼?/p>