The Simplex Method

In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension.

• Wikipedia

🐝 The Simplex Method is a popular algorithmic approach in linear programming used to find the optimal solution to linear inequalities.

🐛 It was developed by George Dantzig in 1947 and has since been foundational in solving problems in operations research, economics, and engineering.

🐌 Linear programming involves maximizing or minimizing a linear objective function, subject to a set of linear constraints. The constraints typically define a feasible region, and the Simplex Method navigates through vertices of this region to find the best value of the objective function.

1. Standard Form Conversion

First, ensure that all the linear programming problem is converted into standard form. This typically means that all constraints are inequalities and are non-negative.

2. Setting Up the Initial Simplex Tableau

Begin with an initial solution that is easy to compute, such as letting all variables but the slack variables be zero.

3. Pivoting

The core operation in the Simplex algorithm involves pivoting to move from one vertex of the feasible region to a neighboring vertex, improving the objective function's value with each move.

4. Optimality Check

After each pivot, check if the current vertex is optimal. If no coefficients of the objective function in the tableau are negative, the current solution is optimal.

graph TD;
    A[Start] --> B[Convert to Standard Form];
    B --> C[Set up Initial Simplex Tableau];
    C --> D{Check Optimality};
    D -- No negative coefficients --> E[Optimal Solution Found];
    D -- Negative coefficients exist --> F[Perform Pivoting];
    F --> G[Update Tableau];
    G --> D;
    E --> H[End Process];

---

Simple Example

Maximize: $Z = 3x_1 + 5x_2$
Subject to:

• $x_1 + 2x_2 ≤ 8$
• $4x_1 + 2x_2 ≤ 12$
• $x_1, x_2 ≥ 0$

First, we shall write the problem in standard form.

To do so we need to write each inequality as an equality, and for that we create a variable $s_i$ that represents the distance of the formula to the limiting factor.

As both formulas are below the limiting numbers (8, 12) we have to add some slack.

• $x_1 + 2x_2 + s_1 = 8$
• $4x_1 + 2x_2 + s_2 = 12$
• $x_1, x_2, s_1, s_2 ≥ 0$

Setting up the Initial Simplex Tableau

To start the Simplex Method, we set up the initial tableau. The columns represent the variables $x1$​, $x2$​, $s1$​, $s2$​, and the solution column (right-hand side, RHS). The rows represent the constraints including the objective function.

Basic Variable	$\color{tomato}x_1$	$\color{tomato}x_2$	$\color{lime}s_1$	$\color{lime}s_2$	= to
$s_1$	1	$\color{gold}2$	1	0	8
$s_2$	4	2	0	1	12
$Z$	-3	-5	0	0	0

Here we have checked the value of $Z$ at the origin ($x_1=0$, $x_2=0$). This choice of 'fixed values' allows for the tweeking of all other values. This is the initial basic feasible solution.

Initial Assumptions

At the beginning of the Simplex Method:

Decision Variables

Set to zero:

• $x_1=0$
• $x_2=0$

Slack Variables

Take values equivalent to the constants on the right-hand side (RHS) of the inequalities when converted to equations, which are the initial constraints themselves. For our problem:

• $s_1=8$
• $s_2=12$

How Simplex Moves From the Origin

The Simplex Method progresses by moving from one vertex of the feasible region to an adjacent vertex. The movement is along the edges of the feasible region defined by the constraints. Each step or pivot:

Pivoting Steps

The Simplex Method progresses by moving from one vertex of the feasible region to an adjacent vertex. The movement is along the edges of the feasible region defined by the constraints.

1. Selects a non-basic variable (one of the $x$s initially set to zero) to increase from zero towards positive, making it a basic variable (included in the solution basis).
2. Correspondingly adjusts other variables (possibly including previously basic variables), which may reduce to zero (turning them non-basic).

Solving

In our specific problem, the initial tableau and the pivot operations reflects that:

• Initial Point:
• $x_1=0$
• $x_2=0$
• $s_1=8$
• $s_2=12$

1. Select the Pivot Column and Row
   • We choose the column with the most negative coefficient in the objective function row to increase the value of $Z$. In this case, it's $x_2​$ with a coefficient of -5. Then, select the pivot row by the minimum ratio test (RHS divided by the corresponding positive pivot column value):
     • For $s_1$: $8/2 = 4$
     • For $s_2$: $12/2 = 6$
       The pivot row is $s1$​ since $4$ is the smallest ratio.

After Pivoting
The variable $x_2​$ was introduced into the basis by allowing it to increase from zero. The corresponding row operations ensured that the system's constraints were still satisfied while aiming to improve the objective function.

2. Perform Row Operations
   • Pivot on $x_2$ in $s_1$'s row:
     • Make the pivot element to 1 by dividing the entire row by 2
     • Zero out the $x2$​ column in other rows using row operations:
       • $s_2$ row: New $s_2$ = Old $s_2$ - (Old $s_1$ × $1$)
       • $Z$ row: New $Z$ = Old $Z$ - (Old $s_1$ × $2.5$)

Basic Variable	$x_1$	$x_2$	$s_1$	$s_2$	= to
$x_2 = 4$	0.5	1	0.5	0	4
$s_2$	3	0	-1	1	4
$Z$	-0.5	0	2.5	0	20

Check if there are any negative coefficients in the objective function row. If not, the current solution is optimal.

All coefficients in $Z$ row are non-negative, indicating that the solution is optimal.

• $x_1​=0$
• $x_2=4$
• $s_1=0$
• $s_2=4$
• Maximum $Z$ value is $20$

Next iteration

Basic Variable	$x_1$	$x_2$	$s_1$	$s_2$	= to
$x_2$	0.5	1	0.5	0	4
$x_1 = 4/3$	$\color{gold}3$	0	-1	1	4
$Z$	-0.5	0	2.5	0	20

Basic Variable	$x_1$	$x_2$	$s_1$	$s_2$	= to
$x_2$	0	1	2/3	-1/6	10/3
$x_1 = 4/3$	1	0	-1/3	1/3	4/3
$Z$	0	0	7/3	1/6	62/3