problemes-lineaires.tex

Contenu du fichier

\documentclass[12pt,a4paper]{article}

\addtolength{\voffset}{-2.5cm}
\addtolength{\textheight}{5cm}
\addtolength{\hoffset}{-1cm}
\addtolength{\textwidth}{2cm}

\usepackage[latin1]{inputenc}
\usepackage[french]{babel}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{multicol}
\usepackage{enumerate}
\usepackage{pst-tree}

\newcommand{\R}{\mathbb{R}}

\newcommand{\svBBNode}[5]{\
\TR{\psframebox{$\begin{array}{ccc}\pscirclebox{#2}&&#3\\&\mathbf{#1}&\\#5&&#4\end{array}$}}}

\setcounter{tocdepth}{1}

\renewcommand{\contentsname}{Table des mati�s}

\title{Programmation lin�re\\ Probl�s r�lus}
\author{S\'ebastien VERBOIS}
\date{Facult\'es universitaires Notre-Dame de la Paix\\
Institut d'Informatique\\
Novembre 2003}

\renewcommand{\theenumi}{\alph{enumi}}
\renewcommand{\labelenumi}{(\theenumi)}
\renewcommand{\theenumii}{\roman{enumii}}
\renewcommand{\labelenumii}{\theenumii.}

\begin{document}
\maketitle
\tableofcontents

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\section{Un probl� simple �eux variables}
\subsection{Mod� original}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z = 
5x_{1} + 4x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcr}
 & x_{1} &+& x_{2} &\le& 20\\
 & 2x_{1} &+& x_{2} &\le& 35\\
-& 3x_{1} &+& x_{2} &\le& 12\\
\multicolumn{4}{r}{x_{1}, x_{2}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\subsection{Probl� avec variables d'�rt}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z = 
5x_{1} + 4x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcrcr}
 & x_{1} &+& x_{2} &+& u_{1} & &  & &  & = & 20\\
 & 2x_{1} &+& x_{2} & &  &+& u_{2} & &  & = & 35\\
-& 3x_{1} &+& x_{2} & &  & &  &+& u_{3} & = & 12\\
\multicolumn{10}{r}{x_{1}, x_{2}, u_{1}, u_{2}, u_{3}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\subsection{R�lution par l'algorithme du simplexe}
\paragraph{Tableau 1 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & u_{3} & 1\\
\hline
1&-5&-4&0&0&0&0&z\\
\hline
0&1&1&1&0&0&20&u_{1}\\
0&2&1&0&1&0&35&u_{2}\\
0&-3&1&0&0&1&12&u_{3}\\
\hline
\end{array}
$\par
\paragraph{Tableau 2 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & u_{3} & 1\\
\hline
1&0&-\frac{3}{2}&0&\frac{5}{2}&0&\frac{175}{2}&z\\
\hline
0&0&\frac{1}{2}&1&-\frac{1}{2}&0&\frac{5}{2}&u_{1}\\
0&1&\frac{1}{2}&0&\frac{1}{2}&0&\frac{35}{2}&x_{1}\\
0&0&\frac{5}{2}&0&\frac{3}{2}&1&\frac{129}{2}&u_{3}\\
\hline
\end{array}
$\par

\paragraph{Tableau 3 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & u_{3} & 1\\
\hline
1&0&0&3&1&0&95&z\\
\hline
0&0&1&2&-1&0&5&x_{2}\\
0&1&0&-1&1&0&15&x_{1}\\
0&0&0&-5&4&1&52&u_{3}\\
\hline
\end{array}
$\par
\paragraph{Conclusion : }L'unique solution optimale est trouv�\par

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{   Un probl� �rois variables de d�sion (FSA)}
\subsection{Mod� original}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z = 
20x_{1} + 16x_{2} + 12x_{3}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcr}
 & x_{1} & &  & &  &\le& 400\\
 & 2x_{1} &+& x_{2} &+& x_{3} &\le& 1000\\
 & 2x_{1} &+& 2x_{2} &+& x_{3} &\le& 1600\\
\multicolumn{6}{r}{x_{1}, x_{2}, x_{3}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\subsection{Probl� avec variables d'�rt}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z = 
20x_{1} + 16x_{2} + 12x_{3}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcrcrcr}
 & x_{1} & &  & &  &+& u_{1} & &  & &  & = & 400\\
 & 2x_{1} &+& x_{2} &+& x_{3} & &  &+& u_{2} & &  & = & 1000\\
 & 2x_{1} &+& 2x_{2} &+& x_{3} & &  & &  &+& u_{3} & = & 1600\\
\multicolumn{12}{r}{x_{1}, x_{2}, x_{3}, u_{1}, u_{2}, u_{3}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\subsection{R�lution par l'algorithme du simplexe}
\paragraph{Tableau 1 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrrr|r|r}
z & x_{1} & x_{2} & x_{3} & u_{1} & u_{2} & u_{3} & 1\\
\hline
1&-20&-16&-12&0&0&0&0&z\\
\hline
0&1&0&0&1&0&0&400&u_{1}\\
0&2&1&1&0&1&0&1000&u_{2}\\
0&2&2&1&0&0&1&1600&u_{3}\\
\hline
\end{array}
$\par
\paragraph{Tableau 2 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrrr|r|r}
z & x_{1} & x_{2} & x_{3} & u_{1} & u_{2} & u_{3} & 1\\
\hline
1&0&-16&-12&20&0&0&8000&z\\
\hline
0&1&0&0&1&0&0&400&x_{1}\\
0&0&1&1&-2&1&0&200&u_{2}\\
0&0&2&1&-2&0&1&800&u_{3}\\
\hline
\end{array}
$\par
\paragraph{Tableau 3 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrrr|r|r}
z & x_{1} & x_{2} & x_{3} & u_{1} & u_{2} & u_{3} & 1\\
\hline
1&0&0&4&-12&16&0&11200&z\\
\hline
0&1&0&0&1&0&0&400&x_{1}\\
0&0&1&1&-2&1&0&200&x_{2}\\
0&0&0&-1&2&-2&1&400&u_{3}\\
\hline
\end{array}
$\par
\paragraph{Tableau 4 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrrr|r|r}
z & x_{1} & x_{2} & x_{3} & u_{1} & u_{2} & u_{3} & 1\\
\hline
1&0&0&-2&0&4&6&13600&z\\
\hline
0&1&0&\frac{1}{2}&0&1&-\frac{1}{2}&200&x_{1}\\
0&0&1&0&0&-1&1&600&x_{2}\\
0&0&0&-\frac{1}{2}&1&-1&\frac{1}{2}&200&u_{1}\\
\hline
\end{array}
$\par
\paragraph{Tableau 5 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrrr|r|r}
z & x_{1} & x_{2} & x_{3} & u_{1} & u_{2} & u_{3} & 1\\
\hline
1&4&0&0&0&8&4&14400&z\\
\hline
0&2&0&1&0&2&-1&400&x_{3}\\
0&0&1&0&0&-1&1&600&x_{2}\\
0&1&0&0&1&0&0&400&u_{1}\\
\hline
\end{array}
$\par
\paragraph{Conclusion : }L'unique solution optimale est trouv�\par
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{   Un probl� �eux phases (ITMP p169)}
\subsection{Mod� original}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\min & z = 
2x_{1} + 3x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcr}
 & 2x_{1} &+& x_{2} &\le& 16\\
 & x_{1} &+& 3x_{2} &\ge& 20\\
 & x_{1} &+& x_{2} &=& 10\\
\multicolumn{4}{r}{x_{1}, x_{2}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\subsection{Probl� avec variables d'�rt}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\min & z = 
2x_{1} + 3x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcr}
 & 2x_{1} &+& x_{2} &+& u_{1} & &  & = & 16\\
-& x_{1} &-& 3x_{2} & &  &+& u_{2} & = & -20\\
 & x_{1} &+& x_{2} & &  & &  & = & 10\\
\multicolumn{8}{r}{x_{1}, x_{2}, u_{1}, u_{2}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\subsection{Recherche d'une solution de base r�isable}
\subsubsection{Probl� auxilliaire}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\min & w = 
t_{1} + t_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcrcrcr}
 & 2x_{1} &+& x_{2} &+& u_{1} & &  & &  & &  & = & 16\\
 & x_{1} &+& 3x_{2} & &  &-& u_{2} &+& t_{1} & &  & = & 20\\
 & x_{1} &+& x_{2} & &  & &  & &  &+& t_{2} & = & 10\\
\multicolumn{12}{r}{x_{1}, x_{2}, u_{1}, u_{2}, t_{1}, t_{2}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\subsubsection{Equivalent canonique}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\min & w = 
30 - 2x_{1} - 4x_{2} + u_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcrcrcr}
 & 2x_{1} &+& x_{2} &+& u_{1} & &  & &  & &  & = & 16\\
 & x_{1} &+& 3x_{2} & &  &-& u_{2} &+& t_{1} & &  & = & 20\\
 & x_{1} &+& x_{2} & &  & &  & &  &+& t_{2} & = & 10\\
\multicolumn{12}{r}{x_{1}, x_{2}, u_{1}, u_{2}, t_{1}, t_{2}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\subsubsection{R�lution du probl� auxilliaire}
\paragraph{Tableau 1 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrrr|r|r}
w & x_{1} & x_{2} & u_{1} & u_{2} & t_{1} & t_{2} & 1\\
\hline
1&2&4&0&-1&0&0&30&w\\
\hline
0&2&1&1&0&0&0&16&u_{1}\\
0&1&3&0&-1&1&0&20&t_{1}\\
0&1&1&0&0&0&1&10&t_{2}\\
\hline
\end{array}
$\par
\paragraph{Tableau 2 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrrr|r|r}
w & x_{1} & x_{2} & u_{1} & u_{2} & t_{1} & t_{2} & 1\\
\hline
1&\frac{2}{3}&0&0&\frac{1}{3}&-\frac{4}{3}&0&\frac{10}{3}&w\\
\hline
0&\frac{5}{3}&0&1&\frac{1}{3}&-\frac{1}{3}&0&\frac{28}{3}&u_{1}\\
0&\frac{1}{3}&1&0&-\frac{1}{3}&\frac{1}{3}&0&\frac{20}{3}&x_{2}\\
0&\frac{2}{3}&0&0&\frac{1}{3}&-\frac{1}{3}&1&\frac{10}{3}&t_{2}\\
\hline
\end{array}
$\par
\paragraph{Tableau 3 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrrr|r|r}
w & x_{1} & x_{2} & u_{1} & u_{2} & t_{1} & t_{2} & 1\\
\hline
1&0&0&0&0&-1&-1&0&w\\
\hline
0&0&0&1&-\frac{1}{2}&\frac{1}{2}&-\frac{5}{2}&1&u_{1}\\
0&0&1&0&-\frac{1}{2}&\frac{1}{2}&-\frac{1}{2}&5&x_{2}\\
0&1&0&0&\frac{1}{2}&-\frac{1}{2}&\frac{3}{2}&5&x_{1}\\
\hline
\end{array}
$\par
\paragraph{Conclusion : }Une des solutions optimales est trouv�\par
\subsection{R�lution du probl� original}
\subsubsection{Equivalent canonique optimal du probl� auxilliaire}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\min & w = 
t_{1} + t_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcrcrcr}
 &  & &  & & u_{1} &-& \frac{1}{2}u_{2} &+& \frac{1}{2}t_{1} &-& \frac{5}{2}t_{2} & = & 1\\
 &  & & x_{2} & &  &-& \frac{1}{2}u_{2} &+& \frac{1}{2}t_{1} &-& \frac{1}{2}t_{2} & = & 5\\
 & x_{1} & &  & &  &+& \frac{1}{2}u_{2} &-& \frac{1}{2}t_{1} &+& \frac{3}{2}t_{2} & = & 5\\
\multicolumn{12}{r}{x_{1}, x_{2}, u_{1}, u_{2}, t_{1}, t_{2}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\subsubsection{Retour au probl� original}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\min & z = 
2x_{1} + 3x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcr}
 &  & &  & & u_{1} &-& \frac{1}{2}u_{2} & = & 1\\
 &  & & x_{2} & &  &-& \frac{1}{2}u_{2} & = & 5\\
 & x_{1} & &  & &  &+& \frac{1}{2}u_{2} & = & 5\\
\multicolumn{8}{r}{x_{1}, x_{2}, u_{1}, u_{2}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\subsubsection{Equivalent canonique r�isable du probl� original}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\min & z = 
25 + \frac{1}{2}u_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcr}
 &  & &  & & u_{1} &-& \frac{1}{2}u_{2} & = & 1\\
 &  & & x_{2} & &  &-& \frac{1}{2}u_{2} & = & 5\\
 & x_{1} & &  & &  &+& \frac{1}{2}u_{2} & = & 5\\
\multicolumn{8}{r}{x_{1}, x_{2}, u_{1}, u_{2}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\subsubsection{R�lution}
\paragraph{Tableau 1 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & 1\\
\hline
1&0&0&0&-\frac{1}{2}&25&z\\
\hline
0&0&0&1&-\frac{1}{2}&1&u_{1}\\
0&0&1&0&-\frac{1}{2}&5&x_{2}\\
0&1&0&0&\frac{1}{2}&5&x_{1}\\
\hline
\end{array}
$\par
\paragraph{Conclusion : }L'unique solution optimale est trouv�\par

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{   Un probl� dual (MOAD pIV20)}
\subsection{Mod� original}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\min & z = 
2x_{1} + 3x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcr}
 & 2x_{1} &+& x_{2} &-& x_{3} &\ge& 4\\
 & 3x_{1} &-& x_{2} &+& 5x_{3} &\ge& 5\\
\multicolumn{6}{r}{x_{1}, x_{2}, x_{3}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\subsection{Probl� avec variables d'�rt}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\min & z = 
2x_{1} + 3x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcrcr}
-& 2x_{1} &-& x_{2} &+& x_{3} &+& u_{1} & &  & = & -4\\
-& 3x_{1} &+& x_{2} &-& 5x_{3} & &  &+& u_{2} & = & -5\\
\multicolumn{10}{r}{x_{1}, x_{2}, x_{3}, u_{1}, u_{2}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\subsection{R�lution par l'algorithme dual du simplexe}
\paragraph{Tableau 1 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|r|r}
z & x_{1} & x_{2} & x_{3} & u_{1} & u_{2} & 1\\
\hline
1&-2&-3&0&0&0&0&z\\
\hline
0&-2&-1&1&1&0&-4&u_{1}\\
0&-3&1&-5&0&1&-5&u_{2}\\
\hline
\end{array}
$\par
\paragraph{Tableau 2 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|r|r}
z & x_{1} & x_{2} & x_{3} & u_{1} & u_{2} & 1\\
\hline
1&-2&-3&0&0&0&0&z\\
\hline
0&-\frac{13}{5}&-\frac{4}{5}&0&1&\frac{1}{5}&-5&u_{1}\\
0&\frac{3}{5}&-\frac{1}{5}&1&0&-\frac{1}{5}&1&x_{3}\\
\hline
\end{array}
$\par
\paragraph{Tableau 3 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|r|r}
z & x_{1} & x_{2} & x_{3} & u_{1} & u_{2} & 1\\
\hline
1&0&-\frac{31}{13}&0&-\frac{10}{13}&-\frac{2}{13}&\frac{50}{13}&z\\
\hline
0&1&\frac{4}{13}&0&-\frac{5}{13}&-\frac{1}{13}&\frac{25}{13}&x_{1}\\
0&0&-\frac{5}{13}&1&\frac{3}{13}&-\frac{2}{13}&-\frac{2}{13}&x_{3}\\
\hline
\end{array}
$\par
\paragraph{Tableau 4 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|r|r}
z & x_{1} & x_{2} & x_{3} & u_{1} & u_{2} & 1\\
\hline
1&0&-2&-1&-1&0&4&z\\
\hline
0&1&\frac{1}{2}&-\frac{1}{2}&-\frac{1}{2}&0&2&x_{1}\\
0&0&\frac{5}{2}&-\frac{13}{2}&-\frac{3}{2}&1&1&u_{2}\\
\hline
\end{array}
$\par
\paragraph{Conclusion : }L'unique solution optimale est trouv�\par

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Un probl� en nombres entiers (ITMP p516)}
\subsection{Mod� original}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z = 
8x_{1} + 5x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcr}
 & x_{1} &+& x_{2} &\le& 6\\
 & 9x_{1} &+& 5x_{2} &\le& 45\\
\multicolumn{4}{r}{x_{1}, x_{2}} & \ge & 0\\
\multicolumn{6}{r}{x_{1}, x_{2} \mbox{ entiers}}
\end{array} \right.
\end{array}}
$\par

\subsection{Probl� relax�S$}
\subsubsection{Probl� avec variables d'�rt}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z = 
8x_{1} + 5x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcr}
 & x_{1} &+& x_{2} &+& u_{1} & &  & = & 6\\
 & 9x_{1} &+& 5x_{2} & &  &+& u_{2} & = & 45\\
\multicolumn{8}{r}{x_{1}, x_{2}, u_{1}, u_{2}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\subsubsection{R�lution par l'algorithme du simplexe}
\paragraph{Tableau 1 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & 1\\
\hline
1&-8&-5&0&0&0&z\\
\hline
0&1&1&1&0&6&u_{1}\\
0&9&5&0&1&45&u_{2}\\
\hline
\end{array}
$\par
\paragraph{Tableau 2 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & 1\\
\hline
1&0&-\frac{5}{9}&0&\frac{8}{9}&40&z\\
\hline
0&0&\frac{4}{9}&1&-\frac{1}{9}&1&u_{1}\\
0&1&\frac{5}{9}&0&\frac{1}{9}&5&x_{1}\\
\hline
\end{array}
$\par
\paragraph{Tableau 3 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & 1\\
\hline
1&0&0&\frac{5}{4}&\frac{3}{4}&\frac{165}{4}&z\\
\hline
0&0&1&\frac{9}{4}&-\frac{1}{4}&\frac{9}{4}&x_{2}\\
0&1&0&-\frac{5}{4}&\frac{1}{4}&\frac{15}{4}&x_{1}\\
\hline
\end{array}
$\par
\paragraph{Conclusion : }L'unique solution optimale est trouv�\par
\subsection{Sous-probl� $S_2$}
\subsubsection{Probl� lin�re}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z = 
\frac{165}{4} - \frac{5}{4}u_{1} - \frac{3}{4}u_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcrcr}
 &  & & x_{2} &+& \frac{9}{4}u_{1} &-& \frac{1}{4}u_{2} & &  & = & \frac{9}{4}\\
 & x_{1} & &  &-& \frac{5}{4}u_{1} &+& \frac{1}{4}u_{2} & &  & = & \frac{15}{4}\\
-& x_{1} & &  & &  & &  &+& u_{3} & = & -4\\
\multicolumn{10}{r}{x_{1}, x_{2}, u_{1}, u_{2}, u_{3}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\subsubsection{R�lution par l'algorithme dual du simplexe}
\paragraph{Tableau 1 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & u_{3} & 1\\
\hline
1&0&0&\frac{5}{4}&\frac{3}{4}&0&\frac{165}{4}&z\\
\hline
0&0&1&\frac{9}{4}&-\frac{1}{4}&0&\frac{9}{4}&x_{2}\\
0&1&0&-\frac{5}{4}&\frac{1}{4}&0&\frac{15}{4}&x_{1}\\
0&0&0&-\frac{5}{4}&\frac{1}{4}&1&-\frac{1}{4}&u_{3}\\
\hline
\end{array}
$\par
\paragraph{Tableau 2 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & u_{3} & 1\\
\hline
1&0&0&0&1&1&41&z\\
\hline
0&0&1&0&\frac{1}{5}&\frac{9}{5}&\frac{9}{5}&x_{2}\\
0&1&0&0&0&-1&4&x_{1}\\
0&0&0&1&-\frac{1}{5}&-\frac{4}{5}&\frac{1}{5}&u_{1}\\
\hline
\end{array}
$\par
\paragraph{Conclusion : }L'unique solution optimale est trouv�\par
\subsection{Sous-probl� $S_{22}$}
\subsubsection{Probl� lin�re}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z = 
41 - u_{2} - u_{3}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcrcrcr}
 &  & & x_{2} & &  &+& \frac{1}{5}u_{2} &+& \frac{9}{5}u_{3} & &  & = & \frac{9}{5}\\
 & x_{1} & &  & &  & &  &-& u_{3} & &  & = & 4\\
 &  & &  & & u_{1} &-& \frac{1}{5}u_{2} &-& \frac{4}{5}u_{3} & &  & = & \frac{1}{5}\\
 &  &-& x_{2} & &  & &  & &  &+& u_{4} & = & -2\\
\multicolumn{12}{r}{x_{1}, x_{2}, u_{1}, u_{2}, u_{3}, u_{4}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\subsubsection{R�lution par l'algorithme dual du simplexe}
\paragraph{Tableau 1 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & u_{3} & u_{4} & 1\\
\hline
1&0&0&0&1&1&0&41&z\\
\hline
0&0&1&0&\frac{1}{5}&\frac{9}{5}&0&\frac{9}{5}&x_{2}\\
0&1&0&0&0&-1&0&4&x_{1}\\
0&0&0&1&-\frac{1}{5}&-\frac{4}{5}&0&\frac{1}{5}&u_{1}\\
0&0&0&0&\frac{1}{5}&\frac{9}{5}&1&-\frac{1}{5}&u_{4}\\
\hline
\end{array}
$\par
\paragraph{Conclusion : }Le probl� est irr�isable.\par
\subsection{Sous-probl� $S_{21}$}
\subsubsection{Probl� lin�re}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z = 
41 - u_{2} - u_{3}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcrcrcr}
 &  & & x_{2} & &  &+& \frac{1}{5}u_{2} &+& \frac{9}{5}u_{3} & &  & = & \frac{9}{5}\\
 & x_{1} & &  & &  & &  &-& u_{3} & &  & = & 4\\
 &  & &  & & u_{1} &-& \frac{1}{5}u_{2} &-& \frac{4}{5}u_{3} & &  & = & \frac{1}{5}\\
 &  & & x_{2} & &  & &  & &  &+& u_{4} & = & 1\\
\multicolumn{12}{r}{x_{1}, x_{2}, u_{1}, u_{2}, u_{3}, u_{4}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\subsubsection{R�lution par l'algorithme dual du simplexe}
\paragraph{Tableau 1 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & u_{3} & u_{4} & 1\\
\hline
1&0&0&0&1&1&0&41&z\\
\hline
0&0&1&0&\frac{1}{5}&\frac{9}{5}&0&\frac{9}{5}&x_{2}\\
0&1&0&0&0&-1&0&4&x_{1}\\
0&0&0&1&-\frac{1}{5}&-\frac{4}{5}&0&\frac{1}{5}&u_{1}\\
0&0&0&0&-\frac{1}{5}&-\frac{9}{5}&1&-\frac{4}{5}&u_{4}\\
\hline
\end{array}
$\par
\paragraph{Tableau 2 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & u_{3} & u_{4} & 1\\
\hline
1&0&0&0&\frac{8}{9}&0&\frac{5}{9}&\frac{365}{9}&z\\
\hline
0&0&1&0&0&0&1&1&x_{2}\\
0&1&0&0&\frac{1}{9}&0&-\frac{5}{9}&\frac{40}{9}&x_{1}\\
0&0&0&1&-\frac{1}{9}&0&-\frac{4}{9}&\frac{5}{9}&u_{1}\\
0&0&0&0&\frac{1}{9}&1&-\frac{5}{9}&\frac{4}{9}&u_{3}\\
\hline
\end{array}
$\par
\paragraph{Conclusion : }L'unique solution optimale est trouv�\par

\subsection{Sous-probl� $S_{212}$}
\subsubsection{Probl� lin�re}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z = 
\frac{365}{9} - \frac{8}{9}u_{2} - \frac{5}{9}u_{4}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcrcrcrcr}
 &  & & x_{2} & &  & &  & &  &+& u_{4} & &  & = & 1\\
 & x_{1} & &  & &  &+& \frac{1}{9}u_{2} & &  &-& \frac{5}{9}u_{4} & &  & = & \frac{40}{9}\\
 &  & &  & & u_{1} &-& \frac{1}{9}u_{2} & &  &-& \frac{4}{9}u_{4} & &  & = & \frac{5}{9}\\
 &  & &  & &  & & \frac{1}{9}u_{2} &+& u_{3} &-& \frac{5}{9}u_{4} & &  & = & \frac{4}{9}\\
-& x_{1} & &  & &  & &  & &  & &  &+& u_{5} & = & -5\\
\multicolumn{14}{r}{x_{1}, x_{2}, u_{1}, u_{2}, u_{3}, u_{4}, u_{5}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\subsubsection{R�lution par l'algorithme dual du simplexe}
\paragraph{Tableau 1 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & u_{3} & u_{4} & u_{5} & 1\\
\hline
1&0&0&0&\frac{8}{9}&0&\frac{5}{9}&0&\frac{365}{9}&z\\
\hline
0&0&1&0&0&0&1&0&1&x_{2}\\
0&1&0&0&\frac{1}{9}&0&-\frac{5}{9}&0&\frac{40}{9}&x_{1}\\
0&0&0&1&-\frac{1}{9}&0&-\frac{4}{9}&0&\frac{5}{9}&u_{1}\\
0&0&0&0&\frac{1}{9}&1&-\frac{5}{9}&0&\frac{4}{9}&u_{3}\\
0&0&0&0&\frac{1}{9}&0&-\frac{5}{9}&1&-\frac{5}{9}&u_{5}\\
\hline
\end{array}
$\par
\paragraph{Tableau 2 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & u_{3} & u_{4} & u_{5} & 1\\
\hline
1&0&0&0&1&0&0&1&40&z\\
\hline
0&0&1&0&\frac{1}{5}&0&0&\frac{9}{5}&0&x_{2}\\
0&1&0&0&0&0&0&-1&5&x_{1}\\
0&0&0&1&-\frac{1}{5}&0&0&-\frac{4}{5}&1&u_{1}\\
0&0&0&0&0&1&0&-1&1&u_{3}\\
0&0&0&0&-\frac{1}{5}&0&1&-\frac{9}{5}&1&u_{4}\\
\hline
\end{array}
$\par
\paragraph{Conclusion : }L'unique solution optimale est trouv�\par
\subsection{Sous-probl� $S_{211}$}
\subsubsection{Probl� lin�re}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z = 
\frac{365}{9} - \frac{8}{9}u_{2} - \frac{5}{9}u_{4}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcrcrcrcr}
 &  & & x_{2} & &  & &  & &  &+& u_{4} & &  & = & 1\\
 & x_{1} & &  & &  &+& \frac{1}{9}u_{2} & &  &-& \frac{5}{9}u_{4} & &  & = & \frac{40}{9}\\
 &  & &  & & u_{1} &-& \frac{1}{9}u_{2} & &  &-& \frac{4}{9}u_{4} & &  & = & \frac{5}{9}\\
 &  & &  & &  & & \frac{1}{9}u_{2} &+& u_{3} &-& \frac{5}{9}u_{4} & &  & = & \frac{4}{9}\\
 & x_{1} & &  & &  & &  & &  & &  &+& u_{5} & = & 4\\
\multicolumn{14}{r}{x_{1}, x_{2}, u_{1}, u_{2}, u_{3}, u_{4}, u_{5}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\subsubsection{R�lution par l'algorithme dual du simplexe}
\paragraph{Tableau 1 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & u_{3} & u_{4} & u_{5} & 1\\
\hline
1&0&0&0&\frac{8}{9}&0&\frac{5}{9}&0&\frac{365}{9}&z\\
\hline
0&0&1&0&0&0&1&0&1&x_{2}\\
0&1&0&0&\frac{1}{9}&0&-\frac{5}{9}&0&\frac{40}{9}&x_{1}\\
0&0&0&1&-\frac{1}{9}&0&-\frac{4}{9}&0&\frac{5}{9}&u_{1}\\
0&0&0&0&\frac{1}{9}&1&-\frac{5}{9}&0&\frac{4}{9}&u_{3}\\
0&0&0&0&-\frac{1}{9}&0&\frac{5}{9}&1&-\frac{4}{9}&u_{5}\\
\hline
\end{array}
$\par
\paragraph{Tableau 2 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & u_{3} & u_{4} & u_{5} & 1\\
\hline
1&0&0&0&0&0&5&8&37&z\\
\hline
0&0&1&0&0&0&1&0&1&x_{2}\\
0&1&0&0&0&0&0&1&4&x_{1}\\
0&0&0&1&0&0&-1&-1&1&u_{1}\\
0&0&0&0&0&1&0&1&0&u_{3}\\
0&0&0&0&1&0&-5&-9&4&u_{2}\\
\hline
\end{array}
$\par
\paragraph{Conclusion : }L'unique solution optimale est trouv�\par
\subsection{Sous-probl� $S_{1}$}
\subsubsection{Probl� lin�re}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z = 
\frac{165}{4} - \frac{5}{4}u_{1} - \frac{3}{4}u_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcrcr}
 &  & & x_{2} &+& \frac{9}{4}u_{1} &-& \frac{1}{4}u_{2} & &  & = & \frac{9}{4}\\
 & x_{1} & &  &-& \frac{5}{4}u_{1} &+& \frac{1}{4}u_{2} & &  & = & \frac{15}{4}\\
 & x_{1} & &  & &  & &  &+& u_{3} & = & 3\\
\multicolumn{10}{r}{x_{1}, x_{2}, u_{1}, u_{2}, u_{3}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\subsubsection{R�lution par l'algorithme dual du simplexe}
\paragraph{Tableau 1 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & u_{3} & 1\\
\hline
1&0&0&\frac{5}{4}&\frac{3}{4}&0&\frac{165}{4}&z\\
\hline
0&0&1&\frac{9}{4}&-\frac{1}{4}&0&\frac{9}{4}&x_{2}\\
0&1&0&-\frac{5}{4}&\frac{1}{4}&0&\frac{15}{4}&x_{1}\\
0&0&0&\frac{5}{4}&-\frac{1}{4}&1&-\frac{3}{4}&u_{3}\\
\hline
\end{array}
$\par
\paragraph{Tableau 2 : }
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & u_{3} & 1\\
\hline
1&0&0&5&0&3&39&z\\
\hline
0&0&1&1&0&-1&3&x_{2}\\
0&1&0&0&0&1&3&x_{1}\\
0&0&0&-5&1&-4&3&u_{2}\\
\hline
\end{array}
$\par
\paragraph{Conclusion : }L'unique solution optimale est trouv�\par

\subsection{Arbre de r�lution}

\begin{center}
\psset{levelsep=3cm,nodesep=0mm,tpos=0.5}
\pstree{\svBBNode{S}{1}{165/4}{-\infty}{ }}{
	\svBBNode{S_1}{7}{39}{39}{\times}\tlput{$x_1\le3$}
	\pstree{\svBBNode{S_2}{2}{41}{-\infty}{ }\trput{$x_1\ge4$}}{
      		\pstree{\svBBNode{S_{21}}{4}{365/9}{-\infty}{}\tlput{$x_2\le1$}}{
			\svBBNode{S_{211}}{6}{37}{37}{\times}\tlput{$x_1\le4$}
			\svBBNode{S_{212}}{5}{40}{40}{\times}\trput{$x_1\ge5$}
		}
      		\svBBNode{S_{22}}{3}{-\infty}{-\infty}{\times}\trput{$x_2\ge2$}
	 }
    	 
}
\end{center}
\paragraph{Conclusion : }L'unique solution optimale est trouv�au noeud $S_{212}$.\par

\end{document}