slides-simplexe.tex

Contenu du fichier

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{M�ode du simplexe}
\newpage
\minitoc
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Un exemple �eux variables de d�sion}
\subsection{Probl� et repr�ntation graphique}
\begin{tabular}[c]{c}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z = 
x_{1} + 3x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcr}
 & x_{1} &+& x_{2} &\le& 14\\
-& 2x_{1} &+& 3x_{2} &\le& 12\\
 & 2x_{1} &-& x_{2} &\le& 12\\
\multicolumn{4}{r}{x_{1}, x_{2}} & \ge & 0
\end{array} \right.
\end{array}}
$\\
\\
$(x_1,x_2)^*=(6,8)$\\
$z^*=30$
\end{tabular}
\hspace{5mm} {
% PARAMETRES
  \psset{unit=0.25cm}
%\psset{arrowsize=3pt 3}
  \psset{arrowinset=0} \fontsize{7}{1}\selectfont
\begin{pspicture}[0.5](-7,-13)(16,16)
% AXES
%,labels=none
  \psaxes[Dx=2,Dy=2,tickstyle=top]{->}(0,0)(-7,-13)(15,15)
  \rput(16,0){$x_1$}\rput(0,16){$x_2$}
% CONTRAINTES
  \psline(0,14)(14,0) \psline(-6,0)(12,12) \psline(0,-12)(12,12)
  \pspolygon[linewidth=0pt,fillstyle=solid,fillcolor=lightgray](0,0)(0,4)(6,8)(8.66,5.33)(6,0)
% SBR
  \psdots*[dotstyle=*,dotscale=1.5](0,0)(0,4)(6,8)(8.66,5.33)(6,0)
% SBNR
  \psdots*[dotstyle=o,dotscale=1.5](-6,0)(0,14)(12,12)(14,0)(0,-12)
% OBJECTIF
  \psline[linestyle=dashed](-6,4)(12,-2)
  \psline[linestyle=dashed]{->}(-5,4)(-4.5,5.5)
\end{pspicture}
}

\subsection{Probl� sous forme standard}
Le probl�\hspace{1cm}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z = 
x_{1} + 3x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcr}
 & x_{1} &+& x_{2} &\le& 14\\
-& 2x_{1} &+& 3x_{2} &\le& 12\\
 & 2x_{1} &-& x_{2} &\le& 12\\
\multicolumn{4}{r}{x_{1}, x_{2}} & \ge & 0
\end{array} \right.
\end{array}}
$
\hspace{1cm}est �ivalent\\
au probl�\hspace{1cm}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z = 
x_{1} + 3x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcrcr}
 & x_{1} &+& x_{2} &+& u_{1} & &  & &  & = & 14\\
-& 2x_{1} &+& 3x_{2} & &  &+& u_{2} & &  & = & 12\\
 & 2x_{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}}
$.

\subsection{Solutions de base et solutions de base r�isables}
$$
{\renewcommand{\arraystretch}{1.1}\renewcommand{\arraycolsep}{4mm}
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
\text{S de B} & x_1 & x_2 & u_1 & u_2 & u_3 & \text{R} & z \\
\hline
\text{A} & 0 & 0 & 14 & 12 & 12 & \text{oui} & 0\\
\text{B} & 0 & 14 & 0 & -30 & 26 & \text{non} & /\\
\text{C} & 0 & 4 & 10 & 0 & 16 & \text{oui} & 12\\
\text{D} & 0 & -12 & 26 & 48 & 0 & \text{non} & /\\
\text{E} & 14 & 0 & 0 & 40 & -16 & \text{non} & /\\
\text{F} & -6 & 0 & 20 & 0 & 24 & \text{non} & /\\
\text{G} & 6 & 0 & 8 & 24 & 0 & \text{oui} & 6\\
\text{H} & 6 & 8 & 0 & 0 & 8 & \text{oui} & 30\\
\text{I} & 8\frac{2}{3} & 5\frac{1}{3} & 0 & 13\frac{1}{3} & 0 & \text{oui} & 24\frac{2}{3}\\
\text{J} & 12 & 12 & -10 & 0 & 0 & \text{non} & /\\
\hline
\end{array}
}
$$
\paragraph{Conlusion : } La solution de base r�isable H est la solution optimale.
\paragraph{Exercice : } Modifier le probl� pour qu'il poss� moins de 10 S de B.

\subsection{Forme dictionnaire et forme tableau d'une solution de base (base F)}
\paragraph{Dictionnaire : }
$ \renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rcrcrcr}
 z    & = & -6 &+&  \frac{9}{2}x_{2} &+& \frac{1}{2}u_{2}\\
\hline
u_{1} & = & 20 &-&  \frac{5}{2}x_{2} &-& \frac{1}{2}u_{2}\\
x_{1} & = & -6 &+& \frac{3}{2}x_{2} &+& \frac{1}{2}u_{2}\\
u_{3} & = & 24 &-& 2x_{2} &-& u_{2}
\end{array}
$
\paragraph{Tableau : }
$ \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{9}{2}&0&-\frac{1}{2}&0&-6&z\\
\hline
0&0&\frac{5}{2}&1&\frac{1}{2}&0&20&u_{1}\\
0&1&-\frac{3}{2}&0&-\frac{1}{2}&0&-6&x_{1}\\
0&0&2&0&1&1&24&u_{3}\\
\hline
\end{array}
$

\subsection{R�lution par l'algorithme du simplexe}
\subsubsection{Premi� base r�isable :  $u_1$, $u_2$, $u_3$}
\paragraph{Dictionnaire 1 : }
$ \renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rcrcrcr}
 z    & = & 0  &+&  x_{1} &+& 3x_{2}\\
\hline
u_{1} & = & 14 &-&  x_{1} &-& x_{2}\\
u_{2} & = & 12 &+& 2x_{1} &-& 3x_{2}\\
u_{3} & = & 12 &-& 2x_{1} &+& x_{2}
\end{array}
$
\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&-1&-3&0&0&0&0&z\\
\hline
0&1&1&1&0&0&14&u_{1}\\
0&-2&3&0&1&0&12&u_{2}\\
0&2&-1&0&0&1&12&u_{3}\\
\hline
\end{array}
$
\subsubsection{  Calcul : $x_2$ entre dans la base et $u_2$ en sort}
\paragraph{D1 $\rightarrow$ D2 : }
$ \renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rcrcrcr}
 z    & = & 0  &+&  x_{1} &+& 3x_{2}\\
