\section{Chapitre 8: La programmation linéaire}
\label{sec:ch8}

\subsection{Forme normale}
\label{sec:formenormale}

\begin{alignat*}{2}
  & \text{maximiser} && c^Tx \\
  & \text{sujet à} & \quad &
  \begin{aligned}[t]
    Ax& \leq b & \\
    x& \geq 0 &
  \end{aligned}
\end{alignat*}

Équivalences de problèmes:
\begin{itemize}
\item $\min c^Tx \iff \max (-c^T)x$
\item $a^Tx \geq k \iff (-a^T)x \leq -k$
\item $a^Tx = k \iff a^Tx \leq k \wedge a^Tx \geq k$
\item $x_i$ libre devient $x_i=x_i^{+} - x_i^{-}, \quad x_i^{+} \geq 0 \wedge x_i^{-} \geq 0$
\end{itemize}

\subsection{Polytope convexe}
\label{sec:polytopeconvexe}

L'espace des solutions d'un système d'inégalités linéaires forme un polytope convexe. Il est possible de résoudre graphiquement un programme linéaire. La solution se situe nécessairement sur un sommet. Si le problème a plus d'une solution, alors celle-ci est définie par une face, ce qui inclus les sommets.

Un espace est convexe le segment reliant deux point de cet espace est entièrement inclus dans l'espace. Combinaison convexe:

\begin{align}
  \alpha\vec{x}+(1-\alpha)\vec{y} \in S
\end{align}

Soit deux solutions valides $y$ et $z$, toute solution $\alpha\vec{y}+(1-\alpha)\vec{z}$ est aussi valide si $\alpha \in \left[ 0,1 \right]$

\subsection{Algorithme du simplexe}
\label{sec:simplexe}

\begin{itemize}
\item Exploite deux propriétés:
  \begin{itemize}
  \item Solution à un sommet du polytope
  \item Espace de recherche convexe
  \end{itemize}
\item Trouve une solution réalisable
\item Parcours les sommets du polytope
\item Variables d'écart: convertir les inéquations en équations en ajoutant une variable. Il y a une variable d'écart par contrainte du programme.
\item Solution initiale: débute avec une solution réalisable. Ce peux être $x_i=0$.
\item Solution de base: contient $m$ variables non-nulles dont les colonnes forment une base.
\item Solution réalisable de base: Solution de base qui satisfait toutes les équations avec des valeurs non négatives. Forment l'ensemble des sommets du polytope
\end{itemize}

Changement de base: Une variable entre dans la base en devenant positive et une autre quitte en devenant nulle

\begin{table}[ht]
\centering
\label{tab:simplexe}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
\textbf{$-c_1$} & \textbf{$-c_2$} & \textbf{$-c_3$} & \textbf{$\ldots$} & \textbf{$-c_n$} & \textbf{$v$} \\ \hline
$a_{11}$        & $a_{12}$        & $a_{13}$        & $\ldots$          & $a_{1n}$        & $b_1$        \\ \hline
$a_{21}$        & $a_{22}$        & $a_{23}$        & $\ldots$          & $a_{2n}$        & $b_2$        \\ \hline
$\ldots$        & $\ldots$        & $\ldots$        & $\ldots$          & $\ldots$        & $\ldots$     \\ \hline
$a_{m1}$        & $a_{m2}$        & $a_{m3}$        & $\ldots$          & $a_{mn}$        & $b_m$        \\ \hline
\end{tabular}
\caption{Tableau du simplexe}
\end{table}

Invariants du tableau:
\begin{itemize}
\item Les colonnes de la base ont une valeur nulle sauf une composante qui a une valeur de 1
\item Le coût d'une variable de la base est 0
\item La valeur objectif apparait dans le coin supérieur droit
\item La valeur des variables non-nulles apparait à la dernière colonne de droite. Ces valeurs sont non-négatives
\end{itemize}

