Class 12 PCM . Mathematics . Mathematics Part II . Linear Programming

Chapter 12: Linear Programming

Ch 12

Mathematics

Class 12 PCM

Lecture 1

Introduction

Reference video · Lecture 1Introduction

Optimisation and Linear Programming

Definition

Optimisation problem — A problem that seeks to maximise or minimise a quantity, such as profit, cost or resource use.

Definition

Linear programming problem (LPP) — A special type of optimisation problem that finds the maximum or minimum value of a linear function subject to linear constraints and non-negativity conditions.

Key terms

  • Decision variables: Unknown quantities chosen in a problem, such as the numbers of products to make or buy.
  • Objective function: The linear function whose maximum or minimum is required.
  • Constraints: Linear equations, inequalities or other restrictions that the decision variables must satisfy.
  • Non-negative restrictions: Conditions such as x≥0x\ge0 and y≥0y\ge0, which prevent negative quantities.
  • Feasible choice: Values of the decision variables that satisfy every constraint, including non-negativity.
General objective function
Z=ax+byZ=ax+by

For two decision variables, the linear objective function has this form, where aa and bb are constants.

Furniture dealer: the optimisation situation

  • Decision: The dealer chooses how many tables and chairs to buy, aiming to maximise total profit.
  • Limits: The investment is at most Rs. 50,000 and storage is at most 60 items.
  • Tables only: The budget allows 20 tables, yielding a profit of Rs. 5,000.
  • Chairs only: Although the budget allows 100 chairs, storage limits the purchase to 60, yielding Rs. 4,500.
  • Mixed purchase: 10 tables and 50 chairs use the full budget and storage capacity, yielding Rs. 6,250; this is a feasible choice, not necessarily the maximum.

Formulating an LPP

Translate a situation into a mathematical model

  1. Define decision variables for the quantities being chosen.
  2. Write the quantity to be maximised or minimised as a linear objective function.
  3. Translate each resource limit or requirement into a linear constraint.
  4. Add non-negativity conditions for the decision variables.
Worked example

Formulate the furniture dealer's problem as an LPP. Also calculate the profit for 10 tables and 50 chairs.

  1. Let xx be the number of tables and yy the number of chairs.
  2. The investment cannot exceed Rs. 50,000; divide the budget inequality by 500.
    2500x+500y≤50000⟺5x+y≤1002500x+500y\le 50000\quad\Longleftrightarrow\quad 5x+y\le 100
  3. The dealer can store at most 60 items.
    x+y≤60x+y\le 60
  4. The quantities bought must be non-negative.
    x≥0,y≥0x\ge 0,\quad y\ge 0
  5. Profit is Rs. 250 per table and Rs. 75 per chair, so this is the objective function.
    Z=250x+75yZ=250x+75y
  6. For 10 tables and 50 chairs, both limits are met and the profit is Rs. 6,250.
    5(10)+50=100,10+50=60,Z=250(10)+75(50)=62505(10)+50=100,\quad 10+50=60,\quad Z=250(10)+75(50)=6250
Answer: Maximise Z=250x+75yZ=250x+75y subject to 5x+y≤1005x+y\le100, x+y≤60x+y\le60, x≥0x\ge0 and y≥0y\ge0. For x=10x=10 and y=50y=50, the profit is Rs. 6,250. This feasible choice is not necessarily optimal.

Solving LPPs in this chapter

  • Method covered: This chapter studies the graphical method for solving linear programming problems.
⚠ Common mistake

Do not confuse the objective function with the constraints: the objective is what must be maximised or minimised, while the constraints limit the choices.

Practice

A workshop makes products A and B. Each A uses 2 hours and each B uses 1 hour, with at most 40 hours available. Profit per unit is Rs. 30 for A and Rs. 20 for B. Formulate the LPP.

Hint: Let xx and yy be the quantities of A and B; translate the time limit and profit into expressions.
Key step: The time constraint is 2x+y≤402x+y\le40.
Solution: Let xx and yy be the quantities of A and B. Maximise Z=30x+20yZ=30x+20y subject to 2x+y≤402x+y\le40, x≥0x\ge0 and y≥0y\ge0.
Practice

A farmer plants wheat and maize. Wheat earns Rs. 400 per plot and maize Rs. 300 per plot. There are at most 12 plots; wheat needs 2 units of fertiliser per plot and maize needs 1, with at most 18 units available. Formulate the LPP.

