%% 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}
\IfFileExists{url.sty}{\usepackage{url}}
                      {\newcommand{\url}{\texttt}}

\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
 \newenvironment{lyxcode}
   {\begin{list}{}{
     \setlength{\rightmargin}{\leftmargin}
     \setlength{\listparindent}{0pt}% needed for AMS classes
     \raggedright
     \setlength{\itemsep}{0pt}
     \setlength{\parsep}{0pt}
     \normalfont\ttfamily}%
    \item[]}
   {\end{list}}
 \theoremstyle{definition}
  \newtheorem{example}[thm]{Exemple}
 \theoremstyle{definition}
  \newtheorem{xca}{Exercice}
 \theoremstyle{definition}
  \newtheorem*{xca*}{Exercice}
 \theoremstyle{plain}    
 \newtheorem*{thm*}{Théorème} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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{TP 1: Programmation linéaire}

Un compte rendu rapide de ce TP sera à rendre pour le jeudi 20 février.
Il contiendra, pour chaque exercice, une description rapide du modèle,
avec les hypothèses faites, les commandes utilisées pour le résoudre,
le résultat, et tout commentaire que vous jugerez utile.

Tous les exercices de cette fiche peuvent être faits avec MuPAD, Maple
ou probablement la plupart des systèmes de calcul formel, ainsi qu'avec
Matlab ou Scilab. Notez que MuPAD permet de résoudre des programmes
linéaires en entiers, et il permettra, dans des séances futures, de
manipuler des tableaux pour exécuter pas à pas l'algorithme du simplex
(comme en cours!). Pour commencer sous MuPAD, le mieux est de suivre
le tutorial que l'on lance avec:

\begin{lyxcode}
?tutorial
\end{lyxcode}
\begin{example}
On considère le programme linéaire suivant:

Maximiser: $-x+y+2z$

Sous les contraintes:
\begin{itemize}
\item $3x+4y-3z\leq23$
\item $5x-4y-3z\leq10$
\item $7x+4y+11z\leq30$
\item $x,y,z\geq0$
\end{itemize}
Voici les commandes pour résoudre le problème sous MuPAD:
\begin{lyxcode}
c:={[}~\{~3{*}x~+~4{*}y~-~3{*}z~<=~23,~

~~~~~~~5{*}x~-~4{*}y~-~3{*}z~<=~10,~

~~~~~~~7{*}x~+~4{*}y~+~11{*}z~<=~30~\},

~~~~~~~-x~+~y~+~2{*}z,

~~~~~~~NonNegative

~~~{]}:

linopt::maximize(c);
\end{lyxcode}
Pour plus d'information, voir la documentation de la bibliothèque
de programmation linéaire linopt avec:
\begin{lyxcode}
?linopt
\end{lyxcode}
Sous \texttt{Maple}, vous pouvez utiliser la fonction \texttt{simplex{[}maximize{]}}
qui est très similaire.
\end{example}
%

\begin{example}
Pour l'utilisation de \texttt{Scilab}, je recommande le site suivant
(en francais!):

