Home | | **Operations Research An Introduction** | | **Resource Management Techniques** | Additional Simplex Algorithms: Dual Simplex Method and Generalized Simplex Algorithm

In the simplex algorithm presented in Chapter 3 the problem starts at a (basic) feasible solution. Successive iterations continue to be feasible until the optimal is reached at the last iteration. The algorithm is sometimes referred to as the primal simplex method.

**ADDITIONAL SIMPLEX ALGORITHMS**

In the
simplex algorithm presented in Chapter 3 the problem starts at a (basic)
feasible solution. Successive iterations continue to be feasible until the
optimal is reached at the last iteration. The algorithm is sometimes referred
to as the primal simplex method.

This
section presents two additional algorithms: The dual simplex and the
generalized simplex. In the dual simplex, the LP starts at a better than
optimal *infeasible* (basic) solution.
Successive iterations remain infeasible and (better than) optimal until
feasibility is restored at the last iteration. The generalized simplex combines
both the primal and dual simplex methods in one algorithm. It deals with problems that start
both nonoptimal and infeasible. In this algorithm, successive iterations are
associated with basic feasible or infeasible (basic) solutions. At the final
iteration, the solution be-comes optimal and feasible (assuming that one
exists).

All three
algorithms, the primal, the dual, and the generalized, are used in the course
of post-optimal analysis calculations, as will be shown in Section 4.5.

**1. Dual Simplex Algorithm**

The crux
of the dual simplex method is to start with a better than optimal and
infeasible basic solution. The optimality and feasibility conditions are
designed to preserve the op-timality of the basic solutions while moving the
solution iterations toward feasibility.

*Dual
feasibility condition.** *The
leaving variable,* *x* *_{n}* *is the
basic variable having the* *most
negative value (ties are broken arbitrarily). If all the basic variables are nonnegative, the algorithm ends.

*Dual
optimality condition.** *Given
that* x _{r} *is the leaving
variable, let

(Ties are
broken arbitrarily.) If a_{rj} ≥ 0 for
all nonbasic *x _{j},* the problem has no feasible
solution.

To start
the LP optimal and infeasible, two requirements must be met:

1.
The objective function must satisfy the optimality
condition of the regular simplex method (Chapter 3).

2.
All the constraints must be of the type (≤).

The
second condition requires converting any (≥) to (≤)
simply by multiplying both sides of the inequality (≥) by -1. If the LP includes (=) constraints, the equation can be
replaced by two inequalities. For example,

After
converting all the constraints to (≤), the starting solution is infeasible if
at least one of the right-hand sides of the inequalities is strictly negative.

**Example
4.4-1**

In the
present example, the first two inequalities are multiplied by -1 to convert
them to (≤) constraints. The starting tableau is thus given as:

According
to the dual feasibility condition, x_{5} (= -6) is the leaving
variable. The next table shows how the dual optimality condition is used to
determine the entering variable.

The
ratios show that x_{2} is the entering variable. Notice that a nonbasic
variable x_{j} is a candidate for entering the basic solution only if
its a_{rj} is
strictly negative. This is the reason x_{1} is excluded in the table
above.

The next
tableau is obtained by using the familiar row operations, which give

The
preceding tableau shows that *x _{4}* leaves and

Notice
how the dual simplex works. In all the iterations, optimality is maintained
(all reduced costs are ≤0).At the
same time, each new iteration moves the solution toward feasibility. At
iteration 3, feasibility is restored for the first time and the process ends
with the optimal feasible solution as

**TORA
Moment.**

TQRA provides
a tutorial module for the dual simplex method. From the SOLVE/MODIY Menu
slect - > Algebraic -> Iterations - > Dual Simplex Remember that you
need to convert (=) constraints to inequalities. You do not need to convert (2:) constraints because TORA will
do the conversion internally. If the LP
does not satisfy the initial requirements of the dual simplex, a message will
appear on the screen.

As in the
regular simplex method, the tutorial module allows you to select the entering
and the leaving variables beforehand. An appropriate feedback then tells you if
your selection is correct.

