Linear Programming | Feasible Region & Objective Function

Published: 2026-07-22 Categories: Inequalities Editor: MathSir Difficulty: ★★★★☆ Reading time: ~17 minutes Pageview: 36

Synopsis

This article covers the essential skills of linear programming – an advanced topic in DSE Paper 1 Section A(2) and Section B worth 4–6 marks. You will learn how to graph linear inequalities to find the feasible region, how to define and optimize the objective function, how to use the vertex method to find maximum/minimum values, and how to handle integer solutions for real-world problems. The article includes step-by-step worked examples, DSE exam techniques, practice questions. These are high-level skills that can help you secure top marks in the exam.

Target Exam Paper	Paper 1 Section A(2) & Section B
Typical Marks	4–6 marks
Syllabus Ref.	Number and Algebra Strand – Inequalities: Linear inequalities and basic linear programming

Learning Objectives

By the end of this article, you should be able to:

Graph a system of linear inequalities and identify the feasible region.
Define and evaluate the objective function at the vertices of the feasible region.
Find the maximum or minimum value of the objective function using the vertex method.
Handle integer solutions when variables are required to be integers.
Translate real-world problems (production, resources, profit) into linear programming models.
Apply all these skills to DSE-style questions.

1. Introduction:

Linear programming appears every year in DSE Paper 1 Section A(2) and Section B. Questions may ask you to:

Find the feasible region from a set of inequalities
Maximize or minimize a linear objective function
Solve real-world problems involving limited resources
Handle cases where variables must be integers

These are high-level skills that can help you secure top marks.

DSE Exam Tip

Linear programming questions often appear in Section A(2) as short-answer questions worth 3–4 marks, and in Section B as longer problems worth 5–6 marks.

2. Graphing Linear Inequalities

A linear inequality in two variables (e.g., $ 2x + 3y \le 12 $) represents a half-plane. To graph it:

Graph the corresponding boundary line ($ 2x + 3y = 12 $).
Use a solid line for $ \le $ or $ \ge $ (including boundary), and a dashed line for $ < $ or $ > $.
Choose a test point (e.g., $ (0,0) $) to determine which side satisfies the inequality.
Shade the region that satisfies all inequalities simultaneously – this is the feasible region.

Worked Example

Question: Shade the feasible region defined by:

$ x \ge 0 $, $ y \ge 0 $, $ x + y \le 6 $, $ 2x + y \le 8 $

Solution

Graph the lines: $ x+y=6 $ and $ 2x+y=8 $, with $ x\ge0, y\ge0 $.

Test $ (0,0) $: $ 0+0 \le 6 $ ✓, $ 0+0 \le 8 $ ✓. So shade below both lines in the first quadrant.

The feasible region is a polygon with vertices: $ (0,0), (4,0), (2,4), (0,6) $.

3. Objective Function and Vertex Method

The objective function is a linear expression to be maximized or minimized, e.g., $ P = 3x + 4y $. The vertex method states that the maximum or minimum value of a linear objective function over a convex polygon occurs at one of the vertices of the feasible region.

Steps:

Find all vertices of the feasible region.
Evaluate the objective function at each vertex.
Choose the maximum or minimum value.

DSE Memory Aid

Vertex method: The optimal solution for a linear program is always at a corner point of the feasible region.

Worked Example

Question: Maximize $ P = 3x + 2y $ subject to:

$ x \ge 0, y \ge 0, x + y \le 5, x + 2y \le 8 $.

Solution

Vertices: Intersections of boundary lines. Compute:

$ (0,0) $: $ P=0 $
$ (5,0) $: $ P=15 $
$ (0,4) $: $ P=8 $
Intersection of $ x+y=5 $ and $ x+2y=8 $: subtract: $ y=3, x=2 $ → $ (2,3) $, $ P=3(2)+2(3)=12 $

Maximum is 15 at $ (5,0) $.

Answer: Max $ P=15 $.

4. Integer Solutions

In real-world problems, variables often must be integers (e.g., number of products, people). The vertex method may give non-integer solutions. To find the optimal integer solution:

Find the optimal vertex (may be non-integer).
Identify all integer points within the feasible region near the vertex.
Evaluate the objective function at these integer points.
Choose the best integer solution.

Common DSE Trap

The optimal integer solution is not always the nearest integer point to the vertex. Always check feasible integer points thoroughly.

Worked Example

Question: Maximize $ P = 10x + 12y $ subject to:

$ x \ge 0, y \ge 0, 2x + 3y \le 30, 3x + 2y \le 30 $, with $ x, y $ integers.

Solution

Vertices: $ (0,0), (10,0), (0,10), (6,6) $ (intersection: $ 2x+3y=30, 3x+2y=30 $ → $ x=y=6 $).

Evaluate at vertices: $ (6,6) \to P=132 $. But $ x,y $ are integers, and $ (6,6) $ is already integer, so optimal integer solution is $ (6,6) $ with $ P=132 $.

