# Simplex Method - Maximization Case

### Consider the general linear programming problem (lpp)

Maximize z = c1x1 + c2x2 + c3x3 + .........+ cnxn

subject to

a11x1 + a12x2 + a13x3 + .........+ a1nxn ≤ b1
a21x1 + a22x2 + a23x3 + .........+ a2nxn ≤ b2
.........................................................................
am1x1 + am2x2 + am3x3 + .........+ amnxn ≤ bm
x1, x2,....., xn≥ 0

Where:
cj (j = 1, 2, ...., n) in the objective function are called the cost or profit coefficients.
bi (i = 1, 2, ...., m) are called resources.
aij (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

a11x1 + a12x2 + a13x3 + .........+ a1nxn + s1 = b1
a21x1 + a22x2 + a23x3 + .........+ a2nxn + s2 = b2
..............................................................................
am1x1 + am2x2 + am3x3 + .........+ amnxn + sm = bm
x1, x2,....., xn≥ 0
s1, s2,....., sm ≥ 0

An initial basic feasible solution is obtained by setting x1 = x2 =........ = xn = 0
s1 = b1
s2 = b2
..............
sm = bm

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

Use Horizontal Scrollbar to View Full Table

cj c1 c2 c3 --- cn
cB Basic variables
B
x1 x2 x3 --- xn Solution values
b (=XB)
cB1 x1 a11 a12 a13 --- a1n b1
cB2 x2 a21 a22 a23 --- a2n b2
cB3 x3 a31 a32 a33 --- a3n b3
--- ----- ---- ---- ----- --- ---- -----
cBm xn am1 am2 am3 --- amn bm
zj-cj    z1-c1 z2-c2 z3-c3 --- zn-cn

Where:
cj = coefficients of the variables (m + n) in the objective function.
cB = coefficients of the current basic variables in the objective function.

B = basic variables in the basis.
XB = solution values of the basic variables.
zj-cj = index row.

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

Share and Recommend