Hint: Let xx and yy be the plots planted with wheat and maize.
Key step: The plot and fertiliser constraints are x+y≤12x+y\le12 and 2x+y≤182x+y\le18.
Solution: Maximise Z=400x+300yZ=400x+300y subject to x+y≤12x+y\le12, 2x+y≤182x+y\le18, x≥0x\ge0 and y≥0y\ge0.

Quick recap

  • An LPP is a special type of optimisation problem involving a linear objective function and linear constraints.
  • Decision variables represent the quantities being chosen; constraints describe limits and requirements.
  • Include non-negativity conditions such as x≥0x\ge0 and y≥0y\ge0.
  • A feasible choice satisfies all constraints, but it is not automatically optimal.
  • The furniture dealer's objective is Z=250x+75yZ=250x+75y, subject to investment and storage limits.
  • This chapter solves LPPs using the graphical method.
Lecture 2

Graphical Method Of Solving Linear Programming Problems

Reference video · Lecture 2Graphical Method Of Solving Linear Programming Problems

Feasible Region and Feasible Solutions

Constraints 5x+y≤100 and x+y≤60, with the feasible region shaded in the first quadrant.
Constraints 5x+y≤1005x+y\leq100 and x+y≤60x+y\leq60, with the feasible region shaded in the first quadrant.

Optimal Solutions and Corner-Point Theorems

Corner-Point Theorem

If an objective function has an optimal value on the feasible region, that value occurs at a corner point (vertex) of the region. The feasible region is a convex polygon.

Bounded-Region Theorem

If the feasible region is bounded, the objective function has both a maximum and a minimum, and each occurs at a corner point.

If the Feasible Region Is Unbounded

  • Existence A maximum or minimum may not exist. If an optimum exists, it occurs at a corner point.
  • Maximum test Let MM be the largest objective value among the corner points. It is the maximum if the open half-plane ax+by>Max+by>M has no point in common with the feasible region.
  • Minimum test Let mm be the smallest objective value among the corner points. It is the minimum if the open half-plane ax+by<max+by<m has no point in common with the feasible region.

Corner-Point Method

Steps to Solve Graphically

  1. Graph the constraints and identify their common feasible region.
  2. Find every corner point by inspection or by solving the equations of intersecting boundary lines.
  3. Evaluate the objective function at each corner point; note the largest value MM and smallest value mm.
  4. For a bounded region, MM and mm are the maximum and minimum. For an unbounded region, apply the relevant open-half-plane test.
Objective Function at Corner Points
Z=ax+byZ=ax+by

Evaluate the objective function at every vertex of the feasible region.

Worked example

Find the maximum return and the investment choice that gives it.

  1. Maximise the investment return; the feasible-region vertices are (0,0)(0,0), (20,0)(20,0), (10,50)(10,50) and (0,60)(0,60).
    Z=250x+75y,5x+y≤100,x+y≤60,x,y≥0Z=250x+75y,\quad 5x+y\leq100,\quad x+y\leq60,\quad x,y\geq0
  2. Find the intersection of the two constraint boundaries.
    5x+y=100x+y=604x=40x=10,y=50\begin{aligned}5x+y&=100\\x+y&=60\\4x&=40\\x&=10,\quad y=50\end{aligned}
  3. Evaluate the objective function at each vertex.
    Z(0,0)=0Z(20,0)=5000Z(10,50)=6250Z(0,60)=4500\begin{aligned}Z(0,0)&=0\\Z(20,0)&=5000\\Z(10,50)&=6250\\Z(0,60)&=4500\end{aligned}
Answer: The maximum is Z=6250Z=6250 at (x,y)=(10,50)(x,y)=(10,50): invest in 10 tables and 50 chairs.
Investment Example: Objective Values
VertexObjective value ZZ
(0,0)(0,0)00
(0,60)(0,60)45004500
(10,50)(10,50)62506250 (maximum)
(20,0)(20,0)50005000
Practice

Maximise Z=4x+yZ=4x+y subject to x+y≤50x+y\leq50, 3x+y≤903x+y\leq90, and x,y≥0x,y\geq0.

Hint: Find the intersection of the two sloping boundary lines and the axis-intercept vertices.
Key step: The feasible-region vertices are (0,0)(0,0), (30,0)(30,0), (20,30)(20,30) and (0,50)(0,50).
Solution: At the vertices, ZZ is respectively 00, 120120, 110110 and 5050. Hence the maximum is 120120 at (30,0)(30,0).
Feasible region for 3x+y≤90 and x+y≤50, restricted to the first quadrant.
Feasible region for 3x+y≤903x+y\leq90 and x+y≤50x+y\leq50, restricted to the first quadrant.
Practice

