Question

Use two-phase simplex method to solve:

Max Z = 5x₁ + 3x₂

S.T.

2x₁ + x₂ ≤ 1

x₁ + 4x₂ ≥ 6

x₁, x₂ ≥ 0

Answer 1

We convert the given problem in standard form by introducing slack variable, surplus variable and artificial variable. Also assign the cost – 1 to artificial variable and the cost 0 to another variables.

We have

Phase-1

Max Z* = 0x₁ + 0x₂ + 0S₁ + 0S₂ – 1A₁

S.T. 2x₁ + x₂ + S₁ = 1

x₁ + 4x₂ – S₂ + A₁ = 6

x₁, x₂, S₁, S₂, A₁ ≥ 0

The initial basic feasible solution is given by

x₁ = x₂ = 0, S₁ = 1, A₁ = 6

Now prepare the initial simplex table

Here, all values of Z_j – C_j are not positive so choose the most negative value of Z_j – C_j, i.e., Z₂ – C₂ is the most negative value. It will enter in the basis and treated as key column. Find key row by taking min \(\left\{\frac{X_B}{x_2}\right\}\).

\(= \left\{\frac11,\frac 64\right\}\)

= 1

1 is key element. Make other elements of key column zero by applying matrix row transformation. We have the first simplex table.

Here all values of Z_j – C_j ≥ 0. Max Z* < 0 and an artificial variable A₁ appears in the basis at positive level. In this case L.P.P. does not possess any feasible solution.