Simplex Method

Simplex Method - Maximization Case

Consider the general linear programming problem

Maximize z = c₁x₁ + c₂x₂ + c₃x₃ + .........+ c_nx_n

subject to

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + .........+ a_1nx_n £ b₁
a₂₁x₁ + a₂₂x₂ + a₂₃x₃ + .........+ a_2nx_n £ b₂
.........................................................................
a_m1x₁ + a_m2x₂ + a_m3x₃ + .........+ a_mnx_n £ b_m
x₁, x₂,....., x_n³ 0

Where:
c_j (j = 1, 2, ...., n) in the objective function are called the cost or profit coefficients.
b_i (i = 1, 2, ...., m) are called resources.
a_ij (i = 1, 2, ...., m; j = 1, 2, ...., n) are called technological coefficients or input-output coefficients.

Converting inequalities to equalities

Introducing slack variables to convert inequalities to equalities

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + .........+ a_1nx_n + s₁ = b₁
a₂₁x₁ + a₂₂x₂ + a₂₃x₃ + .........+ a_2nx_n + s₂ = b₂
..............................................................................
a_m1x₁ + a_m2x₂ + a_m3x₃ + .........+ a_mnx_n + s_m = b_m
x₁, x₂,....., x_n ³ 0
s₁, s₂,....., s_m ³ 0

An initial basic feasible solution is obtained by setting x₁ = x₂ =........ = x_n = 0
s₁ = b₁
s₂ = b₂
..............
s_m = b_m

The initial simplex table is formed by writing out the coefficients and constraints of a LPP in a systematic tabular form. The following table shows the structure of a simplex table.

Structure of a simplex table

Where:
c_j = coefficients of the variables (m + n) in the objective function.
c_B = coefficients of the current basic variables in the objective function.
B = basic variables in the basis.
X_B = solution values of the basic variables.
z_j-c_j = index row.

The rules used for the construction of the initial simplex table are same in both the maximization and the minimization problems.