For 5x+y≤1005x+y\leq100, x+y≤60x+y\leq60, and x,y≥0x,y\geq0, classify (10,50)(10,50), (0,60)(0,60), (20,0)(20,0) and (25,40)(25,40) as feasible or infeasible.

Hint: Substitute each point into both inequalities and check non-negativity.
Key step: The point (25,40)(25,40) gives 5x+y=165>1005x+y=165>100 and x+y=65>60x+y=65>60.
Solution: (10,50)(10,50), (0,60)(0,60) and (20,0)(20,0) are feasible; (25,40)(25,40) is infeasible.
⚠ Common mistake

Do not test only the constraint intercepts: include every feasible intersection of boundary lines, then compare the objective values at all vertices.

Quick recap

  • The feasible region is the common set satisfying all constraints, including non-negativity.
  • Points inside or on the boundary are feasible; points outside are infeasible.
  • A corner point is an intersection of boundary lines.
  • If an optimum exists, it occurs at a corner point.
  • For a bounded region, both maximum and minimum values exist and occur at vertices.
  • For an unbounded region, an optimum may not exist; check the relevant open half-plane.
  • The corner-point method compares the objective values at every feasible vertex.
Lecture 3

Graphical Method Of Solving Linear Programming Problems(Contiune)

Reference video · Lecture 3Graphical Method Of Solving Linear Programming Problems(Contiune)

Bounded Feasible Region: Minimum at a Corner Point

Definition

Corner-point method — For a linear programming problem with a bounded feasible region, evaluate the objective function at every vertex to find its maximum or minimum.

Find the optimum in a bounded region

  1. Graph the constraints and identify the feasible region and its vertices.
  2. Evaluate the objective function at every vertex.
  3. Choose the least or greatest value, as required.
Worked example

Minimise Z=200x+500yZ=200x+500y subject to x+2y≥10x+2y\geq10, 3x+4y≤243x+4y\leq24, x≥0x\geq0, and y≥0y\geq0.

  1. The feasible region has vertices A(0,5)A(0,5), B(4,3)B(4,3) and C(0,6)C(0,6). Evaluate Z=200x+500yZ=200x+500y at each.
    Z(0,5)=2500Z(0,5)=2500
  2. Evaluate the objective at the second vertex.
    Z(4,3)=200(4)+500(3)=2300Z(4,3)=200(4)+500(3)=2300
  3. Evaluate the objective at the third vertex and compare the values.
    Z(0,6)=3000Z(0,6)=3000
Answer: The minimum is Z=2300Z=2300 at (4,3)(4,3).
Bounded feasible region with corner points (0,5), (4,3) and (0,6).
Bounded feasible region with corner points (0,5)(0,5), (4,3)(4,3) and (0,6)(0,6).

Multiple Optimal Solutions

Equal objective values at two vertices

If two vertices of the feasible region give the same optimal value, every point on the line segment joining them also gives that value.

Worked example

Find the minimum and maximum of Z=3x+9yZ=3x+9y subject to x+3y≤60x+3y\leq60, x+y≥10x+y\geq10, x≤yx\leq y, x≥0x\geq0, and y≥0y\geq0.

  1. The vertices are A(0,10)A(0,10), B(5,5)B(5,5), C(15,15)C(15,15) and D(0,20)D(0,20). Compute Z=3x+9yZ=3x+9y at each vertex.
    Z(A)=90,Z(B)=60,Z(C)=180,Z(D)=180Z(A)=90,\quad Z(B)=60,\quad Z(C)=180,\quad Z(D)=180
  2. The least value is at BB. The two vertices giving the greatest value both lie on x+3y=60x+3y=60.
    Z=3(x+3y)Z=3(x+3y)
  3. Thus all points on the segment from CC to DD have the same greatest value.
    Z=180Z=180
Answer: The minimum is 6060 at (5,5)(5,5). The maximum is 180180 at every point on the segment joining (15,15)(15,15) and (0,20)(0,20).

Unbounded Feasible Region

Checking an optimum in an unbounded region

A best value at a vertex does not by itself prove an optimum when the feasible region is unbounded. For a proposed minimum mm, test whether the feasible region intersects the half-plane where Z<mZ<m; for a proposed maximum MM, test whether it intersects the half-plane where Z>MZ>M.

Worked example

