放送大学

線形計画問題

問題解決の数理 第2章 線形計画問題

Webサイトでは、lpSolveパッケージが使われていますが、 ここでは、linprogパッケージを使います。

生産計画問題(p.25)式は、p.28

最大化

$$\begin{aligned} &z=x_1+2x_2 \end{aligned}$$

制約条件

$$\begin{aligned} &x_1+3x_2\leq24\\ &4x_1+4x_2\leq48\\ &2x_1+x_2\leq22\\ &x_1\geq0 ; x_2\geq0 \end{aligned}$$ 
1
2
3
4
5
6
7
8
9
library(linprog)
# 最大化(maximum=T)
cvec<-c(1,2)
# 制約条件
# 右辺
bvec<-c(24,48,22)
# 左辺
Amat<-rbind(c(1,3),c(4,4),c(2,1))
solveLP(cvec,bvec,Amat,maximum=T,const.dir=rep("<=",length(bvec)))

Results of Linear Programming / Linear Optimization

Objective function (Maximum): 18

Iterations in phase 1: 0
Iterations in phase 2: 2
Solution
opt
1 6
2 6

Basic Variables
opt
1 6
2 6
S 3 4

Constraints
actual dir bvec free dual dual.reg
1 24 <= 24 0 0.500 8
2 48 <= 48 0 0.125 16
3 18 <= 22 4 0.000 4

All Variables (including slack variables)
opt cvec min.c max.c marg marg.reg
1 6 1 0.666667 2.000 NA NA
2 6 2 1.000000 3.000 NA NA
S 1 0 0 -Inf 0.500 -0.500 8
S 2 0 0 -Inf 0.125 -0.125 16
S 3 4 0 -1.000000 0.200 0.000 NA

目的関数を変更（p.30上）

最大化

$$\begin{aligned} &z=3x_1+2x_2 \end{aligned}$$

制約条件

$$\begin{aligned} &x_1+3x_2\leq24\\ &4x_1+4x_2\leq48\\ &2x_1+x_2\leq22\\ &x_1\geq0 ; x_2\geq0 \end{aligned}$$ 
1
2
3
4
5
6
7
8
# 最大化
cvec<-c(3,2)
# 制約条件
# 右辺
bvec<-c(24,48,22)
# 左辺
Amat<-rbind(c(1,3),c(4,4),c(2,1))
solveLP(cvec,bvec,Amat,maximum=T,const.dir=rep("<=",length(bvec)))

Results of Linear Programming / Linear Optimization

Objective function (Maximum): 34

Iterations in phase 1: 0
Iterations in phase 2: 2
Solution
opt
1 10
2 2

Basic Variables
opt
1 10
2 2
S 1 8

Constraints
actual dir bvec free dual dual.reg
1 16 <= 24 8 0.00 8
2 48 <= 48 0 0.25 4
3 22 <= 22 0 1.00 4

All Variables (including slack variables)
opt cvec min.c max.c marg marg.reg
1 10 3 2.0 4.00 NA NA
2 2 2 1.5 3.00 NA NA
S 1 8 0 -0.5 0.20 0.00 NA
S 2 0 0 -Inf 0.25 -0.25 4
S 3 0 0 -Inf 1.00 -1.00 4

目的関数を変更（p.30下)

最大化

$$\begin{aligned} &z=2x_1+x_2 \end{aligned}$$

制約条件

$$\begin{aligned} &x_1+3x_2\leq24\\ &4x_1+4x_2\leq48\\ &2x_1+x_2\leq22\\ &x_1\geq0 ; x_2\geq0 \end{aligned}$$ 
1
2
3
4
5
6
7
8
# 最大化
cvec<-c(2,1)
# 制約条件
# 右辺
bvec<-c(24,48,22)
# 左辺
Amat<-rbind(c(1,3),c(4,4),c(2,1))
solveLP(cvec,bvec,Amat,maximum=T,const.dir=rep("<=",length(bvec)))

Results of Linear Programming / Linear Optimization

