In this video, we'll talk about how to formulate a special type of LP problems with wide real-world
applications.
It's called the transportation problem.
This type of problems can be solved using the traditional simplex method.
However, due to their special structure, there exist specialized algorithms that are much
more efficient to solve them.
A typical transportation problem is to find the best solution to fulfill the needs of
n demand points using the capacities of m supply points.
A cost of shipping the products from a supply point to a demand point is involved.
Here is an example.
A manufacturing company has m=2 factories that satisfy the needs of n=3 customers.
The unit shipping cost from a factory to a customer depends on the distance.
For example, from Factory 1 to Customer 1, the unit shipping cost is $8/product.
From Factory 1 to Customer 2, the unit shipping cost is $6/product, and so on.
Each factory has a limited capacity.
Factory 1 can supply at most 40 products per day and Factory 2 can supply at most 50 products
per day.
Each customer will need at least 30 products per day.
For the decision variables, we define xij = the number of products shipped from Factory
i to Customer j.
The objective function is the total cost.
For example, this is the cost of shipping x11 products from Factory 1 to Customer 1.
This is the cost of shipping x12 products from Factory 1 to Customer 2, and so on.
We need to sum up all the cost components.
As for the constraints, each factory has a limited capacity.
The total number of products sent from factory 1 to all three customers should be ≤ 40.
The total number of products sent from factory 2 to all three customers should be ≤ 50.
Each customer's demand should be met.
The total number of products received by customer 1 should be ≥ 30.
Same for Customer 2 and Customer 3.
This is the complete LP problem formulation.
This is a more general form of the transportation problem formulation.
The objective function is the sum of the cost matrix times the decision variables.
The sum of each row is less than or equal to the supply capacity.
The sum of each column is greater than or equal to the required demand.
The example we examined here is also a balanced transportation problem.
This is because the total supply is equal to the total demand.
40+50=90, which is equal to 30+30+30.
This is the formulation of a balanced transportation problem.
The difference between the general transportation problem and the balanced transportation problem
is in the constraints.
These two will be changed to the equality constraints.
And the total supply is equal to the total demand.
For the balanced transportation problem, there is an algorithm called the transportation
simplex to solve it efficiently, which will be talked about in another video.
We can show the mathematical formulation in a diagram like this.
These are the supply nodes, and these are the demand nodes.
These lines with arrows represent the transportation routes.
There is a cost, cij, associated with each route.
We need to determine the amount of products, xij, that will be shipped from supply node
i to the demand node j.
For this balanced problem, the total supply is 90, and the total demand is also 90.
This is another representation of the problem using the transportation tableau.
These are the supply nodes, and these are the demand nodes.
The unit shipping cost is put in the top right corner of each cell.
For example, from Factory 1 to customer 1, the unit shipping cost is $8/product.
We need to determine the amount of products, xij, that will be shipped from supply node
i to the demand node j.
We put the decision variables in the bottom right corner of each cell.
For this balanced problem, the total supply is 90, and the total demand is also 90.
If a problem is unbalanced, we need to balance it first before we use the transportation
simplex method to solve it.
In this example, the demand of customer 1 is increased from 30 to 40.
So the total supply, which is 90, is less than the total demand, which is 100.
In order to balance the problem, we need to introduce a dummy or fake supply node, called
Factory 3, and give it a capacity 10.
Any amount sent from Factory 3 to a customer will represent the unmet demand of that customer.
For each unit of unmet demand, we introduce a penalty, which can be determined by the
financial loss related to the unmet demand.
For example, we assume the penalty for each unit of unmet demand for customer 1 is $20,
for customer 2 is $22, and for customer 3 is $23.
Then the problem is balanced.
For the tableau representation, when we introduce a dummy supply F3, we are actually adding
one row to the original transportation tableau like this.
These are the penalties, and this is the dummy supply amount.
In this example, the supply of factory 1 is increased from 40 to 50.
So the total supply, which is 100, exceeds the total demand, which is 90.
In order to balance the problem, we need to introduce a dummy or fake demand node, called
Customer 4, and give it a demand 10.
Any amount sent from a factory to customer 4 will represent the unused, remaining capacity
of that factory.
For each unused capacity, there is no extra cost involved.
Therefore, c14 and c24 are both 0.
Now the problem is balanced.
For the tableau representation, when we introduce a dummy demand C4, we are actually adding
one column to the original transportation tableau like this.
The unit costs are 0, and this is the dummy demand.
Why is the regular simplex method not very efficient in solving the balanced transportation
problem?
This is because it contains many equality constraints.
The traditional simplex algorithm will have to use the big M method to find the initial
BFS by introducing many artificial variables, which increases the complexity of the problem.
In comparison, the transportation simplex method doesn't need to introduce extra variables
and can deal with the equality constraints directly.
The first step of the transportation simplex method is to find a BFS.
This can be done by using the northwest corner method, the minimum-cost method, or vogel's
method.
They will be introduce in other videos.
Okay, that's how we formulate a balanced transportation problem and represent it in a diagram or transportation
tableau.
Thanks for watching.