News

RO

En Bref

J'enseigne une introduction à la Recherche opérationnelle en 3ème de licence Miage à Nanterre. Ce cours est pour les apprentis comme pour les classiques. Claire Hanen fait en M1 L'optimisation Combinatoire, c'est à dire la suite. Le programme est somme toute assez classique.

Le grand classique : la programmation linéaire, en insistant tout d'abord sur la modélisation, puis sur l'algorithme du simplexe. Un peu de graphe, avec les flots, puis l'affectation linéaire (algorithme hongrois)

La partie programmation linéaire est définitivement fait du point de vu informaticien, ou plus particulièrement algorihmique. La partie matheuse est vraiment réduite à sa plus simple expression. Le public, des étudiants de L3 Miage manquent de base en Math pour suivre un cours plus complet sur les aspects théoriques matheux de la programmation linéaire.

Cours téléchargeables

Exemple de Simplexe

5 4 3 0 0 0 0

Le problème initial sous sa forme normale

  X1 X2 X3 E1 E2 E3 >=
C1 2,00 3,00 1,00 1,00 0,00 0,00 5,00
C2 4,00 1,00 2,00 0,00 1,00 0,00 11,00
C3 3,00 4,00 2,00 0,00 0,00 1,00 8,00
Max 5,00 4,00 3,00 0,00 0,00 0,00 0,00

Résolution

Le pivot est en 1,1

  X1 X2 X3 E1 E2 E3 >=
C1 2,00 3,00 1,00 1,00 0,00 0,00 5,00
C2 4,00 1,00 2,00 0,00 1,00 0,00 11,00
C3 3,00 4,00 2,00 0,00 0,00 1,00 8,00
Max 5,00 4,00 3,00 0,00 0,00 0,00 0,00

Après la normalisation du pivot, et des pivotages réalisés sur les autre lignes, on a

  X1 X2 X3 E1 E2 E3 >=
C1 1,00 1,50 0,50 0,50 0,00 0,00 2,50
C2 0,00 -5,00 0,00 -2,00 1,00 0,00 1,00
C3 0,00 -0,50 0,50 -1,50 0,00 1,00 0,50
Max 0,00 -3,50 0,50 -2,50 0,00 0,00 -12,50

Le pivot est en 3,3

  X1 X2 X3 E1 E2 E3 >=
C1 1,00 1,50 0,50 0,50 0,00 0,00 2,50
C2 0,00 -5,00 0,00 -2,00 1,00 0,00 1,00
C3 0,00 -0,50 0,50 -1,50 0,00 1,00 0,50
Max 0,00 -3,50 0,50 -2,50 0,00 0,00 -12,50

Après la normalisation du pivot, et des pivotages réalisés sur les autre lignes, on a

  X1 X2 X3 E1 E2 E3 >=
C1 1,00 2,00 0,00 2,00 0,00 -1,00 2,00
C2 0,00 -5,00 0,00 -2,00 1,00 0,00 1,00
C3 0,00 -1,00 1,00 -3,00 0,00 2,00 1,00
Max 0,00 -3,00 0,00 -1,00 0,00 -1,00 -13,00

Finalement, les coéfficients de la dernière ligne sont tous négatifs ou nuls : C'est fini