\url{http://cermics.enpc.fr/scilab/}

Vous trouverez en particulier des exemples de résolution de programmes
linéaires dans les TPs sur l'optimisation:
\begin{description}
\item [Questions:]\url{http://cermics.enpc.fr/scilab/Optimisation/Optim_Q_statique/}
\item [Réponses:]\url{http://cermics.enpc.fr/scilab/Optimisation/Optim_R_statique/}
\end{description}
\end{example}
\begin{xca}
Résoudre le problème du régime de Polly
\end{xca}
%

\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}
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 ?

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 ?

Contrainte supplémentaire: vous \emph{devez} être paresseux quand
il s'agit de taper un programme linéaire; l'ordinateur l'est aussi
pour le traiter. Donc, pour chacune de ces questions, vous essayerez
de trouver le programme linéaire le plus petit possible.
\end{xca}
%

\begin{xca}
S'il vous reste du temps, profitez en pour essayer Scilab (par ex.
regarder les autres outils d'optimisation disponibles) et MuPAD (par
ex. commencer le tutorial)
\end{xca}

\chapter{TP2: Simplexe et algèbre linéaire}

Les exercices de cette fiche peuvent être faits avec MuPAD, ou probablement
la plupart des systèmes de calcul formel.

\begin{xca}
Utilisez la bibliothèque \texttt{linopt}, et en particulier les fonctions
pour manipuler les tableaux (\texttt{linopt::Transparent}) pour vérifier
pas à pas vos résolutions de programmes linéaires par l'algorithme
du simplexe. Vous pouvez vous récupérer la plupart des programmes
linéaires du Chvatal a l'adresse suivante \url{http://www.lapcs.univ-lyon1.fr/~nthiery/RO/Notes/tableaux.mu}.
\end{xca}
%

Le but du reste de la séance est de vous familiariser avec le système
de calcul formel MuPAD, en particulier pour programmer. La documentation
de MuPAD contient un tutorial très complet et bien fait; pour y accéder
il suffit de taper ?tutorial. Il existe une version française du tutorial,
mais je ne sais pas si elle est installée.

Pour vous guider, voici quelques exercices de programmation:

\begin{xca}
Programmer une procédure (voir ?proc, ?DOM\_LIST et ?for) qui prends
une liste comme argument, et renvoie le plus grand élément de cette
liste.
\end{xca}
%

\begin{xca}
Programmer une procédure qui prend une matrice $M$ (voir ?matrix)
et un coefficient $c$, et multiplie tous les coefficients de la matrice
par $c$. Évidemment, le plus simple est d'écrire \texttt{c{*}M},
mais ce n'est pas l'objectif de l'exercice.
\end{xca}
%

\begin{xca}
Programmer une procédure qui prend une matrice $M$, et lui applique
le pivot de Gauss.
\end{xca}
%


\chapter{TP3: Programmation et récursivité}

Les exercices de cette fiche peuvent être faits avec MuPAD, Maple,
ou n'importe quel langage de programmation.

\begin{xca}
Programmer une procédure récursive qui prend un entier $n$, et renvoie
le $n$ième nombre de Fibonnacci. Regarder la différence de temps
d'exécution selon si l'on utilise l'option \texttt{remember}, ou pas
(voir ?proc).
\end{xca}
%

\begin{xca}
Programmer une procédure récursive \texttt{listeDeBits} qui prend
un entier $n$, et renvoie toutes les listes de $0$ et de $1$ de
longueur $n$. Par exemple:
\end{xca}
\begin{enumerate}
\item \texttt{listeDeBits(0) = {[}{[}{]}{]}}
\item \texttt{listeDeBits(1) = {[}{[}0{]},{[}1{]}{]}}
\item \texttt{listeDeBits(2) = {[}{[}0,0{]},{[}0,1{]},{[}1,0{]},{[}1,1{]}{]}}
\end{enumerate}
%

\begin{xca}
Programmer une procédure récursive \texttt{compositions} qui prend
un entier $n$, et renvoie toutes les listes d'entiers strictement
positifs dont la somme vaut $n$ (une telle liste est appelée \emph{composition}
de $n$). Par exemple:
\end{xca}
\begin{enumerate}
\item \texttt{compositions(0) = {[}{[}{]}{]}}
\item \texttt{compositions(1) = {[}{[}1{]}{]}}
\item \texttt{compositions(2) = {[}{[}2{]},{[}1,1{]}{]}}
\item \texttt{compositions(3) = {[}{[}3{]},{[}2,1{]},{[}1,2{]},{[}1,1,1{]}{]}}
\end{enumerate}
\begin{xca}
Programmer une procédure récursive \texttt{partitions} qui prend un
entier $n$ et un entier $k$, et renvoie toutes les listes décroissantes
d'entiers entre $1$ et $k$ dont la somme vaut $n$ (une telle liste
est appelée \emph{partition} de $n$ dont les parts sont bornées par
$k$). Par exemple:
\end{xca}
\begin{enumerate}
\item \texttt{partitions(0,10) = {[}{[}{]}{]}}
\item \texttt{partitions(1,10) = {[}{[}1{]}{]}}
\item \texttt{partitions(2,10) = {[}{[}2{]},{[}1,1{]}{]}}
\item \texttt{partitions(3,10) = {[}{[}3{]},{[}2,1{]},{[}1,1,1{]}{]}}
\item \texttt{partitions(3,2) = {[}{[}2,1{]},{[}1,1,1{]}{]}}
\item \texttt{partitions(4,10) = {[}{[}4{]},{[}3,1{]},{[}2,2{]},{[}2,1,1{]},{[}1,1,1,1{]}{]}}
\item \texttt{partitions(4,2) = {[}{[}2,2{]},{[}2,1,1{]},{[}1,1,1,1{]}{]}}
\end{enumerate}
%

\begin{xca}
Problème du sac-à-dos: programmer une procédure récursive qui prend
une liste de $k$ entiers strictements positifs $w$ et un entier
$n$, et renvoie une liste $l$ de $k$ entiers positifs qui maximise
la fonction objective\[
z:=w[1]*l[1]+w[2]*l[2]+\cdots+w[k]*l[k]\]


sous la contrainte que $z$ ne doit pas dépasser $n$. Par exemple:
\end{xca}
\begin{enumerate}
\item \texttt{sacados({[}1{]},2) = {[}2{]}}
\item \texttt{sacados({[}1,1{]},2) = {[}2,0{]} (ou {[}1,1{]} ou {[}0,2{]})}
\item \texttt{sacados({[}5,2,1{]},7) = {[}2,0,1{]} (ou {[}0,1,1{]})}
\item \texttt{sacados({[}5,2{]},8) = {[}1,1{]}}
\end{enumerate}

