Class 12 Chapter 12 (Linear Programming) Class Notes

 Linear Programming

Introduction:

Optimization is the way of life. We all have finite resources and time and we want to make the most of them. Different type of problems which seek to maximize or minimize profit or cost, form a general class of problems called optimization problems. So, an optimization problem may involve finding maximum profit, minimum cost, or minimum use of resources etc.

Linear programming problems are one of the important class of optimization problem. Linear Programming is a mathematical modeling technique in which a linear function is maximized or minimized when subjected to various constraints. A typical example would be taking the limitations of materials and labor, and then determining the best production levels for maximal profits under those conditions.

In general, a linear programming problem is specified as follows:

Given:

(i) n variables x₁, x₂, x₃,... ,x_n.

(ii) m linear inequalities in these variables.

E.g., 2x₁ + 5x₂ ≤ 10, 0 ≤ x₁ ≤ 2, etc.

(iii) We may also have a linear objective function.

E.g. Maximize/Minimize 3x₁ + 5x₂ + 7x₃

Goal: Find values for the x_i’s that satisfy the constraints and maximize/minimize the objective function.

 

Linear Programming Problem and its Mathematical Formulation:

Formulation of an LPP refers to translating the real-world problem into the form of mathematical equations which could be solved. It usually requires a thorough understanding of the problem.

Let us take an example to illustrate the formulation of linear programming problem in various different situations.

Example: Two food stuffs F₁ and F₂ contain vitamins A, B, C. The minimum daily requirements of these vitamins for a certain diet are 3 mg of A, 50 mg of B and 40 mg of C. One unit of the food -stuff F₁ contain 1 mg of A, 25 mg of B and 10 mg of C whereas one unit of the food-stuff F₂ contains 1 mg of A,

10 mg of B and 20 mg of C. The cost of one unit food-stuff F₁ is Rs 1 and that of F₂ is Rs 2. Formulate the problem as a linear programming problem.

Solution:

Let x units of F₁ and y units of F₂ are used in the diet.

Since 1 mg of F₁ contains 1 mg of A and one unit of F₂ contains 1 mg of A and the minimum requirement of A is 3 mg.

Therefore, x + y ≥ 3

Similarly for vitamins B and C, we have

25x + 10y ≥ 50 and 10x + 20y ≥ 40

Also, x ≥ 0, y ≥ 0

The cost of x units of F₁ and y units of F₂ is x + 2y

Since the cost is to be minimized, therefore the LPP is

Minimize Z = x + 2y 

Subjected to

x + y ≥ 3

25x + 10y ≥ 50

10x + 20y ≥ 40

x ≥ 0, y ≥ 0

This is the required LPP.

•  Linear function Z = x + 2y, which has to be minimized is called a linear objective function.
•  Variables x and y are called decision variables.
•  The linear inequalities or equations or restrictions on the variables of a linear programming problem are called constraints. So, x + y ≥ 3, 25x + 10y ≥ 50, 10x + 20y ≥ 40 are constraints.
•  The conditions x ≥ 0, y ≥ 0 are called non-negative restrictions.

 Some important Definition:

•  A set of values of the decision variables which satisfy the constraints of a LPP is called a solution  of the LPP.
•  A solution of a LPP which also satisfy the non-negativity restrictions of the problem is called its feasible solution. The set of all feasible solutions of a LPP is called the feasible region.
•  Any point outside the feasible region is an infeasible solution.
•  A feasible solution which optimize (maximize or minimize) the objective function of a LPP is  called an optimal solution of the LPP.

 Graphical method of solving linear programming problems:

 The graphical method for solving linear programming problems is applicable to those problems which involve only two variables. This method is based upon a theorem called extreme point theorem which is stated as follows:

Corner Point Method:

 This method comprises of the following steps:

 

1. Find the feasible region of the linear programming problem and determine its corner points (vertices) either by inspection or by solving the two equations of the lines intersecting at that point.
2. Evaluate the objective function Z = ax + by at each corner point. Let M and m respectively denote the largest and smallest values of these points.
3. (i) When the feasible region is bounded, M and m are the maximum and minimum values of Z.

    (ii) In case, the feasible region is unbounded, we have:

4. (a) M is the maximum value of Z, if the open half plane determined by ax + by > M has no point in common with the feasible region. Otherwise, Z has no maximum value.

(b) Similarly, m is the minimum value of Z, if the open half plane determined by ax + by < m has no point in common with the feasible region. Otherwise, Z has no minimum value.

Problem:

Maximize Z = 3x + 4y

Subject to the constraints:

x + y ≤ 4, x ≥ 0, y ≥ 0

Solution:

The feasible region determined by the constraints x + y ≤ 4, x ≥ 0, y ≥ 0 is as follows:

                                                          

The corner points of the feasible region are O (0, 0), A (4, 0), and B (0, 4).

The values of Z at these points are as follows:

                                             

Therefore, the maximum value of Z is 16 at the point B (0, 4).

Problem:

Minimize Z = x + 2y

subject to 2x + y ≥ 3, x + 2y ≥ 6, x ≥ 0, y ≥ 0.

Solution:

The feasible region determined by the constraints, 2x + y ≥ 3, x + 2y ≥ 6, x ≥ 0, and y ≥ 0 is as follows:

                                                        

The corner points of the feasible region are A (6, 0) and B (0, 3).

The values of Z at these corner points are as follows:

                     

It can be seen that the value of Z at points A and B is same. If we take any other point such as (2, 2) on

line x + 2y = 6, then Z = 6

Thus, the minimum value of Z occurs for more than 2 points.

