Linear Programming

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: Step 1. Write the given transportation problem in tabular form (if not given). Step 2. Go over to the north-west corner of the table. Suppose it is the (i, j)th cell. Step 3. 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 Continue reading

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 Continue reading

FORMULATION OF LINEAR PROGRAMMING PROBLEM (LPP): Formulation of a Linear Programming Problem involves constructing a mathematical model from the given data. This can be done only if the following requirements are met: There should be a clearly identifiable objective and it should be measurable in quantitative terms. E.g. In a manufacturing problem the objective can be maximisation of profit or minimisation of cost. The resources to be allocated in the problem should be identifiable and quantitatively measurable. E.g. The use of labour time, or raw material in the manufacturing process should be clearly stated. The relationships representing the objective function and the constraints equations must be linear. There should be a series of feasible alternative courses of action available to the decision maker. These are determined by the resource constraints. When all the above mentioned conditions are satisfied the problem can be expressed as L.P. problem. Then solve it for Continue reading

Corresponding to every linear programming problem, there is another linear programming problem. The given problem is called the primal and the other its dual. Although the idea of duality is essentially mathematical, it has important interpretations. This can help managers in answering questions about alternative courses of action and their effect on values of the objective function. When the primal problem is of the maximisation type the dual is of the minimisation type and vice versa. It is an interesting feature of the simplex method that we can use it to solve either the original problem – the primal – or the dual. Whichever problem we start out to solve, it will also give us the solution to the other problem. Consider the following general linear programming problem. Maximise Z = c1x1 + c2x2, Subject to a11x1 + a12x2 <or = b1 a21x1 + b22x2 <or = b2 x1,x2 > Continue reading

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 Continue reading

The mathematical definition of linear programming (L.P.) can be stated as – “It is the analysis of problems in which a linear function of a number of variables is to be maximized (minimized), when those variables are subject to a number of restraints in the form of linear inequalities”. Linear programming models thus belong to a class of mathematical programming models concerned with efficient allocation of resources to known activities with the objective of meeting a desired goal. Organizations can have many goals. Hence, a wide variety of problems can be efficiently solved using L.P. technique. Here are a few examples: A product mix problem: Decide the combination of various product quantities to maximise profit or to minimise production cost. Allocation of bank funds: To achieve highest possible returns. This should be achieved within liquidity limits set by RBI and maintaining flexibility to meet the customers demand for loans. Manufacturing Continue reading