Corrected Solutions to Linear Programming Problem Examples

(E9 to E17)

Verified Application of Graphical Method (Corner Point Method)

October 31, 2025

Contents
1 Introduction and Related Terminology 2

2 Mathematical Formulation of Linear Programming Problem 4

3 Different Types of Linear Programming Problems 6

1
Key Definitions in Linear Programming
• Linear Programming Problem (LPP): A mathematical technique used to find the best outcome
(maximum profit or minimum cost) for a given set of limited resources.

• Decision Variables (x, y, . . . ): The quantities we must decide upon (e.g., number of items to produce,
amount to invest). They are always non-negative.
• Objective Function (Z): The linear mathematical expression that represents the goal (e.g., Maximize Z =
10x + 6y or Minimize Z = 4x + y).
• Constraints: The linear inequalities or equations that represent the limitations on resources or
capacity (e.g., 2x + y ≤ 10).
• Non-Negativity Constraints: The requirement that decision variables cannot be negative (e.g.,
x ≥ 0, y ≥ 0). This ensures the solution makes physical sense.
• Feasible Region: The region (graphical area) defined by all the constraints and non-negativity
restrictions. Any point in this region represents a valid solution.
• Feasible Solution: Any combination of decision variable values (a point (x, y)) that lies within the
feasible region and satisfies all constraints.
• Infeasible Region/Problem: The area outside the feasible region. An LPP is Infeasible if no
point satisfies all constraints simultaneously (the feasible region is empty).

• Optimum Solution/Optimal Solution: The feasible solution that gives the absolute maximum
(for maximization problems) or minimum (for minimization problems) value of the objective function
Z.
• Unbounded Solution/Problem: A solution type where the feasible region is unlimited in the
direction of the objective function, allowing Z to increase (for Max LPP) or decrease (for Min LPP)
infinitely.
• Corner Points (Vertices): The points where the boundary lines of the constraints intersect. The
optimal solution, if it exists, always occurs at one or more of these corner points.

1 Introduction and Related Terminology

We begin with an easy, real-life scenario: the Sweet Success Bakery deciding how many Cakes and
Pies to bake daily.

Example Scenario: Sweet Success Bakery

The bakery aims to maximize daily profit.
• Cakes yield $10 profit; Pies yield $6 profit.
• Resources: Total 10 kg of Flour and 6 kg of Sugar are available.

• Usage: Cake requires 2 kg Flour, 1 kg Sugar. Pie requires 1 kg Flour, 1 kg Sugar.

• Capacity: The oven can only bake a maximum of 4 Cakes.

2
Familiarize with Terms Related to Linear Programming Problem
Q1: What are the quantities the bakery must decide upon to reach its goal?

• A: The number of Cakes and the number of Pies.

• Concept Illustrated: Decision Variables
– Let x be the number of Cakes.
– Let y be the number of Pies.

Q2: How can the bakery’s goal of maximizing profit be expressed mathematically?
• A: Profit is ($10 ×Cakes) + ($6 × Pies).

• Concept Illustrated: Objective Function

Maximize Z = 10x + 6y

Q3: What are the physical limitations (resources and capacity) that restrict the pro-
duction plan?
• A: Limitations on Flour, Sugar, and Oven Capacity.

• Concept Illustrated: Constraints

– Flour Constraint: 2x + 1y ≤ 10
– Sugar Constraint: 1x + 1y ≤ 6
– Oven Constraint: x ≤ 4

Q4: Can the number of Cakes or Pies produced be negative?

• A: No, production must be zero or positive.
• Concept Illustrated: Non-Negative Constraints

x ≥ 0, y≥0

Q5: What is the overall process of finding the specific combination of x and y that
results in the highest possible profit, given all the limitations?
• A: The process of finding the best value (maximum profit) subject to constraints.

• Concept Illustrated: Optimization

– We seek the maximum value of Z in the feasible region defined by the constraints.

Need for Framing Linear Programming Problem

Q6: Why frame this problem mathematically instead of just guessing the
production numbers?
∗ A: Because there are many conflicting constraints and many possible production plans.
LPP framing provides a systematic method to find the unique best solution among infinite
possibilities.
∗ Concept Illustrated: Need for Framing LPP
· LPP converts the complex resource allocation issue into a geometric problem (finding
a corner point), which is solvable using standard algorithms.

3
 2 Mathematical Formulation of Linear Programming
Problem
Example E7 : Complete Bakery Formulation (Up to 3 Non-
Trivial Constraints)
Q7: How do we set the problem in terms of decision variables, identify the
objective function, and identify the set of problem constraints?
· A: By explicitly defining x, y and the goal Z, and listing the resource limits.
· Complete LPP Formulation:

