선형 계획법이란?

선형 최적화로도 알려진 선형 계획법은 범위, 선형 등식 및 선형 부등식 제약 조건이 적용되는 선형 목적 함수를 최소화하거나 극대화합니다. 예제 문제에는 공정 산업에서의 혼합, 제조업에서의 생산 계획, 금융에서의 현금 흐름 일치, 에너지 및 수송에서의 계획 등이 포함됩니다.

선형 계획법은 다음 함수를 최소화하는 벡터 \(x\)를 구하는 수학적 문제입니다.

\[\min_{x} \left\{f^{\mathsf{T}}x\right\}\]

적용되는 제약 조건은 다음과 같습니다.

\[\begin{eqnarray}Ax \leq b & \quad & \text{(inequality constraint)} \\A_{eq}x = b_{eq} & \quad & \text{(equality constraint)} \\lb \leq x \leq ub & \quad & \text{(bound constraint)}\end{eqnarray}\]

MATLAB을 사용한 선형 계획법

MATLAB^®을 사용하여 선형 계획법 문제 풀이에 널리 사용되는 다음과 같은 알고리즘을 구현할 수 있습니다.

• 내점: primal-dual predictor-corrector 알고리즘을 사용하며, 구조가 있거나 희소 행렬로 정의할 수 있는 대규모 선형 계획법에 특히 유용합니다.
• 단체: 체계적 절차를 사용하여 선형 계획법에 대한 후보 꼭짓점 해를 생성하고 테스트합니다. 단체 알고리즘 및 관련 쌍대-단체 알고리즘은 선형 최적화에 가장 널리 사용되는 알고리즘입니다.

Optimization Toolbox™의 linprog 솔버는 이러한 선형 최적화 기법을 구현합니다.

선형 계획법의 특수 사례

제약 조건이 네트워크 구조를 띠는 선형 최적화 문제의 몇몇 특수 사례에 대한 알고리즘은 일반적으로 범용 내점 및 단체 알고리즘보다 빠릅니다. 다음과 같은 특수 사례가 있습니다.

• 최대 네트워크 흐름: augmenting-path 및 push-relabel 알고리즘을 사용합니다.
• 최단 경로: Dijkstra, Bellman-Ford 및 탐색 알고리즘을 사용합니다.
• 선형 할당: 이분 매칭 알고리즘을 사용합니다.

알고리즘 및 선형 최적화에 대한 자세한 내용은 Optimization Toolbox를 참조하십시오.