게임이론이란 게임을 하는 것을 말합니다!

여기서 게임이란 흔히 알고 있는 비디오 게임, 온라인 게임, 보드게임 등이 아니라 의사결정을 하는 상황을 게임, 정확히는 게임상황이라고 합니다.

게임이론에는 크게 협조적 게임이론과 비협조적 게임이론으로 나눠지는데 이 분야를 처음 접한 사람은 협조와 비협조의 어감 차이 때문에 착각하는 경우가 종종 있습니다.

협조적 게임이론은 참가하는 사람의 인간성이 좋아 다른 사람과 협조를 잘하는 게임이론이고 비협조적 게임이론은 매우 나쁜사람들이 참가하는 게임이론일까요??

게임이론의 전제조건이 하나 있습니다.

바로 참가하는 모든 사람들은 이성적이라는 것이죠 이 이성적이라는 것은 착하고 나쁘고를 떠나서 항상 합리적인 판단만한다는 것입니다. 

그렇다면 협조적과 비협조적이라는 것은 무엇일까요??

협조적 게임이론은 사람들이 강제가 아닌 자기의지로 구속력 있는 계약을 맺을 수 있는 상황을 분석합니다.

여기서 구속력 있는 계약이란 A와 B가 계약을 맺었는데 A가 그 계약을 깨버렸습니다!!

그 때 B는 C, D, E 등등 다른 사람한테 가서 호소하여 계약을 위반한 A를 처벌할 수 있는 게임이론이 바로 협조적 게임이론입니다.

비협조적 게임이론은 게임의 규칙이 허용하는 구속력 있는 계약은 맺을 수 있지만 게임의 규칙에 있지 않는 계약은 맺지 못합니다. 그래서 규칙에 있지 않은 계약을 맺은 경우 A가 계약 위반 했을 때 처벌할 수 없습니다.

먼저 이 포스트에서 주로 다루게 될 내용은 비협조적 게임이론입니다. 

몇가지 게임이론의 용어가 있는데 저기 위에 있는 문명 5 게임의 간디 짤방으로 이야기를 해보겠습니다.

플레이어 : 간디와 문명 5 게임을 하고 있는 여러분

전략집합 : 각 플레이어가 선택할 수 있는 전략 (간디의 경우 (돈받기, 선빵필승) 문명5의 플레이어(돈주기, 선빵필승))

보수 : 특정 전략을 취함으로써 얻을 수 있는 이익

그러면 이러한 게임을 다음과 같이 표로 나타낼 수 있습니다.

만약 자신이 돈을 주게 되고 간디도 순순히 돈을 받게 된다면 자신은 -5원 손해를 입고 간디는 5원을 얻습니다.

만약 자신이 돈을 주게 되는 상황에서 간디가 주먹을 날리면 돈도 뺏기고 치료비 때문에 -15원을 잃습니다 

그리고 간디는 해맑게 돈받을 준비를 하고 있는 상황에서 자신이 선빵을 치면 간디의 소지금을 털어 얻을 수 있고 간디는 치료비와 소지금을 -25원 잃습니다.

마지막으로 둘다 선빵을 때리면 둘다 중환자실에 가서 -20원씩 잃습니다.

이 상황에서는 과연 어떤 선택이 가장 최선일까요??

그런데 게임이론에서 중요한 사실하나 알고 계신가요??

바로 간디는 여러분이 무엇을 선택할지 알고 있습니다!!!

그러면 간디는 독심술사여서 무엇을 선택할지 알고 있는것일까요??

그런데 충격적인건 여러분 또한 간디가 무엇을 선택할지 알고 있습니다!!

어떻게 이런 상황이 가능할까요??

그것은 아까전 이야기했던 참가자는 모두 이성적이다! 라는 가정에 의한 것입니다.

이성적이면 어떻게 되는가? 간디는 여러분이 쓸 전략을 모두 알고 있고 여러분 또한 간디가 쓸 전략을 모두 알고 있습니다. 또한 간디는 여러분이 이성적이라는 것을 알고 있고 여러분 또한 간디가 이성적이라는 것을 알고 있습니다.

이것을 공통 지식(Common knowledge)라고 합니다.

그러면 서로 이성적인 것을 알고 이성에 의한 로지컬 띵킹으로 모든 전략에서 가장 자신의 이익이 최대화 되는 쪽으로 선택하겠죠?

위의 표를 다시 가져와 봅시다. 

이 행렬을 보수행렬이라고 하며 각 선택한 전략에 따른 이익(보수)를 보여주고 있습니다.

그러면 과연 이성적인 여러분과 간디는 어떤 전략을 취하게 될까요?

둘다 선빵 때리는것은 손해가 크니까 안하겠죠?

자 로지컬 띵킹을 해봅시다

여러분이 돈주기 전략을 택한다면 간디의 전략 돈받기를 할시 -5 , 선빵을 할 시 -15 해서 총 -20의 손해를 봅니다.

똑같이 여러분이 선빵 전략을 택한다면 간디의 전략 돈받기를 할 시 5, 선빵을 할 시 -20을해서 총 -15의 손해를 보는군요. 

따라서 여러분은 손해가 적은 선빵전략을 택하게 됩니다.

간디도 마찬가지입니다.

간디가 돈받기 전략을 택한다면 여러분이 전략 돈주기를 할시 5 , 선빵을 할 시 -25 해서 총 -20의 손해를 봅니다. 

마지막으로 간디가 선빵 전략을 택한다면 여러분이 전략 돈주기를 할시 5 , 선빵을 할 시 -20 해서 총 -15의 손해를 봅니다.

따라서 간디도 선빵전략을 택하게 되죠

이렇게 다른 전략에 비해서 가장 높은 보수를 보장하는 전략을 강우월전략이라고 합니다.

근대 어라??? 둘다 선빵을 때리는 건 손해가 극심한데 이성적으로 생각을 해도 결국 둘다 선빵을 때렸습니다.

이러한 상황을 죄수의 딜레마라고 합니다.

 이런 상황도 생각해봅시다. 

대기업 A와 중소기업 B가 다음과 같은 계약 상황에 놓여있다고 해봅시다.

중소기업의 파기와 합병 선택에 대해서 대기업은 거절이 받아들임 보다더 큰 이득을 줍니다

그리고 대기업 입장에서는 중소기업의 협력에 대해서 동일한 이득(10)을 얻을 수 있습니다.

그러면 대기업은 어찌되건 거절하는게 받아들이는 전략보다 이득이므로 거절할 준비를 합니다.

그러면 자동적으로 중소기업은 파기(1)를 선택하겠죠

그러면 둘다 (1, 1)의 이득을 얻습니다.

그런데 대기업이 "난 큰게 좋아" 하면서 받아들임을 선택한다고 중소기업에게 문서를 보내면 중소기업은 얼쑤 좋다! 하면서 협력을 선택하여 최종적으로는 (10, 2)를 얻게 됩니다.

