Interview Questions

Linear Programming: Simplex Method

MAXIMIZATION CASE

The packaging product mix problem is solved using simplex method.

Maximize Z = 6x1 + 4x2

Subject to constraints,
2x1+3x2 ≤ 120 (Cutting machine)               .....................(i)
2x1+ x2 ≤ 60 (Pinning machine)                ......................(ii)
where x1, x2 ≥ 0

Considering the constraint for cutting machine,

2x1+ 3x2 ≥ 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, s3 which represents the unused resources.

Introducing the slack variable, we have the equation

2x1+ 3x2 + s3 = 120

Similarly for pinning machine, the equation is

2x1+ 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 = 6x1 + 4x2 + 0s3 + 0s4

Subject to constraints,
2x1 + 3x2 + s3 = 120             ....................(i)
2x1 + x2 + s4 = 60                 ....................(ii)
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.

 Co-efficients of Variables

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 the above table. Take the most negative coefficient of the objective function and that is the key column Kc.

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. The following table indicates the key column, key row and the pivotal element.

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 interaction 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 the following iteration table must be made as zero in the iteration Table. 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 8 are,

For s3 Q = SB + (– Kc * Pe)
= s3 + (–2x 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 Table 1 are found as shown in table below.

 s3 and –Z Values Calculated

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, 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 = 6x1 + 4x2

= 6(15) + 4(30)
= 90 + 120
= Rs. 210.00

Iteration Table

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 = Rs. 210.00

Summary of LPP Procedure

Step 1: Formulate the LP problem.

Step 2: Introduce slack /auxiliary variables.

if constraint type is ≤ introduce + S
if constraint type is ≥introduce – S + a and
if constraint type is = introduce a

Step 3: Find the initial basic solution.

Step 4: Establish a simplex table and enter all variable coefficients. If the objective function is maximization, enter the opposite sign co-efficient and if minimization, enter without changing the sign.

Step 5: Take the most negative coefficient in the objective function, Zj to identify the key column (the corresponding variable is the entering variable of the next iteration table).

Step 6: Find the ratio between the solution value and the coefficient of the key column. Enter the values in the minimum ratio column.

Step 7: Take the minimum positive value available in the minimum ratio column to identify the key row. (The corresponding variable is the leaving variable of the table).

Step 8: The intersection element of the key column and key row is the pivotal element.

Step 9: Construct the next iteration table by eliminating the leaving variable and introducing the entering variable.

Step 10: Convert the pivotal element as 1 in the next iteration table and compute the other elements in that row accordingly. This is the pivotal equation row (not key row).

Step 11: Other elements in the key column must be made zero. For simplicity, form the equations as follows: Change the sign of the key column element, multiply with pivotal equation element and add the corresponding variable.

Step 12: Check the values of objective function. If there are negative values, the solution is not an optimal one; go to step 5. Else, if all the values are positive, optimality is reached. Non-negativity for objective function value is not considered. Write down the values of x1, x2,……..xi and calculate the objective function for maximization or minimization.

Note:

(i) If there are no x1, x2 variables in the final iteration table, the values of x1 and x2 are zero.
(ii) Neglect the sign for objective function value in the final iteration table.


Pragna Meter
Next Chapter  
e-University Search
Related Jobs