If vertex non-integer, e.g., $ (5.5, 4.5) $, we would check nearby integer points.

Answer: Max $ P=132 $ at $ (6,6) $.

5. Applications (Word Problems)

Linear programming is used to optimize real-world problems involving limited resources. Common applications include:

Production planning – maximize profit given constraints on materials and labour.
Diet problems – minimize cost while meeting nutritional requirements.
Resource allocation – allocate limited resources to maximize output.
Transportation – minimize shipping costs.

Worked Example

Question: A factory produces two products A and B. Each unit of A requires 2 hours of labour and 1 unit of material; each unit of B requires 1 hour of labour and 2 units of material. The factory has 100 hours of labour and 80 units of material available per week. Profit for A is $30 per unit, for B is $20 per unit. How many of each should be produced to maximize profit?

Solution

Let $ x $ = units of A, $ y $ = units of B.

Constraints: $ 2x + y \le 100 $ (labour), $ x + 2y \le 80 $ (material), $ x \ge 0, y \ge 0 $.

Objective: maximize $ P = 30x + 20y $.

Vertices: $ (0,0), (50,0), (0,40), (40,20) $ (intersection: $ 2x+y=100, x+2y=80 $ → $ x=40, y=20 $).

Evaluate: $ (0,0):0, (50,0):1500, (0,40):800, (40,20):30(40)+20(20)=1200+400=1600 $.

Max profit = $1600 at $ (40,20) $.

Answer: Produce 40 units of A and 20 units of B.

6. Worked Examples

Example 1: Basic LP

Question: Minimize $ C = 4x + 5y $ subject to:

$ x \ge 0, y \ge 0, x + 2y \ge 6, 3x + y \ge 6 $.

Solution

Graph and find vertices: Intersections: $ (0,3) $ (from $ x=0, x+2y=6 $), $ (2,0) $ (from $ y=0, 3x+y=6 $), and intersection of $ x+2y=6 $ and $ 3x+y=6 $: solve: $ x+2y=6, 3x+y=6 $ → $ x=1.2, y=2.4 $.

Evaluate: $ (0,3): C=15, (2,0): C=8, (1.2,2.4): C=4(1.2)+5(2.4)=4.8+12=16.8 $.

Minimum is 8 at $ (2,0) $.

Answer: Min $ C=8 $.

Example 2: Integer Solution

Question: Maximize $ P = 6x + 5y $ subject to:

$ x \ge 0, y \ge 0, 2x + y \le 10, x + 3y \le 12 $, with $ x, y $ integers.

Solution

Vertices: $ (0,0), (5,0), (0,4) $, intersection: $ 2x+y=10, x+3y=12 $ → $ x=3.6, y=2.8 $.

Non-integer vertex $ (3.6,2.8) $. Evaluate nearby integer points in feasible region: $ (3,3): P=18+15=33 $, $ (4,2): P=24+10=34 $, $ (3,2): P=18+10=28 $, $ (4,3): $ check constraints: $ 2(4)+3=11 \le 10 $? No. So best integer is $ (4,2) $ with $ P=34 $.

Also check $ (3,3) $ gives 33. So max integer is 34.

Answer: Max $ P=34 $ at $ (4,2) $.

Example 3: Word Problem

Question: A baker makes cakes and cookies. Each cake requires 3 cups of flour and 2 cups of sugar; each cookie requires 2 cups of flour and 1 cup of sugar. The baker has 60 cups of flour and 40 cups of sugar. Profit is $5 per cake and $3 per cookie. How many of each should be made to maximize profit?

Solution

Let $ x $ = cakes, $ y $ = cookies.

Constraints: $ 3x + 2y \le 60 $, $ 2x + y \le 40 $, $ x \ge 0, y \ge 0 $.

Objective: maximize $ P = 5x + 3y $.

