선형과 선형계획, 간단하게 보자.

최근 명절을 맞이하여 푹 쉬었던 만큼, 보충 과외를 하느라 쉴틈이 없었다.

온라인 MOOC 강좌를 통해 LP model 학습을 한 적이 있었다. 

내가 정리하고자 하는 부분은 간단하게 선형계획(쌍대 미포함)을 왜 사용 하는지 설명하고자 한다.

솔직히 세부적인, 심화적인 내용을 원한다면 선형대수학 분야의 전문적인 강의를 통해 학습 하기를 바란다.

먼저 선형 계획을 논하기 이전에 선형(Linear)을 이해할 필요가 있다.

선형(Linear)은 직역하면 직선화하는 느낌인데, 이 직선이라는 것이 단순히 2차 평면()에 머무는 것이 아니라 고차원 공간()에 그려질 수 있음을 고려할 수 있다. 가장 핵심적인 것은 스칼라와 벡터를 이용하여 이러한 선을 찾는 것이 된다.

스칼라는 굳이 쉽게 말하자면 간단한 숫자다. 중등수학에서 부르는 상수정도로 볼 수도 있겠다.

여기서 벡터는 행렬을 이야기한다. 또, 열벡터와 행벡터를 나누어 부를 수 있으며 그 어원대로 행/열끼리 묶은 각각의 벡터(행렬)를 말한다. 예를 들어, 3*3행렬에 대하여 1*3열벡터를 3개 만들어 낼 수 있다. 

그런데 재미있는 것은, 이러한 부분벡터와 스칼라를 이용하여 결과벡터를 뽑아내고자 한다는 것이다.

아니 이게 무슨 소리인가 하면, 예를 들어 아래와 같은 행렬이 있다고 하자.

벡터 A는 위와 같이 정의해보자.

뭐 A를 다이어트 계획 행렬이라고 하자.

각각의 행벡터 원소에 굳이 의미를 부여하자면, 

[a1=> xx의 다이어트 완성], [a2=> ooo의 나도 몸짱 모델], [a3=> sss의 식이요법] 을 일정시간만큼씩 한달을 꼬박들여 다이어트를 했다고 하자.

이렇게 섭취를 하였을때 (이렇게 적게 먹고는 못산다. 치킨은 먹어줘야된다. 아마도)

어떤 다이어터 t 가 한달 뒤에 빠진 몸무게의 양이 아래와 같이 조사되었다고 하자.

LP 에서 우리는 벡터 A: 3가지 다이어트에 각각 들인 시간을 통해 실제 효과 벡터 Y의 값이 무관하지 않다고 본다.

다시말해, 각각의 행벡터 값이 일정한 효과를 지니고 있다고 생각할 수 있다.

자, 어떤 다이어트 방법이 가장 효과가 좋았을까? 어떤 다이어트 방법이 가장 무쓸모였을까?

이걸 알아보는 방법이 LP(Linear Programming)에서 선형계획 혹은 쌍대를 통한 해를 구하는 방법일 것이다. (이 포스팅에서는 쌍대를 다루지 않는다. 다만 간단히 적자면, minimize 혹은 maximize한 선형계획에 대해 쌍대는 maximize 혹은 minimize 한 결과(약:근사/강:같은)를 얻을 수 있다.)

이를 아래와 같이 표기할 수 있다.

행렬의 곱셈으로 각 x(1~3)들에 대한 식을 세우면 그들이 얼마의 값을 가지는지 유추할 수 있다.

이때, A 벡터(행렬)를 열벡터로 분해하면 각각의 열벡터들은 서로 다른 x와 곱으로 분리할 수 있다. 

다시말해서,

이렇게 각각의 열벡터들은 각 x와 곱형태로 나타나고, 이때 대수x들의 해를 구하려한다면 스칼라가 될 것이다. 그리고 지정된 구간에서의 해를 구하는 과정 중 하나가 선형계획이 될 수 있겠다.

참고 : 

K-MOOC : 강의 MATHEMATICAL FUNDAMENTALS FOR DATA SCIENCE 中 Linear algebra 2

IBM knowledge center : 선형계획https://www.ibm.com/support/knowledgecenter/ko/SSSA5P_12.7.1/ilog.odms.ide.help/OPL_Studio/opllanguser/topics/opl_languser_intro_lp.html