열 생성

열 생성 또는 지연된 열 생성은 대형 선형 프로그램을 해결하기위한 효율적인 알고리즘입니다.

가장 중요한 아이디어는 많은 선형 프로그램이 너무 커서 모든 변수를 명시 적으로 고려할 수 없다는 것입니다. 이 전제는 대부분의 변수가 기본이 아니며 최적의 솔루션에서 0 의 값을 가정한다는 것입니다. 이 때문에 문제를 해결할 때 이론적으로 변수의 하위 집합 만 고려해야합니다. 열 생성은 이 아이디어를 활용하여 목표 함수를 개선할 가능성이 있는 변수,즉 비용이 음수로 감소된 변수(일반성을 잃지 않고 문제가 최소화 문제라고 가정)만 생성합니다.

해결되는 문제는 마스터 문제와 하위 문제의 두 가지 문제로 나뉩니다. 마스터 문제는 변수의 하위 집합만 고려 중인 원래 문제입니다. 하위 문제는 새 변수를 식별하기 위해 만들어진 새로운 문제입니다. 하위 문제의 목적 함수는 현재 이중 변수와 관련하여 새 변수의 비용 절감이며,제약 조건은 변수가 자연적으로 발생하는 제약 조건을 준수하도록 요구합니다.

과정은 다음과 같이 작동합니다. 마스터 문제가 해결되었습니다.이 솔루션에서 마스터 문제의 각 제약 조건에 대해 이중 가격을 얻을 수 있습니다. 이 정보는 하위 문제의 목적 함수에 사용됩니다. 하위 문제가 해결되었습니다. 하위 문제의 목표 값이 음수이면 비용이 음수로 감소된 변수가 확인되었습니다. 그런 다음 이 변수가 마스터 문제에 추가되고 마스터 문제가 다시 해결됩니다. 마스터 문제를 다시 해결하면 새로운 이중 값 세트가 생성되고 부정적인 비용 감소 변수가 식별되지 않을 때까지 프로세스가 반복됩니다. 하위 문제는 음수가 아닌 감소 된 비용으로 솔루션을 반환,우리는 마스터 문제에 대한 솔루션이 최적이라고 결론을 내릴 수있다.

많은 경우,이를 통해 이전에는 다루기 어려웠던 대규모 선형 프로그램을 해결할 수 있습니다. 이 성공적으로 사용되는 문제의 고전적인 예는 절단 재고 문제입니다. 이러한 종류의 접근 방식을 사용하는 선형 프로그래밍의 특정 기술 중 하나는 단치히-울프 분해 알고리즘입니다. 또한 열 생성은 승무원 스케줄링,차량 라우팅 및 널찍한 피-중앙값 문제와 같은 많은 문제에 적용되었습니다.

이 응용 수학 관련 기사는 스텁입니다. 당신은 그것을 확장하여 위키 백과를 도울 수 있습니다.