Optimization

Self-use Tool

Sample Data - Linear Programming

Sample Data - Transportation Problem

Sample Data - Assignment Problem

Sample Data - Shortest Path Analysis

We discussed Prescriptive Analytics in detail, and mentioned that it refers to Linear Programming, Integer Programming, Heuristics, Simulation etc.

We would apply Linear Programming for a Bank. The data has been attached as Sample Data above. It would prescribe the optimal mix in terms of number of customer for multiple Investment Instruments. As an example, it would suggest the number of customers to be served with Savings, Short Term Deposits, Long term deposits and so on, maximizing its returns, within the numerous Business and Statutory Constraints.

Simulation has been covered with an example on "what-if Analysis".

Apart from this, we would apply three more applications, which are variants of Linear and Integer Programming, developed for specific problems.

Transportation Problem is a specific type of Linear Programming Problem. Linear Programming Problems are solved by a Technique called SIMPLEX METHOD. Transportation Problems are solved by a simple variant of Simplex Method, called Transportation Method. It is used in cases, where certain products can be supplied from multiple SOURCES, to multiple DESTINATIONS. With each combination of Source and Destination, a certain Cost is associated. The objective is to minimize the cost associated in Transportation. The transported object could be material or man.

Assignment problem is also a special case of Linear Programming. In fact it is one of the special cases of Transportation problems. It is applicable in cases where multiple person/machines are available for multiple jobs, with each person/job pair having a different cost or time. The objective is to minimize the total cost or time of completing all the jobs by all the persons. An important characteristic of the assignment problem is that the number of person/machine (similar to Sources) is equal to number of job (similar to destinations). In case they are unequal, then a dummy job or dummy person is added with zero cost/time to make it a balanced problem. The most widely used technique for Assignment problem is called Hungarian Method, as it was developed by a Hungarian mathematician D. Konig.

In Logistics and Transportation, it is often necessary to calculate the Shortest Path between every pair of locations in a Network. This objective is solved by two algorithms, Dijkstra's and Floyd's. Usually the network involves n vertices, representing N different locations. The to and fro distances need not be same for pair i, j of vertices. Hence distance from i to j can be different than the same for j to I (a detour, restricted movement etc.). If movement between a pair is not possible, then that entry is depicted as INF in the matrix (way to show impossible movement). These algorithms provide the shortest path between every pair of locations.  Floyd's algorithm is computationally efficient than Dijkstha's and used more often.

As a demonstration on Shortest Path Analysis, Please watch the Video provided at the top right. It illustrates its use on finding the shortest path for any pair out of 21 European Cities.