Unbalanced Transportation Problem

이강우 & 김정자. (2012). EXCEL 2010 경영과학. 한경사, 306.

현실의 수송문제는 총 공급량과 총 수요량이 일치하는 경우는 거의 없으며 이들이 서로 일치하지 않는 공급과잉이나 수요과잉이 발생하는 것이 일반적인 현상이다. 이와 같이 총 공급량과 총 수요량이 서로 일치하지 않는 수송문제를 불균형 수송문제라고 한다.

import os
import sys

# Add the parent directory for importing custom library
sys.path.insert(0, os.path.abspath(os.path.join(os.getcwd(), os.pardir)))

Optimization with PuLP

from pulp import *

prob = LpProblem('Unbalaced Transportation Problem', LpMinimize)

n_suppliers = 3
n_buyers = 4

costs = [
    [4, 5, 6, 8],
    [4, 7, 9, 2], 
    [5, 8, 7, 6]
]

supply = [120, 150, 200]
demand = [150, 60, 130, 180]

routes = [(i, j) for i in range(n_suppliers) for j in range(n_buyers)]

x = LpVariable.dicts('X', routes, lowBound=0)

prob += lpSum([x[i, j] * costs[i][j] for i in range(n_suppliers) for j in range(n_buyers)])

for i in range(n_suppliers):
    prob += lpSum([x[i, j] for j in range(n_buyers)]) == supply[i]
    
for j in range(n_buyers):
    prob += lpSum([x[i, j] for i in range(n_suppliers)]) <= demand[j]
    
# Solving problem
prob.solve()
print('Status', LpStatus[prob.status])

print('Z = {}'.format(value(prob.objective)))
for v in prob.variables():
    print('{} = {}'.format(v.name, v.varValue))

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[2], line 1
----> 1 from pulp import *
      3 prob = LpProblem('Unbalaced Transportation Problem', LpMinimize)
      5 n_suppliers = 3

ModuleNotFoundError: No module named 'pulp'

from gurobipy import *

n_suppliers = 3
n_buyers = 4

costs = [
    [4, 5, 6, 8],
    [4, 7, 9, 2], 
    [5, 8, 7, 6]
]

supply = [120, 150, 200]
demand = [150, 60, 130, 180]

routes = tuplelist([(i, j) for i in range(n_suppliers) for j in range(n_buyers)])

m = Model('Unbalaced Transportation Problem')

x = m.addVars(routes, lb=0, vtype=GRB.CONTINUOUS, name='X')

m.update()

m.setObjective(quicksum(x[i, j] * costs[i][j] for i in range(n_suppliers) for j in range(n_buyers)), GRB.MINIMIZE)

for i in range(n_suppliers):
    m.addConstr(quicksum(x[i, j] for j in range(n_buyers)) == supply[i])
    
for j in range(n_buyers):
    m.addConstr(quicksum(x[i, j] for i in range(n_suppliers)) <= demand[j])

# Optimize model
m.optimize()

print('Z = {}'.format(m.objVal))
for v in m.getVars():
    print('{} = {}'.format(v.varName, v.x))

Transportation Problem with Prohibited Transport Routes

import numpy as np
from pulp import *

prob = LpProblem('Transportation', LpMinimize)

costs = [
    [4, 3, 2, 0],
    [4, 1, 1000, 6], 
    [3, 0, 1, 2]
]

supply = [200, 300, 500]
demand = [100, 60, 130, 300]

n_suppliers = 3
n_buyers = 4

routes = [(i, j) for i in range(n_suppliers) for j in range(n_buyers)]

x = LpVariable.dicts('x', routes, lowBound=0)

prob += lpSum([x[i, j] * costs[i][j] for i in range(n_suppliers) for j in range(n_buyers)])

for i in range(n_suppliers):
    prob += lpSum([x[i, j] for j in range(n_buyers)]) <= supply[i]
    
for j in range(n_buyers):
    prob += lpSum([x[i, j] for i in range(n_suppliers)]) == demand[j]
    
# Solving problem
prob.solve()
print('Status', LpStatus[prob.status])

print('Z = {}'.format(value(prob.objective)))
for v in prob.variables():
    print('{} = {}'.format(v.name, v.varValue))

Transshipment Problem

prob = LpProblem("Transportation", LpMinimize)

S = ["A", "B", "C"]
D = ["1", "2", "3", "4"]
costs = [[21, 12, 25, 11],
         [13, 10, 21, 17],
         [12, 14, 19, 12]]

supply = dict(zip(S, [80, 60, 50]))
demand = dict(zip(D, [50, 40, 70, 30]))
demand

opt_costs = makeDict([S, D], costs, 0)
opt_costs

x = LpVariable.dicts('Route', (S, D), lowBound=0)
x

routes = [(i, j) for i in S for j in D]
routes

prob += lpSum([x[s][d]*opt_costs[s][d] for (s, d) in routes]) # objective function

# constraints
for i in S:
    prob += lpSum([x[i][j] for j in D]) == supply[i]

for j in D:
    prob += lpSum([x[i][j] for i in S]) == demand[j]
    
prob.solve()

for i in prob.variables():
    print(i.name, "=", i.varValue)
print('Status', LpStatus[prob.status])
print(pulp.value(prob.objective))

prob = LpProblem("Unbalanced Transportation", LpMinimize)

S = ["A", "B", "C"]
D = ["1", "2", "3", "4"]
costs = [[21, 12, 25, 11],
         [13, 10, 21, 17],
         [12, 14, 19, 12]]

supply = dict(zip(S, [80, 60, 50]))
demand = dict(zip(D, [60, 50, 80, 40]))

opt_costs = makeDict([S, D], costs, 0)

x = LpVariable.dicts('Route', (S, D), lowBound=0)
x

routes = [(i, j) for i in S for j in D]

prob += lpSum([x[s][d]*opt_costs[s][d] for (s, d) in routes]) # objective function

# constraints
for i in S:
    prob += lpSum([x[i][j] for j in D]) == supply[i]

for j in D:
    prob += lpSum([x[i][j] for i in S]) <= demand[j]
    
prob.solve()

for i in prob.variables():
    print(i.name, "=", i.varValue)
print('Status', LpStatus[prob.status])
print(pulp.value(prob.objective))