Linear programming (LP) 의 정의와 활용방법

 

LP란 무엇인가?

 

 

LP란 Linear의 프로그래밍으로

Linear에서 최적해를 찾는 방법입니다.

 

그럼 Linear 는 무엇이냐?

바로 지난 번 말씀드렸던 도표 상 최하단에 있던

선형 가정입니다.

LP는 이 선형가정의 최적해를 찾는 방법인 셈이죠.

 

 

-덧-

 

Linear (선형가정) 이란?

상대없고 결정적이고 연속이고(소수점도 허용)  직선적인 x,y

(윗 범주의 특성을 다 갖추고 + 직선) 

 

 

 

이론적 고찰 (수식)

 

선형가정의 최적해를 도출하기 위해서는 

먼저 수식화 가정이 진행돼야 합니다.

 

예를 들어 볼까요?

2가지 제품 X1과 X2가 있습니다.

X1제품을 만드는데

배관재 12미터와 노동력 9시간 배터리 1개가 들고
수익은 제품 1개당 350만원 입니다.

 

반면 제품 X2를 만드는데는

배관재 16미터와 노동력 6시간 배터리 1개가 들고
수익은 제품 1개당 300만원 입니다.

 

우리 회사에서는 200개의 배터리를 활용할 수 있고

1566시간의 노동력을 제공할 수 있으며

2880미터의 배관제를 구매할 수 있습니다.

이 때 회사의 이득을 최대로 만드는 방법은 무엇일까요? 

 

LP는 바로 이런 여런 다른 조건 하에서

최적의 방법을 도출하는 방법입니다.

 

단, Linear (선형가정)이기 때문에

앞에서도 말했듯
상대없고 결정적이고 연속이고 직선적인

x,y 여야만 하겠죠?

 

 

최적해 도출 방법

 

그럼 어떻게 최적해를 찾을 수 있을까요?

가장 먼저 할 일은

(1) 목표를 세우고 의사결정요소를 파악한 후

제약조건을 설정하는 것 입니다.

 

풀어 말하면 어떤 목적하에 무엇을 결정하냐입니다.

단, 제약조건 안에서요.

 

(2) 다음은 (1)에서 만든 결정요소와 제약조건을 활용하여

최적의 값을 찾는 것입니다. (목표 달성을 위해)

이는 수식으로 이루어 지는데요.

 

위에 언급했던 예를 다시 활용해보죠.

위 예로 수식을 만들면 아래와 같습니다.

MAX : 350X1 + 300X2 (목적)

X1+X2 <= 200 (배터리)

9X1+X2 <=1566 (노동력)

12X1+16X2 <=2880 (배관재)

 

위 조건들을 모두 만족하는

X, Y 중 가장 높은 값을 찾으면

그 것이 답 즉, 최적해가 됩니다.

 

그림으로 보면 좀 더 이해가 편한데요.

각 직선이 위의 제약조건들을 나타내는 선이며

모든 직선에 포함되는 녹색 부분이

우리가 선택가능한 조건이 됩니다.

그리고 위 조건 중 가장 외곽에 위치한 점이

최적해가 됩니다.

 

 

 

왜 최 외곽이 최적해가 되는지는

위 그림을 참고하면 쉽습니다.

가장 많은 면적을 차지하는 위치가 최적해인데

가장 외곽에 위치한 점이 그 부분이기 때문이죠.

 

 

-덧-

 

위 그림을 참고로하면 LP의 몇가지 특징이 보이는데요.

1) 답이 여러 가지이거나, 없을 수도 있다.

2) x1, x2까지는 2차원에 표현이 되지만 3부터는 3차원에

4부터는 그림으로는 설명이 불가능 해진다.

 

 

 

실무 활용 방법 (엑셀 활용)

 

간단한 제약식만 사용되는 경우에는

직접 계산해 최적해를 찾을 수 있지만

사실 조금만 더 식이 복잡하고 많아져도

어려운 경우가 많습니다.

이때 주로 활용하는 툴이 엑셀입니다.

엑셀에 위 수식의 값을 넣어 계산하게 되는데요.

 

위 수식을 행렬로 정리한 모습

 

코딩을 조금 다뤘던 분들이라면 익숙한

위와 같은 행렬을 활용하게 됩니다.

우리가 엑셀에 입력하는 값이 위 행렬처럼 작용하여

엑셀에서 계산을 가능하게 해주는 거죠.

 

-덧-

 

행렬에 대해 더 궁금하신 분들은

제 블로그 경제수학에

정리되어 있는 부분을 참고하시기 바랍니다.

 

이제 실제로 적용하는 방법을 보겠습니다.

 

 

(1) 제약조건 입력 

 

위 예의 수식을 입력해야 하는데요.

사실상 컴퓨터가 인식할 수 있도록

아까 행렬에서 보여드렸던 값을 넣습니다.

 

-덧-

 

개인적으로 목적에는 빨간색을

최적해에는 노란색을 넣습니다.

 

 

 

(2) 함수설정

 

SUMPRODUCT를 사용합니다.

이 함수는 설정한 블록별로 곱하기 매칭을 시켜

더한 값을 표시해주는 함수입니다.

행렬 기능을 사용하기 유용한 함수입니다.

위 식에서는 SUMPRODUCT(B2:C2,$B$6:$C$6)

를 입력해 준 후 드래그 해서 주황 부분까지 내립니다.

 

-덧-

 

$표시를 해주지 않으면 드래그 시

참조영역이 아래로 내려가기 때문에

꼭 $표시를 해 주시기 바랍니다.

 

 

 

(3) 해 찾기 기능 추가

 

데이터에서 해 찾기를 찾을 수 없는 경우만 보시기 바랍니다.

먼저 좌측 하단 옵션으로 들어갑니다.

 

추가 기능을 누른 후 해 찾기를 찾아 추가합니다.

 

 

 

(4) 해찾기 실행

 

정상적으로 진행되었으면

데이터에서 해 찾기를 찾을 수 있습니다.

 

 

(5) 해 찾기 매개변수 설정

 

이제 매개변수를 설정할 차례입니다.

목표 값을 표시할 칸을 설정한 후

대상 값을 최대로 할지 최소로 할지 정합니다.

 

최적해를 찾아야 하는 칸을

변수 셀로 설정합니다.

 

아까 함수를 걸었던 제약 조건 칸을

제한 조건에 종속에 추가 시킵니다.

 

음이 아닌 수로 설정 후

해법 선택을 단순LP변경합니다.

 

해 찾기를 클릭합니다.

 

해 찾기 해 보존을 누른 후 확인 클릭

 

 

비어 있던 노랑, 주황, 빨강 영역이 채워집니다.

X1의 최적생산량은 122

X2의 최적생산량은 78

매출 최대값은 66100원이 되겠네요.

 

 

이상으로

Linear programming (LP) 의 정의와 활용방법

포스팅을 마칩니다.