最小費用流問題

問題解決の数理 第4章 ネットワーク計画法3

最小化

$$\begin{aligned} &z=3*x_{12}+5*x_{13}+2*x_{24}+2*x_{25}+3*x_{34}+3*x_{36}+3*x_{47}+2*x_{57}+4*x_{68} \end{aligned}$$

制約条件

$$\begin{aligned} &x_{12}\leq20\\ &x_{13}\leq25\\ &x_{24}\leq15\\ &x_{25}\leq20\\ &x_{34}\leq20\\ &x_{36}\leq15\\ &x_{47}\leq30\\ &x_{57}\leq20\\ &x_{68}\leq15\\ &x_{12}+x_{13}=40\\ &x_{47}+x_{57}=30\\ &x_{68}=10\\ &x_{12}-x_{24}-x_{25}=0\\ &x_{13}-x_{34}-x_{36}=0\\ &x_{24}+x_{34}-x_{47}=0\\ &x_{25}-x_{57}=0\\ &x_{36}-x_{68}=0 \end{aligned}$$

library("Rglpk")
obj <- c(3,5,2,2,3,3,3,2,4)
mat <- rbind(c(1, 0,0,0,0,0,0,0,0),c(0,1,0,0,0,0,0,0,0),c(0,0,1,0,0,0,0,0,0),c(0,0,0,1,0,0,0,0,0),c(0,0,0,0,1,0,0,0,0),c(0,0,0,0,0,1,0,0,0),
c(0,0,0,0,0,0,1,0,0),c(0,0,0,0,0,0,0,1,0),c(0,0,0,0,0,0,0,0,1),c(1,1,0,0,0,0,0,0,0),c(0,0,0,0,0,0,1,1,0),c(0,0,0,0,0,0,0,0,1),
c(1,0,-1,-1,0,0,0,0,0),c(0,1,0,0,-1,-1,0,0,0),c(0,0,1,0,1,0,-1,0,0),c(0,0,0,1,0,0,0,-1,0),c(0,0,0,0,0,1,0,0,-1))
dir <- c("<=", "<=", "<=", "<=", "<=", "<=", "<=", "<=", "<=", "==", "==","==", "==", "==","==", "==", "==")
rhs <- c(20,25,15,20,20,15,30,20,15,40,30,10,0,0,0,0,0)
max <- F
Rglpk_solve_LP(obj, mat, dir, rhs, max = max)

$optimum
[1] 370

$solution
[1] 20 20 0 20 10 10 10 20 10

$status
[1] 0