%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[frenchb]{amsbook}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{a4wide}
\setlength\parskip{\smallskipamount}
\setlength\parindent{0pt}
\usepackage{amssymb}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \numberwithin{section}{chapter}
 \theoremstyle{plain}    
 \newtheorem{thm}{Theorem}[section]
 \numberwithin{equation}{section} %% Comment out for sequentially-numbered
 \numberwithin{figure}{section} %% Comment out for sequentially-numbered
 \theoremstyle{definition}
  \newtheorem{xca}{Exercice}
 \theoremstyle{definition}
  \newtheorem{problem}[thm]{Problem}
 \theoremstyle{definition}
 \newtheorem*{defn*}{Définition}
 \theoremstyle{plain}    
 \newtheorem*{thm*}{Théorème} 
 \theoremstyle{plain}    
 \newtheorem*{lem*}{Lemme} %%Delete [thm] to re-start numbering
 \theoremstyle{definition}
 \newtheorem{defn}[thm]{Définition}
 \theoremstyle{definition}
  \newtheorem{example}[thm]{Exemple}
 \theoremstyle{definition}
  \newtheorem*{problem*}{Problème}
 \theoremstyle{plain}    
 \newtheorem*{prop*}{Proposition} 
 \theoremstyle{definition}
  \newtheorem*{xca*}{Exercice}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\usepackage{hyperref}
\usepackage[english,francais]{babel}
\makeatletter
% Yucky bugware to make hyperref and babel[francais] work together
\def\url#1{{\selectlanguage{english}\hyper@normalise\url@{#1}}}
\def\href#1#2{{\selectlanguage{english}\hyper@normalise\href@{#1}{#2}}}
\makeatother
\newcommand{\solution}{ \vspace{2cm}}

\usepackage[english,francais]{babel}
\makeatother
\begin{document}

\chapter*{TD 2}

\begin{xca}
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.
\end{xca}


\begin{xca}
{}``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.
\end{xca}

\chapter*{TD 3}

\begin{xca}
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.

\begin{tabular}{|c|c|c|c|c|}
\hline 
Tâches&
Dépendences&
Durée (jours)&
Réd. max (jours)&
Coût de réd (kEuro/jours)\tabularnewline
\hline
\hline 
A&
&
2&
1&
9\tabularnewline
\hline 
B&
A&
7&
2&
2\tabularnewline
\hline 
C&
D&
4&
3&
1\tabularnewline
\hline 
D&
&
2&
0&
\tabularnewline
\hline 
E&
A&
3&
1&
8\tabularnewline
\hline 
F&
C,E&
2&
1&
5\tabularnewline
\hline 
G&
A,F&
3&
1&
7\tabularnewline
\hline 
H&
F,D&
3&
2&
6\tabularnewline
\hline 
I&
B,H&
3&
0&
\tabularnewline
\hline
\end{tabular}

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.
\end{xca}

\chapter*{TD4}

\begin{xca}
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.
\end{xca}
%

