ENSA- TANGER Année 2019/2020
GIND2
Matière : Outils d’Aide à la Décision Monocritère (OADM)
Application 1 :
Un étudiant en agriculture veut déterminer les quantités de trois types de grains à donner au bétail afin de
satisfaire ses besoins en nutrition au cout minimum. Le tableau suivant donne l’information nécessaire pour ce
problème.
Type de grains nutritifs Maïs Blé Orge Minimum
requis
Protéine (mg/Kg) 10 9 11 20
Calcium (mg/Kg) 50 45 58 70
Fer (mg/Kg) 9 8 7 12
Calories (cal/Kg) 1000 800 850 4000
Coût /Kg 5,5 4,7 5,7
Modéliser le problème sous forme d’un programme linéaire (PL) avec des contraintes inégalités.
Donner une première solution de base.
Application 2 :
Résoudre par la méthode du simplexe le programme linéaire suivant :
⎧ Maximiser z = 8x1 +8 x 2 + 47 x 3
⎪
⎪ sous les contraintes :
⎪
⎨ 4x1 + x 2 + 7 x 3 ≤ 2
⎪ x + 4 x + 10 x ≤ 3
⎪ 1 2 3
⎪
⎩ 1x ≥ 0 , x 2 ≥ 0 , x3 ≥ 0
Application 3 :
Résoudre le problème suivant par la méthode de Branch and bound :
Application 4 :
Une compagnie considère cinq développements immobiliers. Chaque développement peut être fait au plus
une fois. Le profit estimé et le capital requis pour chaque développement sont représentés par le tableau
suivant (les montants sont en millions de dollars) :
Le capital total disponible pour effectuer ces développements est de 20 millions de dollars. De plus :
1. On ne peut faire à la fois les développements 1 et 2;
2. On ne peut faire à la fois les développements 3 et 4;
3. Le développement 5 ne peut être fait que si au moins un des développements 1 et 2 a été effectué.
L’objectif est d’identifier la combinaison de développements immobiliers qui maximise le profit total
estimé.
Formulez ce problème à l’aide d’un modèle de programmation à variables binaires (variables : !" = 1, si on
choisit le développement i ; 0, sinon.
Application 5 :
On considère le problème suivant :
Localiser des stations d’incendie dans six villes ( de S1 à S6, une station par ville).
Installer le moins possible.
Pouvoir atteindre chaque ville en moins de 15 minutes à partir d’au moins une station.
Voici le Tableau des temps de trajet :
Station S1 S2 S3 S4 S5 S6
S1 10 20 30 30 20
S2 10 25 35 20 10
S3 20 25 15 30 20
S4 30 35 15 15 25
S5 30 20 30 15 14
S6 20 10 20 25 14
Modéliser ce problème sous forme d’un programme linéaire à variables binaires.
Donner la solution optimale en utilisant Solveur-Excel.
Application 6 :
Une compagnie aérienne dispose d’un tableau ci-dessus comportant 11 vols et 12 séquences de vols (suite de
vols) ainsi que le coût associé à chaque séquence de vols:
Séq_vol 1 2 3 4 5 6 7 8 9 10 11 12
vol
1 1 1 1 1
2 1 1 1 1
3 1 1 1 1
4 1 1 1 1 1
5 1 1 1 1
6 1 1 1
7 1 1 1 1 1
8 1 1 1 1
9 1 1 1
10 1 1 1 1
11 1 1 1 1 1
coût 2 3 4 6 7 5 7 8 9 9 8 9
La compagnie veut respecter les contraintes suivantes :
ü Minimiser le coût d’affectation
ü Assurer le service sur chacun de ses vols
ü Affecter trois équipages pour les 12 séquences de vols
1. Modéliser le problème sous forme d’un PL à variables binaires
2. Donner la solution par Solveur Excel
(Considérer les variables xi ( i=1 à 12) qui vaut 1 si on affecte un équipage à la séquence de vols « i », 0 sinon.
Application 7 :
Une compagnie doit transporter du gravier vers trois sites de construction, S1, S2 et S3 ; La compagnie achète
ce gravier de deux fournisseurs F1 et F2. La compagnie devra louer des camions pour assurer le transport du
gravier des fournisseurs vers les sites de construction. Chaque camion coûte 50€ et peut transporter jusqu’à 5
tonnes du gravier.
Les autres données du problème sont représentées dans le tableau suivant, qui indique :
• Pour chaque site de construction et chaque fournisseur, le prix (en €) de chargement par tonne
• Pour chaque fournisseur, l’offre, soit le nombre de tonnes de gravier disponibles
• Pour site de construction, la demande, soit le nombre de tonnes de gravier demandées
Sites S1 S2 S3 Offre
Fournisseurs (tonnes)
F1 130 160 150 18
F2 180 150 160 14
Demandes 10 5 10
(tonnes)
Le problème consiste à minimiser le coût total afin de transporter le gravier des fournisseurs vers les sites de
construction.
On note par :
!"# le nombre de tonnes de gravier transportées entre le fournisseur !" et le site !" .
"#$ le nombre de camions utilisés pour transporter du gravier entre le fournisseur !" et le site "#
1. Modéliser le problème sous forme d’un PL en nombres entiers (en fonction de !"# %& '"# )
2. Donner la solution par Solveur-Excel.