Maximize Z = 10x + 6y (Objective Function)

Subject to: 2x + y ≤ 10 (Flour Constraint - 1)
x+y ≤6 (Sugar Constraint - 2)
x≤4 (Capacity Constraint - 3)
x, y ≥ 0 (Non-Negative Constraints)

Solving E7 using the Graphical Method (Concept E8 )

Q8: How do we solve this LPP graphically to find the optimal production
plan?
· A: We plot the boundary lines, identify the feasible region, and test the corner points.
· Graphical Method Steps:
y (Pies)

10 L3 : x = 4
L1 : 2x + y = 10

V4 (0, 6)
6
L2 : x + y = 6

V3 (4, 2)

x (Cakes)
V1 (0, 0) V2 (4, 0) 5 6

1. Convert to Equalities & Find Intercepts:

L1 : 2x + y = 10 =⇒ (5, 0), (0, 10)

L2 : x + y = 6 =⇒ (6, 0), (0, 6)

L3 : x = 4 =⇒ Vertical line at x = 4
2. Identify Feasible Region: Since all constraints are ≤, the feasible region lies
below L1 and L2 , to the left of L3 , and in the first quadrant (x, y ≥ 0).
3. Find Corner Points (Vertices):
4. V1 : Origin (0, 0)

4
 5. V2 : Intersection of y = 0 and x = 4: (4, 0)
6. V3 : Intersection of x = 4 and L2 (x + y = 6): 4 + y = 6 =⇒ (4, 2)
7. V4 : Intersection of L2 (x + y = 6) and x = 0: (0, 6)
8. V5 : Intersection of x = 0 and y = 0: V1
9. Test Objective Function Z = 10x + 6y:
Vertex (x, y) Z = 10x + 6y
V1 (0, 0) 10(0) + 6(0) = 0
V2 (4, 0) 10(4) + 6(0) = 40
V3 (4, 2) 10(4) + 6(2) = 52
V4 (0, 6) 10(0) + 6(6) = 36
10. Optimal Solution: The maximum profit is $52 at (4, 2).

5
 3 Different Types of Linear Programming Problems
Example E9 : Manufacturing Problem (Maximization) - Cor-
rected Solution
Q9: Formulate and solve an LPP for a toy company making Dolls (x) and
Cars (y), aiming to maximize profit.
· Profit: Doll=$3, Car=$2.
· Time Constraint: Assembly time is 100 hours. Doll: 2 hrs, Car: 1 hr.
· Material Constraint: Plastic available is 50 units. Doll: 1 unit, Car: 1 unit.
· Market Constraint: Demand for Cars is at most 30.
Formulation:

Maximize Z = 3x + 2y
Subject to: L1 : 2x + y ≤ 100
L2 : x + y ≤ 50
L3 : y ≤ 30
x, y ≥ 0

Solution by Graphical Method

L1 : 2x + y = 100

y (Cars)

50
L2 : x + y = 50
40
V3 (20, 30)
V4 (0, 30)
30 L3 : y = 30

20

10

x (Dolls)
V1 (0, 0) 10 20 30 40 V2 (50,
50 0)

1. Corner Points (Vertices) of the Feasible Region:

2. V1 : (0, 0)
3. V2 : Intersection of y = 0 and L2 (x + y = 50) =⇒ (50, 0)
4. V3 : Intersection of L2 (x + y = 50) and L3 (y = 30) =⇒ (20, 30)
5. V4 : Intersection of x = 0 and L3 (y = 30) =⇒ (0, 30)
6. Test Objective Function Z = 3x + 2y:

6
 Vertex (x, y) Z = 3x + 2y
V1 (0, 0) 3(0) + 2(0) = 0
V2 (50, 0) 3(50) + 2(0) = 150
V3 (20, 30) 3(20) + 2(30) = 120
V4 (0, 30) 3(0) + 2(30) = 60

7. Optimal Solution: Max profit is $150 by making 50 Dolls and 0 Cars.

Example E10 : Diet Problem (Minimization)

Q10: Formulate and solve a problem for a dietician minimizing cost while
ensuring minimum nutritional intake.
· Cost: Supplement A (x): $4/unit, Supplement B (y): $1/unit.
· Requirement: Minimum 15 units of Calcium (Ca); Minimum 20 units of Protein
(Pro).
· Nutrient Content: A has 3 units Ca, 2 units Pro. B has 1 unit Ca, 4 units Pro.
Formulation:

Minimize Z = 4x + y
Subject to: L1 : 3x + y ≥ 15 (Calcium)
L2 : x + 2y ≥ 10 (Protein)
x, y ≥ 0

