Data/데이터 분석

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

Derek Grey 2025. 3. 2. 23:06
반응형

 

 

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

 

0. 개요

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

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

 

 

1. 선형계획법(Linear Programming)

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

즉,

  • 목적 함수(예: 이익)를 최적화하면서
  • 주어진 제약 조건(예: 예산, 자원)을 만족하는 xx 값을 찾는 것이 목표입니다.
  • 모든 식이 선형(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. 결론

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

반응형