Home | | **Operations Research An Introduction** | | **Resource Management Techniques** | Special Cases in the Simplex Method

This section considers four special cases that arise in the use of the simplex method.
1. Degeneracy
2. Alternative optima
3. Unbounded solutions
4. Nonexisting (or infeasible) solutions

**SPECIAL CASES IN THE SIMPLEX METHOD**

This
section considers four special cases that arise in the use of the simplex
method.

1. Degeneracy

2. Alternative
optima

3. Unbounded
solutions

4. Nonexisting
(or infeasible) solutions

Our
interest in studying these special cases is twofold: (1) to present a *theoretical* explanation of these
situations and (2) to provide a *practical*
interpretation of what these special results could mean in a real-life problem.

**1. Degeneracy**

In the
application of the feasibility condition of the simplex method, a tie for the
mini-mum ratio may occur and can be broken arbitrarily. When this happens, at
least one *basic* variable will be zero
in the next iteration and the new solution is said to be degenerate.

There is
nothing alarming about a degenerate solution, with the exception of a small
theoretical inconvenience, called cycling or circling, which we shall discuss
short-ly. From the practical standpoint, the condition reveals that the model
has at least one *redundant *constraint.
To provide more insight into the practical and theoretical im-pacts of
degeneracy, a numeric example is used.

**Example
3.5-1**** ****(Degenerate
Optimal Solution)**

Given the
slack variables *x _{3}* and

In
iteration 0, *x _{3}* and

