We mentioned there that many important practical problems can be modeled as instances of linear programming. Two researchers, L. V. Kantorovich of the former Soviet Union and the Dutch-American T. C. Koopmans, were even awarded the Nobel Prize in 1975 for their contributions to linear programming theory and its applications to economics.

**The Simplex Method**

We have already encountered
linear programming (see Section 6.6)—the general problem of optimizing a linear
function of several variables subject to a set of linear constraints:

We mentioned there that many important practical problems can be modeled as instances of linear programming. Two researchers, L. V. Kantorovich of the former Soviet Union and the Dutch-American T. C. Koopmans, were even awarded the Nobel Prize in 1975 for their contributions to linear programming theory and its applications to economics. Apparently because there is no Nobel Prize in mathematics, the Royal Swedish Academy of Sciences failed to honor the U.S. mathematician G. B. Dantzig, who is universally recognized as the father of linear programming in its modern form and the inventor of the simplex method, the classic algorithm for solving such problems.

**Geometric
Interpretation of Linear Programming**

Before we introduce a general
method for solving linear programming problems, let us consider a small
example, which will help us to see the fundamental prop-erties of such
problems.

**EXAMPLE
1 **Consider the following linear programming problem in two
variables:

By definition, a ** feasible
solution** to this problem is any point

Are there feasible solutions
for which the value of the objective function equals, say, 20? The points ** (x, y)** for which the objective function

with the feasible region—see
Figure 10.2—the answer to the posed question is no. On the other hand, there
are infinitely many feasible points for which the objective function is equal
to, say, 10: they are the intersection points of the line 3** x** + 5

We can find this line either
by shifting, say, the line 3** x** + 5

Note that if we had to maximize
** z** = 3

Does every linear programming
problem have an optimal solution that can be found at a vertex of its feasible
region? Without appropriate qualifications, the answer to this question is no.
To begin with, the feasible region of a linear programming problem can be
empty. For example, if the constraints include two contradictory requirements,
such as ** x** +

Another complication may
arise if the problem’s feasible region is unbounded, as the following example
demonstrates.

**EXAMPLE
2 **If we reverse the inequalities in problem (10.2) to** x **+

Fortunately, the most
important features of the examples we considered above hold for problems with
more than two variables. In particular, a feasible region of a typical linear
programming problem is in many ways similar to convex polygons in the two-dimensional
Cartesian plane. Specifically, it always has a finite number of vertices, which
mathematicians prefer to call ** extreme points** (see Section 3.3).
Furthermore, an optimal solution to a linear programming problem can be found
at one of the extreme points of its feasible region. We reiterate these
properties in the following theorem.

**THEOREM
( Extreme Point Theorem) **Any linear programming
problem with

This theorem implies that to
solve a linear programming problem, at least in the case of a bounded feasible
region, we can ignore all but a finite number of points in its feasible region.
In principle, we can solve such a problem by computing the value of the
objective function at each extreme point and selecting the one with the best
value. There are two major obstacles to implementing this plan, however. The
first lies in the need for a mechanism for generating the extreme points of the
feasible region. As we are going to see below, a rather straightforward
algebraic procedure for this task has been discovered. The second obstacle lies
in the number of extreme points a typical feasible region has. Here, the news
is bad: the number of extreme points is known to grow exponentially with the
size of the problem. This makes the exhaustive inspection of extreme points
unrealistic for most linear programming problems of nontrivial sizes.

Fortunately, it turns out
that there exists an algorithm that typically inspects only a small fraction of
the extreme points of the feasible region before reaching an optimal one. This
famous algorithm is called the ** simplex method**. The idea of this
algorithm can be described in geometric terms as follows. Start by identifying
an extreme point of the feasible region. Then check whether one can get an
improved value of the objective function by going to an adjacent extreme point.
If it is not the case, the current point is optimal—stop; if it is the case,
proceed to an adjacent extreme point with an improved value of the objective
function. After a finite number of steps, the algorithm will either reach an
extreme point where an optimal solution occurs or determine that no optimal
solution exists.

**An
Outline of the Simplex Method**

Our task now is to
“translate” the geometric description of the simplex method into the more
algorithmically precise language of algebra. To begin with, before we can apply
the simplex method to a linear programming problem, it has to be represented in
a special form called the ** standard form**. The standard form has
the following requirements:

It must be a maximization
problem.

All the constraints (except
the nonnegativity constraints) must be in the form of linear equations with
nonnegative right-hand sides.

All the variables must be
required to be nonnegative.

Thus, the general linear
programming problem in standard form with ** m** constraints and

Any linear programming
problem can be transformed into an equivalent problem in standard form. If an
objective function needs to be minimized, it can be replaced by the equivalent
problem of maximizing the same objective function with all its coefficients *c***_{j}** replaced by −

** x **+

Finally, in most linear
programming problems, the variables are required to be nonnegative to begin
with because they represent some physical quantities. If this is not the case
in an initial statement of a problem, an unconstrained variable

*x*_{j}** **can be replaced by the difference between two
new nonnegative variables:

Thus, problem (10.2) in
standard form is the following linear programming problem in four variables:

It is easy to see that if we
find an optimal solution *(x*^{∗}*, y*^{∗}*, u*^{∗}*, v*^{∗}** )** to problem (10.4), we can obtain an optimal
solution to problem (10.2) by simply ignoring its last two coordinates.

The principal advantage of
the standard form lies in the simple mechanism it provides for identifying
extreme points of the feasible region. To do this for problem (10.4), for
example, we need to set two of the four variables in the con-straint equations
to zero to get a system of two linear equations in two unknowns and solve this
system. For the general case of a problem with ** m** equations in

Specifically, we can rewrite
the system of constraint equations of (10.4) as

A basis in the
two-dimensional vector space is composed of any two vectors that are not
proportional to each other; once a basis is chosen, any vector can be uniquely
expressed as a sum of multiples of the basis vectors. Basic and nonba-sic
variables indicate which of the given vectors are, respectively, included and
excluded in a particular basis choice.)

If all the coordinates of a
basic solution are nonnegative, the basic solution is called a ** basic
feasible solution**. For example, if we set to zero variables

As mentioned above, the
simplex method progresses through a series of adjacent extreme points (basic
feasible solutions) with increasing values of the objective function. Each such
point can be represented by a ** simplex tableau**, a table storing the
information about the basic feasible solution corresponding to the extreme
point. For example, the simplex tableau for

In general, a simplex tableau
for a linear programming problem in standard form with ** n** unknowns and

