Ck601-note10

정수계획법의 필요성  선형계획법은 분할성의 가정을 두고 있다. 즉 모든 결정 변수는 제약조건을 충족하고 음수가 아닌 한 어떠한 값 도 가질 수 있다는 전제를 두고 있다.  항공회사에서 여객기 구매계획을 위한 모형의 최적해가 B747 을 1 3/4 대, Air Bus 400 을 2 1/3 대 구입하는 것이라 면 이는 실행이 불가능한 답이다.  결정변수 값이 정수라야 실행이 가능한 경우에는 최적해 가 정수가 된다는 것을 보장할 수 없는 선형계획법 대신 에 정수를 보장하는 정수선형계획법 ( 整數線形計劃法 ; integer linear programming: 이하 정수계획법이라 칭함 ) 을 이용하여야 한다.

정수계획법의 복잡성  간단해 보이는 정수제약조건의 첨가로 인하여 제 3 장에 서 설명한 심플렉스법만으로는 최적해를 구할 수 없고 정수를 보장할 수 있는 해법을 추가로 사용하여야 한다.  이렇게 추가로 사용하는 해법은 심플렉스법과 같이 효율 적이지 못하기 때문에 정수계획법의 최적해를 구하는 데 는 많은 시간이 소요된다.  컴퓨터의 발달로 선형계획법의 경우에는 문제의 크기에 거의 제한을 받지 않고 있으나 정수계획법의 경우에는 변수의 수와 제약조건의 수가 100 개 정도를 넘게되면 최 적해를 구하기가 어렵다.

정수계획법의 해법  1958 년에 R. E. Gomory 가 처음으로 “cutting plain method” 로도 불리는 Gomory 법과  A. H. Land 와 A. C. Doig 가 1960 년에 개발한 분단탐색법 ( 分段探索法 ; branch and bound method) 이 정수를 유 도하는 해법으로 사용되고 있다.  컴퓨터가 발달한 요즈음에도 문제가 큰 경우에는 최적해 를 구하는 대신 수용할 만한 선에서 만족해 (satisfactory solution) 를 구하여 활용하고 있는 실정으로 실무자들의 욕구를 충족시켜 주지 못하고 있다.

정수계획법의 분류  연속적변수 ( 連續的變數 ; continuous variable)  정수변수 ( 整數變數 ; integer variable)  일반정수변수 ( 一般整數變數 ; general integer variable)  이가정수변수 ( 二價整數變數 ; bianry integer variable)  전정수계획법 ( 全整數計劃法 ; all or pure integer programming)  혼합정수계획법 ( 混合整數計劃法 ; mixed integer programming)  전 0-1 이가정수계획법 (all 0-1 integer programming)  혼합 0-1 이가정수계획법 (mixed 0-1 integer programming)

예제 6-2  제일통운에서는 16 억 6,000 만원의 자금을 확보하여 가 격이 8,000 만원인 A 형과 6,000 만원인 B 형 특장차를 구 매하려고 한다. A 형 특장차로는 월 80 만원, B 형 특장차 로는 월 70 만원의 순이익을 얻을 수 있을 것으로 예상하 고 있다. A 형은 한 대당 월 12 시간, B 형은 월 20 시간의 정 비를 해야 할 것으로 예상하나 회사의 정비부에서 신규 구입하는 차량의 정비에 할애할 수 있는 시간은 월 380 시 간으로 추정하고 있다. 이익을 최대화하려면 두 종류의 차량을 몇 대씩 구입하여야 하는 가 ?

예제 6-2 의 정수계획모형

그래프를 이용한 해법  정수제약조건을 적용하지 않은 선형계획모형으로 가해 영역을 찾고 등가이익선을 그려 최적해를 구한다.  정수계획모형의 가능해는 선형계획모형의 가해영역내에 있어야 하고 정수여야 하므로 가해영역내에 있는 모든 점들이 아니라 x1 과 x2 의 좌표가 정수인 점들만이다.  정수구성점 ( 整數構成點 ; integer lattice point)  등가이익선을 원점 방향으로 평행으로 옮겨 오면서 제일 먼저 만나는 정수구성점이 정수계획모형의 최적해가 된 다.

비분할성기회비용  선형계획모형의 최적해에서 Z=1,779 1/11 이고, 정수계 획모형의 최적해에서는 Z=1,750 이다. 이 차이 29 1/11 은 결정변수 값의 분할을 허용하지 않고 정수를 요구한 데 기인하므로 이를 비분할성기회비용 ( 非分割性機會費用 ; opportunity cost of indivisibility) 이라 한다.

분단탐색법  분단탐색법은 먼저 정수계획모형에서 정수제약을 제외 한 선형계획모형의 최적해에서 2 개의 분단제약조건 ( 分 段制約條件 ; branching constraint) 을 도출한다.  이 제약조건을 선형계획모형에 하나씩 추가한 2 개의 확 장선형계획모형 ( 擴張線形計劃模型 ; augmented linear programming model) 을 구축하여 최적해를 구하고,  다시 분단제약조건을 도출하여 확장선형계획모형에 추 가하여 최적해를 구하는 과정을 정수제약을 가진 결정변 수 값이 정수가 될 때까지 반복하는 방법이다.

 (1) 정수제약이 없는 선형계획모형에서 구한 최적해가 정 수계획모형의 정수제약을 충족하면 이는 정수계획모형 의 최적해다.  (2) 정수제약을 가진 결정변수 x j 가 모두 정수가 아니면 아래와 같이 정수부분 (k j ) 과 소수부분 (f j ) 으로 나누어 나타 낼 수 있다.  x j = k j + f j

 이 중에서 임의로 하나를 분단변수 ( 分段變數 ; branching variable) 로 선택하여 ( 일반적으로 소수부분 f j 가 가장 큰 변수를 선택 ) 다음과 같은 2 개의 분단제약조건을 도출하 고 선형계획모형에 각각 하나씩 추가하여 2 개의 확장선 형계획모형을 구축한다.

 (3) (2) 에서 유도한 2 개의 확장선형계획모형의 최적해를 구하여 다음과 같은 절차를 따른다.  ① 모든 f j 의 값이 0 인 모형은 분단을 중단하고 원래의 정수계획 모형의 최적해 대상으로 남겨둔다.  ② 실행불능해 (infeasible solution) 인 모형은 분단을 중단한다.  ③ 모든 f j 의 값이 0 이 아닌 모형은 목적함수 값이 큰 ( 최소화문제 의 경우 작은 ) 모형을 먼저 분단을 시작하되 그 목적함수 값이 ① 에서 최적해 대상으로 남겨둔 모형의 목적함수 값보다 작지 않 으면 ( 최소화문제의 경우 크지 않으면 ) (2) 와 같은 방법으로 분단 을 계속하고, 작으면 ( 최소화문제의 경우 크면 ) 분단을 중단한다.

 (4) 더 이상 분단할 확장선형계획모형이 없을 때까지 (2) 와 (3) 을 반복한다.  모든 분단이 끝나면 원래의 정수계획모형의 최적해 대상 으로 남겨둔 해를 비교하여 목적함수 값이 가장 큰 ( 최소 화문제의 경우 가장작은 ) 확장선형계획모형의 최적해가 원래의 정수계획모형의 최적해가 된다.