Question

Find all basic feasible solutions for the following LP and identify the adjacent basic feasible solutions of each basic feasible solution.

max z= 3x1 +5x2 s.t.

x1 <4

2x2 < 12

3x1 +2x2 < 18

x1>0, x2>0

Answer 1

Problem is

Max Z = 3 x1 + 5 x2

subject to

x1 ≤ 4 2 x2 ≤ 12 3 x1 + 2 x2 ≤ 18

and x1,x2≥0;

The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate 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 = 3 x1 + 5 x2 + 0 S1 + 0 S2 + 0 S3 subject to x1 + S1 = 4 2 x2 + S2 = 12 3 x1 + 2 x2 + S3 = 18 and x1,x2,S1,S2,S3≥0

Iteration-1 Cj 3 5 0 0 0 B CB XB x1 x2 S1 S2 S3 MinRatio XBx2 S1 0 4 1 0 1 0 0 --- S2 0 12 0 (2) 0 1 0 122=6 → S3 0 18 3 2 0 0 1 182=9 Z=0 Zj 0 0 0 0 0 Zj-Cj -3 -5 ↑ 0 0 0

Iteration-2 Cj 3 5 0 0 0 B CB XB x1 x2 S1 S2 S3 MinRatio XBx1 S1 0 4 1 0 1 0 0 41=4 x2 5 6 0 1 0 0.5 0 --- S3 0 6 (3) 0 0 -1 1 63=2 → Z=30 Zj 0 5 0 2.5 0 Zj-Cj -3 ↑ 0 0 2.5 0

Iteration-3 Cj 3 5 0 0 0 B CB XB x1 x2 S1 S2 S3 MinRatio S1 0 2 0 0 1 0.3333 -0.3333 x2 5 6 0 1 0 0.5 0 x1 3 2 1 0 0 -0.3333 0.3333 Z=36 Zj 3 5 0 1.5 1 Zj-Cj 0 0 0 1.5 1

Since all Zj-Cj≥0

Hence, optimal solution is arrived with value of variables as :
x1=2,x2=6

Max Z=36