Linear Programming:VARIANTS OF THE SIMPLEX METHOD

Operations Research (MTH601)

142

Maximize

Z = x1 + 2x2 + 3x3

Subject to

x1 + 2x2 + 3x3 = 15

2x1 + x2 + 5x3 = 20

x1 + 2x2 + x3 + x4 = 10

x1, x2, x3, x4 > 0

Solve the problem by two-phase method.

Maximize

Z = x1 + x2

Subject to

3x1 + 2x2 < 20

2x1 + 3x2 < 20

x1 + 2x2 > 2

x1 , x2 > 0

VARIANTS OF THE SIMPLEX METHOD

In this section we present certain complications encountered in the application of the simplex method and

how they are resolved. These are called the variants of simplex method. We can illustrate the typical cases through

numerical examples. The following variants are being considered.

Minimization

Inequality in the wrong direction

Degeneracy

Unbounded solution

Multiple solutions

Non-existing feasible solution

Unrestricted variables

Minimization:

Sometimes we come across problems in which the objective function has to be minimized instead of

maximizing. This situation can be tackled easily in either of the two ways. One is to make the following minor

changes in the simplex method. The new entering basic variable should be the non-basic variable that would

decrease rather than increase the value of Z at the fastest rate when this variable is increased. Similarly the test for

the fastest rate when this variable is increased. Similarly the test for optimality should be whether Z can increased.

Similarly the test for optimality should be whether Z can be decreased rather than increased by increasing any non-

basic variable.

The second method is to change the problem into an equivalent problem involving maximization and

proceed with the steps of the regular simplex method. The change is effected by maximizing the negative of the

original objective function. Minimizing any function f (x1, x2, x3, ..., xn) subject to set of constraints is completely

equivalent to maximizing -f (x1, x2, ..., xn) subject to the same set of constraints. For example if we want to minimize

a function Z = 5x1 +7x2 - 8x3, it is equivalent to maximizing a function Z = -5x1 - 7x2 + 8x3.

Inequality in the wrong direction.

142

Table of Contents: