CBSE Class 12 Mathematics Linear Programming Notes Set 02

BASIC CONCEPTS

1. Definition: Linear programming (LP) is an optimisation technique in which a linear function is optimised (i.e., minimised or maximised) subject to certain constraints which are in the form of linear inequalities or/and equations. The function to be optimised is called objective function.

2. Applications of Linear Programming: Linear programming is used in determining optimum combination of several variables subject to certain constraints or restrictions.

3. Formation of Linear Programming Problem (LPP): The basic problem in the formulation of a linear programming problem is to set-up some mathematical model. This can be done by asking the following questions:

• (a) What are the unknowns (variables)?
• (b) What is the objective?
• (c) What are the restrictions?

For this, let \( x_1, x_2, x_3, .........., x_n \) be the variables. Let the objective function to be optimized (i.e., minimised or maximised) be given by \( Z \).

• (i) \( Z = c_1 x_1 + c_2 x_2 + ....... + c_n x_n \), where \( c_i, x_i \) \( (i = 1, 2, .........., n) \) are constraints.
• (ii) Let there be \( mn \) constants and let \( b \) be a set of constants such that
  \( a_{11} x_1 + a_{12} x_2 + ...... + a_{1n} x_n \) (\( \leq \), = or \( \geq \)) \( b_1 \)
  \( a_{21} x_1 + a_{22} x_2 + ...... + a_{2n} x_n \) (\( \leq \), = or \( \geq \)) \( b_2 \)
  ...... ...... ...... ......
  ...... ...... ...... ......
  \( a_{m1} x_1 + a_{m2} x_2 + ....... + a_{mn} x_n \) (\( \leq \), = or \( \geq \)) \( b_m \)
• (iii) Finally, let \( x_1 \geq 0, x_2 \geq 0, .........., x_n \geq 0 \), called non-negative constraints.

The problem of determining the values of \( x_1, x_2, .........., x_n \) which makes \( Z \), a minimum or maximum and which satisfies (ii) and (iii) is called the general linear programming problem.

4. General LPP:

• (a) Decision variables: The variables \( x_1, x_2, x_3, ........, x_n \) whose values are to be decided, are called decision variables.
• (b) Objective function: The linear function \( Z = c_1 x_1 + c_2 x_2 + ........ + c_n x_n \) which is to be optimized (maximised or minimised) is called the objective function or preference function of the general linear programming problem.
• (c) Structural constraints: The inequalities given in (ii), are called the structural constraints of the general linear programming problem. The structural constraints are generally in the form of inequalities of \( \geq \) type or \( \leq \) type, but occasionally, a structural constraint may be in the form of an equation.
• (d) Non-negative constraints: The set of inequalities (iii) is usually known as the set of non-negative constraints of the general LPP. These constraints imply that the variables \( x_1, x_2, ...., x_n \) cannot take negative values.
• (e) Feasible solution: Any solution of a general LPP which satisfies all the constraints, structural and non-negative, of the problem, is called a feasible solution to the general LPP.
• (f) Optimum solution: Any feasible solution which optimizes (i.e., minimises or maximises) the objective function of the LPP is called optimum solution.

5. Requirements for Mathematical Formulation of LPP: Before getting the mathematical form of a linear programming problem, it is important to recognize the problem which can be handled by linear programming problem. For the formulation of a linear programming problem, the problem must satisfy the following requirements:

• (i) There must be an objective to minimise or maximise something. The objective must be capable of being clearly defined mathematically as a linear function.
• (ii) There must be alternative sources of action so that the problem of selecting the best course of actions may arise.
• (iii) The resources must be in economically quantifiable limited supply. This gives the constraints to LPP.
• (iv) The constraints (restrictions) must be capable of being expressed in the form of linear equations or inequalities.

6. Solving Linear Programming Problem: To solve linear programming problems, Corner Point Method is adopted. Under this method following steps are performed:

• Step I. At first, feasible region is obtained by plotting the graph of given linear constraints and its corner points are obtained by solving the two equations of the lines intersecting at that point.
• Step II. The value of objective function \( Z = ax + by \) is obtained for each corner point by putting its \( x \) and \( y \)-coordinate in place of \( x \) and \( y \) in \( Z = ax + by \). Let \( M \) and \( m \) be largest and smallest value of \( Z \) respectively.
  • Case I: If the feasible region is bounded, then \( M \) and \( m \) are the maximum and minimum values of \( Z \).
  • Case II: If the feasible region is unbounded, then we proceed as follows:
• Step III. The open half plane determined by \( ax + by > M \) and \( ax + by < m \) are obtained.
  • Case I: If there is no common point in the half plane determined by \( ax + by > M \) and feasible region, then \( M \) is maximum value of \( Z \), otherwise \( Z \) has no maximum value.
  • Case II: If there is no common point in the half plane determined by \( ax + by < m \) and feasible region, then \( m \) is minimum value of \( Z \), otherwise \( Z \) has no minimum value.