정수 선형 프로그래밍이란 무엇입니까?

알 수없는 모든 변수가 정수 또는 정수 여야 함을 지정하면서 선형 시스템을 풀려고 할 때 정수 선형 프로그래밍 문제가 발생합니다. 선형 시스템은 프로그래머가 솔루션을 찾으려고하는 상황을 설명하는 일련의 방정식입니다. 일반적으로 최대화하거나 최소화해야하는 하나의 방정식과 알 수없는 변수에 제한을 두는 하나 이상의 제한 방정식으로 구성됩니다. 시스템이 선형이 되려면 각 제한은 선형 방정식이어야합니다. 즉, 지수가 1보다 큰 알 수없는 변수의 인스턴스를 포함하지 않아야합니다.

컴퓨터를 사용하여 일반 선형 시스템을 쉽게 해결할 수 있습니다. 이 프로그램은 도함수를 찾아 0으로 설정하여 해를 식별 할 수 있습니다. 그런 다음 함수에서 바로 근처를 확인하여 포인트가 최대 또는 최소인지 확인할 수 있습니다. 미분이 함수를 따라 각 지점에서 정의되는 한, 컴퓨터는 검사 할 수있는 솔루션 수가 제한되어 있습니다.

선형 프로그래밍은 정수 제한을 추가하여 정수 선형 프로그래밍이됩니다. 즉, 문제는 동일하게 유지되지만 정답은 알 수없는 값의 정수 값으로 구성되어야합니다. 정수 여야합니다. 때때로 이것은 분수가 허용되는 경우와 비교하여 솔루션이 차선 책임을 의미합니다. 그러나 아이템은 종종 개별적이고 개별화 할 수없는 단위로 제공되는 실제 세계를 반영합니다. 이는 기업이 가능한 한 많은 수익을 극대화하기를 원하지만 제품의 일부만 판매 할 수 없기 때문에 정수 선형 프로그래밍이 비즈니스 애플리케이션에 중요합니다.

정수 제한이 설정되면 선형 시스템을 해결하는 문제는 NP- 완료입니다. 이것은 컴퓨터가 시스템을 해결하는 데 필요한 시간이 불확실하다는 것을 의미합니다. 정수 제한을 사용하면 미분의 영점이 정수에 해당한다고 보장 할 수 없으므로 컴퓨터에서 미분 도구를 사용할 수 없습니다. 해결책은 모든 정수 중에서 가장 높거나 가장 낮은 정수가 될 것이므로 컴퓨터는 무한정의 시간이 걸릴 수있는 프로세스를 모두 확인해야합니다.

프로그래머는 이러한 문제의 복잡성을 처리하기 위해 휴리스틱 또는 문제 해결 방법을 개발했습니다. 정수 선형 프로그래밍 문제를 해결하는 한 가지 방법은 분기 및 바운드 알고리즘으로, 컴퓨터는 원래 문제와 관련된 일련의 문제를 해결하여 사용 가능한 값 범위를 하나의 솔루션으로 좁 힙니다. 그러나 복잡한 문제의 경우 시간이 오래 걸릴 수 있습니다.