선형 계획법

선형 계획법 문제를 표현하는 일반적인 형태를 표준형이라고 한다. 표준형은 모든 제약 조건이 등식이며, 모든 결정 변수가 비음 제약을 가지는 형태로 정의된다. 이는 문제를 체계적으로 분석하고 해법을 적용하기 위한 기본 틀을 제공한다.

표준형의 일반적인 수식 표현은 다음과 같다. 목적 함수는 결정 변수의 선형 결합으로 표현되며, 이를 최대화하거나 최소화하는 것이 목표이다. 모든 제약 조건은 선형 등식으로 주어지고, 각 결정 변수는 0 이상의 값을 가져야 한다는 비음 조건이 추가된다.

표준형으로의 변환은 실제 문제를 해결 가능한 형태로 만드는 중요한 과정이다. 부등식 제약은 슬랙 변수나 서플러스 변수를 도입하여 등식으로 바꿀 수 있다. 또한, 자유 변수(부호 제약이 없는 변수)는 두 개의 비음 변수의 차이로 표현함으로써 표준형에 맞출 수 있다. 이러한 표준화 작업을 거치면 단체법과 같은 일반적인 해법을 적용하는 것이 가능해진다.

선형 계획법 문제를 표현하는 또 다른 중요한 형식으로 정규형이 있다. 표준형과 달리 정규형은 모든 제약 조건이 등식이며, 모든 변수가 음이 아닌 조건을 만족하는 형태를 가리킨다. 일반적으로 선형 계획법의 해법인 단체법은 이 정규형을 기본 입력 형태로 요구한다.

정규형은 다음과 같은 구조를 가진다. 목적 함수를 최대화하거나 최소화하는 것이 목표이며, 모든 제약 조건은 선형 등식으로 표현된다. 또한 모든 의사 결정 변수는 0 이상이라는 비음수 제약을 갖는다. 예를 들어, 'Ax = b' 형태의 등식 제약과 'x ≥ 0' 조건이 그것이다. 실제 문제에서는 부등식 제약이 더 자연스럽게 발생하므로, 슬랙 변수나 잉여 변수를 도입하여 부등식을 등식으로 변환하여 정규형으로 만든다.

정규형의 장점은 해를 찾는 알고리즘의 초기 기저 가능해를 구성하기가 상대적으로 용이하다는 점이다. 특히 단체법은 정규형 문제에 대해 잘 정의된 기저 해를 출발점으로 삼아 최적해를 탐색한다. 이는 운용과학의 다양한 응용 문제, 예를 들어 자원 할당이나 생산 계획 문제를 체계적으로 풀기 위한 이론적 토대를 제공한다.

따라서 정규형은 선형 계획법의 이론적 분석과 계산적 실천 사이에서 핵심적인 역할을 한다. 대부분의 선형 계획법 소프트웨어와 솔버는 내부적으로 문제를 정규형 또는 이와 유사한 형태로 변환한 후 최적화 알고리즘을 적용한다.

단체법은 선형 계획법 문제를 해결하는 가장 널리 알려진 알고리즘이다. 조지 버나드 댄치그가 1947년에 공식화한 이 방법은 실행 가능한 영역이 볼록 다면체를 이루고, 최적해가 그 꼭짓점(기저 가능해) 중 하나에 존재한다는 원리에 기반한다. 알고리즘은 한 꼭짓점에서 시작하여 인접한 꼭짓점으로 이동하며 목적 함수 값을 개선하는 과정을 반복한다. 각 반복 단계에서는 기저 변수와 비기저 변수를 교체하는 피벗 연산이 수행되어 새로운 해를 탐색한다.

이 방법은 일반적으로 매우 효율적으로 작동하지만, 이론적으로는 최악의 경우 지수 시간 복잡도를 가질 수 있다. 이러한 한계는 후에 개발된 내점법과 같은 다항 시간 알고리즘의 등장 배경이 되었다. 그러나 실제 대규모 문제를 풀 때 단체법은 여전히 강력하고 신뢰할 수 있는 방법으로 평가받으며, 많은 상용 및 오픈소스 최적화 소프트웨어의 핵심 솔버로 채택되고 있다.

