---

The Simplex Method: Setting up the Simplex Tableau

---

• Simplex method: introduction
  • From Wikipedia:

    The simplex algorithm (or simplex method), created by the American mathematician George Dantzig in 1947, is a very popular algorithm for solving linear programs. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century. Wikipedia page: click here The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Wikipedia page: click here

    ---

  • Presentation:

    There is a rich Mathematical background to the Simplex Method... For brevity, I will show you what to do I will not explain why it works.... (It will take too much time to explain, and you may not have the background - heavy duty Linear Algebra)

  ---

  ---

  ---

  ---

• The standard LP
  • The standard LP has the following form:

    max: a1x1 + a2x2 + ... + anxn // Objective function subject to: c11x1 + c12x2 + ... + c1nxn ≤ d1 // Constraints c21x1 + c22x2 + ... + c2nxn ≤ d2 .... cm1x1 + cm2x2 + ... + cmnxn ≤ dm x1 ≥ 0, x2 ≥ 0, ..., xn ≥ 0

    Note:

    The standard LP problem uses only "≤"-constraints The reason for this is: It is very easy to find a "basic" solution when there are only "≤"-constraints We will see that soon.

    ---

  • Fact:

    The Simplex method uses row operations on matrices in Linear Algebra to find the optimal solution of an LP

    ---

  • We must first learn how to convert the standard LP into a "matrix" (tableau) form !!!

  ---

  ---

  ---

  ---

  I I I I

  ---

  ---

• Prelude to conversion to Simplex Tableau:   converting   "≤"-constraints into  "="-constraints
  • Fact:

    Matrix row operations operates on linear equations of the following form: c11x1 + c12x2 + ... + c1nxn = d1 c21x1 + c22x2 + ... + c2nxn = d2 .... cm1x1 + cm2x2 + ... + cmnxn = dm

    ---

  • The first step in converting a standard LP into the tableau (matrix) form is:

    Convert the "≤"-constraints into "="-constraint by adding one surplus variable to each constraint

    ---

    ---

  • Example:

    Consider the following "≤"-constraint: x1 + x2 ≤ 5 This constraint implies that: We must add an amount ≥ 0 to x1 + x2 to obtain the value 5          In other words: x1 + x2 + (some value ≥ 0) = 5 Or: x1 + x2 + s1 = 5 s1 ≥ 0

    The variable   s₁   is called a surplus variable

    ---

  • Remember:

    The Simplex method will only use equality constraints

  ---

  ---

  ---

  ---

  ---

  ---

• Setting up the Simplex Tableau
  • Consider the following Linear constrained optimalization problem (or Linear Programming (LP) problem):

    max: x1 + x2 s.t.: x1 + 2x2 ≤ 8 3x1 + 2x2 ≤ 12 x1 ≥ 0, x2 ≥ 0

    ---

    ---

  • We first write the objective function as an equation by introducing an objective value variable z:

    max: z = x1 + x2 s.t.: x1 + 2x2 ≤ 8 3x1 + 2x2 ≤ 12 x1 ≥ 0, x2 ≥ 0

    We want to maximize the variable x...

    ---

  • Setting up the Simplex Tableau:

    Re-write the Linear Programming problem as a system of linear equations (=):          Original equation Converted equation --------------------+-------------------------------- z = x1 + x2 ⇒ z - x1 - x2 = 0 x1 + 2x2 ≤ 8 ⇒ x1 + 2x2 + s1 = 8 (Add surplus variable) 3x1 + 2x2 ≤ 12 ⇒ 3x1 + 2x2 + s2 = 12 (Add surplus variable) Put the linear system into a matrix form: Linear system: z - x1 - x2 = 0 x1 + 2x2 + s1 = 8 3x1 + 2x2 + s2 = 12 Lined up: (z is traditionally the last column) -x1 - x2 + z = 0 x1 + 2x2 + s1 = 8 3x1 + 2x2 + s2 = 12 Let's fill in all coefficients for completeness: -1x1 - 1x2 + 0s1 + 0s2 + 1z = 0 1x1 + 2x2 + 1s1 + 0s2 + 0z = 8 3x1 + 2x2 + 0s1 + 1s2 + 0z = 12 Re-written in Matrix form: x1 x2 s1 s2 z | RHS ==========================+==== -1 -1 0 0 1 | 0 1 2 1 0 0 | 8 3 2 0 1 0 | 12

    Notes:

    The order of the columns in a Simplex tableau is traditionally: Original variables of the LP They are named: x1, x2, ... Artificially introduced variables needed to use the Simplex Algorithm They are named: s1, s2, ... (surplus variables) and a1, a2, ... (artificial variables) We will discuss the artificial variables when we discuss "≥"-constraints The objective variable z (which is the last variable in the list) The Right Hand Size (RHS) consists of constant values Example: Original Surplus Obj variable var's func RHS <---------><-------><----> <----> x1 x2 s1 s2 z | RHS ==========================+==== -1 -1 0 0 1 | 0 1 2 1 0 0 | 8 3 2 0 1 0 | 12 The matrix form of the Linear Program is called: a Simplex Tableau         Traditionally, the objective value z is always the last column of the Simplex Tableau Make sure that you follow this notation, because otherwise it will cause confusion on where to find the objective value !!!

  ---

  ---

  ---

  ---

  ---

  ---

