Demand = {'C1': 155,
'C2': 125,
'C3': 265,
'C4': 350,
'C5': 275,
'C6': 130
}
Supply = {'S1': 650,
'S2': 700
}
T = {('C1', 'S1'): 1000, ('C1', 'S2'): 1.4,
('C2', 'S1'): 2.0, ('C2', 'S2'): 1000,
('C3', 'S1'): 2.0, ('C3', 'S2'): 1.4,
('C4', 'S1'): 2.5, ('C4', 'S2'): 1.8,
('C5', 'S1'): 2.8, ('C5', 'S2'): 2.0,
('C6', 'S1'): 2.5, ('C6', 'S2'): 1.8
}Ex. D1: Simple Supply Chain (SSC)
Adapted from this Medium post and from J.C. Kantor’s notebook.
Background
A classic example of a supply chain optimization use case is the transportation problem. Usually, it deals with the distribution of goods from a set of factories (or producers, sources) to a set of customers. The objective is the minimization of the total transportation costs, while satisfying constraints on the available supplies from each source and demand requirements for each destination.
In the CDT context, this setting could correspond to data transfer between sources (instruments) and data centres, or between data centres and HPC centers, or between HPC centers and end-users.
Data
Suppose we have 2 suppliers (factories), \(\mathcal{S} = \{S_1,S_2\}\) and 6 customers, \(\mathcal{C} = \{ C_1,\ldots,C_6\}.\) To each supplier we associate a production capacity and to each client a demand.
The transport costs are pairwise, between suppliers and customers. There is no transport possible between \(S_1\) and \(C_1,\) and between \(S_2\) and \(C_2.\) The associated costs are attributed a large value (1000), to ensure that they are not chosen.
Model
The objective is to minimize the total shipping cost to all customers from all sources.
\[\text{minimize:}\quad \text{Cost} = \sum_{c \in \mathcal{C}}\sum_{s \in \mathcal{S}} T[c,s] x[c,s]\] or simply \[ \min_x \sum_{c \in \mathcal{C}}\sum_{s \in \mathcal{S}} T[c,s] x[c,s],\]
where for each link/arc we have a parameter \(T[c,s]\) denoting the cost of shipping a ton of goods over the link. What we need to determine is the amount of goods to be shipped over each link, which we is represented as a non-negative decision variable \(x[c,s].\)
We add two constraints.
Shipments from all sources can not exceed the manufacturing capacity of the source.
\[\sum_{c \in \mathcal{C}} x[c,s] \leq \text{Supply}[s] \qquad \forall s \in \mathcal{S}.\]
Shipments to each customer must satisfy their demand.
\[\sum_{s\in \mathcal{S}} x[c,s] = \text{Demand}[c] \qquad \forall c \in \mathcal{C}.\]
from pyomo.environ import *
# Step 0: Create an instance of the model and its dual
model = ConcreteModel()
model.dual = Suffix(direction=Suffix.IMPORT)
# Step 1: Define index sets
CUS = list(Demand.keys())
SRC = list(Supply.keys())
# Step 2: Define the decision variable
model.x = Var(CUS, SRC, domain = NonNegativeReals)
# Step 3: Define objective
@model.Objective(sense=minimize)
def cost(m):
return sum([T[c,s]*model.x[c,s] for c in CUS for s in SRC])
# Step 4: Constraints
@model.Constraint(SRC)
def src(m, s):
return sum([model.x[c,s] for c in CUS]) <= Supply[s]
@model.Constraint(CUS)
def dmd(m, c):
return sum([model.x[c,s] for s in SRC]) == Demand[c]
# Step 5: Solve the problem
results = SolverFactory('cbc').solve(model)
results.write()# ==========================================================
# = Solver Results =
# ==========================================================
# ----------------------------------------------------------
# Problem Information
# ----------------------------------------------------------
Problem:
- Name: unknown
Lower bound: 2558.0
Upper bound: 2558.0
Number of objectives: 1
Number of constraints: 8
Number of variables: 12
Number of nonzeros: 6
Sense: minimize
# ----------------------------------------------------------
# Solver Information
# ----------------------------------------------------------
Solver:
- Status: ok
User time: -1.0
System time: 0.0
Wallclock time: 0.01
Termination condition: optimal
Termination message: Model was solved to optimality (subject to tolerances), and an optimal solution is available.
Statistics:
Branch and bound:
Number of bounded subproblems: None
Number of created subproblems: None
Black box:
Number of iterations: 1
Error rc: 0
Time: 0.036546945571899414
# ----------------------------------------------------------
# Solution Information
# ----------------------------------------------------------
Solution:
- number of solutions: 0
number of solutions displayed: 0#model.dual = Suffix(direction=Suffix.IMPORT)
if 'ok' == str(results.Solver.status):
print("Total Shipping Costs = ", model.cost())
print("\nShipping Table:")
for s in SRC:
for c in CUS:
if model.x[c,s]() > 0:
print("Ship from ", s," to ", c, ":", model.x[c,s]())
else:
print("No Valid Solution Found")Total Shipping Costs = 2558.0
Shipping Table:
Ship from S1 to C2 : 125.0
Ship from S1 to C3 : 265.0
Ship from S1 to C4 : 210.0
Ship from S2 to C1 : 155.0
Ship from S2 to C4 : 140.0
Ship from S2 to C5 : 275.0
Ship from S2 to C6 : 130.0Sensitivity Analysis
The solution of the dual problem provides the marginal values: the economic return deriving from a unit (ton) change (increase or decrease) in the availability of resources or in the demand.
We begin with an analysis by supplier.
if 'ok' == str(results.Solver.status):
print("Source Capacity Shipped Margin")
for s in SRC:
print(f"{s:10s}{Supply[s]:10.1f}{model.src[s]():10.1f}{model.dual[model.src[s]]:10.4f}")
else:
print("No Valid Solution Found")Source Capacity Shipped Margin
S1 650.0 600.0 0.0000
S2 700.0 700.0 -0.7000The ‘marginal’ values tell us how much the total costs will be increased for each one ton increase in the available supply from each source. The optimization calculation says that only 600 tons of the 650 available from \(S_1\) should used for a minimum cost solution, which rules out any further cost reductions by increasing the available supply. In fact, we could decrease the supply \(S_1\) without any harm. The marginal value of \(S_1\) is 0.
The source \(S_2\) is a different matter. First, all 700 available tons are being used. Second, from the marginal value we see that the total transportations costs would be reduced by \(0.7\) Euros for each additional ton of supply.
The management conclusion we can draw is that there is excess supply available at \(S_1\) which should, if feasible, be moved to \(S_2.\)
Now we perform a customer analysis.
if 'ok' == str(results.Solver.status):
print("Customer Demand Shipped Margin")
for c in CUS:
print(f"{c:10s}{Demand[c]:10.1f}{model.dmd[c]():10.1f}{model.dual[model.dmd[c]]:10.4f}")
else:
# print("No Valid Solution Found")Customer Demand Shipped Margin
C1 155.0 155.0 2.1000
C2 125.0 125.0 2.0000
C3 265.0 265.0 2.0000
C4 350.0 350.0 2.5000
C5 275.0 275.0 2.7000
C6 130.0 130.0 2.5000Conclusions
Looking at the demand constraints, we see that all of the required demands have been met by the optimal solution.
The marginal values of these constraints indicate how much the total transportation costs will increase if there is an additional ton of demand at any of the locations.
With reference to the matrix \(T\) we can notice differences in two locations: \(C_1\) and \(C_5.\) In \(C_1\) an increase of one ton of demand causes an increase of cost, greater than the list price for shipping to \(C_1\) (2.1 vs 1.4). In \(C_5\) an increase of one ton of demand slightly decreases the cost,less than the list price for shipping to \(C_5\) (2.8 vs 2.7)
To see what’s going on, we re-solve the problem with a one ton increase in the demand at \(C_1.\)
from pyomo.environ import *
Demand1 = {'C1': 156,
'C2': 125,
'C3': 265,
'C4': 350,
'C5': 275,
'C6': 130
}
Supply = {'S1': 650,
'S2': 700
}
T = {('C1', 'S1'): 1000, ('C1', 'S2'): 1.4,
('C2', 'S1'): 2.0, ('C2', 'S2'): 1000,
('C3', 'S1'): 2.0, ('C3', 'S2'): 1.4,
('C4', 'S1'): 2.5, ('C4', 'S2'): 1.8,
('C5', 'S1'): 2.8, ('C5', 'S2'): 2.0,
('C6', 'S1'): 2.5, ('C6', 'S2'): 1.8
}
# Step 0: Create an instance of the model and its dual
model1 = ConcreteModel()
model1.dual = Suffix(direction=Suffix.IMPORT)
# Step 1: Define index sets
CUS = list(Demand1.keys())
SRC = list(Supply.keys())
# Step 2: Define the decision variable
model1.x = Var(CUS, SRC, domain = NonNegativeReals)
# Step 3: Define objective
@model1.Objective(sense=minimize)
def cost(m):
return sum([T[c,s]*model1.x[c,s] for c in CUS for s in SRC])
# Step 4: Constraints
@model1.Constraint(SRC)
def src(m, s):
return sum([model1.x[c,s] for c in CUS]) <= Supply[s]
@model1.Constraint(CUS)
def dmd(m, c):
return sum([model1.x[c,s] for s in SRC]) == Demand1[c]
# Step 5': Solve the problem
results1 = SolverFactory('cbc').solve(model1)
results1.write()# ==========================================================
# = Solver Results =
# ==========================================================
# ----------------------------------------------------------
# Problem Information
# ----------------------------------------------------------
Problem:
- Name: unknown
Lower bound: 2560.1
Upper bound: 2560.1
Number of objectives: 1
Number of constraints: 8
Number of variables: 12
Number of nonzeros: 6
Sense: minimize
# ----------------------------------------------------------
# Solver Information
# ----------------------------------------------------------
Solver:
- Status: ok
User time: -1.0
System time: 0.0
Wallclock time: 0.01
Termination condition: optimal
Termination message: Model was solved to optimality (subject to tolerances), and an optimal solution is available.
Statistics:
Branch and bound:
Number of bounded subproblems: None
Number of created subproblems: None
Black box:
Number of iterations: 1
Error rc: 0
Time: 0.04635906219482422
# ----------------------------------------------------------
# Solution Information
# ----------------------------------------------------------
Solution:
- number of solutions: 0
number of solutions displayed: 0Conclusion
We see the total cost has increased from 2558.0 to 2560.1 Euros, an increase of 2.1 Euros just as predicted by the marginal value assocated with the demand constraint for \(C_1.\)
if 'ok' == str(results1.Solver.status):
print("Total Shipping Costs = ", model1.cost())
print("\nShipping Table:")
for s in SRC:
for c in CUS:
if model1.x[c,s]() > 0:
print("Ship from ", s," to ", c, ":", model1.x[c,s]())
else:
print("No Valid Solution Found")Total Shipping Costs = 2560.1
Shipping Table:
Ship from S1 to C2 : 125.0
Ship from S1 to C3 : 265.0
Ship from S1 to C4 : 211.0
Ship from S2 to C1 : 156.0
Ship from S2 to C4 : 139.0
Ship from S2 to C5 : 275.0
Ship from S2 to C6 : 130.0if 'ok' == str(results.Solver.status):
print("Customer Demand Shipped")
for c in CUS:
print(f"{c:10s}{Demand1[c]:10.1f}{model1.dmd[c]():10.1f}")
else:
print("No Valid Solution Found")Customer Demand Shipped
C1 156.0 156.0
C2 125.0 125.0
C3 265.0 265.0
C4 350.0 350.0
C5 275.0 275.0
C6 130.0 130.0General Conclusion
The dual variables provide an important economic interpretation of the final solution when investigating changes in the parameters of an LP problem.