비선형계획법 아시는구나! 겁.나.어.렵.습.니.다

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

 

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

 

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

 

 

 

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

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

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

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

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

 

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

 

(위 그래프 공유합니다 : 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 ... ) 제약조건이 걸려있는 경우에 관한 것이죠

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