Accueil
slides-dual.tex
slides-dual.tex
—
TeX document,
21Kb
Contenu du fichier
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{La dualit�t l'algorithme dual-simplexe}
\newpage
\minitoc
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Construction intuitive du dual}
\subsection{Un probl� lin�re}
\begin{center}
\begin{tabular}{cc}
$
{\renewcommand{\arraystretch}{1.1} \renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\min z & = \begin{array}{rcrcr} 14 x_1 & + & 12 x_2 & + & 12x_3 \end{array} \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcrcrcr}
x_1 & - &2x_2 & + & 2x_3 & \geq & 1\\
x_1 & + &3x_2 & - & x_3 & \geq & 3\\
\multicolumn{5}{r}{x_1,x_2,x_3} & \geq & 0
\end{array}\right.
\end{array}}
$
&
\begin{tabular}{c}
Solution optimale\\
$(x_1^*,x_2^*,x_3^*)=(9/5,2/5,0)$\\
$z^*=30$.
\end{tabular}
\end{tabular}
\end{center}
\subsection{Borne sup�eure}
\paragraph{Remarque : }
Toute solution r�isable pour le probl� lin�re fournit une borne sup�eure pour la valeur optimale de l'objectif $z^*$.
\paragraph{Exemple : }
Le point $(2,1/2,0)$ est une solution r�isable pour le probl� lin�re. On a donc :
$$z^*\le2\times14+1/2\times12+0\times12=34$$
\subsection{Borne inf�eure}
\subsubsection{Une premi� borne inf�eure}
$$
\begin{array}{rcl}
z=14x_1+12x_2+12x_3 &\ge& 4\times(x_1+3x_2-x_3) = 4x_1+12x_2-4x_3\\
&\ge& 4\times3 = 12
\end{array}
$$
\subsubsection{Une seconde borne inf�eure}
$$
\begin{array}{rcl}
z=14x_1+12x_2+12x_3 &\ge& 7\times(x_1-2x_2+2x_3)+7\times(x_1+3x_2-x_3)\\
&=& 14 x_1 + 7 x_2 + 7 x_3 \ge 7\times1 + 7\times3 = 28
\end{array}
$$
\subsection{Le probl� dual (= meilleure borne inf�eure)}
\begin{center}
\begin{tabular}{cc}
$
{\renewcommand{\arraystretch}{1.1} \renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\max w & = \begin{array}{rcr} y_1 & + & 3y_2 \end{array} \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcrcrcr}
y_1 & + &y_2 & \leq & 14\\
-2y_1 & + & 3y_2 & \leq & 12\\
2y_1 & - & y_2 & \leq & 12\\
\multicolumn{3}{l}{y_1,y_2} & \geq & 0
\end{array}\right.
\end{array}}
$
&
\begin{tabular}{c}
Solution optimale\\
$(y_1^*,y_2^*)=(6,8)$\\
$w^* = 30$
\end{tabular}
\end{tabular}
\end{center}
\section{D�nition}
\subsection{Probl� primal}
$$
{\renewcommand{\arraystretch}{0.9}
\begin{array}{ll}
\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}{ccr}
a_{11}x_{1}+a_{12}x_{2}+\cdots+a_{1n}x_{n}&\geq&b_1,\\
a_{21}x_{1}+a_{22}x_{2}+\cdots+a_{2n}x_{n}&\geq&b_2,\\
\vdots & &\vdots\\
a_{m1}x_{1}+a_{m2}x_{2}+\cdots+a_{mn}x_{n}&\geq&b_m, \\
\multicolumn{1}{r}{x_{1}, x_{2}, \cdots, x_{n}} &\geq&0.
\end{array}
\right.
\end{array}
}
$$
\subsection{Probl� dual}
$$
{\renewcommand{\arraystretch}{0.9}
\begin{array}{ll}
\max w & = y_1 b_1+y_2 b_2+ \cdots+y_m b_m,\\
\mbox{s.c.q.} & \left\{
\begin{array}{ccl}
y_1 a_{11}+y_2 a_{21}+ \cdots +y_m a_{m1} & \le & c_1, \\
y_1 a_{12}+y_2 a_{22}+ \cdots +y_m a_{m2} & \le & c_2, \\
\vdots & & \vdots \\
y_1 a_{1n}+y_2 a_{2n}+ \cdots +y_m a_{mn} & \le & c_n,\\
\multicolumn{1}{r}{y_1,y_2,\ldots,y_m}&\ge&0.
\end{array}\right.
\end{array}
}
$$
\section{Repr�ntation matricielle}
$$
{\renewcommand{\arraystretch}{1.5}
\begin{array}{ccc}
\mbox{\textbf{Probl� primal}} & \hspace{1cm} & \mbox{\textbf{Probl� dual}}\\[2mm]
\begin{array}{ll}
\min_{\bm{x}} & z=\bm{c} \bm{x}\\
\mbox{s.c.q.} & \left\{
\begin{array}{rcl}
\bm{A} \bm{x} & \ge & \bm{b}\\
\bm{x} & \ge & \bm{0}
\end{array}\right.
\end{array}
&
&
\begin{array}{ll}
\max_{\bm{y}} & w=\bm{y} \bm{b} \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcl}
\bm{y} \bm{A} & \le & \bm{c}\\
\bm{y} & \ge & \bm{0}
\end{array}\right.
\end{array}
\end{array}
}
$$
o�\bm{A}=\begin{bmatrix}
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{m1} & a_{m2} & \cdots & a_{mn}
\end{bmatrix}
\bm{x}=\begin{bmatrix} x_1\\x_2\\\vdots\\x_n \end{bmatrix}
\bm{b}=\begin{bmatrix} b_1\\b_2\\\vdots\\b_m \end{bmatrix}
\begin{array}{l}
\bm{c}=\begin{bmatrix} c_1&c_2&\hdots&c_n \end{bmatrix}\\
\\
\bm{y}=\begin{bmatrix} y_1&y_2&\hdots&y_m \end{bmatrix}
\end{array}
$$
\section{Dual d'un probl� de minimisation g�ral}
%%%%%%%%%%%
\subsection{Un exemple}
\subsubsection{Le probl� de minimisation et sa forme canonique}
$$
{\renewcommand{\arraystretch}{1.1} \renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\min z & = \begin{array}{rcrcr} 80 \xi_1 & - & 10\xi_2 & + &50\xi_3 \end{array} \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcrcrcrcr}
3\xi_1 & - &\xi_2 & + & \xi_3 & \leq & 3\\
\xi_1 & + & 2\xi_2 & - &\xi_3 & = & -4\\
\xi_1 & + & \xi_2 & - &\xi_3 & \geq & 2\\
\xi_1 & & & & & \geq & 0\\
& & \xi_2 & & & \leq & 0\\
& & & & \xi_3 &\in & \R \\
\end{array}\right.
\end{array}
}
\Longleftrightarrow
{\renewcommand{\arraystretch}{1.1} \renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\min z & = \begin{array}{rcrcrcr} 80 \lambda_1 & + & 10\lambda_2 & + &50\lambda_3 & - & 50\lambda_4 \end{array} \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcrcrcrcr}
-3\lambda_1 & - &\lambda_2 & - & \lambda_3 & + & \lambda_4 & \geq & -3\\
-\lambda_1 & + & 2\lambda_2 & + &\lambda_3 & - & \lambda_4 & \geq & 4\\
\lambda_1 & - & 2\lambda_2 & - &\lambda_3 & + & \lambda_4 & \geq & -4\\
\lambda_1 & - & \lambda_2 & - &\lambda_3 & + & \lambda_4 & \geq & 2\\
\lambda_1 & , & \lambda_2 & , & \lambda_3 & , & \lambda_4 & \geq & 0\\
\end{array}\right.
\end{array}
}
$$
$$
\begin{array}{l}
\lambda_1=\xi_1\\
\lambda_2=-\xi_2\\
\lambda_3-\lambda_4=\xi_3
\end{array}
$$
\newpage
\subsubsection{La forme canonique et son dual}
\vspace{1cm}
$$
{\renewcommand{\arraystretch}{1.1} \renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\min z & = \begin{array}{rcrcrcr} 80 \lambda_1 & + & 10\lambda_2 & + &50\lambda_3 & - & 50\lambda_4 \end{array} \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcrcrcrcr}
-3\lambda_1 & - &\lambda_2 & - & \lambda_3 & + & \lambda_4 & \geq & -3\\
-\lambda_1 & + & 2\lambda_2 & + &\lambda_3 & - & \lambda_4 & \geq & 4\\
\lambda_1 & - & 2\lambda_2 & - &\lambda_3 & + & \lambda_4 & \geq & -4\\
\lambda_1 & - & \lambda_2 & - &\lambda_3 & + & \lambda_4 & \geq & 2\\
\lambda_1 & , & \lambda_2 & , & \lambda_3 & , & \lambda_4 & \geq & 0\\
\end{array}\right.
\end{array}
}
\Longleftrightarrow
{\renewcommand{\arraystretch}{1.1} \renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\max w & = \begin{array}{rcrcrcr} -3 x_1 & + & 4x_2 & - &4x_3 & + & 2x_4 \end{array} \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcrcrcrcr}
-3x_1 & - &x_2 & + & x_3 & + & x_4 & \leq & 80\\
-x_1 & + & 2x_2 & - &2x_3 & - & x_4 & \leq & 10\\
-x_1 & + & x_2 & - &x_3 & - & x_4 & \leq & 50\\
x_1 & - & x_2 & + &x_3 & + & x_4 & \leq & -50\\
x_1 & , & x_2 & , & x_3 & , & x_4 & \geq & 0\\
\end{array}\right.
\end{array}
}
$$
\newpage
\subsubsection{Dual de la forme canonique et dual du probl� original}
\vspace{1cm}
$$
{\renewcommand{\arraystretch}{1.1} \renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\max w & = \begin{array}{rcrcrcr} -3 x_1 & + & 4x_2 & - &4x_3 & + & 2x_4 \end{array} \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcrcrcrcr}
-3x_1 & - &x_2 & + & x_3 & + & x_4 & \leq & 80\\
-x_1 & + & 2x_2 & - &2x_3 & - & x_4 & \leq & 10\\
-x_1 & + & x_2 & - &x_3 & - & x_4 & \leq & 50\\
x_1 & - & x_2 & + &x_3 & + & x_4 & \leq & -50\\
x_1 & , & x_2 & , & x_3 & , & x_4 & \geq & 0\\
\end{array}\right.
\end{array}
}
\Longleftrightarrow
{\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}
3y_1 & + &y_2 & + & y_3 & \leq & 80\\
-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}
}
$$
$$
\begin{array}{l}
y_1=-x_1\\
y_2=x_3-x_2\\
y_3=x_4
\end{array}
$$
\newpage
\subsection{Le probl� primal et son dual}
\vspace{1cm}
$$
\begin{array}{ccc}
\textbf{Probl� primal} & \hspace{1cm} &\textbf{Probl� dual}\\
\\
{\renewcommand{\arraystretch}{1.1} \renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\min z & = \begin{array}{rcrcr} 80 \xi_1 & - & 10\xi_2 & + &50\xi_3 \end{array} \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcrcrcrcr}
3\xi_1 & - &\xi_2 & + & \xi_3 & \leq & 3\\
\xi_1 & + & 2\xi_2 & - &\xi_3 & = & -4\\
\xi_1 & + & \xi_2 & - &\xi_3 & \geq & 2\\
\xi_1 & & & & & \geq & 0\\
& & \xi_2 & & & \leq & 0\\
& & & & \xi_3 &\in & \R \\
\end{array}\right.
\end{array}
}
&
&
{\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}
3y_1 & + &y_2 & + & y_3 & \leq & 80\\
-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}
}
\end{array}
$$
\newpage
\subsection{G�ralisation}
%\noindent
%A chaque contrainte de {\large (P)} est associ�une variable de {\large(D)}.\\
%A chaque variable de {\large (P)} est associ�une contrainte de {\large (D)}.\\
\subsubsection{Probl� primal}
$$
\begin{array}{ll}
\min z & = \displaystyle \sum_{j=1}^n c_{j}\: x_j\\
\mbox{s.c.q.} & \left\{
\begin{array}{lllcc}
\displaystyle \sum_{j=1}^n a_{ij}\: x_j \ge b_i&&i=1,\ldots,r&&(A)\\
\displaystyle \sum_{j=1}^n a_{ij}\: x_j = b_i&&i=r+1,\ldots,s&&(B)\\
\displaystyle \sum_{j=1}^n a_{ij}\: x_j \le b_i&&i=s+1,\ldots,m&&(C)\\
\displaystyle x_j \ge 0&&j=1,\ldots,p&&[I]\\
\displaystyle x_j \in \R &&j=p+1,\ldots,q&&[II]\\
\displaystyle x_j \le 0&&j=q+1,\ldots,n&&[III]\\
\end{array}
\right.
\end{array}
$$
\subsubsection{Probl� dual}
$$
\begin{array}{ll}
\max w & = \displaystyle \sum_{i=1}^m \lambda_{i}\: b_i \\
\mbox{s.c.q.} & \left\{
\begin{array}{lllcc}
\displaystyle \sum_{i=1}^m \lambda_i\: a_{ij} \le c_j&&j=1,\ldots,p&&[I]\\
\displaystyle \sum_{i=1}^m \lambda_i\: a_{ij}= c_j&&j=p+1,\ldots,q&&[II]\\
\displaystyle \sum_{i=1}^m \lambda_i\: a_{ij} \ge c_j&&j=q+1,\ldots,n&&[III]\\
\displaystyle \lambda_i \ge 0&&i=1,\ldots,r&&(A)\\
\displaystyle \lambda_i \in \R &&i=r+1,\ldots,s&&(B)\\
\displaystyle \lambda_i \le 0&&i=s+1,\ldots,m&&(C)\\
\end{array}
\right.
\end{array}
$$
%%%%%%%%
\newpage
\section{Propri�s}
\begin{svpro}
Le probl� dual du dual d'un probl� lin�re est ce probl� lin�re.
\end{svpro}
\begin{svthe}
Etant donn�n couple de PLs primal et dual, une et une seule des affirmations suivantes est vraie~:
\begin{itemize}
\item Les deux PLs poss�nt des solutions optimales et, �'optimum, les valeurs des deux fonctions objectif sont identiques;
\item Un PL est non born�t l'autre PL est non r�isable;
\item Les deux PLs sont non r�isables.
\end{itemize}
\end{svthe}
\begin{svpro}
Soit $z^*$ la valeur optimale de l'objectif d'un probl� primal et $y_i^*$ la valeur optimale de la variable duale associ��a contrainte $i$ de ce probl� primal. Si l'on accro�d'une unit�e membre de droite de la contrainte $i$ du probl� primal alors $z^*$ va augmenter de $y_i^*$.
\end{svpro}
\begin{svthe} (\textbf{Th�� des �rts compl�ntaires})
Soit un couple de PLs primal et dual (voir repr�ntation matricielle). Des solutions r�isables $x^*$, pour le PL primal, et $y^*$, pour le probl� dual, sont optimales si, et seulement si, elles satisfont aux deux �ations matricielles
$$
y^*(Ax^*-b)=0
\text{ et }
(c-y^*A)x^*=0.
$$
\end{svthe}
\begin{svpro}
Les deux �ations matricielles du th�� pr�dent sont �ivalentes aux assertions suivantes~:
$$
\begin{array}{ccc}
y_i^*>0 & \Rightarrow & \sum_{j=1}^n a_{ij}\:x_j^* = b_i\\\\
\sum_{j=1}^n a_{ij}\:x_j^* > b_i & \Rightarrow & y_i^*=0\\\\
\sum_{i=1}^m y_i^*\:a_{ij} < c_j & \Rightarrow & x_j^*=0\\\\
x_j^*>0 & \Rightarrow & \sum_{i=1}^m y_i^*\:a_{ij}=c_j
\end{array}
$$
\end{svpro}
\newpage
\begin{svcor}
Une solution r�isable $(x^*_1,x^*_2,\ldots,x^*_n)$ du probl� primal est optimale si et seulement si on peut trouver des nombres $(y^*_1,y^*_2,\ldots,y^*_m)$ tels que~:
$$
\left.\begin{array}{ccc}
\sum_{i=1}^m a_{ij}\:y_i^*=c_j & \text{chaque fois que} & x_j^*>0 \\
y_i^*=0 & \text{chaque fois que} & \sum_{j=1}^n a_{ij}\:x_j^* > b_i \\
\end{array}\right\} \text{compl�ntarit�$$
$$
\left.\begin{array}{ccc}
\sum_{i=1}^m a_{ij}\:y_i^* \leq c_j & \text{pour tout} & j=1,2,\ldots,n\\
y_i^*\geq0 & \text{pour tout} & i=1,2,\ldots,m\\
\end{array}\right\} \text{r�isabilit�$$
\end{svcor}
\begin{svcor}
Une solution r�isable $(y^*_1,y^*_2,\ldots,y^*_m)$ du probl� dual est optimale si et seulement si on peut trouver des nombres $(x^*_1,x^*_2,\ldots,x^*_n)$ tels que~:
$$
\left.\begin{array}{ccc}
\sum_{j=1}^n a_{ij}\:x_j^*=b_i & \text{chaque fois que} & y_i^*>0 \\
x_j^*=0 & \text{chaque fois que} & \sum_{i=1}^m a_{ij}\:y_i^* < b_i \\
\end{array}\right\} \text{compl�ntarit�$$
$$
\left.\begin{array}{ccc}
\sum_{j=1}^n a_{ij}\:x_j^* \geq b_i & \text{pour tout} & i=1,2,\ldots,m\\
x_j^*\geq0 & \text{pour tout} & j=1,2,\ldots,n\\
\end{array}\right\} \text{r�isabilit�$$
\end{svcor}
\newpage
{\samepage
\begin{svexe}
Montrer que $(x^*_1,x^*_2,x^*_3,x^*_4,x^*_5)=(1/3,0,5/3,1,0)$ est la solution optimale du probl�~:\\
\mbox{ }\hspace{1cm}$
{\renewcommand{\arraystretch}{1.1} \renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\min z & = \begin{array}{rcrcrcrcr} x_1 & - & 2x_2 & + &4x_3 & + & x_4 & + & 5x_5\end{array} \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcrcrcrcrcr}
2x_1 & - & 3x_2 & + & 8x_3 & + & 4x_4 & + & 5x_5 &\geq & 18\\
-6x_1 & - & x_2 & - & 3x_3 & & & + & 2x_5 &\geq & -7\\
2x_1 & + & 4x_2 & + & 5x_3 & + & 8x_4 & - & 3x_5 &\geq & 12\\
7x_1 & - & 3x_2 & - & 2x_3 & + & 7x_4 & + & 6x_5 &\geq & 5\\
3x_1 & + & x_2 & & & - & x_4 & - & 2x_5 &\geq & 0\\
8x_1 & + & 2x_2 & + & 2x_3 & + & 3x_4 & - & x_5 &\geq & 8\\
\multicolumn{9}{r}{x_1 , x_2 , x_3 , x_4 , x_5} &\geq & 0\\
\end{array}\right.
\end{array}
}
$
\end{svexe}
\begin{svexe}
Montrer que $(y^*_1,y^*_2,y^*_3,y^*_4,y^*_5)=(0,2,0,7,0)$ n'est pas la solution optimale du probl�~:\\
\mbox{ }\hspace{1cm}$
{\renewcommand{\arraystretch}{1.1} \renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\max w & = \begin{array}{rcrcrcrcr} 8y_1 & - & 9y_2 & + &12y_3 & + & 4y_4 & + & 11y_5\end{array} \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcrcrcrcrcr}
2y_1 & - & 3y_2 & + & 4y_3 & + & y_4 & + & 3y_5 &\leq & 1\\
y_1 & + & 7y_2 & + & 3y_3 & - & 2y_4 & + & y_5 &\leq & 1\\
5y_1 & + & 4y_2 & - & 6y_3 & + & 2y_4 & + & 3y_5 &\leq & 22\\
\multicolumn{9}{r}{y_1 , y_2 , y_3 , y_4 , y_5} &\geq & 0\\
\end{array}\right.
\end{array}
}
$
\end{svexe}
}
%%%%%%%%
\newpage
\section{Algorithme dual-simplexe}
\subsection{Repr�ntation matricielle et tableau simplexe}
\begin{center}
%Si
\begin{tabular}{cc}
${\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1pt}
\begin{array}{cc}
\max/\min & z=cx\\
\mbox{s.c.q.} & \left\{\begin{array}{ccc}
Ax & = & b\\
x & \geq & 0
\end{array}
\right.
\end{array}
}$
&
$
\begin{array}{l}
\bar{A}=B^{-1}A\\
\bar{b}=B^{-1}b\\
\bar{c}=c-c_BB^{-1}A
\end{array}
$
\\
\\
%est la repr�ntation matricielle d'un PL sous forme standard et $B$ la matrice carr�form�par les colonnes de $A$ associ� aux variables de la base courante,\\
%alors la forme tableau de la solution de base courante est repr�nt�matriciellement par~:
\multicolumn{2}{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}
\subsection{Algorithme}
\begin{description}
\item[Pas 0 : ] Initialisation
\begin{itemize}
\item Mettre le probl� sous forme standard (contraintes d'�lit�et variables positives)
\item Trouver une solution de base \textbf{dual-r�isable} (tous les co�elatifs $\bar{c}_j$ sont positifs (n�tifs) dans le cas d'un probl� de minimisation (maximisation))
\end{itemize}
\item[Pas 1 : ] Choix de la variable sortante
\begin{itemize}
\item Choisir comme variable sortante une variable en base dont la valeur est strictement n�tive. Soit $x_{i_r}$ cette variable, $\bar{b}_r$ la valeur de cette variable et $r$ le num� de la contrainte qui donne cette valeur.
\item Si aucune variable de base n'est strictement n�tive, alors STOP. La solution de base dual-r�isable courante est primal-r�isable et optimale.
\end{itemize}
\item[Pas 2 : ] Choix de la variable entrante
\begin{itemize}
\item Choisir, parmi les variables hors base $x_j$ qui v�fie $\bar{a}_{rj}<0$, celle qui minimise le rapport $\mid\frac{\bar{c}_j}{\bar{a}_{rj}}\mid$. Soit $x_{s}$ cette variable.
\item Si aucune variable hors base n'est candidate, alors STOP. Le probl� est irr�isable (Le probl� dual est non born�.
\end{itemize}
\item[Pas 3 : ] D�rminer la nouvelle solution de base (pivotage)
\begin{itemize}
\item Exprimer la variable entrante $x_{s}$ en fonction des autres variables �'aide de la contrainte $r$ qui explicitait la variable sortante $x_{i_r}$.
\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}
\subsection{Un probl� primal et son dual}
$$
\begin{array}{lcl}
\textbf{Forme canonique} & \hspace{3mm} &\textbf{Forme standard}\\
\\
{\renewcommand{\arraystretch}{1.1} \renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\min z & = \begin{array}{rcrcr} 14 x_1 & + & 12 x_2 & + & 12x_3 \end{array} \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcrcrcr}
x_1 & - &2x_2 & + & 2x_3 & \geq & 1\\
x_1 & + &3x_2 & - & x_3 & \geq & 3\\
\multicolumn{5}{l}{x_1,x_2,x_3} & \geq & 0
\end{array}\right.
\end{array}}
&
&
{\renewcommand{\arraystretch}{1.1} \renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\min z & = \begin{array}{rcrcr} 14 x_1 & + & 12 x_2 & + & 12x_3 \end{array} \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcrcrcrcr}
x_1 & - &2x_2 & + & 2x_3 & - & t_1 &= & 1\\
x_1 & + &3x_2 & - & x_3 & - & t_2 & = & 3\\
\multicolumn{7}{r}{x_1,x_2,x_3,t_1,t_2} &\geq & 0\\
\end{array}\right.
\end{array}
}
\\
\\
{\renewcommand{\arraystretch}{1.1} \renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\max w & = \begin{array}{rcr} y_1 & + & 3y_2 \end{array} \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcrcrcr}
y_1 & + &y_2 & \leq & 14\\
-2y_1 & + & 3y_2 & \leq & 12\\
2y_1 & - & y_2 & \leq & 12\\
\multicolumn{3}{l}{y_1,y_2} & \geq & 0
\end{array}\right.
\end{array}}
&
&
{\renewcommand{\arraystretch}{1.1} \renewcommand{\arraycolsep}{1.0 pt}
\begin{array}{ll}
\max w & = \begin{array}{rcr} y_1 & + & 3y_2 \end{array} \\
\mbox{s.c.q.} & \left\{
\begin{array}{rcrcrcrcr}
y_1 & + &y_2 & + & u_1 &= & 14\\
-2y_1 & + & 3y_2 & + & u_2 & = & 12\\
2y_1 & - & y_2 & + & u_3 &= & 12\\
\multicolumn{5}{r}{y_1 , y_2, u_1,u_2,u_3 }& \geq & 0\\
\end{array}\right.
\end{array}
}
\end{array}
$$
\subsection{R�lution en parall� du primal et du dual}
\subsubsection{Premi� solution de base}
\begin{tabular}{cc}
\begin{tabular}{c}
Algorithme\\
Dual-Simplexe\\
Tableau 1
\end{tabular}
&
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|r|r}
z & x_{1} & x_{2} & x_{3} & t_{1} & t_{2} & 1\\
\hline
1&-14&-12&-12&0&0&0&z\\
\hline
0&-1&2&-2&1&0&-1&t_{1}\\
0&-1&-3&1&0&1&-3&t_{2}\\
\hline
\end{array}
$\\
\\
\begin{tabular}{c}
Algorithme du\\
Simplexe\\
Tableau 1
\end{tabular}
&
$ \renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|r|r}
w&y_{1}&y_{2}&u_{1}&u_{2}&u_{3}&1\\
\hline
1&-1&-3&0&0&0&0&w\\
\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}
$
\end{tabular}
\subsubsection{Deuxi� solution de base}
\begin{tabular}{cc}
\begin{tabular}{c}
Algorithme\\
Dual-Simplexe\\
Tableau 2
\end{tabular}
&
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|r|r}
z & x_{1} & x_{2} & x_{3} & t_{1} & t_{2} & 1\\
\hline
1&-10&0&-16&0&-4&12&z\\
\hline
0&-\frac{5}{3}&0&-\frac{4}{3}&1&\frac{2}{3}&-3&t_{1}\\
0&\frac{1}{3}&1&-\frac{1}{3}&0&-\frac{1}{3}&1&x_{2}\\
\hline
\end{array}
$\\
\\
\begin{tabular}{c}
Algorithme du\\
Simplexe\\
Tableau 2
\end{tabular}
&
$ \renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|r|r}
w&y_{1}&y_{2}&u_{1}&u_{2}&u_{3}&1\\
\hline
1&-3&0&0&1&0&12&w\\
\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&y_{2}\\
0&\frac{4}{3}&0&0&\frac{1}{3}&1&16&u_{3}\\
\hline
\end{array}
$
\end{tabular}
\subsubsection{Troisi� solution de base}
\begin{tabular}{cc}
\begin{tabular}{c}
Algorithme\\
Dual-Simplexe\\
Tableau 3
\end{tabular}
&
$
\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|r|r}
z & x_{1} & x_{2} & x_{3} & t_{1} & t_{2} & 1\\
\hline
1&0&0&-8&-6&-8&30&z\\
\hline
0&1&0&\frac{4}{5}&-\frac{3}{5}&-\frac{2}{5}&\frac{9}{5}&x_{1}\\
0&0&1&-\frac{3}{5}&\frac{1}{5}&-\frac{1}{5}&\frac{2}{5}&x_{2}\\
\hline
\end{array}
$\\
\\
\begin{tabular}{c}
Algorithme du\\
Simplexe\\
Tableau 3
\end{tabular}
&
$ \renewcommand{\arraystretch}{1.4}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|r|r}
w&y_{1}&y_{2}&u_{1}&u_{2}&u_{3}&1\\
\hline
1&0&0&\frac{9}{5}&\frac{2}{5}&0&30&w\\
\hline
0&1&0&\frac{3}{5}&-\frac{1}{5}&0&6&y_{1}\\
0&0&1&\frac{2}{5}&\frac{1}{5}&0&8&y_{2}\\
0&0&0&-\frac{4}{5}&\frac{3}{5}&1&8&u_{3}\\
\hline
\end{array}
$
\end{tabular}
\paragraph{Conclusion : }L'unique solution optimale est trouv�\par
