Basic Concept of Linear Programming
Basic Concept of Linear Programming
Preamble: Linear programming is a mathematical modeling technique in which a linear function is optimized (maximized or minimized) when subjected to certain constraints and is used to solve everyday decision problems.
Theory
The linear programming model is quite simple from a mathematical viewpoint that outlines adequately general and practical structure to represent interdependent activities that requires production function (i.e. a flow of inputs and outputs) of various types proportional to the level of the activity where levels are supposed to be represented by non-negative numbers.
Importance of linear programming grew rapidly as its use has been widely spread to industry.
This technique has found its applications to significant areas of product mix, blending problems, personnel assignment problem, transportation problem, proficiency in operation of dam system, optimum estimation of executive compensation, agricultural applications, marketing management, manpower management, physical distribution and diet problems. Oil refineries, chemical industries, steel industries, production scheduling, inventory policies, investment portfolio, allocation of advertising budget, construction of warehouses, food processing industry etc. are also using linear programming with substantial accomplishment.
Today it is almost impossible to name an industry that is not using mathematical programming in some form, although the applications and the extent to which it is used vary greatly, even within the same industry.
Formulation of the problem
A simple problem in linear programming is one in which it is necessary to find the optimum value of a linear function subject to definite constraints.
Initially, a problem is stated in a linear programming form which requires defining the variables involved, establishing relationships between them and formulating the objective function and the constraints.
The variables that enter into the problem are called decision variables.
We illustrate this through following example:
Example: A manufacturer produces two types of models M1 and M2. Each M1 model requires 4 hours of grinding and 2 hours of polishing; whereas each M2 model requires 2 hours of grinding and 5 hours of polishing. The manufacturer has two grinders and 3 polishers. Each grinder works for 40 hours a week and each polisher works for 60 hours a week. Profit on an M1 model is 3 and on an M2 model is 4. Whatever is produced in a week is sold in the market. How should the manufacturer allocate his production capacity to the two types of models so that he may make the maximum profit in a week.
Explanation: Let x1 be the number of M1 models and x2 be the number of M2 models produced per week, then the weekly profit (in) is
Z = 3x1 +4x2___(1)
To produce these number of models the total number of grinding hours needed per week = 4x1 + 2x2
and the total number of polishing hours required per week = 2x1 + 5x2
Since the number of grinding hours available is not more than 80 and the number of polishing hours is not more than 180, therefore,
4x1 + 2x2 =< 80___(2)
2x1 + 5x2 =< 180___(3)
Now since, the negative numbers of models are not produced thus we have
x1 >= 0 and x2 >= 0___(4)
Hence this allocation problem is to find x1 and x2 which maximize Z = 3x1 +4x2 subject to
4x1 + 2x2 =<80
2x1 + 5x2 =<180
x1 >= 0 , x2 >=0
Here, expression (1) showing the relationship between the manufacturer’s goal and the decision variables, is called the objective function.
The inequalities (2), (3) and (4) are called the constraints.
Thus the objective function and the constraints being all linear, it is called as a linear programming problem(LPP).
Jaya Bhushan
Assistant Professor
Department of Mathematics
Patna Women’s College (Autonomous)
Mail-ID: jaya.bhushan946@gmail.com
