# Posts Tagged: "Linear Programming"

Transportation and assignment models are special purpose algorithms of the linear programming.  The simplex method of Linear Programming Problems(LPP)  proves to be inefficient is certain situations like determining optimum assignment of jobs to persons, supply of materials from several supply points to several destinations and the like. More effective solution models have been evolved and these are called assignment and transportation models.

The transportation model is concerned with selecting the routes between supply and demand points in order to minimize costs of transportation subject to constraints of supply at any supply point and demand at any demand point.  Assume a company has 4 manufacturing plants with different capacity levels, and 5 regional distribution centres.   4 x 5 = 20 routes are possible.  Given the transportation costs per load of each of 20 routes between the manufacturing (supply) plants and the regional distribution (demand) centres, and supply and demand constraints, how many loads can be transported through different routes so as to minimize transportation costs?  The answer to this question is obtained easily through the transportation algorithm.

Similarly, how are we to assign different jobs to different persons/machines, given cost of job completion for each pair of job machine/person?  The objective is minimizing total cost.  This is best solved through assignment algorithm.…

Initial basic feasible solution of a transportation problem can be obtained by any of the following methods:

1. North–west corner rule

The major advantage of the north–west corner rule method is that it is very simple and easy to apply. Its major disadvantage, however, is that it is not sensitive to costs and consequently yields poor initial solutions. The steps involved in determining an initial solution using north–west corner rule are as follows:

Step1. Write the given transportation problem in tabular form (if not given).

Step2. Go over to the north-west corner of the table. Suppose it is the (i, j)th cell.

Step3. Allocate min (ai, bj) to this cell. If the min (ai , bj) = ai, then the availability of the ith origin is exhausted and demand at the jth destination remains as bj-ai and the ith row is deleted from the table. Again if min (ai, bj) = bj, then demand at the jth destination is fulfilled and the availability at the ith origin remains to be ai-bj and the jth column is deleted from the table.…

The basic steps of the transportation method are:

1. To set up the transportation table.

2. Examine whether total supply equals total demand. If not, introduce a dummy row/column having all its cost elements as zero and Supply/Demand as the (+ive) difference of supply and demand.

3. To find an initial basic feasible solution. An initial BFS for a TP with m sources and n destinations must include m+n–1 basic variables. This initial solution may or may not be optimal. Thus, the initial solution in the transportation method serves the same purpose as the initial solution in the simplex method. There are a few methods to find the initial solution. The widely used methods for finding a initial solution are:

• North West corner rule
• Row minima method
• Column minima method
• Matrix minima method (Lowest cost entry method)
• Vogel’s approximation method (unit cost penalty method) (VAM)
• 4. To obtain an optimal solution by making successive improvements to initial basic feasible solution until no further decrease in the transportation cost is possible. An optimal solution is one where there is no other se of transportation routes that will further reduce the total transportation cost. Thus, we have to evaluate each unoccupied cell in the transportation table in terms of an opportunity of reducing total transportation cost.…

Operations Research approach of problem solving

Optimization is the act of obtaining the best result under any given circumstance. In various practical problems we may have to take many technical or managerial decisions at several stages. The ultimate goal of all such decisions is to either maximize the desired benefit or minimize the effort required. We make decisions in our every day life without even noticing them. Decision-making is one of the main activity of a manager or executive. In simple situations decisions are taken simply by common sense, sound judgment and expertise without using any mathematics. But here the decisions we are concerned with are rather complex and heavily loaded with responsibility. Examples of such decision are finding the appropriate product mix when there are large numbers of products with different profit contributions and production requirement or planning public transportation network in a town having its own layout of factories, apartments, blocks etc. Certainly in such situations also decision may be arrived at intuitively from experience and common sense, yet they are more judicious if backed up by mathematical reasoning. The search of a decision may also be done by trial and error but such a search may be cumbersome and costly.…

Transportation problem is a particular class of linear programming, which is associated with day-to-day activities in our real life and mainly deals with logistics. It helps in solving problems on distribution and transportation of resources from one place to another. The goods are transported from a set of sources (e.g., factory) to a set of destinations (e.g., warehouse) to meet the specific requirements. In other words, transportation problems deal with the transportation of a single product manufactured at different plants (supply origins) to a number of different warehouses (demand destinations). The objective is to satisfy the demand at destinations from the supply constraints at the minimum transportation cost possible. To achieve this objective, we must know the quantity of available supplies and the quantities demanded. In addition, we must also know the location, to find the cost of transporting one unit of commodity from the place of origin to the destination. The model is useful for making strategic decisions involved in selecting optimum transportation routes so as to allocate the production of various plants to several warehouses or distribution centers.

Suppose there are more than one centers, called ‘origins’ , from where the goods need to be transported to more than one places called ‘destinations’ and the costs of transporting or shipping from each of the origin to each of the destination being different and known.…

We see that the primal and the dual of linear programming are related mathematically, we can now show that they are also related in economic sense. Consider the economic interpretation of the duality of linear programming — first for a maximisation problem and then for a minimisation problem.

The maximisation problem: Consider the following linear programming problem.

The optimal solution to this problem dives production of 18 units of Xi and 8 units of x2 per week. It yields the maximum prof of a Rs. 1000,

Maximise Z = 40x1 + 35x2, Subject to

2x1 + 3X2 < or = 60, Raw materials constraint per week.

4x1 + 3X2 < or = 96, Capacity constraint per week.

x1,x2 > or = 0

The optimal solution to this problem gives production of 18 units of x1 and 8 units of x2 per week. It yields the maximum profit of a Rs. 1000.

Now, to rent the facilities of the firm for one week, the firm has 60 kg of raw material and 96 capacity hours. If we let yl represent the rent per kg of raw material and y2 the rent per capacity hour, the firm would receive a total rent equal to 6Oy1 + 96y2.…