Opération de pivot:
\begin{itemize}
\item Choix de la variable $x_j$ qui entre dans la base: coût négatif et valeur absolue la plus grande
\item On minimise le ratio $\frac{b_i}{a_{ij}}$ pour choisir le pivot.
\item On divise la rangée $i$ par $a_{ij}$
\item On soustrait $a_{kj}$ fois la rangée $i$ de la rangée $k$ pour que $a_{kj}$ devienne nul
\item On soustrait $c_j$ fois la rangée $i$ de la première rangée du tableau 
\end{itemize}

Lorsque tous les coefficients des variables de $-f(x)+k$ sont positifs, on a un minimum global. Cette solution réalisable de base est optimale.

Complexité moyenne en temps polynomial. Pire cas en temps exponentiel.

\subsection{Solution initiale}
\label{sec:solutioninitiale}

\begin{itemize}
\item Lorsqu'une valeur négative se trouve à droite de l'équation, il n'y a pas de solution de base réalisable.
\item On doit alors multiplier par -1 les deux côtés de cet équation et ajouter une variable temporaire à chaque équation linéaire.
\item On remplace la fonction objectif par la minimisation des variables temporaires.
\item Une solution réalisable de base optimale pour ce problème (le cout des variable temporaires est de 1) est une solution réalisable de base pour le problèmes original. Si on ne réussis pas à trouver de solution de base optimale, le problème n'est pas réalisable
\end{itemize}

Si toutes les valeurs de la colonne du pivot sont nulles ou négatives, la valeur objective tend vers l'infini. C'est un problème non borné.

\subsection{Chemin le plus court}
\label{sec:cheminpluscourt}

Premier modèle: une variable par arête, inéquations = contraintes de conservation de flot. La première équation est linéairement dépendande, on peut l'enlever.

\begin{align*}
  &\min
  \begin{bmatrix}
    2&4&1&5&1&2
  \end{bmatrix}
               \vec{x}\\
  &\text{s.t.}
  \begin{bmatrix}
    1&0&-1&-1&1&0\\
    0&1&1&0&-1&-1\\
    0&0&0&1&0&1
  \end{bmatrix}
               \begin{bmatrix}
                 x_{ab}\\
                 x_{ac}\\
                 x_{bc}\\
                 x_{bd}\\
                 x_{cb}\\
                 x_{cd}
               \end{bmatrix}
  =
  \begin{bmatrix}
    0\\
    0\\
    1
  \end{bmatrix}
\end{align*}

Deuxième modèle: bout de ficelle reliant les noeuds, on fixe $A$ en position 0 et on tire sur le noeud $D$. Une variable par noeud modélise la position du noeud. Une contrainte par arête pour limiter l'éloignement des noeuds.


\subsection{Dualité}
\label{sec:dualite}

Ces deux programmes linéaires sont équivalents:

Programme 1 (primal)

\begin{align*}
  &\min &c^Tx\\
  &s.t. &Ax=b\\
  &&x \geq 0
\end{align*}
Programme 2 (dual)

\begin{align*}
  &\max &b^Ty\\
  &s.t. &A^Ty \leq c\\
  &&y \in \R
\end{align*}

Comparaison des solutions réalisables

\begin{align*}
  A^Ty &\leq c & \text{Solution dual} \\
  y^TA &\leq c^T & \text{Transposée} \\
  y^TAx &\leq c¸Tx & \text{Mult. par}\ x\\
  y^TB &\leq c^Tx & \text{Solution primal}\\
  b^Ty &\leq c^Tx & \text{Propriété du produit scalaire}
\end{align*}

\paragraph{Matrice B}