Vertices: $ (0,0), (20,0), (0,30) $, intersection: $ 3x+2y=60, 2x+y=40 $ → $ x=20, y=0 $? Wait: solve: from $ y=40-2x $ into first: $ 3x+2(40-2x)=60 $ → $ 3x+80-4x=60 $ → $ -x=-20 $ → $ x=20, y=0 $. Actually intersection is (20,0) which is already a vertex. The other intersection is (0,30)? Check: $ 2(0)+y=40 $ gives $ y=40 $, but then $ 3(0)+2(40)=80>60 $, so (0,40) not feasible. So feasible vertices: (0,0), (20,0), (0,30) and (intersection of lines not boundary? Actually we need to find all vertices: (0,0), (20,0), (0,30), and intersection of the two lines gave (20,0) again. So feasible region is triangle with vertices (0,0), (20,0), (0,30). Evaluate: (0,0):0, (20,0):100, (0,30):90. Max at (20,0) with P=100.

But wait, check (10,10)? That is inside. So max is 100 at x=20,y=0.

Answer: 20 cakes, 0 cookies.

7. DSE-Style Practice Questions

Section A(2) & Section B Style

Question 1 MC
Which point is in the feasible region defined by $ x \ge 0, y \ge 0, x+y \le 4, 2x+y \le 5 $?
A. $ (1,3) $ B. $ (2,2) $ C. $ (3,1) $ D. $ (4,0) $

Question 2 MC
Maximize $ P = 2x + y $ subject to $ x \ge 0, y \ge 0, x+y \le 6, x+2y \le 8 $. The maximum value is:
A. $ 8 $ B. $ 10 $ C. $ 12 $ D. $ 14 $

Question 3 Short Answer
Find the vertices of the feasible region defined by $ x \ge 0, y \ge 0, 2x+3y \le 12, x+y \le 5 $.

Question 4 Short Answer
Maximize $ P = 4x + 5y $ subject to $ x \ge 0, y \ge 0, x+2y \le 8, 2x+y \le 10 $.

Question 5 MC
If $ x, y $ must be integers, what is the maximum of $ P = 3x + 4y $ subject to $ x \ge 0, y \ge 0, x+y \le 5, x+2y \le 7 $?
A. $ 15 $ B. $ 16 $ C. $ 17 $ D. $ 18 $

8. Solutions with Explanations

Question 1: B. $ (2,2) $
Check: $ 2+2=4 \le 4 $ ✓, $ 2(2)+2=6 \le 5 $? No, $ 6>5 $, so not feasible. Try C: $ (3,1): 3+1=4 \le 4 $ ✓, $ 2(3)+1=7 \le 5 $? No. Try D: $ (4,0): 4+0=4 \le 4 $ ✓, $ 2(4)+0=8 \le 5 $? No. So only A: $ (1,3): 1+3=4 $ ✓, $ 2(1)+3=5 \le 5 $ ✓. So A is feasible. Answer A.

Question 2: C. $ 12 $
Vertices: $ (0,0), (6,0), (0,4) $, intersection: $ x+y=6, x+2y=8 $ → $ x=4, y=2 $. Evaluate: $ (6,0):12, (0,4):4, (4,2):10 $. Max=12 at $ (6,0) $.

Question 3: $ (0,0), (5,0), (0,4), (2,3) $
Intersection: $ 2x+3y=12, x+y=5 $ → $ x=3, y=2 $? Let's solve: from $ x=5-y $ into first: $ 2(5-y)+3y=12 $ → $ 10-2y+3y=12 $ → $ y=2, x=3 $. So vertices: $ (0,0), (5,0), (0,4), (3,2) $.

Question 4: Max $ P=22 $ at $ (3,2) $
Vertices: $ (0,0), (5,0), (0,4) $, intersection: $ x+2y=8, 2x+y=10 $ → $ x=4, y=2 $. Evaluate: $ (5,0):20, (0,4):20, (4,2):4(4)+5(2)=16+10=26 $. Wait, check constraints: $ (4,2): x+2y=4+4=8 \le 8 $ ✓, $ 2x+y=8+2=10 \le 10 $ ✓. So max is 26 at (4,2). So answer 26.

Question 5: C. $ 17 $
Vertices: $ (0,0), (5,0), (0,3.5) $ (but integer), intersection: $ x+y=5, x+2y=7 $ → $ x=3, y=2 $. Evaluate integer points: $ (5,0):15, (0,3):12, (3,2):9+8=17, (2,2):14, (4,1):16 $. Max=17 at $ (3,2) $.

9. Exercise

Click the following link to have
An Exercise on Linear Programming | Feasible Region & Objective Function

Key Takeaways

What You Should Remember

Feasible region: The set of points satisfying all constraints; it is a convex polygon.
Vertex method: The optimal value occurs at a vertex of the feasible region.
Integer solutions: When variables must be integers, check feasible integer points near vertices.
Applications: Linear programming models real-world optimization problems.
Graphing: Use test points and solid/dashed lines correctly.
This topic guarantees 4–6 marks in DSE Paper 1 Section A(2) and Section B – master these skills!

Summary Checklist for Revision

Graph linear inequalities
Identify feasible region (shaded area)
Find vertices of feasible region
Evaluate objective function at vertices
Choose max/min
Handle integer solutions by checking nearby integer points
Translate word problems into constraints and objective

Linear Programming | Feasible Region & Objective Function

Synopsis

Learning Objectives

1. Introduction:

2. Graphing Linear Inequalities

Worked Example

3. Objective Function and Vertex Method

Worked Example

4. Integer Solutions

Worked Example

5. Applications (Word Problems)

Worked Example

6. Worked Examples

Example 1: Basic LP

Example 2: Integer Solution

Example 3: Word Problem

7. DSE-Style Practice Questions

8. Solutions with Explanations

9. Exercise

Key Takeaways

Summary Checklist for Revision

Keywords

DSE Maths Categories

DSE Maths Tags

Who is MathSir ?

DSE Mathematics

Friendly Links