이렇게 중소기업과 대기업 모두 중간의 (10,0)과 (10,2)에 관한 이득이 가장 큰 것을 알고 있으면서도 실제 전략은 이성에 의하여 대기업은 거절을하고 중소기업은 파기를 하게 됩니다. 이러한 대기업의 거절함 전략을 약우월전략이라고 합니다. 

이렇듯 약 우월전략에서는 협상이나 여러 변수에 의하여 항상 강우월전략처럼 가장 이득이 큰 전략을 택한다는 보장이 없습니다.

그런데 게임이론에서는 강우월전략이나 약우월전략이 없는 경우도 있습니다.

이럴 때는 어떻게 선택해야될까요?? 그냥 정신줄 놓고 찍신 강림하면 될까요?

흠.. ? 위 동영상에 내쉬균형의 대한 내용도 담고 있네요

근대 너무 간략하게 넘어가네요 그럼 다른 포스트에서 내쉬균형이라는 주제로 찾아오겠습니다.

비선형계획법은 목적함수나 제약조건을 선형으로 나타낼 수 없는 것을 말합니다.

선형계획법에선 심플렉스라는 강력한 방법을 이용해서 풀었습니다 그리고 정수계획법에서는 단체법은 쓸 수 없었으나 제약 완화를 통해서 다시 선형계획법으로 만들어 심플렉스를 적용하거나 특수한 기법을 통해 심플렉스를 적용하여 빠르게 정수해를 구할 수 있었죠.

그러나 비선형계획법에서는 이 좋은 심플렉스를 사용하지 못합니다.

예를들어 초밥먹은 갯수에 따라서 만족도가 위와 같다고 합시다

그러면 저 그래프가 최대화가 될 때 돈도 아끼고 만족도도 챙기고 일석이조겠죠??

비용은 한정되어 있는데 얼마나 초밥을 먹어야할까요?

여러가지 제약조건이 걸려 있는 상황에서는 저런 간단한 곡선조차 문제를 매우 풀지 못하게 만듭니다.

선형계획법에서는 제약조건이 많이 걸려있어도 연산 난이도만 올라가지 문제를 못 건드리는 수준까지는 아니였거든요

다른 예로 양에 따른 가격의 감소 문제도 비선형입니다.

(위 그래프 공유합니다 : www.geogebra.org/calculator/ftw7kytb)

만약 선박에 싣은 물건의 총량에 따라 운송비가 할인되면(규모의 경제) 싣는 량에 비래해서 총 비용은 위 그래프와 같습니다. 여기서는 싣는 량에 따라 3단계로 구분하였습니다.

1단계는 싣는량에 비례해서 5원

2단계는 싣는량에 비례해서 2원

3단계는 싣는량에 비례해서 0.5원

이것을 어떻게 풀면 최적으로 선박에 싣을 수 있는 량이나 비용을 구할 수 있을까요?

위의 그래프 개형을 보면 쉽게 예측은 가능하지만 이 또한 여러 제약조건이 덕지덕지 붙기 시작하면 답이 없어집니다.

예를 들어볼까요?

5개의 품목이 있는데 각각의 무게와 이득은 다음과 같습니다.

A = 10      2

B = 20      2.1

C = 25     1.8

D = 30     4

E = 35      3

(단위 Kg)

이것을 선박에 싣는다고 할 때 총 용량은 50Ton 까지 싣을 수 있으면 각각의 물건을 몇개 싣는게 가장 이득이 클까요?

목적은 이득을 가장 최대화하는 것.. 그러면 목적함수는 이렇게 나타낼 수 있겠네요

MAX : 2A+2.1B+1.8C+4D+3E - 운반비용 함수(A+B+C+D+E)

s.t.   : 10A+20B+25C+ 30D + 35E <=50000

흠 선형계획법으로 어떻게 풀지 감이 안잡히네요

그러면 한가지 생각을 해봅시다. 예로부터 복잡한 문제들의 해법을 구하기 위해서 먼저 시행해왔던 기본적인 규칙이 있습니다.

바로 규칙없이 그냥 심플하게 단순한것부터 보는 것입니다.

비선형계획법의 가장 단순한 영역은 목적함수만 생각할 때이며 이것을 제약조건이 없는 최적화라고 합니다.

위에서 다시 한계효용 곡선을 가져왔습니다.

목적함수만 두고 볼때 가장 이득을 볼 수 있는 지점은 명확합니다.

바로 그래프가 오목하게 올라와 있는 부분이죠

이처럼 볼록하거나 오목한 함수는 최대값과 최소값을 찾기가 쉽습니다

정확히는 지역 최소값이나 지역 최대값이 전역 최소값과 전역 최대값입니다.

아하 그러면 오목하거나 볼록한 함수는 공략할만하다는 것을 알았습니다.

이러한 것을 볼록 집합(혹은 오목 집합)이라고 합니다.

그런데 이런 말이 나올 수가 있습니다. "볼록집합만 가지고 뭘할 수 있겠어?? 그냥 진짜 특수한 경우만 쓸 수 있는게 아니야??"라고요

맞는 말이긴 합니다만 아래 예제를 봅시다

y=x는 실수 전체에서 오목집합입니다

이 y=sinx 그래프는 오목집합이 아닙니다.

그런데 정의역을 0~PI(3.14)까지로 줄이면

이 함수는 오목집합이 됩니다.

거기다 0~PI/2까지로 정의역을 줄여도 오목함수가 됩니다.

이제 이해가 되나요??

원래 목적함수가 오목집합이 아니더라도 제약조건에 의하여 오목집합이 될 수 있고 또 그게 아니라면 몇가지 조건을 완화하거나 추가함으로 오목집합으로 만들면되기 때문에 중요한 것입니다.

거기다 지금은 제약조건은 고려 안한다고 했죠?

위에서 설명을 명제으로 쓰면 다음과 같습니다.

먼저 지역 최대값을 만족하는 조건을 정의하면

그리고 지역 최대값이 전역 최대값으로 갈 수 있는 조건을 따져봅시다.

여기서 엄격한 오목함수라는 말이 나왔는데 자세한것은 책을 보시는게 좋고 일단 그냥 y=x는 엄격한 오목함수가 아니고 그냥 오목함수라는 것입니다.

이제 이 오목함수라는 개념을 적용해서 해를 구할 수 있습니다.

어떻게 구하냐고요?

생각해봅시다 오목집합의 경우는 위 조건에 의해서 몇가지 사실과 미적분학에서 기초지식 그리고 저희가 알고 있는 몇가지 상식만 가지고 있으면 어떻게 구하는지 이해가 가능합니다.

사실1 - 함수 F(x)의 경우 오목집합이면 지역 최대값이 전역최대값을 만족한다

사실2 - F(x)의 경우 미분한 그래프에서는 양의 기울기를 가지다 최대값에서 0을 찍고 음의 기울기를 가진다.

사실3 - 오목집합 혹은 볼록집합인 경우는 해가 양수가 나오는 구간과 음수가 나오는 구간이 있다.

