In this video, I will be formulating and solving this transshipment problem involving shipping
items from 3 plants to 2 Warehouses, and from those 2 warehouses to 3 Distribution
centres.
In transportation problems, we ship directly between origins and destinations.
But transshipment refers to shipping from origins through transfer points
to final destinations.
In essence, the transshipment problem is a transportation problem that has
intermediate points inserted between origins and destinations.
These intermediate points are referred to as transshipment nodes.
They are temporary locations as the goods only pass through them.
Back to the transshipment problem we want to formulate an LP for.
The origins are the 3 plants.
with capacities or supply values of 600, 500, and 700 respectively.
The two Warehouses will be the transhipment nodes that the goods will pass through
on their way to their destinations.
The nodes are labelled 4 and 5 here in continuation from node #3 here.
The distribution centres are the destinations, with demand quantities
350, 600, and 800 respectively.
The plan is to ship from the plants to the warehouses,
then from the warehouses to the distribution centres.
The costs of shipping from Plant 1 to the two warehouses are 6 and 5,
4 and 7 for Plant 2, and 8 & 5 for Plant 3.
Similarly, from Warehouse 1 to the destination centres,
the costs are 6, 7, and 9 and 3, 6 and 12 for warehouse 2.
Thus, we have completed the Network representation of the transshipment problem.
For the LP formulation, let’s begin by defining the decision variables:
Let Xij be the number of units shipped from node i to node j.
The objective is to minimize total shipping costs
which we write as follows For example, it costs $6 to ship a unit from
node 1 to node 4.
So, 6X_14 gives the total cost of shipping between node 1 and node 4.
Similarly, we have 5X_15 for the total cost of shipping between nodes 1 and 5.
We continue in that fashion, ensuring that all these arrows (which we call arcs) are
represented …till we get to 12X_58 here.
Next, we write a constraint for each of the nodes in the network.
Note that total Supply is 1800 and total Demand is 1750.
Since supply is greater than demand, we will not ship all items from the plants,
so the Supply constraints will be “less than or equal” constraints.
Thus, from node 1 we cannot ship more than 600 units to nodes 4 and 5,
and we write: X_14 + X_15 ≤ 600.
Similarly for node 2, X_24 + X_25 ≤ 500.
And for node 3, less or equal to 700.
Nodes 4 and 5 are the warehouses which are Transshipment nodes
so whatever they receive from any of the 3 Plants, they ship out to the distribution
centres.
Therefore, whatever node 4 receives from nodes 1, 2 and 3
must equal what it gives to nodes 6, 7, and 8.
We can rewrite that as follows so that all variables are on the left.
Similarly for node 5, X_15 + X_25 + X_35 must equal X_56 + X_57
+ X_58 which can also be written as follows:
Next for the destinations that is, the distribution centres
we have demand amounts which can be fully met because total demand is less than total
supply.
Therefore, the destination constraints will all be equality constraints.
Thus, for node 6, we have X_46 + X_56 = 350 For node 7, X_47 + X_57 = 600
and X_48 + X_58 = 800 for node 8 Since we can’t ship negative number of units,
we add the nonnegativity constraint Xij ≥ 0 for all i and j.
The LP formulation for the problem is now complete.
Now, suppose the demand at node 6 increases from 350 to 400.
Then total supply equals total demand what is called a balanced transhipment problem
As a result, we can rewrite the supply constraints as “equality” constraints.
But if Demand at node 6 increases to 500, the problem becomes unbalanced again
as total demand will be greater than total supply.
Therefore, demand will not be fully met at some nodes.
That will require changing Demand constraints to “less than or equal” constraints.
Going back to our original model we sometimes have cases where we could ship
directly between origins and destinations, or between any 2 nodes.
For example, suppose Node 3 can ship directly to node 6,
then we add X_36 to the left side of node 3 constraint,
We also do the same for node 6 constraint.
Back to the original model.
Suppose instead that plant 1 can ship to plant 2,
then we add X_12 to the left side of constraint 1 to account for the additional outgoing route.
But for constraint 2, we add X_12 to the right side since the amount shipped from plant 1
will be added to the already existing 500 units at node 2.
Rewriting constraint 2, we see that X_12 has a negative sign while others are positive
as indicated by the direction of the arcs touching node 2.
We could also have capacitated routes, in which case the amount that can be shipped
along a route is constrained.
For example suppose node 2 cannot ship more than 200 units
to node 4, we will add the constraint X_24 ≤ 200 to
the model.
And if node 3 must ship at least 150 units to node 5
we will add X_35 ≥ 150 to the model.
In some cases, one or more transshipment nodes may also be capacitated.
For example suppose due to space limitation
node 4 cannot handle more than 1000 units.
Then we can write X_14 + X_24 + X_34 ≤ 1000 Since, for transhipment nodes,
total inflows equal total outflows, then we could as well say that the total units
leaving node 4 must also be less or equal to 1000.
Finally, suppose shipment is not permitted through certain routes.
For example, from node 5 to node 8, we could omit the corresponding variable from
the model or add a constraint that sets the variable to
0.
Let’s now solve the original model in LINDO.
If you’re not familiar with LINDO please see description for a video on how to install
and use it.
On clicking solve, no sensitivity
and close we have the solution in the reports Window
here.
We have the objective function value here and the amounts to ship between nodes here.
And that’s it for this video.
Thanks for watching.