**PROBLEM SET **4.4A

1. Consider
the solution space in Figure
4.3, where it is desired to find the optimum extreme point that uses the *dual* simplex method to minimize *z* = 2x_{1} + *x _{2.}* The optimal solution occurs at
point

(a) Can the dual simplex start at point A?

*(b) If the starting basic (infeasible
but better than optimum) solution is given by point G, would it be possible for
the iterations of the dual simplex method to follow the path G -> *E* -> *F?* Explain.

(c) If the starting basic (infeasible)
solution starts at point *L,* identify a possible path of the dual simplex method that
leads to the optimum feasible point at point *F.*

2. Generate
the dual simplex iterations for the following problems (usingTORA for
conve-nience), and trace the path of the algorithm on the graphical solution space.

Minimize *z* = 2x_{1} + *3x _{2}*

*3.* *Dual Simplex with Artificial Constraints. *Consider
the following problem:

The
starting basic solution consisting of surplus variables *x _{4}* and x

4. Using
the artificial constraint procedure introduced in Problem 3, solve the
following problems by the dual simplex method. In each case, indicate whether
the resulting solution is feasible, infeasible, or unbounded.

5. Solve
the following LP in three different ways (useTORA for convenience). Which
method appears to be the most efficient computationally?

**2. Generalized Simplex Algorithm**

The
(primal) simplex algorithm in Chapter 3 starts feasible but nonoptimal. The
dual simplex in Section 4.4.1 starts (better than) optimal but infeasible. What
if an LP model starts both nonoptimal and infeasible? We have seen that the primal
simplex accounts for the infeasibility of the starting solution by using
artificial variables. Similarly, the dual simplex accounts for the
nonoptimality by using an artificial constraint (see Problem 3, Set
4.4a).Although these procedures are designed to enhance *automatic* computations, such details may cause one to lose sight of
what the simplex algorithm truly entails-namely, the optimum solution of an LP
is associated with a comer point (or basic) solution. Based on this
observation, you should be able to "tailor" your own sim-plex
algorithm for LP models that start both nonoptimal and infeasible. The
following example illustrates what we call the generalized simplex algorithm.

**Example 4.4-2**

Consider
the LP model of Problem 4(a), Set 4.4a. The model can be put in the
following tableau form in which the starting basic solution (x_{3}, x_{4},
x_{5}) is both nonoptimal (because x_{3} has a negative reduced
cost) and infeasible (because x_{4}
= -8). (The first equation has
been multiplied by -1 to reveal the infeasibility directly in the Solution
column.)

We can
solve the problem without the use of any artificial variables or artificial
constraints as follows: Remove infeasibility first by applying a version of the
dual simplex feasibility condi-tion that selects *x _{4}* as the leaving variable. To
determine the entering variable, all we need is a nonbasic variable whose
constraint coefficient in the x

The
solution in the preceding tableau is now feasible but nonoptimal, and we can
use the primal simplex to determine the optimal solution. In general, had we
not restored feasibility in the preceding tableau, we would repeat the
procedure as necessary until feasibility is satisfied or there is evidence that
the problem has no feasible solution (which happens if a basic variable is
negative and all its constraint coefficients are nonnegative). Once feasibility
is established, the next step is to pay attention to optimality by applying the
proper optimality condition of the pri-mal simplex method.

**Remarks.** The essence of Example 4.4-2 is
that the simplex method is not rigid. The literature abounds with variations of
the simplex method (e.g., the primal-dual method, the symmetrical method, the
criss-cross method, and the multiplex method) that give the impression that
each procedure is different, when, in effect, they all seek a corner point
solution, with a slant toward automated computations and, perhaps,
computational efficiency.

**PROBLEM
SET 4.4B**

1. The LP
model of Problem 4(c), Set 4.4a, has no feasible solution. Show how this
condi-tion is detected by the *generalized
simplex procedure.*

2. The LP
model of Problem 4(d), Set 4.4a, has no bounded solution. Show how this condi-tion
is detected by the *generalized sirnplex
procedure.*

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.