사실4 - 중간값 정리에 의하여 양수가 나오는 구간과 음수가 나오는 구간 사이에 F'(x)의 해가 존재한다!!!

      -> 따라서 이 구간을 잘 살펴서 좁히면 F'(x)의 해 지점인 c를 찾을 수 있고 결국 최적화를 만족하는 곳은 c라는 것을 알 수 있습니다. 

이 방법을 바로 이분법(bisection method)라고 합니다.

위키피디아에서 사진을 퍼왔습니다.

이렇게 보면 함수 F(x)가 0이 되는 지점을 찾기 위해서 구간을 정해두고 계속 계산을 하여 중간값 정리를 응용하여

F(b)<0를 만족하는 것을 확인하고 있습니다.

물론 완전한 해를 보장하지는 못하지만 어느정도 구간은 추정할 수 있죠 마치 통계학에서 말하는 구간추청처럼 말이죠

이제 예제를 보면서 하는 방법을 알아봅시다.

일단 몇가지 정의를 해야할 변수가 있습니다.

마지막에 저만의 언어를 넣었습니다. 일일히 수식 입력하기 귀찮아서 제가 "x바"라고 하면 위에서 본 표현을 떠올려주시면 되겠습니다.

그러면 절차를 간단하게 소개를 해보면 오목집합인 경우

그러면 가장 먼저 해야될 일은 과연 위의 1.일까요?

흠.. 가장 먼저 해야될 일은 오목함수라는 것을 보이는 거겠죠?

이계도함수를 구해보면 -12(3x^2 + 5x^4) 가 되는군요

x가 실수 어떤 값을 넣어도 저 함수는 항상 음수값를 가지고 x에 0을 넣으면 함수 값은 0이 되니 오목함수라고 할 수 있습니다.

그 다음 대강 지점을 구해보죠

일단 원래 함수의 한 번 미분한 함수

12(1-x^3 -x^5)에서 x에다 간단하게 0을 넣어봅시다

그러면 -12가 나오네요

그리고  1을 넣으면 음수 나올거같은데...

-12정도 나오네요

그러면 0과 1 사이에 중간값정리의 의하여 해가 존재하는 건 확실합니다.

다음 0과 1 사이값인 0.5를 생각해봅시다.

0.5에서 기울기 값은 10.125가 나옵니다.

이 값은 0 이상의 양수이기 때문에 다시 이것을 x 언더로 둡시다.

그리고 또 사이의 값인 0.75를 구하고

다시 구해보면 4.0xxxx 정도가 나오고 다시 x 언더에 넣고 ... 무한 반복합니다. 원하는 만큼의 정밀도가 나올때까지.......

표로 표현하면 다음과 같습니다.

그러면 이제 어떻게 비선형에서 오목 또는 볼록집합일 경우 푸는 방법은 알았습니다.

하지만 아직 못한 이야기도 있습니다. 바로 변수가 여러개일 경우와 (x1, x2 ... ) 제약조건이 걸려있는 경우에 관한 것이죠

비선형계획법이 상당히 난해하다보니 너무 길어지네요 다른 포스트에서 이 다른 경우에 관해 다루겠습니다.

TTT란 특정 시점까지 시험한 총 시간을 뜻합니다.

예를들어 다음과 같이 자동차에 대한 고장 시점 자료가 있다고 합시다.

1---------X

2---------------------X

3--------------X

4------------------------------------------X

5------------------------------X

----------------------------------------------->시간

자동차 1이 고장날 시점이 5년이라고 한다면 이 때 TTT를 구해봅시다

5년 전까지는 5대 모두 잘 작동하고 있었으므로 TTT는 5*5=25가 됩니다.

자동차 2가 6.5년에 고장 났다고 한다면 이 때 TTT는 그 전까지 4대가 작동하고 있었으므로 다음과 같이 계산됩니다.

TTT(자동차 1 고장시점) + (6.5-5) *4 = 31

그러면 TTT가 왜 필요할까요?

TTT가 필요한 이유는 비모수적 방법 중 고장 분포를 잘 나타내는 방법중 하나이기 때문입니다.

예를들어 어떤 나라에 바이러스가 퍼져서 사망자가 늘어나고 있다고 해봅시다.

그러면 그 사망자에 대한 통계값이 나올텐데 어떤 분포로 나오는지 모르니 일단 데이터만 가지고 분석해보려고 합니다.

이 방법을 전문용어로 비모수적 방법이라고 합니다.

TTT는 이 비모수적 방법중 하나로 유용하게 쓰이기 때문에 사용하는데 보통 그냥 저 데이터만 사용하기 보다는 그래프로 나타내어 사용합니다. 이것을 TTT plot이라고 합니다.

일단 그래프로 나타내기 위해서 (x, y)의 값을 알아야하는데 좌표 수식 한개를 먼저 봅시다.

이것을 1번부품부터 해서 n번 부품까지 값을 차례대로 구해서 점을 찍는거죠

저 수식을 해석해보면 다음과 같습니다.

i/n 은 고장난 부품이 차지하는 비율입니다.

그리고 최종적으로는 n/n으록 가기 때문에 1이 됩니다.

TTT(i 부품 고장 시점 ) / TTT(모든 부품 고장 시점)는 전체 TTT시간(모든 부품이 고장나기까지 걸린 개별시간을 전부 합친값) 에서 특정 i부품까지 고장난 시간이 차지하는 비율입니다.

결론적으로 저 수식은 특정 부품이 파괴될 때까지 전체 부품과 시간에 대한 비율을 나타냅니다.

이제 실제 그래프로 나타내고 해석을 해봅시다.

위에서 언급한 자동차가 출고 후 고장될 때까지 걸린 개월 수가 다음과 같다고 합시다.

6.3 11.0 21.5 48.4 90.1 120.2 163.0 182.5 198.0 219.0

이때 TTT 그래프를 그리기 위해서 일단 고장 시점 막대 그래프를 한번 그려봅시다.

총 10개의 부품이 있고 최종 고장까지 걸린 개월 수는 219개월입니다.

이제 각 TTT지수를 구해봅시다.

이때 TTT plot을 그리면 다음과 같습니다.

이렇게 처음엔 고장률이 단위 TTT비율보다 부품의 고장개수 비율(i/n)이 많은 것을 알 수 있습니다.

좀더 알기 쉽게 하기 위해서 다음과 같이 수정해봅시다.

좀더 해석하기 쉽게 하기 위해서 y=x를 추가했습니다.

이제 확실히 보입니다. 

그래프 초반에는 단위 TTT비율보다 부품의 고장개수 비율(i/n) 이 더 많기 때문에 기울기가 작다가 점점 1:1 비율이 되는 순간 y=x의 기울기를 어느정도 유지하다 후반에는 TTT비율이 상승함으로 끝이납니다.

저 그래프의 고장률을 해석하면 초기에는 고장률이 점점 감소하다가 중반에는 서로 일정한 비율을 유지하고 종국에는 고장률이 다시 증가합니다.

이떄 고장률이 시간에 따라 증가하는 것을 증가형(IFR)이라 하고 i/n < TTT비율이 성립합니다.

