수리계획모형의 간결성과 중복성에 관한 연구

Abstract

주어진 문제를 해결하기 위해 수리적 접근법을 사용할 경우 수리모형의 간결성이 요구되는 경우가 많다. 모형을 이해시켜야 할 경우 간결성은 중요해진다. 실제 많은 수리모형의 해법의 효율성은 모형을 구성하는 제약식의 수와 직접적인 연관성을 가지고 있기 때문에 가능한 제약식의 수가 적도록 모형을 구성하는 것이 요청된다. 그러나 모형이 정수계획법으로 정형화되면 선형계획법과는 달리 오형의 해를 구하는 방법으로 선형계획법의 심플렉스 해법과 같은 일반적인 해법이 존재하지 않기 때문에 해법의 효율성을 위해 제약식의 중복성(redundancy)이 필요한 경우가 있을 수 있다. 본 논문에서는 모형을 구성하는 제약식의 중복성을 활용하여 해를 효율적으로 도출하는 방법을 모색해보도록 한다.