\chapter{TP 4: Réseaux de transports}

Les exercices de cette fiche peuvent être faits avec MuPAD, Maple,
ou probablement la plupart des systèmes de calcul formel. La bibliothèque
Network de MuPAD (networks de Maple) permet de manipuler des réseaux
de transport.

Il y a quelques bugs dans la bibliothèque Network de MuPAD <= 2.5.2
qui sont corrigés dans le fichier suivant: \url{http://www.lapcs.univ-lyon1.fr/~nthiery/RO/Notes/networkfix.mu}.
Il suffit de le télécharger, et de le lire au début de la session
MuPAD avec la commande

\begin{lyxcode}
read(\char`\"{}<chemin>networkfix.mu\char`\"{}):
\end{lyxcode}
D'autre part, cette bibliothèque fonctionne mal en calculs approchés
(le programmeur n'a pas été prudent avec les tests à zéro, d'où des
instabilités numériques). Il est donc prudent de ne faire que des
calculs avec des nombres rationnels plutôt que des flotants.

\begin{xca*}
Consulter la documentation de \texttt{Network::minCost}, et essayer
l'exemple proposé.

Vérifiez la solution optimale que l'on avait obtenu pour le premier
exemple du cours sur les réseaux de transport.
\end{xca*}
%

\begin{xca*}
Résolution du problème d'assignement avec les réseaux de transport.

Modéliser le problème du cours de l'assignement cours/prof et le résoudre.

On suppose maintenant que l'utilisateur fournit une matrice décrivant
un problème d'assignement similaire. Voici par exemple la matrice
du problème du cours (on a transformé les nombres flotants en rationnels):
\begin{lyxcode}
matrix({[}{[}3,~4,~23/10,~29/10,~28/10{]},~\\
~~~~~~~~{[}225/100,~32/10,~37/10,~19/10,~44/10{]},~\\
~~~~~~~~{[}26/10,~37/10,~45/10,~27/10,~31/10{]},~\\
~~~~~~~~{[}39/10,~41/10,~26/10,~39/10,~24/10{]},~\\
~~~~~~~~{[}28/10,~28/10,~35/10,~34/10,~42/10{]}{]});
\end{lyxcode}
Écrire une procédure qui prend un telle matrice comme argument, et
renvoit l'assignement optimal. Note: ?for, ?proc, et ?linalg::matdim
sont vos amis!
\end{xca*}
%

\begin{xca*}
L'objectif est maintenant d'évaluer la complexité en moyenne de l'algorithme
précédent, en fonction de la taille $n$ de la matrice.

Pour chaque entier $n$ entre $1$ et $10$ (ou beaucoup plus si vous
pouvez), tirer un certain nombre de matrices aléatoires de taille
$n\times n$, et faire la moyenne du temps de calcul (cf. ?random
et ?time). Tracer la courbe obtenue (cf. ?plot), et essayer de trouver
une fonction de la forme $an^{d}$ qui ajuste cette courbe au mieux.

Essayer de majorer au mieux la complexité au pire théorique de cet
algorithme.

Conclusion ?
\end{xca*}
%

\begin{thm*}
(Théorème de König ou lemme des mariages) On a un ensemble de $n$
filles et $n$ garçons que l'on veut marier ensemble. Dans notre grande
magnanimité, on veut bien faire attention à ne pas marier deux personnes
qui ne se connaissent pas.

Si chaque fille connait exactement $k\geq1$ garçons et chaque garçon
connaît exactement $k$ filles, alors on peut arranger $n$ mariages
de façon à ne pas marier des inconnus.
\end{thm*}
\begin{xca*}
Prouvez ce théorème en construisant le problème de transport qui va
bien.
\end{xca*}

\chapter{TP 5 Ordres partiels et ordonnancement}

Les exercices de cette fiche peuvent être faits avec MuPAD, Maple,
ou probablement la plupart des systèmes de calcul formel. La bibliothèque
Network de MuPAD (networks de Maple) permet de manipuler des graphes.

Le but de ce TP est d'implanter quelques algorithmes sur les ordres
partiels, et en particulier la recherche par branchement et coupe
d'un ordonnancement optimal UET d'un ordre partiel sur un nombre donné
de processeurs.

On représentera un ordre partiel par son diagramme de Hasse; c'est-à-dire
par un graphe orienté contenant uniquement les arêtes de l'ordre qui
ne se déduisent pas par transitivité.

La liste des fonctions à implanter, avec leurs documentations, leurs
prototypes et quelques tests est disponible sur \url{http://www.lapcs.univ-lyon1.fr/~nthiery/RO/Notes/OrdresPartiels.mu}.

Vous pouvez trouver de l'inspiration dans le fichier suivant:\url{http://www.lapcs.univ-lyon1.fr/~nthiery/RO/Notes/exemples.mu}

Essayer d'évaluer la complexité au pire de chacune des fonctions que
vous implantez.
\end{document}
