Exos élimination de Fourier-Motzkin
Exo 1
Déterminer par emploi de l'algorithme
de Fourier-Motzkin la satisfiabilité du système suivant sur
les rationnels.
- 0 ≤ x
- 0 ≤ y
- -x -y ≤ 2
- -x+y ≤ 3
- x+2y ≤ 8
Donner une interprétation géométrique des étapes de cet algorithme.
Exo 2
- Déterminer graphiquement une solution du système de l'exo 1
qui minimise la fonction
-2x-y.
- Utiliser l'algorithme
de Fourier-Motzkin en ajoutant
l'égalité
z = -2x-y puis en éliminant x et y. Quel est le minimum de z ?
Exo 3
Déterminer graphiquement puis algébriquement via Fourier-Motzkin
la projection des solutions du système suivant sur l'axe des x
puis sur l'axe des y.
Illustrer comment trouver effectivement via Fourier-Motzkin une solution du système.
- x ≥ 0
- x+2y ≤ 6
- x+y ≥2
- x-y ≤3
- y ≥0
Exo 4
Dans les rationnels, résoudre via Fourier-Motzkin puis graphiquement :
- max z = 5x+y
- x ≥ 0
- y ≥ 1
- 2x+3y ≤ 6
- 2x+y ≥ 5
Exo 5
- Comment traiter les équations au sein d'inéquations via Fourier-Motzkin ?
- Généraliser l'algorithme de Fourier-Motzkin pour inclure le traitement
des inégalités strictes.
Fred Mesnard
