The transportation problem is one of the classical problems teached in linear programming classes. The problem, put simply, states that a given set of customers with a specified demand must be satisfied by another set of supplier with certain capacities (“supply”). For a detailed explanation of the transportation problem you can e.g. read this: https://econweb.ucsd.edu/~jsobel/172aw02/notes8.pdf.
The lpSolve package available in R can be used for modelling and solving the transportation problem.
I will show how to do this. I define a problem in which 3 suppliers seek to satisfy 4 customers. The suppliers have capacities 100, 300 and 400 respectively. The customers have demand 100, 100, 200, and 400 respectively. Furthermore, the cost for supplying customer i by supplier j is defined for every possible combination and stated in a cost matrix.
Using this information we can model and solve the transportation problem (deciding which demand to fulfill by which supplier) with the lpSolve package in R.
First, I prepare the modeling-part:
library(lpSolve) # specifying cost matrix cost.mat <- matrix(nrow=3,ncol=4) cost.mat[1,] <- 1:4 cost.mat[2,] <- 4:1 cost.mat[3,] <- c(1,4,3,2) # this is a minimization problem direction = "min" # capacity may not be exceeded row.signs <- rep("<=",3) row.rhs <- c(100,300,400) # demand must be satisfied col.signs <- rep(">=",4) col.rhs <- c(100,100,200,400)
Then, I solve the problem:
# solve and assign lp object solution <- lp.transport(cost.mat = cost.mat, direction = direction, row.signs = row.signs, row.rhs = row.rhs, col.signs = col.signs, col.rhs = col.rhs)
Let us review the “optimal” costs:
## Success: the objective function is 1400
Let us review the optimal solution of the transportation problem (i.e. the optimal material flows to this problem):
## [,1] [,2] [,3] [,4] ## [1,] 0 100 0 0 ## [2,] 0 0 200 100 ## [3,] 100 0 0 300
The assignent problem is another classical problem, and you can see how I solved it in R here: Cost minimal production scheduling – solving the assignment problem with lpSolve, using lp.assign