1.서 론

본 논문에서 새로이 정의하는 문제는 수행을 고려하 는 총 작업의 수가 n 일 때 m 개의 기간(period)에 걸쳐 각 기간별로 수행할 작업들을 선택하는 문제이다. 모든 작업들은 기간별 작업집합 N _i , i = 1, …, m에 나뉘어 속 하여 있고, N _i 에 속한 작업들은 늦어도 기간 i 까지는 수 행되어야 한다. 기간 i 에서 수행할 작업으로 k_i 개를 선 택한다. N _i 에 속한 작업 j 를 수행하는데 걸리는 시간은 a_ij 이고, 수행되면 c_ij 의 이익이 발생한다. 기간 1부터 기 간 t 동안에 총 투입할 수 있는 생산시간은 b_t 이다(t = 1, …, m).

우리는 이 문제를 선수제약 다기간 0-1 배낭문제(K; cardinality constrained multi-period 0-1 knapsack problem)라 부른다. 즉 문제 (K)는 기간에 따라 투입할 수 있는 생산 시간의 제약 하에서 모든 기간에 걸쳐 발생하는 총 이익 이 최대가 되도록 각 기간별로 수행할 작업들을 여러 개 선택할 수 있는 문제이다.

변수 x_ij 는 작업집합 N _i 에 속한 작업 j 의 수행여부를 표현하는 0-1 변수라 하자. 즉 작업 j 를 수행하면 1, 아 니면 0의 값을 갖는 것으로 정의한다. 그러면 선수제약 다기간 0-1 배낭문제 (K)는 다음과 같이 표현된다.

subject to

여기서, 모든 a_ij , c_ij , b_t 는 양수, k_i 는 정수, 1 ≤ k_i ≤ ni , 0 < b₁ < b₂ < … < b_m 이고, 집합 N _i 는 서로 중복적이지 않다.

문제 (K)는 기존의 다기간 배낭문제에서 확장되어 기 간별로 수행할 작업을 복수 개인 k_i 로 선택할 수 있도록 확장된 문제이다. 문제 (K)에서 선수제약 (3)의 우변 k_i 가 모두 1이 되는 특수한 경우, 즉 각 기간 i 마다 수행할 작 업을 한 작업만으로 제한한 경우의 문제는 기존의 다중선 택 다기간 배낭문제(multiple-choice multi-period knapsack problem)가 된다[5]. 문제 (K)에서 선수제약 (3)이 완화되어 삭제된 문제는 다기간 배낭문제(multi-period knapsack problem) 가 된다[2, 4].

문제 (K)는 0-1 정수계획 문제이므로 최적해는 일반적 으로 분지한계법을 적용하여 구하며, 한계전략으로는 선 형계획 완화를 사용한다. 그러면 분지한계법의 각 분지 단계마다 선형계획 완화문제를 반복적으로 풀어야하므 로, 선형계획 완화문제의 최적해를 신속하게 구하는 효 율적인 해법이 요구된다. 이에 본 논문에서는 정수계획 문제 (K)가 선형계획으로 완화된 문제에 대해 연구한다. 이 선형계획 문제를 선수제약 다기간 선형계획 배낭문제 라 부르자. 이 문제는 선수제약과 다기간 제약 구조를 갖 는 선형계획 문제 자체로서도 그 특성을 연구할 만한 가 치가 있다.

제 2장에서는 선수제약 다기간 선형계획 배낭문제 (P) 를 제시한다. 제 3장에서는 문제 (P)의 효율적인 해법을 개발하기 위해 기존 연구와는 달리 먼저 문제 (P)를 각 기간에 대응하여 발생하는 여러 독립적인 부문제로 분해 하고 그 특성을 정리한다. 제 4장에서는 문제 (P)의 다기 간 제약구조에 성립하는 모수분석적 분배특성들을 보이 고, 이 특성을 기반으로 문제 (P)의 효율적인 해법을 제시 한다. 아울러 이 해법이 갖는 최악상황하의 계산복잡도 를 분석한다. 제 5장에서는 수치예제를 통해 해법의 적용 을 보인다.

2.선수제약 다기간 선형계획 배낭문제

선수제약 다기간 선형계획 배낭문제 (P)는 다음과 같 이 표현된다.

subject to

Faaland[4]는 제약식 (7)이 존재하지 않고, 모든 변수 는 정수 값을 갖는 다기간 배낭문제를 제시하였다. 그는 이 정수계획 문제의 최적해를 구하기 위한 분지한계법 에 활용하기 위해 선형계획 완화문제를 연구하였다. 그 는 이 선형계획 완화된 문제를 쌍대문제로 변환하고 쌍 대문제에 존재하는 다기간 제약구조의 특수성을 이용하 여, 최악상황하의 계산복잡도가 O (m)인 해법을 제시하 였다.