Objective function (Maximum): 22

Iterations in phase 1: 0
Iterations in phase 2: 1
Solution
opt
1 11
2 0

Basic Variables
opt
1 11
S 1 13
S 2 4

Constraints
actual dir bvec free dual dual.reg
1 11 <= 24 13 0 13
2 44 <= 48 4 0 4
3 22 <= 22 0 1 22

All Variables (including slack variables)
opt cvec min.c max.c marg marg.reg
1 11 2 0 Inf NA NA
2 0 1 -Inf 1.0 0 2
S 1 13 0 NA 2.0 0 NA
S 2 4 0 NA 0.5 0 NA
S 3 0 0 -Inf 1.0 -1 22

輸送問題(p.31) 式は、p.33

1
2
3
4
5
6
7
8
9
library(linprog)
# 最小化（maximum=F）
cvec<-c(10,6,16,8,8,10)
# 制約条件
# 右辺
bvec<-c(80,160,120,40,80)
# 左辺
Amat<-rbind(c(1,1,1,0,0,0),c(0,0,0,1,1,1),c(1,0,0,1,0,0),c(0,1,0,0,1,0),c(0,0,1,0,0,1))
solveLP(cvec,bvec,Amat,maximum=F,const.dir=rep(">=",length(bvec)))

Results of Linear Programming / Linear Optimization

Objective function (Minimum): 2080

Iterations in phase 1: 5
Iterations in phase 2: 3
Solution
opt
1 40
2 40
3 0
4 80
5 0
6 80

Basic Variables
opt
1 40
2 40
4 80
6 80
S 2 0

Constraints
actual dir bvec free dual dual.reg
1 80 >= 80 0 2 80
2 160 >= 160 0 0 NA
3 120 >= 120 0 8 Inf
4 40 >= 40 0 4 40
5 80 >= 80 0 10 Inf

All Variables (including slack variables)
opt cvec min.c max.c marg marg.reg
1 40 10 -12 14 NA NA
2 40 6 -10 10 NA NA
3 0 16 99 77 4 40
4 80 8 -12 10 NA NA
5 0 8 99 77 4 40
6 80 10 -20 14 NA NA
S 1 0 0 -2 Inf 2 80
S 2 0 0 -4 2 0 NA
S 3 0 0 -8 Inf 8 Inf
S 4 0 0 -4 Inf 4 40
S 5 0 0 -10 Inf 10 Inf

演習問題 2.1(p.37)

PCの回収量を　$x_1$
携帯電話の回収量を $x_2$ とする

最小　

$$\begin{aligned} &z=240x_1+800x_2\\ \end{aligned}$$
制約式
$$\begin{aligned}　 &x_1+5x_2\geq240\\ &x_1+2x_2\geq90\\ &3x_1+0x_2\geq60\\ &x_1\geq0 ; x_2\geq0 \end{aligned}$$ 
1
2
3
4
5
6
7
8
9
library(linprog)
# 最小化（maximum=F）
cvec<-c(240,800)
# 制約条件
# 右辺
bvec<-c(240,90,60)
# 左辺
Amat<-rbind(c(1,5),c(1,2),c(3,0))
solveLP(cvec,bvec,Amat,maximum=F,const.dir=rep(">=",length(bvec)))

Results of Linear Programming / Linear Optimization

Objective function (Minimum): 40000

Iterations in phase 1: 3
Iterations in phase 2: 0
Solution
opt
1 20
2 44

Basic Variables
opt
1 20
2 44
S 2 18

Constraints
actual dir bvec free dual dual.reg
1 240 >= 240 0 160.0000 Inf
2 108 >= 90 18 0.0000 18
3 60 >= 60 0 26.6667 660

All Variables (including slack variables)
opt cvec min.c max.c marg marg.reg
1 20 240 -320.0000 Inf NA NA
2 44 800 -1600.0000 1200 NA NA
S 1 0 0 -160.0000 Inf 160.0000 Inf
S 2 18 0 -133.3333 NA 0.0000 NA
S 3 0 0 -26.6667 Inf 26.6667 660

