선형 계획 문제의 정의
정의 1
목적 함수objective function와 제약constraint들이 리니어한 최적화 문제를 선형 계획 문제linear Programming Problem, 짧게는 선형 문제lP라 한다. 쉽게 말해, 선형 문제란 선형성을 가지는 목적 함수 $f: \mathbb{R}^{n} \to \mathbb{R}$ 가 주어진 벡터 $\mathbf{c} \in \mathbb{R}^{n}$ 에 대해 $$ f \left( \mathbf{x} \right) := \mathbf{c}^{T} \mathbf{x} $$ 이고 주어진 행렬 $A \in \mathbb{R}^{m \times n}$ 과 $\mathbf{b} \in \mathbb{R}^{m \times 1}$ 에 대해 $$ A \mathbf{x} \le \mathbf{b} $$ 을 만족시키면서 $f$ 의 함수값이 최적화되는 $\mathbf{x} \in \mathbb{R}^{n}$ 를 구하는 문제다. 주로 다음과 같이 나타낸다. $$ \begin{matrix} \text{Optimize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} \le \mathbf{b} \end{matrix} $$ 이러한 문제에서 최적화를 떠나 일단 제약 조건은 만족시키는 해를 가용해feasible solution라 하고, 그들 중에서 목적 함수를 최대화하거나 최소화하는 해를 최적해optimal solution라 한다.
설명
말풀이
선형은 말 그대로 주어진 목적 함수와 제약 조건이 선형이기 때문에 붙은 말이다. 수식에 $\mathbf{x} = \left( x_{1} , \cdots , x_{n} \right)$ 들의 제곱항이나 로그 같은 비선형 함수꼴이 들어가지 않으며 제약 역시 행렬(부등)식의 꼴로 나타나야 한다는 점에서 알맞은 표현이다. 주로 행렬대수, 선형대수에서 다음과 같이 등식으로 나타난 문제를 푸는 것과 대비된다. $$ A \mathbf{x} = \mathbf{b} $$
계획program은 흔히 우리가 아는 컴퓨터의 응용 프로그램이 아니라 스케쥴schedule이나 태스크task를 의미한다. 실제 선형 계획법의 응용에서 각각의 변수 $x_{1} , \cdots , x_{n}$ 들은 시간, 에너지, 자원 등의 여러가지 요소를 나타낼 수 있다.
가령 경제나 경영학에서 이것들을 가지고 무언가를 최대화한다면 그것은 아마 효용utility, 최소화한다면 비용cost이 될 것이다. 출퇴근시간과 효율이 다른 직원들을 어떤 작업에 배치하는가에 따른 최적의 근무표를 만들어야한다면 선형 계획법이 가장 우선적으로 고려되는 방법일 수 있다.
예시 2
$$ \begin{matrix} \text{Optimize} & x_{1} + x_{2} \\ \text{subject to} & x_{1} \ge 0 \\ & x_{2} \ge 0 \\ & x_{2} - x_{1} \le 1 \\ & x_{1} + 6 x_{2} \le 15 \\ & 4 x_{1} - x_{2} \le 10 \end{matrix} $$
위와 같은 선형 문제를 생각해보자. 무려 조건이 다섯개나 되기 때문에 언뜻 복잡해보이지만, 막상 다루는 변수는 $x_{1}$ 와 $x_{2}$ 둘 뿐이니 이를 $2$차원에 평면에 나타내보면 다음의 그림과 같이 조건을 만족하는 영역을 확인할 수 있다.
이러한 영역에 속하는 모든 점들은 일단 제약 조건을 만족하긴하는 가용해feasible solution다. 이제 이들 중 목적 함수 $\Lambda \left( x_{1} , x_{2} \right) = x_{1} + x_{2}$ 가 최대가 되게 하는 점을 찾으면 된다. 기하적으로 말하자면 직선 가용해의 영역과 $x_{1} + x_{2} = \lambda$ 가 겹치는intersect 부분 중 $\lambda$ 가 제일 커지는 곳, 그러니까 직선의 $y$-절편이 가장 커지는 점을 찾으면 되는 것이다.
실제 예제의 해답은 $\lambda = 5$ 가 되도록 하는 $\left( x_{1} , x_{2} \right) = (3,2)$ 다. 그런데 이러한 풀이는 어딘가 낯이 익다. 일반적인 교과과정을 거쳤다면 아마 고등학교 1학년 쯤 교과서에서 이와 비슷한 문제들을 보았을 것이다. 이처럼 기본적인 아이디어는 중학교를 갓 졸업한 어린이 친구들도 이해할 수 있을 정도로 간단하다. 애초에 ‘선형’이 붙었다는 것은 실제 풀이가 어떻든 개념 자체는 쉽다는 것이다.