Determine whether Z=−50x+20yZ=-50x+20y has a minimum or maximum under 2x−y≥−52x-y\geq-5, 3x+y≥33x+y\geq3, 2x−3y≤122x-3y\leq12, x≥0x\geq0, and y≥0y\geq0.

  1. The feasible region is unbounded. At its listed vertices, Z=−50x+20yZ=-50x+20y takes the following values.
    Z(0,5)=100,Z(0,3)=60,Z(1,0)=−50,Z(6,0)=−300Z(0,5)=100,\quad Z(0,3)=60,\quad Z(1,0)=-50,\quad Z(6,0)=-300
  2. The smallest vertex value is −300-300. To check whether it is a true minimum, test the points where Z<−300Z<-300.
    −50x+20y<−300  ⟺  −5x+2y<−30-50x+20y<-300\iff -5x+2y<-30
  3. This strict half-plane intersects the feasible region, so feasible points have objective values below −300-300.
  4. For the maximum candidate 100100, the test region Z>100Z>100 does not intersect the feasible region; the maximum is attained at (0,5)(0,5).
    −50x+20y>100-50x+20y>100
Answer: There is no minimum because feasible points satisfy Z<−300Z<-300. The maximum is 100100 at (0,5)(0,5).
⚠ Common mistake

In an unbounded feasible region, do not assume the smallest or greatest vertex value is the optimum; check whether better objective values occur elsewhere in the region.

Infeasible Linear Programming Problem

Definition

Infeasible problem — A linear programming problem is infeasible if no point satisfies all its constraints simultaneously.

Worked example

Check whether the constraints x+y≥8x+y\geq8, 3x+5y≤153x+5y\leq15, x≥0x\geq0, and y≥0y\geq0 have a feasible solution.

  1. The non-negativity conditions and x+y≥8x+y\geq8 imply a lower bound on 3x+5y3x+5y.
    3x+5y≥3x+3y=3(x+y)≥243x+5y\geq3x+3y=3(x+y)\geq24
  2. This contradicts the constraint 3x+5y≤153x+5y\leq15, so the feasible region is empty.
    24>1524>15
Answer: There is no feasible region and hence no feasible solution. The objective function does not change this conclusion.

General Properties of Linear Programming

  • Feasible region: It is always convex; the line segment between any two of its points lies entirely within it.
  • Optimal value: When a finite optimum exists, it occurs at a vertex of the feasible region.
  • Multiple optima: If two vertices give the same optimal value, the entire segment between them gives that value.
  • Variables: The decision variables are subject to non-negativity constraints such as x≥0x\geq0 and y≥0y\geq0.
Practice

Maximise Z=2x+yZ=2x+y subject to x+y≤4x+y\leq4, x≤2x\leq2, y≤3y\leq3, x≥0x\geq0, and y≥0y\geq0.

Hint: Evaluate the objective at the vertices of the feasible region.
Key step: The vertices include (0,0)(0,0), (2,0)(2,0), (2,2)(2,2), (1,3)(1,3) and (0,3)(0,3).
Solution: The corresponding values are 0,4,6,5,30,4,6,5,3. Therefore, the maximum is 66 at (2,2)(2,2).
Practice

Determine whether x+y≥7x+y\geq7, 2x+3y≤122x+3y\leq12, x≥0x\geq0 and y≥0y\geq0 are feasible.

Hint: Use non-negativity to obtain a lower bound for 2x+3y2x+3y.
Key step: Since x,y≥0x,y\geq0, 2x+3y≥2x+2y=2(x+y)≥142x+3y\geq2x+2y=2(x+y)\geq14.
Solution: This contradicts 2x+3y≤122x+3y\leq12. Hence, there is no feasible solution.

Quick recap

  • For a bounded feasible region, evaluate the objective at every vertex to find the optimum.
  • Equal optimal values at two vertices mean every point between them is optimal.
  • In an unbounded region, test whether points with a better objective value intersect the feasible region.
  • A problem is infeasible when its constraints cannot all hold at the same time.
  • The feasible region is convex, and a finite optimum occurs at a vertex.

Formula sheet

General objective function
Z=ax+byZ=ax+by
Objective Function at Corner Points
Z=ax+byZ=ax+by

Mathematics — ALL CHAPTERS

1

Relations And Functions

View

2

Inverse Trigonometric Functions

View

3

Matrices

View

4

DETERMINANTS 

View

5

Continuity And Differentiability

View

6

Application Of Derivatives

View

7

Integrals

View

8

APPLICATION OF INTEGRALS

View

9

DIFFERENTIAL EQUATIONS

View

10

VECTOR ALGEBRA

View

11

Three Dimensional Geometry

View

12

Linear Programming

View

13

Probability

View

14

Proofs In Mathematics

View

15

Mathematical Modelling

View