PED 151 Operations Research (OR)
LP – Graphical Solution
Fall 2024-2025
Example 1 – Beaver Creek Pottery Company
Resource Requirements
Labor Clay Profit
Product
(hr/unit) (lb/unit) ($/unit)
Bowl 1 4 40
Mug 2 3 50
Resource
40 hr/day 120 lbs
Availability
Step 1: Decision variables
x1 = number of bowls to produce per day
x2 = number of mugs to produce per day
2 OR – LP Graphical Solution
Example 1 – Beaver Creek Pottery Company (Cont’d)
Step 2: Objective Function
Maximize Profit Z
Complete Linear Programming
Z = 40 x1 + 50 x2 Model:
Step 3: Constraints Maximize Z = $40x1 + $50x2
• Resource Constraints
Subject to:
1x1 + 2x2 40 (hours of labor)
1x1 + 2x2 40
4x1 + 3x2 120 (pounds of clay) 4x1 + 3x2 120
x1, x2 0
• Non-Negativity Constraints
x1 0 and x2 0
3 OR – LP Graphical Solution
Example 1 – Beaver Creek Pottery Company
Graphical Solution
x2
50 –
Complete Linear
Programming Model: 40 –
4 x1 + 3 x2 <120 lb
Maximize Z = $40 x1 + 50 x2
Maximize Z = $40x1 + 30 –
Optimal point:
$50x2 Area common to x1* = 24 bowls
20 –
Subject to: both constraints x2* = 8 mugs
• 1x1 + 2x2 40 (Feasibility Region) Z* = $1,360
10 –
• 4x1 + 3x2 120 x1 + 2 x2 <40 hr
• x1, x2 0 0– | | | | | |
10 20 30 40 50 60 x1
4 OR – LP Graphical Solution
Graphical Solution
Can be used when there are two decision variables
The solution steps are:
1. Plot the constraint equations at their limits by converting
each equation to an equality
2. Identify the feasible solution space
3. Create an iso-profit line based on the objective function
4. Move this line outwards until the optimal point is identified
(for a maximization problem)
5 OR – LP Graphical Solution
Example 2 – Product Mix Problem
Maximize Profit = $7X1 + $5X2 X2
Subject to: 100 –
–
4X1 + 3X2 ≤ 240 (Constraint A)
80 –
2X1 + 1X2 ≤ 100 (Constraint B)
Number of Watch-TVs
– Assembly (constraint B)
X1, X2 ≥ 0 60 –
–
40 –
1. Plotting the constraint equations –
Electronics (constraint A)
Disregard the inequality portion of 20 –
the constraints (< or >). –
Make each constraint an equality (=) –
| | | | | | | | | | | X1
transforms it into the equation for a 0 20 40 60 80 100
straight line. Number of Walkmans
6 OR – LP Graphical Solution
Example 2 – Product Mix Problem (Cont’d)
Maximize Profit = $7X1 + $5X2 X2
Subject to: 100 –
4X1 + 3X2 ≤ 240 (Constraint A) –
2X1 + 1X2 ≤ 100 (Constraint B) 80 – Assembly (constraint B)
Number of Watch-TVs
–
X1, X2 ≥ 0
60 –
–
2. Identifying the feasible region 40 –
– Electronics (constraint A)
It is the area on the graph that 20 – Feasible
contains the solutions that satisfy –
region
all the constraints simultaneously. –| | | | | | | | | | | X1
0 20 40 60 80 100
Number of Walkmans
7 OR – LP Graphical Solution
Example 2 – Product Mix Problem (Cont’d)
Maximize Profit = $7X1 + $5X2 X2
Subject to: 100 –
4X1 + 3X2 ≤ 240 (Constraint A) –
2X1 + 1X2 ≤ 100 (Constraint B) 80 –
Number of Watch-TVs
–
X1, X2 ≥ 0
60 –
$210 = $7X1 + $5X2
–
(0, 42)
3. Create an iso-profit line based 40 –
on the objective function –
20 – (30, 0)
Choose a possible value for the
–
objective function
0 –| | | | | | | | | | | X1
Solve for the axis intercepts of the 0 20 40 60 80 100
function and plot the line Number of Walkmans
8 OR – LP Graphical Solution
Example 2 – Product Mix Problem (Cont’d)
Maximize Profit = $7X1 + $5X2
X2
Subject to:
100 –
4X1 + 3X2 ≤ 240 (Constraint A) – $350 = $7X1 + $5X2
2X1 + 1X2 ≤ 100 (Constraint B) 80 –
Number of Watch-TVs
$280 = $7X1 + $5X2
X1, X2 ≥ 0 –
60 – $210 = $7X1 + $5X2
–
4. Move this line outwards until 40 –
the optimal point is identified –
$420 = $7X1 + $5X2
20 –
–
0 –| | | | | | | | | | | X1
0 20 40 60 80 100
Number of Walkmans
9 OR – LP Graphical Solution
Example 2 – Product Mix Problem (Cont’d)
X2
100 –
– Maximum profit line
Number of Watch-TVs
80 –
–
60 – Optimal solution point
– (X1 = 30, X2 = 40)
40 –
–
$410 = $7X1 + $5X2
20 –
–
0 –| | | | | | | | | | | X1
0 20 40 60 80 100
Number of Walkmans
10 OR – LP Graphical Solution
Example 2 – Product Mix Problem (Cont’d)
Corner Point Method: X2
Corner point: A point that lies at
the intersection of two (or possibly 100 –
more) constraint lines on the 2 –
Number of Watch-TVs
boundary of the feasible region. 80 –
–
Even though all the points in the
60 –
feasible region represent possible
–
solutions, we can limit our search 3
40 –
to the corner points.
–
No interior points in the feasible 20 –
region need be considered because –
at least one corner point is better X1
1 0 –| | | | | | | | | | |
than any interior point. 0 20 40 4 60 80 100
Number of Walkmans
11 OR – LP Graphical Solution
Corner-Point Method
The optimal value will always be at a corner point
Find the objective function value at each corner point
and choose the one with the highest profit
Solve for the intersection of two constraints
4X1 + 3X2 ≤ 240 (electronics time)
2X1 + 1X2 ≤ 100 (assembly time)
Point 1: (X1 = 0, X2 = 0) Profit $7(0) + $5(0) = $0
Point 2: (X1 = 0, X2 = 80) Profit $7(0) + $5(80) = $400
Point 4: (X1 = 50, X2 = 0) Profit $7(50) + $5(0) = $350
Point 3: (X1 = 30, X2 = 40) Profit $7(30) + $5(40) = $410
12 OR – LP Graphical Solution
Example 3 – Resource Utilization
Decision Variables
X1 = number of tons of black-and-white chemical produced
X2 = number of tons of colour picture chemical produced
Objective Function
Minimize total cost = 2,500X1 + 3,000X2
Subject to:
X1 ≥ 30 (tons of black-and-white chemical)
X2 ≥ 20 (tons of colour chemical)
X1 + X2 ≥ 60 (tons total)
X1 , X2 ≥ 0 (non-negativity requirements)
13 OR – LP Graphical Solution
Example 3 – Resource Utilization (Cont’d)
Point (a) = (40, 20) X2
60 – X1 + X2 = 60
Z at (a) = $160,000
50 –
Feasible
region
Point (b) = (30, 30) 40 –
Z at (b) = $165,000 30 –
b
20 –
a
Lowest total cost is at 10 –
X1 = 30
X2 = 20
point (a) | | | | | | | X1
0 10 20 30 40 50 60
14 OR – LP Graphical Solution
Example 4 – Airline Flights
A local Airline Company is considering air service from its hub of operations
in Germany to Rome, and Dublin. They have one gate at Berlin Airport, which
operates 12 hours per day.
Each flight requires 1 hour of gate time and the pilot crew labour is limited to
150 hours per day.
Each flight to Rome consumes 15 hours of pilot crew time and is expected to
produce a profit of €2,500. The market for service to Rome is limited to 9
flights per day.
Serving Dublin uses 10 hours of pilot crew time per flight and will result in a
profit of €2,000 per flight.
Determine the number of daily flights to Rome and Dublin to maximize total
profit.
15 OR – LP Graphical Solution
Example 4 – Airline Flights (Cont’d)
Decision Variables
x1 = number of flights per day to Rome
x2 = number of flights per day to Dublin
The objective function is to maximize profits (Z)
Maximize Z = € 2,500x1 + € 2,000x2
The constraints are:
x1 + x2 ≤ 12 (gate capacity)
15x1 + 10 x2 ≤ 150 (labour)
x1 ≤9 (market)
x1 , x2 ≥ 0 (non-negativity requirements)
16 OR – LP Graphical Solution
Example 4 – Airline Flights (Cont’d)
x2
15 — A careful drawing
15 x1 + 10 x2 ≤ 150 (labor) of iso-profit lines
parallel to the one
E shown indicates
that point D is the
10 — optimal solution.
x1 ≤ 9 (market)
D
5—
Feasible
x1 + x2 ≤ 12 (gate)
region
C
B
0— | | | x1
A 5 10 15
17 OR – LP Graphical Solution
Example 4 – Airline Flights (Cont’d)
x2
15 —
15 x1 + 10 x2 ≤ 150 (labor)
The maximum profit results from
E´
making six flights to Rome and six
10 —
flights to Dublin
$2,500(6) + $2,000(6) = $27,000
x1 ≤ 9 (market)
D´
5—
Feasible
x1 + x2 ≤ 12 (gate)
region
C
B
0— | | | x1
A 5 10 15
18 OR – LP Graphical Solution
Example 5
Find the maximum
values of the function: 3–
z = 5x + 2y, 3x + 2y ≥ 6
Given the following set
of constraints:
2–
2x + 3y ≥ 6,
3x + 2y ≥ 6,
x& y≥0 2x + 3y ≥ 6
1-
Unbounded
I I I
Solution 1 2 3
19 OR – LP Graphical Solution 19
Example 6
Find the minimum
values of the function 5–
z = 5x + 2y,
4-
Given the following set
of constraints: 3x + 3y ≤ 9
3-
3x + 3y ≤ 9, 4x + 5y ≥ 20
4x + 5y ≥ 20, 2–
x and y ≥ 0
1-
Infeasible Solution I I I I I
1 2 3 4 5
20 OR – LP Graphical Solution 20
Example 7
• Maximize the function:
z = $40x1 + 30x2,
• Given the following set of
constraints:
• 1x1 + 2x2 40
• 4x1 + 3x2 120
• x 1 & x2 0
• Objective function is parallel
to a constraint line.
Multiple Optimal Solutions
21 OR – LP Graphical Solution
Irregular Types of Linear Programming Problems
For some linear programming models, the general rules do not apply
Multiple optimal solutions: More than one solutions
gives an optimum answer
Infeasible solutions: Every possible solution violates at
least one constraint
Unbounded solutions: Value of objective function
increases indefinitely
22 OR – LP Graphical Solution
Graphical Solution – Exercise
Find the maximum values of the function
z = 3x1 + 5x2,
Given the following set of constraints:
x1 ≤ 4,
2x2 ≤ 12,
3x1 + 2x2 ≤ 18,
3x1 + 5x2 ≤ 50,
x1 & x2 ≥ 0
Will the optimum solution change if z = 3x1 + 2x2?
23 OR – LP Graphical Solution
23
Thank You
Questions?
Dalia.rashed@alexu.edu.eg
