2  Simplex

2.1 Introduction

In linear optimization, consider a problem in canonical form:

\(\max\{c^T x \,|\, Ax \leq b, x \geq 0\}\)

where:
- \(x\) is the vector of variables to be determined
- \(c\) is the vector of coefficients of the objective function
- \(A\) is the matrix of coefficients of the constraints

Any problem in canonical form can be reformulated into a problem of the form:

\(\max\{c_{0} + c^T x \,|\, Ax + x' = b, x \geq 0\, x' \geq 0\}\)

This form is known as the standard form.

The Simplex algorithm is a method to move from one basic solution to another while seeking to improve the objective function.
When an optimal basic solution is reached, i.e. one that maximizes the objective function, the algorithm stops.

2.1.1 Definition Basic solution and optimal basic solution

In the standard form below, we assume \(b \geq 0\ \). The constant \(c_{0}\) is introduced for technical reasons.
In this case, \((x,x'​) = (0,b)\) constitutes a basic solution of the problem, and we also refer to the variables \(x'\) as basic and the variables \(x\) as non-basic. If the problem is unbounded, it has no optimal solution, and the solution below is admissible.

2.1.2 Preparation Data organization

Let \(n\) be the number of non-basic variables, and \(m\) be the number of basic variables.
To perform the calculations, it is useful to organize the data in a table \(A\) which initially has the following form:

_	\(c_{1}\)	…	\(c_{n}\)	0	0…	0	\(-c_{0}\)
\(x_{n+1}\)	\(a_{1,1}\)	…	\(a_{1,n}\)	1	0…	0	\(b_{1}\)
…	…	…	…	…	……	…	…
\(x_{n+m}\)	\(a_{m,1}\)	…	\(a_{m,n}\)	0	0…	1	\(b_{m}\)

On this table, we will perform the algorithm explained in the following section. At each iteration of the algorithm, we move from one basic solution to another, each time increasing the non-basic variables (while respecting the constraints).

2.2 Algorithm

Each iteration of the algorithm consists of three consecutive operations:

2.2.1 Step 1 Pivot selection

In this step, an incoming variable (non-basic) and an outgoing variable (basic) are selected as follows:

– We find \(1 \leq e \leq n\) such that \(c_{e} \geq 0\).
– There are two possible scenarios:

• \(\forall i \in [n+1, m], a_{i,e} \leq 0\). In this case, the problem is unbounded and has no optimal solution.
  
• We look for a basic variable minimizing the quantity \(b_{i} / a_{i,e}\). We denote it \(x_{s}, s \in [n+1, m]\).
  We know that \(a_{s,e} > 0\) and will use this value as a pivot.
  

2.2.2 Step 2 Table update

This is the heart of the algorithm.
Given \(x_{e}\) as the incoming variable, \(x_{s}\) as the outgoing variable, and \(a_{s-n, e}\) as the pivot, we perform the following operations and obtain a new table \(A'\) (in the following order):

# 1) Process lines except pivot

• \(\forall i \in [1, m+n]\), \(\forall j \in [1, m], j \neq s-n\), \(a'_{j,i} \leftarrow a_{j,i}-a_{s-n,i}*a_{j,e}/a_{s-n,e}\)
  
• \(\forall j \in [1, m], j \neq s-n\), \(b'_{j} \leftarrow b_{j}-a_{j,e}*b_{s-n}/a_{s-n,e}\)
  

# 2) Process pivot line

• \(\forall i \in [1, m+n], a'_{s-n,i} \leftarrow a_{s-n,i}/a_{s-n,e}\)
  
• \(b_{s-n} \leftarrow b'_{s-n}/a_{s-n,e}\)
  

# 3) Process coefficients line

• \(\forall i \in [1, m+n]\), \(c'_{i} \leftarrow c_{i} - c_{e} * a'_{s-n,i}\)
• \(c'_{0} \leftarrow c_{0} + c_{e} * b_{s-n}\)

2.2.3 Step 3 Solution optimality

After each iteration of Step 1 and Step 2, we check whether the stop conditions have been met.
The program stops if:

• all coefficients \(c_{i}\) are negative. in this case, the basic solution associated with our matrix \(A\) is an optimal basic solution to our problem, and the value of our objective function as a function of this solution is equal to \(c_{0}\).
  
• all non-basic variables have already been output. In this case, the problem has no optimal solution, and \((0,b)\) is an admissible solution.
  

2.3 Code

To transform a problem into equation form, and find its optimal basic solution using the Simplex algorithm:

simplexe = Simplexe(canonical_form)
basic_sol, obj_value = simplexe.execute_simplexe()

To print the table obtained at the end of the calculation:

simplexe.print_table()

2.3.1 Examples

\(\textbf{2.3.1.1 Bounded Problem}\)

\(\max 3x_{1} + x_{2} + 2x_{3}\)
\(x_{1} + x_{2} + 3x_{3} \leq 30\)
\(2x_{1} + 2x_{2} + 5x_{3} \leq 24\)
\(4x_{1} + 1x_{2} + 2x_{3} \leq 36\)
\(x_{1},x_{2},x_{3} \geq 0\)

canonical_form = [
    [3, 1, 2],
    [1, 1, 3, 30],
    [2, 2, 5, 24],
    [4, 1, 2, 36]
]
simplexe = Simplexe(canonical_form)
basic_sol, obj_value = simplexe.execute_simplexe()

[✅]Optimal solution found.

Basic Solution:  [8.0, 4.0, 0, 18.0, 0, 0]
Objective function value:  28.0

simplexe.print_table()

['0', '0', '-1/6', '0', '-1/6', '-2/3', '-28']
['0', '0', '1/2', '1', '-1/2', '0', '18']
['0', '1', '8/3', '0', '2/3', '-1/3', '4']
['1', '0', '-1/6', '0', '-1/6', '1/3', '8']

\(\textbf{2.3.1.2 Unbounded Problem}\)

\(\max x_{1} + 2x_{2}\)
\(-x_{1} - x_{2} \leq 3\)
\(-2x_{1} - 3x_{2} \leq 5\)
\(x_{1},x_{2} \geq 0\)

canonical_form = [
    [1, 2],
    [-1, -1, 3],
    [-2, -3, 5],
]

simplexe = Simplexe(canonical_form)
basic_sol, obj_value = simplexe.execute_simplexe()

[❌]No optimal solution found.

Basic Solution:  [0, 0, 3, 5]
Objective function value:  0