📂최적화이론

선형계획법에서 목적 함수의 무한성

설명

$$ \begin{matrix} \text{Maximize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} = \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{matrix} $$

행렬 $A \in \mathbb{R}^{m \times n}$ 과 $\mathbf{b} \in \mathbb{R}^{m \times 1}$ 와 $\mathbf{c} \in \mathbb{R}^{n}$ 에 대해 선형계획문제가 위와 같이 방정식 폼으로 나타난다고 하자. 제약조건에 따름에도 불구하고 목적 함수^{objective function}가 언바운드^unbounded될 수 있다.

백마디 말보다 그림 한 번 보는 게 낫다¹. 기하적으로 심플렉스 메소드를 생각했을 때 목적 함수가 언바운드라는 것은 애초에 심플렉스 자체를 구성할 수 없다는 의미가 된다. 이처럼 목적 함수가 바운드 되어 있지 않은 경우 최대화 문제임에도 대상값^{objective value}이 계속해서 커지는 일을 겪을 수도 있다.

판별법

$$ \begin{align*} \zeta &=& \bar{\zeta} &+& \sum_{j \in \mathcal{N}} \bar{c}_{j} x_{j} \\ x_{n+i} &=& \bar{b}_{i} &-& \sum_{j \in \mathcal{N}} \bar{a}_{ij} x_{j} \end{align*} $$

주어진 문제에서 풀이가 진행됨에 따라 변하는 계수 위에 바^bar를 둔 딕셔너리 혹은 태블로를 위와 같이 나타냈을 때, 이탈 변수^{leaving variable}가 $x_{i}$ 라고 하면 모든 $$ \bar{a}_{i1} \bar{b}_{i}, \cdots , \bar{a}_{in} \bar{b}_{i} $$ 가 양수가 아니면 목적 함수가 언바운드임을 알 수 있다.²