The packaging product mix problem is solved using simplex method.

Maximize Z = 6x_{1} + 4x_{2}

Subject to constraints,

2x_{1}+3x_{2} ≤ 120 (Cutting machine) .....................(i)

2x_{1}+ x_{2} ≤ 60 (Pinning machine) ......................(ii)

where x_{1}, x_{2} ≥ 0

Considering the constraint for cutting machine,

2x_{1}+ 3x_{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

2x_{1}+ 3x_{2} + s_{3} = 120

Similarly for pinning machine, the equation is

2x_{1}+ x_{2} + s_{4} = 60

The variables s_{3} and s_{4} 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 x_{1} and x_{2} are equated to zero,

i.e., x_{1} = 0 and x_{2} = 0, then

s_{3} = 120

s_{4} = 60

This is the basic solution of the system, and variables s_{3} and s_{4} are known as Basic Variables, S_{B} while x_{1} and x_{2} 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,

Z_{max} = 6x_{1} + 4x_{2} + 0s_{3} + 0s_{4}

Subject to constraints,

2x_{1} + 3x_{2} + s_{3} = 120 ....................(i)

2x_{1} + x_{2} + s_{4} = 60 ....................(ii)

where x_{1}, x_{2} ≥ 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 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, x_{1} replaces s_{4} 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 s_{4} /2. This row is called as Pivotal Equation Row P_{e}. 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 = S_{B} + (–K_{c} * P_{e})

The equations for the variables in the iteration number 1 of table 8 are,

For s_{3} Q = S_{B} + (– K_{c} * P_{e})

= s_{3} + (–2x P_{e})

= s_{3} – 2P_{e} …………………………(i)

For – Z, Q = S_{B} + (– K_{c} * P_{e})

= – Z + ((– 6) * P_{e})

= – Z + 6P_{e} …………………………(ii)

Using the equations (i) and (ii) the values of s_{3} and –Z for the values of Table 1 are found as shown in table below.

* s*_{3} and –Z Values Calculated

Using these equations, enter the values of basic variables S_{B} 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 x_{1} and x_{2} for the final iteration table gives the optimal values of the decision variables i.e., x_{1} = 15, x_{2} = 30. Substituting these values in the objectives function equation, we get

Z_{max} = 6x_{1} + 4x_{2}

= 6(15) + 4(30)

= 90 + 120

= Rs. 210.00

*Iteration Table*

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} = 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 x_{1}, x_{2},……..xi and calculate the objective function for maximization or minimization.

*Note:*

(i) If there are no x_{1}, x_{2} variables in the final iteration table, the values of x_{1} and x_{2} are zero.

(ii) Neglect the sign for objective function value in the final iteration table.