Question

Consider the following linear program:  
maximize z = x1 + 4x2 subject to: x1 + 2x2 <= 13 x1 - x2 <= 8 - x1 + x2 <= 2
-3 <= x1 <= 8 -5 <= x2 <= 4

Starting with x1 and x2 nonbasic at their lower bounds, perform ONE iteration of the Bounded Variables Revised Simplex Method. (Tableau or matrix form is acceptable). Show your work. Clearly identify the entering and leaving variables. After the pivot, identify the resulting basic feasible solution (if one exists).

Answer 1

MAX Z = x1 + 4x2

subject to

x1 + 2x2 <= 13

x1 - x2 <= 8

-x1 + x2 <= 2

-3<= x1 <= 8

-5<= x2 <= 4

Solution:

Problem is

Max Z =x1 +4x2

subject to

x1+2x2?13

x1-x2? 8

-x1+x2 ?2

and x1,x2?0;

The problem is converted to canonical form by adding slack, surplus and artificial variables as appropriate

1. As the constraint 1 is of type '?' we should add slack variable S1

2. As the constraint 2 is of type '?' we should add slack variable S2

3. As the constraint 3 is of type '?' we should add slack variable S3

After introducing slack variables

Max Z = x1+4 x2+0S1+0S2+ 0S3

subject to

x1+2x2+S1 = 13

x1-x2 +S2 = 8

-x1+x2 +S3 = 2

and x1,x2,S1,S2,S3?0

Iteration-1 Cj 14 0 0 0   

B CB XB x1 x2 S1 S2 S3 MinRatio xb/x2

S1 0 13 1 2 1 0 0 13/2=6.5

S2 0 8 1 -1 0 1 0 ---

S3 0 2 -1 (1) 0 0 1 2/1=2?

Z=0 Z=0 0=

Zj=?CBXB Zj Zj=?CBxj 0 0=0×1+0×1+0×(-1)

Zj=?CBx1 0 0=0×2+0×(-1)+0×1

Zj=?CBx2 0 0=0×1+0×0+0×0

Zj=?CBS1 0 0=0×0+0×1+0×0

Zj=?CBS2 0

Positive maximum Cj-Zj is 4 and its column index is 2. So, the entering variable is x2.

Minimum ratio is 2 and its row index is 3. So, the leaving basis variable is S3.

? The pivot element is 1.

Entering =x2, Departing =S3, Key Element =1

R3(new)=R3(old)

R1(new)=R1(old)-2R3(new)

R2(new)=R2(old)+R3(new)

Iteration-2 Cj 1 4 0 0 0   

B CB XB x1 Entering variable x2 S1 S2 S3 MinRatio

XB

x1

S1 Leaving variable 0 9 9=13-2×2

R1(new)=R1(old)-2R3(new) (3) 3=1-2×(-1) (pivot element)

R1(new)=R1(old)-2R3(new) 0 0=2-2×1

R1(new)=R1(old)-2R3(new) 1 1=1-2×0

R1(new)=R1(old)-2R3(new) 0 0=0-2×0

R1(new)=R1(old)-2R3(new) -2 -2=0-2×1

R1(new)=R1(old)-2R3(new)   

9

3

=3?

S2 0 10 10=8+2

R2(new)=R2(old)+R3(new) 0 0=1+(-1)

R2(new)=R2(old)+R3(new) 0 0=(-1)+1

R2(new)=R2(old)+R3(new) 0 0=0+0

R2(new)=R2(old)+R3(new) 1 1=1+0

R2(new)=R2(old)+R3(new) 1 1=0+1

R2(new)=R2(old)+R3(new) ---

x2 4 2 2=2

R3(new)=R3(old) -1 -1=-1

R3(new)=R3(old) 1 1=1

R3(new)=R3(old) 0 0=0

R3(new)=R3(old) 0 0=0

R3(new)=R3(old) 1 1=1

R3(new)=R3(old) ---

Z=8 8=4×2

Zj=?CBXB Zj Zj=?CBxj -4 -4=0×3+0×0+4×(-1)

Zj=?CBx1 4 4=0×0+0×0+4×1

Zj=?CBx2 0 0=0×1+0×0+4×0

Zj=?CBS1 0 0=0×0+0×1+4×0

Zj=?CBS2 4 4=0×(-2)+0×1+4×1

Zj=?CBS3   

Cj-Zj 5 5=1-(-4)? 0 0=4-4 0 0=0-0 0 0=0-0 -4 -4=0-4   

Positive maximum Cj-Zj is 5 and its column index is 1. So, the entering variable is x1.

Minimum ratio is 3 and its row index is 1. So, the leaving basis variable is S1.

? The pivot element is 3.

Entering =x1, Departing =S1, Key Element =3

R1(new)=R1(old)÷3

R2(new)=R2(old)

R3(new)=R3(old)+R1(new

Iteration-3 Cj 1 4 0 0 0   

B CB XB x1 x2 S1 S2 S3 MinRatio

x1 1 3 3=9÷3

R1(new)=R1(old)÷3 1 1=3÷3

R1(new)=R1(old)÷3 0 0=0÷3

R1(new)=R1(old)÷3

1

3

1

3

=1÷3

R1(new)=R1(old)÷3 0 0=0÷3

R1(new)=R1(old)÷3 -

2

3

-

2

3

=(-2)÷3

R1(new)=R1(old)÷3   

S2 0 10 10=10

R2(new)=R2(old) 0 0=0

R2(new)=R2(old) 0 0=0

R2(new)=R2(old) 0 0=0

R2(new)=R2(old) 1 1=1

R2(new)=R2(old) 1 1=1

R2(new)=R2(old)   

x2 4 5 5=2+3

R3(new)=R3(old)+R1(new) 0 0=(-1)+1

R3(new)=R3(old)+R1(new) 1 1=1+0

R3(new)=R3(old)+R1(new)

1

3

1

3

=0+

1

3

R3(new)=R3(old)+R1(new) 0 0=0+0

R3(new)=R3(old)+R1(new)

1

3

1

3

=1+(-

2

3

)

R3(new)=R3(old)+R1(new)   

Z=23 23=1×3+4×5

Zj=?CBXB Zj Zj=?CBxj 1 1=1×1+0×0+4×0

Zj=?CBx1 4 4=1×0+0×0+4×1

Zj=?CBx2

5

3

5

3

=1×

1

3

+0×0+4×

1

3

Zj=?CBS1 0 0=1×0+0×1+4×0

Zj=?CBS2

2

3

2

3

=1×(-

2

3

)+0×1+4×

1

3

Zj=?CBS3   

Cj-Zj 0 0=1-1 0 0=4-4 -

5

3

-

5

3

=0-

5

3

0 0=0-0 -

2

3

-

2

3

=0-

2

3

Since all Cj-Zj?0

Hence, optimal solution is arrived with value of variables as :

x1=3,x2=5

Max Z=23