목적 함수와 제약 조건

목적 함수

선형계획법에서의 목적 함수는 특정 목표를 달성하기 위해 최적화하려는 대상을 수학적으로 표현한 것이다. 이 목표는 보통 비용 최소화 또는 이익 최대화와 같은 형태로 나타난다. 일반적으로 선형계획법에서 다루는 목적 함수는 선형 함수로 정의된다.

목적 함수는 다음과 같은 형태로 나타낼 수 있다:

$z = \mathbf{c}^\top \mathbf{x}$

여기서: - $z$ 는 목적 함수 값이다. - $\mathbf{c}$ 는 계수 벡터로, 각 변수에 대한 가중치를 나타낸다. - $\mathbf{x}$ 는 결정 변수 벡터로, 최적화를 위해 조정되는 값들이다. - $\mathbf{c}^\top$ 는 벡터 $\mathbf{c}$ 의 전치 행렬로, $\mathbf{x}$ 와 내적을 구하기 위해 전치된 형태이다.

제약 조건

제약 조건은 결정 변수들이 만족해야 하는 제한 사항들을 나타낸다. 제약 조건도 선형 함수로 표현되며, 이는 다음과 같은 형태로 나타난다:

$\mathbf{A} \mathbf{x} \leq \mathbf{b}$

여기서: - $\mathbf{A}$ 는 계수 행렬로, 각 제약 조건의 계수를 나타낸다. - $\mathbf{x}$ 는 결정 변수 벡터이다. - $\mathbf{b}$ 는 상수 벡터로, 제약 조건의 우변을 나타낸다.

이 경우, $\leq$ 부등호는 이하 제약 조건을 의미하며, 특정 상황에서는 등호 또는 이상 부등호가 사용될 수 있다. 예를 들어, 등호 제약 조건은 다음과 같이 나타난다:

$\mathbf{A} \mathbf{x} = \mathbf{b}$

또는 이상 제약 조건은 다음과 같다:

$\mathbf{A} \mathbf{x} \geq \mathbf{b}$

결정 변수의 비음성 제약

선형계획법에서는 일반적으로 비음성 제약을 추가하여, 결정 변수들이 음수가 되지 않도록 한다. 이는 다음과 같은 형태로 표현된다:

$\mathbf{x} \geq 0$

여기서, $\mathbf{x} \geq 0$ 은 모든 결정 변수 $x_i$ 가 0보다 크거나 같아야 함을 의미한다.

제약 조건의 형태

제약 조건은 다양한 형태로 나타날 수 있으며, 문제의 성격에 따라 그 구체적인 표현이 달라진다. 아래는 자주 사용되는 제약 조건의 형태들이다.

부등식 제약 조건

부등식 제약 조건은 일반적으로 자원이나 비용과 같은 제한을 나타내는 데 사용된다. 부등식 제약 조건은 다음과 같은 형식으로 표현된다:

$\mathbf{A} \mathbf{x} \leq \mathbf{b}$

이는 각 자원 $i$ 에 대해 사용량이 자원 한계 $b_i$ 를 초과하지 않도록 보장한다. 즉, 각 행렬 $A_{ij}$ 는 변수 $x_j$ 가 자원 $i$ 에 얼마나 기여하는지를 나타내며, $b_i$ 는 해당 자원의 최대 한도이다.

등식 제약 조건

등식 제약 조건은 보통 균형을 맞추거나 동등한 자원 할당을 요구할 때 사용된다. 예를 들어, 특정 생산 라인에서의 투입과 산출이 같아야 하는 경우 등식 제약 조건이 필요하다. 이는 다음과 같은 형식으로 표현된다:

$\mathbf{A} \mathbf{x} = \mathbf{b}$

이 경우 각 자원 $i$ 는 사용량이 정확히 $b_i$ 와 같아야 한다.

이상 제약 조건

이상 제약 조건은 특정 자원이 최소한 얼마만큼 이상 사용되어야 한다는 제한을 나타낸다. 이는 다음과 같은 형식으로 나타난다:

$\mathbf{A} \mathbf{x} \geq \mathbf{b}$

이 조건은 자원 $i$ 의 사용량이 최소 $b_i$ 이상이어야 한다는 것을 의미한다. 예를 들어, 최소 생산 요구량이 있는 경우 이러한 제약 조건을 사용할 수 있다.

제약 조건의 해석

제약 조건의 형태에 따라, 선형계획 문제에서 가능한 해의 공간이 달라진다. 예를 들어, 부등식 제약 조건만 존재하는 문제는 많은 해를 가질 수 있지만, 등식 제약 조건을 추가하면 해의 공간이 축소된다. 이러한 제약 조건은 문제의 가능한 영역(feasible region)을 정의하며, 이 영역 내에서 최적의 해를 찾는 것이 목적이다.

이때 가능한 해 영역은 결정 변수들에 의해 정의된 다면체(polytop) 형태를 가지며, 이 다면체의 경계에서 최적해가 위치하는 경우가 많다. 특히, 단체법(Simplex Method)은 이러한 경계를 탐색하는 알고리즘 중 하나이다.

제약 조건을 행렬로 표현하기

선형계획 문제의 제약 조건은 다수의 부등식과 등식으로 구성될 수 있으며, 이를 행렬 형태로 통합하여 표현할 수 있다. 일반적인 형태는 다음과 같다:

$\mathbf{A}_1 \mathbf{x} \leq \mathbf{b}_1 \quad , \quad \mathbf{A}_2 \mathbf{x} = \mathbf{b}_2$

여기서: - $\mathbf{A}_1$ , $\mathbf{b}_1$ 는 부등식 제약 조건에 대한 계수 행렬과 상수 벡터이다. - $\mathbf{A}_2$ , $\mathbf{b}_2$ 는 등식 제약 조건에 대한 계수 행렬과 상수 벡터이다.

이러한 형태의 제약 조건은 표준형 선형계획 문제로 전환되며, 이후 단체법을 통해 해를 구할 수 있다.

물리적 의미

제약 조건은 단순한 수학적 표현을 넘어서서, 실제 문제에서 의미 있는 방식으로 해석된다. 예를 들어: - $x_1$ 과 $x_2$ 는 제품의 생산량을 나타내며, 이를 최적화하는 문제에서는 자원 사용 제약이 부여된다. - $b_1$ , $b_2$ 는 사용 가능한 자원의 양을 의미하며, 각 자원의 한도를 초과하지 않도록 설정된다.

제약 조건의 형태와 목적 함수는 문제의 실제 성격을 반영하며, 이를 통해 다양한 실제 문제를 수학적으로 모델링할 수 있다.