Graphes et Programmation Lineaire

PARTIE A : GENERALITES

Presentation

Le cours "Graphes et Programmation Lineaire" couvre deux domaines complementaires de la recherche operationnelle: la theorie des graphes pour modeliser des reseaux et relations, et la programmation lineaire pour optimiser des systemes sous contraintes. Ces outils mathematiques sont essentiels pour resoudre des problemes complexes d'optimisation dans l'industrie, la logistique, et les reseaux.

Annee Academique : 2023-2024
Semestre : 8
Categorie : Mathematiques Appliquees / Recherche Operationnelle

---

PARTIE B : PARTIE DESCRIPTIVE

Details de l'experience

Environnement et contexte

Le cours combinait theorie mathematique rigoureuse et applications pratiques via des logiciels d'optimisation. Nous avons etudie des algorithmes classiques (Dijkstra, Ford-Fulkerson, Simplexe) et les avons appliques a des problemes reels: routage, planification, allocation de ressources, ordonnancement.

Ma fonction

Dans ce cours, j'ai ete responsable de :

• Modeliser des problemes reels en graphes ou programmes lineaires
• Appliquer des algorithmes de recherche de chemins, flots, et arbres couvrants
• Formuler et resoudre des problemes d'optimisation lineaire
• Utiliser des solveurs (Python, CPLEX, GLPK)
• Interpreter les solutions et analyses de sensibilite
• Resoudre des problemes de transport, affectation, et ordonnancement

PARTIE C : PARTIE TECHNIQUE

Cette section explore les aspects techniques des graphes et de la programmation lineaire.

Concepts techniques appris

1. Theorie des Graphes - Definitions

Graphe G = (V, E) :

• V : ensemble de sommets (vertices)
• E : ensemble d'aretes (edges) ou arcs

Types :

• Graphe oriente : arcs avec direction
• Graphe non oriente : aretes sans direction
• Graphe pondere : poids sur aretes/arcs
• Graphe simple : pas de boucle ni arete multiple

Degre :

• Degre d'un sommet : nombre d'aretes incidentes
• Degre entrant/sortant (graphe oriente)

Chemin : sequence de sommets relies par aretes
Cycle : chemin ferme (revient au point de depart)
Connexite : tous sommets accessibles depuis tout autre

2. Algorithmes de Plus Court Chemin

Algorithme de Dijkstra :
Trouve plus court chemin d'une source vers tous autres sommets.

Complexite : O((V+E)log V) avec tas

Limitation : poids positifs uniquement

Algorithme de Bellman-Ford :
Gere poids negatifs, detecte cycles negatifs.

Complexite : O(VE)

Algorithme de Floyd-Warshall :
Plus courts chemins entre toutes paires de sommets.

Complexite : O(V³)

Applications :

• GPS et navigation
• Routage reseau
• Planification de trajets
• Jeux video (IA)

3. Arbres Couvrants

Arbre : graphe connexe acyclique
Arbre couvrant : arbre incluant tous les sommets

Arbre Couvrant de Poids Minimum (MST) :

Algorithme de Kruskal :

• Trier aretes par poids croissant
• Ajouter arete si ne cree pas cycle
• Utilise union-find pour detecter cycles

Algorithme de Prim :

• Partir d'un sommet
• Ajouter arete de poids min reliant arbre a sommet exterieur
• Repeter jusqu'a tous sommets inclus

Applications :

• Conception de reseaux (electrique, eau, telecoms) a cout minimum
• Clustering

4. Flots dans les Reseaux

Reseau de flot :
Graphe oriente avec capacites sur arcs.

Probleme du flot maximum :
Maximiser flot de la source s vers puits t.

Contraintes :

• Flot ≤ capacite sur chaque arc
• Conservation du flot (entrant = sortant sauf s et t)

Algorithme de Ford-Fulkerson :

• Trouver chemin augmentant (capacite residuelle > 0)
• Augmenter flot le long de ce chemin
• Repeter jusqu'a plus de chemin augmentant

Theoreme flot-max = coupe-min :
Valeur du flot maximal = capacite de la coupe minimale.

Algorithme d'Edmonds-Karp :
Ford-Fulkerson avec BFS pour trouver chemin augmentant.

Complexite : O(VE²)

Applications :

• Reseaux de transport (trafic routier, fluides)
• Reseaux de communication (bande passante)
• Appariement biparti

5. Probleme d'Affectation

Probleme :
Affecter n taches a n agents, minimiser cout total.

Matrice de couts C :
C_ij = cout d'affecter tache j a agent i

Formulation :

Minimiser Σ Σ C_ij x x_ij

Contraintes:
Σ_j x_ij = 1  (chaque agent 1 tache)
Σ_i x_ij = 1  (chaque tache 1 agent)
x_ij ∈ {0,1}

Algorithme hongrois :
Resout en O(n³).

Applications :

• Affectation personnel/postes
• Planification production
• Appariement (dating apps!)

6. Coloration de Graphes

Probleme :
Attribuer couleur a chaque sommet tel que sommets adjacents ont couleurs differentes.

Nombre chromatique χ(G) :
Nombre minimum de couleurs necessaires.

Theoreme des 4 couleurs :
Tout graphe planaire χ ≤ 4.

Algorithmes :

• Glouton (pas optimal mais rapide)
• Recherche exhaustive (exponentiel)

Applications :

• Allocation frequences radio
• Ordonnancement (conflits de ressources)
• Allocation registres (compilateurs)

7. Programmation Lineaire - Formulation

Forme standard :

Maximiser (ou Minimiser) Z = c1*x1 + c2*x2 + ... + cn*xn

Sous contraintes:
a11*x1 + a12*x2 + ... + a1n*xn ≤ b1
a21*x1 + a22*x2 + ... + a2n*xn ≤ b2
...
am1*x1 + am2*x2 + ... + amn*xn ≤ bm

x1, x2, ..., xn ≥ 0

Forme matricielle :

Max c^T x
s.t. Ax ≤ b, x ≥ 0

Region admissible :
Polyedre convexe defini par contraintes.

Theoreme fondamental :
Si solution optimale existe, elle se trouve a un sommet du polyedre.

8. Algorithme du Simplexe

Principe :
Parcours iteratif des sommets du polyedre vers l'optimum.

Etapes :

1. Partir d'un sommet admissible (solution de base)
2. Tester directions ameliorantes
3. Se deplacer vers sommet adjacent ameliorant Z
4. Repeter jusqu'a optimum (aucune direction n'ameliore)

Tableau du simplexe :
Forme tableau pour calculs iteratifs.

Variables d'ecart :
Transformer inegalites en egalites.

Complexite :
Exponentielle au pire cas, mais polynomial en pratique.

9. Dualite

Probleme Primal :

Max c^T x
s.t. Ax ≤ b, x ≥ 0

Probleme Dual :

Min b^T y
s.t. A^T y ≥ c, y ≥ 0

Theoreme de dualite forte :
Si primal a solution optimale x*, dual a solution optimale y* et :

c^T x* = b^T y*

Interpretation economique :

