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.
• Manufacturing problem: To manufacture goods (say furniture) so as to give maximum profits bearing in mind the time constrain and the market demand for the goods.
• Advertising application: To achieve the best possible exposure to the client’s product at the lowest possible advertising cost.
• Portfolio selection: Select specific investments among available alternatives so as to maximise return or to minimise risk.
• Staffing problem: Develop a work schedule that allows say, a large restaurant or a hospital or a police station to meet their man power needs at all hours with minimum number of employees.
• Trim loss problem: Find the combination of components to be produced from standard sheets in order to keep trim loss to a minimum.

An extension of application of linear programming technique is found in transportation and assignment problems.

TERMINOLOGY OF LINEAR PROGRAMMING:

A typical linear programme has the following components:

1. An objective function.
2. Constraints or restrictions.
3. Non-negativity restriction.

And the following terms are commonly used to describe a typical L.P.P.

• Decision variables: Decision variables are the unknowns whose values are to be determined from the solution of the problem. E.g. decision variables in the furniture manufacturing problem are say the tables and chairs whose values or actual units of production are to be found from the solution of the problem. These variables should be inter-related in terms of consumption of resources. For example, both tables and chairs require carpenter’s time and also wood and other resources and any change in the quantity produced of table affects the production level of chairs. Secondly the relationship among the variables should be linear.

• Objective function: A firms objectives are expressed as a function of decision variables. It represents the mathematical equation of the goals of the firm in terms of unknown values of the decision variables. Thus if the objective is to maximise net profits in a furniture manufacturing problem, then profits are expressed as function of (dependent on) the net per unit profits of table and chair and the number of units produced (of tables and chairs).

• Constraints: A constraint represents the limitations imposed on the values of decision variables in the solution. These limitations exist due to limited availability of resources as well as the requirements of these resources in the production of each unit of the decision variable. For example manufacturer of a table requires certain amount of time in a certain department and the department works only for a given period, (say 8 hours in a day for 5 days in a week). The constraints may represent some other type of limitations also. As in the production of a commodity the market demand can put an upper limit on the value of the decision variable in the optimal solution. Thus, the constraints define the limits within which a solution to the problem must be found. These constraints must be capable of expression in mathematical form of an equality or inequality.

• Linear relationships: Linear programming deals with problems in which the objective function and the constraints can be expressed as linear functions. Hence, when the problem is solved graphically, in a two variable case the constraints the objective function, gives a straight line on a two dimensional graph.

• Equations and inequalities: Equations are represented by = (equality) sign. They are specific statements. But many business problems cannot be neatly expressed in equations (called strict equality). Instead of precise statements, we may have only minimum or maximum requirements or availability. For example we may state that available labour time is 40 hours per week, hence, labour time used in production should be less than or equal to 40 hours per week. We thus need inequalities. Less than or equal to relationship is written as () and () sign indicates greater than or equal to relationship. Most of the constraints in a LPP are expressed as inequalities. They indicate the upper or the lower limits of resource use or production level. They do not express exact levels. Thus, they allow for many possibilities of the optimal values of the decision variable i.e. more than one combination of the decision variables may give the same optimal value of the objective function.

• Non-negativity restrictions: Linear programming technique is used to obtain solution to real world problems. The solution to the problem implies finding values of the decision variables. These must be non-negative. As one cannot think of manufacture of -4 tables or -6 chairs i.e. negative production. Hence, decision variable should assume either zero or positive values. If we denote two decision variables as X1 and X2 then the non negativity restriction is expressed as X1 > = 0; X2 >= 0.

This site uses Akismet to reduce spam. Learn how your comment data is processed.