Linear programming — 선형 계획법

선형 계획법은 수학적 계획법의 한 분야이자 널리 활용되는 운영 연구 방법으로, 선형 제약 조건 하에서 선형 함수의 극값(최댓값 또는 최솟값)을 구하는 문제의 이론과 풀이 방법을 다룬다.

선형 계획법(LP)은 경제학, 경영, 계획, 물류 및 기타 분야의 최적화 문제를 해결하기 위한 가장 강력하고 널리 사용되는 도구 중 하나이다.

주제 및 목적

선형 계획법의 기본 과제는 목표와 자원 사용에 대한 제약 조건 모두가 선형 관계로 표현될 수 있을 때, 특정 목표를 달성하기 위해 제한된 자원을 배분하는 최적의 방법을 찾는 것이다.

• 선형 계획법은 다음과 같은 실용적인 문제를 해결할 수 있다:
• 최적 생산 계획.
• 수송 흐름의 최적화 (수송 문제).
• 투자의 최적 배분.
• 재료의 최적 재단. 할당 문제.

LP 문제의 수학적 정식화

선형 계획법의 표준 문제는 다음과 같이 정식화된다:

선형 목적 함수를 최대화하거나 최소화하는 결정 변수의 값을 구해야 한다. 이때 결정 변수에는 선형 등식 및/또는 선형 부등식 체계로 이루어진 제약 조건이 부과된다. 일반적으로 결정 변수의 비음수 조건(값이 0 이상이어야 함)이 추가되며, 이는 종종 문제의 물리적 또는 경제적 의미에 의해 요구된다.

수학적으로 이는 선형 함수 및 선형 방정식/부등식 체계를 다루는 것을 의미한다.

LP의 기본 개념

• 결정 변수 (관리 변수): 문제를 푸는 과정에서 값을 결정해야 하는 양(예: 다양한 제품의 생산량, 다양한 목표에 배분되는 자원의 양).
• 목적 함수: 최대화 또는 최소화해야 하는 결정 변수의 선형 함수. 이는 문제의 목표를 수량적으로 표현한다(예: 총 이익, 총 비용).
• 제약 조건: 결정 변수가 만족해야 하는 선형 등식 및/또는 부등식 체계. 제약 조건은 자원 한계, 기술적 요구 사항, 계획 목표 및 기타 문제 조건을 반영한다.
• 허용 가능 해의 영역 (가능 영역): 문제의 모든 제약 조건을 만족하는 결정 변수 값의 집합 전체. 다차원 공간에서 기하학적으로 가능 영역은 볼록 다면체(폴리에드론)로 나타나며, 비유계이거나 공집합일 수도 있다.
• 허용 가능 해: 가능 영역에 속하는 임의의 변수 값의 집합.
• 최적 해: 목적 함수가 극값(최댓값 또는 최솟값)에 도달하는 허용 가능 해. 최적 해가 존재하면, 항상 가능 영역의 경계, 즉 볼록 다면체의 꼭짓점 중 적어도 하나에서 발견된다(LP의 기본 정리).

LP 문제의 풀이 방법

선형 계획법 문제를 푸는 주요 방법에는 여러 가지가 있다:

• 도해법: 결정 변수가 두 개인 문제에 적용된다. 평면에서 가능 영역과 목적 함수를 시각적으로 나타내고, 가능 영역의 꼭짓점 분석 또는 목적 함수의 등위선 이동을 통해 최적 해를 찾을 수 있다.
• 심플렉스법: George Dantzig이 개발한 범용 반복 알고리즘. 이 방법은 최적 해를 찾을 때까지 각 단계에서 목적 함수의 값을 개선하면서 가능 영역의 한 꼭짓점에서 인접한 꼭짓점으로 순차적으로 이동한다. LP 문제 풀이의 고전적이고 가장 잘 알려진 방법이다.
• 내부점 방법: 심플렉스법 이후에 등장한 대안적인 알고리즘 분류. 이 방법은 가능 영역의 경계가 아닌 내부를 통해 최적 해로 이동한다. 이 방법은 매우 대규모의 LP 문제를 해결하는 데 특히 효과적이다.

선형 계획법의 쌍대성

모든 선형 계획법 문제(원문제라고 함)에는 쌍대 문제라고 불리는 또 다른 LP 문제를 대응시킬 수 있다. 원문제와 쌍대 문제는 밀접하게 연관되어 있다:

한 문제의 해는 다른 문제의 해에 대한 정보를 제공한다. 두 문제의 최적 목적 함수 값은 (존재한다면) 일치한다. 쌍대 문제의 변수는 중요한 경제적 해석을 가지며, 자원의 잠재 가격(또는 쌍대 평가)에 해당하여, 해당 자원에 대한 제약 조건이 소폭 변화할 때 원문제의 최적 목적 함수 값이 얼마나 변하는지를 보여준다.

LP의 적용

선형 계획법은 다음 분야에서 광범위하게 활용된다:

• 경제 및 비즈니스 (생산 계획, 물류, 금융, 마케팅).
• 산업 (공정 최적화, 재고 관리, 재료 재단).
• 운송 (경로 및 일정 최적화). 농업 (경작 면적 최적화, 사료 배합).
• 에너지 (발전 설비 부하 최적화).

참고 문헌

• Dantzig, G. Линейное программирование, его применения и обобщения. — М.: Прогресс, 1966.
• Yudin, D. B., Goldstein, E. G. Линейное программирование (теория, методы и приложения). — М.: Наука, 1969.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

관련 항목

• 운영 연구
• 최적화
• 목적 함수
• 제약 조건
• 허용 가능 해의 영역
• 최적 해