Lectuer_4_Linear Programming : Special Cases in Graphical Method

4.1 Multiple Optimal Solution

Example 1
Solve by using graphical method

Max Z = 4x1 + 3x2 Subject to
4x1+ 3x2 ? 24
x1 ? 4.5
x2 ? 6
x1 ? 0 , x2 ? 0

Solution

The first constraint 4x1+ 3x2 ? 24, written in a form of equation 4x1+ 3x2 = 24
Put x1 =0, then x2 = 8 Put x2 =0, then x1 = 6
The coordinates are (0, 8) and (6, 0)

The second constraint x1 ? 4.5, written in a form of equation
x1 = 4.5

The third constraint x2 ? 6, written in a form of equation
x2 = 6





1






The corner points of feasible region are A, B, C and D. So the coordinates for the corner points are
A (0, 6)
B (1.5, 6) (Solve the two equations 4x1+ 3x2 = 24 and x2 = 6 to get the coordinates) C (4.5, 2) (Solve the two equations 4x1+ 3x2 = 24 and x1 = 4.5 to get the coordinates) D (4.5, 0)

We know that Max Z = 4x1 + 3x2 At A (0, 6)
Z = 4(0) + 3(6) = 18

At B (1.5, 6)
Z = 4(1.5) + 3(6) = 24

At C (4.5, 2)
Z = 4(4.5) + 3(2) = 24


At D (4.5, 0)
Z = 4(4.5) + 3(0) = 18

Max Z = 24, which is achieved at both B and C corner points. It can be achieved not only at B and C but every point between B and C. Hence the given problem has multiple optimal solutions.















4.2 No Optimal Solution

Example 1

Solve graphically

Max Z = 3x1 + 2x2 Subject to
x1+ x2 ? 1
x1+ x2 ? 3
x1 ? 0 , x2 ? 0

Solution

The first constraint x1+ x2 ? 1, written in a form of equation
x1+ x2 = 1
Put x1 =0, then x2 = 1 Put x2 =0, then x1 = 1
The coordinates are (0, 1) and (1, 0)

The first constraint x1+ x2 ? 3, written in a form of equation
x1+ x2 = 3
Put x1 =0, then x2 = 3 Put x2 =0, then x1 = 3
The coordinates are (0, 3) and (3, 0)








There is no common feasible region generated by two constraints together i.e. we cannot identify even a single point satisfying the constraints. Hence there is no optimal solution.







4. 3 Unbounded Solution

Example
Solve by graphical method

Max Z = 3x1 + 5x2 Subject to
2x1+ x2 ? 7 x1+ x2 ? 6 x1+ 3x2 ? 9
x1 ? 0 , x2 ? 0

Solution

The first constraint 2x1+ x2 ? 7, written in a form of equation
2x1+ x2 = 7
Put x1 =0, then x2 = 7 Put x2 =0, then x1 = 3.5
The coordinates are (0, 7) and (3.5, 0)

The second constraint x1+ x2 ? 6, written in a form of equation
x1+ x2 = 6
Put x1 =0, then x2 = 6 Put x2 =0, then x1 = 6
The coordinates are (0, 6) and (6, 0)


The third constraint x1+ 3x2 ? 9, written in a form of equation
x1+ 3x2 = 9
Put x1 =0, then x2 = 3 Put x2 =0, then x1 = 9
The coordinates are (0, 3) and (9, 0)










The corner points of feasible region are A, B, C and D. So the coordinates for the corner points are
A (0, 7)
B (1, 5) (Solve the two equations 2x1+ x2 = 7 and x1+ x2 = 6 to get the coordinates)
C (4.5, 1.5) (Solve the two equations x1+ x2 = 6 and x1+ 3x2 = 9 to get the coordinates) D (9, 0)

We know that Max Z = 3x1 + 5x2 At A (0, 7)
Z = 3(0) + 5(7) = 35

At B (1, 5)
Z = 3(1) + 5(5) = 28

At C (4.5, 1.5)
Z = 3(4.5) + 5(1.5) = 21

At D (9, 0)
Z = 3(9) + 5(0) = 27
The values of objective function at corner points are 35, 28, 21 and 27. But there exists infinite number of points in the feasible region which is unbounded. The value of objective function will be more than the value of these four corner points i.e. the maximum value of the objective function occurs at a point at ?. Hence the given problem has unbounded solution.