선형계획법

선형계획법이란

 

선형계획법 (리니어 프로그래밍(Linear Programming))

선형계획법은 최적화이론의 한 분야입니다. 최적화이론은 최소의 비용과 노력으로 가장 적절한 것(최적)을 찾아내는 방법을 뜻합니다. (최적선형은 결국 선형계획법을 뜻하는 것이죠)

 

축산을 경영하는데 있어서 필요한 경영 계획법(축산경영계획법)들 중에서 이 선형계획법이 나옵니다. 

축산에서 이 개념을 쓰는 이유는 축산도 회사처럼 경영을 잘 해야 비용은 적고 높은 수익을 낼 수 있기 때문입니다.

소를 키우는 이유는 돈을 벌기 위함이 목적이기 때문에 당연히 경영관리에 힘을 써야합니다. 

들어오는 수입이 많더라도 나가는 비용이 많으면 경영을 잘 한다고 할수가 없거든요. 

내가 가지고 있는 자원 안에서 어떻게 선택하면 또는 어떻게 조합을 하면, 순수익을 최대화 할 수 있는지, 아니면 비용을 최소화할 수 있는지를 수학의 함수를 이용해서 이를 구하는 겁니다. 

내가 가지고 있는 자원이 무한하다면 이런 고민을 할 필요가 없죠. 근데 사람은 가지고 있는 자원이 각자 한계가 있기 때문에 이런 고민을 하는 겁니다. 

정의: 선형계획법은 제한된 자원을 각 생산부문에합리적으로 배분하기 위해 생산조건을 수식화하고 최적화시키는 계획방법이다.

정의: 함수를 이용해서 순수익 최대, 비용 최소를 위해 수립하는 계획이다.

 

선형계획법이 쓰이는 곳

선형계획법은 우리 실생활 여러 곳에서 쓰일 수 있습니다.

한정된 자원이나 총소득의 최적 배분에 사용되기도 하고

수송 계획을 세울 때 운임을 최소화하는 데 사용 할수도 있구요.

사료공장에서 사료배합에도 쓰일 수 있습니다.

공장에서 가지고 있는 여러가지 원료사료들을(한정된 자원) 조합해서 사료배합의 최적의 조합비를 구할 수 있거든요.

 

선형계획법에서 Linear의 뜻

선형계획법 (Linear Programming) 에서 Linear(리니어) 는 수학개념입니다.

뜻하는 것은 문제에 내포된 변수간의 관계를 일차함수로 나타낼 수 있다는 뜻 입니다.

=계획을 세울 경우, 기초가 되는 상호관계(변수들 간의 관계)가 1차식의 형식(일차함수)임을 나타냅니다.

일차함수는 좌표선상에서 직선으로 나타내지기 때문에 선형계획법에서 '선형' 을 의미하는 것이죠.

 

선형계획법에서는 제약조건이 되는 식을 세우는데 일차부등식, 일차방정식으로 나타낼 수 있어요. 구하고자 하는 값을 나타내는 목적함수도 일차식으로 나타낼 수 있어서 이 주어진 식들을 다 만족하는 해를 구하면 되는 겁니다.  

 

 

선형계획법 계산 문제를 하나 풀어보겠습니다.

선형계획법은 제일 처음해야할 것은 어떤 것을 x, y 로 둘 것인가 고민하는 것입니다. 그 다음은 x, y를 이용하여 부등식만 잘 세우면 됩니다. 

 

문제)

어느 회사에서 A제품 생산시 개당 8시간 필요하고, 10kg의 원료가 필요하다.

B제품 생산시 개당 33시간 필요하고, 10kg의 원료가 필요하다.

제품을 만드는데 주어진 시간은 90시간 이하이고, 총원료는 50kg 이하로 사용하고자한다.

A제품 한 개 판매시 이익금은 1만원, B제품 한 개 판매시 이익금은 2만원이다.

A제품과 B제품을 각각 몇 개 만들 때 이익이 최대가 되고, 최대이익금은 얼마인가.

 

풀이)

제품	시간	원료	이익금
A	8	10	1만원
B	33	10	2만원

 

A제품=x개, B제품=y개 로 둔다.

최대이익금=K로 둔다.

 

제약조건

①x≥0, y≥0 (제품이 마이너스 몇 개 이런 거는 있을 수가 없으므로 양수여야 합니다.)

②8x+33y≤90 (90시간 이하)

③10x+10y≤50 (50kg 이하)

 

목적함수: K=1x+2y (단위는 만원으로 할게요. 만원을 생략하는 거에요. K=1(0000)x+2(0000)y)

 

 

desmos를 이용해 식그리기

 

desmos를 이용해서 위의 제약조건과 목적함수를 그려보았습니다. 겹쳐서 잘 안 보이기는 한데, 주황색영역은 y 범위이고, 파란색 범위는 x 범위입니다. 초록색영역은 8x+33y≤90 이고 보라색영역은 10x+10y≤50, 파란색 선은 목적함수 K=1x+2y를 나타낸 것입니다.

 

3가지 제약조건을 만족하는 공통된 영역은 원점에 보이는 사각형 부분입니다.  이 공통된 영역 중에서 우리가 궁금해하는 목적함수 K=1x+2y(파란색 직선)가 지나가는 곳 중 최댓값이 되는 곳은 사각형에서 제일 바깥쪽입니다. 저 곳은 제약조건 1번 일차부등식과 2번 일차부등식의 교차점인 것을 알 수 있습니다.

그래서 우리는 제약조건 1번 일차부등식과 2번 일차부등식을 연립해서 x값과 y값을 구해주면 간단하게 해결이 됩니다.

 

②8x+33y≤90 

③10x+10y≤50 

 

②8x+33y≤90 에 10을 곱해주면 ②80x+330y≤900

③10x+10y≤50  에 8을 곱해주면 ③80x+80y≤400  

 

 ②80x+330y≤900

-③80x+80y≤400  

250y=500

y=2

 

8x+66=90

8x=24

x=3

 

이익이 최대가 되는 것은 y는 2개, x는 3개 일 때 인 것을 알 수 있습니다. 

최대이익금은 목적함수 K=x+2y 에 x, y 대입해주면, 최대이익금=3+4=7이 나오는데, 단위가 만원이니까 7만원인 것을 알 수 있습니다.