Additional variable used in solving LP

Please send your query

Your Name (required)

Your Email (required)

Phone

Your Query

Additional variable used in solving LP

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,
2x1+ 3x2
120
(Cutting machine)
2x1+ x2
60
(Pinning machine)
where,
x1, x2
0
Considering the constraint for cutting machine,
2×1+ 3×2 120
The inequality indicates that the left-hand 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 Non-Basic Variables. If all the variables are non-negative, 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: Co-efficients 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
Zj
0
– 6
– 4
0
0
If the objective of the given problem is a maximization one, enter the co-efficient 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
Kr
S4
60
2
1
0
1 30
Zj
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 S4/2. This row is called as Pivotal Equation Row Pe. The other co-efficients 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 + 6Pe
…(ii)
Using the equations (i) and (ii) the values of S3 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
Pe
x1
30
1
½
0
½
60
S4 / 2
Zj
100
0
– 1
0
3
Z + 6Pe
Using these equations, enter the values of basic variables SB and objective function Z. If all the values in the objective function are non-negative, 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 non-negative, 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
Kr
Zj
0
– 6
– 4
0
0
1
S3
60
0
2
1
–1
30
S3 – 2pe
Kr
x1
30
1
½
0
½
60
S4/2
Pe
Zj
100
0
– 1
0
3
Z + 6Pe
2
Pe
X2
30
0
1
½
–1/2
S3/2
x1
15
1
0
– 1/4
¾
S3 – Pe/2
Zj
210
0
0
½
5/2
Z + Pe
The solution is,
x1 = 15 corrugated boxes are to be produced and
x2 = 30 carton boxes are to be produced to yield a
Profit, Zmax = `  210.00
Summary of LPP Procedure
= ` 210.00