Solution by Graphical Method

y (Supp. B)

L1 : 3x + y = 15

L2 : x + 2y = 10
V2 (0, 5)
V3 (4, 3)

x (Supp. A)
V1 (5, 0)

1. Corner Points (Unbounded ≥ region): V1 (5, 0), V2 (0, 5), V3 (4, 3).
2. Test Z = 4x + y:
Vertex (x, y) Z = 4x + y
V1 (5, 0) 4(5) + 0 = 20
V2 (0, 5) 4(0) + 5 = 5
V3 (4, 3) 4(4) + 3 = 19
3. Optimal Solution: Min cost is $5 by using 0 units of A and 5 units of B.

7
 Example E11 : Transportation Problem (Minimization) - Cor-
rected Solution
Q11: Formulate and solve an LPP for shipping grain from two silos (x
from S1, y from S2) to a mill, minimizing cost.
· Cost: S1 to Mill: $5/ton, S2 to Mill: $4/ton.
· Requirement: Mill needs at least 120 tons.
· Capacity: S1 holds max 70 tons; S2 holds max 90 tons.
Formulation:

Minimize Z = 5x + 4y
Subject to: L1 : x + y ≥ 120 (Mill Demand)
L2 : x ≤ 70 (S1 Capacity)
L3 : y ≤ 90 (S2 Capacity)
x, y ≥ 0

Solution by Graphical Method

y (Tons from S2)

L2 : x = 70 L1 : x + y = 120
120
V3 (70,L90): y = 90
V290
(30, 90) 3

50
V1 (70, 50)

x (Tons from S1)

30 70 90 120
1. Corner Points: V1 (70, 50), V2 (30, 90), V3 (70, 90).
2. Test Z = 5x + 4y:
Vertex (x, y) Z = 5x + 4y
V1 (70, 50) 5(70) + 4(50) = 550
V2 (30, 90) 5(30) + 4(90) = 510
V3 (70, 90) 5(70) + 4(90) = 710
3. Optimal Solution: Min cost is $510 by shipping 30 tons from S1 and 90 tons
from S2.

Example E12 : Blending Problem (Quality Constraint) - Cor-

rected Solution
Q12: Formulate and solve an LPP for a metal alloy company blending
Steel 1 (x) and Steel 2 (y) to meet minimum strength requirements.
· Cost: Steel 1: $20/kg, Steel 2: $30/kg.
· Requirement: The blend must weigh exactly 50 kg and have an average strength of
at least 25 N/kg.
· Strength: Steel 1: 22 N/kg, Steel 2: 28 N/kg.
Formulation:

Minimize Z = 20x + 30y

Subject to: L1 : x + y = 50 (Total Weight)
L2 : 22x + 28y ≥ 1250 (Strength Requirement)
x, y ≥ 0

8
 Solution by Graphical Method

y (Steel 2, kg)

L1 : x + y = 50
VA (0, 50)
50
Feasible Region (Segment on L1 )
L2 : 22x + 28y = 1250
40

25 VB (25, 25)

10

x (Steel 1, kg)
10 25 40 50
1. Feasible Region: The feasible segment of L1 runs from (0, 50) to (25, 25).
2. Test Z = 20x + 30y on Feasible Endpoints:
Endpoint (x, y) Z = 20x + 30y
VA (0, 50) 20(0) + 30(50) = 1500
VB (25, 25) 20(25) + 30(25) = 1250
3. Optimal Solution: Min cost is $1250 by blending 25 kg of Steel 1 and 25 kg
of Steel 2.

Example E13 : Investment Problem (Maximization) - Corrected

Solution
Q13: Formulate and solve an LPP for a fund manager deciding between
two funds, F1 (x) and F2 (y), maximizing returns.
· Return: F1: 12%, F2: 8%.
· Budget: Total investment must be ≤ $50, 000.
· Rule 1: Investment in F1 must be at most 60% of the total investment (0.4x − 0.6y ≤ 0).
· Rule 2: F2 investment must be at least $10,000.
Formulation:

Maximize Z = 0.12x + 0.08y

Subject to: L1 : x + y ≤ 50000
2
L2 : 2x − 3y ≤ 0 (or y ≥ x)
3
L3 : y ≥ 10000
x, y ≥ 0

9
 Solution by Graphical Method

y (F2 Investment) (k)

50k L1 : x + y = 50k

40k

30k L2 : y = 23 x
V3 (30k, 20k)
20k

