LPP - Linear programming problem Introduction

We are already familiar with graphical reorientation of linear equations and inequations. This chapter describes the application of linear equations and inequations in solving different kinds of practical problems. Let us consider few examples to understand what we mean by linear programming problem.

Example1:

Find two positive numbers whose sum is at least 15 and whose difference is at the most 7 such that their product is maximum.

Before solving this problem, we have to state the problem

Step 1:

We have to choose two positive numbers. Let the two positive numbers be x and y. This x and y are decision variables.

Step 2:

Our object is to minimise the product xy.

Let Z = xy. We have to maximise Z.

Step 3:

We have the following conditions on the variables x and y.

a) Sum of the numbers is atleast 15

i.e., x + y 15

b) Difference of the numbers is at most 7

i.e., x - y 7

c) Since the x and y should be positive, we have two more conditions

x > 0, y > 0

We call Z as objective function and the liner inequations

x > 0, y > 0 as Linear constraints.

The mathematical model for this problem is maximize the objective function Z = xy.

Subject to the constraints

x > 0, y > 0

Example 2:

A decorative item dealer deals in only two items - wall hangings and artificial plants. He has 15,000 dollars to invest and a space to store all the most 80 pieces. A wall hanging costs him 300 dollars and an artificial plant 300 dollars. He can sell a wall hanging at a profit of 50 dollars and an artificial plant at a profit of 18 dollars. Assume that he can sell all the items that he buys. Let us make a mathematical model to maximize his profit with the given conditions.

Let the person sells x number of wall hangings and y number of artificial plants.

We tabulate the given data as follows:

Since the object in this problem is to maximise the profit, let

Z = 50x + 18y be the profit function.

Since the dealer has space availability of (to store) 80 pieces

Since he can invest 15,000 dollars, his cost cannot be more than 15,000 dollars

Therefore 300x + 150 y  £  15,000 dollars

The mathematical model for this problem is

Maximize Z = 50x + 18y (objective function)

Subject to the condition

with non-negativity conditions

Note that in both the examples the conditions are linear inequations; these mathematical models which tells to optimise (minimize or maximise) the objective function Z subject to certain condition on the variables is called a Linear programming problem (LPP).

During World War II, the military managements in the U.K and the USA engaged a team of scientists to study the limited military resources and form a plan of action or programme to utilise them in the most effective manner. This was done under the name 'Operation Research' (OR) because the team was dealing with research on military operation.

In 1947, George B. Dantzig developed the first mathematical technique of linear programming.

To get the best deal in any venture, one must make the best (optimum) use of one's resources such as time, money, labour etc. When resources are limited, they are constraints. Linear programming seeks to optimise a function. (e.g., maximise the profit or minimise the cost) subject to constraints such as limited time or man power.