SKEDSOFT

Introduction:

There are many methods to solve the Linear Programming Problem, such as dual simplex method, Trial and Error method, Vector method and Simplex Method. Though we use graphical method for solution when we have two problem variables, the other method can be used when there are more than two decision variables in the problem.

Dual simplex method:

where the primal solution may be infeasible, but corresponding variables indicate that dual is feasible. Thus, solution of primal is infeasible but optimum. In a dual simplex method initial solution is infeasible but optimum, and through iteration it reaches feasibility at which stages it also reaches true optimum.

Example:  Minimize Z = 2a 1b s.t.

3a 1b ≥ 3

4a 3b ≥ 6

1a 2b ≤ 3 and both a and b are ≥ 0.

Solution:

The problem can be written as:

Maximize Z = –2a – 1b s.t.

–3a – 1b ≤ –3

–4a – 3b ≤ –6

1a 2b ≤ 3 and both a and b are ≥ 0.

The linear programming version is:

Maximize Z = –2a – 1b 0S₁ 0S₂ 0S₃ s.t

–3a – 1b 1S₁ 0S₂ 0S₃ = –3

–4a – 3b 0S₁ 1S₂ 0S₃ = –6

1a 2b 0S₁ 0S₂ 1S₃ = 3

And a, b, S₁, S₂, and S₃ all ≥ 0.

Now observe here, both S₁ = –3 and S₂ = –6 are negative and S₃ = 3 positive. This shows that the basic variables of primal (S₁ and S₃) are infeasible. Moreover the net evaluation row elements are negative or zeros, the solution is optimal. Now let us change the solution towards feasibility without disturbing optimality. That is deciding the incoming variable and outgoing variable.