📂최적화이론

선형 계획 문제의 방정식 폼

정의 ¹

행렬 $A \in \mathbb{R}^{m \times n}$ 과 $\mathbf{b} \in \mathbb{R}^{m \times 1}$ 와 $\mathbf{c} \in \mathbb{R}^{n}$ 에 대해 다음과 같은 선형계획문제를 표준형^{standard form} 혹은 방정식 폼^{equational form}이라 한다. $$ \begin{matrix} \text{Maximize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} = \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{matrix} $$

---

• $\mathbf{c}^{T}$ 는 전치를 의미한다.
• 최적화는 최대화 혹은 최소화를 말한다.

설명

표준형으로의 변환

기본적으로는 어떤 선형계획문제라도 표준형으로 바꿀 수 있다. 가령 다음과 같은 최대화 문제가 주어져있다고 해보자.

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

변환의 기본적인 아이디어는 ‘부등식을 몰아주는 것’이다. 첫번째 제약 $$ 2 x_{1} - x_{2} \le 4 $$ 은 사실 어떤 $x_{3} \ge 0$ 에 대해 $$ 2 x_{1} - x_{2} + x_{3} = 4 $$ 와 같이 나타내도 전혀 문제 없다. $2 x_{1} - x_{2}$ 가 $4$ 보다 작은 양만큼을 $x_{3} > 0$ 가 보충해주는 역할을 하기 때문이다. 이렇게 등식을 느슨하게 만들어주는 역할을 하는 변수를 슬랙 변수^{slack variable}라 한다. 두번째 제약 $$ x_{1} + 3 x_{2} \ge 5 $$ 은 양변에 $-1$ 을 곱하고 첫번째 제약에서 그랬던 것처럼 새로운 슬랙 변수 $x_{4}$ 를 도입하면 $$ - x_{1} - 3 x_{2} + x_{4} = - 5 $$ 이다. 여기까지 보면 언뜻 $$ \begin{matrix} \text{Maximize} & 3 x_{1} - 2 x_{2} \\ \text{subject to} & 2 x_{1} - x_{2} + x_{3} = 4 \\ & - x_{1} - 3 x_{2} + x_{4} = - 5 \\ & x_{2}, x_{3}, x_{4} \ge 0 \end{matrix} $$ 은 방정식 꼴의 조건을 만족한 것처럼 보이지만, 아직 $x_{1} \ge 0$ 이라는 제약이 없기 때문에 이를 형식에 맞춰주어야한다. 주어진 문제에서 $x_{1}$ 는 실수 전체로 허용되어 있기 때문에 이를 두 양수의 차 $x_{1} = y_{1} - z_{1}$ 로 분해해주면 $x_{1}$ 은 식에서 사라지고, 다음과 같은 방정식 폼으로 나타낼 수 있다. $$ \begin{matrix} \text{Maximize} & 3 \left( y_{1} - z_{1} \right) - 2 x_{2} \\ \text{subject to} & 2 \left( y_{1} - z_{1} \right) - x_{2} + x_{3} = 4 \\ & - \left( y_{1} - z_{1} \right) - 3 x_{2} + x_{4} = - 5 \\ & y_{1}, z_{1}, x_{2}, x_{3}, x_{4} \ge 0 \end{matrix} $$

방정식 폼의 기하

방정식 $A \mathbf{x} = \mathbf{b}$ 은 일반적인 평면, 초평면^hyperplane을 이루고, $\mathbf{x} \ge \mathbf{0}$ 라는 조건에 따라 유클리드 공간에서 뿔 모양이 되도록 하는 부분만 취할 수 있게 된다. 슬랙 변수가 도입됨에 따라 차원 자체는 커지지만 최적화를 위해 탐색해야하는 공간 자체는 극도록 단순해진 것이다.

한편 이 해공간은 다름아닌 심플렉스고, 여기에서 심플렉스 메소드의 아이디어로 이어지게 된다.