단체법의 구체적인 계산 절차는 문제를 표준형으로 변환한 후, 다음과 같은 주요 단계를 거친다.

이 과정은 최적해를 찾거나 문제가 무한계임을 확인할 때까지 2~5단계를 반복한다. 단체법의 다양한 변형으로는 수정 단체법, 이중 단체법 등이 개발되어 계산 효율성을 높였다.

내점법은 선형 계획법 문제의 해를 탐색할 때, 가능 영역의 경계를 따라 이동하는 단체법과 달리 가능 영역의 내부를 통과하는 경로를 따라 최적점에 접근하는 알고리즘 군을 총칭한다. 1984년 나렌드라 카르마카르가 제안한 카르마카르 알고리즘이 최초의 실용적인 다항 시간 내점법으로 알려지며 주목받기 시작했다. 이 방법은 계산 복잡도 이론상 단체법보다 우수한 성능을 보일 수 있음이 증명되어, 대규모 선형 계획법 문제 해결에 중요한 대안이 되었다.

내점법의 핵심 원리는 장벽 함수를 이용하여 제약 조건을 목적 함수에 반영하는 것이다. 예를 들어, 변수가 0보다 커야 하는 비음수 제약이 있을 때, 로그 장벽 함수를 목적 함수에 더하면 변수가 경계에 가까워질수록 함수 값이 급격히 증가하도록 만들어 실질적으로 내부 영역으로 해를 유도한다. 이렇게 변형된 문제를 일련의 매개변수 값에 대해 풀어가며 원래 문제의 최적해에 수렴하는 방식으로 진행된다.

주요 내점법 알고리즘으로는 원시-쌍대 내점법이 널리 사용된다. 이 방법은 원시 문제와 그 쌍대 문제를 동시에 고려하며, 뉴턴 방법을 적용하여 각 반복 단계에서 탐색 방향을 계산한다. 내점법은 특히 매우 많은 변수와 제약 조건을 가진 대규모 희소 행렬 문제에서 효율적인 성능을 보인다.

현대의 최적화 소프트웨어 패키지들은 대부분 단체법과 내점법을 모두 구현하여 문제의 규모와 구조에 따라 적절한 솔버를 선택할 수 있도록 하고 있다. 내점법의 발전은 볼록 계획법 및 반정부호 계획법 등 더 넓은 범위의 최적화 문제 해법에도 영향을 미쳤다.

선형 계획법은 운용과학의 핵심 도구로서, 제한된 자원을 가장 효율적으로 배분하는 문제를 해결하는 데 널리 활용된다. 특히 생산 계획, 물류 및 운송, 인력 스케줄링 등 실무적 의사결정 문제를 수학적으로 모델링하고 최적해를 찾는 데 적합하다. 이 기법은 복잡한 시스템에서 비용 최소화나 이익 극대화와 같은 목표를 선형 제약 조건 하에서 체계적으로 달성할 수 있게 해준다.

운용과학에서의 전형적인 응용 사례로는 식품 가공 공장의 원료 혼합 문제가 있다. 예를 들어, 최소 비용으로 영양 요건을 충족하는 사료를 배합하거나, 다양한 원자재를 사용하여 특정 품질 규격을 만족시키는 제품을 생산하는 문제를 선형 계획법으로 풀 수 있다. 또한 유통망 설계, 창고 위치 선정, 차량 경로 문제와 같은 공급망 관리 분야에서도 광범위하게 적용되어 운송 비용과 시간을 절감한다.

이처럼 선형 계획법은 복잡한 현실 문제를 단순화하고, 정량적 분석을 통해 합리적인 최적 의사결정을 지원하는 강력한 의사결정 지원 시스템의 기초를 이룬다. 컴퓨터의 발전과 함께 대규모 문제에도 적용 가능해지면서, 그 활용 범위는 통신 네트워크 설계, 마케팅 예산 배분 등으로 계속 확대되고 있다.

