경영과학 - 선형계획법(Linear Programming)

선형계획법은 현재 최적화 방법론중에서 가장 대중적인 방법이라고 할 수 있습니다. 우리가 선택해야 하는 대안(의사결정 변수)들을 선형의 등식이나 부등식으로 표현하여 최적화를 수행하는 것을 뜻합니다. 선형계획법은 유한한 자원을 효율적으로 분배할 때도 많이 활용되며 예시적으로 장난감회사에서 매출과 비용을 고려할 때 A장난감을 많이 생산할지 B장난감을 많이 생산할지 등과 같은 상황에 대한 답을 찾는 경우에도 적용할 수 있습니다. 

선형계획법은 크게 의사결정변수(Decision Variable), 목적함수(Objective Function), 제약조건(Constraints), 부호제약(Sign Restrictions)로 이루어져 있습니다.

해당 블로그에서는 장난감 회사의 생산문제를 기반으로 위에서 언급한 의사결정변수, 목적함수, 제약조건, 부호제약에 대해서 정리해고 Python기반의 Google OR-tools를 활용하여 선형계획법 문제의 해를 찾아보도록 하겠습니다.

[의사결정변수(Decision Variable]

의사결정변수는 의사결정자가 결정해야 할 대상을 뜻합니다. 즉 의사결졍변수는 아직 값은 모르지만 우리가 최적화를 통해 결정하고자(알고자)하는 변수를 뜻합니다.  선형계획법에서 의사결정변수는 정수의 값이 아니라 실수를 가진다고 가정합니다.(정수로 가정하는 경우 정수계획법(Integer Programming)이라고 불리게 됩니다.)

군인 장난감과 기차 장난감을 생산하는 장난감 생산회사가 있다고 가정해보겠습니다. 그렇다면 장난감회사에서는 일주일에 몇개의 군인 장난감과 기차 장난감을 각각 생산해야해는지 결정해야 합니다. 따라서 의사결정변수는 아래와 같이 정의 될 수 있습니다.

$x_1$: 일주일에 생산해야하는 군인 장난감의 수

$x_2$: 일주일에 생산해야하는 기차 장난감의 수

[목적함수(Objective Function)]

목적함수는 의사결정자가 이루고자하는 목표를 나타내며, 이를 수리적으로 표현한 것입니다. 목적함수는 최대화(매출/이익 등) 또는 최소화(비용 등)의 대상이 되며, 이러한 최대화/최소화하고자 하는 함수를 목적함수라고 정의하게 됩니다.

장난감 회사는 군인 장난감을 판매하면 3원의 이득이 있고 기차 장난감을 판매하면 2원의 이익이 있다고 가정하겠습니다. 그렇다면 목적함수는 다음과 같이 정의됩니다.

$Maximize z =3x_1+2x_2$

[제약조건(Constraints)]

제약조건은 용어 의미 그대로 우리의 목적을 이루는 것에 제한을 주는 조건을 뜻한다. 현실적인 제약조건이 없다면 목적함수의 값은 한없이 커지거나 줄어들 수 있다.

장난감 회사는 군인 장난감 또는 기차 장난감을 생산하는데 총 100시간을 소요할 수 있고, 군인 장난감을 생산하는데는 2시간, 기차 장난감을 생산하는데는 1시간이 소요됩니다. 또한 장난감을 포장하는데 소요되는 시간은 80시간을 초과할 수 없고 군인 장난감, 기차 장난감 각각 포장시간은 1시간씩 소요됩니다. 마지막으로 군인 장난감은 일주일에 최대 40개만 생산됩니다. 이를 제약식으로 표현하면 아래와 같습니다.

$2x_1+x_2 <=100$

$x_1+x_2 <=80$

$x_1 <=40$

[부호제약(Sign Restrictions)]

부호제약은 의사결졍변수가 가질 수 있는 값의 범위 입니다. 주로 양수조건, 음수조건 등을 가지게 됩니다. 

장난감회사는 군인 장난감이나 기차 장난감을 음수로 생산할 수 없습니다. 따라서 의사결정변수의 부호 조건은 아래와 같습니다.

$x_1, x_2 >=0$  

이제 위의 식을 정리해서 표현하면 아래와 같은 선형계획모형을 만들 수 있습니다.

 

$Maximize z =3x_1+2x_2$ (목적함수)

$2x_1+x_2 <=100$ (생산시간제약)

$x_1+x_2 <=80$ (포장시간제약)

$x_1 <=40$ (생산수 제약)

$x_1, x_2 >=0$  (부호제약)

 

이제 위의 문제를 Google OR-tools를 활용하여 최적의 해를 찾아보도록 하겠습니다.

from ortools.linear_solver import pywraplp
from ortools.init import pywrapinit


## define solver
solver = pywraplp.Solver.CreateSolver('GLOP')

## define decision variable
x_1 = solver.NumVar(0, solver.infinity(), 'x_1')
x_2 = solver.NumVar(0, solver.infinity(), 'x_2')


## define constraints
solver.Add(2*x_1+x_2 <= 100)
solver.Add(x_1+x_2 <= 80)
solver.Add(x_1 <= 40)


## defince objective function
solver.Maximize(3*x_1 + 2*x_2)

## invoke the solver
status = solver.Solve()

if status == pywraplp.Solver.OPTIMAL:
    print('Objective value =', solver.Objective().Value())
    print('x_1 =', round(x_1.solution_value(),0))
    print('x_2 =', round(x_2.solution_value(),0))

else:
    print('The problem does not have an optimal solution.')

최종적으로 군인 장난감($x_1$)은 20개 기차 장난감($x_2$)은 60개를 생산하라는 최적해를 얻을 수 있습니다.