CBSE Class 12 Mathematics Linear Programming Notes Set 03

Important Notes and Formulas

Introduction

With the help of linear programming models, a decision maker can most efficiently and effectively employ his production factors and limited resources to get maximum profit at minimum cost. He can also take quick decisions, which are important in modern times because any delay or postponement may give an advantage to other organisations.
Linear programming: Linear programming is a method of determining a particular programme or plan of action to optimize (maximize or minimize).
Linear programming problem (L.P.P.): It is a problem of finding the optimal (maximum or minimum) value of a linear function subject to certain restrictions (constraints) determined by a set of linear inequations with variables as non-negative.

General Form of L.P.P.

The general form of a linear programming problem is
Optimize (Maximize or Minimize) \( Z = c_1x_1 + c_2x_2 + \dots + c_nx_n \)
Subject to
\[ \left. \begin{matrix} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n \ (\leq, =, \geq)\ b_1 \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n \ (\leq, =, \geq)\ b_2 \\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n \ (\leq, =, \geq)\ b_m \end{matrix} \right\rbrace \quad \dots(1) \]
\( x_1, x_2, \dots, x_n \geq 0 \)    ...(2)

The definitions of various terms related to the LPP are as follows:
(a) Objective function: The linear function Z which is to be maximized or minimized is the objective function of the LPP.
(b) Decision variables: \( x_1, x_2, \dots, x_n \) are the decision variables.
(c) Constraints: The inequations or equations (1) in the variables of a LPP which describe the conditions under which the optimization (maximization or minimization) is to be accomplished are called constraints.
In the constraints given in the general form of LPP there may be any one of the three signs ≤, =, ≥.
(d) Non-negativity restrictions: These are the constraints (2) which describe that the variables involved in a LPP are non-negative.
(e) Feasible region: The common region determined by all the constraints including the non-negative constraints of a LPP is called the feasible region or solution region.
A feasible region may be (i) bounded (ii) unbounded.

(i) Bounded feasible region:

Constraints are:
x + 3y ≤ 12
3x + y ≤ 12
x ≥ 0, y ≥ 0

(f) Corner points of a feasible region: Corner points of a feasible region are the points of intersection of two boundary lines.

To Solve an LPP Graphically (Corner Point Method)

Working rule:
(a) Formulate the given linear programming problem.
(b) Convert the linear constraints into equalities and then draw their graphs, which will be straight lines.
(c) Find the feasible region of the linear programming problem and determine its corner points by solving the equations of the lines taken two at a time.
(d) Determine the value of the objective function Z at each corner point. Also, find the least value m and the greatest value M of the values of the objective function at the corner points.
(e) If the feasible region R is bounded, then M and m will be the maximum and minimum values of Z, respectively.

Solved Examples

Previous Year Questions

Very Short Answer Questions (1 Mark)

Question 1. The corner points of the feasible region of an LPP are (0, 0), (0, 8), (2, 7), (5, 4) and (6, 0). The maximum profit P = 3x + 2y occurs at the point ________ . [CBSE 2020, 1M]
Answer:
Given that the corner points are (0, 0), (0, 8), (2, 7), (5, 4) and (6, 0)
and P = 3x + 2y
at (0, 8), P = 16;   at (5, 4), P = 23
at (2, 7), P = 20;   at (6, 0), P = 18
at (0, 0), P = 0
\( P_{max} \) = 23 at (5, 4) [1]

Long Answer Questions I (4 Marks)