Linear Programming Problems

Linear Programming is a technique of obtaining optimum solution to a problem out of many solutions. It has a specific objective such as maximizing profit or minimizing the expenses. This technique is typically applied to solve decision making problems in business; but its origin is in WWII. It was developed to make the best (optimum) use of available resources in the war.

• Equalities and Inequalities

The equation ${3x + 4y = 11}$ is satisfied by ${x=1, y= 2}$ and the inequation ${3x + 4y > 11}$ is satisfied by ${x=1, y = 4}$.

In ${XY}$ plane, a linear equation represents a straight line and an inequation (or inequality) represents a region.

• Terms Associated with Linear Programming

An ${LPP}$ contains a set of inequations, which consist of many variables..

1) Objective Function – This is a linear function of variables, which is to be optimized. (Generally denoted by ${z}$ or ${c}$)

2) Constraints – These are the restrictions or conditions which are always satisfied by the optimum solution. These are in the form of linear equations or linear inequations.

3) Decision Variables – The optimum solution requires a set of values of decision variables. Generally, in an ${LPP}$, except the objective functions, all other variables are decision variables.

Virtually, any business can be modeled using linear programming technique, but the model should have a firm background.

• Formulation of LPP

It involves expressing the information in the problem in terms of decision variables, constraints and objective function. It involves following steps :

I) Identifying the decision variables, say ${x,y}$.

II) Identifying the constraints and expressing them in linear equations/ inequations.

III) Identifying and expressing the objective function in terms of decision variables.

IV) Adding non-negativity constraints (if any). These are set when the decision variables are defined. The number of products to be made, number of persons to be employed can never be negative. So, these will either be ${0}$ or positive. Hence the name non-negativity constraints.

• Solving the LPP (Graphical Methods)

It should be noted that there can be many values of decision variables, which satisfy the constraints. Such a set of decision variables is known as solution to LPP.

A solution satisfying the non-negativity constraints is known as a feasible solution.

A feasible solution, which optimizes the objective function is the optimal feasible solution. This is the required solution to the problem.

When the constraints are plotted on a graph, we get a feasible region, which is the set of all feasible solutions. According to convex polygon theorem, the objective function attains its optimum value on at least one of the vertices of the convex polygon formed by the constraint equations/ inequations.

• Corner Point Method

This method is easy to implement. Having obtained the convex polygon, one has to find the coordinates of the vertices of the polygon either by solving the equations of intersecting lines simultaneously/ by inspection.

At each of the vertices, we find the value of the objective function. That vertex, which optimizes the objective function, gives the required solution.