최적화 문제 (Optimization) / Linear Programming (선형 계획법) / python PuLP 라이브러리

안녕하세요, 이번 포스팅에서는 최적화 문제의 일종인 선형 계획법을 Python PuLP 라이브러리를 이용해 풀어보도록 하겠습니다. 

 

선형 계획법(Linear Programming)이란? 

먼저, 선형계획법이란 무엇일까요?

수학에서 선형 계획법은 최적화 문제의 일종으로 주어진 선형 조건들을 만족시키면서 선형인 목적 함수를 최적화하는 문제입니다. 

'최적화 문제'라는 단어가 나왔는데 간단하게 말해서 주어진 조건들을 만족시키면서 목적 함수를 최적화하는 문제입니다. 

선형 계획법은 가변 요소 사이에 일차 방정식이 성립할 경우, 즉 선형(線型)의 관계가 있을 때, 변화의 한계를 정할 때에 사용하는 방법으로, 생산계획·수송계획 등 문제에 선형 계획법이 이용되고 있습니다.

할당 문제도 선형 계획법으로 풀 수 있습니다.

 

예를 들어 판매 과장이 세일즈맨을 각 지역으로 할당하는 문제에 직면했다고 생각해 봅시다.

• 조건
  • 세일즈맨에게는 제각기의 특성이 있어서 세일즈맨에 따라 적절한 지역이 다르고, 몇몇 세일즈맨은 매우 우수하여 어느 지역이라도 담당할 수 있으며 더욱이 다른 세일즈맨보다 더 좋은 업적을 올릴 수가 있습니다.
• 목적
  • 판매과장의 문제는 세일즈맨의 지역할당을 통해 전체의 판매량을 최대로 함에 있을 것입니다.
• 이 경우 만약 세일즈맨이 각각의 지역에 있어서 상대적 효율을 수량화 할 수 있다고 하면 간단한 선형 계획법의 수법을 써서 최적의 할당을 정할 수가 있습니다.

 

선형 계획법(Linear Programming) 예시

더 구체적인 예시를 통해 선형 계획법 문제를 함께 풀어보도록 하겠습니다.

 

조이는 두 가지 종류의 빵을 판매합니다. 

	초코빵 🍪	밀빵 🌾	가지고 있는 재료량
밀가루	100g	50g	3,000g
초콜릿	10g	0g	100g
Profit	100원	40원

• 초코빵을 만들기 위해서는 밀가루 100g과 초콜릿 10g이 필요하고,
• 밀빵을 만들기 위해서는 밀가루 50g이 필요합니다. 
• 재료비를 제하고 초코빵을 팔면 100원이 남고, 밀빵을 팔면 40원이 남습니다. 
• 오늘 조이는 밀가루 3000g과 초콜릿 100g을 재료로 갖고 있습니다. 

만든 빵을 전부 팔 수 있고 더 이상 재료 공급을 받지 않는다고 가정한다면, 조이는 이익을 극대화하기 위해서 어떤 종류의 빵을 얼마나 만들어야할까요?

 

위 문제는 다음과 같이 나타낼 수 있습니다. 

(x1은 초코빵의 개수, x2는 밀빵의 개수 의미하는 변수) 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

이익 극대화 시점은 이익을 나타내는 직선(=초록색 직선)이 해가 존재할 수 있는 영역(=빨간색과 파란색 모두에 해당하는 영역) 중 원점에서 가장 떨어진 점 (10, 40)에 접할 때입니다.

이 예시에서 가장 많은 이익을 남기는 방법은 초코빵 10개, 밀빵 40개를 만드는 것이고, 그렇게 했을 때 2,600원의 이익을 얻을 수 있습니다. 

 

PuLP 라이브러리 사용

위 문제를 Linear Programming 문제를 풀 수 있는 Python 라이브러리인 PuLP를 사용해 풀어봅시다. 

 

일반적인 PuLP 모델링 프로세스는 다음과 같습니다. 

1. Initialize Model (모델 초기화)
2. Define Decision Variables (결정 변수 정의)
3. Define the Objective Function (목적 함수 정의)
4. Define the Constraints (제약조건 정의)
5. Solve Model (모델 풀이)

 

모델링에 들어가기 전에 pulp 라이브러리를 설치 후 패키지를 불러와 주세요. 

! pip install PuLP
import pulp

 

1. Initialize Model (모델 초기화)

# 문제 정의
problem = pulp.LpProblem(name="Bakery_Profit_Maximization", sense=pulp.LpMaximize)

• LpProblem 기능을 이용해 모델을 만들어주세요. 
• 모델 name은 "Bakery_Profit_Maximization"로 지정하였습니다. 
• 저희는 목적 함수를 최대화하는 것이 목적이기 때문에 sense=pulp.LpMaximize를 입력했습니다.
  • 만약 최소화하는 것이 목적이라면 sense=pulp.LpMinimize를 입력해주세요. 

2. Define Decision Variables (결정 변수 정의)

# 변수 정의
choco_bread = pulp.LpVariable("Choco_Bread", lowBound=0, cat='Integer')
wheat_bread = pulp.LpVariable("Wheat_Bread", lowBound=0, cat='Integer')

•  
• 주어진 문제에서 결정 변수는 초코빵의 개수, 밀빵의 개수입니다. 
• LpVariable 기능을 이용해 결정 변수를 정의합니다. 
  • name: 변수의 이름입니다. 저희는 각각 초코빵("Choco_Bread"), 밀빵("Wheat_Bread")이라고 주었어요. 
  • lowBound: Lower bound. Default는 None인데 개수가 음수가 나올 수 없으니 0을 주었습니다. 
  • upBound: Upper bound. Default는 None인데 빵 개수에 상한선은 없으니 따로 값을 주지 않았습니다. 
  • cat: 변수의 타입입니다. Integer, Binary, Continuous(default) 이렇게 세 개를 선택할 수 있어요. 빵의 개수는 정수이니 'Integer'를 주었습니다. 

더 자세한 내용은 공식 문서를 참고해주세요! (https://coin-or.github.io/pulp/)

3. Define the Objective Function (목적 함수 정의)

# 목적 함수 (이익을 극대화)
# 재료비를 제하고 초코빵을 팔면 100원이 남고 밀빵를 팔면 40원이 남는다.
problem += (100 * choco_bread + 40 * wheat_bread)

주어진 문제에서 목적함수는 "초코빵의 Profit * 초코빵의 개수 + 밀빵의 Profit * 밀빵의 개수"를 최대화 시키는 것입니다.

최대화는 모델 초기 설정 시 sense = pulp.LpMaximize 라는 파라미터로 이미 설정해 주었습니다.  

4. Define the Constraints (제약조건 정의)

# 제약 조건 (재료 사용량 제약)
# 초코빵을 만들기 위해서는 밀가루 100g과 초콜릿 10g이 필요하고 밀빵을 만들기 위해서는 밀가루 50g이 필요하다.
# 오늘 홍길동 씨는 밀가루 3000g과 초콜릿 100g을 재료로 갖고 있다.
problem += (100 * choco_bread + 50 * wheat_bread <= 3000, "밀가루 제약")
problem += (10 * choco_bread <= 100, "초콜릿 제약")

목적함수 정의와 마찬가지로 제약 조건을 정의해주세요. 

5. Solve Model (모델 풀이)

# 최적화 문제 풀이
problem.solve()

 

아주 간단히 problem.solve()를 입력하면 위에서 정의한 문제를 풀이합니다. 

 

결과 출력

# 최적 생산량 출력
if problem.status == pulp.LpStatusOptimal:
    choco_bread_quantity = choco_bread.value()
    wheat_bread_quantity = wheat_bread.value()
    print(f"초코빵 생산량: {choco_bread_quantity} 개")
    print(f"밀빵 생산량: {wheat_bread_quantity} 개")
else:
    print("최적 해를 찾을 수 없습니다.")

위와 같이 결과를 Print해보면 초코빵 10개, 밀빵 40개라는 결과를 얻을 수 있습니다. 

 

 

출처

• 선형 계획법 정의: https://w.wiki/7gdY
• Python Tutorial : Basics of PuLP modeling: https://youtu.be/lMaryTY6ngM?feature=shared
  
• Linear Programming in Python Using PuLP: https://youtu.be/qa4trkLfvwQ?feature=shared