Duality in linear programming

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

Formulation of Linear Programming Problem

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

Introduction to Linear Programming (L.P)

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. ManufacturingContinue reading