Linear Programming: The

Graphical Method

1
Introduction

2
Introduction
• Since most real world problems have more
than two decision variables, such problems
cannot be solved graphically.
• However, graphical approach provides
understanding of solving an LP problem
algebraically, involving more than two
variables.
• Though two-variable problems hardly exist in
practice, the treatment provides concrete
foundations for the development of the
general simplex algorithm presented in
Chapter 3. 3
Example
Reddy Mikks produces both interior and exterior paints from
two raw materials, Ml and M2. The following table provides the
basic data of the problem:

A market survey indicates that the daily demand for interior

paint cannot exceed that for exterior paint by more than 1 ton.
Also, the maximum daily demand for interior paint is 2 tons.
Reddy Mikks wants to determine the optimum (best) product
mix of interior and exterior paints that maximizes the total
daily profit.
4
Solution

• Any values of X1 and X2 that satisfy all five constraints

constitute a feasible solution. Otherwise, the solution is
infeasible.
• For example, the solution, X1 = 3 tons per day and X2 = 1 ton
per day, is feasible because it does not violate any of the
constraints, including the nonnegativity restric­tions.

5
Solution

The feasible solution space of the problem represents the area

in the first quadrant in which all the constraints are satisfied
simultaneously.
6
Solution

• An important characteristic of the optimum LP solution is that it

is always associated with a corner point of the solution space
(where two lines intersect).
• This is true even if the objective function happens to be parallel
to a constraint.
7
Solution
• For exam­ple, if the objective function is z = 6X1 + 4X2,
which is parallel to constraint 1, we can always say that the
optimum occurs at either corner point B or corner point C.
• Actu­ally any point on the line segment BC will be an
alternative optimum, but the important observation here is
that the line segment BC is totally defined by the corner
points B and C.
• The observation that the LP optimum is always associated
with a corner point means that the optimum solution can
be found simply by enumerating all the corner points as
the following table shows:

8
Solution

9
Graphical Solution
Methods:

• Extreme point solution method

• Iso-profit (cost) function line method