선형 계획법은 경제학에서 자원의 효율적 배분 문제를 해결하는 핵심 도구로 널리 사용된다. 경제 활동은 흔히 한정된 자원(노동, 자본, 원자재 등)을 사용하여 생산량이나 이익을 극대화하거나 비용을 최소화하는 문제로 모델링될 수 있으며, 이러한 문제는 선형 제약 조건과 선형 목적 함수로 표현하기 적합하다. 특히 레오니트 칸토로비치가 1939년 소련의 산업 생산 계획 문제를 해결하기 위해 선형 계획법의 초기 형태를 개발한 것은 경제학적 응용의 시초로 꼽힌다.

주요 응용 분야로는 생산 계획이 대표적이다. 여러 종류의 제품을 생산하는 공장이 주어진 원자재, 기계 가동 시간, 인력 등 제약 조건 하에서 최대 이익을 내기 위해 각 제품별 생산량을 결정하는 문제는 전형적인 선형 계획법 모형이다. 또한 자원 할당 문제, 예를 들어 한정된 예산으로 다양한 광고 매체에 광고비를 배분하여 총 노출 효과를 극대화하는 미디어 믹스 최적화에도 활용된다.

이처럼 선형 계획법은 경제 의사결정의 합리화를 위한 강력한 분석 도구로서, 복잡한 경제 현상을 체계적이고 정량적으로 모델링하여 최적 해를 도출하는 데 기여한다. 이는 운용과학 및 경제학의 실용적 교차점을 보여주는 사례이다.

네트워크 최적화는 선형 계획법의 주요 응용 분야 중 하나로, 네트워크 구조를 가진 문제의 효율적인 해결을 목표로 한다. 이는 교통, 통신, 물류 시스템 등에서 자원의 흐름을 최적으로 설계하고 관리하는 데 핵심적으로 사용된다. 네트워크는 노드와 이들을 연결하는 링크로 구성되며, 선형 계획법을 통해 링크의 용량, 비용, 수요와 같은 제약 조건 하에서 전체 시스템의 비용을 최소화하거나 효율을 극대화하는 흐름을 찾아낸다.

대표적인 문제로는 최단 경로 문제, 최대 흐름 문제, 최소 비용 흐름 문제 등이 있다. 예를 들어, 최소 비용 흐름 문제는 공급지에서 수요지로 물품을 운송할 때 각 경로의 단위 운송 비용과 처리 용량이 주어졌을 때, 총 운송 비용을 최소화하는 각 경로의 운송량을 결정하는 문제이다. 이러한 문제들은 선형 계획법의 표준형으로 정형화될 수 있으며, 네트워크의 특수한 구조를 활용한 전용 알고리즘도 개발되어 있다.

네트워크 최적화는 현실 세계의 복잡한 물류 및 운송 문제를 모델링하고 해결하는 데 널리 적용된다. 항공사의 승무원 스케줄링, 택배 회사의 배송 경로 최적화, 통신 네트워크의 대역폭 할당, 에너지 그리드의 전력 흐름 관리 등 다양한 분야에서 실용적인 가치를 창출한다. 특히 조지 버나드 댄치그가 개발한 단체법은 이러한 네트워크 문제를 해결하는 강력한 도구로 자리 잡았다.

이처럼 네트워크 최적화는 선형 계획법의 이론이 구체적인 공학 및 경영 과학 문제에 깊이 관여하는 대표적인 사례이다. 네트워크의 선형적 구조 덕분에 일반적인 선형 계획법 알고리즘보다 더 효율적으로 해를 구할 수 있는 경우가 많아, 이론과 실무를 연결하는 중요한 다리 역할을 한다.

