여러 문제를 정수계획법으로 고치는 방법에는 어떤 방법이 있을까요?

정수계획법은 특정 문제를 풀 때는 선형계획법보다 유용합니다.

 

집을 사냐 안사냐(0-1 계획법)

장난감을 몇개 살것인가(정수계획법)

 

그런데 정수계획법은 선형계획법에 속해 있는 한 분류이기 때문에 어떠한 대상에 대해서 수식으로 표현하려고하면 일단 선형계획법으로 표현하는게 훨씬 쉽습니다. 문제는 그러한 선형계획법으로 나타낸 수식을 어떻게 정수계획법으로 바꾸는지가 문제가 되죠

마치 초상화를 그릴때 선형계획법은 소묘와도 같으며 정수계획법은 그러한 소묘 위에 물감을 덧칠하는 수체화와 같습니다.

 

그러면 이번 이야기의 주제가 파악되셨나요?

바로 소묘 위에다 수체화를 덧칠하는 방법... 선형계획법을 정수계획법으로 바꾸는 방법에 대해서 알아봅시다.

 

먼저 몸풀이 예제 하나

 

O리온 사는 과자를 만드는 회사입니다.

이 회사에서 신제품 출시를 위해서 공장과 창고를 새로운 위치에 짓을려고 하려고합니다.

공장과 창고 후보지로는 부산과 강원도가 있습니다.

이때 조건이 있습니다.

1. 건설 예산은 100억원이 있습니다.

2. 창고는 최대 1개만 지을 수 있다고 합니다.

3. 한 지역에 공장을 하지 않는다면 그 지역에 창고는 필요 없다고 합니다.

이 때 이 문제를 어떻게 정수계획법으로 나타낼까요?

보기	계획	기대 이익(단위 : 억)	건설 비용(단위 : 억)
1	부산에 공장 짓기	90	60
2	강원도에 공장 짓기	50	30
3	부산에 창고 짓기	60	50
4	강원도에 창고 짓기	40	20

 

먼저 변수를 지정해 줍시다.

계획들 보기 순번대로 X1, X2, X3, X4로 배정해주면되는군요

 

다음은 목적함수를 구해야합니다.

기대 이익이 크면 클수록 좋으므로 다음 수식을 최대화하는게 목적이 되겠네요

 

최대화 : Z=90X1 + 50X2 + 60X3 + 40X4

 

다음으로는 제약 조건을 구해야합니다.

먼저 1. 에 대한 제약조건을 구해봅시다 이거는 건설 비용이 나와있으니 쉽게 구할 수 있습니다.

 

60X1 + 30X2 + 50X3 + 20X4 ≤ 100

 

양변을 10으로 나눠줍시다

 

6X1 + 3X2 + 5X3 + 2X4 ≤ 10

 

 

다음 조건 2. 를 생각해봅시다. 창고는 최대 1개만 지을 수 있으며 X3가 1이라는 뜻은 부산에 창고를 짓는다 X4가 1이라는 뜻은 강원도에 창고를 짓는다라는 뜻이므로 다음과 같이 조건을 나타낼 수 있습니다.

 

X3+X4 ≤ 1

 

마지막으로 3. 이 남았군요

 

잘 생각해봅시다 부산에 창고와 에 대해서 다음 표를 봅시다.

 

X1(부산에 공장을 짓는다)	X3(부산에 창고를 짓는다)
0	0
1	0
1	1

 

위 표를 보시면 X1 - X3할 때 항상 0보다 같거나 큰 값을 가진다는 걸 알 수 있습니다.

반대로 X3가 1이고 X1이 0인 경우만 음수 값을 가지네요

 

따라서 조건 3.을 표현하면 다음과 같습니다.

 

X1 - X3 ≥ 0 

X1 ≥ X3

 

이러한 방법을 강원도에도 적용시켜보면 

 

X2 ≥ X4

 

가 나옵니다.

 

따라서 위 수식을 정리하면 다음과 같습니다.

 

목적함수

최대화 : Z=90X1 + 50X2 + 60X3 + 40X4

 

제약조건

6X1 + 3X2 + 5X3 + 2X4 ≤ 10

X3+X4 ≤ 1

X1 ≥ X3

X2 ≥ X4

그리고 Xj 는 정수

(실수 값이 들어갈 수 있으니 정수 조건을 추가해줍니다)

 

 

 

 

자 이제 몸풀이가 끝났으니 본격적으로 시작해봅시다.

 

처음으로 알아볼 것은 제약조건에 OR이 들어간 경우입니다.

 

위 예제에서 제약 조건은 4개가 있었습니다.

 

제약조건

6X1 + 3X2 + 5X3 + 2X4 ≤ 10------1

