📂最適化理論

MATLABで線形計画問題を解く方法

概要

Optimization Toolboxを使えばいいんだ¹。線形計画問題を行列形で表された$A, \mathbf{b}, \mathbf{c}$を入れて使う。

コード

$$\begin{matrix} \text{Maximize} & & x_{1} & + & x_{2} \\ \text{subject to} &-& x_{1} & + & x_{2} & \le & 1 \\ & & x_{1} & & & \le & 3 \\ & & & & x_{2} & \le & 2 \end{matrix}$$

簡単な例として、$x_{1} , x_{2} \ge 0$のような最大化問題を解いてみよう。生エビ寿司屋ではこの問題をシンプレックス・メソッドを使って手で解いて、その答え$\left( x_{1}^{\ast}, x_{2}^{\ast} \right) = (3,2)$を知っている。この線形計画問題は、

$$\begin{matrix} \text{Optimize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} \le \mathbf{b} \end{matrix}$$

このような形で、$\mathbf{c} = (1,1)$、$A = \begin{bmatrix} -1 & 1 \\ 1 & 0 \\ 1 & 0 \end{bmatrix}$、$\mathbf{b} = (1,3,2)$だから、次のように書き写して解くことができる。

>> A = [-1 1
    1 0
    0 1];

b = [1 3 2];
c = [-1 -1];

x = linprog(f,A,b,[],[], [0,0])

ここで、c = [-1,-1]をc = [1,1]ではなく使う理由は、linprog()の基本的な最適化方向が最小化のためだ。その方向だけを反転すれば最大化と同じで、結果は我々が既に知っていたように$\left( x_{1}, x_{2} \right) = \left( 3,2 \right) =$[3 2]だ。

최적해를 구했습니다.

x =

     3
     2

環境

• OS: Windows
• MATLAB: v9.9.0.1592791 (R2020b)
• Optimization Toolbox: v9.0 (R2020b)

参考にした方がいいもの

• Excelで線形計画問題を解く方法
• Juliaで線形計画問題を解く方法 JuMP.jl
• Pythonで線形計画問題を解く方法 scipy
• MATLABで線形計画問題を解く方法 Optimization Toolbox
• Rで線形計画問題を解く方法 lpSolve