[최적화] 최선의 결과를 찾는 선형계획법과 정수계획법

 

 

주어진 조건 속에서 최상의 해를 찾는 과정

 

0. 개요

최적화(Optimization)는 주어진 조건 하에서 최상의 해를 찾는 과정입니다. 머신러닝 모델의 파라미터 튜닝부터 물류 최적화까지, 데이터 사이언스와 AI에서도 필수적인 개념이라고 할 수 있죠. 

 그중에서도 선형계획법(Linear Programming, LP) 은 목적 함수와 제약 조건이 모두 선형(linear)인 최적화 문제를 푸는 강력한 방법이다. 예를 들면, "이익을 최대로 하면서도 예산을 초과하지 않게 공장을 운영하려면?" 같은 문제를 푸는 데 유용합니다. 

 

 

1. 선형계획법(Linear Programming)

선형계획법은 다음과 같은 형태를 가집니다.

즉,

• 목적 함수(예: 이익)를 최적화하면서
• 주어진 제약 조건(예: 예산, 자원)을 만족하는 xxx 값을 찾는 것이 목표입니다.
• 모든 식이 선형(Linear)이어야 하는 수식을 갖추고 있습니다.

1-1. 예제: 공장 생산 최적화 문제

에를 들어,어떤 공장에서 제품 A와 B를 생산한다고 가정해보겠습니다.

• 제품 A는 개당 3시간, 제품 B는 개당 2시간이 걸립니다.
• 총 생산 시간은 18시간을 초과할 수 없습니다.
• 제품 A의 이익은 5달러, B는 3달러라고 해보겠습니다.

이때, 이익을 최대화하는 제품 생산 개수는?

이를 수식으로 정리하면:

위와 같은 결과를 갖게 되는 것 입니다. 

 

1-1. 파이썬 실습

 

from scipy.optimize import linprog

# 목적 함수 계수 (최대화 문제는 음수로 변환)
c = [-5, -3]

# 제약 조건 계수 및 값
A = [[3, 2]]  # 3A + 2B
b = [18]       # ≤ 18

# 변수의 하한 (A, B >= 0)
x_bounds = [(0, None), (0, None)]

# 선형 계획법 풀이
res = linprog(c, A_ub=A, b_ub=b, bounds=x_bounds, method="highs")

# 결과 출력
print(f"최적 생산량: 제품 A = {res.x[0]:.2f}, 제품 B = {res.x[1]:.2f}")
print(f"최대 이익: {-res.fun:.2f}")

 

위와 같이 코드를 돌리게 되면 선형계획법에 따라 우리가 공장에서 한정된 시간(18) 시간 내에 최대 이익을 만들 수 있는 상품을 만들어 낼 수 있습니다.

 

 

- 최적 생산량: 제품 A = 6.00, 제품 B = 0.00  
- 최대 이익: 30.00  

 

위와 같이 선형위에서 면적을 최대화하는 과정을 만든 것 입니다. 반대로 최소화 과정도 있기 때문에, 만약 비용 절감이 목적이라면 해당과 반대되는 식으로 만들수도 있습니다.

 

2. 정수계획법(Integer Programming)

하지만,  선형계획법에서는 해가 실수(예: 3.5)일 수도 있습니다, 현실에서는 반쪽짜리 제품을 만들 수 없으므로 정수만 허용해야 하는 경우가 많습니다. 위에서는 운이좋게 제품 생산이 6과 0으로 떨어졌지만, 선형계획법은 정수가 아닙니다. 이런 경우 정수계획법(Integer Programming, IP) 을 사용해야 합니다. 그리고, 정수계획법은 3가지 유형으로 나눠집니다.

 

2-1. 정수계획법의 유형

1. 순수 정수계획법 (Pure IP): 모든 변수는 정수여야 함.
2. 혼합 정수계획법 (Mixed Integer Programming, MIP): 일부 변수만 정수로 제한됨.
3. 0-1 정수계획법 (Binary Integer Programming, BIP): 변수들이 0 또는 1만 가질 수 있음. (예: 특정 공장을 열지 닫을지 결정하는 문제)

2-2. 예제

 

선형계획법과 정수계획법의 차이를 예시로 들기 위해 한 공장에서 일반 직원과 숙련 직원 두 종류의 인력을 배치하는 예시 문제를 만들어보겠습니다.

 

• 일반 직원 한 명이 하루에 3개, 숙련 직원 한 명이 하루에 5개의 제품을 생산한다고 해보겠습니다.
• 목표는 총 20개 이상의 제품을 생산하는 것입니다.
• 일반 직원의 급여는 4만 원, 숙련 직원의 급여는 6만 원이므로 급여 비용을 최소화하고 싶습니다.
• 하지만 직원 수는 정수여야 하므로 정수계획법을 적용해야 합니다!

 

2-2-1 : 선형계획법

from scipy.optimize import linprog

# 목적 함수: 급여 비용 최소화 (-1을 곱해서 최소화 문제로 변환)
c = [4, 6]

# 제약 조건: 생산량이 20개 이상이어야 함
A = [[-3, -5]]  # -3x - 5y <= -20 (즉, 3x + 5y >= 20)
b = [-20]

# 변수 범위 (음수가 되면 안 됨)
x_bounds = [(0, None), (0, None)]

# 선형 계획법 실행
res_lp = linprog(c, A_ub=A, b_ub=b, bounds=x_bounds, method="highs")

# 결과 출력
print(f"선형계획법 결과: 일반 직원 = {res_lp.x[0]:.2f}, 숙련 직원 = {res_lp.x[1]:.2f}")
print(f"최소 급여 비용: {res_lp.fun:.2f}만 원")

 

선형계획법을 적용하면 일반 직원 2.67명, 숙련 직원 2.67명이 최적해로 나옵니다. 하지만 현실적으로 0.67명의 직원은 고용할 수 없으므로 정수 해가 필요합니다.

 

2-2-2 : 정수계획법

 

from pulp import LpMinimize, LpProblem, LpVariable

# 문제 정의
model = LpProblem(name="integer-staffing", sense=LpMinimize)

# 변수 정의 (정수형 변수)
x = LpVariable(name="General_Staff", lowBound=0, cat="Integer")
y = LpVariable(name="Skilled_Staff", lowBound=0, cat="Integer")

# 목적 함수: 급여 비용 최소화
model += 4 * x + 6 * y, "Total_Cost"

# 제약 조건: 생산량이 20개 이상이어야 함
model += 3 * x + 5 * y >= 20, "Production_Constraint"

# 최적화 실행
model.solve()

# 결과 출력
print(f"정수계획법 결과: 일반 직원 = {x.varValue}, 숙련 직원 = {y.varValue}")
print(f"최소 급여 비용: {model.objective.value()}만 원")

 

정수계획법의 결과는 일반 직원 3명, 숙련 직원 3명으로 배치되었고, 인력을 2.67(?) 명으로 배치 하지 않아도 됩니다.

 

실수해는 2.67 이기 때문에 2.67 이 최적화지만, 우리는 인원이라는 정수값이 필요하기 때문에 3명씩 배치하는것이 최적화라는 것을 알 수 있습니다. 이렇게, 비슷하지만 살짝은 다른 두 방법을 알아보았습니다.

 

3. 결론

정수계획법과 선형계획법은 현실적인 의사결정(예: 공장 운영, 물류 최적화, 인력 배치 등)에 유용한 방법론입니다. 해당 도메인 영역에서는 쉽고 직관적이기 때문에 많이 쓰이고 있고요! 이상. 오늘은 최적화 기법에 대해 간단하게 알아보았습니다!