Programmation linéaire

Un problème simple

Cet exercice est à faire à la main.

Soit le programme linéaire écrit sous forme canonique

Maximiser \(18x_1 + 12.5x_2\)
Sous
\(\begin{array}{c r r r} x_1 & + & x_2 & \leq & 20\\ x_1 & & & \leq & 12\\ & & x_2 & \leq & 16\\ & & x_1,x_2 & \ge & 0\\ \end{array}\)

  1. Écrire le programme sous forme standard.
  2. Résoudre le problème avec une approche géométrique.
  3. Résoudre le problème en utilisant l’algorithme du simplexe.

Le reste du TD est à développer dans un notebook Jupyter.

Algorithme du simplexe

On va coder l’algorithme du simplexe, en utilisant la méthode des tableaux.

Étant donné un programme linéaire sous forme standard

Maximiser \(c·\bar{x}\),
Sous \(A\bar{x} = b\),

où \(c\) est la fonction de coût, \(b\) le vecteur des constantes, et \(\bar{x}\) le vecteur des variables (base et hors-base), la méthode encode ce programme dans le tableau

\[\begin{array}{ c | c} c & 0\\ \hline A & b \end{array}\]

Ensuite, tant qu’il existe une entrée positive dans la ligne de coût \(c\), l’algorithme exécute une transformation appelée pivot sur les lignes du tableau. L’algorithme termine lorsqu’il n’y a plus d’entrées positives dans le coût, ou bien lorsqu’il détermine que le programme linéaire est non-borné.

Si \(v\) est la variable hors-base de \(x\) sélectionnée pour opérer le pivot, une itération du pivot consiste en les opérations suivantes :

La conséquence d’un pivot est de transformer la variable \(v\) de variable hors base en variable de base. La solution associée à la transformation sera celle où les variables hors base valent \(0\), et les variables de base valent l’entrée correspondante dans le vecteur \(b\).

Exemple

Soit le programme linéaire sous forme standard

Maximiser \(x_1 + x_2\)
Sous
\(\begin{array}{c r r r} x_3 =& 8& - 4x_1& + x_2\\ x_4 =& 10& - 2x_1& - x_2\\ x_5 =& 2& + 5x_1& - 2x_2 \end{array}\)

le tableau correspondant est

\[\begin{array}{ c c c c c | c} x_1 & x_2 & x_3 & x_4 & x_5\\ 1 & 1 & 0 & 0 & 0 & 0\\ \hline 4 & -1 & 1 & & & 8\\ 2 & 1 & & 1 & & 10\\ -5 & 2 & & & 1 & 2 \end{array},\]

où on reconnaît les variables hors-base \(x_1,x_2\) et les variables de base \(x_3,x_4,x_5\) (associées à la matrice identité), et auquel on associe la solution réalisable de base \((x_1,x_2,x_3,x_4,x_5)=(0,0, 8, 10, 2)\).

Puisque les coûts associées sont \(1,1\), l’algorithme du simplexe peut choisir aussi bien la variable \(x_1\) que la variable \(x_2\) comme variable entrante pour pivoter. Choisissons la variable \(x_1\), le pivot va alors calculer

La ligne choisie pour pivoter sera donc la ligne 1, ce qui va donner après pivotage le tableau

\[\begin{array}{c c c c c | c} x_1 & x_2 & x_3 & x_4 & x_5\\ & \frac{5}{4} & -\frac{1}{4} & & & 2 \\ \hline 1 & -\frac{1}{4} & \frac{1}{4} & & & 2\\ & \frac{3}{2} & -\frac{1}{2} & 1 & & 6\\ & \frac{3}{4} & \frac{5}{4} & & 1 & 12 \end{array},\]

où \(x_1,x_4,x_5\) sont devenues variables de base, et où la solution réalisable de base correspond à \((x_1,x_2,x_3,x_4,x_5)=(2,0, 0, 6, 12)\). La valeur de l’objectif est maintenant \(2\).

: Écrire une fonction pivot(cout, variables) prenant les entrées suivantes :

La fonction doit donner en sortie le résultat d’un pivot de l’algorithme du simplexe, c’est à dire un tuple (cout, variables, faisable), où

Si le problème est non-borné, on va plutôt donner en sortie (cout, variables, None), où cout et variables n’ont pas été modifiés. Si l’algorithme a déjà atteint le maximum, on n’opérera pas de pivot, on donnera en sortie (cout, variables, faisable), où cout et variables n’ont pas été modifiés.

Appliquer cette fonction à :

cout = [1, 1, 0, 0, 0, 0]
variables = [
    [ 4, -1, 1, 0, 0,  8],
    [ 2,  1, 0, 1, 0, 10],
    [-5,  2, 0, 0, 1,  2]
]
pivot(cout, variables)

: Écrire l’algorithme du simplexe complet.

Appliquer votre programme à l’example ci-dessus :

c = [1, 1]
A = [[4, -1],
     [2, 1],
     [-5, 2]]
b = [8, 10, 2]
simplexe(c, A, b)