Dudzinski and Walukiewicz[2]은 제약식 (7)이 존재하지 않고, 모든 변수는 0-1 값을 갖는 다기간 0-1 배낭문제를 제시하였다. 그들은 NP -hard인 이 문제의 최적해를 구 하기 위해 분지한계법이 바람직하다는 것과 한계전략으 로서 LP완화 문제를 효율적으로 해결하는 해법의 중요 성을 언급하였다. 해법은 먼저 기간 1에서 집합 N₁ 에 속 한 변수들로만 이루어지는 선형계획 배낭문제의 최적해 를 구하고 비영의 값을 갖는 변수들을 선정한다. 반복적 으로 기간 t(t = 2 , …, m - 1)에서는 이전 단계에서 선정 된 비영의 최적해 값을 갖는 변수들과 여기에 집합 N_t 에 속하는 변수들을 추가하여 이루어지는 축소된 선형계 획 배낭문제를 고려하고, 이 문제의 최적해를 구한 후 비영의 값을 갖는 변수들을 선정한다. 최종적으로 기간 m 에서도 이전 단계에서 선정된 비영의 최적해 값을 갖 는 변수들과 여기에 집합 N_m 에 속하는 변수들을 추가하 여 만들어지는 축소된 선형계획 배낭문제를 고려하고 최 적해를 구한다. 최종적으로 구해진 최적해를 변환함으로 써 원문제의 최적해로 유도하는 O (mn) 의 해법을 제시 하였다.

Lin and Wu[5]는 각 기간 i 마다 한 작업만이 선택되 도록 하는 다중선택 다기간 0-1 배낭문제를 제시하였다. 제약식 (7)에서 모든 k_i 가 1이 되는 경우, 즉 ∑ j ∈ N i x ij = 1, i∈I 인 제약을 다중선택 제약이라 부른다. 그들은 이 문 제의 최적해를 구하기 위한 분지한계법의 한계전략으로 서 선형계획 완화된 문제를 연구하였다. 특히 다중선택 제약이 갖는 변수들간의 볼록우월성과 최대 두 개의 변 수가 동시에 분수값을 갖고 이들은 인접한 변수라는 특 성을 정리하고, 이 특성에 기반하여 선형계획 완화문제 의 최적해를 구하는 해법을 제시하였다.

본 논문에서 제시한 선수제약을 갖는 다기간 선형계 획 문제 (P)에서는 각 기간 i 마다 한 개 이상의 k_i 개 작 업들을 선택할 수 있는 문제이다. 따라서 본 문제 (P)에 는 LIn and Wu[5]의 해법에 기반이 되는 다중선택 제약 의 여러 특성들이 성립하지 않는다.

이에 따라 본 연구에서는 기존 연구와는 달리 각각의 기간을 독립적으로 고려하여 문제 (P)로부터 각 기간에 대응하는 독립적인 m 개의 부문제를 정의하고, 선수제약 을 갖는 이들 부문제의 최적 기저변화에 대한 특성을 정 리한다. 다음으로 이러한 특성을 활용하여 문제 (P)의 여 러 다기간 제약에 대한 모수분석 특성을 분석하고 정리 하여 문제 (P)의 효율적인 해법을 개발한다.

3.문제의 분해

문제 (P)에서 제약식 (6)은 m 개의 제약식으로 구성되 며, t 번째 제약식에서 우변 b_t 를 배분할 대상 작업들에 는 기간 1로부터 기간 t 까지의 모든 작업들이 포함된다. 그러나 본 연구에서는 각 기간을 독립적으로 고려해서, 한 기간 i 에 속한 작업 j ∈ N _i 들로만 구성된 다음과 같 은 부문제 (SPi)를 정의한다( i∈I).

위 부문제 (SPi)는 선수제약을 갖는 선형계획 배낭문제 의 형태를 갖는다. 이러한 유형의 문제는 Campello and Maculan[1], Dudzinski[3]이 연구하였다. 부문제 (SPi)에서 k_i 가 정수가 아닌 실수인 경우의 문제는 Won[6]이 연구 하였다.

Campello and Maculan[1]은 부문제 (SPi)의 기저가능 해가 갖는 특성으로서 두 변수가 동시에 분수값을 갖고, 그 합은 항상 1이 된다는 것을 보였다. 이들은 부문제 (SPi)의 쌍대문제를 고려하고, 쌍대 최적해는 계산 복잡 도 O (n_i³) 에 구할 수 있음과 이로부터 문제 (P)의 최적해를 선형 시간 안에 도출할 수 있음을 보였다.

Dudzinski[3]는 제약식 (11)이 등식으로 성립한다는 점 을 이용하여, 각 변수 x_ij 를 나머지 변수로 표현하고 목적 함수 (9)와 제약식 (10)에 치환, 대입함으로써(j = 1, 2, …, n_i), 부문제 (SPi)를 ni 개 선형계획 배낭문제로 변환하였다. 다음으로 각 변환된 부문제들의 최적 목적함수 값을 비교 함으로써 최적해를 구하는 O (n_i²) 의 해법을 제시하였다. 그러나 이 해법은 각 변수를 나머지 다른 변수로 치환해 서 부문제의 해를 구하므로, 분지한계법을 위한 문제 (P) 의 해법에 적용하기 힘들다는 단점이 있다.

Won[6]은 우변상수 k_i 가 정수가 아닌 실수 값을 갖는 문제를 연구하고, 이 제약을 확장된 일반상한 제약이라 불렀다. 우변 k_i 가 실수인 경우의 최적 기저의 특성은 선 택적 의미를 갖는 정수인 경우의 특성과는 다르게 나타 난다. 즉, k_i 가 실수인 경우 분수값을 갖는 변수의 수는 한 개나 두 개가 될 수 있으나, 정수인 경우에는 분수값 을 갖는 변수의 수는 0이거나 또는 두 개가 된다.

본 논문에서는 k_i 가 정수인 부문제 (SPi)에서 기저가능 해가 갖는 최적 기저변화의 특성을 다음 보조정리 1에서 보이고 최적비율 탐색해법에 활용한다.

먼저 필요한 기호들을 정리한다. 위 부문제 (SPi)에서 임의의 두 지수 j₁ , j₂ 가 j₁ < j₂ 이면 a_ij1 ≤ a_ij2 이 되도록 변수들이 재배열된 것으로 가정한다. 제약식 (10)의 우변 은 모수 b 로 설정한다. 부문제의 한 기저가능해를 x_i ≡ (x_i1 , …, x_ini)라 하고, 제약식 (10)에서 이 해가 갖는 좌변 값을 b ˆ i = ∑ j ∈ N i a ij x ¯ ij, 목적함수 값을 z i b ˆ i = ∑ j ∈ N i c ij x ¯ ij 라 하자. 또한 지수집합 J _i 를 J _i ≡{ j ∣ x_ij = 1 , j∈N _i }이 라 정의한다. 이 부문제에 가능해가 있음을 보장하기 위해 모수 b 의 범위는 b ≥ b ˆ i min으로 설정한다. 여기서, b ˆ i min은 제약식 (10)의 계수 a_ij들 중에서 가장 작은 k_i 개 계수들의 합으로 정의한다. 즉 b ˆ i min = ∑ j = 1 k i a ij 이 된다. b ˆ i min에 대응 하는 해는 xij = 1, j ∈ J _i = {1, …, k_i }, x_ij = 0, j∈ N _i＼ J _i 이다. 이 초기해는 부문제의 우변 b 가 b = b ˆ i min가 되면 바 로 최적해가 된다.

부문제 (SPi)에서 제약식 (10) 및 (11)에 해당하는 두 기저변수의 지수를 각각 j₁, j₂라 하고, 축소 기저행렬 B 는 두 기저변수에 해당하는 제약식 (10) 및 (11)의 열로 구성된 2×2행렬로 정의한다. 우변이 b ˆ i 에서 Δb_i 만큼 더 증가할 때 최적 목적함수 값의 변화는 다음 식 (13)과 같 이 표현된다.

여기서 c B = c i j 1 , c i j 2 , e = (1, 0)^t 이다. 위 식에서 a i j 1 = a i j 2 인 경우에는 θ_i (j₁, j₂ ) ≡∞로 정의한다. 식 (13)에서 Δb_i 의 증가에 따른 목적함수의 증가 비율을 다음과 같 이 θ_i (j₁, j₂ ) 로 표기한다.

부문제의 목적함수 z_i (b)는 b가 b ˆ i min로부터 증가함에 따 라 위로 볼록한 조각적 선형함수(piecewise linear concave function)의 형태를 이룬다. 다음 보조정리 1에서 우변 b ˆ i 는 편의상 z_i (b)의 한 절점(break point)이라 하자. 절점에 대응 하는 최적해에서 분수값을 갖는 변수의 수는 0이다. 절점 이 아닌 경우에는 항상 두 변수가 분수값을 갖고 그 합은 1을 유지한다. 그러나 이 두 변수가 인접한 변수가 되지는 않는다.