演習問題 2.2(p.37)

最小化

$$\begin{aligned} z=3x_{Aa}+7x_{Ab}+4x_{Ac}+5x_{Ba}+8x_{Bb}+7x_{Bc}+10x_{Ca}+6x_{Cb}+8x_{Cc} \end{aligned}$$

制約式

$$\begin{aligned} & x_{Aa}+x_{Ab}+x_{Ac}+0x_{Ba}+0x_{Bb}+0x_{Bc}+0x_{Ca}+0x_{Cb}+0x_{Cc} = 1\\ & 0x_{Aa}+0x_{Ab}+0x_{Ac}+1x_{Ba}+1x_{Bb}+1x_{Bc}+0x_{Ca}+0x_{Cb}+0x_{Cc} = 1\\ & 0x_{Aa}+0x_{Ab}+0x_{Ac}+0x_{Ba}+0x_{Bb}+0x_{Bc}+1x_{Ca}+1x_{Cb}+1x_{Cc} = 1\\ & x_{Aa}+0x_{Ab}+0x_{Ac}+x_{Ba}+0x_{Bb}+0x_{Bc}+1x_{Ca}+0x_{Cb}+0x_{Cc} = 1\\ & 0x_{Aa}+x_{Ab}+0x_{Ac}+0x_{Ba}+1x_{Bb}+0x_{Bc}+0x_{Ca}+1x_{Cb}+0x_{Cc} = 1\\ & 0x_{Aa}+0x_{Ab}+x_{Ac}+0x_{Ba}+0x_{Bb}+1x_{Bc}+0x_{Ca}+0x_{Cb}+1x_{Cc} = 1 \end{aligned}$$ 
1
2
3
4
5
6
7
8
9
library(linprog)
# 最小化（maximum=F）
cvec<-c(3,7,4,5,8,7,10,6,8)
# 制約条件
# 右辺
bvec<-c(1,1,1,1,1,1)
# 左辺
Amat<-rbind(c(1,1,1,0,0,0,0,0,0),c(0,0,0,1,1,1,0,0,0),c(0,0,0,0,0,0,1,1,1),c(1,0,0,1,0,0,1,0,0),c(0,1,0,0,1,0,0,1,0),c(0,0,1,0,0,1,0,0,1))
solveLP(cvec,bvec,Amat,maximum=F,const.dir=rep(">=",length(bvec)))

Results of Linear Programming / Linear Optimization

Objective function (Minimum): 15

Iterations in phase 1: 6
Iterations in phase 2: 3
Solution
opt（作家と担当者の組み合わせ）
1 0 Aa
2 0 Ab
3 1 Ac
4 1 Ba
5 0 Bb
6 0 Bc
7 0 Ca
8 1 Cb
9 0 Cc

Basic Variables
opt
3 1
4 1
6 0
8 1
9 0
S 1 0

Constraints
actual dir bvec free dual dual.reg
1 1 >= 1 0 0 NA
2 1 >= 1 0 3 1
3 1 >= 1 0 4 1
4 1 >= 1 0 2 Inf
5 1 >= 1 0 2 Inf
6 1 >= 1 0 4 Inf

All Variables (including slack variables)
opt cvec min.c max.c marg marg.reg
1 0 3 99 77 1 1
2 0 7 99 77 5 1
3 1 4 -6 5 NA NA
4 1 5 -7 6 NA NA
5 0 8 99 77 3 1
6 0 7 -8 9 NA NA
7 0 10 99 77 4 1
8 1 6 -8 9 NA NA
9 0 8 -11 10 NA NA
S 1 0 0 -2 3 0 NA
S 2 0 0 -3 Inf 3 1
S 3 0 0 -4 Inf 4 1
S 4 0 0 -2 Inf 2 Inf
S 5 0 0 -2 Inf 2 Inf
S 6 0 0 -4 Inf 4 Inf