선형 계획법

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

수학에서, 선형 계획법(線型計劃法, 영어: linear programming 리니어 프로그래밍[*])은 최적화 문제의 일종으로 주어진 선형 조건들을 만족시키면서 선형인 목적 함수를 최적화하는 문제이다. 선형 계획법은 운용 과학, 미시 경제학, 네트워크 경로 최적화 등 많은 분야에서 사용되고 있으며, 선형 계획법의 특수한 경우인 네트워크 흐름과 같은 문제들에 대해서는 여러 특화된 알고리즘들이 연구되어 왔다.

선형 계획법은 운용 과학 중에서 가장 일반적인 기법이다. 선형 계획법은 가변 요소 사이에 일차 방정식이 성립할 경우, 즉 선형(線型)의 관계가 있을 때, 변화의 한계를 정할 때에 사용하는 생산계획·수송계획 등 문제에 선형 계획법이 이용되고 있다. 할당 문제도 이 수법으로 풀어진다. 가령 판매 과장이 세일즈맨을 각 지역으로 할당하는 문제에 직면하고 있다고 하자. 세일즈맨에게는 제각기의 특성이 있어서, 어느 세일즈맨에게는 어느 지역이 적절하지만 그러나 세일즈맨의 몇몇은 매우 우수하여 어느 지역이라도 담당할 수 있으며 더욱이 다른 세일즈맨보다 더 좋은 업적을 올릴 수가 있다. 판매과장의 문제는 세일즈맨의 지역할당을 통하여 전체의 판매량을 최대로 함에 있을 것이다. 이 경우 만약 세일즈맨이 각각의 지역에 있어서 상대적 효율을 수량화 할 수 있다고 하면 간단한 선형 계획법의 수법을 써서 최적의 할당을 정할 수가 있다.

[편집]

예를 들어 홍길동씨가 빵 가게를 운영한다고 하자. 두 가지 종류의 빵을 판매하는데, 초코빵은 고급 빵으로 밀가루 100g과 초콜릿 10g이 필요하고 밀빵은 보통 빵으로 밀가루 50g만이 필요하다. 재료비를 제하고 초코빵을 팔면 100원이 남고 밀빵를 팔면 40원이 남는다고 하자. 오늘 홍길동 씨는 밀가루 3000g과 초콜릿 100g을 재료로 갖고 있다. 만든 빵을 다 팔 수 있고 더 이상 재료 공급을 받지 않는다고 가정한다면, 홍길동씨는 이익을 극대화 하기 위해서 어떤 빵을 얼마나 만들어야 할까? 이 문제를 풀기 위해 다음과 같은 선형 계획 문제를 만들 수 있다.

목적: \max_{\mathbf{x}} 100 x_1 + 40 x_2
조건: 100 x_1 + 50 x_2 \le 3000,
10 x_1 \le 100,
x_1,\,x_2 \ge 0.

여기서 x_1은 초코빵을 x_2는 밀빵의 개수를 의미하는 변수이다. 오늘 홍길동씨가 가장 많은 이익을 남기는 방법은 가능한 한 많은 초코빵을 만들고 남는 밀로 밀빵을 만드는 것이다. 따라서 초코빵 10개와 밀빵 40개를 만들면 되겠다.

표준형[편집]

선형 계획 문제는 수식으로 어떻게 표현하느냐에 따라 다른 형태를 가질 수 있다. 하지만 선형 계획 문제의 최적해를 찾는 알고리즘을 개발하기 위해 일괄된 형태의 문제가 필요하다. 다행히도 부등식은 등식으로 등식은 부등식으로 변환하는 간단한 방법이 있다. 예를 들어 x_1 + x_2 \le b_1과 같은 부등식은 x_1 + x_2 + s_1 = b_1,\,s_1 \ge 0와 같은 등식과 간단한 조건으로 이루어진 형태로 바꿀 수 있고, 2x_1 + 3x_2 = b_1과 같은 등식은 2x_1 + 3x_2 \ge b_12x_1 + 3x_2 \le b_1의 두 부등식으로 변환할 수 있다. 따라서 특정한 형태의 표준형을 정하고 표준 문제의 최적해를 구하는 알고리즘을 구하면 어떠한 문제에도 적용할 수 있을 것이다. 선형 계획 문제의 표준형은 저자마다 다르지만 보통 다음과 같다.

목적:  \max_{\mathbf{x}} \mathbf{c}^T \mathbf{x}
조건:  \mathbf{Ax} \le \mathbf{b},
 \mathbf{x} \ge 0.

여기서 \mathbf{A}m \times n 행렬이고 \mathbf{c}\mathbf{x}n차원 벡터이며 \mathbf{b}m차원 벡터이다.

쌍대성[편집]

모든 선형 계획 문제에는 그에 대응하는 쌍대 문제가 있다. 쌍대 문제의 해는 원 문제의 해에 대한 정보를 담고 있기 때문에 매우 중요하고 유용하다.

원 문제가 최소화 문제라면 쌍대 문제는 최대화 문제가 되는데, 쌍대 문제의 최적값이 원 문제의 최적값보다 크지 않다는 것이 약한 쌍대성 정리, 사실 이 두 최적값이 같다는 것이 강한 쌍대성 정리이다.

목적:  \max_{\mathbf{x}} \mathbf{c}^T \mathbf{x}
조건:  \mathbf{Ax} \le \mathbf{b},
 \mathbf{x} \ge 0.

위와 같이 표준형으로 나타낸 선형 계획 문제가 있을 때, 그 쌍대 문제는 아래와 같이 나타낼 수 있다.

목적:  \min_{\mathbf{y}} \mathbf{b}^T \mathbf{y}
조건:  \mathbf{A^T y} \ge \mathbf{c},
 \mathbf{y} \ge 0.

알고리즘[편집]

단체법[편집]

단체법제2차 세계 대전 당시 조지 댄치그가 군수 물자 보급의 최적화를 위하여 선형 계획법 문제를 해결하기 위하여 개발하였다.

내부점법[편집]

내부점법(Interior point method)은 나렌드라 카르마르카르(마라티어: नरेंद्र करमरकर, 영어: Narendra Karmarkar)가 1984년에 개발했다. 단체법과는 다르게, 최적해를 실현내부구역(영어: feasible region)의 내부에서 찾아간다.

바깥 고리[편집]

Heckert GNU white.svgCc.logo.circle.svg 이 문서에는 다음커뮤니케이션에서 GFDL 또는 CC-SA 라이선스로 배포한 글로벌 세계대백과사전의 내용을 기초로 작성된 글이 포함되어 있습니다.