Question

Identify the type of optimal solution for the following LP problems by the graphical solution method. Show your work

(1)   Min    2X₁ + 3X₂

            S.T.   2X₁ - 2X₂    <=   2

                  -2X₁ +   X₂    <=   1

                  X₁ => 0,    X₂ => 0

If the objective function of the above formulation is changed from Min 2X₁ + 3X₂ to Max 2X₁ + 3X₂, what type of optimal solution does this problem provide? Note that all constraints remain unchanged.

Answer 1

Solution:

MIN Zx = 2 x1 + 3 x2

subject to

2 x1 - 2 x2 ≤ 2 - 2 x1 + x2 ≤ 1

and x1,x2≥0;

Hint to draw constraints

1. To draw constraint 2x1-2x2≤2→(1)

Treat it as 2x1-2x2=2

When x1=0 then x2=?

⇒2(0)-2x2=2

⇒-2x2=2

⇒x2=2-2=-1

When x2=0 then x1=?

⇒2x1-2(0)=2

⇒2x1=2

⇒x1=22=1

x1	0	1
x2	-1	0

2. To draw constraint -2x1+x2≤1→(2)

Treat it as -2x1+x2=1

When x1=0 then x2=?

⇒-2(0)+x2=1

⇒x2=1

When x2=0 then x1=?

⇒-2x1+(0)=1

⇒-2x1=1

⇒x1=1-2=-0.5

x1	0	-0.5
x2	1	0

The value of the objective function at each of these extreme points is as follows:

Extreme Point Coordinates (x1,x2)	Lines through Extreme Point	Objective function value Z=2x1+3x2
A(0,1)	2→-2x1+x2≤1 3→x1≥0	2(0)+3(1)=3
B(0,0)	3→x1≥0 4→x2≥0	2(0)+3(0)=0
C(1,0)	1→2x1-2x2≤2 4→x2≥0	2(1)+3(0)=2

The miniimum value of the objective function Z=0 occurs at the extreme point (0,0).

Hence, the optimal solution to the given LP problem is : x1=0,x2=0 and min Z=0.

WHEN THE FORMULATION IS CHANGED FROM MIN TO MAX

Problem is

MAX Zx = 2 x1 + 3 x2

subject to

2 x1 - 2 x2 ≤ 2 - 2 x1 + x2 ≤ 1

and x1,x2≥0;

Hint to draw constraints

1. To draw constraint 2x1-2x2≤2→(1)

Treat it as 2x1-2x2=2

When x1=0 then x2=?

⇒2(0)-2x2=2

⇒-2x2=2

⇒x2=2-2=-1

When x2=0 then x1=?

⇒2x1-2(0)=2

⇒2x1=2

⇒x1=22=1

x1	0	1
x2	-1	0

2. To draw constraint -2x1+x2≤1→(2)

Treat it as -2x1+x2=1

When x1=0 then x2=?

⇒-2(0)+x2=1

⇒x2=1

When x2=0 then x1=?

⇒-2x1+(0)=1

⇒-2x1=1

⇒x1=1-2=-0.5

x1	0	-0.5
x2	1	0

The value of the objective function at each of these extreme points is as follows:

Extreme Point Coordinates (x1,x2)	Lines through Extreme Point	Objective function value Z=2x1+3x2
O(0,0)	3→x1≥0 4→x2≥0	2(0)+3(0)=0
A(1,0)	1→2x1-2x2≤2 4→x2≥0	2(1)+3(0)=2
B(0,1)	2→-2x1+x2≤1 3→x1≥0	2(0)+3(1)=3

Problem has an unbounded solution.

Note: In maximization problem, if shaded area is open-ended. This means that the maximization is not possible and the LPP has no finite solution. Hence the solution of the given problem is unbounded.