Linear Programming - The Simplex Method

Background for Linear Programming

    

Linear programming is an area of linear algebra in which the goal is to maximize or minimize a linear function    of    variables on a region    whose boundary is defined by linear inequalities and equations.  In this context, when we speak of a "linear function of variables" we mean that     has the form
    
        .

The region    is a convex polytope.  If all the vertices of    are known, then the maximum of   will occur at one of these vertices.  

    The solution can be constructed using the simplex method and is attributed to George Dantzig (1914 - ) who was born in Portland, Oregon.  The simplex method starts at the origin and follows a path along the edges of the polytope to the vertex where the maximum occurs.  The history of the development of the simplex method has been summarized in the article:

An Interview with George B. Dantzig: The Father of Linear Programming  by Donald J. Albers; Constance Reid; in The College Mathematics Journal, Vol. 17, No. 4. (Sep., 1986), pp. 292-314, Jstor.  

Standard Form of the Linear Programming Problem

    The standard form of the linear programming problem is to maximize    of    variables .  
    
(1)     Maximize   

       
    
         where       for  .  

(2)     Subject to the m constraints  

         where       for  .  

(3)     With the primary constraints      for   .  

    The coefficients   and    can be any real number.  It is often the case that  ,  but the cases  or    can occur.

 

Setting up the Extended Simplex Tableau

    For computational purposes, we construct a tableau. The first rows consist of the coefficients matrix , the identity matrix and the column vector . In the -row of the tableau the first elements are the coefficients  ,  which are called the coefficients of the augmented objective equation.  The remainder of the bottom row is filled in with zeros.  An extra column on the right will be used in the decision process in solving for the variables.

    

Column

    

    The non-negative variable is called a slack variable and is the amount that the linear combination    falls short of the bound  .  It's purpose is to change an inequality to an equation, i.e. we have

(4)       for rows    in the tableau.    

    The goal of the simplex method is to exchange some of the columns of 1's and 0's of the slack variables into columns of 1's and 0's of the decision variables.  

A explanation of this tableau is given in the link below.

Simplex Method Details  

 

Algorithm (Simplex Method).  To find the minimum of    over the convex polytope .  

(i)    Use non-negative slack variables    and form a system of equations and the initial tableau.

(ii)   Determine the exchange variable, the pivot row and pivotal element.  
       The exchange variable is chosen in the pivot column where    is the smallest negative coefficient.  
       The pivot row    is chosen where the minimum ratio occurs for all rows with  .  
       The pivot element is .

(iii)  Perform row operations to zero out elements in the pivotal column above and below the pivot row .

(iv)  Repeat steps (ii) and (iii) until there are no negative coefficients    in the bottom row.  

 

Mathematica Subroutines (Simplex Method).  To find the minimum of    over the convex polytope .  
Activate the following four cells.

Warning.  The above subroutines are for pedagogical purposes to illustrate the simplex method.  They will not work for certain cases when  ,  and in cases where more than one coefficient     is set equal to zero in one step of the iteration.   For complicated problems one of the Mathematica subroutines:  ConstrainedMin, ConstrainedMax, or LinearProgramming  should be used.