10
Terminology for solution of LP
• Solution:
• A feasible solution is a solution for which all the
constraints are satisfied.
• A corner point feasible solution (CPF) is a feasible
solution that lies at a corner point.
• An infeasible solution is a solution for which at least
one constraint is violated.
• The feasible region is the collection of all feasible
solution.
• An Optimal solution is a feasible solution that has the
most favorable value of the objective function. (it is
always one of the CPF solution
• The most favorable value is the largest (smallest) value
if the objective function is to be maximized (minimized).
• An unbounded solution is a solution that increase or
decrease infinitely the value of the objective function of
the LP. 11
Terminology for solution of LP
• Basic Solution:- For a set of m simultaneous
equations in ‘n’ variables ( n > m), a solution obtained
by setting ‘n – m’ variables equal to zero and solving
for remaining ‘m’ equations in ‘n’ variables is called a
basic solution. The n – m variables whose value did
not appear in the solution are called non – basic
variables and the remaining variables are called basic
variables.
• Basic Feasible Solution (BFS):- A feasible solution to
an LPP which is also the basic solution is called BFS.
ie, all basic variables assume non negative values.
BFS are of two types.
– Degenerate: A BFS is called degenerate if the value of at least
one basic variable is zero.
– Non – Degenerate: A BFS is called non – degenerate if the
value of all m basic variables are non – zero and positive. 12
Terminology for solution of LP
• Optimal BFS: - A BFS which optimizes the objective
function of the given LPP is called an Optimal BFS.

13
Graphical solution
• While obtaining the optimal solution to the LP
problem by the graphical method , the statements
of the following theorems of linear programming is
used:-

• Theorems I:- The feasible solution space

constitutes a convex set.

• Theorems II:- within the feasible solution space,

feasible solution correspond to the extreme (or
Corner) points of the feasible solution space.

• Theorem III:- There are a finite number of basic

feasible solution with the feasible solution space.
14
Graphical solution

• Theorem IV:- The optimum feasible solution, if it exists. will

occur at one, or more, of the extreme points that are basic
feasible solutions.

• Note.
Convex set is a polygon "Convex" implies that if any two points of the
polygon are selected arbitrarily then straight line segment Joining these
two points lies completely within the polygon. The extreme points of the
convex set are the basic solution to the linear programming problem.

15
Graphical solution
Extreme point solution method:

1. Plot each constraint as an equation and then decide which

side of the line is feasible (if it’s an inequality).
2. Find the feasible region.
3. find the coordinates of the corner (extreme) points of the feasible
region.

4. Substitute the corner point coordinates in the objective function

5. Choose the optimal solution

16
Example 1: A Minimization Problem

• LP Formulation
Min z = 5x1 + 2x2
s.t. 2x1 + 5x2 > 10
4x1 - x2 > 12
x 1 + x2 > 4
x1, x2 > 0
17
Example 1: Graphical Solution
• Graph the Constraints
• Constraint 1: When x1 = 0, then x2 = 2; when x2 =
0, then x1 = 5. Connect (5,0) and (0,2). The ">" side
is above this line.
• Constraint 2: When x2 = 0, then x1 = 3. But
setting x1 to 0 will yield x2 = -12, which is not on
the graph. Thus, to get a second point on this
line, set x1 to any number larger than 3 and solve
for x2: when x1 = 5, then x2 = 8. Connect (3,0) and
(5,8). The ">" side is to the right.
• Constraint 3: When x1 = 0, then x2 = 4; when x2 =
0, then x1 = 4. Connect (4,0) and (0,4). The ">" side
is above this line.
18
Example 1: Graphical Solution
• Constraints Graphed

x22 Feasible Region

4x11 - x22 > 12

5
4
x11 + x22 > 4

3
2x11 + 5x22 > 10
2
(16/5,4/5)
1 (10/3, 2/3)
x11
1 2 3 4 5 6
(5,0) 19
Example 1: Graphical Solution
• Solve for the Extreme Point at the Intersection of the second and third Constraints
4x1 - x2 = 12
x1+ x2 = 4
Adding these two equations gives:
5x1 = 16 or x1 = 16/5.
Substituting this into x1 + x2 = 4 gives: x2 = 4/5
• Solve for the extreme point at the intersection of the first and third constraints
2x1 + 5x2 =10
x1 + x2= 4
Multiply the second equation by -2 and add to the first equation, gives
3x2 = 2 or x2 = 2/3
Substituting this in the second equation gives x1 = 10/3

Point Z
(16/5, 4/5) 88/5
(10/3, 2/3) 18
(5, 0) 25 20
Example 2: A Maximization Problem

Max z = 5x1 + 7x2

s.t. x1 < 6
2x1 + 3x2 < 19
x1 + x2 < 8
x1, x2 > 0
21
Example 2: A Maximization Problem
• Constraint #1 Graphed
x2
8

6
x1 < 6
5

1 (6, 0)

1 2 3 4 5 6 7 8 9 10
x1
22
Example 2: A Maximization Problem
• Constraint #2 Graphed
x2

8 (0, 6 1/3)
7

6 2x1 + 3x2 < 19

5

4
3

2
(9 1/2, 0)
1

1 2 3 4 5 6 7 8 9 10
x1
23
Example 2: A Maximization Problem
• Constraint #3 Graphed
x2
(0, 8)
8

6
x1 + x2 < 8
5

1 (8, 0)

1 2 3 4 5 6 7 8 9 10
x1
24
Example 2: A Maximization Problem
• Combined-Constraint Graph
x2
8
x1 + x2 < 8
7

6
x1 < 6
5

2
2x1 + 3x2 < 19
1

1 2 3 4 5 6 7 8 9 10
x1
25
Example 2: A Maximization Problem
• Feasible Solution Region
x2
8

2 Feasible
1
Region

1 2 3 4 5 6 7 8 9 10
x1
26
Example 2: A Maximization Problem
• The Five Extreme Points

7
5
(0, 19/3) 6

4 (5, 3)
3
4

2 Feasible 3 (6, 2)
1
Region
1 2
(0, 0) x1
1 2 3 4 5 6 7 8 9 10

(6, 0) 27
Example 2: A Maximization Problem
• Having identified the feasible region for the
problem, we now search for the optimal
solution, which will be the point in the
feasible region with the largest (in case of
maximization or the smallest (in case of
minimization) of the objective function.
• To find this optimal solution, we need to
evaluate the objective function at each one of
the corner points of the feasible region.

28
Example 2: A Maximization Problem
• Optimal Solution
Point Z
x2
(0,0) 0
8
(6,0) 30
7
(6,2) 44
6
Optimal Solution (5,3) 46
5
(0,19/3) 44.33
4

1 2 3 4 5 6 7 8 9 10
x1
29
Extreme Points and the Optimal Solution
• The corners or vertices of the feasible region
are referred to as the extreme points.
• An optimal solution to an LP problem can be
found at an extreme point of the feasible
region.
• When looking for the optimal solution, you do
not have to evaluate all feasible solution
points.
• You have to consider only the extreme points
of the feasible region.

30
Feasible Region
• The feasible region for a two-variable linear
programming problem can be nonexistent, a single
point, a line, a polygon, or an unbounded area.
• Any linear program falls in one of three categories:
– is infeasible
– has a unique optimal solution or alternate optimal
solutions
– has an objective function that can be increased
without bound
• A feasible region may be unbounded and yet there may
be optimal solutions. This is common in minimization
problems and is possible in maximization problems.
31
Special Cases
• Alternative Optimal Solutions
In the graphical method, if the objective function
line is parallel to a boundary constraint in the
direction of optimization, there are alternate
optimal solutions, with all points on this line
segment being optimal.
• Infeasibility
A linear program which is overconstrained so that
no point satisfies all the constraints is said to be
infeasible.
• Unbounded
For a max (min) problem, an unbounded LP occurs
in it is possible to find points in the feasible region
with arbitrarily large (small) Z
32
Example with Multiple Optimal
Solutions
x2
z1 z2 z3
Maximize z = 3x1 – x2
4

3 subject to 15x1 – 5x2  30

2
10x1 + 30x2  120
1
x1  0, x2  0
0
0 1 2 3 4 x1

33
Example: Infeasible Problem
• Solve graphically for the optimal solution:

Max z = 2x1 + 6x2

s.t. 4x1 + 3x2 < 12

2x1 + x2 > 8
x1, x2 > 0

34
Example: Infeasible Problem
• There are no points that satisfy both
constraints, hence this problem has no
feasible region, and no optimal solution.
x2

8 2x1 + x2 > 8

4x1 + 3x2 < 12

4

x1
3 4 35
Example: Unbounded Problem
• Solve graphically for the optimal solution:

Max z = 3x1 + 4x2

s.t. x1 + x2 > 5
3x1 + x2 > 8

x1, x2 > 0

36
Example: Unbounded
•
Problem
The feasible region is unbounded and the objective
function line can be moved parallel to itself without
bound so that z can be increased infinitely.

x2

3x1 + x2 > 8
8

5
x1 + x2 > 5

x1
2.67 5 37
Solve the following LP graphically
max 45 x1 + 60 x2 Objective Function
s.t. 10 x1 + 20 x2  1800 A Structural
28 x1 + 12 x2  1440 B constraints
6 x1 + 15 x2  2040 C
15 x1 + 10
0 x2  2400 D
x1  40 E
x2  100 F
x1 ≥ 0, x2 ≥ 0 nonnegativity

Where x1 is the quantity produced

Are the LP
from product Q, and x2 is the
assumptions
quantity of product P valid for this problem?

38
The graphical solution
P
Assignment:
240 Max Q Complete the
E problem to find the
200
D optimal solution
160

120 Max P
F
80 A
(
40 1
B C
)
0
0 40 80 120 160 200 240 280 320 360 Q
39
Possible Outcomes of an LP

1. Infeasible – feasible region is empty; e.g., if the

constraints include
x1+ x2  6 and x1+ x2  7

2. Unbounded - Max 15x1+ 7x2 (no finite optimal

s.t. x1 + x2  1 solution)
x1, x2  0

3. Multiple optimal solutions - max 3x1 + 3x2

s.t. x1+ x2  1
x1, x2  0

4. Unique Optimal Solution

Note: multiple optimal solutions occur in many practical (real-world) LPs.

40
41