What is
the practical implication of degeneracy? Look at the graphical solution in
Figure 3.7. Three lines pass through the optimum point *(x _{1}* = 0,

From the
theoretical standpoint, degeneracy has two implications. The first is the
phe-nomenon of cycling or circling. Looking at simplex iterations 1 and 2, you
will notice that the objective value does not improve *(z* = 18). It is thus possible for the simplex
method to enter a repetitive sequence of iterations, never improving the
objective value and never satisfying the optimality condition (see Problem 4,
Set 3.5a). Although there are methods for eliminat-ing cycling, these methods
lead to drastic slowdown in computations. For this reason, most LP codes do not
include provisions for cycling, relying on the fact that it is a rare
occurrence in practice.

The
second theoretical point arises in the examination of iterations 1 and 2. Both
iterations, though differing in the basic-nonbasic categorization of the
variables, yield identical values for all the variables and objective
value-namely,

x_{1}=0,
x_{2}= 2, x_{3}= 0, x_{4}=0, z=18

Is it
possible then to stop the computations at iteration 1 (when degeneracy first appears),
even though it is not optimum? The answer is no, because the solution may be *temporarily* de-generate as Problem 2,
Set 3.5a demonstrates.

**PROBLEM SET ****3.5A**

*1.
Consider the graphical solution space in Figure 3.8. Suppose that the simplex
iterations start at *A* and that the optimum solution
occurs at *D.* Further, assume that the objective function is defined such that at *A,* x_{I}
enters the solution first.

a. Identify
(on the graph) the corner points that define the simplex method path to the
optimum point.

b. Determine
the maximum possible number of simplex iterations needed to reach the optimum
solution, assuming no cycling.

2. Consider
the following LP:

a. Show
that the associated simplex iterations are temporarily degenerate (you may use
TORA for convenience).

b. Verify
the result by solving the problem graphically (TORA's Graphic module can be
used here).

*3. TORA **experiment.** *Consider the LP in Problem* *2.

a. Use
TORA to generate the simplex iterations. How many iterations are needed to
reach the optimum?

b. Interchange
constraints (1) and (3)
and re-solve the problem with TORA. How many iterations are needed to solve the
problem?

c. Explain
why the numbers of iterations in (a) and (b) are different.

*4. TORA Experiment *Consider
the following LP (authored by E.M. Beale to demonstrate* *cycling):

From
TORA's SOLVEIMODIFY menu, select Solve => Algebraic. => Iterations => All-slack. Next, "thumb" through
the successive simplex iterations using the command Next iteration (do not use All iterations,
because the simplex method will then cycle in-definitely). You will notice that
the starting all-slack basic feasible solution at iteration 0 will reappear
identically in iteration 6. This example illustrates the occurrence of cycling
in the simplex iterations and the possibility that the algorithm may never
converge to the optimum solution.

It is interesting that cycling will
not occur in this example if all the coefficients in this LP are converted to integer
values by using proper multiples (try it!).

**2. Alternative Optima**

When the
objective function is parallel to a nonredundant **binding constraint** (i.e., a constraint that is satisfied as an
equation at the optimal solution), the objective function can assume the same
optimal value at more than one solution point, thus giving rise to alternative
optima. The next example shows that there is an *infinite* number of such solutions. It also demonstrates the practical significance of encoun-tering such
solutions.

**Example **3.5-2 **(Infinite Number of Solutions)**

Figure
3.9 demonstrates how alternative optima can arise in the LP model when the
objec-tive function is parallel to a binding constraint. Any point on the *line segment* *Be* represents an alternative
optimum with the same objective value *z*
== 10.

The
iterations of the model are given by the following tableaus.

Iteration
1 gives the optimum solution *x _{1}* = 0,

The
simplex method determines only the two corner points Band C. Mathematically, we can determine
all the points *(x _{1}, x_{2})*
on the line segment

**Remarks. **In practice, alternative optima
are useful because we can choose from many solutions without experiencing
deterioration in the objective value. For instance, in the present ex-ample,
the solution at *B* shows that activity
2 only is at a positive level, whereas at C both activities are positive. If the example represents a
product-mix situation, there may be advan-tages in producing two products
rather than one to meet market competition. In this ease, the so-lution at C
may be more appealing.

**PROBLEM
SeT **3.5B

*1. For
the following LP, identify three alternative optimal basic solutions, and then
write a general expression for all the nonbasic alternative optima comprising
these three basic solutions.

*Note: *Although the problem has more
than three alternative basic solution optima,* *you are only required to identify three of them. You may use TORA
for convenience.

2. Solve
the following LP:

From the
optimal tableau, show that all the alternative optima are not corner points
(i.e., nonbasic). Give a two-dimensional graphical demonstration of the type of
solu-tion space and objective function that will produce this result. (You may
use TORA for convenience.)

3. For
the following LP, show that the optimal solution is degenerate and that none of
the alternative solutions are corner points (you may use TORA for convenience).

**3. Unbounded Solution**

In some
LP models, the values of the variables may be increased indefinitely without
violating any of the constraints-meaning that the solution space is *unbounded* in at least one variable. As a
result, the objective value may increase (maximization case) or decrease
(minimization case) indefinitely. In this case, both the solution space and the
optimum objective value are unbounded.

Unboundedness
points to the possibility that the model is poorly constructed. The most likely
irregularity in such models is that one or more nonredundant constraints have
not been accounted for, and the parameters (constants) of some constraints may
not have been estimated correctly.

The
following examples show how unboundedness, in both the solution space and the
objective value, can be recognized in the simplex tableau.

In the
starting tableau, both x_{l} and x_{2} have negative z-equation
coefficients. Hence either one can improve the solution. Because x_{l}
has the most negative coefficient, it is normally selected as the entering
variable. However, all the constraint coefficients under x_{2} (Le.,
the denominators of the ratios of the feasibility condition) are negative or
zero. This means that there is no leaving variable and that x_{2} can
be increased indefinitely without violating any of the constraints (compare
with the graphical interpretation of the minimum ratio in Figure 3.5). Because
each unit increase in x_{l} will increase z by 1, an infinite increase
in x_{2} leads to an infinite increase in z.

Thus, the
problem has no bounded solution. This result can be seen in Figure 3.10. The
solution space is unbounded in the direction of x_{2}, and the value of
z can be increased indefinitely. **Remarks.**
What would have happened if we had applied the strict optimality condition that
3.5 calls for x_{l} to enter the solution? The answer is that a
succeeding tableau would eventually have led to an entering variable with the
same characteristics as x_{2}. See Problem 1, Set3.5c.

**PROBLEM SET 3.5C**

1. TORA
Experiment. Solve Example 3.5-3 using TORA's Iterations option and show that
even though the solution starts with x_{l} as the entering variable
(per the optimality condition), the simplex algorithm will point eventually to
an unbounded solution.

*2.
Consider the LP:

a. By
inspecting the constraints, determine the direction *(x _{I}. x_{2},* or

b. Without
further computations, what can you conclude regarding the optimum objective
value?

3. In
some ill-constructed LP models, the solution space may be unbounded even though
the problem may have a bounded objective value. Such an occurrence can point
only to irregularities in the construction of the model. In large problems, it
may be difficult to detect unboundedness by inspection. Devise a procedure for
determining whether or not a solution space is unbounded.

**4. Infeasible Solution**

LP models
with inconsistent constraints have no feasible solution. This situation can never
occur if *all* the constraints are of
the type ≤ with
nonnegative right-hand sides because the slacks provide a feasible solution.
For other types of constraints, we use artificial variables. Although the
artificial variables are penalized in the objective function to force them to
zero at the optimum, this can occur only if the model has a feasible space.
Otherwise, at least one artificial variable will be *positive* in the optimum iteration. From the practical standpoint,
an infeasible space points to the possibility that the model is not formulated
correctly.

**Example 3.5-4 (Infeasible
Solution Space)**

Consider
the following LP:

Using the
penalty M = 100 for the artificial variable R, the following tableaux provide
the simplex iterations of the model.

Optimum
iteration 1 shows that the artificial variable *R* is *positive* (= 4),
which indicates that the problem is infeasible. Figure 3.11 demonstrates the
infeasible solution space. By allowing

the
artificial variable to be positive, the simplex method, in essence, has
reversed the direction of the inequality from *3x _{1}* +

**PROBLEM
SET 3.50**

*1.
Tooleo produces three types of tools, T1, *T2,*
and T3. The tools use two raw materials, *M1*
and *M2,* according to the data in the following table:

The
available daily quantities of raw materials *M1*
and *M2* are 1000 units and 1200 units,
respectively. The marketing department informed the production manager that
according to their research, the daily demand for all three tools must be at
least 500 units. Will the manufacturing department be able to satisfy the
demand? If not, what is the most Toolco can
provide of the three tools?

*2. TO RA Experiment. *Consider
the LP model

Use
TORA's Iterations => M-Meth6d to show that the optimal
solution includes an artificial basic variable, but at zero level. Does the
problem have a *feasible* optimal
solution?

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2021 BrainKart.com; All Rights Reserved. (BS) Developed by Therithal info, Chennai.