logo

매트랩으로 선형계획문제 푸는 법 📂최적화이론

매트랩으로 선형계획문제 푸는 법

개요

Optimization Toolbox를 사용하면 된다1. 행렬 꼴로 나타난 선형계획문제의 A,b,cA, \mathbf{b}, \mathbf{c} 를 넣어서 쓴다.

코드

Maximizex1+x2subject to−x1+x2≤1x1≤3x2≤2 \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}

간단한 예제로써 x1,x2≥0x_{1} , x_{2} \ge 0 에서 위와 같은 최대화 문제를 풀어보자. 생새우초밥집에서는 이 문제를 심플렉스 메소드를 써서 손으로 풀어보았고 그 답 (x1∗,x2∗)=(3,2)\left( x_{1}^{\ast}, x_{2}^{\ast} \right) = (3,2) 를 알고 있다. 이 선형계획문제는

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

위와 같은 꼴에서 c=(1,1)\mathbf{c} = (1,1), A=[−111010]A = \begin{bmatrix} -1 & 1 \\ 1 & 0 \\ 1 & 0 \end{bmatrix}, b=(1,3,2)\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()의 기본적인 최적화 방향이 최소화기 때문이다. 그 방향만 반전해주면 최대화와 마찬가지고, 그 결과는 우리가 이미 알고 있던 것처럼 (x1,x2)=(3,2)=\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)

같이보기

  1. https://kr.mathworks.com/help/optim/ug/linprog.html ↩︎