\hline
u_{1} & = & 14 &-&  x_{1} &-& x_{2}\\
x_{2} & = &  4 &+& \frac{2}{3}x_{1} &-& \frac{1}{3}u_{2}\\
u_{3} & = & 12 &-& 2x_{1} &+& x_{2}
\end{array}
$
\paragraph{T1 $\rightarrow$ T2 : }
$ \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&-1&-3&0&0&0&0&z\\
\hline
0&1&1&1&0&0&14&u_{1}\\
0&-\frac{2}{3}&1&0&\frac{1}{3}&0&4&x_{2}\\
0&2&-1&0&0&1&12&u_{3}\\
\hline
\end{array}
$

\subsubsection{Seconde base r�isable : $u_1$, $x_2$, $u_3$}
\paragraph{Dictionnaire 2 : }
$ \renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rcrcrcr}
 z    & = & 12 &+& 3x_{1} &-& u_{2}\\
\hline
u_{1} & = & 10 &-& \frac{5}{3} x_{1} &+& \frac{1}{3}u_{2}\\
x_{2} & = &  4 &+& \frac{2}{3}x_{1} &-& \frac{1}{3}u_{2}\\
u_{3} & = & 16 &-& \frac{4}{3}x_{1} &-& \frac{1}{3}u_{2}
\end{array}
$
\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&-3&0&0&1&0&12&z\\
\hline
0&\frac{5}{3}&0&1&-\frac{1}{3}&0&10&u_{1}\\
0&-\frac{2}{3}&1&0&\frac{1}{3}&0&4&x_{2}\\
0&\frac{4}{3}&0&0&\frac{1}{3}&1&16&u_{3}\\
\hline
\end{array}
$

\subsubsection{  Calcul : $x_1$ entre dans la base et $u_1$ en sort}
\paragraph{D2 $\rightarrow$ D3 : }
$ \renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rcrcrcr}
 z    & = & 12 &+& 3x_{1} &-& u_{2}\\
\hline
x_{1} & = & 6 &-& \frac{3}{5}u_{1} &+& \frac{1}{5}u_{2}\\
x_{2} & = &  4 &+& \frac{2}{3}x_{1} &-& \frac{1}{3}u_{2}\\
u_{3} & = & 16 &-& \frac{4}{3}x_{1} &-& \frac{1}{3}u_{2}
\end{array}
$
\paragraph{T2 $\rightarrow$ T3 : }
$ \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&-3&0&0&1&0&12&z\\
\hline
0&1&0&\frac{3}{5}&-\frac{1}{5}&0&6&x_{1}\\
0&-\frac{2}{3}&1&0&\frac{1}{3}&0&4&x_{2}\\
0&\frac{4}{3}&0&0&\frac{1}{3}&1&16&u_{3}\\
\hline
\end{array}
$


\subsubsection{Troisi� base r�isable :  $x_1$, $x_2$, $u_3$}
\paragraph{Dictionnaire 3 : }
$ \renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rcrcrcr}
 z    & = & 30 &-& \frac{9}{5}u_{1} &-& \frac{2}{5}u_{2}\\
\hline
x_{1} & = & 6 &-& \frac{3}{5}u_{1} &+& \frac{1}{5}u_{2}\\
x_{2} & = & 8 &-& \frac{2}{5}u_{1} &-& \frac{1}{5}u_{2}\\
u_{3} & = & 8 &+& \frac{4}{5}u_{1} &-& \frac{3}{5}u_{2}
\end{array}
$
\paragraph{Tableau 3 : }
$ \renewcommand{\arraystretch}{1.4}\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{9}{5}&\frac{2}{5}&0&30&z\\
\hline
0&1&0&\frac{3}{5}&-\frac{1}{5}&0&6&x_{1}\\
0&0&1&\frac{2}{5}&\frac{1}{5}&0&8&x_{2}\\
0&0&0&-\frac{4}{5}&\frac{3}{5}&1&8&u_{3}\\
\hline
\end{array}
$
\paragraph{Conclusion : }L'unique solution optimale est trouv�\par

\subsection{Repr�ntation matricielle}
\subsubsection{Repr�ntation matricielle du probl� lin�re}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z = 
x_{1} + 3x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcr}
 & x_{1} &+& x_{2} &+& u_{1} & = & 14\\
-& 2x_{1} &+& 3x_{2} &+& u_{2} & = & 12\\
 & 2x_{1} &-& x_{2} &+& u_{3} & = & 12\\
