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 :

Cours\Professeur  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 σ de {1, ⋯, 5} (le cours i est enseigné par le prof σ(i)). Pour résoudre ce problème, on recherche donc parmi les 5! = 120 permutations de {1, ⋯, 5} celle qui maximise la fonction objective :

z = ∑_{i} A_{i,σ(i)},

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 σ de {1, …, n} par une matrice M(σ) telle que M(σ)_{i,σ(i)} = 1 et M(σ)_{i,j} = 0 ailleurs. Déterminer pour n = 2 l’enveloppe convexe de ces matrices.

Définition. Une matrice X = [x_{ij}] de taille n × n est doublement stochastique si les coefficients x_{ij} sont positifs et si la somme des coefficients sur chaque ligne et chaque colonne vaut 1 :

[ \begin{matrix}0, 5 & 0, 2 & 0, 3 \\ 0, 01 & 0, 7 & 0, 29 \\ 0, 49 & 0, 1 & 0, 41 \end{matrix} ] .

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. (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. Pour toute matrice X doublement stochastique, on peut trouver une matrice de permutation Y de façon à ce que si x_{ij} = 0 alors y_{ij} = 0.

Exercice 10. L’objectif de cet exercice est de démontrer le lemme :

(1) Mettre en équations les contraintes que doivent vérifier les coordonnées y_{ij} de Y.

(2) Définir un programme linéaire P en relâchant la contrainte y_{ij} ∈ {0, 1} en 0 ≤ y_{ij} ≤ 1.

(3) Montrer que P est faisable.

(4) 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 x_{ij} basique, et de même pour chaque j.

(5) 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 (v_{1}, …, v_{n}) une famille de n vecteurs de ℝ^{m}, et b un autre vecteur de ℝ^{m}. Alors soit b est dans le cone engendré par (v_{1}, …, v_{n}), 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. 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é c_{1} fois [1,1], c_{2} fois [1,2], c_{3} fois [2,1] et c_{4} 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 : (c_{1} − c_{4})/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 = (a_{ij}) 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 a_{ij} :

– Si a_{ij} ≥ 0, Louis reçoit a_{ij} de Claire

– Si a_{ij} ≤ 0, Claire reçoit −a_{ij} de Louis

– Si a_{ij} = 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 x_{i}. Claire joue selon une stratégie de son choix : à la fin du match, elle a joué c_{j} fois la stratégie pure j. On note N := ∑_{i} c_{i} et y_{i} := \frac{c_{i}}{N}. Calculer le gain moyen par tour pour Louis.

Définition. Les vecteurs x := (x_{1}, …, x_{m}) et y := (y_{1}, …, y_{n}) sont dit stochastiques :

x_{i} ≥ 0 et x_{1} + ⋯ + x_{m} = 1.

On considère x := [x_{1}, …, x_{m}] comme un vecteur ligne, et y := [y_{1}, …, y_{n}]^{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 :

min_{y} xAy

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é min_{y} xAy. On appelle une telle stratégie mixte optimale ; son gain moyen vaut

max_{x} min_{y} xAy

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. On peut toujours atteindre la quantité min_{y} xAy avec un y de la forme :

(0, …, 0, 1, 0, …, 0).

Autrement dit :

min_{y} xAy = min_{j} ∑_{i=1}^{m} a_{ij}x_{i}.

Interprétation ?

Proof. Clairement, pour une stratégie pure j donnée :

min_{y} xAy ≤ ∑_{i=1}^{m} a_{ij}x_{i}.

Maintenant, supposons que j_{0} minimise ∑_{i=1}^{m} a_{ij_{0}}x_{i} :

∑_{i=1}^{m} a_{ij}x_{i} ≥ ∑_{i=1}^{m} a_{ij_{0}}x_{i} pour j = 1, …, n.

Alors, si y := (y_{1}, …, y_{n}) est un vecteur stochastique, on a :

xAy = ∑_{j=1}^{n} ∑_{i=1}^{m} x_{i}a_{ij}y_{j} = ∑_{j=1}^{n} y_{j} (∑_{i=1}^{m} a_{ij}x_{i}) ≥ ∑_{j=1}^{n} y_{j} (∑_{i=1}^{m} a_{ij_{0}}x_{i}) = (∑_{j=1}^{n} y_{j}) (∑_{i=1}^{m} a_{ij_{0}}x_{i}) .

Donc, comme voulu,

xAy ≥ ∑_{i=1}^{m} a_{ij_{0}}x_{i}

□

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. (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 :

min_{y} x^{∗}Ay = max_{x} xAy^{∗},

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é. □

Définition. Si A est interprétée comme un jeu, la valeur du jeu est la quantité :

min_{y} x^{∗}Ay = max_{x} xAy^{∗}.

Exercice. Calculer la valeur du jeu de Morra et du jeu caillou/pierre/ciseaux/puit.

D’où vient cette particularité ?

0.0.2.1. 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. Faire l’analyse de ce nouveau jeu.