보조정리 1 부문제 (SPi)에서 한 기저가능해 x_i 의 좌변 값을 b ˆ i 라 하자. 우변이 b ˆ i 에서 더 증가함에 따라 발생 하는 새로운 기저변수의 지수 f₁ , f₂ 와 최적 목적함수의 증가 비율은 다음과 같이 결정된다.

(증명) 부문제 (SPi)의 우변이 b ˆ i 이면 기저가능해 x 는 최적해이며, 제약식 (10) 및 제약식 (11)은 등식으로 만족 한다. 여기서 ∣ J _i ∣ = k_i 이다. 우변이 b ˆ i 에서 작은 양 Δb_i 만 큼 더 증가할 때 발생하는 새로운 최적해도 제약식 (10) 및 (11)을 등식으로 만족해야 한다. 우변이 Δb_i 만큼 더 증가했으므로 제약식 (10)을 등식으로 만족시키기 위해서는, 현재의 해 x_i 에서 1의 값을 갖는 한 변수 x i j 1 j 1 ∈ J i의 값은 감소하여야 하고, 현재 0의 값을 갖고 있는 다른 한 변수 x i j 2 j 2 ∈ N i \ J i , j 2 > j 1는 증가하여야 한다. 여기서 j₂ > j₁ 이면 a i j 2 ≥ a i j 1 임에 유의한다. 또한 제약식 (11)을 등식으로 유지하기 위해서는 변화된 두 변수가 동시에 분 수값을 갖고 그 합은 1이 될 수밖에 없다[1]. 따라서 목적 함수 z i b ˆ i + Δ b i는 식 (13)과 같이 발생하며, 목적함수 값이 최대로 증가하는 비율은 정리와 같이 결정된다. ■

부문제 (SPi)의 모수 b 가 b ˆ i min에서 점차 증가함에 따라 발생하는 목적함수의 최적 증가비율들은 보조정리 1을 적용하여 구할 수 있다. 다음에 제시한 최적비율 탐색해 법은 이러한 최적 증가비율들을 구하는 해법이다. 구해진 최적비율들의 집합을 목록 L _i^* 라 한다. 이 최적비율 탐색 해법은 k_i 가 정수일 때 부문제 (SPi)의 임의의 우변에 대 한 최적해를 찾는 데에도 활용될 수 있다. 이 경우 최악상 황하의 계산복잡도는 제 4장에서 보이듯이 O(n_i²logn_i) 으로 분석된다.

최적비율 탐색해법

0. J _i ← {1, …, k_i }, L _i ← ∅, L _i^* ← ∅

1. 다음과 같이 모든 비율 θ_i (j₁, j₂ ) 를 계산하고, 비율 크기의 비증가 순으로 후보 비율목록 L _i 에 정리한다. 여기서 비율 값이 음수이거나 ∞ 이면 미리 제거한다.

2. 비율목록 L _i 에서 첫 번째 위치한 가장 큰 비율을 선택한다. 이 비율을 θ_i (f₁, f₂ ) 라 하자.

3. f₁∈ J _i , f₂ ∉ J _i 이면, 다음을 수행하고, 단계 4로 간다.

4. L _i ← L _i＼{θ_i (f₁, f₂ )}라 한다.

L_i = ∅ 이면, 과정을 끝낸다. 아니면 단계 2로 간다.

4.다기간 제약구조의 특성 및 해법

본 장에서는 문제 (P)에서 여러 기간에 대한 제약식 (6)의 우변들을 각 부문제에 최적으로 배분하는 다기간 제약구조의 분배특성을 분석하고 해법에 적용한다. 문제 (P)의 한 가능해 x =(x₁, …, xm)가 갖는 제약식 (6)의 좌변 값은 ∑ i = 1 t ∑ j ∈ N i a ij x ¯ ij = b ¯ t , t = 1 , …, m 으로 계산 된다. 따라서 제약식 (6)의 각 우변이 b_t 이라면 가능해 x 는 바로 최적해가 된다. 문제 (P)의 초기해로는 x_ij = 1, j ∈ J _i = {1, …, k_i }, x_ij = 0, j∈ N _i ＼ J _i , i∈I 로 설정한다. 이 초기해 x 는 제약식 (6)의 우변이 b ¯ t min = ∑ i = 1 t b ˆ i min , t = 1, …, m 이면 바로 최적해가 된다.

