CBSE Class 12 Maths –Chapter 12 Linear Programming- Study Materials

Linear Programming & Its Applications 

• It is an important optimization (maximization or minimization) technique used in decision making is business and everyday life for obtaining the maximum or minimum values as required of a linear expression to satisfying certain number of given linear restrictions.

• Involve finding maximum profit, minimum cost, or minimum use of resources etc.

• Used in industry, commerce, management science etc.

Linear Programming Problem and its Mathematical Formulation: 

Definitions 

Optimal value
• Maximum or Minimum value of a linear function

Objective Function
• The function which is to be optimized (maximized/minimized)
• Linear function Z = ax + by, where a, b are constants, which has to be maximised or minimized is called a linear objective function.
• Eg:Z = 250x+ 75y where variables x and y are called decision variables

Linear Constraints  
• System of linear inequations/equations under which objective function is to be optimized
• Linear inequalities/equations or restrictions on the variables of a linear programming problem
• Also called as Overriding Conditions or Constraints
• The conditions x ≥ 0, y ≥ 0 are called non-negative restrictions.

Non-negative Restrictions
• All the variables considered for making decisions assume non-negative values.

Optimisation problem
•  A problem which seeks to maximise or minimise a linear function (say of two variables x and y) subject to certain constraints as determined by a set of linear inequalities
• Linear programming problems (LPP) are special type of optimisation problems.

Note: 
• The term linear implies that all the mathematical relations used in the problem are linear relations .
• The term programming refers to the method of determining a particular programme or plan of action.

Mathematical Formulation of the Problem 

A general LPP can be stated as (Max/Min) Z- c₁x₁ + c₂x₂ + CₙXₙ (Objective function) subject to constraints and the non-negative restriction

• x₁, X₂,….., Xₙ ≥ 0 where all a₁₁, a₁₂, ……, amn;
• b₁, b₂…….bm; C₁, C₂ Cₙ are constants and
• X₁, X₂. ……. Xₙ are variables

Graphical method of solving linear programming problems 

Terminologies 

Solution of a LPP
• A set of values of the variables x₁, X₂,….., Xₙ satisfying the constraints of a LPP

Feasible Solution of a LPP
• A set of values of the variables x₁, X₂,….., Xₙ satisfying the constraints and non-negative restrictions of a LPP
• Points within and on the boundary of the feasible region represent feasible solutions of the constraints

Feasible Region 
• The common region determined by all the constraints including non-negative constraints x, y ≥ 0 of a linear programming problem is called the feasible region (or solution region) for the problem

Feasible Choice 
• Each point in the Feasible region

Infeasible Region 
• Region outside the feasible region

Infeasible Solution 
• Any point outside the feasible region

Optimal Solution of a LPP
• A feasible solution of a LPP is said to, be optimal (or optimum), if it also optimizes the objective f unction of the problem.

Graphical Solution of a LPP 
• The solution of a LPP obtained by graphical method ie.., by drawing the graphs corresponding to the constraints and the non-negative restrictions

Unbounded Solution
• If the value of the objective function can be increased or decreased indefinitely, such solutions

Example: 

Graph the constraints stated as linear inequalities:

5x + y ≥ 100…………….. Equation (1)
x+y ≥ 60…………………… Equation (2)
x ≥ 0…………………………..Equation (3)
y ≥ 0…………………………..Equation (4)

For Plotting the Equation (1),

• Let x = 0, Hence we get the point y=100
• Let y = 0, Hence we get the point x-100/5 – 20
• Equation (1) is obtained by joining the points (20,100)

For Plotting the Equation (2),

• Let x = 0, Hence we get the point y=60
• Let y = 0, Hence we get the point x=60
• Equation (2) is obtained by joining the points (60,60)

From Equation (3) and Equation (4) we know both x and y are greater than 0

From the graph above,

• Points within and on the boundary of the feasible region represent feasible solutions of the constraints.

• In Fig 12.1, every point within and on the boundary of the feasible region OABC represents feasible solution to the problem.

• For example, the point (10, 50) is a feasible solution of the problem and so are the points (0, 60), (20, 0) etc.

• Any point outside the feasible region is called an infeasible solution. For example, the point (25, 40) is an infeasible solution of the problem.

• Now, we see that every point in the feasible region OABC satisfies all the constraints as given in (1) to (4), and since there are infinitely many points, it is not evident how we should go about finding a point that gives a maximum value of the objective function Z= 250x + 75y

Theorem 1

• Let R be the feasible region (convex polygon) for a linear programming problem
• Let Z= ax + by be the objective function.
• When Z has an optimal value (maximum or minimum), where the variables x and y are subject to constraints described by linear inequalities, this optimal value must occur at a corner point (vertex) of the feasible region.

Theorem 2 

• Let R be the feasible region for a linear programming problem
• Let Z = ax + by be the objective function.
• If R is bounded**, then the objective function Z has both a maximum and a minimum value on R and each of these occurs at a corner point (vertex) of R.
•Remark
• If R is unbounded, then a maximum or a minimum value of the objective function may not exist. However, if it exists, it must occur at a corner point of R .

Graphical Method to Solve a Linear Programming Problem

• There are two techniques of solving a LPP by graphical method

1. Corner point method
2. Iso-profit or Iso-cost method

Corner Point Method 