\begin{itemize}
\item $B$ est la matrice formée des colonnes de la matrice $A$ associées aux variables de la base (prises dans l'ordre où les 1 apparaissent, de haut en bas).
\item $B^{-1}A$ est la matrice des coefficients du tableau dans son état final
\item $C_B$ est le coût associé aux variables de base
\item Le vecteur de coût est donnée par $c^T-c_B^TB^{-1}A \geq 0$
\item Si les deux solutions sont optimales, on a l'égalité $C^Tx = c+B^Tx_B = c_B^TB^{-1}b = y^Tb = b^Ty$
\end{itemize}

\paragraph{Généralisation}

\begin{table}[ht]
\centering
\label{tab:primaldual}
\begin{tabular}{l|l}
\textbf{Primal}       & \textbf{Dual}         \\
\hline
Équation              & Variable libre        \\
Inégalité             & Variable non-négative \\
Variable libre        & Équation              \\
Variable non-négative & inégalité             \\
minimisation          & maximisation         
\end{tabular}
\caption{Primal et dual}
\end{table}

\begin{itemize}
\item $E$: Contraintes d'égalité
\item $L$: Variables libres
\item $A[i]$: $i$e rangée de $A$
\end{itemize}


\begin{table}[ht]
\centering
\label{my-labeltab:primaldualeq}
\begin{tabular}{lllll}
     & $\min c^Tx$      &              &      & $\max b^Ty$        \\
s.t. & $A[i]x=b_i$      & $i \in E$    & s.t. & $y_i \in \R$       \\
     & $A[i]x \geq b_i$ & $i \notin E$ &      & $y_i \geq 0$       \\
     & $x_j \in \R$     & $j \in L$    &      & $A^T[j]y=c_j$      \\
     & $x_j \geq 0$     & $j \notin L$ &      & $A^T[j]y \leq c_j$
\end{tabular}
\caption{Primal et dual en équations}
\end{table}


\subsection{Programmation en nombres entiers}
\label{sec:nombresentiers}

\begin{alignat*}{2}
  & \text{maximiser} && c^Tx \\
  & \text{sujet à} & \quad &
  \begin{aligned}[t]
    Ax& \leq b & \\
    x& \in \N^{n} &
  \end{aligned}
\end{alignat*}

Deux techniques à utiliser après le simplexe:
\begin{itemize}
\item Fouille dans un arbre de recherche
  \begin{itemize}
  \item Ajout de deux branches pour les valeurs $x_i=v$ non entières
  \item $x_i \leq \floor{v}$, $x_i \geq \ceil{v}$
  \item La meilleure valeur objective $v^\star$ devient une borne minimale
  \end{itemize}
\item Coupes de Gomory
  \begin{itemize}
  \item Coupe: contrainte ajoutée à un programme linéaire
  \item Depuis le tableau du simplexe, on extrait une équation de la forme $x_i+\sum_{j \notin B}a_{i,j}x_j=b_i$.
  \item La coupe de Gomory prend la forme
    \begin{align}
      \sum_{j \notin B}(a_{i,j}-\floor{a_{i,j}})x_j-s=b_i-\floor{b_i}
    \end{align}
  \item Exemple:
    \begin{align}
      y+0.5s_1-0.5s_3&=2.5\\
      0.5s_1+0.5s_3-s_4&=0.5
    \end{align}
  \end{itemize}
\end{itemize}

\subsection{Matrices totalement unimodulaires}
\label{sec:matricestotalementunimod}

\begin{itemize}
\item Matrices totalement unimodulaires: chaque sous-matrice a un déterminant de -1,0 ou 1. Son adjointe a donc aussi seulement des -1,0 et 1. 
\item Si $A$ est inversible, alors sont inverse ne contient que des -1,0,1. Son inverse est donc une matrice entière.
\item $x_B=B^{-1}b$, $x$ sera entier.
\item Si $A$ est totalement unimodulaire et $b$ est un vecteur d'entier, alors la solution du simplexe sera entière
\item Si une sous-matrice d'un problème est unimodulaire, on peut résoudre les autres variables par Branch and Bound et ensuite utiliser le simplexe pour réduire la taille du problème
\end{itemize}

\paragraph{Matrice d'incidence d'un graphe}

\begin{align}
  A_{i,j} &= \begin{cases}
              1 &\text{si la destination de l'arete}\ j\ \text{est le noeud}\ i\\
              -1&\text{si l'origine de l'arete}\ j\ \text{est le noeud}\ i\\
              0 &sinon
            \end{cases}
\end{align}












%%% Local Variables:
%%% mode: latex
%%% TeX-master: "notes_de_cours"
%%% End: