R語言在幾類優化問題中的應用

摘要：R語言以其免費、開源、靈活、擴展程序包豐富等優點，在工程及科研領域得到越來越廣泛的應用。本文介紹了R語言的基本功能，并利用R語言的lpSolve、Rglpk、igraph擴展程序包來解決運籌學中的線性規劃、整數規劃、運輸問題、最短路問題、最小生成樹問題五類典型優化問題。

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.

關鍵詞：R語言;優化問題;程序包

Key words： R language;optimization problems;program package

中圖分類號：TP311.1? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1006-4311（2019）17-0238-03

0? 引言

當前，在優化問題的科學計算中，使用較多的是商業軟件如Matlab、Mathematica等，這類軟件功能強大、應用方便，但也存在著價格昂貴、體積龐大等缺點。而R作為一款免費的開源軟件，具有編程簡單、體積小巧、數據分析功能強大、擴展性能好等特點，在很多應用場合可以替代商業軟件。

1? R語言簡介

R語言是一種自由軟件編程語言與操作環境，主要用于統計分析、繪圖、數據挖掘等。最初是由新西蘭奧克蘭大學的Ross Ihaka和Robert Gentleman開發，因此稱為R，現在由“R開發核心團隊”負責開發和維護[1]。

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

2? 幾類優化問題的求解示例

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

本文示例中所用到的程序包有lpSolve、Rglpk、igraph。

2.1 線性規劃問題

例1：有一砌塊生產廠家生產兩種砌塊，其中一種是有顏色的。每生產有色砌塊1m3，需要2h機器時間、3h人工和2mm3顏料，利潤是150元/m3;每生產無色砌塊1m3，需要1h機器時間和4h人工，利潤是90元/m3。現共有10h機器時間、24h人工和8mm3顏料，問每一種砌塊生產多少，廠家所得利潤最大[5]。

求解此問題，可設生產有色砌塊x1 m3，生產無色砌塊x2 m3，則此問題的優化模型為：

可使用lpSolve程序包中的lp（ ）函數進行求解，函數的語法可以參閱lpSolve文件。

求解此問題的R代碼為：

目標函數z取得最大值即當有色砌塊和無色砌塊分別生產3.2m3和3.6m3時，廠家所得利潤最大，最大值為804元。

對于無可行解的線性規劃問題，lp（ ）函數也會給出提示。例如線性規劃模型：

程序會給出結果Error： no feasible solution found，即認為模型有誤，同時也說明線性規劃問題無可行解。

2.2 整數規劃問題

例2：某商場對售貨員的需求經過統計分析如表1所示。

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

2.3 運輸問題

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

此問題為運輸問題中的產銷平衡問題。運輸問題的本質也是一類線性規劃問題，可以利用lpSolve包中的lp.transport（ ）函數進行求解。求解此問題的R代碼為：

即A1向B1，B3分別調運2t，5t，A2向B1，B4分別調運1t，3t，A3向B2，B4分別調運6t，3t，此時總運費為85百元。需要說明的是，此問題的最優解不唯一。

對于產銷不平衡問題，也可以利用lp.transport（ ）函數進行求解。

例4：某公司從兩個產地A1，A2將物品運往三個銷地B1，B2，B3，各銷地的銷量以及從產地到銷地的每件物品的運輸單價（元/件）如表3所示。問：應如何組織運輸，使總運輸費用最小？

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

2.4 最短路問題

例5：里特城是一個農村的小鎮，它的消防隊要為包括許多農場社區在內的大片地區提供服務。這個地區有很多條路，從消防站到任何一個社區都有很多條路線。因為時間是到達火災發生點的主要因素，所以消防隊隊長希望事先能夠確定從消防站到每一個農場社區的最短路。

圖1示意了連接消防站和其中一個農場社區的道路系統（長度單位為km），O為消防站所在地，T為農場社區所在地，求O到T的最短路徑[8]。

此問題中，O為出發點，T為終點，最短路問題可使用igraph程序包進行求解，首先根據點、邊、權，在程序中構建出網絡，然后利用shortest.paths（ ）函數和get.shortest.paths（ ）函數求解最短路徑。

2.5 最小生成樹問題

例6：某單位準備對其所屬的7個值班室聯接局域網，這個網絡可能聯通的途徑如圖2所示，圖中v1、v2，…，v7表示7個分隊值班室，圖中的邊為可能聯網的途徑，邊上的所賦的權數為這條路線的長度，單位為百米。請設計一個網絡能聯通7個分隊值班室，并使總的線路長度為最短。

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

與例5類似，構建出網絡后，求最小生成樹的代碼如下：

程序運行結果如下：

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

3? 結束語

R語言最初只是一個統計分析軟件包，在統計學和數據處理方面應用廣泛。近年來，隨著版本的升級和擴展程序包的日益豐富，在優化問題處理方面的應用也逐漸增多。本文示例了R語言及擴展程序包在優化問題中最基本的應用，隨著進一步的開發，R語言在解決優化問題方面的優勢將更加明顯。

參考文獻：

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

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

[3]藍洋，何秀，朱誠勖，張玉娟.R語言在生物科學研究繪圖中的應用[J].華東師范大學學報（自然科學版），2019（1）：124-135.

[4]薛毅.數學建模：基于R[M].北京：機械工業出版社，2017.

[5]朱杰江.建筑結構優化及應用[M].北京：北京大學出版社， 2011.

[6]韓伯棠.管理運籌學[M].北京：高等教育出版社， 2015.

[7]孟麗莎.管理運籌學[M].北京：清華大學出版社，2011.

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

作者簡介：高成強（1981-），男，河北邯鄲人，講師，研究方向為工程管理。