In practice, most problems contain more than two variables and are consequently too large to be tackled by conventional means. Therefore, an algebraic technique is used to solve large problems using Simplex Method. This method is carried out through iterative process systematically step by step, and finally the maximum or minimum values of the objective function are attained.The basic concepts of simplex method are explained using the Example 6 of the packaging product mix problem illustrated in the previous chapter. The simplex method solves the linear programming problem in iterations to improve the value of the objective function. The simplex approach not only yields the optimal solution but also other valuable information to perform economic and ‘what if’ analysis.
Additional Variables Used in Solving LPP
Three types of additional variables are used in simplex method such as:
(a) Slack variables (S1, S2, S3..…Sn): Slack variables refer to the amount of unused resources like raw materials, labour and money.
(b) Surplus variables (S1, S2, S3..…Sn): Surplus variable is the amount of resources by which the left hand side of the equation exceeds the minimum limit.
(c) Artificial Variables (a1, a2, a3.. …an): Artificial variables are temporary slack variables which are used for purposes of calculation, and are removed later.
The above variables are used to convert the inequalities into equality equations, as given in the Table 3.1 below.
Table 3.1: Types of Additional Variables


Constraint Type 

Variable Added 
Format 









(a)

Less than or equal to

<

Add Slack Variable

+S










(b)

Greater than or equal to

>

Subtract surplus variable and add artificial variable

–S + a










(c)

Equal to

=

Add artificial variable

+a
















Maximization Case
The packaging product mix problem (Example 6 of previous chapter) is solved using simplex method.
Maximize Z = 6×1 + 4×2
Subject to constraints,

2x_{1}+ 3x_{2}

120

(Cutting machine)


2x_{1}+ x_{2}

60

(Pinning machine)

where,

x_{1}, x_{2}

0


Considering the constraint for cutting machine,
2×1+ 3×2 120
The inequality indicates that the lefthand side of the constraints equation has some amount of unused resources on cutting machine. To convert this inequality constraint into an equation, introduce a slack variable, S 3 which represents the unused resources. Introducing the slack variable, we have the equation
2×1+ 3×2 + S3 = 120
Similarly for pinning machine, the equation is
2×1+ x2 + S4 = 60
The variables S3 and S4 are known as slack variables corresponding to the three constraints. Now we have in all four variables (which includes slack variable) and two equations. If any two variables are equated to zero, we can solve the three equations of the system in two unknowns.
If variables x1 and x2 are equated to zero,
i.e., x1 = 0 and x2 = 0, then
S3 = 120
S4 = 60
This is the basic solution of the system, and variables S3 and S4 are known as Basic Variables, SB while x1 and x2 known as NonBasic Variables. If all the variables are nonnegative, a basic feasible solution of a linear programming problem is called a Basic Feasible Solution.
Rewriting the constraints with slack variables gives us,
Zmax = 6×1 + 4×2 + 0S3 + 0S4
Subject to constraints,
2×1 + 3×2 + S3 = 120
2×1 + x2 + S4 = 60
where, x1, x2 0
Though there are many forms of presenting Simplex Table for calculation, we represent the coefficients of variables in a tabular form as shown in Table 3.2.
Table 3.2: Coefficients of Variables

Iteration

Basic

Solution

X1

X2

S3

S4

Minimum

Equation



Number

Variables

Value

KC




Ratio















0

S3

120

2

3

1

0

60





S4

60

2

1

0

1

30





– Z_{j}

0

– 6

– 4

0

0


























If the objective of the given problem is a maximization one, enter the coefficient of the objective function Zj with opposite sign as shown in Table 3.3. Take the most negative coefficient of the objective function and that is the key column K c. In this case, it is 6. Find the ratio between the solution value and the key column coefficient and enter it in the minimum ratio column. The intersecting coefficients of the key column and key row are called the pivotal element i.e. 2. The variable corresponding to the key column is the entering element of the next iteration table and the corresponding variable of the key row is the leaving element of the next iteration table. In other words, x1 replaces S4 in the next iteration table. Table 3.3 indicates the key column, key row and the pivotal element.
Table 3.3

Iteration

Basic

Solution

X1

X2

S3

S4

Minimum

Equation



Number

Variables

Value

KC




Ratio















0

S3

120

2

3

1

0

60















K_{r}

S4

60

2

1

0

1 
30 















–Z_{j}

0

6

4

0

0


























In the next iteration, enter the basic variables by eliminating the leaving variable (i.e., key row) and introducing the entering variable (i.e., key column). Make the pivotal element as 1 and enter the values of other elements in that row accordingly. In this case, convert the pivotal element value 2 as 1 in the next iteration table. For this, divide the pivotal element by 2. Similarly divide the other elements in that row by 2. The equation is S_{4}/2. This row is called as Pivotal Equation Row P_{e}. The other coefficients of the key column in iteration Table 3.4 must be made as zero in the iteration Table 3.5. For this, a solver, Q, is formed for easy calculation. Change the sign of the key column coefficient, multiply with pivotal equation element and add with the corresponding variable to get the equation,
Solver, Q = SB + (–Kc Pe)
The equations for the variables in the iteration number 1 of Table 3.4 are,
For S3 Q = SB + (– Kc × Pe)
= S3 + (–2 × Pe)
= S3 – 2Pe …(i)
For – Z, Q = SB + (– Kc Pe)
= – Z + ((– 6) Pe)



= – Z + 6P_{e}







…(ii)

Using the equations (i) and (ii) the values of S_{3} and –Z for the values of Iteration 1 are found as shown in Table 3.4







Table 3.4: Iteration 1






















Iteration

Basic


Solution

X1

X2

S3

S4

Minimum

Equation





Number

Variables


Value

KC

KC



Ratio



















0


S3


120

2

3

1

0

60




















Kr

S4


60

2

1

0

1

30





















– Zj


0

– 6

– 4

0

0




















1

Kr

S3


60

0

2

1

– 1

30

S3 – 2Pe



















P_{e}

x1


30

1

½

0

½

60

S4 / 2




















– Zj


100

0

– 1

0

3


– Z + 6P_{e}































Using these equations, enter the values of basic variables SB and objective function Z. If all the values in the objective function are nonnegative, the solution is optimal. Here, we have one negative value – 1. Repeat the steps to find the key row and pivotal equation values for the iteration 2 and check for optimality.In the iteration 2 number of Table 3.5, all the values of Zj are nonnegative, Zj 0, hence optimality is reached. The corresponding values of x1 and x2 for the final iteration table gives the optimal values of the decision variables i.e., x1 = 15, x2 = 30. Substituting these values in the objectives function equation, we get
Zmax = 6×1 + 4×2
= 6(15) + 4(30)
Table 3.5: Iteration 2


Iteration

Basic

Solution

X1

X2

S3

S4

Minimum

Equation




Number

Variables

Value





Ratio
















0


S3

120

2

3

1

0

60






S4

60

2

1

0

1

30





K_{r}

– Z_{j}

0

– 6

– 4

0

0

















1


S3

60

0

2

1

–1

30

S3 – 2p_{e}




Kr

x1

30

1

½

0

½

60

S4/2




P_{e}

– Z_{j}

100

0

– 1

0

3


– Z + 6P_{e}















2

P_{e}

X2

30

0

1

½

–1/2


S3/2





x1

15

1

0

– 1/4

¾


S3 – Pe/2





– Zj

210

0

0

½

5/2


– Z + P_{e}


























The solution is,
x_{1} = 15 corrugated boxes are to be produced and
x_{2} = 30 carton boxes are to be produced to yield a
Profit, Z_{max} = ` 210.00
Summary of LPP Procedure
= ` 210.00