# A-18

# Module A

# The Simplex Solution Method

An artificial variable allows for an initial basic feasible solution at the origin, but it has no real meaning.

To alleviate this difficulty and get a solution at the origin, we add an artificial variable (A_{1}) to the constraint equation,

2 x 1 + 4 x 2 - s 1 + A 1 = 1 6

The artificial variable, A_{1}, does not have a meaning, as a slack variable or a surplus variable does. It is inserted into the equation simply to give a positive solution at the origin; we are artificially creating a solution:

A 1 = 1 6 2 ( 0 ) + 4 ( 0 ) - 0 + A 1 = 1 6 2 x 1 + 4 x 2 - s 1 + A 1 = 1 6

The artificial variable is somewhat analogous to a booster rocket—its purpose is to get us off the ground; but once we get started, it has no real use and thus is discarded. The arti- ficial solution helps get the simplex process started, but we do not want it to end up in the optimal solution, because it has no real meaning.

When a surplus variable is subtracted and an artificial variable is added, the phosphate constraint becomes

4 x 1 + 3 x 2 - s 2 + A 2 = 2 4

The effect of surplus and artificial variables on the objective function must now be con- sidered. Like a slack variable, a surplus variable has no effect on the objective function in terms of increasing or decreasing cost. For example, a surplus of 24 pounds of nitrogen does not contribute to the cost of the objective function, because the cost is determined solely by the number of bags of fertilizer purchased (i.e., the values of x_{1 }and x_{2}). Thus, a coefficient of 0 is assigned to each surplus variable in the objective function.

By assigning a “cost” of $0 to each surplus variable, we are not prohibiting it from being in the final optimal solution. It would be quite realistic to have a final solution that showed some surplus nitrogen or phosphate. Likewise, assigning a cost of $0 to an artificial variable in the objective function would not prohibit it from being in the final optimal solution. However, if the artificial variable appeared in the solution, it would render the final solu- tion meaningless. Therefore, we must ensure that an artificial variable is not in the final solution.

Artificial variables are assigned a large cost in the objective function

to eliminate them from the final solution.

As previously noted, the presence of a particular variable in the final solution is based on its relative profit or cost. For example, if a bag of Super-gro costs $600 instead of $6 and Crop-quick stayed at $3, it is doubtful that the farmer would purchase Super-gro (i.e., x_{1 }would not be in the solution). Thus, we can prohibit a variable from being in the final solu- tion by assigning it a very large cost. Rather than assigning a dollar cost to an artificial vari- able, we will assign a value of M, which represents a large positive cost (say, $1,000,000). This operation produces the following objective function for our example:

m i n i m i z e Z = 6 x 1 + 3 x 2 + 0 s 1 + 0 s 2 + M A 1 + M A

2

The completely transformed minimization model can now be summarized as minimize Z = 6x_{1 }+ 3x_{2 }+ 0s_{1 }+ 0s_{2 }+ MA_{1 }+ MA_{2 }

subject to

x 1 , x 2 , s 1 , s 2 , A 1 , A 2 Ú 0 4 x 1 + 3 x 2 - s 2 + A 2 = 2 4 2 x 1 + 4 x 1 - s 1 + A 1 = 1 6