Chapter 2 linear programming problems

2.2.2 Simplex method

The general steps of the simplex method are as follows.

1. Start with an initial extreme point of the feasible solution set.

2. Improve the initial solution if possible by finding another extreme point of
feasible solution set with a better objective function value. At this step the
simplex method implicitly eliminates from consideration all those extreme
points of the feasible solution set whose objective function values are worse
than the present one. This makes the procedure more efficient than the
enumeration method.

3. Continue to find better extreme point of feasible solution set, improving the
objective function value at every step.

19

4. When a particular extreme point of feasible solution set cannot be improved
further, it becomes an optimal solution and the simplex method terminates.

2.2.3 Simplex method in tableau form

The various steps of the simplex method can be carried out in a more compact

manner by using a tableau form to represent the constraints and the objective
function. In addition by developing some simple formulas, the various calculations
can be made mechanical [55]. In this section the simplex method is presented by
illustrating the steps and using a tableau form for an example in canonical form.
We consider the following linear programming problem.
maximize z = 6x₁ + 8x₂
subject to
5x₁ + 10x₂ ≤ 60,
4x₁ + 4x₂ ≤ 40,
x₁ , x₂ ≥ 0.

20

The standard form of the above LP problem is shown below.

maximize z = 6x₁ + 8x₂ + 0s₁ + 0s₂
subject to
5x₁ + 10x₂ + s₁ ≤ 60,
4x₁ + 4x₂ + s₂ ≤ 40,
x₁ , x₂ , s₁ , s₂ ≥ 0,
where s₁ and s₂ are slack variables, which are introduced to balance the constraints.

• Basic variable. A variable is said to be basic variable if it has unit coeffi-

cient in one of the constraints and zero coefficient in the remaining constraints
[53].

If all the constraints are “≤”, then the standard form is to be treated as the

canonical form. The canonical form is generally used to prepare the initial simplex
tableau [53]. The initial simplex table of the above problem is shown in Table 2.1.