다르게 시간에 따라 감소하는 것을 감소형(DER)라 하고 i/n > TTT비율이 성립합니다.

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

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

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

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

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

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

이렇게 말이죠

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

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

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

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

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

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

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

단계 2. 분지

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

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

단계 3  탐색

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

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

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

그런데 잘생각해봅시다.

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

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

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

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

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

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

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

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

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

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 이 나옵니다

정리

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

일반적으로 동적계획 문제는 최적 경로 찾기나 지정된 3곳 중에 금액이나 사람 등을 몇 개 투입해야 최대 이익이 될 수 있는지 등을 계산하였습니다.

그런데 만약 다음과 같은 경로 찾기 문제를 생각해봅시다

A   --   B    --   D

    ㄴ  C   ┘     

여기서 A에서 B와 C로 갈 수 있다고 할 때 그냥 거리가 짧은 쪽을 고르면 쉽게 풀리는 문제입니다.

그런데 만약 A에서 B와 C를 확률적으로 갈 수 있다고할 때  즉, 두 길이 50%와 50%확률로 갈 수 있다고 할 때 는 어떻게 될까요?

가장 기본적인 생각은 기댓값이라는 아이디어입니다.

로또복권 한장을 사면 기댓값이 22원 정도... 만원내기로 동전 던지기를 할 때 기댓값은 5천원...

이렇게 실제 실현된 값은 아니지만 기댓값이라는 개념으로 위의 문제에서 확률에 따른 길의 길이를 기댓값으로 수치화 할 수 있습니다. 따라서 이 기댓값을 가지고 동적계획법 계산이 가능해집니다.

예를 들어보죠

여러분은 아주 잘나가는 햄버거 요리사입니다.

 그런데 어느날 아주 유명한 미식가가 찾아와 햄버거 하나를 주문합니다.

이 미식가를 만족시키면 자신의 평판이 오를것이 분명하기 때문에 최대한 열심히 만들려고합니다.

그런데 미식가가 어떤 취향인지를 몰라서 일단 햄버거를 여러개 만들 생각도 해봅니다.

과연 이 미식가를 만족시킬 수 있을까요??

이때 확률론적 동적계획법을 사용하면 미식가를 최대한으로 만족하고 여러분의 평판과 임금이 오를 수 있습니다!! 

일단 저기서 추가적인 조건이 있습니다.

  1. 일단 여러분은 한번 요리를 시작하면 무조건 3천원이 소모되며 햄버거 하나당 추가적으로 1천원이 더 소모됩니다.

  2. 한번 요리를 시작하면 5분이 소요됩니다.

  3. 임의로 만든 햄버거 하나가 미식가를 만족시킬 확률은 50%이며 모든 햄버거가 입맛에 안맞으면 1.6만원의 손해를 입습니다.

  4. 미식가는 15분동안 기다려 줄 수 있습니다.

이때 어떻게하면 최소한의 소모로 미식가를 만족시킬 수 있을까요?

그러면 잘 생각해봅시다. 3개를 만들었는데 미식가가 만족하는 퀄리티의 햄버거가 2개라고한다면 의미가 있을까요?

미식가는 하나의 햄버거만 주문했기 때문에 1개 이상을 만족시키는 것은 의미가 없습니다.

그러면  목표는 최소한으로 만들어서 최대한 미식가를 만족시킬 수 있는 L값을 정하는 것입니다.

따라서 미식가가 만족할 확률은 다음과 같이 정해집니다.

이제 햄버거에 대한 기댓값을 정의해봤으니 동적계획법에서 중요한 3가지 요소 단계, 상태, 결정변수를 정의해 봅시다.

먼저 단계!

여기서는 단계란 미식가가 최대 15분을 기다려줄 수 있고 요리 한번하는데 5분이 소요되므로 총 3번 요리할 동안 기다려 줄 수 있습니다. 

따라서 단계는 3개가 있다고 볼 수 있습니다.

그러면 상태와 결정변수를 분석해봅시다.

결정변수는 뭘까요? 여기서 변경할 수 있는 숫자는 한번에 생산하는 햄버거의 갯수뿐이죠?

마지막으로 상태는 특정 단계에서 만족 했는가 안했는가 입니다.

그래야 만족하는 루트로 갈지 만족하지 못하는 루트로 갈지 정할 수 있거든요

그러면 이제 식을 정의해봅시다

한 단계당 무조건 요리를 해야하고 햄버거 수에 따라 비용이 달라지므로 다음과 같이 나타낼 수 있습니다.

3+Li

따라서 이 문제의 동적계획법 수식은 다음과 같습니다.

따라서 이것을 다시 동적계획법에서 풀듯이 뒤에서 부터 풀면 다음과 같습니다.

어때요 그냥 동적계획법과 다를바없이 쉽지 않나요?

운용과학(OR)에서 여러 모형들의 기원은 그렇게 뚜렷하지 않습니다. 선형계획법이나 정수계획법 수송문제 등등...

그런데 이 동적계획법은 창조자가 잘 알려져있습니다 바로 리처드 벨만이라는 사람으로 동적계획법이 다이나믹 프로그래밍이 된것도 이 사람이 다이나믹이라는 말이 멋있어서 붙였기 때문이라는 설이 있습니다.

따라서 다이나믹이라는 뜻도 동적이라는 뜻도 이 계획법과는 상관이 없는 뜻입니다.....

여하튼 이번 포스트에서는 동적계획법이 무엇이며 어떻게 쓰이는지 알아봅시다.

동적계획법은 최적의 해를 찾기 위해 이전에 구한 답을 이용하여 문제를 푸는 기술 혹은 방법을 말합니다.

이렇게 써두면 직관적으로 이해가 안갑니다

재미있는 예를 들어보죠

옛날 어느 중동의 나라에 한 청년이 살고 있었습니다. 청년은 골동품을 모으는 취미가 있었는데 어느날 골동품 시장에서 신비한 램프를 샀습니다. 그리고 램프를 보관하기 위해서 닦는 순간 램프의 요정이 나타난것입니다!

램프의 요정은 램프의 봉인을 풀어준 대가로 보물을 준다고 합니다.  요정은 세계에서 가장 진귀하다는 보물 1위부터 100위까지를 가지고 있는데 전부는 줄 수 없고 자신이랑 게임을 해서 한개만 받을 수 있다고 합니다.

게임은 요정이 보물 100개를 30초마다 하나씩 보여주는데 자신이 원하는 보물에서 멈춰! 라고 말하면 그 보물을 준다고 합니다. 다만 이미 지나간 보물은 받을 수 없고 당연히 앞으로 나올 보물 또한 받을 수 없습니다.

청년은 보물을 보자마자 요정이 지금까지 보여준 보물들의 상대적인 순위를 제대로 파악할 수 있다고 할 때 과연 보물을 몇번째 보여줄 때 쯤 멈추는게 현명할까요?? 

이 문제는 동적계획법 문제입니다. 최적의 해는 언제쯤 멈춰야 최대의 가치가 되는지 그리고 보물의 상대적인 순위를 파악할 수 있으므로 이전 구한 답을 이용해서 문제를 풀게 됩니다. 동적계획법의 정의에 딱 맞는 문제입니다.

참고로 위 문제의 정답은 약 33번째 쯤에 보물을 받는게 가장 가치가 높습니다.

이렇게 복잡한 문제도 풀 수 있는 동적계획법! 그런데 아직까지는 좀 아리송합니다. 특히 지금까지 선형계획법으로 잘 풀어왔는데 동적계획법이 무슨 소용이냐!라는 말이 있을 수 있습니다. 그래서 어떤 문제를 동적 계획법으로 풀 수 있는지 알아봅시다.

먼저 중요한 개념은 최적성의 원칙(principle of optimality)가 없으면 동적계획법으로 풀 수 없습니다!

그러면 최적성의 원칙이 무엇인지 알아야겠죠?

예를 들어 봅시다

여러분은 의사입니다. 근대 이웃마을에 위급한 환자가 있다고 연락이 와 급하게 가야합니다. 

이웃마을까지 가는데 다음과 같은 루트가 있다고 할 때 어떤 루트로 가야할까요?

이런 최단경로를 찾는 문제는 대표적인 동적계획법 문제입니다.

그런데 모든 최단경로 문제가 동적계획법으로 풀 수 있을까요?

만약 위 루트에서 A루트로 가면 길이 너무 험해서 포인트에서 환자까지 가는데 1시간이 걸립니다.

편한 길인 B루트로 가면 포인트에서 환자까지 가는데 30분이 걸립니다.

이렇게 같은 지점을 가는데 그 지점에서 다음 지점으로 이동할 때 걸리는 시간이 이전 루트에 영향을 받습니다.

이렇게 되면 최적성의 원칙이 깨졌다고 합니다.

그러면 이렇게 최적성의 원칙이 깨지면 왜 동적계획법으로 풀 수 없을까요?

핵심은 이전 답을 재활용한다는 것에 있습니다.

만약 이전 루트에 따라서 포인트에서 환자까지 가는 길에 영향을 준다면 의사 위치에서 포인트까지 가는 길이 짧은 루트는 아무 상관이 없습니다.

짧은 루트로 갔는데 오히려 포인트에서 환자까지 가는데 시간이 다른 루트에서 온 것보다 더 걸릴 수도 있는 것이지요

기본적으로 최단경로를 찾는 문제는 A 지점에서 (정확히는 단계 안의 노드 입니다만 단계라는 용어는 나중에 다시 설명하겠습니다.)  B 지점까지의 최단경로를 알면 A지점에서 C지점으로 가는데는 B에서 C로 가는 최단 경로만 구하면됩니다.

그렇게 되면 앞서 미리 구한 A에서 B까지 가는 최단 경로 답을 이용하여 그냥 더하면 되죠 

min(AB) + min(BC) = min(AC) 

하지만 최적성의 원칙이 깨지면 위와 수식의 방식을 쓸 수 없습니다.

AB로 가는 최단 경로가 BC의 최단 경로에 영향을 주기 때문에 AC의 최단 경로라는 것을 보장하지 못하거든요

그러면 이제 어떤 문제가 동적계획법으로 풀 수 있는지를 알았으니 특정 문제를 동적계획법으로 나타내는 방법을 알아봅시다.

문제를 정의하기 위해서 동적계획법만의 세 가지 중요 변수가 있습니다.  

단계(Stage) : i 

: 동적 계획법의 단계를 나타냅니다.

상태(state)  : s

: 특정 단계에서 선택할 수 있는 노드를 말합니다

결정변수(control) : x 

: 특정 단계에서 다음 단계로 가는 최적의 상태를 선택하는 것을 말합니다.

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

이렇게 개념만 보면 머리가 아프니 정리할겸 예제를 봅시다.

삼송(三松)이라는 기업은 여러개의 자회사들을 두고 있는 초거대 기업이있다고 합시다.

이 기업에서 분석하길 자회사 3곳(삼송전자, 삼송자동차, 삼송중공업)에 경영비상이 걸려 특별경영개선팀을 파견하려고 합니다.

특별경영개선팀은 총 5개의 그룹이 있으며 각 회사마다 파견되는 개선팀에 따라 이득이 다음과 같다고 할 때 어떻게 경영개선팀을 보내는게 최대한 이득을 볼 수 있을까요?

 (단위 : 억원)

여기서 전자와 중공업은 최대 팀을 2개 자동차는 3개를 보낸다는 정책이 있습니다.

일단 이문제는 목표가 명확합니다. 최대한 돈을 벌자!

그리고 자원은 특별경영개선팀 5그룹이 있습니다.

동적계획법 풀이 1단계는 단계, 상태, 결정 변수를 정하는 것입니다.

먼저 이 문제에서 결정 변수를 정의해보면 [특정 그룹에 얼마나 많은 개선팀을 파견할 것인가??]가 됩니다.

그리고 단계를 나눠보면 

삼송전자-> 삼송자동차 -> 삼송중공업

이렇게 3단계로 나뉠 수 있습니다.

각 단계에서 변화하는 요소는 과연 무엇일까요?

이게 동적계획법의 킵 포인트로 바로 개선팀의 남는 개수가 변화합니다.

정확히는 자원이 변화할 수도 있는 가능성을 따지는 겁니다.

다시 각 단계에 상태를 부여해봅시다.

 S1              S2                 S3

삼송전자-> 삼송자동차 -> 삼송중공업

각 상태에서의 팀의 개수는 다음과 같습니다.

S1 = 5

S2 = 5-X2 = S1 - X2 

S3 = 5-X2-X3 = S2 - X3

그 다음으로 해야할 것은 각 단계에 관해서 재귀적 관계를 정립하는 것입니다.

요런 관계

저 위 수식은 동적계획법에서 매우 중요하므로 동적계획법을 요령껏 잘 쓸려면 외워둡시다

이제 저 수식으로 문제를 푸는데 푸는 방법이 다소 특이(?)합니다. 

이런 미로 찾기 아시나요??

미로 찾기는 출구에서 이리저리 복잡하게 헤매면서 푸는 재미가 있죠

근대 이 미로찾기를 쉽고 간단하게 풀 수 있는 방법이 있습니다.

바로 출구부터 시작하는 것이지요

그러면 놀랍게 입구에서 시작하는 것보다 더 빠르게 풀 수 있답니다.

그 이유는 미로찾기 알고리즘에 있습니다. 

(시간 나시면 한번 보시는걸 추천합니다 동적계획법으로 미로찾는 알고리즘입니다)

즉 출발 지점에서 부터 진행하지 않고 출구지점에서 부터 진행하자!! 이게 동적 알고리즘의 핵심입니다.

그러면 다시 삼송 기업의 회생(?) 팀 파견 문제로 돌아가봅시다

아까 본 재귀 수식에 i=3일 때를 넣습니다. 즉 마지막 단계에서 수식은 시작합니다.

그러면 4단계가 없으므로 자동적으로 3단계까지 누적이득과 3단계에서의 이득은 같게 됩니다

