PROGRAMMATION LINÉAIRE
PARTIE II
[Link]@[Link] Chapitre 1: Formulation d’un programme linéaire
Citation
2
Euler: « Il n’y a rien dans le monde qui ne
se réalise sans la volonté de minimiser ou
maximiser quelque chose »
PL : Modélisation
Processus d’optimisation
3
Modélisation
Problème Modèle
Mise en œuvre Résolution
Décision Solution
Interprétation
PL : Modélisation
Objectifs du chapitre 1
4
À la fin de ce chapitre, l’étudiant sera capable de :
Formuler un programme linéaire modélisant un problème
d’optimisation:
Définir les variables de décisions et leurs natures
Définir la fonction-objectif
Définir les contraintes liés au PL
Etablir les relations entre les éléments
Classifier le type du problème.
PL : Modélisation
Plan du cours
5
Chapitre 1 : Formulation d’un programme linéaire
Chapitre 2 : Résolution graphique
Chapitre 3 : Résolution algébrique
Chapitre 4 : La Méthode de Simplexe
Chapitre 5 : Dualité
PL : Modélisation
6 Partie II: Classification
Dans ce chapitre on se focalisera sur la
modélisation.
La résolution sera traitée à partir du chapitre 2.
PL : Modélisation
Variables de décision et nature du
7
PL
Les variables de décision représentent, comme leurs noms l’indiquent,
les décisions à prendre afin de satisfaire le ou les objectifs. La
nature, du programme linéaire, est liée à la nature des variables de
décision.
On parlera alors de quatre classes de problèmes linéaires.
Les variables de décision peuvent être :
1- Continues : le programme linéaire est dit continu.
2- Entières : Le programme linéaire est dit en nombre entier(PLNE).
3- Binaires : le programme linéaire est dit binaire.
4- Mixtes : le programme linéaire est dit mixte.
PL : Modélisation
Exemple1: de problème de sac à dos
8
PL : Modélisation
Modélisation du problème de sac à dos
9
PL : Modélisation
Exemple2: Sélection de projets
10
5 projets doivent être évalués sur 3 ans. Etant
donné le coût de chaque projet pour chaque
année et le profit obtenu par l’exécution d’un
projet.
Décider quels projets exécuter sans dépasser
le budget disponible pour chaque année.
PL : Modélisation
Données des projets
11
Coût par année Profit
Projet 1 2 3
1 5 1 8 20
2 4 7 10 40
3 3 9 2 20
4 7 4 1 15
5 8 6 10 30
Budget 25 25 25
PL : Modélisation
Exercice 1:Problème de couverture
12
Problématique Schéma descriptif
Le département de sécurité
d’un campus veut installer
des téléphones d’urgence.
Chaque rue doit être servie
par un téléphone, le but
étant de minimiser le
nombre de téléphones à
installer .
(installation aux carrefours)
PL : Modélisation
Exercice 2:Problème de couverture
13
Formuler sans le résoudre le programme. Les temps (en minutes)
Il y a six villes dans la région
R. La région doit déterminer
où construire les casernes de
pompiers. La région veut
construire le nombre
minimum de casernes de
pompiers et s'assurer qu'au
moins une caserne de
pompiers est près de 15
minutes de chaque ville. Les
temps (en minutes) requis,
pour conduire entre les 6
villes, sont les suivants:
PL : Modélisation
Exercice 3:Problème avec coûts fixes
14
3 compagnies de téléphone offrent des tarifs différents pour les
communications longue distance.
Compagnie Abonnement Prix / minute
1 16 0.25
2 25 0.21
3 18 0.22
On veut trouver le plan d’abonnement optimal pour 200
minutes de communication / mois.
1. Résoudre le problème à la main.
2. Modéliser le problème sous forme de programme linéaire
PLNE 25/02/2017
Problème 1: PL et logique
15
Soient P1,...,Pn des propositions logiques, chacune
étant vraie ou fausse.
En introduisant des variables binaires, représenter les
relations suivantes par des contraintes linéaires :
1. P1 est vraie.
2. Toutes les propositions sont vraies.
3. Au moins k propositions sont vraies.
4. Si P1 est vraie, alors P2 est vraie.
5. P1 et P2 sont équivalentes.
6. Si P1 ou P2 est vraie, alors au plus deux des
propositions P3,...,Pn sont vraies.
PL : Modélisation