다음 정리 2 및 정리 3은 문제 (P)에서 다기간 제약식 (6)의 각 우변 b_t 가 기간 1로부터 기간 t 까지 속한 모든 작업들에 최적으로 분배되는 방식을 보여준다(t∈I). 정리 2에서 가능해 x = (x 1, …, xm)가 기간 i 에서 갖는 목적 함수 증가비율 θ_i^* (f₁, f₂ ) 는 부문제 (SPi)의 우변이 b ˆ i = ∑ j ∈ N i a ij x ¯ ij일 때 보조정리 1에 의해 결정된 비율이다. 즉, θ_i^* (f₁, f₂ ) ∈ L _i^* 이다.

정리 2 문제 (P)의 한 기저가능해를 x , 이 해의 우변 값 을 b ¯ t = ∑ i = 1 t ∑ j ∈ N i a ij x ¯ ij, t = 1 , …, m 라 하자. 문제 (P) 의 우변들이 b_t 에서 더 증가함에 따라 발생하는 새로운 기저변수의 지수 f₁ , f₂ 와 최적 목적함수의 증가비율 θ_p^* (f₁, f₂ ) 는 다음과 같이 결정된다.

여기서, θ_i^* (f₁, f₂ ) ∈L _i^* , i∈I = {t∈I ∣ b_t < b_t }이다.

(증명) 문제 (P)의 우변 b_t , t = 1 , …, m 는 현 기저가능 해 x 가 갖는 제약식 (6)의 좌변값과 같으므로 현 기저가 능해는 최적해이다. 각 우변이 현재의 b_t , t = 1 , …, m , 로부터 더 증가하려면 우변에 증가할 수 있는 여유가 있 어야 한다. 이러한 제약식의 지수집합을 I 라 하면, I = {t∈I ∣ b_t < b_t }이다. 다기간 제약구조 (6)에 의해 임의의 기간 t∈I 에 해당하는 제약식의 모든 계수들은 기간 t 이후의 기간에 해당하는 모든 제약식에 포함되어 있다. 따라서 I 에 속하는 모든 제약식의 우변이 동시에 적절 히 작은 양 Δb 만큼 더 증가될 때의 기저변화는, 여러 부 문제 (SPi), i∈I, 들 중에서 어느 한 부문제의 우변이 Δb 만큼 더 증가될 때의 변화와 같다. 어느 한 부문제 (SPi)에서 우변이 Δb 만큼 더 증가할 때의 최적 목적함 수의 증가비율은 보조정리 1에서와 같이 θ_i^* (f₁, f₂ ) ∈L _i^* 로 구해진다. 따라서 우변 b_t , t∈I가 Δb 만큼 더 증가 할 때 발생하는 최적 목적함수의 증가비율은 여러 비율 들 θ_i^* (f₁, f₂ ) , i∈I 중에서 가장 큰 비율로 결정된다. 따 라서 정리가 성립한다. ■

다음 정리 3은 정리 2에 의해 결정된 최적 기저가 최 적으로 유지되면서 각 우변들이 증가할 수 있는 최대값 을 보여준다.

정리 3 문제 (P)에서 한 기저가능해를 x , 이 해의 우변 값을 b_t , t = 1 , …, m , 우변이 증가함에 따라 발생하는 목적함수 값의 최대 증가비율을 θ_p^* (f₁, f₂ )라 하자. 가능 해 x 가 최적으로 유지되면서 각 우변이 증가할 수 있는 최대값은 다음과 같이 결정된다.

여기서, Δb_q = min{Δb_t ∣ t∈I, t ≥ p}, Δb_t = b_t = b_t , I= {t∈I ∣ b_t < b_t }이다.

(증명) 문제 (P)에서 제약식 (6)의 우변이 b_t이면 가능해 x 는 문제 (P)의 최적해가 된다. 우변 b_t , t∈I , 들이 증가 가능한 값을 Δb 라 하자. 1) 제약식 (6)에서 변수 x p f 1 , x p f 2 는 기간 p 뿐만 아니라 기간 p + 1 부터 기간 m 까지 모든 제약식에 속하고 있다. 여기서 우변을 더 증가시킬 여유가 있는 제약식들의 집합은 I= {t ∣ b_t < b_t }이다. 따라서 Δb_t = b_t = b_t라 할 때, 증가 가능한 Δb 는 Δb_q =min{Δb_t ∣ t∈I, t ≥ p }보다 커질 수는 없다. 따라서 Δb 의 최대값은 Δb_q 이다. 2) 가정으로부터 목적함수 값의 최대 증가비율 θ_p^* (f₁, f₂ )는 기간 p 에서 발생하므로, 제약식 (7)로부터 x ¯ p f 1 + x ¯ p f 2 = 1 이 성립한다. 따라서 t∈I, t ≥ p인 모든 제약식 t 에 포함된 a p f 1 x ¯ p f 1 + a p f 2 x ¯ p f 2 는 a p f 1 + a p f 2 − a p f 1 x ¯ p f 2 으로 표현된다. 여기서 변수 x ¯ p f 2 는 0 ≤ x ¯ p f 2 ≤ 1 이므로, x 가 최 적으로 유지되는 Δb 의 변동구간은 0 ≤ Δ b ≤ a p f 2 − a p f 1 이다. 따라서 Δb 의 최대값은 (a p f 2 − a p f 1)이다. 위 1)과 2) 로부터 증가 가능한 Δb 의 최대값은 정리와 같이 계산 된다. ■