좀 더 식을 전개하면

이렇게 쓸 수 있습니다.

그러면 각 식마다 키포인트가 되는건 

이것을 구하는게 됩니다.

그러면 저 수식이 없는 단계는 몇단계였죠?? 그렇습니다 마지막 단계인 3단계가 없죠

그러면 3단계부터 상태에 따른 이득을 표로 나타내면 다음과 같습니다.

1단계에서 S1=5라고 위에서 언급했으므로 상태가 5일때만 계산해주면 됩니다

따라서 파견은

삼송전자, 삼송자동차, 삼송중공업 순서로

0개, 3개, 2개팀을 파견하던지

2개, 2개, 1개팀을 파견하는 것이 최적파견이 됩니다.

동적계획법은 문제에 따라서 약간의 변형이 필요할 수 있습니다 

다른 포스트에서 유명한 문제인 배낭 문제를 동적계획법으로 풀어보고 비교하면서 알아보면 동적계획법 풀이에 대한  좋은 시각을 가질 수 있습니다. 

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

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

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

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

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

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

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

먼저 몸풀이 예제 하나

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

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

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

이때 조건이 있습니다.

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

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

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

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

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

계획들 보기 순번대로 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보다 같거나 큰 값을 가진다는 걸 알 수 있습니다.

반대로 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는 어떤 수가 되도 상관이 없다는 뜻이 됩니다.

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

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

정수계획법은 간단히 말하자면 선형계획법에서 정수해만을 인정하는 경우를 말합니다.

그래서 식은 선형계획법 식과 다름이 없습니다.

단지 제약이 해가 정수여야 한다는 것입니다.

그러면 이런걸 어디다 써먹을까요? 

바로 결정 문제에서 많이 쓰입니다. 서울에 집을 5채를 사겠다고 하지 4.3채를 사겠다고 하지 않잖아요

그런데 이러한 정수계획법에서 일부는 정수 해가 나오고 일부는 실수 해가 나올 수 있는데 이것을 혼합정수계획법(MIP)라고 합니다.

정수계획법에서는 이 정수라는 놈 때문에 선형계획법에서 편리하게 사용했던 단체법을 사용할 수가 없습니다.

그래서 정수계획법에서는 각 문제에 따라 알맞은 계산방법이나 근사해를 구하는 발견적 기법 즉, 휴라스틱을 사용합니다.

정수계획법 문제 예를 봅시다

많이들 들어본 배낭문제가 그 예중 하나입니다.

재미있게 보셨나요?

도둑은 결국 자전거만 끌고 집에 가는군요

영상에서는 욕심쟁이 알고리즘이 나왔지만 이거는 나중에 알아보도록 합시다.

이처럼 도둑도 포기하게 만든 배낭문제! 쉬워보이지만 깊게 파고들면 매우 복잡한 문제입니다.

예시를 들기 위해 위에서 나온 물품의 가치는 다음과 같다고 합시다.

가방에는 최대 20KG까지 들어갈 수 있으므로 위 문제를 수식으로 나타내면 다음과 같습니다.

여기서 X1이나 X2가 0.5와 같은 값을 가질 수 있을까요?

그러면 가장 가치있는 자전거를 0.5개.... 즉 반토막을 내서 가져가면 가치가 50만원일까요?

이렇게 가져가냐 안가져가냐를 따지는 문제... 더 포괄해서 하는가 않하는가를 따지는 문제를 0-1계획법이라고 합니다. 

그러면 정수계획법의 대략적인 문제의 형태가 보이기 시작합니다.

그러면 이제 이 문제를 해결할 수 있는 해법에 대해 토의하기 

이러한 정수계획법의 휴라스틱 해법으로는 두가지가 있습니다.

절단평면법

분지한계법

이 두가지 방법을 모두 설명하려고하면 분량이 매우 많기 때문에 절단평면법은 다른 포스터에서 다뤄보기로 하고 이 포스터에서는 분지한계법을 알아보도록 합시다.

그러면 차근차근 해법을 살펴보도록 합시다.

 *분지한계법(Branch-and-bound technique)

이 방법은 모든 가능해를 계산하는 열거식의 일종입니다.

모든 해를 계산하는게 바보같고 택틱컬하지 않다고요?

아뇨 모든 가능한 방법을 검토해보는건 100% 가장 확실한 방법입니다.

단지 시간이 조금 오래 걸릴뿐이죠..

분지한계법은 쪼개서 정복하는 알고리즘입니다. 큰 해영역에서 진짜 이 영역은 아무리 봐도 아니다싶은 부분은 잘라내고 남은 영역에서 탐색하고 또 잘라내고 탐색하는것을 반복하는거죠.

따라서 분지한계법은 이진트리의 형태를 띄고 있습니다.

대강 이런 느낌...

그리고 또 중요한건 탐색하면서 해의 상한과 하한을 정한다는 특이한 점이 있습니다.

이거는 지금 설명하면 이해가 잘안될 수 있으니 예를 보고 갑니다.

실제 알고리즘은 3단계로 간단한 편입니다. 

분지 -> 한계설정 -> 살펴보기 -> 분지 -> 한계설정 -> 살펴보기 .... 

위 배낭문제를 예로 들어봅시다.

먼저 위 식에서 수정해야할 점은 해가 정수라는 조건을 없애는 것입니다.

더 정확히는 해가 0~1까지로 제한합니다.

이렇게 해의 조건을 완화하는 것을 Relaxation이라 하는데 조건을 완화함으로 더 쉽게 문제를 풀 수 있습니다.

위 수식을 제약조건을 완화하여 다시쓰면 다음과 같습니다.

다음 해야할 것은 위 수식을 일단 단체법으로 풀어봐야합니다.

풀면 최적해는 (0, 1, 0, 0.4)로 나오며 값은 90이 되는데 이 90이라는 값이 바로 앞으로 풀면서 나올 모든 값들의 상한이 됩니다.

왜냐하면 정수해는 실수해보다 값이 반드시 같거나 작기 때문입니다.

비유를 하자면... 만약 자동차와 비행기가 같은 목적지로 간다고 생각해봅시다. 비행기는 밑에 건물이 있던 없던 쌩하고 목표까지 날아갈 수 있는데 자동차는 도로나 여러 신호를 봐가면서 가야하기 떄문에 훨씬 시간이 오래 걸립니다.

이때 공중을 아무 제약조건도 없는 상황 그리고 도로나 여러 신호상황을 정수 제약조건으로 봐도 무방합니다.

그리고 목적지까지 가는데 걸리는 시간이 바로 해의 값이고요

정리하면 다음과 같습니다.

IP 문제의 정수해의 Z값 =< IP 문제의 완화상태 실수해의 Z값 

그러면 상한이 90이라고 설정하고 다음할 작업은 분할을 실행할 변수를 선택하는 것입니다.

어떤 변수를 선택할지에 대해서 최적화된 방법이 있습니다만 여기서는 그냥 X1 , X2, X3... 이렇게 숫자 순서대로 합시다

