정수형 선형 계획법

몇번 논의한 적은 있지만, 본격적으로 들어가서, 선형 계획법을 하더라도 대부분의 값은 비정수형으로 나온다. 예를 들어서 나의 답이 X1 = 73.5, X2 = 19.7이라고 하자. 이러한 답이 일반적으로 나오는 형태이다. 그러나, 이를 적용하는 것은 매우 어렵다. 휴리스틱 기법을 사용하기도 하지만 이러한 방식으로 도출한 정답은 최적 값이 아니다. 때문에 X1 , X2 >= 0 이라는 non-negativity constraint 에다가 are Integer라는 제약조건을 추가하는 것이 정수형 선형 계획법이다. 엑셀에서 어떠한 방식으로 정수형 해가 어떻게 도출되는지 파악해보도록 하겠다. 예시 데이터 셋 우선 위와 같은 상황이 있다고 하자. 이를 tight한 선형 계획법이라고 한다. 정수형 조건이 빠진다면 완화된 선형 계획법이라고 부를 수 있다. 완화된 선형계획법을 진행하여서 정수 해가 나왔다면 그것은 운이 좋은 경우이다. 하지만 대부분은 그렇지 않다. 다음을 보자. 가능 구역 (Fea...

원문링크 : 정수형 선형 계획법