다음은 정리 2 및 정리 3을 적용하여 문제 (P)의 최적 해를 구하는 해법이다. 여기서 목록 L^* 는 각 최적비율 목록 L _i^* 에 속한 모든 비율들의 집합이며, 비율크기의 비 증가순으로 다시 정리한 목록이다

해법

0. I = I = {1, 2, …, m }, L_i ← ∅, L _i^* ← ∅, J_i ← {1, …, k_i }, i∈I, L^*←∅, Δ b t = b t − ∑ i = 1 t ∑ j ∈ J i a ij, t∈I

다음으로 위 해법이 최악상황에서 최적해를 구하는데 소요되는 계산복잡도를 분석한다. 해법의 단계 0은 상 수회에 계산된다. 해법의 단계 1에서 문제의 모든 계수 들 a_ij 를 비감소순으로 정렬하는 데 ∑ i = 1 m O n i log n i ≤ O n log n 가 소요된다. 여기서 n 은 문제의 총 변수의 수 이다. 즉 n = ∑ i = 1 m n i 이다. 다음으로 최적비율 탐색해법 의 단계 0은 상수회에 계산된다. 최적비율 탐색해법의 단 계 1에서 모든 비율을 계산하는데 O (n_i²)의 계산이, 이를 비증가 순으로 정리하여 후보비율 목록 L _i 를 작성하는데 O (n_i² log n_i)의 계산이 소요된다. 최적비율 탐색해법의 주 회전단계 2, 3, 4는 각 상수회에 계산되고 최대 회전수는 목록 L _i 의 비율개수 O (n_i²) 이므로, 단계 2, 3, 4가 회전하 여 최적비율 목록 L _i^* 를 작성하는 데는 O (n_i²) 의 계산이 소요된다. 이상 최적비율 탐색해법의 각 단계로부터 최적 비율 목록 L _i^* 를 작성하는 데에는 최대 O (n_i² log n_i)의 계 산이 소요된다. 따라서 모든 L _i^* 로부터 목록 L^*를 작성하 는 데에 ∑ i = 1 m O n i 2 log n i ≤ O n 2 log n이 소요된다. 결국 해법의 단계 1에서 계수들을 정렬하는 데에 O (n log n) , 최적비율 탐색해법을 적용하여 목록 L^*를 작성하는 데에 O (n² log n)이므로, 단계 1의 최대 계산양은 O (n² log n)이 다. 다음으로 해법의 주 회전단계는 단계 2, 3, 4, 5, 6, 7 이다. 단계 2에서는 상수회의 계산이 소요된다. 단계 3에 서는 최대 O (m) 의 비교가 필요하다. 단계 4, 5, 6, 7에서 는 상수회의 계산이 소요된다. 목록 L^*의 최대 비율 개수 는 O (n²) 이므로 주 회전단계의 최대 회전수는 O (n²) 이 다. 따라서 주 회전단계에 소요되는 계산은 O (mn²) 이다. 이상으로부터 해법의 단계 1에서 O (n² log n) , 주 회전단 계에서 O (mn²) 이 소요되므로 제시한 해법의 계산 복잡 도는 max [O (n² log n), O (mn²) ]이 된다.

5.수치예제

다음과 같이 선수 제약을 갖는 다기간 선형계획 문제 에 해법을 적용하여 최적해를 구한다.

Maximize ∑ i = 1 3 ∑ j ∈ N i c ij x ij

subject to

∑ j ∈ N 1 a 1 j x 1 j ≤ 12 ,

∑ i = 1 2 ∑ j ∈ N i a ij x ij ≤ 22 ,

∑ i = 1 3 ∑ j ∈ N i a ij x ij ≤ 44 ,

∑ j ∈ N 1 x 2j = 1

∑ j ∈ N 3 x 3 j = 2 ,

