Linear Programming

Linear Programming is an Operations Research technique which originated during the early 1950s. Having diverse practical applications, this technique has benefited immensely various organizations in their production and other operations. Prof. G B Dantzig is one of the pioneers in formulating the procedure of linear Programming.

This technique can be applied in various situations: long range planning, production planning, warehousing decisions, physical distribution, marketing and product-mix decisions, Fluid blending problems, exploration of oil deposits, purchasing decisions, quality control decisions, material utilization decisions etc.


The basic problem solved by Linear Programming is that of optimizing either profit or total costs or some other utility function. It takes into consideration the limitations or constraints on the availability or usage of different resources such as manpower, machinery, materials, time and money and also other limitations and constraints such as those existing in the market (e.g. only so many units of a product could be sold) or specification for quality such as the maximum or minimum limits on the performance characteristics of particular product etc. In short Linear Programming deals with optimizing a desired objective under a situation where there are various constraints. Most of the management problems are optimal decision making problems made under the various limitations. Therefore, Linear Programming rightly attracts the attention of practicing executives.
The solution of a Linear Programming problem involves:

(1) Expressing the objective in an algebraic form involving the decision variables in algebraic notations. This expression is called the objective function, which is either to be maximized or minimized.
(2) Expressing the constraints in algebraic inequalities involving the decisions variables in algebraic notations.
(3) The above two steps complete the formulation of the Linear Programming problem. This, now, is solved for the determination of the optimal values of the decision variables by means of a mathematical procedure. Simple Linear Programming problems can be solved as a graphical procedure.

Formulation of a Linear Programming Problem:

Suppose a Company produces two products X and Y, both of which require a particular raw material and a particular machine Product X requires 4 machine hours and 3 kg of the raw material per unit of the product, and product Y requires 2 machine hours and 6 Kg of raw material per unit of the product. Suppose that the availability of the raw material and machine hours is limited. The raw material is available to the maximum extent of only 240 Kg per month and the machine hours are available to a maximum extent of only 200 machine hours per month. Each of the products X and Y contribute to the profit margin by Rs 7 and Rs 9 respectively per unit of the product. How many units of products X and Y should the company produce every month?

In the above problem, the company has to decide on the quantities of X and Y which are the decision variables and this is to be done so as maximize the profit margin which is the objective under the limitations or constraints of resources. Linear Programming problems typically have three elements:

(1) Decision variables, the determination of whose value is the problem to be solved
(2) Objective function, which is to be either maximized or minimized (e.g. maximization of profits or minimization total costs, as the case may be)
(3) Constraints or limitation or conditions related to the decision variables.

Example: Let X and Y denote the quantities of the products X and Y. The Objectives Function is given by: maximize profit contribution.

P = 7X + 9Y;

Subjects to the constraints:

4X + 2Y ≤ 200 …..constraint for machine hour;
3X + 6Y ≤240 …. constraint for raw materials;

X ≥ 0
Y ≥ 0

The last two constraints express that the quantities of X and Y cannot be negative. These are known as non negativity constraints which are necessary for all Linear Programming problems.

Having formulated the problem thus we shall try to solve the problem of the decision variables X and Y means of a graphical technique.

Taking the first constraints of machine hours, let us convert it into the following:

Y + 2X ≤ 100

Similarly, the second constraint of raw materials can be converted into

Y + 0.5X ≤ 40

A graph can be plotted on the basis of P= 7X + 9Y. The solution evolved for a maximum profit margin would be between 400 to 500 percent for which the values of X = 40 units, Y = 20 units. The plotting of graph is not within the scope of this article. The other method to obtain an optimum solution is through differentiation (calculus).