Answer to Question #242477 in Operations Research for opr

Question

Briefly explain artificial variables/slack variables technique in solving a linear programming

Answer 1

ARTIFICIAL VARIABLES TECHNIQUE

Introduction:

LPP in which constraints may also have >, and = signs after ensuring that all bi ≥ 0 are considered in this section. In such cases basis matrix cannot be obtained as an identify matrix in the stm1ing simplex table, therefore we introduce a new type of variable called the artificial variable. These variables are fictitious and cannot have any physical meaning. The artificial variable technique is a device to get the starting basic feasible solution, so that simplex procedure may be adopted as usual until the optimal solution is obtained. To solve such LPP there are two methods.

(i) The Big M Method or Method of Penalties.

(ii) The Two-phase Simplex Method.

The Big M Method:

The following steps are involved in solving an LPP using the Big M method.

Step 1: Express the problem in the standard form.

Step 2: Add non-negative artificial variables to the left side of each of the equations corresponding to constraints of the type >, or = However, addition of these artificial variable causes violation of the corresponding constraints. Therefore, we would like to get rid of these variables and would not allow them to appear in the final solution. This is achieved by assigning a very large penalty (-M for maximization and + M for minimization) in the objective function.

Step 3: Solve the modified LPP by simplex method, until anyone of the three cases may arise.

1. If no artificial variable appears in the basis and the optimality conditions are satisfied, then the current solution is an optimal basic feasible solution.

2. If at least one artificial variable in the basis at zero level and the optimality condition is satisfied then the current solution is an optimal basic feasible solution (though degenerated solution).

3. If at least one artificial variable appears on the basis at the positive level and the optimality condition is satisfied, then the original problem has no feasible solution. The solution satisfies the constraints but does not optimize the objective function, since it contains a very large penalty M and is called pseudo optimal solution.

Note: While applying the simplex method, whenever an artificial variable happens to leave the basis, we drop that artificial variable and omit all the entries corresponding to its column from the simplex table.

SLACK VARIABLE TECHNIQUE

In an optimization problem, a slack variable is a variable that is added to an inequality constraint to transform it into equality. Introducing a slack variable replaces an inequality constraint with an equality constraint and a non-negativity constraint on the slack variable.

Slack variables are used in particular in linear programming. As with the other variables in the augmented constraints, the slack variable cannot take on negative values, as the simplex algorithm requires them to be positive or zero.

• If a slack variable associated with a constraint is zero at a particular candidate solution, the constraint is binding there, as the constraint restricts the possible changes from that point.
• If a slack variable is positive at a particular candidate solution, the constraint is non-binding there, as the constraint does not restrict the possible changes from that point.
• If a slack variable is negative at some point, the point is infeasible (not allowed), as it does not satisfy the constraint.