Therefore, the value of Z is minimum at every point on the line x + 2y = 6

Problem:

Maximize Z = x + y

subject to x – y ≤ -1, -x + y ≤ 0, x, y ≥ 0.

Solution:

The region determined by the constraints

x – y ≤ -1, -x + y ≤ 0, x, y ≥ 0 is as follows:

From the figure, we can see that there is no point satisfying all the constraints simultaneously. Thus, the problem is having no feasible region and hence no feasible solution.                                                                         

Thus, Z has no maximum value.

 

Different Types of Linear Programming Problems:

 

1. Manufacturing problems:

In these problems, we determine the number of units of different products which should be produced and sold by a firm when each product requires a fixed manpower, machine hours, labour hour per unit of product, warehouse space per unit of the output etc., in order to make maximum profit.

 

Problem: A manufacturer produces nuts ad bolts. It takes 1 hour of work on machine A and 3 hours on machine B to produce a package of nuts. It takes 3 hours on machine A and 1 hour on machine B to produce a package of bolts. He earns a profit, of Rs 17.50 per package on nuts and Rs. 7.00 per package on bolts. How many packages of each should be produced each day so as to maximize his profit, if he operates his machines for at the most 12 hours a day?

 

Solution:

Let the manufacturer produce x packages of nuts and y packages of bolts. Therefore,

x ≥ 0 and y ≥ 0

The given information can be compiled in a table as follows:

                               

The profit on a package of nuts is Rs 17.50 and on a package of bolts is Rs 7.

Therefore, the constraints are

x + 3y ≤ 12

3x + y ≤ 12

Total profit, Z = 17.5x + 7y

The mathematical formulation of the given problem is

Maximize Z = 17.5x + 7y    …….. (1)

subject to the constraints,

x + 3y ≤ 12    ………… (2)

3x + y ≤ 12    ………… (3)

x, y ≥ 0    …………….. (4)

The feasible region determined by the system of constraints is as follows:

                                                          

The corner points are A (4, 0), B (3, 3), and C (0, 4).

The values of Z at these corner points are as follows:

                                             

The maximum value of Z is Rs 73.50 at (3, 3).

Thus, 3 packages of nuts and 3 packages of bolts should be produced each day to get the

maximum profit of Rs 73.50.

 

2. Diet problems:

In these problems, we determine the amount of different kinds of constituents/nutrients which should be included in a diet so as to minimize the cost of the desired diet such that it contains a certain minimum amount of each constituent/nutrients.

 

Problem:

Reshma wishes to mix two types of food P and Q in such a way that the vitamin contents of the mixture contain at least 8 units of vitamin A and 11 units of vitamin B. Food P costs Rs 60/kg and Food Q costs Rs 80/kg. Food P contains 3 units /kg of vitamin A and 5 units /kg of vitamin B while food Q contains 4 units /kg of vitamin A and 2 units /kg of vitamin B. Determine the minimum cost of the mixture?

Solution:

Let the mixture contain x kg of food P and y kg of food Q. Therefore,

x ≥ 0 and y ≥ 0

The given information can be compiled in a table as follows:

                                    

The mixture must contain at least 8 units of vitamin A and 11 units of vitamin B.

Therefore, the constraints are

3x + 4y ≥ 8

5x + 2y ≥ 11

Total cost, Z, of purchasing food is, Z = 60x + 80y

The mathematical formulation of the given problem is

Minimize Z = 60x + 80y   …….. (1)

subject to the constraints,

3x + 4y ≥ 8     …….. (2)

5x + 2y ≥ 11   ……. (3)

x, y ≥ 0            …… (4)

The feasible region determined by the system of constraints is as follows:

                                                       

It can be seen that the feasible region is unbounded.

The corner points of the feasible region are A(8/3, 0), B(2, 1/2) and C(0, 11/2).

The values of Z at these corner points are as follows:

                                                    

As the feasible region is unbounded, therefore, 160 may or may not be the minimum value of

1. For this, we graph the inequality, 60x + 80y < 160 or 3x + 4y < 8, and check whether the

resulting half plane has points in common with the feasible region or not.

It can be seen that the feasible region has no common point with 3x + 4y < 8

Therefore, the minimum cost of the mixture will be Rs 160 at the line segment joining the

points (8/3, 0) and (2, 1/2).

 

3. Transportation problems:

 In these problems, we determine a transportation schedule in order to find the cheapest way of transporting a product from plants/factories situated at different locations to different markets.

 

Problem:

An aeroplane can carry a maximum of 200 passengers. A profit of Rs 1000 is made on each executive class ticket and a profit of Rs 600 is made on each economy class ticket. The airline reserves at least 20 seats for executive class. However, at least 4 times as many passengers prefer to travel by economy class than by the executive class. Determine how many tickets of each type must be sold in order to maximize the profit for the airline. What is the maximum profit?

Solution:

Let the airline sell x tickets of executive class and y tickets of economy class.

The mathematical formulation of the given problem is as follows:

Maximize z = 1000x + 600y    …..... (1)

subject to the constraints,

x + y ≤ 200   ………….(2)

x ≥ 20            …………(3)

y – 4x ≥ 0     ………….(4)

x, y ≥ 0         ………….(5)

The feasible region determined by the constraints is as follows:

                                                    

The corner points of the feasible region are A (20, 80), B (40, 160) and C (20, 180).

The values of z at these corner points are as follows:

                   

 

The maximum value of z is 136000 at (40, 160).

Thus, 40 tickets of executive class and 160 tickets of economy class should be sold to maximize the profit and the maximum profit is Rs 136000.

 

 

 

 

 

 

 

 

Share: