# CHAPTER 16

# SIMPLEX METHOD

# 16.1 Solving Linear Equations Using Row Operations

The examples in previous chapters illustrate that solving linear programs involves the solution of systems of linear simultaneous algebraic equations. In this section we describe a method for solving a system of *n* linear equations in *n* unknowns that we use in subsequent sections. The method uses elementary row operations and corresponding elementary matrices. For a discussion of numerical issues involved in solving a system of simultaneous linear algebraic equations, we refer the reader to [41] and [53].

An elementary row operation on a given matrix is an algebraic manipulation of the matrix that corresponds to one of the following:

**1.**Interchanging any two rows of the matrix

**2.**Multiplying one of its rows by a real nonzero number

**3.**Adding a scalar multiple of one row to another row

An elementary row operation on a matrix is equivalent to premultiplying the matrix by a corresponding *elementary matrix*, which we define next.

**Definition 16.1** We call ** E** an

*elementary matrix of the first kind*if

**is obtained from the identity matrix**

*E***by interchanging any two of its rows.**

*I*An elementary matrix of the first kind formed from ** I** by interchanging the

*i*th and the

*j*th rows has the form

Note that ** E** is invertible and

**=**

*E*

*E*^{−1}.

**Definition 16.2** We call ** E** an

*elementary matrix of the second kind*if

**is obtained from the ...**

*E*Get *An Introduction to Optimization, 4th Edition* now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.