L3 : y = 10k
V1 (0, 10k)
10k
V2 (15k, 10k) V4 (40k, 10k)
x (F1 Investment) (k)
10k 20k 30k 40k 50k
1. Corner Points: V1 (0, 10000), V2 (15000, 10000), V3 (30000, 20000), V4 (40000, 10000).
2. Test Objective Function Z = 0.12x + 0.08y:
Vertex (x, y) Z = 0.12x + 0.08y
V1 (0, 10000) 0.12(0) + 0.08(10000) = 800
V2 (15000, 10000) 0.12(15000) + 0.08(10000) = 2600
V3 (30000, 20000) 0.12(30000) + 0.08(20000) = 5200
V4 (40000, 10000) 0.12(40000) + 0.08(10000) = 5600
3. Optimal Solution: Max return is $5600 by investing $40, 000 in F1 and
$10, 000 in F2.

Example E14 : Personnel Scheduling Problem (Minimization) -

Corrected Solution
Q14: Formulate and solve an LPP for a call center minimizing labor cost
using full-time (x) and part-time (y) workers.
· Cost: Full-time: $200/day, Part-time: $120/day.
· Total Employees: Must hire at least 15 employees.
· Rule 1: Full-time employees must be at least half the number of part-time employees.
Formulation:

Minimize Z = 200x + 120y

Subject to: L1 : x + y ≥ 15
L2 : x − 0.5y ≥ 0 (or y ≤ 2x)
x, y ≥ 0

10
 Solution by Graphical Method
L2 : y = 2x

y (Part-Time)
L1 : x + y = 15
15

V2 (5, 10)
10

x (Full-Time)
5 10 V1 (15,
15 0)
1. Corner Points (Unbounded ≥ region): V1 (15, 0), V2 (5, 10).
2. Test Z = 200x + 120y:
Vertex (x, y) Z = 200x + 120y
V1 (15, 0) 200(15) + 120(0) = 3000
V2 (5, 10) 200(5) + 120(10) = 2200
3. Optimal Solution: Min cost is $2200 by hiring 5 full − time and 10 part − time
employees.

Example E15 : Advertising Mix Problem (Maximization) - Cor-

rected Solution
Q15: Formulate and solve an LPP maximizing customer reach using Radio
ads (x) and Newspaper ads (y).
· Reach: Radio: 10,000 customers, Newspaper: 4,000 customers.
· Budget: Total budget is $5,000. Radio: $500/ad, Newspaper: $100/ad.
· Rule 1: Must run at least 5 Radio ads.
· Rule 2: Total ads cannot exceed 20.
Formulation:

Maximize Z = 10000x + 4000y

Subject to: L1 : 5x + y ≤ 50
L2 : x ≥ 5
L3 : x + y ≤ 20
x, y ≥ 0

11
 Solution by Graphical Method

y (Newspaper Ads)
L2 : x = 5
50
L1 : 5x + y = 50

40

30

20 L3 : x + y = 20

V4 (5, 15) V3 (7.5, 12.5)

12.5
10

x (Radio Ads)
V1 (5, 0) 5 7.510V2 (10,
15 0)20

1. Corner Points: V1 (5, 0), V2 (10, 0), V3 (7.5, 12.5), V4 (5, 15).
2. Test Objective Function Z = 10000x + 4000y:
Vertex (x, y) Z = 10000x + 4000y
V1 (5, 0) 10000(5) + 4000(0) = 50000
V2 (10, 0) 10000(10) + 4000(0) = 100000
V3 (7.5, 12.5) 10000(7.5) + 4000(12.5) = 125000
V4 (5, 15) 10000(5) + 4000(15) = 110000
3. Optimal Solution: Max reach is 125, 000 customers by running 7.5 Radio ads
and 12.5 Newspaper ads.

Example E16 : Agricultural Scheduling Problem (Maximization)

- Corrected Solution
Q16: Formulate and solve an LPP for planting Corn (x) and Soybeans (y)
maximizing profit based on planting season limits.
· Profit: Corn: $600/acre, Soybean: $450/acre.
· Total Land: 200 acres available.
· Planting Window (Time): Corn takes 2 days/acre, Soybeans 1 day/acre. Total
days available: 300.
· Rule: The acreage dedicated to Corn must be at least 50 acres.
Formulation:

Maximize Z = 600x + 450y

Subject to: L1 : x + y ≤ 200
L2 : 2x + y ≤ 300
L3 : x ≥ 50
x, y ≥ 0

12
 Solution by Graphical Method

y (Soybean Acres)
200 L3 : x = 50 L : x + y = 200
L2 : 2x1+ y = 300

V4150
(50, 150)
V3 (100, 100)
100

50

x (Corn Acres)
V1 (50,
50 0)100 150V2 200
(150, 0)