그러면 X1을 어떻게하냐... 바로 1과 0을 대입합니다! 

그러면 위 이진 트리처럼 X1에 대해서 두개의 자식 노드가 생성됩니다.

다음 위 자식노드의 수식을 단체법을 이용하여 값을 구해줍니다. 

왼쪽 자식 노드

해 (1, 0, 0.4, 0)

값 90

오른쪽 자식 노드

해 ( 1, 0 , 0.2 , 0)

해 70

둘 다 정수해가 아니군요 따라서 하한을 설정할 수 없습니다.

일단 상한은 그대로 90입니다.

일단 둘다 분지를 해야하는데 왼쪽부터 분지해봅시다.

X2가 0과 1에 대해서 분지하면 다음과 같습니다.

이제 한눈에 봐도 쉽게 풀릴 정도로 수식이 나왔습니다.

일단 왼쪽 자식 노드를 살펴보면...

해는 (0, 0.8) 즉 (0,0,0,0.8)이며 값은 80입니다.

그런데 잘생각해보면 저런 문제는 그냥 눈으로 쓱 봐도 풀 수 있지 않나요?

딱봐도 저 문제의 정수해는 X3=1일 때 값이 50이라는 것을 알 수 있습니다.

원래 저 노드도 실수해가 나왔기 때문에 X3에 대해서 분지해야되지만 너무 많이 내려가네요 이쯤에서 그냥 눈으로 쓱 보고 풀 수 있으니 정수해 하나 구했다고 칩시다. 문제 잘못골랐네여

그래서 꼼수(?)를 합의봤다고 치고 정수해 (0, 0, 1, 0)을 얻었습니다. 이 해의 값은 50이죠

오른쪽도 마찬가지로 제약조건을 만족하는 정수해는 없으므로 (0, 1, 0, 0)을 얻었고 해의 값은 50입니다.

원래라면 왼쪽 오른쪽 정수해가 나올 때까지 분지해야합니다......

그러면 이제 정수해에 의해서 하한이 정해집니다.

상한 : 90

하한 : 50 (0,0,1,0), (0, 1, 0, 0)

다음은 X1=1일 때 X2에 대해서 분지해봅시다.

이번에도 두 자식노드 전부다 실수해기 때문에 분지가 되는군요......

그러면 오른쪽 노드만 분지하고 왼쪽은 암산으로 풉시다.

왼쪽 노드의 정수해를 구해보면 (1, 0, 0, 0)으로 값은 5가 됩니다. 이 값은 하한으로 설정해둔 50보다 작으므로 더 이상 분지할 필요가 없습니다.

반면 오른쪽 노드의 경우는 해가 (1, 1, 0, 0.2)가 나오며 이 값은 75가 됩니다.

따라서 상한과 하한 사이에 있으므로 이 노드를 한번 더 X3에 대해서 분지해 줍시다.

왼쪽은 X4가 0.2일 경우 해는 (1,1,0,0.2) 값은 75가 됩니다. 따라서 X4에 대해서 한번더 분지해줘야합니다........

오른쪽에서는  X4의 해가 0보다 같거나 커야하는데 위반하므로 해를 구할 수 없습니다.

따라서 오른쪽 노드는 더이상 분지하지 않습니다.

따라서 왼쪽 노드를 X4에 대해서 분지하면

위 그림과 같이 나오며 이 때 오른쪽 노드의 경우는 상항을 벗어났으므로 탈락

그리고 왼쪽 노드는 범위 안에 있으면서 하한값보다 높기 때문에 해 (1,1,0,0)이 최적해가 되며 그 값은 55입니다...

정리하면 

처음엔 정수해 문제를 실수해로 완화하고 단체법으로 풀기 여기서 정수해가 나오면 그걸로 사용합니다.

이때 처음 나온 실수해의 값 Z가 상한이되며 하한은 -oo입니다.

다음엔 특정 변수를 분지하기 

분지한 변수를 다시 단체법으로 풀고 정수해면 하한으로 설정

.... 이 작업의 반복이 바로 분지한계법입니다.

지금까지 분지한 그림

사실 분지한계법의 풀이는 이진 트리 형태를 띄고 있기 때문에 더 빨리 해를 찾을 수 있는 몇가지 수법이 존재합니다. 그 수법에 대해서는 언젠간 다른 포스터에서 다루기로 해봅시다.

카이제곱 적합도 검정이란 검증량 Q 값이 카이제곱 분포를 따른다는 뜻입니다.

먼저 적합도 검정에 대해 쉽게 말하자면... 모나미양은 볼펜을 만드는 회사에서 품질관리를 하고있습니다. 회사에서 새로운 신제품을 출시했는데 이 제품이 고장이 너무 많이 생긴다는 클레임이 여러 곳에서 들어왔습니다. 그래서 모나미양은 제품 출시부터 고장날 때까지의 시간 표본들을 수집하여 분석해봤더니 이 고장 표본들이 지수분포를 따르는것같습니다. 이 때 그러면 모나미양은 고장분포를 지수분포라고 논리적으로 상사에게 보고할 수 있을까요? 무엇을 근거로 보고를 할까요? 이 때 모나미양에게 필요한 통계학 도구가 바로 카이제곱 적합도 검정입니다. 표본을 구했을 때 이 표본은 어떠한 분포로부터 나왔을 겁니다. 지수분포, 와이블 분포, 포아송 분포 등등.. 그런데 그 분포가 뭔지 모르니까 카이제곱 정규성 검정으로 처음에 생각한 표본이 맞는지 아닌지 따져볼 수 있습니다.

그러면 검정량 Q는 뭐고 어떻게 구하고 카이제곱 분포를 따른다는 그 의미는 뭘까요??

먼저 검정량 Q에 관한 중요한 정리가 있습니다.

실제 증명은 limiting probability지식을 요구하기 때문에 증명하지 않고 일단 요것이 이렇다는 것말 알아두면 됩니다.

그러면 저 정리를 분석해봅시다.

여기서 X1, X2... 은 관측도수입니다.

예를들어 주사위를 40번 던져서 눈이 1이 나온게  8번이라고 한다면 X1은 8이 됩니다.

또한 n은 시행 횟수가 됩니다. 마지막으로 P1은 주사위 눈이 1이 나올 확률 즉, 1/6이 되겠네요

그러면 당연히 n*P1은 주사위 눈이 1이 나올 기댓값 n*P2는 주사위 눈이 2가 나올 기댓값 이렇게 됩니다.

확장해서 X1-n*P1 의 의미는 실제 관측도수를 기댓값으로 빼버린 것이지요

그러면 무엇을 얻을 수 있을까요?

바로 기댓값에서 얼마나 엇나났는지를 확인할 수 있습니다. 여기서 제곱을 해준것은 음수도 나올 수 있기 때문에 제곱을 해준것이며 마지막 기댓값으로 나눠준 것은 이 엇나감이 기댓값과 비례해서 어느정도 크기로 차이가 나는지 나타냅니다.

