Simplex Method Introduction

In the previous chapter, we discussed about the graphical method for solving linear programming problems (LPP). Although the graphical method is an invaluable aid to understand the properties of linear programming models, it provides very little help in handling practical problems.

In this chapter, we concentrate on the simplex method for solving linear programming problems with a larger number of variables.

Many different methods have been proposed to solve linear programming problems, but simplex method has proved to be the most effective. This technique will nurture your insight needed for a sound understanding of several approaches to other programming models, which will be studied in subsequent chapters. Simplex Method is applicable to any problem that can be formulated in terms of linear objective function, subject to a set of linear constraints. Often, this method is termed Dantzig's simplex method, in honour of the mathematician who devised the approach.

In the following section, we introduce you to the standard vocabulary of the simplex method.

Basic Terminology - Simplex Method Linear Programming (LP)

Slack variable

Specifically:
a_i1x₁ + a_i2x₂ + a_i3x₃ + .........+ a_inx_n ≤ b_i can be written as
a_i1x₁ + a_i2x₂ + a_i3x₃ + .........+ a_inx_n + s_i = b_i

Where i = 1, 2, ..., m

Surplus variable

Specifically:
a_i1x₁ + a_i2x₂ + a_i3x₃ + .........+ a_inx_n ≥ b_i can be written as
a_i1x₁ + a_i2x₂ + a_i3x₃ + .........+ a_inx_n - s_i = b_i

Where i = 1, 2, ..., m

Artificial variable