선형 계획법

선형 계획법은 선형 등식 및 부등식 제약 조건에 따라 선형 목적 함수를 최적화하는 것으로, 최적화 문제 중 가장 널리 적용되는 유형입니다.

Definition

선형 계획법은 의사결정 변수의 선형 함수를 선형 제약 조건 하에서 최소화하거나 최대화하는 것입니다. 그 실행 가능 영역은 볼록 다면체이며, 최적해가 존재한다면 꼭짓점에서 달성됩니다.

Scope

이 주제는 선형 계획법의 표준 형식, 실행 가능 다면체 및 그 꼭짓점의 기하학적 특성, 심플렉스 방법, 선형 계획법의 쌍대성 및 상보적 여유 조건, 민감도 분석, 그리고 대규모 문제 해결을 위한 내부점 방법을 다룹니다.

Core questions

• 실제 자원 문제는 어떻게 선형 계획법으로 공식화됩니까?
• 최적해가 실행 가능 다면체의 꼭짓점에서 발생하는 이유는 무엇입니까?
• 쌍대 선형 계획법은 원시 문제에 대해 무엇을 알려줍니까?
• 어떤 알고리즘이 대규모 선형 계획법을 효율적으로 해결합니까?

Key theories

선형 계획법의 기본 정리

선형 계획법에 최적해가 존재한다면, 최적해는 실행 가능 다면체의 꼭짓점에서 달성되며, 이는 탐색을 유한한 수의 후보점으로 줄입니다.

쌍대성 및 상보적 여유 조건

모든 선형 계획법은 원시 문제와 동일한 최적값을 갖는 쌍대 문제를 가지며, 상보적 여유 조건은 활성 제약 조건과 0이 아닌 쌍대 변수를 연결하여 최적성 증명과 경제적 해석을 제공합니다.

심플렉스 및 내부점 방법

심플렉스 방법은 목적 함수를 개선하기 위해 꼭짓점 사이를 이동하는 반면, 내부점 방법은 내부를 통과하며 선형 계획법을 증명 가능한 다항 시간 내에 해결합니다.

Clinical relevance

선형 계획법은 운영 연구의 초석으로, 생산 계획, 운송 및 물류, 스케줄링, 식단 및 혼합 문제, 네트워크 흐름 등에 사용되며, 정수 및 비선형 최적화 내의 서브루틴으로도 활용됩니다.

History

칸토로비치(Kantorovich)는 1939년에 생산 계획을 위한 선형 최적화를 도입했으며, 단치히(Dantzig)는 1947년에 일반적인 문제와 심플렉스 방법을 정립했습니다. 폰 노이만(Von Neumann)은 게임 이론과의 쌍대성을 인식했고, 이후 카치얀(Khachiyan)의 타원체 방법과 카르마르카(Karmarkar)의 내부점 방법이 다항 시간 해결 가능성을 확립했습니다.

Key figures

• George Dantzig
• Leonid Kantorovich
• John von Neumann
• Narendra Karmarkar

Seminal works

• dantzig1963
• luenberger2008

Frequently asked questions

최적해가 왜 꼭짓점에 위치합니까?

선형 목적 함수는 고정된 방향으로 가장 빠르게 증가하므로, 볼록 다면체 위에서 그 최적값은 경계로, 궁극적으로는 모서리로 밀려납니다. 목적 함수가 모서리나 면을 따라 일정하지 않는 한, 최적해는 꼭짓점에서 달성됩니다.

심플렉스 방법은 항상 빠릅니까?

실제로 심플렉스 방법은 매우 효율적이지만, 최악의 경우 예시에서는 지수적으로 많은 단계를 거칠 수 있습니다. 내부점 방법은 다항 시간 보장을 제공하며, 현대의 솔버는 문제에 따라 두 가지 방법을 모두 사용합니다.