비선형 정수 계획은 일반적으로 선형 부분과 정수 부분으로 나눌 수 있는 것으로 간주되므로 정수 계획은 종종 선형 계획의 특수 부분으로 간주됩니다. 선형 계획 문제에서 일부 최적 솔루션은 분수 또는 소수일 수 있지만 일부 특정 문제의 경우 솔루션이 정수여야 하는 경우가 많습니다. 예를 들어, 솔루션은 기계 수, 작업 수 또는 적재된 자동차 수입니다. 정수의 요구 사항을 충족시키기 위해 언뜻 보면, 네가 해야 할 일은 얻은 비정수를 반올림하는 것 같다. 사실 정수가 반드시 실행 가능한 최적의 해법은 아니므로 정수 계획을 해결할 수 있는 특별한 방법이 있어야 합니다. 정수 계획에서 모든 변수가 정수로 제한된 경우 순수 정수 구성이라고 합니다. 일부 변수만 정수로 제한된 경우 혼합 정수 구성이라고 합니다. 정수 계획의 특수한 경우는 0 1 구성이며 변수는 0 또는 1 으로 제한됩니다.
R.E. Gomory 가 1958 년에 절단 평면법을 제안한 이후 정수 계획은 이미 독립된 분기가 되었으며, 지난 30 년 동안 사람들은 여러 가지 문제를 해결할 수 있는 여러 가지 방법을 개발했다. 정수 계획을 해결하는 가장 일반적인 방법은 원래 문제의 도수라고 하는 관련 문제를 점진적으로 생성하는 것입니다. 각 파생 문제에는 보다 쉽게 해결할 수 있는 릴랙스 문제 (릴랙스 문제의 소스 문제 라고 함) 가 함께 제공됩니다. 릴랙스 문제의 해결을 통해 소스 문제의 귀착점, 즉 소스 문제를 포기해야 하는지 아니면 하나 이상의 자체 파생 문제를 만들어 대체해야 하는지 결정합니다. 그런 다음 취소되거나 대체되지 않은 원래 문제의 파생 문제를 선택하고 해결되지 않은 파생 문제가 없을 때까지 위 단계를 반복합니다. 현재 비교적 성공적이고 유행하는 방법은 가지구분법과 절단평면법이 있는데, 모두 상술한 틀 아래에서 형성된 것이다.
0- 1 프로그래밍은 정수 계획에서 중요한 위치를 차지합니다. 한편으로는 분배, 토지 선택, 납품과 같은 많은 실제 문제들이 이런 계획으로 귀결될 수 있다. 한편, 임의의 경계 변수의 정수 계획은 0- 1 계획과 같으며, 많은 비선형 계획 문제는 0- 1 계획 방법으로 정수 계획 문제로 나타낼 수 있으므로 많은 사람들이 이 방향의 연구에 힘쓰고 있습니다. 0- 1 계획을 해결하는 일반적인 방법은 분기 구분 방법이며, 할당 문제를 해결하는 헝가리 방법과 같은 다양한 특수 문제에 대한 특별한 방법도 있습니다.
[편집]
정수 프로그래밍과 조합 최적화의 관계
넓은 의미에서 정수 계획과 조합 최적화의 영역은 동일하며 제한된 수의 대안에서 특정 기준을 충족하는 최상의 솔루션을 찾는 것입니다. 정수 계획의 광범위한 배경을 반영하는 많은 전형적인 문제들이 있다. 배낭 (또는 적재) 문제, 고정 비용 문제, 조화로운 원정 문제 (조합집 문제), 효과적인 원정 문제 (조합커버 문제), 배송 문제 등이 있습니다. 따라서 정수 프로그래밍의 적용 범위도 매우 광범위합니다. 산업 공학 설계 및 과학 연구뿐만 아니라 컴퓨터 설계, 시스템 신뢰성, 코딩 및 경제 분석에도 많은 응용 프로그램이 있습니다.
[편집]
정수 계획 유형
정수 계획은 다음과 같이 구분됩니다.
1. 순수 정수 계획: 모든 결정 변수가 정수 구성이어야 합니다.
2. 혼합 정수 계획: 일부 결정 변수에는 정수 계획이 필요합니다.
3. 순수 0- 1 정수 계획: 모든 결정 변수가 0- 1 정수 계획이어야 합니다.
4. 혼합 0- 1 계획: 특정 결정 변수가 0- 1 인 정수 계획이 필요합니다.
정수 계획과 선형 계획의 차이점은 정수 제약 조건이 추가된다는 것입니다. 정수 제약 조건을 고려하지 않는 선형 구성을 정수 프로그래밍이라고 하는 선형 릴랙스 모델입니다.
[편집]
정수 계획 모델
실생활에서 결정 변수가 부품 수, 세트 수, 상자 수, 선박 수, 차 수 등을 나타내는 경우 제품의 경우 변수는 정수 값만 반올림할 수 있습니다. 예를 들어, 절단 모델은 실제로 정수 계획 모델입니다. 이 경우 의사 결정 변수는 절단 된 강관의 수를 나타내며 정수 값만 취할 수 있습니다. 따라서 정수 계획 모델도 광범위하게 적용되는데, 아래 예시에서 알 수 있습니다.
정수 계획을 해결하는 자연스러운 아이디어 중 하나는 정수 계획의 최적 솔루션이 정수 계획의 선형 릴랙스 모델의 최적 풀림을 통해 얻을 수 있는지 여부입니다. 대답은' 아니오' 입니다. 이렇게 반올림한 결과는 실행 가능한 해결책이 아니기 때문입니다.
정수 프로그래밍은 일반적인 선형 프로그래밍보다 해결하기가 더 어렵습니다. 지금까지 정수 계획을 해결하는 기본 아이디어는 특정 검색 규칙에 따라 정수 계획의 선형 릴랙스 모델의 실행 가능한 도메인에서 정수 최적 솔루션을 찾는 것입니다 (또는 정수 최적 솔루션이 없음을 확인). 따라서 정수 계획에 대한 솔루션을 찾는 데 더 많은 시간이 소요됩니다. 현재 일반적으로 사용되는 해법은 주로 분기계법, 절단평면법, 궁법입니다.