0 ≤ x ij ≤ 1 , ∀ j ∈ N i , i ∈ I = 1 , 2 , 3 .

여기서, N₁ = {1, 2, 3, 4}, N₂ = {1, 2, 3, 4}, N₃ = {1, 2, 3, 4}, b₁ = 12 , b₂ = 22 , b₃ = 44 , k₁ = 2, k₂ = 1, k₃ = 2이다. 또한, 각 목적함수의 계수 c_ij , 제약식의 계수 a_ij 는 다음 표와 같다. Table 1

<1회>

0. I= {1, 2, 3}, L _i ← ∅, L _i^* ← ∅, i∈I , J₁ ← {1, 2} , J₂ ← {1} , J₃ ← {1, 2} , L^* ← ∅, Δb₁ = 6 , Δb₂ = 11, Δb₃ = 22 .

1. 최적비율 탐색해법을 적용하여 최적비율 목록인 L₁^* , L₂^* , L₃^* 를 작성한다. 먼저 첫 기간에 해당하는 최적비 율 목록 L₁^* 를 다음과 같이 작성한다.

(1회)

(1) L₁ = {θ₁ (1, 2) = 1.00, θ₁ (1, 3) = 0.80, θ₁ (2, 3) = 0.67, θ₁ (1, 4) = 0.63, θ₁ (2, 4) = 0.50, θ₁ (3, 4) = 0.33}

(2) θ₁ (1, 2) = 1.00 선택(f₁ = 1, f₂ = 2)

(3) 1 ∈J₁, 2∈J₁ 이므로 단계 4로 간다.

(4) L₁ ← L₁＼{θ₁ (1, 2)}, 단계 2로 간다.

(2회)

(2) θ₁ (1, 3) = 0.80 선택(f₁ = 1, f₂ = 3)

(3) 1 ∈J₁, 3 ∉J₁ 이므로 J₁ = {2, 3}, L₁^* = {θ₁ (1, 3)}, 단계 4로 간다.

(4) L₁ ← L₁＼{θ₁ (1, 3)}, 단계 2로 간다.

(3회)

(2) θ₁ (2, 3) = 0.67 선택(f₁ = 2, f₂ = 3)

(3) 2 ∈J₁, 3∈J₁ 이므로 단계 4로 간다.

(4) L₁ ← L₁＼{θ₁ (2, 3)}, 단계 2로 간다.

(4회)

(2) θ₁ (1, 4) = 0.63 선택(f₁ = 1 , f₂ = 4)

(3) 1 ∉J₁, 4 ∉J₁ 이므로 단계 4로 간다.

(4) L₁ ← L₁＼{θ₁ (1, 4)}, 단계 2로 간다.

(5회)

(2) θ₁ (2, 4) = 0.50 선택(f₁ = 2 , f₂ = 4)

(3) 2 ∈J₁, 4 ∉J₁ 이므로 J₁ = {3, 4}, L₁^* = {θ₁ (1, 3), θ₁ (2, 4)}, 단계 4로 간다.

(4) L₁ ← L₁＼{θ₁ (2, 4)}, 단계 2로 간다.

(6회)

(2) θ₁ (3,4) = 0.33 선택(f₁ = 3 , f₂ = 4)

(3) 3 ∈J₁, 4 ∈J₁ 이므로 단계 4로 간다.

(4) L₁ ← L₁＼{θ₁ (3, 4)}, L _i = ∅ 이므로 과정을 끝 낸다.

첫 기간에 해당하는 최적비율 목록 L₁^* 는 다음과 같 이 구해진다.

L₁^* = {θ₁ (1, 3), θ₁ (2, 4)}

마찬가지로, 다음 두 기간에 해당하는 최적비율 목 록도 다음과 같이 구해진다.

L₂^* = {θ₂ (1, 3), θ₂ (3, 4)}

L₃^* = {θ₃ (1, 3), θ₃ (2, 4)},

그리고 최종적으로 각 목록 L _i^* 에 있는 최적비율들을 비율크기의 비증가순으로 정리한 목록 L^* 는 다음과 같다.

2. 비율목록 L^* 에서 가장 큰 비율 θ₂ (1, 3) 을 선택한다 (p = 2 , f₁ = 1 , f₂ = 3).

3. 2 ∈I , Δb_q = m in {Δb₂ = 11, Δb₃ = 22} = 11 , q = 2

4. Δb_q (= 11) > a₂₃ = a₂₁ (= 4) , 단계 5로 간다.

5. Δb₂ = 11 = 4 = 7 , Δb₃ = 22 = 4 = 18 , J₂ = {3}, L^* ← L^*＼{θ₂ (1, 3)}, 단계 2로 간다.

