Travaux dirigés
Recherche opérationnelle et Optimisation Discrète
Document also available in PDF, Postscript, DVI, pure text, LaTeX and LyX.
TD 2
Exercice 1
Un bûcheron a 100 hectares de bois de feuillus. Couper un hectare
de bois et laisser la zone se régénérer naturellement coûte 10 kF
par hectares, et rapporte 50 kF. Alternativement, couper un hectare
de bois, et replanter avec des pins coûte 50 kF par hectares, et rapporte
à terme 120 kF. Sachant que le bûcheron n'a que 4000 kF en caisse
au début de l'opération, déterminer la meilleure stratégie à adopter
et le profit escomptable.
Exercice 2
``Faites-le vous-même''. Choisir un sous-domaine du premier quadrant
du plan défini comme l'intersection d'un certain nombre de demi-plans,
et choisir une direction d'optimisation. Donner les équations de ces
demi-plans, ainsi que l'expression de la fonction objective correspondant
à cette direction d'optimisation. Calculer, au moyen de l'algorithme
du simplexe, le point du domaine maximisant la fonction objective.
Réitérer en choisissant des domaines qui donnent des programmes linéaires
infaisables, non bornés, présentant des dégénérescences ou nécessitant
l'utilisation du simplexe en deux phases.
TD 3
Exercice 3
Vous êtes chargé de la planification d'un chantier qui nécessite le
traitement de 9 tâches décrites dans le tableau suivant. Il peut
être nécessaire, pour traiter une tâche donnée, (par ex. F) que
le traitement d'autres tâches soit terminé (ici C et E). De
plus, on peut choisir d'accélérer le traitement d'une tâche donnée,
moyennant un surcoût par jours de réduction; le nombre maximum de
jours de réduction et le sûrcout dépendent de la tâche.
| Tâches |
Dépendences |
Durée (jours) |
Réd. max (jours) |
Coût de réd (kEuro/jours) |
| A |
|
2 |
1 |
9 |
| B |
A |
7 |
2 |
2 |
| C |
D |
4 |
3 |
1 |
| D |
|
2 |
0 |
|
| E |
A |
3 |
1 |
8 |
| F |
C,E |
2 |
1 |
5 |
| G |
A,F |
3 |
1 |
7 |
| H |
F,D |
3 |
2 |
6 |
| I |
B,H |
3 |
0 |
|
Quelle est la durée minimale du chantier sans surcoût ?
Peut-on effectuer le chantier en moins de 8 jours ?
Note: pour ces deux premières questions, la programmation linéaire
n'est pas vraiment indispensable; on peut les résoudre «à la main».
Par contre, pour les questions suivantes la programmation linéaire
devient vraiment utile. C'est pourquoi je recommande, à titre d'exercice
préliminaire, de modéliser quand-même ces questions précédentes par
des programmes linéaires.
Quelle est le coût minimal pour finir le chantier en 10 jours ?
Quelle est la durée minimale du chantier avec un surcoût de 15 au
plus ?
Pour chacune de ces questions, on essaiera de trouver les programmes
linéaires les plus simples possibles.
TD4
Exercice 4
Utiliser le théorème de dualité pour vérifier les solutions des problèmes
de programmation linéaire que vous avez résolu jusqu'ici. Faites le
d'abord en utilisant la donnée du dernier dictionnaire, et ensuite
sans cette donnée, mais en utilisant le théorème de complémentarité
des variables d'écarts.
Exercice 5
(suite de la fiche 2) fUn bûcheron a 100 hectares de bois de feuillus.
Couper un hectare de bois et laisser la zone se régénérer naturellement
coûte 10 kF par hectares, et rapporte 50 kF. Alternativement, couper
un hectare de bois, et replanter avec des pins coûte 50 kF par hectares,
et rapporte à terme 120 kF. Sachant que le bûcheron n'a que 4000 kF
en caisse au début de l'opération, déterminer la meilleure stratégie
à adopter et le profit escomptable.
Maintenant, le bûcheron a aussi l'option d'emprunter pour augmenter
son capital initial, et ce pour un taux d'intérêt total de S%
sur la durée de l'opération. Alternativement, il peut décider d'investir
son capital dans une autre activité rapportant T% sur la durée
de l'opération. Déterminer, selon les valeurs de S et T, la
meilleure stratégie à adopter.
Exercice 6
Pouvez vous interpréter les conditions de complémentarité des variables
d'écart en termes économiques ?
TD 5: Combinatoire polyhédrale I
L'objectif de ce TD est d'utiliser la programmation linéaire pour
résoudre un problème d'optimisation discrète.
Problem 0.0.1
Problème d'assignement de cours entre plusieurs professeurs.
Dans le département de mathématiques d'une université aux USA, l'évaluation
des enseignants par les étudiants a donné au cours des derniers semestres
les résultats suivants:
| CoursProfesseur |
Bill |
Yu |
Luis |
John |
Hugh |
| Calculus 1 |
3 |
4 |
2,3 |
2,9 |
2,8 |
| Differential Equations |
2,25 |
3,2 |
3,7 |
1,9 |
4,4 |
| Statistics |
2,6 |
3,7 |
4,5 |
2.7 |
3,1 |
| Calculus 2 |
3,9 |
4,1 |
2,6 |
3,9 |
2,4 |
| Discrete maths |
2,8 |
2,8 |
3,5 |
3,4 |
4,2 |
Dans un semestre, chaque cours est enseigné par un professeur, et
chaque professeur enseigne un cours. Le chef du département veut répartir
les cours du prochain semestre entre les professeurs de façon à exploiter
au mieux leurs talents respectifs (ou minimiser la grogne des étudiants,
au choix...). Il décide de prendre comme mesure de la qualité
d'une répartition la moyenne sur chaque cours de la note du professeur
qui l'enseigne.
Chaque assignement correspond à une permutation sigma de { 1,···,5}
(le cours i est enseigné par le prof sigma(i)). Pour résoudre
ce problème, on recherche donc parmi les 5!=120 permutations de
{ 1,···,5} celle qui maximise la fonction objective:
où A est la matrice des notes ci-dessus.
Notez que la fonction objective est linéaire. On va donc essayer de
considérer les permutations comme points extrémaux d'un convexe.
Exercice 7
On peut représenter une permutation sigma de { 1,...,n}
par une matrice M(sigma) telle que M(sigma)i,sigma(i)=1
et M(sigma)i,j=0 ailleurs. Déterminer pour n=2 l'enveloppe
convexe de ces matrices.
Définition 1
Une matrice X=[xij] de taille n× n est doublement
stochastique
si les coefficients xij sont positifs et si la
somme des coefficients sur chaque ligne et chaque colonne vaut 1:
|
|
[
[
[
[ |
| 0,5 |
0,2 |
0,3 |
| 0,01 |
0,7 |
0,29 |
| 0,49 |
0,1 |
0,41 |
|
]
]
]
] |
. |
Exercice 8
Montrer que les matrices de permutations sont les matrices doublement
stochastiques à coeffs entiers.
Montrer que toute matrice dans l'enveloppe convexe des matrices de
permutations est doublement stochastique.
Théorème 1
(Birkhoff-Von Neumann) L'ensemble des matrices doublement stochastiques
est l'enveloppe convexe des matrices de permutations.
Exercice 9
Écrire la matrice doublement stochastique ci-dessus comme combinaison
linéaire convexe de matrices de permutations.
Lemme 1
Pour toute matrice X doublement stochastique, on peut trouver une
matrice de permutation Y de façon à ce que si xij=0 alors
yij=0.
Exercice 10
L'objectif de cet exercice est de démontrer le lemme:
-
Mettre en équations les contraintes que doivent vérifier les coordonnées
yij de Y.
- Définir un programme linéaire P en relâchant la contrainte yijappartient à{ 0,1}
en 0<= yij<=1.
- Montrer que P est faisable.
- Montrer que toutes solution basique faisable est à coordonnées 0,1.
Pour cela, on pourra par exemple montrer que pour chaque i il y
a exactement une variable xij basique, et de même pour chaque
j.
- Conclure
En fait, la propriété utilisée dans la démonstration de ce lemme est
un cas particulier d'un théorème beaucoup plus général, dit théorème
d'intégralité, qui garanti l'existence de solutions entières pour
une grande classe de programmes linéaires: les problèmes de transports.
Exercice 11
Expliquer comment on pourrait utiliser la programmation linéaire pour
résoudre le problème d'assignement des cours/profs.
TD 6: Convexité
Définition 0.0.2
On appelle inconsistant un système d'équations et d'inéquations
si l'on peut déduire de l'existence d'une solution de ce système une
absurdité comme 0=1 ou 0>=1.
Exemple 0.0.3
Le système x,y>=0 et x+y<=-1 est inconsistant.
Theorem 0.0.4
(Tücker) Un système d'équations et d'inéquations est inconsistant
si, et seulement si, il n'a pas de solutions.
Theorem 0.0.5
(Farkas) Soit (v1,...,vn) une famille de n vecteurs
de Rm, et b un autre vecteur de Rm. Alors soit b
est dans le cone engendré par (v1,...,vn), soit il existe
un hyperplan qui les sépare.
Exercice 12
Démontrer ces deux théorèmes successivement en utilisant le théorème
de dualité de la programmation linéaire.
TD 7: Jeux matriciels
0.0.1 Le jeu de Morra
Règles du jeu (pour deux personnes, Louis et Claire).
À chaque tour, chaque joueur cache un ou deux pions, et essaye de
parier, à voix haute, combien de pions l'autre joueur a caché. Si
un seul des joueurs a parié la bonne solution, son score augmente
d'autant de point qu'il y a de pions cachés en tout; le score de l'autre
joueur diminue du même nombre de points. Sinon, rien ne ce passe.
Par exemple, si Claire cache 2 pions et parie 1 tandis que Louis cache
2 pions et parie 2, Louis gagne 4 points et Claire en perds 4.
Le but est de trouver une stratégie gagnante.
Exercice 13
Jouez!
À chaque étape, chaque joueur a le choix entre 4 actions:
-
[1,1]: Cacher 1 pion, parier 1 pion
- [1,2]: Cacher 1 pion, parier 2 pions
- [2,1]: Cacher 2 pions, parier 1 pion
- [2,2]: Cacher 2 pions, parier 2 pions
Chacune de ces options est appelée stratégie pure.
Problème 1
Est-ce que suivre une stratégie pure est une stratégie raisonnable
?
Quelles autres stratégies ?
Exercice 14
Claire et Louis font un long match.
Stratégie de Claire: inconnue; elle a joué c1 fois [1,1],
c2 fois [1,2], c3 fois [2,1] et c4 fois
[2,2].
Stratégie de Louis: lancer une pièce à chaque tour pour choisir entre
[1,2] et [2,1].
Calculer les gains et pertes de Claire et Louis.
Résultat:
Gain de Louis: (c1-c4)/2.
Perte moyenne maximale à chaque tour: 1/2.
Une stratégie aléatoire de ce type est appellée stratégie mixte.
Exercice 15
Généralisation: on suppose que Louis se fixe une stratégie mixte.
Caractérisez la meilleure stratégie de contre-attaque de Claire, c'est-à-dire
celle qui minimise le gain moyen de Louis.
Problem 0.0.6
Comment caractériser la meilleure stratégie mixte pour Louis ?
0.0.2 Jeux matriciels
Chaque matrice A=(aij) définit un jeu. À chaque tour, le joueur
par Ligne (Louis) choisit une ligne i parmi les m lignes, et
le joueur par Colonnes (Claire) choisit une colonne j parmi les
n colonnes.
Le gain pour Louis est le coefficient aij:
-
Si aij>=0, Louis reçoit aij de Claire
- Si aij<=0, Claire reçoit -aij de Louis
- Si aij=0, il n'y a pas d'échange
Exercice 16
Écrire la matrice pour le jeu de Morra.
Écrire la matrice pour le jeu papier/ciseaux/caillou/puits.
Exercice 17
Dans un long match, Louis adopte une stratégie mixte, en choisissant
au hasard la stratégie pure i avec une probabilité fixée xi.
Claire joue selon une stratégie de son choix: à la fin du match, elle
a joué cj fois la stratégie pure j.
On note N:=sumici et yi:=ci/N. Calculer
le gain moyen par tour pour Louis.
Définition 2
Les vecteurs x:=(x1,...,xm) et y:=(y1,...,yn)
sont dit stochastiques
:
xi>=0 et x1+···+xm=1.
On considère x:=[x1,...,xm] comme un vecteur ligne, et
y:=[y1,...,yn]T comme un vecteur colonne, de façon
à pouvoir écrire commodément le gain de Louis sous la forme:
xAy.
Exercice 18
Louis adopte une stratégie mixte donnée. Caractériser le gain au pire
pour Louis.
Ici, x est constant. Cela peut se mettre sous la forme du programme
linéaire en y:
Si Louis veut une bonne garantie pour maintenir ces gains hauts (ou
ses pertes faibles), il peut chercher une stratégie mixte qui maximise
la quantité miny xAy.
On appelle une telle stratégie mixte optimale; son gain moyen
vaut
Problem 0.0.7
Est-ce que la stratégie mixte optimale est la meilleure stratégie
?
Problem 0.0.8
Comment calculer la stratégie optimale ?
Tel quel, le problème ne se met pas sous la forme d'un programme linéaire.
On avait vu une astuce pour se débarasser d'un min dans les contraintes;
celle ci ne s'applique cependant que lorsque l'on prend le min
d'un nombre fini d'expressions, alors qu'ici il y en a a priori autant
que de choix de y.
Proposition 1
On peut toujours atteindre la quantité miny xAy avec
un y de la forme:
(0,...,0,1,0,...,0).
Autrement dit:
Interprétation ?
Proof:
Clairement, pour une stratégie pure j donnée:
Maintenant, supposons que j0 minimise sumi=1maij0xi:
|
|
|
aijxi>= |
|
a |
|
xi pour j=1,...,n. |
Alors, si y:=(y1,...,yn) est un vecteur stochastique,
on a:
|
xAy= |
|
|
xiaijyj= |
|
yj |
(
(
(
(
(
(
( |
|
aijxi |
)
)
)
)
)
)
) |
>= |
|
yj |
(
(
(
(
(
(
( |
|
a |
|
xi |
)
)
)
)
)
)
) |
= |
(
(
(
(
(
(
( |
|
yj |
)
)
)
)
)
)
) |
(
(
(
(
(
(
( |
|
a |
|
xi |
)
)
)
)
)
)
) |
. |
Donc, comme voulu,
QED
Exercice 19
Formuler le problème de trouver une stratégie mixte optimale pour
Louis comme un programme linéaire.
Supposons que Claire veuille aussi adopter une stratégie mixte optimale.
Formuler de même son problème sous forme de programme linéaire.
Théorème 2
(Théorème minimax). Pour toute matrice m× n A, il existe
un vecteur stochastique x* de longueur m, et un vecteur stochastique
y* de longueur n tel que:
où le minimum est pris sur tout les vecteurs stochastiques y de
longueur n, et le maximum est pris sur tout les vecteurs stochastiques
x de longueur m.
Interprétation ?
Proof:
Application immédiate du théorème de dualité.
QED
Définition 3
Si A est interprétée comme un jeu, la valeur du jeu
est
la quantité:
Exercice 1
Calculer la valeur du jeu de Morra et du jeu caillou/pierre/ciseaux/puit.
D'où vient cette particularité ?
Stratégie cachée / stratégie révélée
Problem 0.0.9
Est-ce que révéler sa stratégie à son adversaire, diminue l'espérance
de gain?
0.0.3 Morra modifié
Il n'est pas très pratique de devoir annoncer simultanément les paris.
Problem 0.0.10
Est-ce que le jeu est modifié si Claire annonce toujours son pari
en premier ?
Exercice 2
Faire l'analyse de ce nouveau jeu.
Travaux dirigés
Recherche opérationnelle et Optimisation Discrète
Travaux dirigés, licence /
UCBL, Maîtrise MIM, Recherche Opérationnelle /
Nicolas M. Thiéry
Last modified: Fri Jun 25 12:06:36 2004