Algorithme du Simplexe — Méthode des deux phases

Implémentation de l'algorithme du simplexe basée sur la méthode du tableau, avec Phase I (point réalisable) et Phase II (optimisation), une interface CLI et une application Streamlit.

---

Structure du projet

simplex_project/
│
├── simplex/                   # ← Module principal (logique pure)
│   ├── __init__.py
│   ├── core.py                # Algorithme : Phase I, Phase II, structures
│   └── display.py             # Formatage et affichage des tableaux
│
├── app/                       # ← Interfaces utilisateur
│   ├── cli.py                 # Interface ligne de commande
│   └── streamlit_app.py       # Interface web Streamlit
│
├── examples/
│   └── examples.py            # Exemples prêts à l'emploi
│
├── tests/
│   └── test_simplex.py        # Tests unitaires
│
├── requirements.txt
└── README.md

---

Installation

pip install -r requirements.txt

---

Utilisation

1. Interface CLI (terminal)

# Mode interactif (saisie au clavier)
python app/cli.py

# Exemple prédéfini
python app/cli.py --example belt
python app/cli.py --example production
python app/cli.py --example equality
python app/cli.py --example mixed

# Pour  le problème de Klee-Minty (remplaçer <n> par la valeur de n)
python example/examples <n>   

# Sans afficher les tableaux intermédiaires
python app/cli.py --example belt --no-tableaux

# Lister les exemples disponibles
python app/cli.py --list-examples

2. Application web Streamlit

streamlit run app/streamlit_app.py

Puis ouvrir http://localhost:8501 dans le navigateur.

3. Utilisation directe du module Python

import numpy as np
from simplex import solve, print_result

c = np.array([3.0, 2.0])
A = np.array([[1, 2], [2, 1], [1, 0], [0, 1]], dtype=float)
b = np.array([14.0, 14.0, 6.0, 6.0])
signs = ["<=", "<=", "<=", "<="]

result = solve(c, A, b, signs, problem_type="max")
print_result(result)

# Accès programmatique
print("Valeur optimale :", result.objective_value)
print("Solution :", result.solution)
print("Statut :", result.status)   # 'optimal' | 'infeasible' | 'unbounded'

4. Lancer les tests

python tests/test_simplex.py
# ou avec pytest
python -m pytest tests/ -v

---

Algorithme

Fondement mathématique

Le problème résolu est :

min  z = c^T x
s.t. Ax = b,  x ≥ 0

Toute maximisation est convertie en minimisation (c ← −c).

Phase I

Pour chaque type de contrainte, des variables auxiliaires sont ajoutées :

Signe	Variables ajoutées	Base initiale
<=	variable d'écart +s_i	s_i
>=	variable d'excès −e_i + artificielle +a_i	a_i
=	variable artificielle +a_i	a_i

L'objectif de Phase I est : minimiser la somme des artificielles. Si l'optimum vaut 0 → solution réalisable trouvée.

Phase II

On part de la base réalisable obtenue en Phase I. On remplace la fonction objectif par le vrai c et on itère le simplexe.

Critères

• Entrante : variable hors base avec le coût réduit le plus négatif (argmin z_j)
• Sortante : test du ratio minimum (min b_i / A_{ij} pour A_{ij} > 0)
• Arrêt : tous les coûts réduits ≥ 0

---

Format des entrées

Paramètre	Type Python	Exemple
c	np.ndarray	[3, 2]
A	np.ndarray	[[1, 2], [2, 1]]
b	np.ndarray	[14, 14]
signs	List[str]	["<=", "<="]
problem_type	str	"max" ou "min"