<2회>

2. θ₁ (1, 3) 을 선택한다(p = 1, f₁ = 1, f₂ = 3).

3. 1 ∈I , Δb_q = m in {Δb₁ = 6, Δb₂ = 7, Δb₃ = 18} = 6 , q = 1

4. Δb_q (= 6) > a₁₃ = a₁₁ (= 5) , 단계 5로 간다.

5. Δb₁ = 6 = 5 = 1 , Δb₂ = 7 = 5 = 2 , Δb₃ = 18 = 5 = 13 , J₁ = {2, 3}, L^* ← L^*＼{θ₁ (1, 3)}, 단계 2로 간다.

<3회>

2. θ₃ (1, 3) 을 선택한다(p = 3 , f₁ = 1 , f₂ = 3).

3. 3 ∈I , Δb_q = m in {Δb₃ = 13} = 13 , q = 3

4. Δb_q (= 13) > a₃₃ = a₃₁ (= 7) , 단계 5로 간다.

5. Δb₃ = 13 = 7 = 6 , J₃ = {2, 3}, L^* ← L^*＼{θ₃ (1, 3)}, 단계 2로 간다.

<4회>

2. θ₂ (3, 4) 를 선택한다(p = 2 , f₁ = 3 , f₂ = 4).

3. 2 ∈I , Δb_q = m in {Δb₂ = 2, Δb₃ = 6} = 2 , q = 2

4. Δb_q (= 2) < x₂₄ = a₂₃ (= 6) , 단계 6으로 간다.

6. x₂₄ = 2/6 , x₂₃ = 1 = x₂₄ = 4/6 , J₂ = ∅, 6. x₂₄ = 2/6 , a₂₃ = 1 = x₂₄ = 4/6 , J₂ = ∅, q(= 2) < m이므로 단계 7로 간다.

7. I = {3}, Δb₃ = 6 = 2 = 4 , L^* ← L^*＼{θ₂ (3, 4)}, 단계 2로 간다.

<5회>

2. θ₁ (2, 4) 를 선택한다(p = 1 , f₁ = 2 , f₂ = 4).

3. 1 ∉I 이므로, 단계 2로 간다.

<6회>

2. θ₃ (2, 4) 를 선택한다(p = 3 , f₁ = 2 , f₂ = 4).

3. 3 ∈I , Δb_q = m in {Δb₃ = 4} = 4 , q = 3

4. Δb_q (= 4) < a₃₄ = a₃₂ (= 10) , 단계 6으로 간다.

6. x₃₄ = 4/10 , x₃₂ = 1 = x₃₄ = 6/10 , J₃ = {3} q(= 3) = m 이므로, x_ij = 1, j ∈ J _i , i∈I 로 설정하고 과정을 종료한다.

이상의 과정을 통해서 구해진 최적해는 다음과 같다.

6.결 론

본 연구에서는 선수제약을 가지는 다기간 0-1 배낭문 제를 새로이 정의하였다. 이 문제는 기존의 다기간 배낭 문제[2, 4]와 다중선택 제약 다기간 배낭문제[5]를 포함 하는 확장된 모형이다. 이 확장된 모형은 다기간 배낭문 제처럼 다기간에 걸친 자원배분을 통해 총 이익을 최대 화하는 작업들을 선택할 뿐만 아니라, 각 기간마다 선택 되어야 할 작업의 수를 임의의 여러 개로 조정할 수 있 는 모형이다.

본 논문에서는 이 확장된 모형이 선형계획으로 완화된 문제에 대해 연구하였다. 이 문제를 선수제약 다기간 선 형계획 배낭문제라 부른다. 이 선형계획 문제는 확장된 모형의 정수 최적해를 구하기 위한 분지한계법의 한계전 략으로 사용된다. 따라서 이 선형계획 문제의 최적해를 신속히 찾을 수 있는 효율적인 해법의 개발이 필요하다.

해법 개발을 위해 선수제약 다기간 선형계획 배낭문제 를 각각의 기간에 대응되는 여러 부문제로 분해하였다. 이 부문제는 선수제약을 갖는 이차원 선형계획 배낭문제 의 형태로 발생한다. 부문제가 갖는 최적기저 변화의 특 성을 정리하고, 이를 활용하여 문제의 다기간 제약구조가 갖는 자원 배분시의 분배특성을 분석함으로써 문제의 최 적해를 효율적으로 찾는 해법을 개발하였다. 해법의 계산 복잡도는 max[O (n² log n) , O (mn²) ]으로 분석되었다.