Introduction
The allocation of scarce resources is a universal issue, and the goal is usually to do so in an optimal way. The ability to transport goods at an optimal cost is of particular interest to both businesses and individuals. Linear programming is a method of allocating resources in an optimal way; and it is one of the most widely used tools for decision making in manufacturing industries.
In the term linear programming, programming refers to mathematical programming. In this context, it refers to a process which allocates resources in the best possible (optimal) way; to minimize costs or to maximize profits. In linear programming, the resources to be allocated are known as decision variables. The criterion for choosing the best values of the decision variables is known as the objective function. Restrictions on the availability of resources form what is known as a constraint set.
The word linear indicates that the criteria for choosing optimal values of the decision variables can be described by a linear function of these variables; i.e., a function involving only the first powers of the decision variables, and no products of the variables. Thus the entire problem can be expressed in terms of straight lines, planes, or similar geometric figures. In addition to the linear requirements, there is a restriction of non-negativity; i.e., it is impossible to have negative resources.
One of the most important applications of linear programming has been in the physical distribution of products, commonly referred to as transportation problems. Essentially, the purpose is to minimize the cost of shipping goods from one location to another in such a way that the needs of each destination is met and each shipping location operates within its capacity.
History
Formulation & Mathematical Model of a Transportation Problem
The best way to go about understanding the mathematics behind the transportation problem is to think of a real-life example. Let’s say a clothing company has m number of warehouses, where the goods are produced. The company also has n number of outlet stores, where the goods will be sold. We know there exists m number of warehouses and n number of outlet stores, but we need to explicitly label how many there are. We label the warehouse as: $ i=1,2,...,m $ And we label the outlet stores as: $ j = 1, 2, ... , n $ Now this is where Supply and Demand comes into play. The warehouses have a level of supply and the outlet stores have a level of demand that need to be met. We can label the supply from the warehouses as $ a_i $ and the demand at the outlet stores as $ b_j $. Now the question is what are we trying to calculate? In the simplest of terms, the transportation problem is an optimization problem. We want to get goods from, in our case, warehouses to the outlet stores at minimum cost. Knowing this, and assuming that shipping cost is linear, we can define shipping cost from the ith warehouse to the jth outlet store as $ c_{ij} $. The last thing that needs to be defined is the number of units transported from the ith warehouse to the jth, which we can call $ x_{ij} $. So now we have all of the terms we need to begin solving the problem.
A quick recap of what is written above:
- m and n are defined as the number of sources and the number of destinations, respectively (warehouses and outlet stores in our example)
- The goods produced at the ith source is defined as $ a_i $
- The demand at the jth destination is defined as $ b_j $
- $ c_{ij} $ is defined as the shipping cost when being shipped from i to j
- $ x_{ij} $ is defined as the number of units being shipped from source i to destination j
Note: $ x_{ij}\geq 0 $; you can’t have a negative number of units.
Example
Conclusion
