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.  

Definition (Convex Polytope).  In two dimensions a convex polytope is a region that is the intersection of a finite set of half-planes (the general idea of a convex  polygon).  In three dimensions a convex polytope is solid region that is the intersection of a finite set of half-spaces (the generalized idea of a convex polyhedron).  The generalization in n dimensions is called a polytope.

Example 1.  Two students Ann and Carl work x and y hours per week, respectively.  Together they can work at most 40 hours per week.  According to the rules for part timers Ann can work at most 8 hours more that Carl.  But Carl can work at most 6 hours more than Ann.  There is an extra constraint  .  Determine the region    for these constraints.
1 (a).  If Ann and Carl earn $15 and $17 per hour, respectively, then find their maximum combined income per week.
1 (b).  If Ann and Carl earn $17 and $15 per hour, respectively, then find their maximum combined income per week.
1 (c).  If Ann and Carl both earn $16 per hour, respectively, then find their maximum combined income per week.

Solution 1 (a).

Solution 1 (b).

Solution 1 (c).

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.  

Computer Programs  Linear Programming  

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.

Example 2.  Consider the region in the plane defined by the inequalities:  

           

2 (a).  Find the maximum of      over the region .  
2 (b).  Find the maximum of      over the region .  

Solution 2 (a).

Solution 2 (b).

Example 3.  Consider the region in the plane defined by the inequalities:  

          

3 (a).  Find the maximum of      over the region .  
3 (b).  Find the maximum of      over the region .  

Solution 3 (a).

Solution 3 (b).

Example 4.  Find the maximum of      subject to the constraints:

          

Solution 4.

Example 5.  Find the maximum of      subject to the constraints:

           

Solution 5.

Example 6.  Find the maximum of       subject to the constraints:

          

Solution 6.

Research Experience for Undergraduates

Linear Programming  Internet hyperlinks to web sites and a bibliography of articles.  

Download this Mathematica Notebook Linear Programming-Simplex Method

(c) John H. Mathews 2005