The last row of a simplex
tableau is called the ** objective row**. It is initialized by
the coefficients of the objective function with their signs reversed (in the
first

For example, according to
this criterion, the basic feasible solution ** (**0

** x **+

must be satisfied, which
means that

** x **≤

Note that if we increase the
value of ** x** from 0 to 4, the largest
amount possible, we will find ourselves at the point

Similarly, the negative value
in the ** y**-column of the objective row
signals the fact that we can also increase the value of the objective function
by increasing the value of the

** y **+

which means that

If we increase the value of ** y** from 0 to 2, the largest amount possible, we
will find ourselves at the point

If there are several negative
entries in the objective row, a commonly used rule is to select the most
negative one, i.e., the negative number with the largest absolute value. This
rule is motivated by the observation that such a choice yields the largest
increase in the objective function’s value per unit of change in a vari-able’s
value. (In our example, an increase in the ** x**-value from 0 to 1 at

Now we will explain how to
choose a ** departing variable**, i.e., a basic variable to become nonbasic
in the next tableau. (The total number of basic variables in any basic solution
must be equal to

The row with the smallest ** θ** -ratio determines the departing variable,
i.e., the variable to become nonbasic. Ties may be broken arbitrarily. For our
example, it is variable

and denote it row. Note that
if there are no positive entries in the pivot column, no ** θ** -ratio can be computed, which indicates that
the problem is unbounded and the algorithm stops.

Finally, the following steps
need to be taken to transform a current tableau into the next one. (This
transformation, called ** pivoting**, is similar to the
princi-pal step of the Gauss-Jordan elimination algorithm for solving systems
of linear equations—see Problem 8 in Exercises 6.2.) First, divide all the
entries of the pivot

Tableau (10.6) represents the
basic feasible solution ** (**0

The next iteration—do it
yourself as a good exercise!—yields tableau (10.7):

This tableau represents the
basic feasible solution ** (**3

Let us summarize the steps of
the simplex method.

**Summary
of the simplex method**

**Step 0 ***Initialization*** **Present a given linear programming problem in stan-dard form and
set up an initial tableau with nonnegative entries in the rightmost column and ** m** other columns composing the

**Step 1 ***Optimality test*** **If all the entries in the objective row (except, possibly,** **the one in the rightmost column, which
represents the value of the objective function) are nonnegative—stop: the
tableau represents an optimal solution whose basic variables’ values are in the
rightmost column and the remaining, nonbasic variables’ values are zeros.

**Step 2 ***Finding the entering variable*** **Select a negative entry from among the** **first ** n** elements of the objective
row. (A commonly used rule is to select the negative entry with the largest
absolute value, with ties broken arbitrarily.) Mark its column to indicate the
entering variable and the pivot column.

**Step 3 ***Finding the departing
variable*** **For each positive entry in
the pivot** **column, calculate the ** θ** -ratio by dividing that row’s entry in the
right-most column by its entry in the pivot column. (If all the entries in the
pivot column are negative or zero, the problem is unbounded—stop.) Find the row
with the smallest

**Step 4 ***Forming the next tableau*** **Divide all the entries in the pivot row by** **its entry in the pivot column. Subtract from each of the other
rows, including the objective row, the new pivot row multiplied by the entry in
the pivot column of the row in question. (This will make all the entries in the
pivot column 0’s except for 1 in the pivot row.) Replace the label of the pivot
row by the variable’s name of the pivot column and go back to Step 1.

**Further
Notes on the Simplex Method**

Formal proofs of validity of
the simplex method steps can be found in books devoted to a detailed discussion
of linear programming (e.g., [Dan63]). A few important remarks about the method
still need to be made, however. Generally speaking, an iteration of the simplex
method leads to an extreme point of the prob-lem’s feasible region with a
greater value of the objective function. In degenerate cases, which arise when
one or more basic variables are equal to zero, the simplex method can only
guarantee that the value of the objective function at the new extreme point is
greater than or equal to its value at the previous point. In turn, this opens
the door to the possibility not only that the objective function’s values
“stall” for several iterations in a row but that the algorithm might cycle back
to a previously considered point and hence never terminate. The latter
phenomenon is called ** cycling**. Although it rarely if ever
happens in practice, specific examples of problems where cycling does occur
have been constructed. A simple modifica-tion of Steps 2 and 3 of the simplex
method, called

**Step 2 modified **Among the columns with a negative entry in the
objective** **row, select the column
with the smallest subscript.

**Step 3 modified **Resolve a tie among the smallest** ***θ*** **-ratios by selecting the** **row labeled by the basic variable with
the smallest subscript.

Another caveat deals with the
assumptions made in Step 0. They are automat-ically satisfied if a problem is
given in the form where all the constraints imposed on nonnegative variables
are inequalities *a*_{i}_{1}*x*_{1} + **^{. . .}** +

the
obvious basic feasible solution *x*_{1} = **^{. . .}** =

may present a nontrivial
obstacle. Moreover, for problems with an empty feasible region, no initial
basic feasible solution exists, and we need an algorithmic way to identify such
problems. One of the ways to address these issues is to use an exten-sion to the
classic simplex method called the ** two-phase simplex method** (see, e.g.,
[Kol95]). In a nutshell, this method adds a set of artificial variables to the
equality constraints of a given problem so that the new problem has an obvious
basic fea-sible solution. It then solves the linear programming problem of
minimizing the sum of the artificial variables by the simplex method. The
optimal solution to this problem either yields an initial tableau for the
original problem or indicates that the feasible region of the original problem
is empty.

How efficient is the simplex
method? Since the algorithm progresses through a sequence of adjacent points of
a feasible region, one should probably expect bad news because the number of
extreme points is known to grow exponentially with the problem size. Indeed,
the worst-case efficiency of the simplex method has been shown to be
exponential as well. Fortunately, more than half a century of practical
experience with the algorithm has shown that the number of iterations in a
typical application ranges between ** m** and 3

Since its discovery in 1947,
the simplex method has been a subject of intensive study by many researchers.
Some of them have worked on improvements to the original algorithm and details
of its efficient implementation. As a result of these efforts, programs
implementing the simplex method have been polished to the point that very large
problems with hundreds of thousands of constraints and variables can be solved
in a routine manner. In fact, such programs have evolved into sophisticated
software packages. These packages enable the user to enter a problem’s
constraints and obtain a solution in a user-friendly form. They also provide
tools for investigating important properties of the solution, such as its
sensitivity to changes in the input data. Such investigations are very
important for many applications, including those in economics. At the other end
of the spectrum, linear programming problems of a moderate size can nowadays be
solved on a desktop using a standard spreadsheet facility or by taking
advantage of specialized software available on the Internet.

Researchers have also tried
to find algorithms for solving linear programming problems with polynomial-time
efficiency in the worst case. An important mile-stone in the history of such
algorithms was the proof by L. G. Khachian [Kha79] showing that the ** ellipsoid
method** can solve any linear programming problem in polynomial time.
Although the ellipsoid method was much slower than the simplex method in
practice, its better worst-case efficiency encouraged a search for
alterna-tives to the simplex method. In 1984, Narendra Karmarkar published an
algorithm that not only had a polynomial worst-case efficiency but also was
competitive with the simplex method in empirical tests as well. Although we are
not going to discuss

**Exercises 10.1**

**
**Consider the following version of the post office location problem
(Problem 3 in Exercises 3.3): Given ** n** integers

Solve the following linear
programming problems geometrically.

where *c*_{1} and *c*_{2} are some real numbers not both equal to zero.

Give an example of the
coefficient values *c*_{1} and *c*_{2} for which the problem has a unique optimal
solution.

**
**Give an example of the coefficient values *c*_{1} and *c*_{2} for which the problem has infinitely many
optimal solutions.

**
**Give an example of the coefficient values *c*_{1} and *c*_{2} for which the problem does not have an optimal
solution.

**
**Would the solution to problem (10.2) be different if its inequality
constraints were strict, i.e., ** x** +

**
**Trace the simplex method on

**
**the problem of Exercise 2a.

**
**the problem of Exercise 2b.

**
**Trace the simplex method on the problem of Example 1 in Section 6.6

**
**by hand.

**
**by using one of the implementations available on the Internet.

**
**Determine how many iterations the simplex method needs to solve the
problem

**
**Can we apply the simplex method to solve the knapsack problem (see
Exam-ple 2 in Section 6.6)? If you answer yes, indicate whether it is a good
algorithm for the problem in question; if you answer no, explain why not.

**
**Prove that no linear programming problem can have exactly ** k** ≥ 1 optimal solutions unless

**
**If a linear programming problem

**
**Express the primal and dual problems in matrix notations.

**
**Find the dual of the linear programming problem

maximize *x*_{1} + 4*x*_{2} − *x*_{3} subject to *x*_{1} + *x*_{2} + *x*_{3} ≤ 6

*x*_{1}** **−

**
**Solve the primal and dual problems and compare the optimal values
of their objective functions.

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

Introduction to the Design and Analysis of Algorithms : Iterative Improvement : The Simplex Method |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.