• Based on the principle of extreme point theorem.
• Procedure to Solve a LPP Graphically by Corner Point Method
• Consider each constraint as an equation.
• Plot each equation on graph, as each one will geometrically represent a straight line.
• The common region, thus obtained satisfying all the constraints and the non-negative restrictions is called the feasible region. It is a convex polygon .
• Determine the vertices (corner points) of the convex polygon. These vertices are known as the extreme points of corners of the feasible region.
• Find the values of the objective function at each of the extreme points.
• The point at which the value of the objective function is optimum (maximum or minimum) is the optimal solution of the given LPP.

Isom-profit or Iso-cost Method 

Procedure to Solve a LPP Graphically by Iso-profit or Iso-cost Method

• Consider each constraint as an equation.
• Plot each equation on graph as each one will geometrically represent a straight line.
• The polygonal region so obtained, satisfying all the constraints and the non-negative restrictions is the convex set of all feasible solutions of the given LPP, which is also known as feasible region.
• Determine the extreme points of the feasible region.
• Give some convenient value k to the objective function Z and draw the corresponding straight line in the xy-plane.
• If the problem is of maximization, then draw lines parallel to the line Z = k and obtain a line which is farthest from the origin and has atleast one point common to the feasible region.
• If the problem is of minimization, then draw lines parallel to the line Z- k and obtain a line, which is nearest to the origin and has atleast one point common to the feasible region.
• The common point so obtained is the optimal solution of the given LPP.

Working Rule for Marking Feasible Region 

Consider the constraint ax + by ≥ C, where c > 0.

• First draw the straight line ax + by = c by joining any two points on it.
• For this find two convenient points satisfying this equation.
• This straight line divides the xy-plane in two parts.
• The inequation ax + by c will represent that part of the xy-plane which lies to that side of the line ax + by = c in which the origin lies.

Again, consider the constraint ax + by ≥ c, where c > 0.

• Draw the straight line ax + by = c by joining any two points on it.
• This straight line divides the xy-plane in two parts.
• The inequation ax + by ≥ c will represent that part of the xy-plane, which lies to that side of the line ax + by = c in which the origin does not lie.

Important Points to be remembered 

1. Basic Feasible Solution
• A BFS is a basic solution which also satisfies the non-negativity restrictions.

2. Optimum Basic Feasible Solution
• A BFS is said to be optimum, if it also optimizes (Max or min) the objective function.

Example

Solve the following linear programming problem graphically:
Maximise Z- 4x + y…………………………… Equation (1)

Subject to the constraints:

• x + y ≤ 50……………………Equation (2)
• 3x + y ≤ 90………………….Equation (3)
• x ≥ 0 , y ≥ 0…………………Equation (4)

Solution: 

For Plotting the Equation (2),

• Let x = 0, Hence we get the point y=50
• Let y = 0, Hence we get the point x= 50
• Equation (2) is obtained by joining the points (50,50)

For Plotting the Equation (3),

• Let x = 0, Hence we get the point y=90
• Let y = 0, Hence we get the point x=30
• Equation (3) is obtained by joining the points (30,90)

From Equation (4) we know both x and y are greater than 0

Hence the points are (0, 0), (50, 50), (0, 50), (30, 0), (30, 90). The shaded region in graph is the feasible region determined by the system of constraints (2) to (4). We observe that the feasible region OABC is bounded.

Using the Corner Point Method to determine the maximum value of Z by substituting the vertices of the bounded region. Hence, maximum value of Z is 120 at the point (30, 0).

Example

Determine graphically the minimum value of the objective function

Z = – 50x + 20y …..(1)

Subject to the constraints:

• 2x -y ≥ -5…… (2)
• 3x + y ≥ 3….. (3)
• 2x – 3y ≤ 12.. (4)
• x ≥ 0, y ≥ 0…. (5)

Solution:

Graph the feasible region of the system of inequalities (2) to (5). The feasible region (shaded) is shown.

By Observation that the feasible region is unbounded.

We now evaluate Z at the corner points.

From this table, we find that – 300 is the smallest value of Z at the corner point (6, 0).

Since the region would have been bounded, this smallest value of Z is the minimum value of Z

(Theorem 2). 

But here we see that the feasible region is unbounded. Therefore, – 300 may or may not be the minimum value of Z.

To decide this issue, we graph the inequality 50x + 20y < 300

i.e., 5x + 2y < 30 (By dividing the Equation above by 10)

And check whether the resulting open half plane has points in common with feasible region or not.

If it has common points, then -300 will not be the minimum value of Z. Otherwise, -300 will be the minimum value of Z.

As shown in the graph above, it has common points. Therefore, Z= -50 x + 20 y has no minimum value subject to the given constraints.

General features of linear programming problems 

1. The feasible region is always a convex region.
2. The maximum (or minimum) solution of the objective function occurs at the vertex (corner) of the feasible region.
3. If two corner points produce the same maximum (or minimum) value of the objective function, then every point on the line segment joining these points will also give the same maximum (or minimum) value.

Different Types of Linear Programming Problems 

A few important linear programming problems are listed below:

1. Manufacturing problems

• 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.

2. Diet problems

• Determine the amount of different kinds of constituents/nutrients which should be included in a diet so as to minimise the cost of the desired diet such that it contains a certain minimum amount of each constituent/nutrients.

3. Transportation problems

• 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.