경영과학 - 수송계획법(Transportation Problem)

해당 글에서는 선형계획법의 응용으로써 수송문제를 다루어보고자 합니다. 수송문제란 다수의 공급지와 다수의 수요지가 존재하는 상황에서 어떤 공급지에서 어떤 수요지로 얼마만큼의 물량이 가야하는지를 결정하는 문제입니다. 

일반적으로 수송문제는 3가지 상황에 대한 이해가 필요합니다. 첫 번째로는 공급지에서 수요지로 물량을 이동할 때 발생하는 비용입니다. 두 번째는 공급지에서 공급가능한 양(Capacity), 마지막으로는 수요지에서 필요로 하는 수요량입니다. 위의 3가지 상황을 활용하여 목적함수, 의사결정변수 등을 정의하게 됩니다.

예시를 통해 수송계획문제 해결방안에 대해서 정리해보도록 하겠습니다.

장난감을 생산하는 한 회사가 3개의 공장(공장 1, 공장 2, 공장3)을 보유하고 있고, 해당 장난감을 받을 도시가 4개(도시1, 도시2, 도시3, 도시4)가 있다고 가정해보겠습니다.  각 공장에서 각 도시로 하나의 장난감을 공급할 때 발생하는 비용은 아래와 같으며, 수송문제는 비용을 최소하는 것이 목적입니다.

	도시1	도시2	도시3	도시4
공장1	8	6	10	9
공장2	9	12	13	7
공장3	14	9	16	5

 각 공장의 공급 가능량과 수요처의 수요량은 다음과 같습니다.

공급가능량 : 공장1 - 35 / 공장2 - 50 / 공장3 - 40

수요량 : 도시1 - 45 / 도시2 - 20 /  도시3 - 30 / 도시4 - 30

위 문제를 수식으로 나타내면 다음과 같습니다.

목적함수: $$Min \sum_{i}^{3}\sum_{j}^{4} C_{ij}X_{ij}$$

공급지제약조건: $$\sum_{j}^{4} X_{ij}=S_i$$

수요지제약조건: $$\sum_{i}^{3} X_{ij}=d_i$$ 

부호조건: $$X_{ij} >=0$$

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

from ortools.linear_solver import pywraplp
from ortools.init import pywrapinit
import pandas as pd
import numpy as np


## Problem Conditions
num_plant = 3
num_city = 4

cost_matrix = [[8,6,10,9],
	 [9,12,13,7],
	 [14,9,16,5]]

plant_supply_capa = [35,50,40]
demand = [45,20,30,30]

먼저 공급지수, 수요지수, 비용, 공급량, 수요량과 같은 문제상황을 입력합니다.

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

## Define Decision Variable
x={}
for i in range(num_plant):
    for j in range(num_city):
        x[i,j] = solver.NumVar(0, solver.infinity(), '')


## Define Constratins

## Supply Constraints
for i in range(num_plant):
    solver.Add(solver.Sum(x[i,j] for j in range(num_city)) == plant_supply_capa[i])
    
## Demand Constraints
for j in range(num_city):
    solver.Add(solver.Sum(x[i,j] for i in range(num_plant))==demand[j])

해당문제에서 의사결정 변수는 공급지수 * 수요지수가 됩니다. 따라서 Dictionary를 활용하여 의사결정변수를 저장합니다. 수식에서 표현한것과 마찬가지로 $X_{ij}$를 하나씩 Dictionary에 정의한다고 생각하시면 됩니다. 공급지, 수요지 제약조건을 줄 때도 Dict에 저장되어 있는 $X_{ij}$를 활용하여  수식을 표현하게 됩니다.

## Define Objective function
objective_terms = []
for i in range(num_plant):
    for j in range(num_city):
        objective_terms.append(cost_matrix[i][j]*x[i,j])


solver.Minimize(solver.Sum(objective_terms))    

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

if status == pywraplp.Solver.OPTIMAL:
    print('Objective value =', solver.Objective().Value())
    for i in range(num_plant):
        for j in range(num_city):
            print('x({},{}) ='.format(i,j), round(x[i,j].solution_value()))
   

else:
    print('The problem does not have an optimal solution.')
    
 '''
 Objective value = 1020.0
x(0,0) = 0
x(0,1) = 10
x(0,2) = 25
x(0,3) = 0
x(1,0) = 45
x(1,1) = 0
x(1,2) = 5
x(1,3) = 0
x(2,0) = 0
x(2,1) = 10
x(2,2) = 0
x(2,3) = 30
'''

마지막으로 목적함수를 정의합니다. 이도 공급지(i), 수요지(j)를 하나씩 불러와서 비용과 곱해준 후 sum을 수행합니다. 이처럼 for loop 및 list comprehension과 유사한 방법을 활용하여 상당히 직관적으로 수식을 구현해볼 수 있습니다.