• Property of a Simplex Tableau
  • Property that every Simplex Tableau must satisfy:

    A Simplex Tableau with m rows must have: at least   m "canonical unit" column vectors on the Left Hand Size of the tableau

    ---

  • Explanation:

    A column vector is a column of values Example: LHS of Simplex Tableau RHS -------------------------+------- -1 -1 0 0 1 | 0 1 2 1 0 0 | 8 3 2 0 1 0 | 12 ^ ^ | | "column" vectors A canonical unit column vector is a column vector where: One of the value is equal to 1 All other values are equal to 0 Example: LHS of Simplex Tableau RHS -------------------------+------- -1 -1 0 0 1 | 0 1 2 1 0 0 | 8 3 2 0 1 0 | 12 ^ ^ ^ | | | "Canonical unit" column vectors Observe that: The Simplex tableau has 3 rows There are also 3 canonical unit vectors in the Simplex tableau !!!

  ---

  ---

  ---

  ---

  I I I I

  ---

  ---

• Basic variables, basis and basic solutions
  • 3 important concepts in the Simplex method:

    Basic variable Basis Bsiac solution

    ---

    ---

    ---

    ---

  • Definition: Basic variable:

    A basic variable is: a variable that is associated with a canonical unit vector in the Simplex Tableau

    Related: Non-basic variable:

    A non-basic variable is a variable that is not a basic variable

    Example:

    x1 x2 s1 s2 z | RHS ==========================+==== -1 -1 0 0 1 | 0 1 2 1 0 0 | 8 3 2 0 1 0 | 12 Basic variables: s1 s2 z Non-basic variables: x1 x2

    ---

    ---

  • Definition: Basis

    Basis = the collection of basic variables

    ---

    ---

  • Definition: Basic solution

    Basic solution = the solution found in ("associated with") a Simplex tableau by:       Setting the non-basic variables = 0 Solving the basic variables (using some very simple equations)

    Example:

    Consider the following Simplex Tableau: x1 x2 s1 s2 z | RHS ==========================+==== -1 -1 0 0 1 | 0 1 2 1 0 0 | 8 3 2 0 1 0 | 12 Basic variables: s1 s2 z Non-basic variables: x1 x2 This corresponds to this set of equations: -1x1 - 1x2 + 0s1 + 0s2 + 1z = 0 1x1 + 2x2 + 1s1 + 0s2 + 0z = 8 3x1 + 2x2 + 0s1 + 1s2 + 0z = 12 To find the basic solution: Set the non-basic variables (x1 and x2) to 0: 0 + 0 + 0s1 + 0s2 + 1z = 0 0 + 0 + 1s1 + 0s2 + 0z = 8 0 + 0 + 0s1 + 1s2 + 0z = 12 Or: 0s1 + 0s2 + 1z = 0 1s1 + 0s2 + 0z = 8 0s1 + 1s2 + 0z = 12 "Solve" it (there not much to solve really) ---result: z = 0 s1 = 8 s2 = 12

    ---

  • This leads to a simple recipe on how to find the basic solution for a Simplex tableau:

    Set the values of the non-basic variable   = 0 (zero) Set the values of the basic variable   = Right-Hand-Side

    ---

    ---

    ---

    ---

    ---

    ---

  • Fact:

    Every Simplex tableau is associated with a basic solution. (That's because a Simplex Tableau with m rows always has m basic variables !!!) See: the property of a Simpelx Tableau: click here

  ---

  ---

  ---

  ---

  ---

• The locations of the basic solution in Simplex

  • Fact about the basic solutions in a Simplex tableau:

    Every basic solution is a "corner point" in the feasible region !!!

    ---

    ---

    ---

  • Example: the location of a basic solution

    Simplex Tableau: Matrix form: x1 x2 s1 s2 z | RHS ==========================+==== -1 -1 0 0 1 | 0 1 2 1 0 0 | 8 3 2 0 1 0 | 12 Basic solution: x1   =   0       (non-basic variable = 0)) x2   =   0       (non-basic variable = 0)) s1   =   8       (basic variable = RHS)) s2   =   12     (basic variable = RHS)) z   =   0        (basic variable = RHS)) Note: Since the objective function z = x1 + x2, and x1   =   0       (non-basic variable = 0)) x2   =   0       (non-basic variable = 0)) Naturally, the objective variable z = x1 + x2 is equal to 0 + 0 = 0 !!! Graphical depiction of this basic solution: (x1 = 0, x2 = 0)