• Primal : production optimale
• Dual : valorisation des ressources (prix d'ombre)

Ecarts complementaires :

Si x_j > 0 alors contrainte duale j saturee
Si y_i > 0 alors contrainte primale i saturee

10. Analyse de Sensibilite

Questions :

• Comment l'optimum varie si on change un parametre (cout, ressource) ?
• Plage de validite de la solution actuelle ?

Prix d'ombre (shadow price) :
Variation de Z si on augmente ressource b_i d'une unite.
= variable duale y_i*

Cout reduit :
Pour variable hors base : combien c_j doit diminuer pour entrer en base.

Plages de variation :

• Coefficients objectif c_j
• Seconds membres b_i

Dans ces plages, solution optimale (base) reste identique.

11. Probleme de Transport

Contexte :
m sources (offres s_i), n destinations (demandes d_j).
Cout c_ij pour transporter de i vers j.

Formulation :

Min Σ_i Σ_j c_ij x x_ij

s.t.
Σ_j x_ij = s_i  (offre source i)
Σ_i x_ij = d_j  (demande destination j)
x_ij ≥ 0

Condition d'existence :
Σ s_i = Σ d_j (offre totale = demande totale)

Methode de resolution :

• Methode du coin nord-ouest (solution initiale)
• Stepping-stone ou MODI pour optimiser

Applications :

• Logistique et distribution
• Planification production multi-sites

12. Programmation Lineaire en Nombres Entiers

PLNE (Programmation Lineaire en Nombres Entiers) :

Max c^T x
s.t. Ax ≤ b, x ≥ 0, x ∈ Z^n

Difficulte :
NP-difficile (pas de methode polynomiale connue).

Methodes de resolution :

Branch and Bound :

• Resoudre relaxation continue (ignorer contrainte entiere)
• Brancher sur variable fractionnaire
• Explorer arbre de decision
• Borner avec solutions entieres trouvees

Coupes (Cutting Planes) :
Ajouter contraintes lineaires eliminant solutions fractionnaires sans enlever solutions entieres.

Methodes heuristiques :
Trouver bonnes solutions (pas necessairement optimales) rapidement.

Programmation 0-1 :
Variables binaires (decisions oui/non).

Applications :

• Planification
• Ordonnancement
• Localisation d'installations
• Sac a dos (knapsack)
• Tournees de vehicules

PARTIE D : PARTIE ANALYTIQUE

Connaissances et competences mobilisees

• Modelisation de problemes reels en graphes ou programmes lineaires
• Comprehension et application d'algorithmes classiques
• Formulation mathematique de problemes d'optimisation
• Utilisation de solveurs (Python, logiciels dedies)
• Interpretation de solutions et analyse de sensibilite
• Evaluation de complexite algorithmique
• Resolution de problemes de transport, affectation, et ordonnancement
• Esprit critique sur pertinence des modeles et limites

Auto-evaluation

Ce cours a ete mathematiquement exigeant mais tres enrichissant. La theorie des graphes offre un langage puissant pour modeliser de nombreux systemes: reseaux, relations, dependances.

Les algorithmes classiques (Dijkstra, Kruskal, Ford-Fulkerson) sont elegants et ont fait leurs preuves. Les comprendre en profondeur (pas juste les appliquer mecaniquement) aide a adapter ou concevoir de nouveaux algorithmes.

La programmation lineaire est un outil d'optimisation extremement puissant. La capacite a formuler un probleme complexe en systeme d'equations lineaires est une competence precieuse. Le simplexe, bien que conceptuellement simple (parcours de sommets), demande rigueur dans les calculs.

L'analyse de sensibilite et la dualite sont des concepts profonds. Comprendre que chaque probleme d'optimisation a un dual avec interpretation economique (prix d'ombre) est fascinant.

La programmation en nombres entiers complexifie drastiquement les problemes. La frontiere entre polynomial (PL continue) et NP-difficile (PLNE) est impressionnante. Cela souligne l'importance des heuristiques et approximations en pratique.

Les applications sont omnipresentes: logistique, telecoms, production, transport, finance. Savoir reconnaitre qu'un probleme industriel peut se modeliser en graphe ou PL est une competence transversale.

L'utilisation de solveurs modernes (comme CPLEX, Gurobi, ou bibliotheques Python) democratise l'optimisation. Mais comprendre la theorie sous-jacente reste essentiel pour formuler correctement, interpreter resultats, et diagnostiquer problemes.

Mon avis

Ce cours est fondamental pour tout ingenieur confronte a des problemes d'optimisation, de planification, ou de gestion de reseaux.

Points forts :

• Equilibre theorie/pratique
• Algorithmes classiques bien expliques
• Applications variees et concretes
• Utilisation d'outils logiciels modernes

Points a ameliorer :

• Plus de temps sur PLNE et heuristiques
• Cas d'etudes industriels de grande echelle
• Programmation non-lineaire (extension naturelle)
• Optimisation multi-objectifs

Reflexions personnelles :

L'optimisation est au coeur de nombreux defis industriels: comment produire plus avec moins de ressources, livrer plus vite a moindre cout, utiliser au mieux l'energie, etc. Les outils mathematiques de ce cours permettent d'aborder ces questions de maniere rigoureuse.

La modelisation est souvent la partie la plus difficile. Transformer un probleme reel confus en modele mathematique propre demande abstraction et simplification intelligente. Un modele trop simple perd en pertinence; trop complexe devient insoluble.

Le fosse entre problemes polynomiaux et NP-difficiles rappelle les limites de l'optimisation exacte. Pour problemes de grande taille ou complexes, les heuristiques et metaheuristiques (algorithmes genetiques, recuit simule, etc.) sont incontournables, meme si elles ne garantissent pas l'optimalite.

La recherche operationnelle est un domaine vaste et actif. Les problemes reels incluent souvent incertitudes, dynamique, contraintes non-lineaires. L'optimisation stochastique, robuste, et en ligne sont des extensions importantes.

Applications professionnelles :

Ces competences sont applicables dans de nombreux secteurs :

• Logistique : routage de vehicules, gestion d'entrepots, supply chain
• Telecommunications : routage, allocation de bande passante
• Energie : optimisation de production, smart grids
• Transport : gestion de trafic, planification de lignes
• Production : ordonnancement, allocation de ressources
• Finance : optimisation de portefeuille
• Sante : planification d'emplois du temps, allocation de ressources hospitalieres

La maitrise de ces outils, couplee a des competences en data science et apprentissage automatique, ouvre des perspectives en data-driven optimization: utiliser donnees massives pour affiner modeles et predictions, puis optimiser en consequence.

Maitriser ces techniques en S8 est essentiel pour tout ingenieur souhaitant concevoir ou ameliorer des systemes efficaces dans un monde toujours plus connecte et complexe.

---

Documents de Cours

---

Cours suivi en 2023-2024 a l'INSA Toulouse, Departement Genie Electrique et Informatique.

Minimize Σ Σ C_ij x x_ij

Constraints:
Σ_j x_ij = 1  (each agent 1 task)
Σ_i x_ij = 1  (each task 1 agent)
x_ij ∈ {0,1}

Maximize (or Minimize) Z = c1*x1 + c2*x2 + ... + cn*xn

Subject to:
a11*x1 + a12*x2 + ... + a1n*xn ≤ b1
a21*x1 + a22*x2 + ... + a2n*xn ≤ b2
...
am1*x1 + am2*x2 + ... + amn*xn ≤ bm

x1, x2, ..., xn ≥ 0

Max c^T x
s.t. Ax ≤ b, x ≥ 0

Max c^T x
s.t. Ax ≤ b, x ≥ 0

Min b^T y
s.t. A^T y ≥ c, y ≥ 0

c^T x* = b^T y*

If x_j > 0 then dual constraint j is tight
If y_i > 0 then primal constraint i is tight

Min Σ_i Σ_j c_ij x x_ij

s.t.
Σ_j x_ij = s_i  (supply at source i)
Σ_i x_ij = d_j  (demand at destination j)
x_ij ≥ 0

Max c^T x
s.t. Ax ≤ b, x ≥ 0, x ∈ Z^n