Accueil
slides-phase1.tex
slides-phase1.tex
—
TeX document,
9Kb
Contenu du fichier
\newpage
%%%%%%%%%%%
\section{Initialisation de l'algorithme du simplexe}
\subsection{Un probl� et sa repr�ntation graphique}
\begin{center}
\begin{tabular}{cc}
\begin{tabular}{c}
$
{\renewcommand{\arraystretch}{1.2}
\begin{array}[b]{l}
\mbox{max } z = 3 x_1 + 5 x_2 \\
\mbox{s.c.q.} \left\{ \begin{array}{rcrcr}
& & 2 x_2 &\leq& 12\\
x_1 &-& 2 x_2 &\leq& -2\\
-3 x_1 &-& 2 x_2 &\leq& -18\\
x_1 &,& x_2 &\geq& 0
\end{array} \right.
\end{array}}
$\\
\\
$(x_1,x_2)^*=(10,6)$\\
$z^*=60$
\end{tabular}
&
%\framebox
{
% PARAMETRES
\psset{unit=0.4cm}
\psset{arrowinset=0}
\begin{pspicture}[0.5](-1,-1)(13,11)
% AXES
% ,labels=none
\psaxes[Dx=3,Dy=3,tickstyle=top]{->}(0,0)(0,0)(12,10)
\rput(13,0){$x_1$}\rput(0,11){$x_2$}
% CONTRAINTES
\psline(0,1)(12,7) \psline(0,6)(12,6) \psline(0,9)(6,0)
\pspolygon[linewidth=0pt,fillstyle=solid,fillcolor=lightgray](4,3)(10,6)(2,6)
% OBJECTIF
\psline[linestyle=dashed](5,0)(0,3) \psline{->}(3.25,1.25)(3.65,1.8)
% SOMMETS
\psset{dotstyle=*}\psset{dotscale=1.1}
\psdots(4,3)\psdots(10,6)\psdots(2,6)
\rput(5.5,3){$(4,3)$}\rput(10,5){$(10,6)$}\rput(3,7){$(2,6)$}
\end{pspicture}
}
%\BoxedEPSF{./FUNDP_AD_SLIDES.eps/ProbPhase1.eps scaled 450}
\end{tabular}
\end{center}
\subsection{Probl� original sous forme standard}
$$
{\renewcommand{\arraystretch}{1.3}
\begin{array}{l}
\max z = 3 x_1 + 5 x_2 \\
\mbox{s.c.q.} \left\{ \begin{array}{rcrrrrcr}
& & 2 x_2 & + u_1 & & &=& 12\\
x_1 &-& 2 x_2 & &+ u_2 & &=& -2\\
-3x_1 &-& 2 x_2 & & & + u_3 &=& -18\\
x_1,& & x_2,& u_1,& u_2,& u_3&\geq& 0
\end{array} \right.
\end{array}}
$$
\noindent
\begin{tabular}{ll}
$
{\renewcommand{\arraystretch}{1.0}
\renewcommand{\arraycolsep}{2pt}
\begin{array}{rrrrrr|r}
\hspace{6mm}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&-5&0&0&0&0\\
\hline
0&0&2&1&0&0&12\\
0&1&-2&0&1&0&-2\\
0&-3&-2&0&0&1&-18\\
\hline
\end{array}}
$
&
\begin{tabular}{c}
Variables hors base :\\$x_1$, $x_2$\\
Solution de base :\\$(0,0,12,-2,-18)$
\end{tabular}
\end{tabular}
\bigskip
\textbf{Probl� :} La solution de base n'est pas r�isable.
%On ne peut donc pas d�rrer l'algorithme du Simplexe.
%Du point de vue g��ique �signifie que le point (0,0) n'est pas un sommet du polygone des solutions r�isabe.
\subsection{Probl� de phase 1}
$$
{\renewcommand{\arraystretch}{1.3}
\begin{array}{l}
\mbox{min } v = t_1+t_2\\
\mbox{s.c.q. }\left\{ \begin{array}{rrrrrrrcr}
& 2x_2 & +u_1 & & &&&=& 12\\
-x_1 & +2x_2 & &-u_2 & &+t_1 & &=& 2\\
3x_1 &+ 2x_2 & & & -u_3 & &+t_2 &=&18\\
\multicolumn{7}{r}{x_1, x_2, u_1, u_2, u_3, t_1, t_2}&\geq& 0
\end{array} \right. \end{array}
}
$$
\textbf{Remarques :}
\begin{itemize}
\item La valeur de l'objectif $v$ est sup�eure ou �le �� pour toutes les solutions r�isables.
\item Si la valeur de $v$ �'optimum est strictement positive, alors le probl� original n'est pas r�isable.
\item Si la valeur de $v$ �'optimum est nulle, alors la solution optimale du probl� de phase 1 est une solution de base
r�isable du probl� original.
\end{itemize}
\subsection{R�lution du probl� de phase 1}
$$
{\renewcommand{\arraystretch}{1.2}
\begin{array}{rrrrrrrr|r|c}
v&x_1&x_2&u_1&u_2&u_3&t_1&t_2&1&\\
\hline
1&2&4&0&-1&-1&0&0&20&v\\
\hline
0&0&2&1&0&0&0&0&12&u_1\\
0&-1&\fbox{2}&0&-1&0&1&0&2&t_1\\
0&3&2&0&0&-1&0&1&18&t_2\\
\hline
\end{array}}
$$
\begin{center}
{\bf Premi� it�tion~:} $x_2$ entre et $t_1$ sort.
\end{center}
$$
{\renewcommand{\arraystretch}{1.2}
\begin{array}{rrrrrrrr|r|c}
v&x_1&x_2&u_1&u_2&u_3&t_1&t_2&1\\
\hline
1&4&0&0&1&-1&-2&0&16&v\\
\hline
0&1&0&1&1&0&-1&0&10&u_1\\
0&-\frac{1}{2}&1&0&-\frac{1}{2}&0&\frac{1}{2}&0&1&x_2\\
0&\fbox{4}&0&0&1&-1&-1&1&16&t_2\\
\hline
\end{array}}
$$
\begin{center}
{\bf Deuxi� it�tion~:} $x_1$ entre et $t_2$ sort.
\end{center}
$$
{\renewcommand{\arraystretch}{1.2}
\begin{array}{rrrrrrrr|r|c}
v&x_1&x_2&u_1&u_2&u_3&t_1&t_2&1\\
\hline
1&0&0&0&0&0&-1&0&0&v\\
\hline
0&0&0&1&\frac{3}{4}&\frac{1}{4}&-\frac{3}{4}&-\frac{1}{4}&6&u_1\\
0&0&1&0&-\frac{3}{8}&-\frac{1}{8}&\frac{3}{8}&\frac{1}{8}&3&x_2\\
0&1&0&0&\frac{1}{4}&-\frac{1}{4}&-\frac{1}{4}&\frac{1}{4}&4&x_1\\
\hline
\end{array}}
$$
\begin{center}
\textbf{Variable entrante} : aucune candidate
\end{center}
\textbf{Conclusion :}
\begin{itemize}
\item Solution optimale du probl� de phase 1 :
$$(x_1,x_2,u_1,u_2,u_3,t_1,t_2)=(4,3,6,0,0,0,0)$$
\item Valeur optimale de l'objectif du primal : $v=0$\\
\item $(x_1,x_2,u_1,u_2,u_3)=(4,3,6,0,0)$ est donc une solution de base r�isable pour le probl� original.
\end{itemize}
\newpage
\subsection{Retour au probl� original}
\begin{enumerate}
\item Enlever les variables $t_1$ et $t_2$ et
remplacer l'objectif du probl� de phase 1 par l'objectif du probl� original.\\
$
{\renewcommand{\arraystretch}{1.2}
\begin{array}{rrrrrr|r|c}
z&x_1&x_2&u_1&u_2&u_3&1&\\
\hline
1&-3&-5&0&0&0&0&z\\
\hline
0&0&0&1&3/4&1/4&6&u_1\\
0&0&1&0&-3/8&-1/8&3&x_2\\
0&1&0&0&1/4&-1/4&4&x_1\\
\hline
\end{array}}
$
\item Eliminer les variables de base de l'objectif.\\
$
{\renewcommand{\arraystretch}{1.2}
\begin{array}{rrrrrr|r|c}
z&x_1&x_2&u_1&u_2&u_3&1&\\
\hline
1&0&0&0&-9/8&-11/8&27&z\\
\hline
0&0&0&1&3/4&1/4&6&u_1\\
0&0&1&0&-3/8&-1/8&3&x_2\\
0&1&0&0&1/4&-1/4&4&x_1\\
\hline
\end{array}}
$
\end{enumerate}
\subsection{R�lution du probl� original}
\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{6mm}1\\
\hline
1&0&0&0&-9/8&-11/8&27\\
\hline
0&0&0&1&3/4&1/4&6\\
0&0&1&0&-3/8&-1/8&3\\
0&1&0&0&1/4&-1/4&4\\
\hline
\end{array}}
$
&
\begin{tabular}{l}
Variables hors base : $u_2$, $u_3$\\
Solution de base : $(4,3,6,0,0)$\\
Valeur de l'objectif : $z=27$
\end{tabular}
\end{tabular}
\begin{center}
Variable entrante : $u_3$\hspace{1cm}
Variable sortante : $u_1$
\end{center}
\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{6mm}1\\
\hline
1&0&0&11/2&3&0&60\\
\hline
0&0&0&4&3&1&24\\
0&0&1&1/2&0&0&6\\
0&1&0&1&1&0&10\\
\hline
\end{array}}
$
&
\begin{tabular}{l}
Variables hors base : $u_1$, $u_2$\\
Solution de base : $(10,6,0,0,24)$\\
Valeur de l'objectif : $z=60$
\end{tabular}
\end{tabular}
\bigskip
\noindent
Variable entrante : aucune candidate\\
Solution optimale : $(x_1,x_2,u_1,u_2,u_3)=(10,6,0,0,24)$\\
Valeur de l'objectif �'optimum : $z=60$
%%%%%%%%%%%
\newpage
\section{Un probl� non r�isable}
\subsection{Probl� et repr�ntation graphique}
\begin{tabular}{cc}
$
{\renewcommand{\arraystretch}{1.2}
\begin{array}{l}
\mbox{min } z = 3 x_1 + x_2 \\
\mbox{s.c.q.} \left\{ \begin{array}{rcrcr}
x_1 & - & x_2 &\leq& -1\\
-x_1 &-& x_2 &\leq& -3\\
2x_1 &+& x_2 &\leq& 2\\
\multicolumn{3}{r}{x_1, x_2} &\geq& 0
\end{array} \right.
\end{array}}
$
&
%\framebox
{
% PARAMETRES
\psset{unit=1cm}
\psset{arrowinset=0}
\begin{pspicture}[0.5](-1,-1)(5,5)
% AXES
\psaxes[Dx=1,Dy=1,tickstyle=top]{->}(0,0)(0,0)(4,4)
\rput(4.5,0){$x_1$}\rput(0,4.5){$x_2$}
% CONTRAINTES
\psline(1,0)(0,2)\psline(3,0)(0,3)\psline(2,3)(0,1)
\psline{->}(0.6,0.7)(0.2,0.5)
\psline{->}(3.4,0.1)(3.4,0.5)
\psline{->}(0.1,3.5)(0.5,3.5)
\psline{->}(1.2,2.35)(1,2.6)
\psline{->}(1.6,1.65)(1.9,1.95)
\end{pspicture}
}
%\BoxedEPSF{./FUNDP_AD_SLIDES.eps/irrealis.eps scaled 600}
\end{tabular}
\subsection{Probl� original sous forme standard}
$$
{\renewcommand{\arraystretch}{1.2}
\begin{array}{l}
\mbox{min } z = 3 x_1 + x_2 \\
\mbox{s.c.q.} \left\{ \begin{array}{rcrrrrcr}
x_1 & - & x_2 & + u_1 & & &=& -1\\
-x_1 &-& x_2 & &+ u_2 & &=& -3\\
2x_1 &+& x_2 & & & + u_3 &=&2\\
\multicolumn{6}{r}{x_1, x_2, u_1, u_2, u_3} &\geq& 0
\end{array} \right.
\end{array}}
$$
\noindent
\begin{tabular}{ll}
$
{\renewcommand{\arraystretch}{1.0}
\renewcommand{\arraycolsep}{2pt}
\begin{array}{rrrrrr|r}
\hspace{6mm}z&\hspace{6mm}x_1&\hspace{6mm}x_2&\hspace{6mm}u_1&\hspace{6mm}u_2&\hspace{6mm}u_3&\hspace{6mm}1\\
\hline
1&-3&-1&0&0&0&0\\
\hline
0&1&-1&1&0&0&-1\\
0&-1&-1&0&1&0&-3\\
0&2&1&0&0&1&2\\
\hline
\end{array}}
$
&
\begin{tabular}{c}
Variables hors base :\\$x_1$, $x_2$\\
Solution de base :\\$(0,0,-1,-3,2)$
\end{tabular}
\end{tabular}
\bigskip
\noindent
La solution de base n'est pas r�isable.
\newpage
\subsection{Probl� de phase 1}
$$
{\renewcommand{\arraystretch}{1.3}
\begin{array}{l}
\min w = t_1+t_2\\
\mbox{s.c.q. }\left\{ \begin{array}{rrrrrrrrcr}
-x_1 & + & x_2 & - u_1 & & & + t_1 & &=& 1\\
x_1 &+& x_2 & &- u_2 & & & +t_2 &=& 3\\
2x_1 &+& x_2 & & & + u_3 & & & =&2\\
\multicolumn{8}{r}{x_1, x_2, u_1, u_2, u_3,t_1,t_2} &\geq& 0
\end{array} \right. \end{array}
}
$$
\vspace{-5mm}
\subsection{R�lution du probl� de phase 1}
$$
{\renewcommand{\arraystretch}{1.2}
\begin{array}{rrrrrrrr|r|c}
w&x_1&x_2&u_1&u_2&u_3&t_1&t_2&1&\\
\hline
1&0&2&-1&-1&0&0&0&4&w\\
\hline
0&-1&\fbox{1}&-1&0&0&1&0&1&t_1\\
0&1&1&0&-1&0&0&1&3&t_2\\
0&2&1&0&0&1&0&0&2&u_3\\
\hline
\end{array}}
$$
\begin{center}
{\bf Premi� it�tion~:} $x_2$ entre et $t_1$ sort.
\end{center}
$$
{\renewcommand{\arraystretch}{1.2}
\begin{array}{rrrrrrrr|r|c}
w&x_1&x_2&u_1&u_2&u_3&t_1&t_2&1&\\
\hline
1&2&0&1&-1&0&-2&0&2&w\\
\hline
0&-1&1&-1&0&0&1&0&1&x_2\\
0&2&0&1&-1&0&-1&1&2&t_2\\
0&3&0&\fbox{1}&0&1&-1&0&1&u_3\\
\hline
\end{array}}
$$
\begin{center}
{\bf Deuxi� it�tion~:} $u_1$ entre et $u_3$ sort.
\end{center}
$$
{\renewcommand{\arraystretch}{1.2}
\begin{array}{rrrrrrrr|r|c}
w&x_1&x_2&u_1&u_2&u_3&t_1&t_2&1&\\
\hline
1&-1&0&0&-1&-1&-1&0&1&w\\
\hline
0&2&1&0&0&1&0&0&2&x_2\\
0&-1&0&0&-1&-1&0&1&1&t_2\\
0&3&0&1&0&1&-1&0&1&u_1\\
\hline
\end{array}}
$$
\noindent
\begin{center}
Tableau optimal du probl� de phase 1 avec $w>0$.
\end{center}
\textbf{Conclusion} : Le probl� original n'est pas r�isable.
