우린 언제나 그랬듯이 답을 찾아낼 것이다(일반화된 분지절단법)

일반화된 분지절단법이란 어떠한 정수계획법에도 쓸 수 있는 분지절단법을 말합니다.

저번에 썼던 포스트에서 정수계획법에 대한 간단한 설명과 기초 개념을 다뤘습니다.

그 후 정수계획법을 푸는 방법 중 하나인 분지절단법에 대해서 알아봤고 배낭문제에 적용하여 풀이를 해봤습니다.

 

그런데 생각해봅시다 저번에 풀었던 배낭문제는 결국 하냐 안하냐로 귀결되는 정수계획법의 한 분야인 0-1계획법 문제였습니다. 그러면 다른 정수계획법 문제에 분지절단법을 적용하려고 하면 어떻게 될까요??

 

저번에 다뤘던 배낭문제를 다시 꺼내봅시다.

여기서 분지절단법으로 풀때 X1을 분할 변수로 두고 0일 때와 1일 때로 두고 풀었습니다. 

이렇게 말이죠

 

그리고 쭉쭉 분할해서 다음과 같은 그림을 얻었습니다.

 

 

 

 

그러면 만약 문제가 0-1계획법 문제가 아니라 그냥 정수계획법문제면 처음 시작할 때 어떻게 분할할지도 막막합니다.

 

그래서 이번 포스트에서는 다른 정수형문제도 막힘없이 풀기 위해서 일반화된 분지절단법을 알아보도록 합시다.

 

 

기본적인 초반의 흐름은 0-1계획법에서 했던 내용과 같습니다.

 

처음엔 하한을 무한으로 둔다... 상한은 문제를 단체법으로 푼 뒤 나오는 값을 사용한다. 이렇게 말이죠

 

근대 분지에서 약간 틀립니다.

 

한번 보시죠 내용은 (박순달 저)경영과학 제 3판 민영사에서 가져왔습니다.

 

단계 2. 분지

(1) 최적해에서 정수가 아닌 변수를 선택한다.

(2) 원문제에 다음 제약식을 각각 추가한 두 개의 새로운 문제를 문제목록에 등록한다.

단계 3  탐색

문제목록에서 문제 하나를 선택한다. 만일 비어 있으면 끝난다.

 

---

여기서 분지를 잘봅시다. 저기서 원문제에 관해 제약식을 추가하여 두 개의 새로운 문제를 등록하는 과정은 0-1계획법 분지계획법 풀이에서 보았던 트리가 생성되는 과정입니다.

또한 일반화된 분지절단법의 경우 저 제약식을 원래 문제에 집어 넣어 풀이를 하게 됩니다.

그런데 잘생각해봅시다.

0-1계획법에서는 처음에 x1에 0과 1을 넣어 분지했죠?? 이렇게 말이에요

 

그런데 잘생각해보면 이것 또한 제약식을 추가한 것과 같습니다. 

 

그 다음 저 제약식을 포함한 두개의 자식 노드로 나뉜거죠

 

아하 그럼 이제 눈에 보입니다.

바로 본질적으로 0-1계획법 풀이와 달라지지 않았다는 것이죠

 

전혀 새로운게 아니라 제약식에 부등호가 추가되었을 뿐입니다.

 

이제 어떻게 돌아가는지 대충 보이시죠?

 

그러면 문제 하나 풀어봅시다.

먼저 단체법으로 위 식을 풀어보면 

 

 

	Z	X1	X2	X3	X4	solution
	1	0	0	1/4	3/2	75/4
X2	0	0	1	-3/4	-1/2	5/4
X1	0	1	0	-1/4	1/2	13/4

 

x1=13/4 , x2= 5/4 , x3=0, x4=0 그리고 최대값은 75/4입니다.

 

따라서 상한을 75/4=18.xxx로 설정할 수 있겠군요

 

그럼 먼저 간단하게 x1에 대해서 분지하도록 하고 기준을 3에 둡시다. 

 

일단 기준을 정했으면 제약식은 다음과 같습니다.

그 다음은?? 그냥 x1에 위 수식을 각각 대입하면됩니다

 

그러면 먼저 왼쪽 노드부터 생각해봅시다 

 

왼쪽 노드를 풀기 귀찮으니 단체법 계산기에 넣으면...

 

x1=3

x2=1.5

x3=0

x4=0.5    그리고 z값은 18이 되는군요

 

일단 이 해는 정수해가 아니므로 한번 더 분지시켜봅시다

 

왼쪽 자식노드를 x2에 대해서 기준값 1( 1은 0과 1 즉 2개를 내포하고 있죠?)에 관해서 분지하면

 

다음 왼쪽 노드를 계산기 넣고 돌려보면

 

x1=3

x2=1

x3=1

x4=1

Z=17 이 나옵니다

 

드디어 찾고 찾던 정수해 단! 하나가 나왔군요

일단 그러면 저 정수해를 기록해두고 하한을 17로 둡시다

 

다음 오른쪽도 돌려봐야죠?

 

오른쪽같은 경우는

x1=2.5

x2=2

x3=0

x4=1.5

z=16.5가 나옵니다

 

그런데 z값이 왼쪽에서 나온 하한인 17보다 작군요

 

그러면 더 이상 오른쪽 노드는 분지할 필요가 없습니다.

 

다음으로 다시 부모 노드로 돌아가서

 

이번엔 오른쪽 노드를 파해쳐봅시다

 

오른쪽노드의 해는 비가해 즉, 해를 구할 수 없다고 나옵니다.

 

그러면 현재까지 구한 정수해는 한개밖에 없죠??

그러면 이 문제의 해답은 

 

 

x1=3

x2=1

x3=1

x4=1 이며 Z=17 이 나옵니다

정리

 

 

이렇게 일반화된 분지한계법의 풀이는 살짝 더 복잡하지만 익숙해지면 정수계획은 문제없이 풀 수 있는 강력한 도구 중 하나입니다.