정수 계획법은 선형 계획법의 특수한 형태로, 의사결정 변수 중 일부 또는 전부가 정수 값을 가져야 한다는 추가적인 조건이 부여된 최적화 문제를 다룬다. 이는 자원의 개수, 기계의 대수, 사람의 수 등과 같이 실수가 아닌 정수 단위로만 계획을 세워야 하는 현실 세계의 다양한 문제를 모델링하는 데 필수적이다. 선형 계획법의 제약 조건과 목적 함수는 모두 선형성을 유지하지만, 변수의 정수 조건 때문에 문제의 복잡도가 크게 증가하여 해법이 훨씬 어려워진다.

정수 계획법 문제는 정수 조건이 부여된 변수의 범위에 따라 여러 유형으로 나뉜다. 모든 변수가 정수여야 하는 경우를 순수 정수 계획법이라 하며, 일부 변수만 정수이고 나머지는 실수 값을 허용하는 경우는 혼합 정수 계획법이라고 한다. 특히 변수가 0 또는 1의 값만을 취하는 이진 변수를 사용하는 문제는 0-1 정수 계획법으로 불리며, 시설 입지 결정이나 프로젝트 선택 문제 등에 널리 활용된다.

이러한 문제를 해결하기 위한 대표적인 알고리즘으로는 분기 한정법이 있다. 이 방법은 가능한 정수 해의 공간을 체계적으로 탐색하는데, 선형 계획법 완화 문제(정수 조건을 제거한 문제)의 해를 구한 후, 이를 기준으로 해 공간을 분기하고 각 부분 문제에 대한 상한 또는 하한을 계산하여 탐색 범위를 제한한다. 또한, 절단 평면법은 완화 문제의 실수 최적해 주변에 새로운 선형 제약 조건(절단 평면)을 계속 추가하여 정수 최적해에 점점 수렴하도록 하는 기법이다. 현대의 최적화 소프트웨어는 이러한 기법들을 효율적으로 결합하여 복잡한 정수 계획법 문제를 푼다.

정수 계획법은 순수한 수학적 최적화 이론을 넘어 실용적인 운용과학 분야에서 광범위하게 응용된다. 대표적으로 물류 네트워크에서의 차량 경로 문제, 공장의 생산 계획 및 일정 스케줄링, 통신 네트워크 설계, 그리고 금융에서의 포트폴리오 선택 문제 등이 있다. 이러한 문제들은 선형 관계로 표현할 수 있지만, 의사결정이 정수 단위로 이루어져야 하기 때문에 정수 계획법을 적용해야 최적의 해를 찾을 수 있다.

비선형 계획법은 선형 계획법과 대비되는 개념으로, 목적 함수나 제약 조건 중 적어도 하나가 비선형인 최적화 문제를 다루는 분야이다. 선형 계획법이 모든 관계를 직선(1차식)으로 가정하는 반면, 비선형 계획법은 곡선이나 더 복잡한 함수 관계를 포함하는 현실 세계의 다양한 문제를 모델링할 수 있다. 이는 공학, 경제학, 금융 등에서 발생하는 복잡한 시스템의 최적화에 필수적이다.

비선형 계획법 문제의 해법은 선형 계획법에 비해 일반적으로 훨씬 복잡하며, 국소 최적점과 전역 최적점의 구분, 수렴성 보장 등 추가적인 고려 사항이 많다. 대표적인 해법으로는 경사 하강법, 뉴턴 방법, 라그랑주 승수법, 내점법 등이 있으며, 문제의 특성(예: 볼록성)에 따라 적합한 알고리즘이 선택된다. 컴퓨터의 발전과 계산 능력 향상은 비선형 계획법의 적용 범위를 크게 확장시켰다.

비선형 계획법과 선형 계획법은 상호 보완적 관계에 있다. 복잡한 비선형 문제를 일련의 선형 문제로 근사화하여 단체법으로 푸는 분할 계획법 같은 접근법이 개발되기도 했다. 또한, 정수 계획법과 결합된 비선형 정수 계획법은 디지털 시스템 설계나 스케줄링 등 이산적 결정과 비선형 관계가 공존하는 문제를 해결하는 데 사용된다.