数理最適化ツールとしてのR
5
0
0
全文
(2) 北海道教育大学紀要（自然科学編）第67巻 第１号 Journal of Hokkaido University of Education（Natural Sciences）Vol. 67, No.1. 平 成 28 年 ８ 月 August, 2016. 数理最適化ツールとしてのR 若 林 高 明 北海道教育大学旭川校数学教育教室. R as an Mathematical Optimization Tool WAKABAYASHI Taka’aki Department of Mathematics Education, Asahikawa Campus, Hokkaido University of Education. ABSTRACT Mathematical optimization is the selection of a best element with regard to some criteria from some set of available alternatives. R is a free software environment for statistical computing and graphics. R can be available as an optimization tool by using some packages. In this paper, we present how to use of R as an optimization tool with some examples.. １ はじめに 数理最適化とは，実際の問題を数式として書き下すことを通じて，最適解もしくはそれに近い解を得るた めの方法論である［1］。Rは，元来，統計解析用のフリーソフトウェアであるが［2］，拡張機能として，統計解 ［4］ 。これらを利用することで，Rを最適化ツー 析用途にとどまらない数多のパッケージが開発されている［3］. ルとして利用できる。この方法を用いることで，例えば，商用数理計画ソフトウェアやExcelの拡張機能を 用いる等の方法に比べて，より簡便かつ低コストで最適化を実行できると考えられる。本稿では，幾つかの 例題を通じてこのことを検証する。. 2 Rのパッケージを用いた最適化 2.1 lpSolveパッケージの利用 数理最適化問題のうち，最も基本的かつ簡単なものは，目的関数および制約条件がすべて一次式で表現さ れる線形最適化問題である。線形最適化問題を解くためのRパッケージに，lpSolveパッケージがある。この パッケージは，線形計画問題，整数計画問題，0-1 整数計画問題に対応している。線形計画問題は，制約条 件及び目的関数が共に一次式で表される最適化問題である。整数計画問題は，制約条件における変数の値を 整数に限定したものであり，0-1 整数計画問題は，更に 0 と 1 に限定したものである。. 1.
(3) 若 林 高 明. 他の多くの最適化問題が上記の問題に帰着できるため，このパッケージの利用価値は高いと考えられる。 以下，線形計画問題の例題を示す。 例題１ （線形計画問題）. 1＋2x2 ≦ 4 x 制約条件 最大化 x1＋x2 2x1＋x2 ≦ 4 . この例題は，2 変数の線形計画問題（最大化問題）なので，x1-x2 平面上のグラフを描くことで，最適解 4 8 が求められる（x1＝x2＝ のとき目的関数の値 ）。以下，lpSolveパッケージを用いて，R上でこの例題を解 3 3 く例を示す。使用したRのバージョンは，3.1.2（Windows版）である。R本体及び必要なパッケージがイン ストールされた状態でRを起動し，Rコンソールから以下のコマンドを実行する。但し，以下，特に断らな いかぎり，行頭の ’>’ は，Rコンソールのコマンドプロンプトを表し，’#’ > library(lpSolve) ɹɹɹɹ# lpSolve ύοέʔδͷಡΈࠐΈ は，その行の以下がコメントであ. > f_obj<-c(1,1) ɹɹɹɹ# తؔͷ ることを表す。. > f_con<-matrix(c(1,2,2,1),ncol=2,byrow=T) ɹɹɹɹ > ɹɹɹɹ# lpSolve ύοέʔδͷಡΈࠐΈ # library(lpSolve) ੍ࣜͷߦྻ (2 ྻɼཁૉΛߦ͝ͱʹಡΈࠐΉ ) > f_obj<-c(1,1) ɹɹɹɹ # తؔͷ > f_dir <- c("<=", "<=") ɹɹɹɹɹɹɹ# ੍ࣜͷෆ߸ > ɹɹɹɹ > f_con<-matrix(c(1,2,2,1),ncol=2,byrow=T) r_rhs<-c(4,4) ɹɹɹɹɹɹɹɹɹɹɹɹ# ੍ࣜͷӈล # (2 ྻɼཁૉΛߦ͝ͱʹಡΈࠐΉ ) # ࠷େԽΛղ͘ > ੍ࣜͷߦྻ lp("max",f_obj,f_con,f_dir,r_rhs) ɹɹɹ > f_dir <c("<=", "<=") ɹɹɹɹɹɹɹ # ੍ࣜͷෆ߸ Success: the objective function is 2.666667 > ɹɹɹɹɹɹɹɹɹɹɹɹ # ੍ࣜͷӈล # r_rhs<-c(4,4) ࠷దղʹର͢Δతؔͷ =2.666667 > ɹɹɹ# ࠷େԽΛղ͘ > lp("max",f_obj,f_con,f_dir,r_rhs) lp("max",f_obj,f_con,f_dir,r_rhs)$solution Success: the objective function is 2.666667 [1] 1.333333 1.333333 # # ࠷దղʹର͢Δతؔͷ ࠷దղ x1 = x2 = 1.333333 =2.666667 > lp("max",f_obj,f_con,f_dir,r_rhs)$solution [1] 1.333333 1.333333 # ࠷దղ x1 = x2 = 1.333333. 以下，整数計画問題の例題および，これをR上で解く例を示す。 例題２ （整数計画問題）. . x1＋2x2＋3x3 ≦ 9 制約条件 3x1＋2x2＋2x3 ≦ 15 最大化 x1＋9x2＋3x3 x1, x2, x3 は整数. > library(lpSolve) > f.obj<-c(1,9,3) ɹɹɹɹ# తؔͷ > f.con<-matrix(c(1,2,3,3,2,2),nrow=2,byrow=T) > # library(lpSolve) ੍ࣜͷߦྻ (3 ྻɼཁૉΛߦ͝ͱʹಡΈࠐΉ) > f.obj<-c(1,9,3) ɹɹɹɹ # తؔͷ > f.dir<-c("<=","<=") ɹɹɹɹɹɹɹ # ੍ࣜͷෆ߸ > f.con<-matrix(c(1,2,3,3,2,2),nrow=2,byrow=T) > f.rhs<-c(9,15) ɹɹɹɹɹɹɹɹɹɹɹɹ# ੍ࣜͷӈล # (3 ྻɼཁૉΛߦ͝ͱʹಡΈࠐΉ) > ੍ࣜͷߦྻ lp("max",f.obj,f.con,f.dir,f.rhs,int.vec=1:3) ɹɹɹɹ# ࠷େԽΛղ͘ > f.dir<-c("<=","<=") ɹɹɹɹɹɹɹ # ੍ࣜͷෆ߸ Success: the objective function is 37 > ɹɹɹɹɹɹɹɹɹɹɹɹ # ੍ࣜͷӈล # f.rhs<-c(9,15) ࠷దղʹର͢Δతؔͷ =37 > ɹɹɹɹ# ࠷େԽΛղ͘ > lp("max",f.obj,f.con,f.dir,f.rhs,int.vec=1:3) lp("max",f.obj,f.con,f.dir,f.rhs,int.vec=1:3)$solution Success: the objective function is 37 [1] 1 4 0 # # ࠷దղʹର͢Δతؔͷ ࠷దղ x1 = 1, x2 = 4, x3 = 0=37 > lp("max",f.obj,f.con,f.dir,f.rhs,int.vec=1:3)$solution [1] 1 4 0 以下，0-1 整数計画問題の例題およびこれをR上で解く例を示す。 # ࠷దղ x1 = 1, x2 = 4, x3 = 0 2.
(4) 数理最適化ツールとしての R. 例題３ （0-1 整数計画問題）. 1＋3x2＋4x3＋5x4 ≦ 7 2x 制約条件 最大化 16x1＋19x2＋23x3＋28x4 x1, x2, x3, x4 ∈ { 0, 1} . この問題は，重さがそれぞれ，2,3,4,5［kg］，価値がそれぞれ，16,19,23,28［万円］の品物 x1～ x4 が１つずつ あるとき，7kgまで詰められるナップサックに，価値が最大となるような品物の組み合わせを選んで詰める という，いわゆる 0-1 ナップサック問題と呼ばれる問題である［5］。. > library(lpSolve) > v<-c(16,19,23,28) ɹɹɹɹ# ͷՁͷϕΫτϧ > w<-matrix(c(2,3,4,5),nrow=1) ɹɹɹɹ# ͷॏ͞ͷߦྻ > lp("max", v, w, "<=", 7, all.bin=T) ɹɹɹɹ# ࠷େԽΛղ͘ Success: the objective function is 44 # ࠷దղʹର͢Δతؔͷ=44 > lp("max", v, w, "<=", 7, all.bin=T)$solution [1] 1 0 0 1 # ࠷దղ x1 = 1, x2 = x3 = 0, x4 = 1. 2.2 quadprogパッケージの利用 二次計画問題は，目的関数が二次式，すべての制約条件が一次式で表現される数理最適化問題である。 quadprogパッケージは，二次計画問題を解くためのパッケージである。以下，二次計画問題の例題および quadprogパッケージを用いてR上でこれを解く例を示す。 ［6］ 例題４ （二次計画問題）. . x1＋x2 ≦ 2 －x1＋2x2 ≦ 2 制約条件 最大化 1 x 21＋x 22＋x1x2－2x1－6x2 2x1＋x2 ≦ 3 2 0 ≦ x1, 0 ≦ x2 行列表記を用いると，目的関数 （x） f は以下のように書ける。 （x） f ＝ 1 xT Hx＋f Tx 2. ここで， H＝. 1 －1 , f＝ －2 , x＝ －1 2 －6 . x1 x2. . である。 制約条件を以下のように書く。 AT x ≧ bT ここで， A＝. －1 1 －2 , b＝ －1 －2 －1 . －2 －2 －3 . である。. 3.
(5) 若 林 高 明. > library(quadprog) ɹɹɹɹɹ# quadprog ύοέʔδͷಡΈࠐΈ > H <- matrix(c(1,-1,-1,2),2,2) > f <- c(2,6) > b <- c(-2,-2,-3) > A <- matrix(c(-1,-1,1,-2,-2,-1),2,3) > solve.QP(H,f,A,b) ɹɹɹɹ# solve.QP ͷ݁ՌҰ෦ͷΈදࣔ $solution ɹ [1] 0.6666667 1.3333333 # ࠷దղ x1 = 0.6666667, x2 = 1.3333333 $value [1] -8.222222 # ࠷దղʹର͢Δతؔͷ = −8.222222. ３ おわりに 本稿においては，統計解析ソフトウェアRを数理最適化ツールとして利用できることを検証し，幾つかの 数理最適化問題のR上での解法の例を示した。Rを利用した数理最適化は，この分野の初学者にとっても， 比較的理解しやすいアプローチであると考えられる。今後の課題としては，現実的問題に適用し，その実用 性を確認することなどが挙げられる。. 参考文献 ［１］久保幹雄，J.P. ペドロソ，村松正和，A. レイス，あたらしい数理最適化Python言語とGurobiで解く，近代科学社（2012） ［２］The R Project for Statistical Computing, https://www.r-project.org（2016年３月30日確認） ［３］長畑秀和，大橋和正，Rで学ぶ経営工学の手法，共立出版（2008） ［４］Rjpwiki，http://www.okadajp.org/RWiki/?RjpWiki（2016年３月23日確認） ［５］OR事典Wiki，http://www.orsj.or.jp/wiki/wiki/index.php/ナップサック問題（2016年３月30日確認） ［６］ 二 次 計 画 法 －MATLAB quadprog－MATHWORKS日 本，http://jp.mathworks.com/help/optim/ug/quadprog.htm （2016年３月29日確認）. （旭川校准教授）. 4.
(6)
関連したドキュメント
Mathematical Modelling of Tumour Angiogenesis and the Action of Angiostatin as a Protease Inhibitor*
In this paper a mathematical model of tumour angiogen- esis has been described on the basis of the chemical kinetics governing the chemistry of angiogenic factors, protease activity
本研究所は、いくつかの出版活動を行っている。「Publications of RIMS」
We present the new multiresolution network flow minimum cut algorithm, which is es- pecially efficient in identification of the maximum a posteriori (MAP) estimates of corrupted
In this paper, taking into account pipelining and optimization, we improve throughput and e ffi ciency of the TRSA method, a parallel architecture solution for RSA security based on
We present the new multiresolution network flow minimum cut algorithm, which is es- pecially efficient in identification of the maximum a posteriori (MAP) estimates of corrupted
Research in mathematics education should address the relationship between language and mathematics learning from a theoretical perspective that combines current perspectives
We have found that the model can account for (1) antigen recognition, (2) an innate immune response (neutrophils and macrophages), (3) an adaptive immune response (T cells), 4)
* Department of Mathematical Science, School of Fundamental Science and Engineering, Waseda University, 3‐4‐1 Okubo, Shinjuku, Tokyo 169‐8555, Japan... \mathrm{e}