X3+X4 ≤ 1--------------------------2

X1 ≥ X3 ----------------------------3

X2 ≥ X4 ----------------------------4

 

여기서 추가 조건으로 부산이나 강원도 둘 중 하나만 택해서 건설해야할 때 어떻게 수식을 수정해야할까요?

 

제약조건을 더 첨가해야할까요? 아니면 수식 수정을 해야할까요?

 

이런 문제를 Either-or constraints라 하며 이러한 제약은 생각보다 쉽게 수정이 가능합니다.

 

그 방법은 바로 추가 변수를 주는 방법입니다.

 

여기서 제약을 만족하려면 두 가지 새로운 변수를 도입해야하는데 먼저 무지막지하게 큰 수 M과 1과 0의 값만을 가지는 y라는 변수를 도입합니다.

 

그리고 다음과 같이 설정합니다.

 

My ≥ X3-X1 --------------------------------3

M(1-y) ≥ X4-X2 ----------------------------4

 

그러면 y가 만약 0이면 다음과 같이 되겠죠?

0 ≥ X3-X1 --------------------------------3

M ≥ X4-X2 --------------------------------4

여기서 M은 매우 큰 숫자이기 때문에 X4와 X2가 무슨 값이든 다 만족해버립니다.

즉 식 4의 경우는 필요없는 수식... 없는 수식과 마찬가지가 됩니다. 반대로 3번 수식은 처음 상태 그대로군요

 

이렇게 다시쓰면 다음과 같습니다.

목적함수

최대화 : Z=90X1 + 50X2 + 60X3 + 40X4

 

제약조건

6X1 + 3X2 + 5X3 + 2X4 ≤ 10

X3+X4 ≤ 1

My ≥ X3-X1

M(1-y) ≥ X4-X2

그리고 Xj 는 정수

y는 0 or 1

 

그런데 곰곰히 잘 생각해보면 이것을 일반화할 수 있지 않을까요??

 

그러니까 이러한 방법을 잘 이용하면 100개의 조건 중에서 10개나 20개 선택하는 것이 가능하지 않을까요?

 

그 방법은... 있습니다!

 

그러한 문제를 K out of N constraints라고 합니다.

 

조건이 10개중 3개를 선택한다면 다음과같이 나타낼 수 있습니다.

 

조건1

조건2

조건3

...

조건10

 

 

(Y1)조건1

(Y2)조건2

(Y3)조건3

...

(Y10)조건10

Yi는 0 or 1

 

 

이렇게 일반화를 하면 모양이 조금 안예뻐지긴 합니다. 그러면 다음으로 넘어가봅시다.

 

두번째로 알아볼 것은 초기 시작비용이 존재할 경우입니다.

 

만약 모 악덕 사체업자 너구리가 나오는 게임을 시작한다고 합시다

 

이 게임은 게임기가 필요합니다 그러면 게임을 하려면 게임기를 사야겠네요

 

즉 시도를 안하면 아무 비용도 없었던게 한다고 결정하면 비용이 생기게 됩니다.

 

요렇게 말이죠

수식으로 나타내면 다음과 같습니다.

 

 

 

그러면 이러한 문제를 어떻게 정수계획법으로 나타낼 수 있을까요?

 

이것도 간단하게 풀립니다.

 

바로 변수 y를 도입하는 것입니다.

 

 

그런데 y값은 여전히 조건문입니다.

이것을 어떻게 일반 제약 수식으로 바꿀 수 있을까요?

 

방법은 위에서 보던 M이라는 매우 큰 수를 도입하는것입니다.

 

 

이렇게되면 x가 0이면 y는 0 or 1의 값이 될 수 있으며 x가 1이면 y는 무조건 1이 되야합니다.

 

그런데 아직 문제가 남아있습니다. x가 0일 때 y는 1도 될 수 있기 때문입니다.

 

이러한 문제를 해결하기 위해선 상식문제 하나 풀어 봐야합니다.

 

과연 게임기를 안샀는데 게임을 살 필요가 있을까요 없을까요?

흠 수집마니아나 뭔가 꿍꿍이가 있는 사람이 아니면 게임기가 없는데 게임을 살 필요는 없겠죠?

그렇다면 게임기가 없을 때 게임이 있는 해는 고려하지 않아도 됩니다.

즉 다시 말하자면 x가 0일 때 y는 어떤 수가 되도 상관이 없다는 뜻이 됩니다.

 

이렇게 문제를 선형계획법으로 나타내고 그것을 정수계획법으로 바꾸는 방법도 알아봤습니다.

위의 방법을 잘 섞으면 못 나타낼 정수계획문제는 없다고 생각드네요!