PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (210)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (38)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
simplex algorithm (Algorithm)

The simplex algorithm is used as part of the simplex method (due to George B. Dantzig) to solve linear programming problems. The algorithm is applied to a linear programming problem that is in canonical form.

A canonical system of equations has an ordered subset of variables (called the basis) such that for each $ i$, the $ i^{th}$ basic variable has a unit coefficient in the $ i^{th}$ equation and zero coefficient in the other equations.

As an example $ x_1, \ldots , x_r$ are basic variables in the following system of $ r$ equations:


$\displaystyle x_1 \quad \quad$ $\displaystyle +$ $\displaystyle a_{1,r+1}x_{r+1} + \cdots + a_{1,n}x_n = b_1$  
$\displaystyle x_2 \quad$ $\displaystyle +$ $\displaystyle a_{2,r+1}x_{r+1}+ \cdots + a_{2,n}x_n = b_2$  
$\displaystyle \ldots$      
$\displaystyle x_r$ $\displaystyle +$ $\displaystyle a_{r,r+1}x_{r+1} + \cdots + a_{r,n}x_n = b_r$  

The simplex algorithm is used as one phase of the simplex method.

Suppose that we have a canonical system with basic variables $ x_1, \ldots, x_m, -z$ and we seek to find nonnegative $ x_i$ $ i=1, \ldots, n$ such that $ z$ is minimal. That is, we have


$\displaystyle x_i + \sum_{j=m+1}^n a_{ij} x_j$ $\displaystyle =$ $\displaystyle b_i \quad i=1, \ldots, m$  
$\displaystyle -z + \sum_{j=m+1}^n c_j x_j$ $\displaystyle =$ $\displaystyle -z_o$  

where $ a_{ij}, b_j , c_j , z_o$ are constants, and $ b_j \geq 0, \quad j=1,\ldots, m$.

Notice that if we set $ x_{m+1} = 0, \ldots, x_n = 0$ we will have a feasible solution with $ z=z_o.$. Hence, any optimal solution will have $ z \leq z_o$. The algorithm can now be described as follows:

Step 1. Set $ N = \{m+1, \ldots , n\}$ and $ B=\{1, \ldots, m\}$. Put $ c_j = 0$ for $ j\in B$.

Step 2. If there an index $ j \in N$ such that $ c_j < 0$ then choose $ s \in N$ such that

$\displaystyle c_s = \operatorname{min}_{j \in N} c_j $
else stop. The solution is given by $ x_i = 0$ for $ i \in N$ and $ x_i = b_i$ for $ i \in B$, $ z=z_o$.

Step 3. If $ a_{is} \leq 0$ for all $ i$ then stop. The value of $ z$ has no lower bound. Else, let $ \frac{b_r}{a_{rs}} = \operatorname{min}_{a_{is}>0} \frac{b_i}{a_{is}}$. If there is more than one choice for $ r$ it does not matter which one is chosen unless $ b_i = 0$. This is the so-called degenerate case. In this case, one can choose uniformly at random from among those $ i$ for which $ b_i = 0$.

Step 4. (Pivot on $ a_{rs}$). Multiply the $ r^{th}$ equation by $ \frac{1}{a_{rs}}$ and for each $ i=1, \ldots, m$, $ i \ne r$ replace equation $ i$ by the sum of equation $ i$ and the (replaced) equation $ r$ multiplied by $ -a_{is}$. Replace the equation for $ z$ by the sum of the equation for $ z$ and the (replaced) equation $ r$ multiplied by $ -c_s$. Note: The replacement operations of course change the coefficients $ a_{ij}$ and $ c_j$. As the algorithm proceeds it is of course necessary to use the changed coefficients.

Step 5. (Update $ B$ and $ N$) Put $ s$ into $ B$ and $ r$ into $ N$ and remove $ s$ from $ N$ and $ r$ from $ B$. Go to step 2.

There are examples where the algorithm does not terminate in a finite number of steps; but if there is non-degeneracy at each iteration, the algorithm will terminate in a finite number of steps.



"simplex algorithm" is owned by Mathprof. [ full author list (6) | owner history (7) ]
(view preamble)

View style:

Other names:  simplex method
Keywords:  linear programming
Log in to rate this entry.
(view current ratings)

Cross-references: iteration, finite, necessary, operations, sum, pivot, lower bound, index, solution, feasible, minimal, coefficient, unit, basis, variables, subset, equations, canonical, algorithm, linear programming problems
There are 2 references to this entry.

This is version 19 of simplex algorithm, born on 2003-04-24, modified 2006-10-30.
Object id is 4212, canonical name is SimplexAlgorithm.
Accessed 14871 times total.

Classification:
AMS MSC: 90C05 (Operations research, mathematical programming :: Mathematical programming :: Linear programming)
Pending Errata and Addenda
None.
[ View all 8 ]
Discussion
Style: Expand: Order:
forum policy
Announced simplex algorithm object up for adoption by PrimeFan on 2006-10-13 16:28:25
I've given up control of the simplex algorithm object. Hopefully now it can be adopted or transferred to someone who actually knows what this is talking about.
[ reply | up ]
cross-link to Nelder Mead by sanders_muc on 2006-06-06 03:17:12
Maybe, one should add that the term "simplex algorithm" is also used to refer to the Nelder-Mead algorithm.

 Simon
[ reply | up ]
Interact
post | correct | update request | add example | add (any)