1. Corner Points: V1 (50, 0), V2 (150, 0), V3 (100, 100), V4 (50, 150).
2. Test Objective Function Z = 600x + 450y:
Vertex (x, y) Z = 600x + 450y
V1 (50, 0) 600(50) + 450(0) = 30000
V2 (150, 0) 600(150) + 450(0) = 90000
V3 (100, 100) 600(100) + 450(100) = 105000
V4 (50, 150) 600(50) + 450(150) = 97500
3. Optimal Solution: Max profit is $105, 000 by planting 100 acres of Corn
and 100 acres of Soybeans.

Example E17 : Material Procurement Problem (Minimization) -

CORRECTED DIAGRAM
Q17: Formulate and solve an LPP for a construction company minimizing
the cost of ordering sand (x) and gravel (y) to meet minimum volume and
weight requirements.
· Cost: Sand: $10/cubic meter, Gravel: $15/cubic meter.
· Volume Requirement: Need at least 500 cubic meters total.
· Weight Requirement: Sand weighs 1 ton/cubic meter, Gravel weighs 1.5 tons/cubic
meter. Need at least 600 tons total.
Formulation:

Minimize Z = 10x + 15y

Subject to: L1 : x + y ≥ 500 (Volume)
L2 : x + 1.5y ≥ 600 (Weight)
x, y ≥ 0

13
 Solution by Graphical Method

y (Gravel, m3 )
V2 (0, 500)
500 L1 : x + y = 500

400 L2 : x + 1.5y = 600

V3 (300, 200)
200

100
Optimal Segment (Z=6000)
x (Sand, m3 )
100 300 500 600V1 (600, 0)
1. Corner Points (Unbounded ≥ region): V1 (600, 0), V2 (0, 500), V3 (300, 200).
2. Test Z = 10x + 15y:
Vertex (x, y) Z = 10x + 15y
V1 (600, 0) 10(600) + 15(0) = 6000
V2 (0, 500) 10(0) + 15(500) = 7500
V3 (300, 200) 10(300) + 15(200) = 6000
3. Optimal Solution: Min cost is $6000. This is a case of Multiple Optimal
Solutions. Any point on the line segment connecting (600, 0) and (300, 200) is
optimal.
1. Corner Points (Unbounded ≥ region): V1 (600, 0), V2 (0, 500), V3 (300, 200).
2. Test Z = 10x + 15y:
Vertex (x, y) Z = 10x + 15y
V1 (600, 0) 10(600) + 15(0) = 6000
V2 (0, 500) 10(0) + 15(500) = 7500
V3 (300, 200) 10(300) + 15(200) = 6000
3. Optimal Solution: Min cost is $6000. This is a case of Multiple Optimal
Solutions. Any point on the line segment connecting (600, 0) and (300, 200) is
optimal.

Example E18 : Infeasible LPP (Concept E20 ) - Corrected Solu-

tion
Q18: Formulate a scenario where the constraints conflict, making a solu-
tion impossible.
· A: A factory must produce at least 10 widgets (x ≥ 10) and at least 10 gadgets
(y ≥ 10). However, total labor is only enough to produce a maximum of 15 items
(x + y ≤ 15).
Formulation illustrating Infeasibility:

Maximize Z = x + y
Subject to: L1 : x + y ≤ 15
L2 : x ≥ 10
L3 : y ≥ 10
x, y ≥ 0

14
 Explanation: The set of points satisfying both x ≥ 10 and y ≥ 10 requires x+y ≥ 20.
This directly conflicts with x + y ≤ 15. There is no common solution region; thus,
the problem is Infeasible.
y

L2 : x = 10

L1 : x + y = 15
No Solution

Required x + y ≥ 20
Infeasible Region

L3 : y = 10

Example E19 : Unbounded LPP (Concept E20 )

Q19: Formulate a scenario where the objective function can theoretically
increase infinitely.
· A: A company has no resource constraints other than minimum production require-
ments, and the goal is to maximize profit.
· Problem Statement: Maximize profit Z from two products x and y (profit $5/unit
and $7/unit, respectively), given that production of x must be at least 10 units and
production of y must be at least 5 units.
Formulation illustrating Unboundedness:

Maximize Z = 5x + 7y
Subject to: x ≥ 10
y≥5
x, y ≥ 0

Explanation: The feasible region extends infinitely into the first quadrant. Since
the profit function Z increases as x and y increase, the objective function value can
grow without limit, meaning the LPP is Unbounded (in practice, this signals that
necessary constraints were omitted from the model).

15
y

L1 : x = 10

Unbounded Max Z

L2 : y = 5
(10, 5)

16