#LyX 2.0 created this file. For more info see http://www.lyx.org/
\lyxformat 413
\begin_document
\begin_header
\textclass amsbook
\begin_preamble
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\usepackage{hyperref}
\newcommand{\solution}{ \vspace{2cm}}
% Bug fix: without forcing the switch to francais after \begin{document}, chapter, table of contents and others are not translated properly
\AtBeginDocument{
\selectlanguage{francais}
}
\end_preamble
\use_default_options false
\begin_modules
theorems-ams
eqs-within-sections
figs-within-sections
\end_modules
\maintain_unincluded_children false
\language french
\language_package default
\inputencoding latin1
\fontencoding global
\font_roman ae
\font_sans default
\font_typewriter default
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_amsmath 2
\use_esint 0
\use_mhchem 0
\use_mathdots 1
\cite_engine basic
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\use_refstyle 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation skip
\defskip smallskip
\quotes_language french
\papercolumns 1
\papersides 2
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header
\begin_body
\begin_layout Title
Cours de Recherche Opérationnelle
\begin_inset Newline newline
\end_inset
IUT d'Orsay
\end_layout
\begin_layout Author
Nicolas M.
THIÉRY
\end_layout
\begin_layout Email
Nicolas.Thiery@u-psud.fr
\end_layout
\begin_layout URL
http://Nicolas.Thiery.name/
\end_layout
\begin_layout Chapter
Introduction à l'optimisation
\end_layout
\begin_layout Section
TD: Ordonnancement par la méthode des potentiels
\end_layout
\begin_layout Exercise*
On veut construire une maison, ce qui consiste en
\begin_inset Formula $9$
\end_inset
tâches, le plus rapidement possible, avec les contraintes suivantes:
\end_layout
\begin_deeper
\begin_layout Itemize
Certaines tâches dépendent d'autres tâches
\end_layout
\begin_layout Itemize
Toutes les tâches demandent une semaine de travail.
\end_layout
\begin_layout Itemize
Chaque ouvrier ne peut travailler que sur une tâche par jour
\end_layout
\begin_layout Itemize
Il n'y a pas de gain de temps si plusieurs ouvriers travaillent sur la même
tâche
\end_layout
\end_deeper
\begin_layout Standard
\begin_inset VSpace 0.3cm
\end_inset
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename maison.eps
\end_inset
\end_layout
\begin_layout Standard
\begin_inset VSpace 0.3cm
\end_inset
\end_layout
\begin_layout Example*
Organisez un emploi du temps pour un ouvrier, de façon à construire la maison
le plus rapidement.
\end_layout
\begin_layout Example*
\begin_inset Tabular
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
semaine 1
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
semaine 2
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
semaine 3
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
semaine 4
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
semaine 5
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
semaine 6
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
semaine 7
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
ouvrier 1
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\end_inset
\end_layout
\begin_layout Example*
De même, s'il y a deux ouvriers:
\end_layout
\begin_layout Example*
\begin_inset Tabular
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
semaine 1
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
semaine 2
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
semaine 3
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
semaine 4
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
semaine 5
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
semaine 6
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
semaine 7
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
ouvrier 1
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
ouvrier 2
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\end_inset
\end_layout
\begin_layout Example*
De même, s'il y a trois ouvriers:
\end_layout
\begin_layout Example*
\begin_inset Tabular
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
semaine 1
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
semaine 2
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
semaine 3
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
semaine 4
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
semaine 5
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
semaine 6
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
semaine7
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
ouvrier 1
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
ouvrier 2
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\lang english
ouvrier 3
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\end_inset
\end_layout
\begin_layout Example*
Et s'il y a plus d'ouvriers ?
\end_layout
\begin_layout Standard
Généralisation avec des durées.
\end_layout
\begin_layout Section
Problèmes d'optimisation
\end_layout
\begin_layout Problem
Quelles sont les coordonnées du point culminant du massif de la Chartreuse?
\end_layout
\begin_layout Problem
\begin_inset Graphics
filename Chartreuse.jpg
lyxscale 85
width 100col%
\end_inset
\end_layout
\begin_layout Problem
Modélisation:
\end_layout
\begin_layout Definition
Un
\emph on
problème d'optimisation
\emph default
est décrit par:
\end_layout
\begin_deeper
\begin_layout Itemize
Un
\emph on
domaine
\emph default
\begin_inset Formula $S$
\end_inset
\begin_inset Newline newline
\end_inset
Ici,
\begin_inset Formula $S$
\end_inset
est l'ensemble des points
\begin_inset Formula $p$
\end_inset
de la surface de la terre, décrits par leur coordonnées (longitude, latitude).
\begin_inset Newline newline
\end_inset
Un élément de
\begin_inset Formula $S$
\end_inset
est appellé
\emph on
solution
\emph default
.
\end_layout
\begin_layout Itemize
Des contraintes
\begin_inset Formula $C$
\end_inset
définissant un sous-ensemble de
\begin_inset Formula $S$
\end_inset
.
\begin_inset Newline newline
\end_inset
Ici,
\begin_inset Formula $C(p):=\texttt{« \ensuremath{p}est dans le massif de la Chartreuse »}$
\end_inset
.
\begin_inset Newline newline
\end_inset
Une solution
\begin_inset Formula $p$
\end_inset
vérifiant les contraintes
\begin_inset Formula $C(p)$
\end_inset
est dite
\emph on
solution faisable
\emph default
.
\end_layout
\begin_layout Itemize
Une
\emph on
fonction objectif
\emph default
:
\begin_inset Formula $z:S\mapsto\mathbb{R}$
\end_inset
\begin_inset Newline newline
\end_inset
Ici la fonction
\begin_inset Formula $p\mapsto z(p)$
\end_inset
qui associe à un point
\begin_inset Formula $p$
\end_inset
de la surface de la terre sont altitude
\begin_inset Formula $z(p)$
\end_inset
.
\end_layout
\end_deeper
\begin_layout Definition
Il faut de plus préciser s'il s'agit d'un problème de
\emph on
maximisation
\emph default
ou de
\emph on
minimisation
\emph default
.
\end_layout
\begin_layout Definition
Une solution faisable
\begin_inset Formula $p$
\end_inset
est dite
\emph on
optimale
\emph default
si
\begin_inset Formula $z(p)\geq z(q)$
\end_inset
pour toute autre solution faisable
\begin_inset Formula $q$
\end_inset
.
\end_layout
\begin_layout Definition
But: déterminer l'ensemble des solutions optimales.
\end_layout
\begin_layout Example
Modéliser les problèmes suivants, puis les résoudre ou proposer des méthodes
de résolution:
\end_layout
\begin_deeper
\begin_layout Enumerate
Calcul du plus court chemin dans un graphe.
\end_layout
\begin_layout Enumerate
Recherche d'un ordonnancement optimal pour ...
\end_layout
\begin_layout Enumerate
Déterminer le plus petits nombre de cartons nécessaires pour un déménagement.
\end_layout
\begin_layout Enumerate
Chercher un mat en un minimum de coup
\end_layout
\begin_layout Enumerate
Recherche de l'élément maximal d'un tableau de
\begin_inset Formula $n$
\end_inset
valeurs aléatoires.
\end_layout
\begin_layout Enumerate
Maximiser
\begin_inset Formula $z$
\end_inset
pour
\begin_inset Formula $z$
\end_inset
dans
\begin_inset Formula $[0,1[$
\end_inset
.
\end_layout
\begin_layout Enumerate
Maximiser
\begin_inset Formula $z$
\end_inset
pour
\begin_inset Formula $z$
\end_inset
dans
\begin_inset Formula $\mathbb{R}^{+}$
\end_inset
.
\end_layout
\begin_layout Enumerate
Déterminer la valeur minimale de la fonction
\begin_inset Formula $x^{2}+2x-4$
\end_inset
.
\begin_inset Newline newline
\end_inset
\family typewriter
plotfunc2d(x^2 + 2*x - 4)
\end_layout
\begin_layout Enumerate
Déterminer la valeur minimale de la fonction
\begin_inset Formula $2x^{3}-5x^{2}-x+7$
\end_inset
.
\begin_inset Newline newline
\end_inset
\family typewriter
plotfunc2d(2*x^3 - 5*x - x + 7)
\end_layout
\begin_layout Enumerate
Déterminer la valeur maximale de la fonction
\begin_inset Formula $\sin(x)\sin(\pi x+2)+0.01x^{2}$
\end_inset
.
\begin_inset Newline newline
\end_inset
\family typewriter
plotfunc2d(sin(x) * sin(PI*x+2)-0.01*x^2,x=-20..20)
\end_layout
\begin_layout Enumerate
Quelle est la profondeur maximale de l'océan?
\end_layout
\end_deeper
\begin_layout Standard
Bilan: un problème d'optimisation peut avoir
\end_layout
\begin_layout Itemize
Aucune solution
\end_layout
\begin_layout Itemize
Aucune solution optimale (non borné)
\end_layout
\begin_layout Itemize
Une unique solution optimale
\end_layout
\begin_layout Standard
Quelques méthodes d'optimisation:
\end_layout
\begin_layout Enumerate
Méthodes globales:
\end_layout
\begin_deeper
\begin_layout Itemize
Monte-Carlo
\end_layout
\begin_layout Itemize
Recherche exhaustive (toujours possible pour un problème discret fini; parfois
la seule méthode existante)
\end_layout
\begin_layout Itemize
Recherche exhaustive structurée, avec coupures de branches.
\end_layout
\end_deeper
\begin_layout Enumerate
Méthodes locales, itératives:
\begin_inset Newline newline
\end_inset
Lorsque le problème a une propriété de «convexité», l'optimisation locale
amène à une optimisation globale!
\end_layout
\begin_deeper
\begin_layout Itemize
Algorithmes gloutons
\end_layout
\begin_layout Itemize
Méthodes analytiques (gradient)
\end_layout
\begin_layout Itemize
Méthode du simplexe
\end_layout
\end_deeper
\begin_layout Enumerate
Méthodes mixtes:
\end_layout
\begin_deeper
\begin_layout Itemize
Monte-Carlo + gradient
\end_layout
\begin_layout Itemize
Recuit simulé, \SpecialChar \ldots{}
\end_layout
\end_deeper
\begin_layout Chapter
Programmation linéaire
\end_layout
\begin_layout Section
Rappel d'algèbre linéaire
\end_layout
\begin_layout Problem
Considérons le système suivant:
\end_layout
\begin_deeper
\begin_layout LyX-Code
5 = s1 + 2*x1 + 3*x2 + x3
\end_layout
\begin_layout LyX-Code
11 = s2 + 4*x1 + x2 + 2*x3
\end_layout
\begin_layout LyX-Code
8 = s3 + 3*x1 + 4*x2 + 2*x3
\end_layout
\end_deeper
\begin_layout Problem
Que peut-on dire d
\end_layout
\begin_layout Problem
\begin_inset Formula $1+\frac{1+\pi}{\sqrt{1+\frac{}{}}}$
\end_inset
\end_layout
\begin_layout Problem
essus?
\end_layout
\begin_layout Problem
\begin_inset ERT
status open
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
\end_layout
\begin_layout Problem
C'est un système
\emph on
linéaire
\emph default
à 6 inconnues et 3 équations.
\end_layout
\begin_layout Problem
On peut décrire l'ensemble des solutions en prenant comme paramètres
\family typewriter
x1
\family default
,
\family typewriter
x2
\family default
et
\family typewriter
x3
\family default
.
\end_layout
\begin_layout Problem
En effet, vu sa forme triangulaire, s1, s2 et s3 s'expriment en fonction
de
\family typewriter
x1
\family default
,
\family typewriter
x2
\family default
et
\family typewriter
x3
\family default
.
\end_layout
\begin_layout Problem
Transformer le système pour prendre comme paramètres
\begin_inset Formula $ $
\end_inset
\family typewriter
s1
\family default
,
\family typewriter
s2
\family default
, et
\family typewriter
x1
\family default
.
\end_layout
\begin_layout Section
Qu'est-ce que la programmation linéaire
\end_layout
\begin_layout Subsection
Exemple: le problème du régime de Polly
\begin_inset CommandInset citation
LatexCommand cite
after "p.3"
key "Chvatal_LP"
\end_inset
\end_layout
\begin_layout Itemize
Besoins journaliers:
\end_layout
\begin_deeper
\begin_layout Description
Énergie 2000 kcal
\end_layout
\begin_layout Description
Protéines 55g
\end_layout
\begin_layout Description
Calcium 800 mg
\end_layout
\end_deeper
\begin_layout Itemize
Nourriture disponible
\end_layout
\begin_deeper
\begin_layout Standard
\begin_inset Tabular
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Portion
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Énergie (kcal)
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Protéines (g)
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Calcium (mg)
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Prix/portion
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Céréales
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
28g
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
110
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
4
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
2
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
3
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Poulet
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
100g
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
205
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
32
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
12
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
24
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Oeufs
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
2 gros
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
160
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
13
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
54
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
13
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Lait entier
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
237cc
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
160
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
8
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
285
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
9
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Tarte
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
170g
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
420
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
4
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
22
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
20
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Porc et haricots
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
260g
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
260
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
14
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
80
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
19
\end_layout
\end_inset
|
\end_inset
\end_layout
\end_deeper
\begin_layout Itemize
Contraintes:
\end_layout
\begin_deeper
\begin_layout Description
Céréales au plus 4 portions par jour
\end_layout
\begin_layout Description
Poulet au plus 3 portions par jour
\end_layout
\begin_layout Description
Oeufs au plus 2 portions par jour
\end_layout
\begin_layout Description
Lait au plus 8 portions par jour
\end_layout
\begin_layout Description
Tarte au plus 2 portions par jour
\end_layout
\begin_layout Description
Porc
\begin_inset space ~
\end_inset
et
\begin_inset space ~
\end_inset
haricots au plus 2 portions par jour
\end_layout
\end_deeper
\begin_layout Problem
Polly peut-elle trouver une solution ?
\end_layout
\begin_layout Problem
Comment formaliser le problème ? (modélisation)
\end_layout
\begin_layout Problem
Qu'est-ce qui fait la spécificité du problème ?
\end_layout
\begin_layout Problem
Savez-vous résoudre des problèmes similaires ?
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
\end_layout
\begin_layout Subsection
Forme standard d'un problème de programmation linéaire
\end_layout
\begin_layout Problem
\begin_inset CommandInset citation
LatexCommand cite
after "p. 5"
key "Chvatal_LP"
\end_inset
\end_layout
\begin_deeper
\begin_layout LyX-Code
Maximiser: 5*x1 + 4*x2 + 3*x3
\end_layout
\begin_layout LyX-Code
Sous les contraintes: 2*x1 + 3*x2 + x3 <= 5
\end_layout
\begin_layout LyX-Code
4*x1 + x2 + 2*x3 <= 11
\end_layout
\begin_layout LyX-Code
3*x1 + 4*x2 + 2*x3 <= 8
\end_layout
\begin_layout LyX-Code
x1, x2, x3 >= 0
\end_layout
\begin_layout LyX-Code
\end_layout
\begin_layout LyX-Code
Minimiser: 3*x1 - x2
\end_layout
\begin_layout LyX-Code
Sous les contraintes: - x1 + 6*x2 - x3 + x4 >= -3
\end_layout
\begin_layout LyX-Code
7*x2 + 2*x4 = 5
\end_layout
\begin_layout LyX-Code
x1 + x2 + x3 = 1
\end_layout
\begin_layout LyX-Code
x3 + x4 <= 2
\end_layout
\begin_layout LyX-Code
x2, x3 >= 0
\end_layout
\end_deeper
\begin_layout Definition*
Problème de programmation linéaire sous
\emph on
forme standard:
\end_layout
\begin_layout Definition*
Maximiser:
\end_layout
\begin_layout Definition*
\begin_inset Formula
\[
z:=\sum_{j=1}^{n}c_{j}x_{j}
\]
\end_inset
\end_layout
\begin_layout Definition*
Sous les contraintes:
\end_layout
\begin_layout Definition*
\begin_inset Formula
\[
\sum_{j=1}^{n}a_{ij}x_{j}\leq b_{i},\textrm{ pour }i=1,\ldots,m
\]
\end_inset
\end_layout
\begin_layout Definition*
\begin_inset Formula
\[
x_{j}\geq0,\textrm{ pour }j=1,\ldots,n
\]
\end_inset
\end_layout
\begin_layout Definition*
Un choix des valeurs des variables
\begin_inset Formula $(x_{1},\ldots,x_{n})$
\end_inset
est appelé
\emph on
solution
\emph default
du problème.
\end_layout
\begin_layout Definition*
Une solution est
\emph on
faisable
\emph default
si elle vérifie les contraintes.
\end_layout
\begin_layout Definition*
\begin_inset Formula $z$
\end_inset
est appelé
\emph on
fonction objective
\emph default
.
À chaque solution elle associe une valeur.
\end_layout
\begin_layout Definition*
Une solution est
\emph on
optimale
\emph default
si elle est faisable et maximize la fonction objective.
\end_layout
\begin_layout Exercise
Peut-on mettre sous forme standard les exemples précédents ?
\end_layout
\begin_layout Subsection
Existence de solutions optimales ?
\end_layout
\begin_layout Problem
\begin_inset CommandInset citation
LatexCommand cite
after "p. 7"
key "Chvatal_LP"
\end_inset
On considère les trois problèmes de programmation linéaire standard suivants,
écrits avec la syntaxe du système de calcul formel
\family typewriter
MuPAD
\family default
:
\end_layout
\begin_deeper
\begin_layout LyX-Code
Chvatal7a := [ [ x1 <= 3,
\end_layout
\begin_layout LyX-Code
x2 <= 7 ],
\end_layout
\begin_layout LyX-Code
3 +x1 +x2,
\end_layout
\begin_layout LyX-Code
NonNegative]:
\end_layout
\begin_layout LyX-Code
Chvatal7b := [ [ x1 +x2 <= 2,
\end_layout
\begin_layout LyX-Code
-2*x1-2*x2 <= -10 ],
\end_layout
\begin_layout LyX-Code
3*x1 -x2,
\end_layout
\begin_layout LyX-Code
NonNegative]:
\end_layout
\begin_layout LyX-Code
Chvatal7c := [ [-2*x1 +x2 <= -1,
\end_layout
\begin_layout LyX-Code
-x1-2*x2 <= -2 ],
\end_layout
\begin_layout LyX-Code
x1 -x2,
\end_layout
\begin_layout LyX-Code
NonNegative]:
\end_layout
\begin_layout LyX-Code
extra := [ [ x1 +x2 <= 1 ],
\end_layout
\begin_layout LyX-Code
x1 +x2,
\end_layout
\begin_layout LyX-Code
NonNegative]:
\end_layout
\end_deeper
\begin_layout LyX-Code
\end_layout
\begin_layout Problem
Déterminer pour ces trois problèmes s'il y a des solutions optimales.
\end_layout
\begin_layout LyX-Code
\begin_inset ERT
status open
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\backslash
solution
\end_layout
\end_inset
\end_layout
\begin_layout Itemize
Premier cas: une solution optimale unique
\end_layout
\begin_layout Itemize
Deuxième cas: pas de solution faisable
\end_layout
\begin_layout Itemize
Troisième cas: pas de solution optimale, car on peut faire tendre la fonction
objective vers l'infini avec des solutions faisables.
\end_layout
\begin_layout Itemize
Quatrième cas: une infinité de solutions optimales.
\end_layout
\begin_layout Section
Algorithme du simplexe
\end_layout
\begin_layout Subsection
Premier problème
\end_layout
\begin_layout Problem
\begin_inset CommandInset label
LatexCommand label
name "probleme:simplexe1"
\end_inset
\begin_inset CommandInset citation
LatexCommand cite
after "p. 13"
key "Chvatal_LP"
\end_inset
\end_layout
\begin_deeper
\begin_layout LyX-Code
Chvatal13 := [{2*x1 + 3*x2 + x3 <= 5,
\end_layout
\begin_layout LyX-Code
4*x1 + x2 + 2*x3 <= 11,
\end_layout
\begin_layout LyX-Code
3*x1 + 4*x2 + 2*x3 <= 8 },
\end_layout
\begin_layout LyX-Code
5*x1 + 4*x2 + 3*x3,
\end_layout
\begin_layout LyX-Code
NonNegative]:
\end_layout
\end_deeper
\begin_layout Standard
Solution faisable ?
\end_layout
\begin_layout Standard
Amélioration de la solution ?
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\backslash
solution
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Introduction de variables d'écart:
\end_layout
\begin_layout LyX-Code
5 = s1 + 2*x1 + 3*x2 + x3
\end_layout
\begin_layout LyX-Code
11 = s2 + 4*x1 + x2 + 2*x3
\end_layout
\begin_layout LyX-Code
8 = s3 + 3*x1 + 4*x2 + 2*x3
\end_layout
\begin_layout LyX-Code
----------------------------------
\end_layout
\begin_layout LyX-Code
z = 5*x1 + 4*x2 + 3*x3
\end_layout
\begin_layout Standard
En augmentant
\family typewriter
x1
\family default
jusqu'à
\begin_inset Formula $5/2$
\end_inset
, on fait tomber
\family typewriter
s1
\family default
à zéro.
\end_layout
\begin_layout Standard
On transforme le système, pour se ramener à une situation similaire à la
précédente:
\end_layout
\begin_layout LyX-Code
5/2 = x1 + 3/2*x2 + 1/2*x3 + 1/2*s1
\end_layout
\begin_layout LyX-Code
1 = s2 - 5*x2 - 2*s1
\end_layout
\begin_layout LyX-Code
1/2 = s3 - 1/2*x2 + 1/2*x3 - 3/2*s1
\end_layout
\begin_layout LyX-Code
-----------------------------------------
\end_layout
\begin_layout LyX-Code
z = 25/2 - 7/2 x2 + 1/2*x3 - 5/2*s1
\end_layout
\begin_layout Standard
On augmente x3 jusqu'à 1, ce qui fait tomber s3 à 0:
\end_layout
\begin_layout LyX-Code
1 = x3 - x2 - 3*s1 + 2*s3
\end_layout
\begin_layout LyX-Code
2 = x1 + 2*x2 + 2*s1 - s3
\end_layout
\begin_layout LyX-Code
1 = s2 - 5*x2 - 2*s1
\end_layout
\begin_layout LyX-Code
---------------------------------
\end_layout
\begin_layout LyX-Code
z = 13 - 3*x2 - s1 - s3
\end_layout
\begin_layout Standard
Et maintenant, que fait-on ?
\end_layout
\begin_layout Subsection
Tableaux
\end_layout
\begin_layout Problem
\begin_inset CommandInset citation
LatexCommand cite
after "p. 19"
key "Chvatal_LP"
\end_inset
\end_layout
\begin_deeper
\begin_layout LyX-Code
Chvatal19 := [[ x1 + 3*x2 + x3 <= 3,
\end_layout
\begin_layout LyX-Code
-x1 +3*x3 <= 2,
\end_layout
\begin_layout LyX-Code
2*x1 + 3*x2 - x3 <= 2,
\end_layout
\begin_layout LyX-Code
2*x1 - x2 + 2*x3 <= 4],
\end_layout
\begin_layout LyX-Code
5*x1 + 5*x2 + 3*x3,
\end_layout
\begin_layout LyX-Code
NonNegative]:
\end_layout
\end_deeper
\begin_layout Definition*
\emph on
Tableau initial:
\end_layout
\begin_layout Definition*
\begin_inset Formula
\[
b_{i}=s_{i}+\sum_{j=1}^{n}a_{ij}x_{j},\textrm{ pour }i=1,\ldots,m
\]
\end_inset
\end_layout
\begin_layout Definition*
\begin_inset Formula
\[
z=\sum_{j=1}^{n}c_{j}x_{j}
\]
\end_inset
\end_layout
\begin_layout Definition*
Ou sous forme matricielle:
\begin_inset Formula
\begin{eqnarray*}
B & = & S+AX\\
z & = & CX\\
X & \geq & 0
\end{eqnarray*}
\end_inset
\end_layout
\begin_layout Example*
Tableau initial du problème précédent:
\end_layout
\begin_deeper
\begin_layout LyX-Code
3 = s1 + x1 + 3 x2 + x3
\end_layout
\begin_layout LyX-Code
2 = s2 - x1 + 3 x3
\end_layout
\begin_layout LyX-Code
2 = s3 + 2 x1 + 3 x2 - x3
\end_layout
\begin_layout LyX-Code
4 = s4 + 2 x1 - x2 + 2 x3
\end_layout
\begin_layout LyX-Code
---------------------------------
\end_layout
\begin_layout LyX-Code
z = 0 + 5 x1 + 5 x2 + 3 x3
\end_layout
\end_deeper
\begin_layout Example
On peut l'abréger sous forme matricielle:
\end_layout
\begin_deeper
\begin_layout LyX-Code
read("tableaux.mu"):
\end_layout
\begin_layout LyX-Code
linopt::Transparent(Chvatal19);
\end_layout
\begin_layout LyX-Code
+- -+
\end_layout
\begin_layout LyX-Code
|"linopt","restr",slk[1],slk[2],slk[3],slk[4],x3,x1,x2|
\end_layout
\begin_layout LyX-Code
| |
\end_layout
\begin_layout LyX-Code
| "obj", 0, 0, 0, 0, 0, 3, 5, 5|
\end_layout
\begin_layout LyX-Code
| |
\end_layout
\begin_layout LyX-Code
| slk[1], 3, 1, 0, 0, 0, 1, 1, 3|
\end_layout
\begin_layout LyX-Code
| |
\end_layout
\begin_layout LyX-Code
| slk[2], 2, 0, 1, 0, 0, 3,-1, 0|
\end_layout
\begin_layout LyX-Code
| |
\end_layout
\begin_layout LyX-Code
| slk[3], 2, 0, 0, 1, 0, -1, 2, 3|
\end_layout
\begin_layout LyX-Code
| |
\end_layout
\begin_layout LyX-Code
| slk[4], 4, 0, 0, 0, 1, 2, 2,-1|
\end_layout
\begin_layout LyX-Code
+- -+
\end_layout
\end_deeper
\begin_layout Definition*
De manière générale, un
\emph on
tableau
\emph default
est un ensemble d'équations de la forme:
\end_layout
\begin_deeper
\begin_layout LyX-Code
4 = x1 + 3/2 x2 - 1/2 x3 + 1/2 s4
\end_layout
\begin_layout LyX-Code
2 = s1 + 3/2 x2 + 3/2 x3 - 1/2 s4
\end_layout
\begin_layout LyX-Code
3 = s2 + 3/2 x2 + 5/2 x3 + 1/2 s4
\end_layout
\begin_layout LyX-Code
2 = s3 - 4 x2 + 3 x3 - s4
\end_layout
\begin_layout LyX-Code
----------------------------------------
\end_layout
\begin_layout LyX-Code
z = 5 - 5/2 x2 + 11/2 x3 - 5/2 s4
\end_layout
\end_deeper
\begin_layout Definition*
\begin_inset Formula $x_{1},s_{1},s_{2},s_{3}$
\end_inset
sont les variables
\emph on
basiques;
\emph default
\begin_inset Formula $\{x_{1},s_{1},s_{2},s_{3}\}$
\end_inset
est la
\emph on
base
\emph default
.
\end_layout
\begin_layout Definition*
\begin_inset Formula $x_{2},x_{3},s_{4}$
\end_inset
sont les variables
\emph on
non basiques.
\end_layout
\begin_layout Definition
Le point de coordonnées
\begin_inset Formula $(0,\ldots,0)$
\end_inset
dans les variables non-basiques est appellé
\emph on
solution basique
\emph default
du tableau.
\end_layout
\begin_layout Definition
Un tableau est
\emph on
faisable
\emph default
si la solution basique
\begin_inset Formula $(0,\ldots,0)$
\end_inset
est une solution faisable.
\end_layout
\begin_layout Definition
De manière équivalente, un tableau est faisable si les constantes dans les
équations du haut sont toutes positives ou nulles.
\end_layout
\begin_layout Standard
Revenons à l'exemple
\begin_inset CommandInset citation
LatexCommand cite
after "p. 19"
key "Chvatal_LP"
\end_inset
:
\end_layout
\begin_layout LyX-Code
read("tableaux.mu"):
\end_layout
\begin_layout LyX-Code
t:=linopt::Transparent(Chvatal19);
\end_layout
\begin_layout LyX-Code
t:=linopt::Transparent::userstep(t, slk[3], x3);
\end_layout
\begin_layout Exercise
\begin_inset CommandInset citation
LatexCommand cite
after "2.1 p. 26"
key "Chvatal_LP"
\end_inset
\end_layout
\begin_layout Exercise
Utilisez l'algorithme du simplexe pour résoudre les programmes linéaires
suivants:
\end_layout
\begin_deeper
\begin_layout LyX-Code
Chvatal26_21a :=
\end_layout
\begin_layout LyX-Code
[[ x1 +x2+2*x3 <= 4,
\end_layout
\begin_layout LyX-Code
2*x1 +3*x3 <= 5,
\end_layout
\begin_layout LyX-Code
2*x1 +x2+3*x3 <= 7],
\end_layout
\begin_layout LyX-Code
3*x1+2*x2+4*x3,
\end_layout
\begin_layout LyX-Code
NonNegative]:
\end_layout
\begin_layout LyX-Code
\end_layout
\begin_layout LyX-Code
Chvatal26_21c :=
\end_layout
\begin_layout LyX-Code
[[2*x1+3*x2 <= 3,
\end_layout
\begin_layout LyX-Code
x1+5*x2 <= 1,
\end_layout
\begin_layout LyX-Code
2*x1 +x2 <= 4,
\end_layout
\begin_layout LyX-Code
4*x1 +x2 <= 5],
\end_layout
\begin_layout LyX-Code
2*x1 +x2,
\end_layout
\begin_layout LyX-Code
NonNegative]:
\end_layout
\end_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
%
\end_layout
\end_inset
\end_layout
\begin_layout Exercise
Essayez d'appliquer l'algorithme du simplexe aux programmes linéaires de
l'exercice
\begin_inset CommandInset citation
LatexCommand cite
after "p. 7"
key "Chvatal_LP"
\end_inset
(cf.
ci-dessus).
Que se passe-t'il ?
\end_layout
\begin_layout Section
Pièges et comment les éviter
\end_layout
\begin_layout Subsection
Bilan des épisodes précédents
\end_layout
\begin_layout Standard
On a un algorithme qui marche sur quelques exemples.
\end_layout
\begin_layout Standard
Il faut vérifier trois points pour savoir s'il marche en général:
\end_layout
\begin_layout Enumerate
Initialisation
\end_layout
\begin_layout Enumerate
Itération
\end_layout
\begin_layout Enumerate
Terminaison
\end_layout
\begin_layout Subsection
Itération
\end_layout
\begin_layout Proposition*
Étant donné un tableau faisable, on peut toujours effectuer l'une des opérations
suivantes:
\end_layout
\begin_layout Enumerate
Conclure que le système a une solution optimale unique, la calculer et la
certifier;
\end_layout
\begin_layout Enumerate
Conclure que le système a une infinité de solutions optimales, les calculer
et les certifier;
\end_layout
\begin_layout Enumerate
Conclure que le système est non borné, et le certifier en décrivant une
demi-droite de solutions sur laquelle
\begin_inset Formula $z$
\end_inset
prend des valeurs aussi grandes que voulu.
\end_layout
\begin_layout Enumerate
Trouver une variable entrante, une variable sortante, et effectuer un pivot.
Par construction, le tableau obtenu est équivalent au tableau précédent,
et est encore faisable.
De plus,
\begin_inset Formula $z$
\end_inset
a
\emph on
augmenté au sens large
\emph default
(i.e.
la constante
\begin_inset Formula $z^{*}$
\end_inset
dans la nouvelle expression de
\begin_inset Formula $z$
\end_inset
est supérieure ou égale à l'ancienne).
\end_layout
\begin_layout Proof
Il suffit d'analyser le tableau faisable.
Notons
\begin_inset Formula $S_{1},\ldots,S_{m}$
\end_inset
les variables basiques,
\begin_inset Formula $X_{1},\ldots,X_{n}$
\end_inset
les variables non-basiques, et
\begin_inset Formula $C_{1},\ldots,C_{n},z^{*}$
\end_inset
les coefficients tels que
\begin_inset Formula $z=z^{*}+\sum C_{i}X_{i}$
\end_inset
.
\end_layout
\begin_layout Proof
Par exemple, dans le tableau final du problème
\begin_inset CommandInset ref
LatexCommand ref
reference "probleme:simplexe1"
\end_inset
, on a
\begin_inset Formula $X_{1}=x_{2}$
\end_inset
,
\begin_inset Formula $X_{2}=s_{1}$
\end_inset
,
\begin_inset Formula $X_{3}=s_{2}$
\end_inset
,
\begin_inset Formula $S_{1}=x_{1}$
\end_inset
,
\begin_inset Formula $S_{2}=x_{3}$
\end_inset
,
\begin_inset Formula $S_{3}=s_{3}$
\end_inset
,
\begin_inset Formula $C_{1}=-3$
\end_inset
,
\begin_inset Formula $C_{2}=-1$
\end_inset
,
\begin_inset Formula $C_{3}=-1$
\end_inset
et
\begin_inset Formula $z^{*}=13$
\end_inset
.
\end_layout
\begin_deeper
\begin_layout Enumerate
Si
\begin_inset Formula $C_{i}<0$
\end_inset
, pour tout
\begin_inset Formula $i$
\end_inset
, alors la solution basique du tableau, de coordonnées
\begin_inset Formula $X_{1}^{*}=\cdots=X_{n}^{*}=0$
\end_inset
est l'unique solution optimale.
Vérifiez le en prouvant qu'une toute solution faisable quelconque de coordonnée
s
\begin_inset Formula $X_{1},\ldots,X_{n}$
\end_inset
donnant la même valeur
\begin_inset Formula $z=z^{*}$
\end_inset
à la fonction objective est égale à la solution basique du tableau.
\end_layout
\begin_layout Enumerate
Si
\begin_inset Formula $C_{i}\leq0$
\end_inset
pour tout
\begin_inset Formula $i$
\end_inset
, la solution basique du tableau est optimale, et l'ensemble des solutions
optimales est décrit par les inéquations linéaires du système et l'annulation
des variables non-basiques
\begin_inset Formula $X_{i}$
\end_inset
pour lesquelles on a
\begin_inset Formula $C_{i}<0$
\end_inset
.
Les détails sont similaires au 1.
\end_layout
\begin_layout Enumerate
Sinon, on peut prendre
\begin_inset Formula $X_{i}$
\end_inset
, variable non-basique avec un coefficient
\begin_inset Formula $C_{i}>0$
\end_inset
.
Si les équations du tableau n'imposent pas de limite sur
\begin_inset Formula $X_{i}$
\end_inset
, le système est non borné: la demi-droite décrite par
\begin_inset Formula $(0,\ldots,0,X_{i},0,\ldots,0)$
\end_inset
pour
\begin_inset Formula $X_{i}\geq0$
\end_inset
est composée de solutions faisables qui donnent des valeurs aussi grandes
que voulu à
\begin_inset Formula $z$
\end_inset
.
\end_layout
\begin_layout Enumerate
Autrement, une des variables basiques
\begin_inset Formula $S_{j}$
\end_inset
tombe à zéro, et on peut faire un pivot entre la variable entrante
\begin_inset Formula $X_{i}$
\end_inset
et la variable sortante
\begin_inset Formula $S_{j}$
\end_inset
.
Par construction, la nouvelle solution basique correspond à une solution
faisable
\begin_inset Formula $(0,\ldots,0,X_{i},0,\ldots,0)$
\end_inset
pour un
\begin_inset Formula $X_{i}\geq0$
\end_inset
.
En particulier le nouveau tableau est faisable, et comme
\begin_inset Formula $C_{i}\geq0$
\end_inset
, la constante
\begin_inset Formula $z^{*}$
\end_inset
a augmenté au sens large.
\end_layout
\end_deeper
\begin_layout Example*
\begin_inset CommandInset citation
LatexCommand cite
after "p. 29"
key "Chvatal_LP"
\end_inset
Système où
\begin_inset Formula $z$
\end_inset
n'augmente pas strictement lors du pivot:
\end_layout
\begin_layout LyX-Code
Chvatal29 := [[ 2*x3 <= 1,
\end_layout
\begin_layout LyX-Code
- x1 + 3*x2 + 4*x3 <= 2,
\end_layout
\begin_layout LyX-Code
2*x1 - 4*x2 + 6*x3 <= 3],
\end_layout
\begin_layout LyX-Code
2*x1 - x2 + 8*x3,
\end_layout
\begin_layout LyX-Code
NonNegative]:
\end_layout
\begin_layout LyX-Code
t0:= linopt::Transparent(Chvatal29);
\end_layout
\begin_layout LyX-Code
t1:= linopt::Transparent::userstep(t0, slk[1], x3);
\end_layout
\begin_layout LyX-Code
t2:= linopt::Transparent::userstep(t1, slk[3], x1);
\end_layout
\begin_layout LyX-Code
t3:= linopt::Transparent::userstep(t2, slk[2], x2);
\end_layout
\begin_layout LyX-Code
t4:= linopt::Transparent::userstep(t3, x3, slk[1]);
\end_layout
\begin_layout Remark*
Lorsque
\begin_inset Formula $z$
\end_inset
n'augmente pas, on est forcément dans une situation de dégénérescence:
le pivot change le tableau, mais pas la solution basique décrite par le
tableau.
\end_layout
\begin_layout Subsection
Terminaison
\end_layout
\begin_layout Problem
Peut-on garantir que l'algorithme va finir par s'arrêter ?
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\backslash
solution
\end_layout
\end_inset
\end_layout
\begin_layout Theorem*
Si l'algorithme du simplexe ne cycle pas, il termine en au plus
\begin_inset Formula $C(n+m,m)$
\end_inset
itérations.
\end_layout
\begin_layout Proof
(Résumé)
\end_layout
\begin_layout Proof
Chaque itération correspond à un tableau faisable.
\end_layout
\begin_layout Proof
Un tableau faisable est entièrement caractérisé par le choix des variables
basiques.
\end_layout
\begin_layout Proof
Il n'y a
\begin_inset Quotes fld
\end_inset
que
\begin_inset Quotes frd
\end_inset
\begin_inset Formula $C(n+m,m)$
\end_inset
choix possibles de variables basiques.
\end_layout
\begin_layout Remark*
L'algorithme ne peut cycler qu'en présence de dégénérescence.
\end_layout
\begin_layout Standard
Avec une stratégie incorrecte, l'algorithme du simplexe peut cycler éternellemen
t:
\end_layout
\begin_layout Example*
\begin_inset CommandInset citation
LatexCommand cite
after "p. 31"
key "Chvatal_LP"
\end_inset
Système cyclant en 6 itérations avec la stratégie:
\end_layout
\begin_deeper
\begin_layout Itemize
Choix de la variable entrante avec le coefficient dans l'expression de
\begin_inset Formula $z$
\end_inset
le plus fort
\end_layout
\begin_layout Itemize
Choix de la variable sortante avec le plus petit index
\end_layout
\begin_layout LyX-Code
Chvatal31 := [[0.5*x1 - 5.5*x2 - 2.5*x3 + 9*x4 <= 0,
\end_layout
\begin_layout LyX-Code
0.5*x1 - 1.5*x2 - 0.5*x3 + x4 <= 0,
\end_layout
\begin_layout LyX-Code
x1 <= 1],
\end_layout
\begin_layout LyX-Code
10*x1 - 57*x2 - 9*x3 - 24*x4,
\end_layout
\begin_layout LyX-Code
NonNegative]:
\end_layout
\begin_layout LyX-Code
t0 := linopt::Transparent(Chvatal31);
\end_layout
\begin_layout LyX-Code
t1 := linopt::Transparent::userstep(t0, slk[1], x1);
\end_layout
\begin_layout LyX-Code
t2 := linopt::Transparent::userstep(t1, slk[2], x2);
\end_layout
\begin_layout LyX-Code
t3 := linopt::Transparent::userstep(t2, x1, x3);
\end_layout
\begin_layout LyX-Code
t4 := linopt::Transparent::userstep(t3, x2, x4);
\end_layout
\begin_layout LyX-Code
t5 := linopt::Transparent::userstep(t4, x3, slk[1]);
\end_layout
\begin_layout LyX-Code
t6 := linopt::Transparent::userstep(t5, x4, slk[2]);
\end_layout
\end_deeper
\begin_layout Standard
Comment garantir que l'algorithme ne cyclera pas ?
\end_layout
\begin_layout Itemize
Méthode des perturbations
\end_layout
\begin_layout Itemize
La méthode du plus petit index
\end_layout
\begin_deeper
\begin_layout Theorem*
L'algorithme du simplexe termine si, lorsqu'il y a ambiguïté sur le choix
de la variable entrante ou sortante, on choisit toujours la variable de
plus petit index.
\end_layout
\begin_layout Standard
Cette méthode est simple et élégante.
\end_layout
\begin_layout Standard
Par contre, elle empêche toute stratégie pour faire converger l'algorithme
plus vite.
\end_layout
\end_deeper
\begin_layout Itemize
Méthodes intermédiaires
\end_layout
\begin_layout Subsection
Initialisation
\end_layout
\begin_layout Standard
Pour le moment, l'algorithme du simplexe nécessite de partir d'un tableau
faisable.
\end_layout
\begin_layout Problem*
Dans le cas général, comment se ramener à un tableau faisable?
\end_layout
\begin_layout Problem*
Le système pourrait même ne pas avoir de solution!
\end_layout
\begin_layout Example*
\begin_inset CommandInset citation
LatexCommand cite
after "p. 39"
key "Chvatal_LP"
\end_inset
Système
\begin_inset Formula $P_{1}$
\end_inset
:
\end_layout
\begin_layout Example*
Maximiser:
\begin_inset Formula $x_{1}-x_{2}+x_{3}$
\end_inset
\end_layout
\begin_layout Example*
Sous les contraintes:
\end_layout
\begin_layout Example*
\begin_inset Formula $2x_{1}-x_{2}+2x_{3}\leq4$
\end_inset
\end_layout
\begin_layout Example*
\begin_inset Formula $2x_{1}-3x_{2}+x_{3}\leq-5$
\end_inset
\end_layout
\begin_layout Example*
\begin_inset Formula $-x_{1}+x_{2}-2x_{3}\leq-1$
\end_inset
\end_layout
\begin_layout Example*
\begin_inset Formula $x_{1},x_{2},x_{3}\geq0$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\backslash
solution
\end_layout
\end_inset
\end_layout
\begin_layout Example*
Introduction d'un
\emph on
système
\emph default
auxiliaire
\begin_inset Formula $P_{0}$
\end_inset
pour déterminer si
\begin_inset Formula $P$
\end_inset
est faisable:
\end_layout
\begin_layout Example*
Maximiser:
\begin_inset Formula $-x_{0}$
\end_inset
\end_layout
\begin_layout Example*
Sous les contraintes:
\end_layout
\begin_layout Example*
\begin_inset Formula $2x_{1}-x_{2}+2x_{3}-x_{0}\leq4$
\end_inset
\end_layout
\begin_layout Example*
\begin_inset Formula $2x_{1}-3x_{2}+x_{3}-x_{0}\leq-5$
\end_inset
\end_layout
\begin_layout Example*
\begin_inset Formula $-x_{1}+x_{2}-2x_{3}-x_{0}\leq-1$
\end_inset
\end_layout
\begin_layout Example*
\begin_inset Formula $x_{0},x_{1},x_{2},x_{3}\geq0$
\end_inset
\end_layout
\begin_layout Example*
Remarques:
\end_layout
\begin_deeper
\begin_layout Itemize
\emph on
\begin_inset Formula $P_{0}$
\end_inset
est faisable (prendre
\begin_inset Formula $x_{0}$
\end_inset
suffisamment grand);
\end_layout
\begin_layout Itemize
\emph on
Les solutions faisables de
\begin_inset Formula $P$
\end_inset
correspondent aux solutions faisables de
\begin_inset Formula $P_{0}$
\end_inset
avec
\begin_inset Formula $x_{0}=0$
\end_inset
;
\end_layout
\begin_layout Itemize
\emph on
\begin_inset Formula $P$
\end_inset
est faisable si et seulement si
\begin_inset Formula $P_{0}$
\end_inset
a une solution faisable avec
\begin_inset Formula $x_{0}=0$
\end_inset
.
\end_layout
\end_deeper
\begin_layout Example*
Étudions ce nouveau système:
\end_layout
\begin_deeper
\begin_layout LyX-Code
Chvatal40 := [[ -x1 + x2 - 2*x3 - x0 <= -1,
\end_layout
\begin_layout LyX-Code
2*x1 - 3*x2 + x3 - x0 <= -5,
\end_layout
\begin_layout LyX-Code
2*x1 - x2 + 2*x3 - x0 <= 4],
\end_layout
\begin_layout LyX-Code
-x0,
\end_layout
\begin_layout LyX-Code
NonNegative]:
\end_layout
\begin_layout LyX-Code
t0:=linopt::Transparent(Chvatal40);
\end_layout
\begin_layout LyX-Code
t1:=linopt::Transparent::userstep(t0, slk[2], x0);
\end_layout
\begin_layout LyX-Code
t2:=linopt::Transparent::userstep(t1, slk[1], x2);
\end_layout
\begin_layout LyX-Code
t3:=linopt::Transparent::userstep(t2, x0, x3);
\end_layout
\end_deeper
\begin_layout Example*
Maintenant, nous savons que le système
\begin_inset Formula $P$
\end_inset
est faisable.
\end_layout
\begin_layout Example*
En fait, en éliminant
\begin_inset Formula $x_{0}$
\end_inset
on obtient même un tableau faisable pour
\begin_inset Formula $P$
\end_inset
!
\end_layout
\begin_layout Standard
Algorithme du simplexe en deux phases pour résoudre un problème
\begin_inset Formula $P$
\end_inset
sous forme standard:
\end_layout
\begin_layout Standard
Phase I:
\end_layout
\begin_layout Enumerate
Si
\begin_inset Formula $(0,\ldots,0)$
\end_inset
est solution faisable de
\begin_inset Formula $P$
\end_inset
, on passe directement à la phase II.
\end_layout
\begin_layout Enumerate
Définir un problème auxiliaire
\begin_inset Formula $P_{0}$
\end_inset
.
\end_layout
\begin_layout Enumerate
Le premier tableau pour
\begin_inset Formula $P_{0}$
\end_inset
est infaisable.
\end_layout
\begin_layout Enumerate
Le rendre faisable par un pivot approprié de
\begin_inset Formula $x_{0}$
\end_inset
.
\end_layout
\begin_layout Enumerate
Appliquer le simplexe habituel:
\end_layout
\begin_deeper
\begin_layout Enumerate
Si à une étape donnée,
\begin_inset Formula $x_{0}$
\end_inset
peut sortir de la base, le faire en priorité:
\end_layout
\begin_deeper
\begin_layout Standard
En effet, il y a une solution faisable avec
\begin_inset Formula $x_{0}=0$
\end_inset
, et on peut passer en phase II.
\end_layout
\end_deeper
\begin_layout Enumerate
Si à une étape donnée on atteint une solution optimale:
\end_layout
\begin_deeper
\begin_layout Enumerate
Si
\begin_inset Formula $x_{0}$
\end_inset
n'est pas basique:
\end_layout
\begin_deeper
\begin_layout Standard
Il y a une solution faisable avec
\begin_inset Formula $x_{0}=0$
\end_inset
.
On peut donc passer en phase II.
\end_layout
\end_deeper
\begin_layout Enumerate
Si
\begin_inset Formula $x_{0}$
\end_inset
est basique et
\begin_inset Formula $z_{0}<0$
\end_inset
:
\end_layout
\begin_deeper
\begin_layout Standard
\begin_inset Formula $P$
\end_inset
est infaisable, et on s'arrête.
\end_layout
\end_deeper
\begin_layout Enumerate
Sinon
\begin_inset Formula $x_{0}$
\end_inset
est basique et
\begin_inset Formula $z_{0}=0$
\end_inset
:
\end_layout
\begin_deeper
\begin_layout Standard
Situation impossible si on fait toujours sortir
\begin_inset Formula $x_{0}$
\end_inset
en priorité de la base.
\end_layout
\end_deeper
\end_deeper
\end_deeper
\begin_layout Enumerate
Tirer de
\begin_inset Formula $P_{0}$
\end_inset
un tableau faisable pour
\begin_inset Formula $P$
\end_inset
;
\end_layout
\begin_layout Standard
Phase II:
\end_layout
\begin_layout Enumerate
Appliquer le simplexe habituel à partir du tableau donné par
\begin_inset Formula $P_{0}$
\end_inset
.
\end_layout
\begin_layout Exercise*
\begin_inset CommandInset citation
LatexCommand cite
after "ex 3.9a p. 44"
key "Chvatal_LP"
\end_inset
\end_layout
\begin_layout Exercise*
Maximiser
\begin_inset Formula $3x_{1}+x_{2}$
\end_inset
\end_layout
\begin_layout Exercise*
Sous les contraintes:
\end_layout
\begin_layout Exercise*
\begin_inset Formula $x_{1}-x_{2}\leq-1$
\end_inset
\end_layout
\begin_layout Exercise*
\begin_inset Formula $-x_{1}-x_{2}\leq-3$
\end_inset
\end_layout
\begin_layout Exercise*
\begin_inset Formula $2x_{1}+x_{2}\leq4$
\end_inset
\end_layout
\begin_layout Exercise*
\begin_inset Formula $x_{1},x_{2}\geq0$
\end_inset
\end_layout
\begin_layout LyX-Code
t0:=linopt::Transparent(Chvatal44_39a0)
\end_layout
\begin_layout LyX-Code
t1:=linopt::Transparent::userstep(t0, slk[2], x0)
\end_layout
\begin_layout LyX-Code
t2:=linopt::Transparent::userstep(t1, slk[1], x1)
\end_layout
\begin_layout LyX-Code
t3:=linopt::Transparent::userstep(t2, x0, x2)
\end_layout
\begin_layout LyX-Code
t0:=linopt::Transparent(Chvatal44_39a)
\end_layout
\begin_layout LyX-Code
t1:=linopt::Transparent::userstep(t0, slk[1], x1)
\end_layout
\begin_layout LyX-Code
t2:=linopt::Transparent::userstep(t1, slk[2], x2)
\end_layout
\begin_layout LyX-Code
t3:=linopt::Transparent::userstep(t2, slk[3], slk[2])
\end_layout
\begin_layout Subsection
Le théorème fondamental de la programmation linéaire
\end_layout
\begin_layout Theorem*
Tout programme linéaire
\begin_inset Formula $P$
\end_inset
sous forme standard a l'une des propriétés suivantes:
\end_layout
\begin_layout Enumerate
Si
\begin_inset Formula $P$
\end_inset
n'a pas de solutions optimales, alors
\begin_inset Formula $P$
\end_inset
est infaisable ou non borné;
\end_layout
\begin_layout Enumerate
Si
\begin_inset Formula $P$
\end_inset
a une solutions faisable, alors
\begin_inset Formula $P$
\end_inset
a une solution basique faisable;
\end_layout
\begin_layout Enumerate
Si
\begin_inset Formula $P$
\end_inset
a une solution optimale, alors
\begin_inset Formula $P$
\end_inset
a une solution basique optimale.
\end_layout
\begin_layout Chapter
Problèmes de flot maximum
\end_layout
\begin_layout Section
Introduction
\end_layout
\begin_layout Definition*
\emph on
+++Problème de flot max:
\end_layout
\begin_deeper
\begin_layout Itemize
Réseau avec source et puits
\end_layout
\begin_layout Itemize
Pas de coûts sur les arcs
\end_layout
\begin_layout Itemize
Contraintes de capacités sur les arcs
\end_layout
\begin_layout Itemize
Production et consommation nulle sur chaque noeud intermédiaire
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../../RO/Notes/flot.eps
lyxscale 300
width 100col%
rotateOrigin center
\end_inset
\end_layout
\end_deeper
\begin_layout Definition*
Objectif:
\end_layout
\begin_layout Definition*
Maximiser le
\emph on
volume
\emph default
du flot, c'est-à-dire la quantité transportée entre
\begin_inset Formula $s$
\end_inset
et
\begin_inset Formula $p$
\end_inset
.
\end_layout
\begin_layout Example*
Un dimanche soir, maximiser le nombre de voitures allant d'Albertville à
Lyon, en les répartissant entre les différentes routes possibles.
\end_layout
\begin_layout Exercise*
Mettre le problème de flot dessiné ci-dessus sous forme de programme linéaire.
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Clairement, cela se généralise à tout problème de flot max.
\end_layout
\begin_layout Problem*
Que peut-on en déduire ?
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
\end_layout
\begin_layout Itemize
On a un algorithme de résolution (simplexe)
\end_layout
\begin_layout Itemize
On doit bien avoir une dualité!
\end_layout
\begin_layout Section
Coupes dans un problème de flot
\end_layout
\begin_layout Definition*
Une
\emph on
coupe
\emph default
\begin_inset Formula $C$
\end_inset
dans un réseau est un ensemble de sommets du réseau contenant la source.
\end_layout
\begin_layout Definition*
La capacité de la coupe
\begin_inset Formula $C$
\end_inset
est la somme des capacités des arrêtes sortantes de
\begin_inset Formula $C$
\end_inset
.
\end_layout
\begin_layout Example*
Dans notre réseau, la coupe
\begin_inset Formula $C=\left\{ s\right\} $
\end_inset
est de capacité
\begin_inset Formula $5$
\end_inset
.
\end_layout
\begin_deeper
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../../RO/Notes/flot.eps
lyxscale 300
width 100col%
rotateOrigin center
\end_inset
\end_layout
\end_deeper
\begin_layout Exercise*
Quelle est la capacité de la coupe
\begin_inset Formula $C=\left\{ s,i_{2},i_{3}\right\} $
\end_inset
?
\end_layout
\begin_layout Exercise*
Que peut-on en déduire sur la valeur d'un flot ?
\end_layout
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\backslash
solution
\end_layout
\end_inset
\end_layout
\begin_layout Proposition*
Pour toute coupe
\begin_inset Formula $C$
\end_inset
et tout flot
\begin_inset Formula $F$
\end_inset
dans un réseau, la capacité
\begin_inset Formula $\left|C\right|$
\end_inset
de la coupe est supérieure au volume
\begin_inset Formula $\left|F\right|$
\end_inset
du flot:
\begin_inset Formula $\left|C\right|\geq\left|F\right|$
\end_inset
.
\end_layout
\begin_layout Exercise*
Chercher un flot maximal et une coupe minimal dans notre exemple?
\end_layout
\begin_layout Exercise*
Que peut-on dire?
\end_layout
\begin_layout Section
Algorithme de Ford-Fulkerson
\end_layout
\begin_layout Standard
Nous allons maintenant donner un algorithme qui permet de calculer un flot
maximal.
\end_layout
\begin_layout Standard
Mieux, comme l'algorithme du simplexe, cet algorithme va donner des résultats
théoriques!
\end_layout
\begin_layout Example*
On veut transporter le plus grand nombre possible de voyageurs de San-Francisco
à New-York, sachant qu'il ne reste que quelques places dans les avions
entre les villes suivantes:
\end_layout
\begin_deeper
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../../RO/Notes/flot-voyageurs.eps
lyxscale 300
width 100col%
rotateOrigin center
\end_inset
\end_layout
\end_deeper
\begin_layout Definition*
Soit
\begin_inset Formula $R$
\end_inset
un réseau, et
\begin_inset Formula $F$
\end_inset
un flot donné dans ce réseau.
\end_layout
\begin_layout Definition*
Un chemin allant de la source
\begin_inset Formula $s$
\end_inset
au puits
\begin_inset Formula $p$
\end_inset
est
\emph on
\begin_inset Formula $F$
\end_inset
-augmentant
\emph default
si pour chaque arête
\begin_inset Formula $ij$
\end_inset
du chemin on a:
\end_layout
\begin_deeper
\begin_layout Itemize
\begin_inset Formula $x_{ij}0$
\end_inset
si l'arc
\begin_inset Formula $ij$
\end_inset
est dans le sens inverse du réseau.
\end_layout
\end_deeper
\begin_layout Standard
À partir d'un chemin
\begin_inset Formula $F$
\end_inset
-augmentant, on peut construire un nouveau flot
\begin_inset Formula $F'$
\end_inset
qui sera de volume strictement plus gros.
\end_layout
\begin_layout Standard
Le principe de l'algorithme de Ford-Fulkerson est de partir d'un flot
\begin_inset Formula $F$
\end_inset
quelconque, et de l'améliorer itérativement en recherchant des chemins
\begin_inset Formula $F$
\end_inset
-augmentant.
\end_layout
\begin_layout Standard
À chaque étape, la recherche d'un chemin
\begin_inset Formula $F$
\end_inset
-augmentant se fait par un parcours en profondeur, de manière similaire
à la recherche d'un chemin
\begin_inset Formula $M$
\end_inset
-augmentant dans un graphe biparti.
Si cette recherche échoue, elle dévoile une coupe de capacité égale au
flot, ce qui donne un certificat d'optimalité du flot.
\end_layout
\begin_layout Remark
On peut toujours initialiser l'algorithme avec un flot nul.
\end_layout
\begin_layout Remark
Si toutes les capacités sont entières et finies, chaque itération augmente
le flot d'au moins
\begin_inset Formula $1$
\end_inset
.
Cet algorithme ne peut donc pas cycler, et il termine en un nombre fini
d'étapes.
\end_layout
\begin_layout Remark
Avec une mauvaise stratégie, et des capacités infinies ou non-entières,
l'algorithme peut ne pas terminer.
\end_layout
\begin_layout Remark
\begin_inset Graphics
filename ../../RO/Notes/flot-mauvais.eps
lyxscale 300
display false
width 50col%
rotateOrigin center
\end_inset
\end_layout
\begin_layout Remark
Avec une stratégie convenable, cet algorithme est en fait polynomial, en
\begin_inset Formula $O\left(n^{3}\right)$
\end_inset
, même si les capacités sont infinies ou non entières.
\end_layout
\begin_layout Remark
Pour les réseaux avec peu d'arcs, il y a des algorithmes plus compliqués
qui permettent d'obtenir d'encore meilleurs bornes.
Cf.
\begin_inset CommandInset citation
LatexCommand cite
after "p.~369"
key "Chvatal_LP"
\end_inset
pour les détails.
\end_layout
\begin_layout Section
Conséquences de l'algorithme de Ford-Fulkerson
\end_layout
\begin_layout Subsection
Théorème de dualité min-max
\end_layout
\begin_layout Theorem*
(Coupe min-Flot max) Dans un réseau, le volume maximal d'un flot est égal
à la capacité minimale d'une coupe.
\end_layout
\begin_layout Standard
Ce théorème est un cas particulier du théorème de dualité de la programmation
linéaire.
\end_layout
\begin_layout Subsection
Théorème d'intégralité
\end_layout
\begin_layout Standard
Dans notre exemple, on veut transporter des personnes
\emph on
entières
\emph default
autant que possible!
\end_layout
\begin_layout Standard
Qu'aurait-il pu se passer si l'on avait utilisé l'algorithme du simplexe?
\end_layout
\begin_layout Standard
Qu'a t-on obtenu avec l'algorithme de Ford-Fulkerson?
\end_layout
\begin_layout Standard
Est-ce un accident?
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
\end_layout
\begin_layout Theorem*
(dit d'intégralité) Soit
\begin_inset Formula $P$
\end_inset
un problème de flot où les contraintes sont entières.
Alors:
\end_layout
\begin_deeper
\begin_layout Enumerate
Si
\begin_inset Formula $P$
\end_inset
a une solution, alors il a une solution à coefficients entiers;
\end_layout
\begin_layout Enumerate
Si
\begin_inset Formula $P$
\end_inset
a une solution optimale, alors il a une solution optimale à coefficients
entiers.
\end_layout
\end_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\end_inset
\end_layout
\begin_layout Proof
La solution initiale
\begin_inset Formula $0$
\end_inset
est à coefficients entiers
\end_layout
\begin_layout Proof
À chaque étape, l'amélioration le long du chemin augmentant est entière
ou infinie.
\end_layout
\begin_layout Standard
Le théorème d'intégralité est assez simple.
Alors quel est son intérêt ?
\end_layout
\begin_layout Standard
Ce que dit fondamentalement le théorème d'intégralité, c'est que dans certains
cas les méthodes de programmation linéaire peuvent être utilisées pour
résoudre des problèmes purement combinatoire, ce qui est loin d'être trivial!
\end_layout
\begin_layout Standard
C'est le sujet de la
\emph on
combinatoire polyhédrale
\emph default
.
On verra quelques exemples la semaine prochaine.
\end_layout
\begin_layout Subsection
Combinatoire polyhédrale: quelques exemples
\end_layout
\begin_layout Subsubsection
Couvertures et couplages dans les graphes bipartis
\end_layout
\begin_layout Standard
On va maintenant regarder une application de la programmation linéaire pour
étudier des graphes non orientés comme le suivant:
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../../RO/Notes/graphe.eps
width 75col%
rotateOrigin center
\end_inset
\end_layout
\begin_layout Standard
Une
\emph on
couverture
\emph default
\begin_inset Formula $C$
\end_inset
de ce graphe est un ensemble de sommets qui touchent toutes les arêtes,
comme par exemple
\begin_inset Formula $C:=\left\{ 1,3,4,7,8\right\} $
\end_inset
:
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../../RO/Notes/graphe-couverture.eps
width 75col%
rotateOrigin center
\end_inset
\end_layout
\begin_layout Example
On a
\begin_inset Formula $8$
\end_inset
petits villages reliés par des routes.
En cas d'accident de la route, on veut que les pompiers puissent intervenir
rapidement.
Le prefet impose que lorsqu'une route relie deux villages, il y ait une
caserne de pompier dans au moins l'un des deux villages.
Évidemment le budget est serré, donc on veut construire des casernes de
pompier dans un nombre minimal de villages.
\end_layout
\begin_layout Example
Modélisation: Chaque village est représenté par un sommet du graphe précédent,
les arêtes représentant les routes.
Résoudre notre problème revient à chercher une couverture de taille minimale
du graphe.
\end_layout
\begin_layout Standard
Un
\emph on
couplage
\emph default
\begin_inset Formula $M$
\end_inset
de ce graphe est un ensemble d'arêtes qui ne se touchent pas, comme par
exemple
\begin_inset Formula $M:=\left\{ \left\{ 1,3\right\} ,\left\{ 4,5\right\} ,\left\{ 7,8\right\} \right\} $
\end_inset
:
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../../RO/Notes/graphe-couplage.eps
width 75col%
rotateOrigin center
\end_inset
\end_layout
\begin_layout Example
On veut loger un groupe de
\begin_inset Formula $8$
\end_inset
personnes dans un hotel, avec des chambres simples et doubles.
Pour minimiser les dépenses, on utiliser le maximum de chambres doubles.
D'un autre côté on ne veut pas forcer deux personnes qui ne se connaissent
pas bien à partager une chambre.
\end_layout
\begin_layout Example
Modélisation: chaque sommet du graphe précédent représente une personne,
et chaque arête relie deux personnes qui se connaissent bien.
Résoudre notre problème revient alors à rechercher un couplage de taille
maximale dans le graphe.
\end_layout
\begin_layout Exercise
Montrer que pour un couplage
\begin_inset Formula $M$
\end_inset
et une couverture
\begin_inset Formula $C$
\end_inset
d'un même graphe, on a toujours
\begin_inset Formula $\left|M\right|\leq\left|C\right|$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\backslash
solution
\end_layout
\end_inset
\end_layout
\begin_layout Proof
Comme
\begin_inset Formula $C$
\end_inset
est une couverture, chaque arête de
\begin_inset Formula $M$
\end_inset
devra être touchée par au moins un sommet dans
\begin_inset Formula $C$
\end_inset
.
De plus,
\begin_inset Formula $M$
\end_inset
étant un couplage, chaque sommet de
\begin_inset Formula $C$
\end_inset
touche au plus une arête de
\begin_inset Formula $M$
\end_inset
.
Donc, on a bien
\begin_inset Formula $\left|M\right|\leq\left|C\right|$
\end_inset
.
\end_layout
\begin_layout Problem
Peut-on trouver
\begin_inset Formula $M$
\end_inset
et
\begin_inset Formula $C$
\end_inset
de façon à avoir égalité ?
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\backslash
solution
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Dans notre exemple, non.
Par contre, on va voir que pour certaines classes de graphe, cela va être
vrai: on aura un théorème de dualité min-max.
Comme par hasard, c'est une conséquence de la programmation linéaire.
\end_layout
\begin_layout Standard
On appelle
\emph on
graphe biparti
\emph default
un graphe dont on peut partitioner les sommets en deux paquets
\begin_inset Formula $A$
\end_inset
et
\begin_inset Formula $B$
\end_inset
de sorte que toutes les arêtes soient entre
\begin_inset Formula $A$
\end_inset
et
\begin_inset Formula $B$
\end_inset
:
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../../RO/Notes/biparti.eps
width 25col%
rotateOrigin center
\end_inset
\end_layout
\begin_layout Exercise
On veut rechercher un couplage maximal du graphe précédent.
Montrer comment on peut résoudre ce problème en utilisant un problème de
flot.
\end_layout
\begin_layout Exercise
Utiliser l'algorithme de Ford-Fulkerson pour le résoudre.
\end_layout
\begin_layout Exercise
On appelle cela la
\begin_inset Quotes fld
\end_inset
Méthode du chemin augmentant
\begin_inset Quotes frd
\end_inset
.
Pourquoi?
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\backslash
solution
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Chaque solution entière
\begin_inset Formula $F$
\end_inset
du problème de flot correspond à un couplage
\begin_inset Formula $M$
\end_inset
du graphe biparti (les arêtes sur lesquelles passent une unité), avec
\begin_inset Formula $\left|M\right|=\left|F\right|$
\end_inset
.
Maximiser le flot revient à rechercher un couplage de taille max.
\emph on
Le théorème d'intégralité nous garanti que Ford-Fulkerson donnera bien une
solution optimale entière
\emph default
!
\end_layout
\begin_layout Exercise
Prendre maintenant la coupe minimale donnée par l'algorithme de Ford-Fulkerson,
et définir
\begin_inset Formula $C$
\end_inset
l'ensemble des sommets
\begin_inset Formula $a$
\end_inset
du graphe biparti tels que:
\end_layout
\begin_deeper
\begin_layout Itemize
soit
\begin_inset Formula $a$
\end_inset
est du côté de la source et
\begin_inset Formula $a$
\end_inset
n'est pas dans la coupe.
\end_layout
\begin_layout Itemize
soit
\begin_inset Formula $a$
\end_inset
est du côté du puit et
\begin_inset Formula $a$
\end_inset
est dans la coupe.
\end_layout
\begin_layout Enumerate
Que constate-t'on?
\end_layout
\end_deeper
\begin_layout Problem
Est-ce une coïncidence?
\end_layout
\begin_layout Exercise
Soit
\begin_inset Formula $G$
\end_inset
un graphe biparti,
\begin_inset Formula $M$
\end_inset
un couplage maximal donné par l'algorithme de Ford-Fulkerson, et
\begin_inset Formula $C$
\end_inset
l'ensemble de sommets obtenu comme ci-dessus.
Montrer que
\begin_inset Formula $C$
\end_inset
est une couverture et que
\begin_inset Formula $\left|M\right|=\left|C\right|$
\end_inset
.
\begin_inset Formula $ $
\end_inset
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%Écrire la démo
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\backslash
solution
\end_layout
\end_inset
\end_layout
\begin_layout Theorem
(König-Egerváry) Dans tout graphe biparti, la taille d'un couplage maximal
est égale à la taille d'une couverture minimale.
\end_layout
\begin_layout Standard
C'est une exemple typique où le théorème de dualité de la programmation
linéaire donne un théorème min-max reliant deux problèmes combinatoires
qui ne sont pas en lien direct a priori.
\end_layout
\begin_layout Exercise
Utiliser la méthode du chemin augmentant pour rechercher un couplage maximal
des graphes suivants (on pourra partir du couplage suggéré):
\end_layout
\begin_deeper
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../../RO/Notes/biparti2.eps
width 75col%
rotateOrigin center
\end_inset
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../../RO/Notes/couplage2.eps
width 75col%
rotateOrigin center
\end_inset
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename ../../RO/Notes/couplage-berge.eps
width 75col%
rotateOrigin center
\end_inset
\end_layout
\end_deeper
\begin_layout Subsubsection
Dualités chaînes/antichaînes dans les ordres partiels; théorème de Dilworth
\end_layout
\begin_layout Problem
\begin_inset CommandInset citation
LatexCommand cite
after "p. 338"
key "Chvatal_LP"
\end_inset
Problème des visites guidées.
Une compagnie propose
\begin_inset Formula $7$
\end_inset
visites guidées dans la journée, notées
\begin_inset Formula $a,b,c,d,e,f,g$
\end_inset
, dont les horaires et durées sont fixées.
Si une visite (par ex.
\begin_inset Formula $a$
\end_inset
) termine suffisament avant une autre (par exemple
\begin_inset Formula $c$
\end_inset
), le guide de la première visite peut enchaîner sur la deuxième; on notera
alors
\begin_inset Formula $a\rightarrow c$
\end_inset
.
En l'occurence, voici tous les enchaînements possibles:
\end_layout
\begin_layout Problem
\begin_inset Formula $a\rightarrow c,\textrm{ }a\rightarrow d,\textrm{ }a\rightarrow f,\textrm{ }a\rightarrow g,\textrm{ }b\rightarrow c,\textrm{ }b\rightarrow g,\textrm{ }d\rightarrow g,\textrm{ }e\rightarrow f,\textrm{ }e\rightarrow g$
\end_inset
.
\end_layout
\begin_deeper
\begin_layout Itemize
Combien faut-il de guides au minimum dans cet exemple ?
\end_layout
\begin_layout Itemize
Comment trouver le nombre minimum de guides nécessaires dans le cas général
?
\end_layout
\end_deeper
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
%
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
\backslash
solution
\end_layout
\end_inset
\end_layout
\begin_layout Definition
Soit
\begin_inset Formula $P=(E,<)$
\end_inset
un ordre partiel.
\end_layout
\begin_layout Definition
Une
\emph on
chaîne
\emph default
\begin_inset Formula $C$
\end_inset
de
\begin_inset Formula $P$
\end_inset
est un ensemble de sommets de
\begin_inset Formula $P$
\end_inset
deux à-deux comparables:
\begin_inset Formula
\[
x\in C\textrm{ et }y\in C\textrm{ }\Rightarrow\textrm{ }x