\begin{xca}
(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.
\end{xca}
%

\begin{xca}
Pouvez vous interpréter les conditions de complémentarité des variables
d'écart en termes économiques ?
\end{xca}

\chapter*{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.

\begin{problem}
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:

\begin{tabular}{|c|c|c|c|c|c|}
\hline 
Cours\textbackslash{}Professeur&
Bill&
Yu&
Luis&
John&
Hugh\tabularnewline
\hline
\hline 
Calculus 1&
3&
4&
2,3&
2,9&
2,8\tabularnewline
\hline 
Differential Equations&
2,25&
3,2&
3,7&
1,9&
4,4\tabularnewline
\hline 
Statistics&
2,6&
3,7&
4,5&
2.7&
3,1\tabularnewline
\hline 
Calculus 2&
3,9&
4,1&
2,6&
3,9&
2,4\tabularnewline
\hline 
Discrete maths&
2,8&
2,8&
3,5&
3,4&
4,2\tabularnewline
\hline
\end{tabular}

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\ldots{}). 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.
\end{problem}
Chaque assignement correspond à une permutation $\sigma$ de $\left\{ 1,\cdots,5\right\} $
(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
$\left\{ 1,\cdots,5\right\} $ celle qui maximise la fonction objective:
\[
z=\sum_{i}\textrm{ }A_{i,\sigma(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.

\begin{xca}
On peut représenter une permutation $\sigma$ de $\left\{ 1,\ldots,n\right\} $
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.

%

%

%

%

%

\solution
\end{xca}
\begin{defn*}
Une matrice $X=[x_{ij}]$ de taille $n\times n$ est \emph{doublement
stochastique} si les coefficients $x_{ij}$ sont positifs et si la
somme des coefficients sur chaque ligne et chaque colonne vaut $1$:

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

\end{defn*}
\begin{xca}
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.
\end{xca}
%

%

%

%

%

\solution

\begin{thm*}
(Birkhoff-Von Neumann) L'ensemble des matrices doublement stochastiques
est l'enveloppe convexe des matrices de permutations.
\end{thm*}
\begin{xca}
Écrire la matrice doublement stochastique ci-dessus comme combinaison
linéaire convexe de matrices de permutations.
\end{xca}
%

%

%

%

%

%

\solution

\begin{lem*}
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$.
\end{lem*}
\begin{xca}
L'objectif de cet exercice est de démontrer le lemme:
\begin{enumerate}
\item Mettre en équations les contraintes que doivent vérifier les coordonnées
$y_{ij}$ de $Y$. 
\item Définir un programme linéaire $P$ en relâchant la contrainte $y_{ij}\in\left\{ 0,1\right\} $
en $0\leq y_{ij}\leq1$. 
\item Montrer que $P$ est faisable. 
\item 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$.
\item Conclure
\end{enumerate}
\end{xca}
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.

%

%

%

%

%

%

\solution

\begin{xca}
Expliquer comment on pourrait utiliser la programmation linéaire pour
résoudre le problème d'assignement des cours/profs.
\end{xca}

\chapter*{TD 6: Convexité}

\begin{defn}
On appelle \emph{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\geq1$.
\end{defn}
\begin{example}
Le système $x,y\geq0$ et $x+y\leq-1$ est inconsistant.
\end{example}
\begin{thm}
(Tücker) Un système d'équations et d'inéquations est inconsistant
si, et seulement si, il n'a pas de solutions.
\end{thm}


\begin{thm}
(Farkas) Soit $(v_{1},\ldots,v_{n})$ une famille de $n$ vecteurs
de $\R^{m}$, et $b$ un autre vecteur de $\R^{m}$. Alors soit $b$
est dans le cone engendré par $(v_{1},\ldots,v_{n})$, soit il existe
un hyperplan qui les sépare.
\end{thm}
\begin{xca}
Démontrer ces deux théorèmes successivement en utilisant le théorème
de dualité de la programmation linéaire.
\end{xca}

\chapter*{TD 7: Jeux matriciels}


\subsection{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.

\begin{xca}
Jouez!
\end{xca}
%

%

%

%

%

%

%

\solution

À chaque étape, chaque joueur a le choix entre 4 actions: 

\begin{itemize}
\item {[}1,1{]}: Cacher 1 pion, parier 1 pion
\item {[}1,2{]}: Cacher 1 pion, parier 2 pions
\item {[}2,1{]}: Cacher 2 pions, parier 1 pion
\item {[}2,2{]}: Cacher 2 pions, parier 2 pions
\end{itemize}
Chacune de ces options est appelée \emph{stratégie pure}.

\begin{problem*}
Est-ce que suivre une stratégie pure est une stratégie raisonnable
?

Quelles autres stratégies ?
\end{problem*}
%

%

%

%

%

%

\solution

\begin{xca}
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.
\end{xca}
%

%

%

%

%

\solution

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.

\begin{xca}
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.
\end{xca}
%

%

%

%

%

%

\solution

\begin{problem}
Comment caractériser la meilleure stratégie mixte pour Louis ?
\end{problem}
%

%

%

%

%

%

\solution


\subsection{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}$:

\begin{itemize}
\item Si $a_{ij}\geq0$, Louis reçoit $a_{ij}$ de Claire
\item Si $a_{ij}\leq0$, Claire reçoit $-a_{ij}$ de Louis
\item Si $a_{ij}=0$, il n'y a pas d'échange
\end{itemize}
\begin{xca}
Écrire la matrice pour le jeu de Morra.

Écrire la matrice pour le jeu papier/ciseaux/caillou/puits.
\end{xca}
%

\begin{xca}
Dans un long match, Louis adopte une \emph{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:=\sum_{i}c_{i}$ et $y_{i}:=\frac{c_{i}}{N}$. Calculer
le gain moyen par tour pour Louis.
\end{xca}
%

%

%

%

%

%

\solution

\begin{defn*}
Les vecteurs $x:=(x_{1},\ldots,x_{m})$ et $y:=(y_{1},\ldots,y_{n})$
sont dit \emph{stochastiques}: \[
x_{i}\geq0\textrm{ et }x_{1}+\cdots+x_{m}=1.\]


On considère $x:=[x_{1},\ldots,x_{m}]$ comme un vecteur ligne, et
$y:=[y_{1},\ldots,y_{n}]^{T}$ comme un vecteur colonne, de façon
à pouvoir écrire commodément le gain de Louis sous la forme:\[
xAy.\]

\end{defn*}
\begin{xca}
Louis adopte une stratégie mixte donnée. Caractériser le gain au pire
pour Louis.
\end{xca}
%

%

%

%

%

%

\solution

Ici, $x$ est constant. Cela peut se mettre sous la forme du programme
linéaire en $y$:

\[
\min_{y}\textrm{ }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}\textrm{ }xAy$. 

On appelle une telle stratégie mixte \emph{optimale}; son gain moyen
vaut\[
\max_{x}\textrm{ }\min_{y}\textrm{ }xAy\]


\begin{problem}
Est-ce que la stratégie mixte optimale est la meilleure stratégie
?
\end{problem}
%

%

%

%

%

%

\solution

%

\begin{problem}
Comment calculer la stratégie optimale ?
\end{problem}
%

%

%

%

%

%

\solution

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$.

\begin{prop*}
On peut toujours atteindre la quantité $\min_{y}\textrm{ }xAy$ avec
un $y$ de la forme: \[
(0,\ldots,0,1,0,\ldots,0).\]


Autrement dit:\[
\min_{y}\textrm{ }xAy=\min_{j}\sum_{i=1}^{m}a_{ij}x_{i}.\]

\end{prop*}
Interprétation ?

\begin{proof}
Clairement, pour une stratégie pure $j$ donnée:

\[
\min_{y}\textrm{ }xAy\leq\sum_{i=1}^{m}a_{ij}x_{i}.\]


Maintenant, supposons que $j_{0}$ minimise $\sum_{i=1}^{m}a_{ij_{0}}x_{i}$:\[
\sum_{i=1}^{m}a_{ij}x_{i}\geq\sum_{i=1}^{m}a_{ij_{0}}x_{i}\textrm{ pour }j=1,\ldots,n.\]


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

\[
xAy=\sum_{j=1}^{n}\sum_{i=1}^{m}x_{i}a_{ij}y_{j}=\sum_{j=1}^{n}y_{j}\left(\sum_{i=1}^{m}a_{ij}x_{i}\right)\geq\sum_{j=1}^{n}y_{j}\left(\sum_{i=1}^{m}a_{ij_{0}}x_{i}\right)=\left(\sum_{j=1}^{n}y_{j}\right)\left(\sum_{i=1}^{m}a_{ij_{0}}x_{i}\right).\]


Donc, comme voulu,

\[
xAy\geq\sum_{i=1}^{m}a_{ij_{0}}x_{i}\]

\end{proof}
\begin{xca}
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.

%

%

%

%

%

%

\solution
\end{xca}
\begin{thm*}
(Théorème minimax). Pour toute matrice $m\times n$ $A$, il existe
un vecteur stochastique $x^{*}$ de longueur $m$, et un vecteur stochastique
$y^{*}$ de longueur $n$ tel que:\[
\min_{y}\textrm{ }x^{*}Ay=\max_{x}\textrm{ }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$. 
\end{thm*}
Interprétation ?

\begin{proof}
Application immédiate du théorème de dualité.
\end{proof}
%

\begin{defn*}
Si $A$ est interprétée comme un jeu, la \emph{valeur du jeu} est
la quantité:

\[
\min_{y}\textrm{ }x^{*}Ay=\max_{x}\textrm{ }xAy^{*}.\]
 
\end{defn*}
\begin{xca*}
Calculer la valeur du jeu de Morra et du jeu caillou/pierre/ciseaux/puit.

%

%

%

%

%

%

%

\solution

D'où vient cette particularité ?
\end{xca*}

\subsubsection{Stratégie cachée / stratégie révélée}

\begin{problem}
Est-ce que révéler sa stratégie à son adversaire, diminue l'espérance
de gain?

%

%

%

%

%

%

\solution
\end{problem}

\subsection{Morra modifié}

Il n'est pas très pratique de devoir annoncer simultanément les paris.

\begin{problem}
Est-ce que le jeu est modifié si Claire annonce toujours son pari
en premier ?
\end{problem}
%

%

%

\begin{xca*}
Faire l'analyse de ce nouveau jeu.\end{xca*}

\end{document}