근대 여기서 중요한게 있습니다. 바로 마지막 점근적으로 자유도가 K-1인 카이제곱분포를 따른다.. 이 뜻은 n이 작으면  조금 안맞지만 n이 커질수록 카이제곱 분포를 따른다는게 됩니다.

그러면 그 엇나감이 모인 Q라는 검증량은 무엇을 의미할까요?

이 검증량 Q를 이해하기 위해서 예를 들어봅시다. 어떤 지역에서 60일 동안 도난 사건을 관측했더니 다음과 같은 결과를 보입니다.

이때 하루에 발생하는 도난건수가 포아송분포를 따르는지 검증해봅시다.

이 문제에선 포아송 분포라는 가정을 세웠는데 람다 값을 모르기 때문에 도난건수가 발생할 확률을 구할 수 없습니다. 따라서 최대우도함수를 사용하여 위에 자료를 토대로 람다를 구하여 확률을 추정을 해봅시다.

여기서 P3까지만 계산했는데 외냐하면 3회 이상부터는 값이 너무 작아서 2회 이상부터는 전부 합쳐버렸습니다.

그러면 Q값까지 구해졌습니다.

여기서 잘 생각해봅시다

만약 ... 만약에 Xi값과 기댓값인 nPi 값이 모든 i에 대해서 같으면 Q값은 0이 나오겠죠?

다르게 Xi값과 기댓값인 nPi 값이 모든 i에 대해서 매우 어긋나있으면 Q 값은 자연스럽게 큰값이 나옵니다.

그런데 더 잘생각해보면 애초에 저 위에 최대우도함수로 람다를 구할때도 확률을 구할 때도 전부 포아송 분포라는 근거로 계산했습니다.

이제 이해가 되나요? 어떠한 분포라는 것을 근거로 Q값을 구했는데 Q값이 크다면 근거 했던 분포가 틀리다는게 됩니다.

근대 여기서 한가지 의문점이 남네요 바로 Q값이 크다는 기준이 없습니다. 무엇을 기준으로 틀리다는걸 말할 수 있을까요?

여기서 문제를 다시 써야합니다.

다시 쓴 문제

이때 하루에 발생하는 도난건수가 포아송분포를 따르는지 유의수준 5%로 검증해봅시다.

자 여기서 유의수준이 등장했습니다.

그러면 먼저 도난건수를 X라 하면 귀무가설과 대립가설부터 정의합니다.

H0 : X는 포아송분포를 따른다.

H1 : X는 포아송분포를 따르지 않는다.

그러면 위에서 구한 Q값은 카이제곱분포를 따른다고 했죠?

그러면 범주를 3개(0회, 1회, 2회이상)로 나눴으므로 k=3 그러면 k-1이 자유도니까 2가 되야겠죠?? 근대 문제가 있습니다. 위에서 최대우도함수를 사용했다는 거죠 이 뜻은 데이터로부터 파라메터를 추정해버렸다는 뜻이 되며 추가적으로 자유도 1을 깍아야합니다. 따라서 최종적으로 k-1-1=1이 자유도가 됩니다.

그러면 유의수준 0.05로 자유도가 1인 카이제곱 분포를 계산해본 결과 3.838이 나오네요

이 유의수준의  뜻은 저 위에 도난사건의 관찰이 극단적으로 나올 확률을 따지는 겁니다.

여기서 극단적으로 나왔다는 것은 도난사건이 관찰 60일까지 일어나지 않았다던지 매일 빠짐없이 도난 사건이 일어났다던지 그런 경우를 말하는 거죠

위에서 구한 Q값이 극단적으로 나올 확률은 약 28%정도가 되네요

그러면 상식적으로 생각해서 관찰을 60번이나 했는데 이 관찰값이 극단적으로 나올 경우가 더 많을까요 아니면 극단적으로 나오지 않을 경우가 더 많을까요??

당연히 극단적으로 나오지 않을 경우가 더 많을겁니다. 따라서 Q값이 3.838보다 작다는 것은 극단적으로 나올 확률이 5%라고 했을 때 극단적으로 나올 확률이 28%보다 5%를 택하는게 더 합리적이므로 가설 H0 즉, "X는 포아송분포를 따른다."를 택할 수 있습니다.

먼저 최대우도추정에 대해 이해하려면 우도의 개념을 알아야합니다.

 우도(Likelihood) = 가능도

우도의 개념은 책에서 나온 딱딱한 정의로는 머리속에 잘 넣어지지 않습니다.

실제로 복잡한 개념이기 때문에 예를 들어 설명하는게 훨씬 좋습니다.

장난꾸러기 짱구는 장난감을 부수는데 천부적인 재능이 있습니다 말 그대로 파괴왕이죠

어느날 짱구 아빠는 말성쟁이 짱구가 장난감을 파괴하는데 걸리는 시간을 알아보기 위해 짱구에게 장난감 20개를 주었습니다. 그리고 장난감의 생존(?) 시간을 측정했고 그 결과는 다음과 같습니다.

이때 짱구 아빠는 과연 짱구가 장난감을 파.괴.하.는 평균 시간을 구할 수 있을까요?

짱구 아빠의 고민을 덜어주기 위해서 사용되는게 우도함수입니다.

만약 짱구의 장난감 파괴확률이 지수분포를 따른다고 하면 우도함수는 이렇게 적을 수 있습니다.

지수분포에서 중요한 인수인 λ를 모르지만 일단 우도함수 λ에 아무 값이나 일단 넣어봅니다 그러면 신기하게 우도함수의 값이 구해지는데 이 값의 정체는 바로 가능성입니다.  바로 지수분포에서 인수 λ가 특정 값일 때 저 위의 파괴 시간들이 나올 가능성을 나타내는거죠 매우 중요하면서 심오한 개념입니다.

여기까지 이해하셨으면 드디어 최대우도함수의 개념을 이해할 수 있습니다. 위에서 보다 싶이 지수분포의 우도함수 값은 λ에 의해 결정됩니다. 그러면 λ값을 계속 바꿔보면 가능성이 최대가 되는 λ를 구할 수 있지 않을까요??

이 개념이 바로 최대우도함수의 핵심입니다.

그리고 이때 편미분의 개념이 사용됩니다.

생각해봅시다 만약 평균 파괴시간 λ값이 10이라고 하면 λ가 10에서 멀어지면 멀어질수록 저 측정결과 값들이 나올 가능성이 낮아지겠죠? 그리고 10에 가까우면 가까울수록 가능성을 커지고요

그러면 우도함수 자체는 극댓값 하나뿐인 함수가 됩니다.  

따라서 λ에 대해 편미분을 하고 그냥 0에 맞추는 λ값을 찾으면 그게 우도함수가 극댓값이 되는 λ값이란소리죠

위에서 우도함수에서 로그를 취해주는 이유는 그게 훨씬 계산이 편리하기 때문입니다.

그러면 이참에 짱구의 평균 장난감 파괴시간을 알아내어 짱구 아빠의 고민을 풀어주도록 합시다.

따라서 짱구는 장난감 한 개 파괴하는데 평균 101.15시간이 걸린다는 것을 알 수 있습니다.