What is Linear Programming?

The word “Linear Programming” is made up of two words, linear and programming. The word ‘linear’ means we are getting a linear equation in formulation of some problem. The ‘linear’ means that the equation is of single degree in one or two variables as an equation of one or two variables in single degree in two-dimensional geometry will always give you a straight line (hence linear).

The word ‘programming’ gives us an impression that the solution shall involve mathematical techniques which are used in computer modeling which allow us to find the best possible solution of the problem after allocation of limited resources available, in order that maximum profit or minimum cost could be achieved subject to given constraints.

Things will be clear to you when you see this example.

A company manufactures two types of screws: type A and type B. All the screws have to pass through a threading machine and a slotting machine. The box of type A screws requires 4 minutes on the threading machine and 6 minutes on this slotting machine. A box of type B screws requires 6 minutes on the threading machine and 3 minutes on this slotting machine.

In a week, each machine is available for 4 hours on any day. On selling these screws, the company gets a profit of Rs. 7 per box on type A screws and Rs. 10 per box on type B screws. Formulate this problem as a LPP to maximize the profit to the company.

The available resources are: Machine for threading and machine for slotting with required time of each type of machine for the two types of screws.

The constraints have been given in terms of duration of availability of each machine for a day.

Profits on sale of two types of screws have been given.

Let us formulate the linear programming problem.

Let x and y be the numbers of screws of type A and type B respectively.

Constraints, obviously in terms of given parameters, are:

1. x ≥ 0; y ≥ 0.

2. For type A screws, the threading machine requires 4 min, and slotting machine requires 6 min. 4x + 6y ≤ 240; and, 6x + 3y ≤ 240 {Availability of 4 hours = 240 Minutes}

(The problem has been solved here)

Let us say net profit is z, which has to be maximized given the constraints above.

Hence, Max z = 7x + 10y, subject to two conditions given above.

This way, we have formulated a linear programming problem. Later we shall discuss as to how to solve it. But before solving, let us acquaint ourselves with some important nomenclature. The first and core word is “Optimization”.