\multicolumn{6}{r}{x_{1}, x_{2}, u_{1}, u_{2}, u_{3}} & \ge & 0
\end{array} \right.
\end{array}}
$
\ \ est not�\ 
${\renewcommand{\arraystretch}{1.5}
\begin{array}{ll}
\mbox{max } & z=cx\\
\mbox{s.c.q.} & \left\{\begin{array}{ccc} 
Ax & = & b\\
x & \geq & 0
\end{array}
\right. 
\end{array}
}$
o�gin{center}
$
x=\begin{bmatrix}
x_1\\ x_2\\ u_1\\u_2\\u_3
\end{bmatrix}
$
\begin{tabular}{c}

$
A=\begin{bmatrix}
1 & 1 & 1 & 0 & 0\\
-2 & 3 & 0 & 1 & 0\\
2 & -1 & 0 & 0 & 1
\end{bmatrix}
$
$
b=\begin{bmatrix}
14\\12\\12
\end{bmatrix}
$\\
\\
$
c=\begin{bmatrix}
1 & 3 & 0 & 0 & 0
\end{bmatrix}
$
\end{tabular}
\end{center}

\subsubsection{S�ction d'une base (base F)}
${\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1pt}
\begin{array}{ll}
\mbox{max } & z=cx\\
\mbox{s.c.q.} & \left\{\begin{array}{ccc} 
Ax & = & b\\
x & \geq & 0
\end{array}
\right. 
\end{array}
}$
avec\ \ 
$
x=\begin{bmatrix}
x_1\\ x_2\\ u_1\\u_2\\u_3
\end{bmatrix}
$
\begin{tabular}{c}
$
A=\begin{bmatrix}
1 & 1 & 1 & 0 & 0\\
-2 & 3 & 0 & 1 & 0\\
2 & -1 & 0 & 0 & 1
\end{bmatrix}
$
$
b=\begin{bmatrix}
14\\12\\12
\end{bmatrix}
$\\
\\
$
c=\begin{bmatrix}
1 & 3 & 0 & 0 & 0
\end{bmatrix}
$
\end{tabular}
\vspace{5mm}
\begin{center}
est �ivalent �end{center}
\vspace{5mm}
${\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1pt}
\begin{array}{ll}
\mbox{max } & z=c_Bx_B+c_Nx_N\\
\mbox{s.c.q.} & \left\{\begin{array}{ccc} 
Bx_B + Nx_N & = & b\\
x_B, x_N & \geq & 0
\end{array}
\right. 
\end{array}
}$
\ o�ace{-4mm}
\begin{tabular}{c}
$
x_B=\begin{bmatrix}
u_1\\ x_1\\ u_3
\end{bmatrix}
$\\
\\
$
x_N=\begin{bmatrix}
x_2\\u_2
\end{bmatrix}
$
\end{tabular}
\hspace{-5mm}
\begin{tabular}{c}
$
B=\begin{bmatrix}
1 & 1 & 0\\
0 & -2 & 0\\
0 & 2 & 1
\end{bmatrix}
$
$
N=\begin{bmatrix}
1 & 0\\
3 & 1\\
-1 & 0
\end{bmatrix}
$
\\
\\
$
c_B=\begin{bmatrix}
0 & 1 & 0
\end{bmatrix}
$
$
c_N=\begin{bmatrix}
3 & 0
\end{bmatrix}
$
\end{tabular}

\subsubsection{Repr�ntation matricielle d'un dictionnaire (base F)}
$${\renewcommand{\arraystretch}{1.5}
\begin{array}{ll}
\mbox{max } & z=c_BB^{-1}b +(c_N-c_BB^{-1}N)x_N\\
\mbox{s.c.q.} & \left\{\begin{array}{ccc} 
x_B & = & B^{-1}b - B^{-1}Nx_N\\
x_B,x_N & \geq & 0
\end{array}
\right. 
\end{array}
}$$
o�gin{center}
$
x_B=\begin{bmatrix}
u_1\\ x_1\\ u_3
\end{bmatrix}
$
$
B^{-1}=\begin{bmatrix}
1 & \frac{1}{2} & 0\\
0 & -\frac{1}{2} & 0\\
0 & 1 & 1
\end{bmatrix}
$
$
B^{-1}b=\begin{bmatrix}
20\\-6\\24
\end{bmatrix}
$
$c_BB^{-1}b=-6$
\end{center}
et
\begin{center}
$
x_N=\begin{bmatrix}
x_2\\ u_2
\end{bmatrix}
$
$c_N-c_BB^{-1}N=\begin{bmatrix}\frac{9}{2} & \frac{1}{2}\end{bmatrix}$
$
B^{-1}N=\begin{bmatrix}
\frac{5}{2} & \frac{1}{2}\\
-\frac{3}{2} & -\frac{1}{2}\\
2 & 1
\end{bmatrix}
$
\end{center}

\paragraph{Notations : } $\pi=c_BB^{-1}$, $\bar{b}=B^{-1}b$ et  $\bar{c}_N=c_N-c_BB^{-1}N$

%\subsubsection{Repr�ntation matricielle d'un tableau simplexe (base F)}
%\begin{center}
%%Si 
%\begin{tabular}{ccc}
%${\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{0pt}
%\begin{array}{cc}
%\max & z=c_BB^{-1}b+\bar{c}x\\
%\mbox{s.c.q.} & \left\{\begin{array}{ccc} 
%\bar{A}x & = & \bar{b}\\
%x & \geq & 0
%\end{array}
%\right. 
%\end{array}
%}$
%&
%avec
%&
%$
%\begin{array}{l}
%\bar{A}=B^{-1}A\\
%\bar{b}=B^{-1}b\\
%\bar{c}=c-c_BB^{-1}A
%\end{array}
%$
%\\
%\\
%\multicolumn{3}{c}{
%$
%\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
%\begin{array}{cccccc|c|c}
%z & x_{1} & x_{2} & x_{3} & \cdots & x_{n} & 1\\
%\hline
%1&-\bar{c}_1&-\bar{c}_2&-\bar{c}_3&\cdots&-\bar{c}_n&c_BB^{-1}b&z\\
%\hline
%0&\bar{a}_{11}&\bar{a}_{12}&\bar{a}_{13}&\cdots&\bar{a}_{1n}&\bar{b}_1&x_{i_1}\\
%\vdots&\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\
%0&\bar{a}_{m1}&\bar{a}_{m2}&\bar{a}_{m3}&\cdots&\bar{a}_{mn}&\bar{b}_m&x_{i_m}\\
%\hline
%\end{array}
%$}
%\end{tabular}
%\end{center}
%
%\subsubsection{Repr�ntation matricielle d'un tableau simplexe (base F)}
%\subsubsection{Lien entre matrices du dictionnaire et du tableau (base F)}
\subsection{Forme matricielle de l'algorithme du simplexe}
\subsubsection{Premi� base r�isable :  $u_1$, $u_2$, $u_3$}
\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&-1&-3&0&0&0&0&z\\
\hline
0&1&1&1&0&0&14&u_{1}\\
0&-2&3&0&1&0&12&u_{2}\\
0&2&-1&0&0&1&12&u_{3}\\
\hline
\end{array}
$
\paragraph{Matrice 1 : }
\begin{tabular}{l}
$
x_B=\begin{bmatrix}
u_1\\ u_2\\ u_3
\end{bmatrix}
$
$
B^{-1}=\left[\begin{array}{rrr}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1
\end{array}\right]
$
$
B^{-1}b=\begin{bmatrix}
14\\12\\12
\end{bmatrix}
$
$c_BB^{-1}b=0$\\
$
x_N=\begin{bmatrix}
x_1\\ x_2
\end{bmatrix}
$
$c_N-c_BB^{-1}N=\begin{bmatrix}1 & 3\end{bmatrix}$
$
B^{-1}N=\left[\begin{array}{rr}
1 & 1\\
-2 & 3\\
2 & -1
\end{array}\right]
$
\end{tabular}

\subsubsection{Seconde base r�isable : $u_1$, $x_2$, $u_3$}
\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&-3&0&0&1&0&12&z\\
\hline
0&\frac{5}{3}&0&1&-\frac{1}{3}&0&10&u_{1}\\
0&-\frac{2}{3}&1&0&\frac{1}{3}&0&4&x_{2}\\
0&\frac{4}{3}&0&0&\frac{1}{3}&1&16&u_{3}\\
\hline
\end{array}
$
\paragraph{Matrice 2 : }
\begin{tabular}{l}
$
x_B=\begin{bmatrix}
u_1\\ x_2\\ u_3
\end{bmatrix}
$
$
B^{-1}=\left[\begin{array}{rrr}
1&-\frac{1}{3}&0\\
0&\frac{1}{3}&0\\
0&\frac{1}{3}&1
\end{array}\right]
$
$
B^{-1}b=\begin{bmatrix}
10\\4\\16
\end{bmatrix}
$
$c_BB^{-1}b=12$\\
$
x_N=\begin{bmatrix}
x_1\\ u_2
\end{bmatrix}
$
$c_N-c_BB^{-1}N=\begin{bmatrix}3 & -1\end{bmatrix}$
$
B^{-1}N=\left[\begin{array}{rr}
\frac{5}{3}&-\frac{1}{3}\\
-\frac{2}{3}&\frac{1}{3}\\
\frac{4}{3}&\frac{1}{3}
\end{array}\right]
$
\end{tabular}

\subsubsection{Troisi� base r�isable :  $x_1$, $x_2$, $u_3$}
\paragraph{Tableau 3 : }
$ \renewcommand{\arraystretch}{1.4}\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{9}{5}&\frac{2}{5}&0&30&z\\
\hline
0&1&0&\frac{3}{5}&-\frac{1}{5}&0&6&x_{1}\\
0&0&1&\frac{2}{5}&\frac{1}{5}&0&8&x_{2}\\
0&0&0&-\frac{4}{5}&\frac{3}{5}&1&8&u_{3}\\
\hline
\end{array}
$
\paragraph{Matrice 3 : }
\begin{tabular}{l}
$
x_B=\begin{bmatrix}
x_1\\ x_2\\ u_3
\end{bmatrix}
$
$
B^{-1}=\left[\begin{array}{rrr}
\frac{3}{5}&-\frac{1}{5}&0\\
\frac{2}{5}&\frac{1}{5}&0\\
-\frac{4}{5}&\frac{3}{5}&1
\end{array}\right]
$
$
B^{-1}b=\begin{bmatrix}
6\\8\\8
\end{bmatrix}
$
$c_BB^{-1}b=30$\\
$
x_N=\begin{bmatrix}
u_1\\ u_2
\end{bmatrix}
$
$c_N-c_BB^{-1}N=\begin{bmatrix}-\frac{9}{5}&-\frac{2}{5}\end{bmatrix}$
$
B^{-1}N=\left[\begin{array}{rr}
\frac{3}{5}&-\frac{1}{5}\\
\frac{2}{5}&\frac{1}{5}\\
-\frac{4}{5}&\frac{3}{5}
\end{array}\right]
$
\end{tabular}
\paragraph{Conclusion : }L'unique solution optimale est trouv�\par

\subsection{Forme r�s�de l'algorithme du simplexe}
\begin{itemize}
\item On ne calcule que la colonne n�ssaire de $B^{-1}N$ (colonne de la variable entrante)
\item On calcule la matrice $B^{-1}$ de la base suivante �artir de la matrice $B^{-1}$ de la base courante.
$$B^{-1}_{(2)}=
\left[\begin{array}{rrr}
1&-\frac{1}{3}&0\\
0&\frac{1}{3}&0\\
0&\frac{1}{3}&1
\end{array}\right]
=
\left[\begin{array}{rrr}
1&-\frac{1}{3}&0\\
0&\frac{1}{3}&0\\
0&\frac{1}{3}&1
\end{array}\right]
\left[\begin{array}{rrr}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1
\end{array}\right]
=E_{(1)}B^{-1}_{(1)}$$
$$B^{-1}_{(3)}=
\left[\begin{array}{rrr}
\frac{3}{5}&-\frac{1}{5}&0\\
\frac{2}{5}&\frac{1}{5}&0\\
-\frac{4}{5}&\frac{3}{5}&1
\end{array}\right]
=
\left[\begin{array}{rrr}
\frac{3}{5} & 0 & 0\\
\frac{2}{5} & 1 & 0\\
-\frac{4}{5} & 0 & 1
\end{array}\right]
\left[\begin{array}{rrr}
1&-\frac{1}{3}&0\\
0&\frac{1}{3}&0\\
0&\frac{1}{3}&1
\end{array}\right]
=E_{(2)}B^{-1}_{(2)}$$
\end{itemize}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Un exemple �rois variables de d�sion}
\subsection{Probl� et repr�ntation graphique}
\begin{center}
$
\begin{array}{ll}
\max  & z = 35 x_1 + 38 x_2 + 30 x_3 \\
\mbox{s.c.q.} &
{\renewcommand{\arraycolsep}{1.0 pt}
\left\{ \begin{array}{rcrcrcr}
4x_1 & + & 4x_2 & + & 2x_3 & \leq & 80\\
2x_1 & + & 3x_2 & + & 2x_3 & \leq & 50\\
 x_1 & + & 2x_2 & + & 3x_3 & \leq & 40\\
x_1  &   &    &    &   & \geq & 0\\
   &   & x_2  &    &   & \geq & 0\\
   &   &    &    & x_3 & \geq & 0
\end{array} \right.}
\end{array}
$
%\framebox
{
\psset{unit=0.17cm}
\fontsize{5}{1}\selectfont
%\psset{arrowsize=4pt 3}
  \psset{arrowinset=0}
\begin{pspicture}[0.5](-17,-7)(20,16)
% SOMMETS
\psset{dotstyle=*}\psset{dotscale=0.9}
\psdots(0,0)\psdots(15,-3)\psdots(13,1)\psdots(0,13)
\psdots(-12,4)\psdots(-7,2)\psdots(-15,-5)\psdots(1,-4)
% AXES
\psline[linestyle=dashed](0,0)(-15,-5)\psline{->}(-15,-5)(-18,-6)\rput(-17,-4){$x_1$}
\psline[linestyle=dashed](0,0)(15,-3)\psline{->}(15,-3)(20,-4)\rput(19,-2){$x_2$}
\psline[linestyle=dashed](0,0)(0,13)\psline{->}(0,13)(0,16)\rput(-2,15){$x_3$}
% ARETES
\psline(15,-3)(13,1)\psline(13,1)(0,13)
\psline(0,13)(-12,4)\psline(-12,4)(-7,2)\psline(-12,4)(-15,-5)
\psline(-15,-5)(1,-4)\psline(-7,2)(1,-4)\psline(-7,2)(13,1)\psline(1,-4)(15,-3)
% COORDONNEES
\rput[bl](1,0){$(0,0,0)$}\rput[t](15,-4){$(0,16\frac{2}{3},0)$}\rput[bl](14,1){$(0,14,4)$}
\rput[Bl](1,13){$(0,0,13\frac{1}{3})$}\rput[Br](-13,4){$(16,0,8)$}
\rput[b](-6,3){$(13\frac{1}{3},3\frac{1}{3},6\frac{2}{3})$}\rput[t](-15,-6){$(20,0,0)$}\rput[t](1,-5){$(10,10,0)$}
% PLANS
\rput(-10,-1){$\Pi_1$}\rput(4,-2){$\Pi_2$}\rput(2,7){$\Pi_3$}
\end{pspicture}}
%\BoxedEPSF{./FUNDP_AD_SLIDES.eps/poly1.eps scaled 400}
\\
\bigskip
\begin{tabular}{llcl}
 & $4x_1+4x_2+2x_3=80$  & & $\Pi_1$\\
Le plan  & $2x_1+3x_2+2x_3=50$  & est rep� par & $\Pi_2$\\
 & $x_1+2x_2+3x_3=40$   & & $\Pi_3$
\end{tabular}
\end{center}

Solution optimale : $(x_1^*,x_2^*,x_3^*)=(16,0,8)$ et $z^*=800$.

\subsection{Probl� sous forme standard}
$
\begin{array}{ll}
\max  & z = 35 x_1 + 38 x_2 + 30 x_3 \\
\mbox{s.c.q.} &
{\renewcommand{\arraycolsep}{1.0 pt}
\left\{ \begin{array}{rcrcrcrcrcrcr}
4x_1 & + & 4x_2 & + & 2x_3 & + & u_1 & & & & & = & 80\\
2x_1 & + & 3x_2 & + & 2x_3 & & & + & u_2 & & & = & 50\\
 x_1 & + & 2x_2 & + & 3x_3 & & & & & + & u_3 & = & 40\\
x_1  &  , & x_2 &  , & x_3 & , & u_1 & , & u_2 & , & u_3 & \geq & 0
\end{array} \right.}
\end{array}
$

\subsection{R�lution par l'algorithme du Simplexe}
\noindent
\begin{tabular}{ll}
$
{\renewcommand{\arraystretch}{1.1}
\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrrr|r}
z&x_1&x_2&x_3&u_1&u_2&u_3&1\\
\hline
1&-35&-38&-30&0&0&0&0\\
\hline
0&4&4&2&1&0&0&80\\
0&2&3&2&0&1&0&50\\
0&1&2&3&0&0&1&40\\
\hline
\end{array}}
$
&
\begin{tabular}{l}
Variables hors base :\\$x_1$, $x_2$, $x_3$\\
Solution de base :\\$(0,0,0,80,50,40)$\\
Valeur de l'objectif :\\$z=0$
\end{tabular}
\end{tabular}
\begin{center}
Variable entrante : $x_2$\\
Variable sortante : $u_2$
\end{center}
\begin{tabular}{ll}
$
{\renewcommand{\arraystretch}{1.1}
\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrrr|r}
z&x_1&x_2&x_3&u_1&u_2&u_3&1\\
\hline
1&-9\frac{2}{3}&0&-4\frac{2}{3}&0&12\frac{2}{3}&0&633\frac{1}{3}\\
\hline
0&1\frac{1}{3}& 0&-\frac{2}{3} &1&-1\frac{1}{3}& 0&13\frac{1}{3}\\
0&\frac{2}{3}&  1&\frac{2}{3}  &0&\frac{1}{3}&   0&16\frac{2}{3}\\
0&-\frac{1}{3}& 0&1\frac{2}{3} &0&-\frac{2}{3}&  1&6\frac{2}{3}\\
\hline
\end{array}}
$
&
\begin{tabular}{l}
Variables hors base :\\$x_1$, $x_3$, $u_2$\\
Solution de base :\\$(0,16\frac{2}{3},0,13\frac{1}{3},0,6\frac{2}{3})$\\
Valeur de l'objectif :\\$z=633\frac{1}{3}$
\end{tabular}
\end{tabular}
\begin{center}
Variable entrante : $x_1$\\
Variable sortante : $u_1$
\end{center}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\noindent
\begin{tabular}{ll}
$
{\renewcommand{\arraystretch}{1.1}
\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrrr|r}
z&x_1&x_2&x_3&u_1&u_2&u_3&1\\
\hline
1&0&0&-9\frac{1}{2}&7\frac{1}{4}&3&0&730\\
\hline
0&1&0&-\frac{1}{2}&\frac{3}{4} &-1&0&10\\
0&0&1&1           &-\frac{1}{2}&1 &0&10\\
0&0&0&1\frac{1}{2}&\frac{1}{4} &-1&1&10\\
\hline
\end{array}}
$
&
\begin{tabular}{l}
Variables hors base :\\$x_3$, $u_1$, $u_2$\\
Solution de base :\\$(10,10,0,0,0,10)$\\
Valeur de l'objectif :\\$z=730$
\end{tabular}
\end{tabular}
\begin{center}
Variable entrante : $x_3$\\
Variable sortante : $u_3$
\end{center}
\begin{tabular}{ll}
$
{\renewcommand{\arraystretch}{1.1}
\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrrr|r}
z&x_1&x_2&x_3&u_1&u_2&u_3&1\\
\hline
1&0&0&0&8\frac{10}{12}&-3\frac{1}{3}&6\frac{1}{3}&793\frac{1}{3}\\
\hline
0&1&0&0&\frac{10}{12}&-1\frac{1}{3}&\frac{1}{3}  &13\frac{1}{3}\\
0&0&1&0&-\frac{2}{3} &1\frac{2}{3} &-\frac{2}{3} &3\frac{1}{3}\\
0&0&0&1&\frac{1}{6}  &-\frac{2}{3} &\frac{2}{3}  &6\frac{2}{3}\\
\hline
\end{array}}
$
&
\begin{tabular}{l}
Variables hors base :\\$u_1$, $u_2$, $u_3$\\
Solution de base :\\$(13\frac{1}{3},3\frac{1}{3},6\frac{2}{3},0,0,0)$\\
Valeur de l'objectif :\\$z=793\frac{1}{3}$
\end{tabular}
\end{tabular}
\begin{center}
Variable entrante : $u_2$\\
Variable sortante : $x_2$
\end{center}
\noindent
\begin{tabular}{ll}
$
{\renewcommand{\arraystretch}{1.1}
\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrrr|r}
z&x_1&x_2&x_3&u_1&u_2&u_3&1\\
\hline
1&0&2&0&7\frac{1}{2}&0&5&800\\
\hline
0&1&\frac{4}{5}&0&\frac{3}{10}  &0&-\frac{1}{5}&16\\
0&0&\frac{3}{5}&0&-\frac{2}{5}  &1&-\frac{2}{5}&2\\
0&0&\frac{2}{5}&1&-\frac{1}{10} &0& \frac{2}{5}&8\\
\hline
\end{array}}
$
&
\begin{tabular}{l}
Variables hors base :\\$x_2$, $u_1$, $u_3$\\
Solution de base :\\$(16,0,8,0,2,0)$\\
Valeur de l'objectif :\\$z=800$
\end{tabular}
\end{tabular}
Variable entrante : aucune candidate\\
Solution optimale : $(x_1,x_2,x_3,u_1,u_2,u_3)=(16,0,8,0,2,0)$\\
Valeur de l'objectif �'optimum : $z=800$

%%%%%%%%%%%
%%%%%%%%%%%
\section{G�ralisation}
%%%%%%%%%%%
\subsection{Forme g�rale d'un probl� lin�re}
$$
\begin{array}{ll}
\max (ou \min)\ z & = \displaystyle  \sum_{j=1}^n c_{j}\: x_j\\
\mbox{s.c.q.} & \left\{
\begin{array}{lllc} 
\displaystyle  \sum_{j=1}^n a_{ij}\: x_j \le b_i&&i=1,\ldots,r&\\
\displaystyle  \sum_{j=1}^n a_{ij}\: x_j = b_i&&i=r+1,\ldots,s&\\
\displaystyle  \sum_{j=1}^n a_{ij}\: x_j \ge b_i&&i=s+1,\ldots,m&\\
\displaystyle   x_j \ge 0&&j=1,\ldots,p&\\
\displaystyle   x_j \in \R &&j=p+1,\ldots,q&\\
\displaystyle   x_j \le 0&&j=q+1,\ldots,n&\\
\end{array}
\right.
\end{array}
$$
\newpage
%%%%%%%%%%%
\subsection{Equivalences}
\begin{itemize}
\item Objectif
$$\max z=c_1x_1+\cdots+c_nx_n  \Longleftrightarrow  \min w=-c_1x_1-\cdots-c_nx_n $$

\item Contraintes
$$a_1x_1+\cdots+a_nx_n \leq b  \Longleftrightarrow 
\left\{\begin{array}{l}
a_1x_1+\cdots+a_nx_n + u= b\\
u \geq 0
\end{array}\right.$$
$$a_1x_1+\cdots+a_nx_n \geq b  \Longleftrightarrow 
\left\{\begin{array}{l}
a_1x_1+\cdots+a_nx_n - s= b\\
s \geq 0
\end{array}\right.$$
$$a_1x_1+\cdots+a_nx_n = b  \Longleftrightarrow 
\left\{\begin{array}{l}
a_1x_1+\cdots+a_nx_n \leq b\\
a_1x_1+\cdots+a_nx_n \geq b
\end{array}\right.$$

\item Variables
$$
\begin{array}{ccc}
         &         x=-y        & \\
y \leq 0 & \Longleftrightarrow & x \geq 0\\
         &        y-x=t       & \\
t \in \R  & \Longleftrightarrow & x,y \geq 0
\end{array}
$$
%$$y \in [a,b] \Longleftrightarrow x \geq 0 \mbox{ et }x \leq b-a\mbox{ avec } x=y-a$$
\end{itemize}

\newpage
%%%%%%%%%%%
\subsection{Exemple}
\vspace{1cm}
$$
{\renewcommand{\arraystretch}{1.1} \renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\max w & = \begin{array}{rcrcr} 3 y_1 & - & 4 y_2 & + & 2y_3 \end{array} \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcrcrcr}
 -y_1 & + &2y_2 & + & y_3 & \geq & 10\\
y_1 & - &y_2 & - & y_3 & = & 50\\
y_1 &  &     & & & \leq &  0\\
  &  & y_2     & & &\in &  \R\\ 
  &  &      & & y_3 &\geq &  0 \\   
\end{array}\right.
\end{array}
 }
\Longleftrightarrow
{\renewcommand{\arraystretch}{1.1} \renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\min z & = \begin{array}{rcrcrcr} 3 x_1 & - & 4x_2 & + &4x_3 & - & 2x_4 \end{array} \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcrcrcrcrcr}
 x_1 & - & 2x_2 & + &2x_3 & + & x_4 & - & x_5 & = & 10\\
-x_1 & + & x_2 & - &x_3 & - & x_4 & & & = & 50\\
\multicolumn{9}{r}{x_1  ,  x_2  ,  x_3   ,  x_4 , x_5} & \geq &  0\\  
\end{array}\right.
\end{array}
 }
$$
avec
$$
\begin{array}{l}
y_1=-x_1\\
y_2=x_3-x_2\\
y_3=x_4
\end{array}
$$
%%%%%%%%%%%
\subsection{Forme standard d'un probl� lin�re}

$${\renewcommand{\arraystretch}{1.2}
\renewcommand{\arraycolsep}{3pt}
\begin{array}{ll}
\max (ou \min) \ z &=\begin{array}{rcrrcr}c_1 x_1&+&c_2 x_2&\cdots &+&c_n x_n
\end{array}\\ 
\mbox{s.c.q.} & \left\{\begin{array}{ccccccccc} 
a_{11}x_{1}&+&a_{12}x_{2}&+&\cdots&+&a_{1n}x_{n}&=&b_1\\
a_{21}x_{1}&+&a_{22}x_{2}&+&\cdots&+&a_{2n}x_{n}&=&b_2\\
     \vdots& &  \vdots   & &      & & \vdots    &       &\vdots\\
a_{m1}x_{1}&+&a_{m2}x_{2}&+&\cdots&+&a_{mn}x_{n}&=&b_m\\
\multicolumn{7}{r}{x_{1}, x_{2},\cdots,x_{n}}  &\geq&0
\end{array}
\right. 
\end{array}
}
$$

%%%%%%%%%%%
\subsection{D�nitions}

\begin{svdef}
On appelle variables {\bfseries\itshape hors base} (v.h.b.) les $(n-m)$ variables du probl� fix� �� pour trouver une solution unique au syst� form�ar les $m$ contraintes d'�lit� Les $m$ variables restantes sont appel� variables de
{\bfseries\itshape base} (v.b.).
\end{svdef}

\newpage
\begin{svdef} On appelle {\bfseries\itshape solution de base} une solution o�ayant choisi $(n-m)$
variables hors base, on obtient une solution unique  en r�lvant les $m$ contraintes d'�lit�du probl�.
\end{svdef}

\begin{svdef}
On appelle {\bfseries\itshape solution de base r�isable} une solution de base qui en plus v�fie les
contraintes de positivit�\end{svdef}

\begin{svdef}
On appelle {\bfseries\itshape solutions de base adjacentes} deux solutions de base dont les variables de base
sont les m�s sauf une.
\end{svdef}


%%%%%%%%%%%
\subsection{Propri�s}

\begin{svpro}  La notion g��ique de sommet du
poly�e des solutions r�isables correspond �a notion alg�ique de solution de base r�isable.
\end{svpro}

\begin{svpro} La notion g��ique de sommets adjacents du poly�e des solutions r�isables correspond �a
notion alg�ique de solutions de base r�isables adjacentes.
\end{svpro}

%%%%%%%%%%%
\newpage
\section{Probl�s particuliers}
%%%%%%%%%%%

%%%%%%%%%%%
\subsection{Probl� non born�
\begin{tabular}{cc}
$
{\renewcommand{\arraystretch}{1.2}
\begin{array}{ll}
\max & z =  x_1  +   x_2 \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcrcl}
-2 x_1 &+&  x_2  &\leq & 2 \\
x_1 &-&    2x_2 &\leq & 2 \\
\multicolumn{3}{r}{x_1,x_2}&\ge &0
\end{array}\right.
\end{array}}
$
&
%\framebox
{
% PARAMETRES
\psset{unit=0.6cm}
\psset{arrowinset=0}
\begin{pspicture}[0.5](-1,-1)(7,7)
% AXES
\psline{->}(-1,0)(6,0)\rput(7,0){$x_1$}
\psline{->}(0,-1,0)(0,6)\rput(0,7){$x_2$}
% CONTRAINTES
\psline(2,0)(6,2)\psline(0,2)(2,6)
%\pspolygon[linewidth=0pt,fillstyle=solid,fillcolor=lightgray](0,0)(2,0)(6,2)(2,6)(0,2)
% OBJECTIF
\psline[linestyle=dashed](5,1)(1,5)
\psline{->}(3,3)(3.5,3.5)
% SOMMETS
\psset{dotstyle=*}\psset{dotscale=1.3}
\psdots(0,0)\psdots(2,0)\psdots(0,2)
\rput(-1,-1){$(0,0)$}\rput(2,-1){$(2,0)$}\rput(-1,2){$(0,2)$}
\end{pspicture}
}
%\BoxedEPSF{./FUNDP_AD_SLIDES.eps/nonborne.eps scaled 950}
\end{tabular}

\newpage
\subsubsection {Premier tableau}
\begin{tabular}{ll}
$
{\renewcommand{\arraystretch}{1.1}
\begin{array}{rrrrr|r}
z&x_1&x_2&u_1&u_2&\\
\hline
1& -1&  -1&   0&  0& 0\\
\hline
0&  -2&  1&  1&  0&    2\\
0&   1& -2&  0&  1&    2\\
\hline
\end{array}}
$
&
\begin{tabular}{l}
Variables hors base : $x_1$, $x_2$\\
Solution de base : $(0,0,2,2)$\\
Valeur de l'objectif : $z=0$
\end{tabular}
\end{tabular}
\begin{flushleft}
Variable entrante : $x_1$\hspace{1cm}
Variable sortante : $u_2$
\end{flushleft}

\subsubsection {Second tableau}
\begin{tabular}{ll}
$
{\renewcommand{\arraystretch}{1.1}
\begin{array}{rrrrr|r}
z&x_1&x_2&u_1&u_2&\\
\hline
1& 0&  -3&   0&  1& 2\\
\hline
0&  0& -3&  1&  2&    6\\
0&  1& -2&  0&  1&    2\\
\hline
\end{array}}
$
&
\begin{tabular}{l}
Variables hors base : $x_2$, $u_2$\\
Solution de base : $(2,0,6,0)$\\
Valeur de l'objectif : $z=2$
\end{tabular}
\end{tabular}
\begin{flushleft}
Variable entrante : $x_2$\hspace{1cm}
Variable sortante : aucune candidate\\
\end{flushleft}
\noindent
\textbf{Conclusion : Le probl� est non born�



%%%%%%%%%%%
\subsection{Infinit�e solutions}
\subsubsection{Probl� et repr�ntation graphique}

\begin{center}
\begin{tabular}{cc}
$
{\renewcommand{\arraystretch}{1.2}
\begin{array}{ll}
\max  & z = 3 x_1 + 2 x_2     \\
\mbox{s.c.q.} & \left\{ \begin{array}{lclcr}
                x_1 & &        &\leq&  4  \\
                    & &  2x_2  &\leq& 12  \\
               3x_1 &+&  2x_2  &\leq& 18  \\
                x_1 & &        &\geq&       0  \\
                    & &    x_2 &\geq&       0  
\end{array} \right.
\end{array}}
$
&
%\framebox
{
% PARAMETRES
\fontsize{8}{1}\selectfont
\psset{unit=0.4cm}
\psset{arrowinset=0}
\begin{pspicture}[0.5](-1,-1)(8,11)
% AXES
\psaxes[Dx=1,Dy=1,tickstyle=top,labels=none]{->}(0,0)(0,0)(7,10)
\rput(8,0){$x_1$}\rput(0,11){$x_2$}
% CONTRAINTES
\psline(0,6)(6,6) \psline(4,0)(4,8) \psline(6,0)(0,9)
\pspolygon[linewidth=0pt,fillstyle=solid,fillcolor=lightgray](0,0)(4,0)(4,3)(2,6)(0,6)
% OBJECTIF
\psline[linestyle=dashed](4,0)(0,6) \psline{->}(2.25,3)(3,3.5)
% SOMMETS
\psset{dotstyle=*}\psset{dotscale=1.1}
\psdots(0,0)\psdots(4,0)\psdots(4,3)\psdots(2,6)\psdots(0,6)
\rput(-1,-1){$(0,0)$}\rput(4,-1){$(4,0)$}\rput(5,3){$(4,3)$}
\rput[t](3,7){$(2,6)$}\rput(-1,6){$(0,6)$}
\end{pspicture}
}
%\BoxedEPSF{./FUNDP_AD_SLIDES.eps/sommet.eps scaled 650}
\end{tabular}
\end{center}

\vspace{-8mm}
\subsubsection{Solutions optimales}
$S=\{(x_1,x_2) | (x_1,x_2) = \alpha(2,6) +(1-\alpha)(4,3) \mbox{ avec } 0\le\alpha\le1\}$\\
$z^*=18$

\newpage
\subsubsection{Probl� sous forme standard}
$$
{\renewcommand{\arraystretch}{1.2}
\renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\max  & z = 3 x_1 +2 x_2     \\
\mbox{s.c.q.} & \left\{ \begin{array}{rcrcrcrcrcr}
                x_1 & &        & + & u_1 & & & & &=&  4  \\
                    & &  2x_2  & & & + & u_2 & & &=& 12  \\
               3x_1 &+&  2x_2  & & & & & + & u_3&=& 18  \\
                x_1 & , & x_2  & , & u_1& , & u_2& , & u_3&\geq&0
\end{array} \right.
\end{array}}
$$
\subsubsection{R�lution : Premier tableau}
\noindent
\begin{tabular}{ll}
$
{\renewcommand{\arraystretch}{1.0}
\renewcommand{\arraycolsep}{1pt}
\begin{array}{rrrrrr|r}
\hspace{3mm}z&\hspace{6mm}x_1&\hspace{6mm}x_2&\hspace{6mm}u_1&\hspace{6mm}u_2&\hspace{6mm}u_3&\hspace{8mm}\\
\hline
1&-3&-2&0&0&0&0\\
\hline
0&1&0&1&0&0&4\\
0&0&2&0&1&0&12\\
0&3&2&0&0&1&18\\
\hline
\end{array}}
$
&
\begin{tabular}{l}
Variables hors base : $x_1$, $x_2$\\
Solution de base : $(0,0,4,12,18)$\\
Valeur de l'objectif : $z=0$
\end{tabular}
\end{tabular}

\begin{center}
Variable entrante : $x_2$\\
Variable sortante : $u_2$\\
\end{center}

\subsubsection{R�lution : Second tableau}
\noindent
\begin{tabular}{ll}
$
{\renewcommand{\arraystretch}{0.9}
\renewcommand{\arraycolsep}{1pt}
\begin{array}{rrrrrr|r}
\hspace{3mm}z&\hspace{6mm}x_1&\hspace{6mm}x_2&\hspace{6mm}u_1&\hspace{6mm}u_2&\hspace{6mm}u_3&\hspace{8mm}\\
\hline
1&-3&0&0&1&0&12\\
\hline
0&1&0&1&0&0&4\\
0&0&1&0&1/2&0&6\\
0&3&0&0&-1&1&6\\
\hline
\end{array}}
$
&
\begin{tabular}{l}
Variables hors base : $x_1$, $u_2$\\
Solution de base : $(0,6,4,0,6)$\\
Valeur de l'objectif : $z=12$
\end{tabular}
\end{tabular}
\begin{center}
Variable entrante : $x_1$\hspace{1cm}
Variable sortante : $u_3$
\end{center}
\subsubsection{R�lution : Troisi� tableau}
\noindent
\begin{tabular}{ll}
$
{\renewcommand{\arraystretch}{0.9}
\renewcommand{\arraycolsep}{1pt}
\begin{array}{rrrrrr|r}
\hspace{3mm}z&\hspace{6mm}x_1&\hspace{6mm}x_2&\hspace{6mm}u_1&\hspace{6mm}u_2&\hspace{6mm}u_3&\hspace{8mm}\\
\hline
1&0&0&0&0&1&18\\
\hline
0&0&0&1&1/3&-1/3&2\\
0&0&1&0&1/2&0&6\\
0&1&0&0&-1/3&1/3&2\\
\hline
\end{array}}
$
&
\begin{tabular}{l}
Variables hors base : $u_2$, $u_3$\\
Solution de base : $(2,6,2,0,0)$\\
Valeur de l'objectif : $z=18$
\end{tabular}
\end{tabular}

\begin{center}
Variable entrante : aucune candidate\\
Solution optimale : $(x_1,x_2,u_1,u_2,u_3)=(2,6,2,0,0)$\\
Valeur de l'objectif �'optimum : $z=18$
\end{center}

\subsubsection{Remarques}
\begin{itemize}
\item Le coefficient de la variable hors base $u_2$ dans l'objectif est nul.
\item Entrer avec $u_2$ ne modifiera donc pas la valeur de $z$.
\item Il y a donc d'autres solutions optimales possibles.
\end{itemize}

\vspace{-5mm}
\subsubsection{Un pivotage suppl�ntaire}
\begin{center}
Variable entrante : $u_2$\hspace{1cm}
Variable sortante : $u_1$
\end{center}

\vspace{-2mm}
\noindent
\begin{tabular}{ll}
$
{\renewcommand{\arraystretch}{0.9}
\renewcommand{\arraycolsep}{1pt}
\begin{array}{rrrrrr|r}
\hspace{3mm}z&\hspace{6mm}x_1&\hspace{6mm}x_2&\hspace{6mm}u_1&\hspace{6mm}u_2&\hspace{6mm}u_3&\hspace{8mm}\\
\hline
1&0&0&0&0&1&18\\
\hline
0&0&0&3&1&-1&6\\
0&0&1&-3/2&0&1/2&3\\
0&1&0&1&0&0&4\\
\hline
\end{array}}
$
&
\begin{tabular}{l}
Variables hors base : $u_1$, $u_3$\\
Solution de base : $(4,3,0,6,0)$\\
Valeur de l'objectif : $z=18$
\end{tabular}
\end{tabular}

\noindent
Autre sommet optimal : $(x_1,x_2,u_1,u_2,u_3)=(4,3,0,6,0)$

\vspace{-5mm}
\subsubsection{Remarque}
Tous les points de l'ar� comprise entre les sommets $(2,6,2,0,0)$ et $(4,3,0,6,0)$ sont optimaux.

\section{Algorithme du simplexe}
\begin{description}
\item[Pas 0 : ] Initialisation
  \begin{itemize}
  \item Mettre le probl� sous forme standard (contraintes d'�lit�et variables positives)
  \item Trouver une premi� solution de base r�isable (utiliser  la m�ode de la section suivante si n�ssaire)
\item Si aucune solution de base r�isable n'existe, alors STOP. Le probl� est irr�isable.
  \end{itemize}
\item[Pas 1 : ] Choix de la variable entrante
  \begin{itemize}
  \item Choisir comme variable entrante une variable hors base qui am�ore la valeur courante de l'objectif.
\item Si aucune variable hors base n'est candidate, alors STOP. La solution de base r�isable courante est une solution optimale.
\item Si la solution de base courante est optimale et qu'il existe une variable hors base qui pourrait entrer sans modifier la valeur de l'objectif, alors le probl� poss� une infinit�e solutions optimales. Sinon, le probl� poss� une solution optimale unique.
  \end{itemize}
\item[Pas 2 : ] Choix de la variable sortante
  \begin{itemize}
  \item La variable sortante est la variable de base qui s'annule en premier lieu lors de l'augmentation de la valeur de la variable entrante. Si plusieurs variables s'annulent en m� temps, choisir une de celles-ci.
\item Si aucune variable de base ne s'annule lors de l'augmentation de la valeur de la variable entrante, alors STOP. Le probl� est non born�  \end{itemize}

\newpage
\item[Pas 3 : ] D�rminer la nouvelle solution de base
  \begin{itemize}
  \item Exprimer la variable entrante en fonction des autres variables �'aide de la contrainte qui explicitait la variable sortante.
\item Eliminer la variable entrante des autres contraintes et de l'objectif.
\item Retourner au \textbf{Pas 1} avec la nouvelle base r�isable.
  \end{itemize}

\end{description}

\paragraph{Remarque :} Pour �ter le cyclage de l'algorithme du simplexe, il suffit de choisir parmi les variable entrantes candidates, la variable de plus petit indice, et de faire de m� pour le choix de la variable sortante.