Rで数理計画

(例題など、どんどん付け足してください。)

ここでは、Rの関数を利用した数理計画問題の解法を説明します。 Rでも既存の関数を利用して、制約条件付き最適化問題を解くことができます。


線形計画法/整数計画法

LP。目的関数が1次(linear)で、制約条件が1次不等式で表現される数理計画問題。

simplex 関数(bootパッケージ)

パッケージ boot の関数 simplex() を利用します。

solveLP 関数(linprogパッケージ)

シンプレックス法を用いてLPを解く。linprogパッケージには,MPS形式のファイルを読みこむ,readMPS関数なども含まれている。 LPの解(最適解,最大(小)値)とともに,双対変数(シャドウバリュー)や感度分析の結果を得ることもできる。 linprog(線形計画/最適化)パッケージ中のオブジェクト一覧

lp関数(lpSolve パッケージ)

ソルバーとして,lp_solveを利用している。整数計画法(および0‐1整数計画問題)にも対応*1。 lpSolve パッケージには割り当て問題や輸送問題の関数もある。lpSolve(線形・整数問題解法用 Lp_solve インターフェース)パッケージ中のオブジェクト一覧

lpSolveAPI(Interface to lp_solve v. 5.5)

機能は上と同じ?

glpk パッケージ

glpk(Gnu Linear Programming Kit)へのインターフェイスを提供。

Rglpk パッケージ

R interface to the GNU Linear Programing Kit (GLPK version 4.25). GLPK is open source software for solving large-scale linear programming (LP), mixed integer linear programming (MILP) and other related problems. Rglpk(R/GNU 線形計画キットインターフェース)パッケージ中のオブジェクト一覧

sublex パッケージ

subplex 最適化アルゴリズム

Rcplex パッケージ

DEA パッケージ 包絡分析

FEAR: Frontier Efficiency Analysis with R

limSolve: Solving Linear Inverse Models

2次計画法

QP。目的関数が2次で制約条件が1次の不等式で表現される数理計画問題。

パッケージ quadprog の関数 solve.QP() を利用します。

解法アルゴリズムには,Goldfarb-Idnani法が採用されているので狭義凸2次計画問題(いわゆる行列Qが正定値対称行列の場合)を解くために利用できます。

パッケージ kernlab の ipop 関数 2次計画法(Quadratic Programming) ソルバー

Rcplex パッケージ

LowRankQP: Low Rank Quadratic Programming

非線形計画法

BB: Solving and Optimizing Large-Scale Nonlinear Systems

目標計画法

goalprog パッケージ

Weighted and lexicographical goal programming and optimization.

線形および2次混合線形計画

Rcplex パッケージ

線形不等式制約条件付き最適化問題

制約条件が線形不等式の場合には、パッケージ base の関数 constrOptim() も利用することができます(線形不等式制約付きの最適化関数 constrOptim 参照)。

割り当て問題

lp.assign.R 関数(lpSolveパッケージ)

輸送問題

lp.transport.R 関数(lpSolveパッケージ)

立地配分

orloca: オペレーションリサーチの立地分析モデルを扱う

orloca(オペレーションリサーチの立地分析モデルを扱う)パッケージ中のオブジェクト一覧

滑らかな非線形関数の最適化

その他

CRAN TASK VIEWS

Optimization and Mathematical Programming


例題1(LP/IP/0-1IP)

線形計画問題

x1 + 9x2 + 3 x3

 上の式の最大化

x1 + 2 x2 + 3 x3  <= 9
3 x1 + 2 x2 + 2 x3 <= 15

lpSolve

f.obj <- c(1, 9, 3) 
f.con <- matrix (c(1, 2, 3, 3, 2, 2), nrow=2, byrow=TRUE)
f.dir <- c("<=", "<=")
f.rhs <- c(9, 15)

整数計画問題

x1 + 9 x2 + 3 x3

 上の式の最大化

x1 + 2 x2 + 3 x3  <= 9
3 x1 + 2 x2 + 2 x3 <= 15
lp ("max", f.obj, f.con, f.dir, f.rhs)
lp ("max", f.obj, f.con, f.dir, f.rhs)$solution

lpSolve

f.obj <- c(1, 9, 3) 
f.con <- matrix (c(1, 2, 3, 3, 2, 2), nrow=2, byrow=TRUE)
f.dir <- c("<=", "<=")
f.rhs <- c(9, 15)
lp ("max", f.obj, f.con, f.dir, f.rhs, int.vec=1:3)
lp ("max", f.obj, f.con, f.dir, f.rhs)$solution

0-1整数計画問題

lpSolve

例題2(QP)

Rで有効フロンティア

例題3(AP)

割り当て問題

例題4(TP)

輸送問題

lpSolve

 実行例(発送地が8, 目的地が5の場合)

>costs <- matrix (100000, 8, 5);#最大輸送費用 10,000
>costs[4,1] <- costs[-4,5] <- 0
>costs[1,2] <- costs[2,3] <- costs[3,4] <- 7; costs[1,3] <- costs[2,4] <- 7.7
>costs[5,1] <- costs[7,3] <- 8; costs[1,4] <- 8.4; costs[6,2] <- 9
>costs[8,4] <- 10; costs[4,2:4] <- c(.7, 1.4, 2.1)
>row.signs <- rep ("<", 8)
>row.rhs <- c(200, 300, 350, 200, 100, 50, 100, 150)
>col.signs <- rep (">", 5)
>col.rhs <- c(250, 100, 400, 500, 200)
>lp.transport (costs, row.signs, row.rhs, col.signs, col.rhs)
>lp.transport (costs, row.signs, row.rhs, col.signs, col.rhs)$solution
         [,1] [,2] [,3] [,4] [,5]
    [1,]    0  100    0  100    0
    [2,]    0    0  300    0    0
    [3,]    0    0    0  350    0
    [4,]  200    0    0    0    0
    [5,]   50    0    0    0   50
    [6,]    0    0    0    0   50
    [7,]    0    0  100    0    0
    [8,]    0    0    0   50  100

*1 lp 関数の引数 int.vec で設定

添付ファイル: fileflontier.jpeg 3309件 [詳細]

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2015-03-01 (日) 01:15:59