선형 계획법: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
편집 요약 없음 |
편집 요약 없음 |
||
1번째 줄:
[[수학]]에서, '''선형 계획법'''(線型計劃法, {{llang|en|linear programming|리니어 프로그래밍}})은 [[최적화 (수학)|최적화]] 문제의 일종으로 주어진 [[선형성|선형]] 조건들을 만족시키면서 선형인 목적 함수를 최적화하는 문제이다. 선형 계획법은 [[운용 과학]], [[미시 경제학]], 네트워크 경로 최적화 등 많은 분야에서 사용되고 있으며, 선형 계획법의 특수한 경우인 [[네트워크 흐름]]과 같은 문제들에 대해서는 여러 특화된 [[알고리즘]]들이 연구되어 왔다.
선형 계획법은 [[운용 과학]] 중에서 가장 일반적인 기법이다. 선형 계획법은 가변 요소 사이에 [[일차 방정식]]이 성립할 경우, 즉 선형(線型)의 관계가 있을 때, 변화의 한계를 정할 때에 사용하는 방법으로, 생산계획·수송계획 등 문제에 선형 계획법이 이용되고 있다. [[할당]] 문제도 이 수법으로 풀어진다. 가령 판매 과장이 세일즈맨을 각 지역으로 할당하는 문제에 직면하고 있다고 하자. 세일즈맨에게는 제각기의 특성이 있어서
== 예 ==
[[파일:선형 계획법.png|400픽셀|섬네일|오른쪽|이익이 최대가 될 때는 이익을 나타내는 직선이 해가 존재할 수 있는 영역 중 원점에서 가장 떨어진 점 (10, 40)에 접할 때이다. <math>100 x_1 + 40 x_2=2600</math>]]
선형 계획법의 간단한 예시는 다음과 같다. 홍길동 씨가 두 가지 종류의 빵을 판매하는데, 초코빵을 만들기 위해서는 밀가루 100g과 초콜릿 10g이 필요하고 밀빵을 만들기 위해서는 밀가루 50g이 필요하다. 재료비를 제하고 초코빵을 팔면 100원이 남고 밀빵를 팔면 40원이 남는다. 오늘 홍길동 씨는 밀가루 3000g과 초콜릿 100g을 재료로 갖고 있다. 만든 빵을 전부 팔 수 있고 더 이상 재료 공급을 받지 않는다고 가정한다면, 홍길동 씨는 이익을 극대화 하기 위해서 어떤 종류의 빵을 얼마나 만들어야 하는지 다음과 같이 선형 계획법을 이용하여 계산할 수 있다.
:{|
줄 14 ⟶ 15:
| <math>x_1,\,x_2 \ge 0.</math>
|}
여기서 <math>x_1</math>은 초코빵을 <math>x_2</math>는 밀빵의 개수를 의미하는 변수이다. 그림을 참고하면 오늘 홍길동 씨가 가장 많은 이익을 남기는 방법은
== 표준형 ==
| |||