Accueil
slides-bb.tex
slides-bb.tex
—
TeX document,
16Kb
Contenu du fichier
%%%%%%%%
\chapter{Branch and bound\\Un exemple}
\newpage
\minitoc
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Le probl� en nombres entiers}
\begin{tabular}{cc}
\begin{minipage}{6.5cm}
$$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z =
4x_{1} - x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcr}
& 7x_{1} &-& 2x_{2} &\le& 14\\
& & & x_{2} &\le& 3\\
& 2x_{1} &-& 2x_{2} &\le& 3\\
\multicolumn{6}{r}{x_1 , x_2 \ge 0 \mbox{ et entiers}}
\end{array} \right.
\end{array}}
$$
$$(x_1,x_2)^* = (2,1)$$
$$z^* = 7$$
\end{minipage}
&
{
% PARAMETRES
\psset{unit=1.2cm}
\psset{arrowinset=0}
%\psset{arrowsize=4pt 3}
%\fontsize{7}{1}\selectfont
\begin{pspicture}[0.5](-0.25,-0.25)(4,4)
% AXES
\psaxes[tickstyle=top,labels=none]{->}(0,0)(-0.25,-0.25)(3.5,3.5)
\rput(4,0){$x_1$}\rput(0,4){$x_2$}
% CONTRAINTES
\psline(-0.25,3)(3.25,3) \psline(1.25,-0.25)(3,1.5) \psline(2,0)(3,3.5)
%\pspolygon[linewidth=0pt,fillstyle=solid,fillcolor=lightgray](0,0)(0,3)(2.86,3)(2.2,0.7)(1.5,0)
% OBJECTIF
\psline[linestyle=dashed](0.31,-0.24)(1.06,3.24)
\psline{->}(1,2.5)(1.24,2.44)
% SR
\psset{dotstyle=*}\psset{dotscale=1.3}
\psdots(0,0)\psdots(1,0)
\psdots(0,1)\psdots(1,1)\psdots(2,1)
\psdots(0,2)\psdots(1,2)\psdots(2,2)
\psdots(0,3)\psdots(1,3)\psdots(2,3)
\psset{dotstyle=o}\psset{dotscale=1.3}
\psdots(2,0)
\psdots(3,0)\psdots(3,1)\psdots(3,2)\psdots(3,3)
\end{pspicture}
}
\end{tabular}
\section{Le probl� relax�S$}
\subsection{R�lution graphique}
\begin{tabular}{cc}
\begin{minipage}{6.5cm}
$$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z =
4x_{1} - x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcr}
& 7x_{1} &-& 2x_{2} &\le& 14\\
& & & x_{2} &\le& 3\\
& 2x_{1} &-& 2x_{2} &\le& 3\\
\multicolumn{4}{r}{x_1 , x_2} &\ge& 0
\end{array} \right.
\end{array}}
$$
$$(x_1,x_2)^* = (\frac{20}{7},3)$$
$$z^* = \frac{59}{7}$$
\end{minipage}
&
{
% PARAMETRES
\psset{unit=1.2cm}
\psset{arrowinset=0}
%\psset{arrowsize=4pt 3}
%\fontsize{7}{1}\selectfont
\begin{pspicture}[0.5](-0.25,-0.25)(4,4)
% AXES
\psaxes[tickstyle=top,labels=none]{->}(0,0)(-0.25,-0.25)(3.5,3.5)
\rput(4,0){$x_1$}\rput(0,4){$x_2$}
% CONTRAINTES
\psline(-0.25,3)(3.25,3) \psline(1.25,-0.25)(3,1.5) \psline(2,0)(3,3.5)
\pspolygon[linewidth=0pt,fillstyle=solid,fillcolor=lightgray](0,0)(0,3)(2.86,3)(2.2,0.7)(1.5,0)
% OBJECTIF
\psline[linestyle=dashed](0.31,-0.24)(1.06,3.24)
\psline{->}(1,2.5)(1.24,2.44)
% SR
\psset{dotstyle=*}\psset{dotscale=1.3}
\psdots(0,0)\psdots(1,0)
\psdots(0,1)\psdots(1,1)\psdots(2,1)
\psdots(0,2)\psdots(1,2)\psdots(2,2)
\psdots(0,3)\psdots(1,3)\psdots(2,3)
\psset{dotstyle=o}\psset{dotscale=1.3}
\psdots(2,0)
\psdots(3,0)\psdots(3,1)\psdots(3,2)\psdots(3,3)
\end{pspicture}
}
\end{tabular}
\subsection{R�lution par l'algorithme du simplexe}
\paragraph{Probl� :}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z =
4x_{1} - x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcrcr}
& 7x_{1} &-& 2x_{2} &+& u_{1} & & & & & = & 14\\
& & & x_{2} & & &+& u_{2} & & & = & 3\\
& 2x_{1} &-& 2x_{2} & & & & &+& u_{3} & = & 3\\
\multicolumn{10}{r}{x_{1}, x_{2}, u_{1}, u_{2}, u_{3}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\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&-4&1&0&0&0&0&z\\
\hline
0&7&-2&1&0&0&14&u_{1}\\
0&0&1&0&1&0&3&u_{2}\\
0&2&-2&0&0&1&3&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&-3&0&0&2&6&z\\
\hline
0&0&5&1&0&-\frac{7}{2}&\frac{7}{2}&u_{1}\\
0&0&1&0&1&0&3&u_{2}\\
0&1&-1&0&0&\frac{1}{2}&\frac{3}{2}&x_{1}\\
\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&\frac{3}{5}&0&-\frac{1}{10}&\frac{81}{10}&z\\
\hline
0&0&1&\frac{1}{5}&0&-\frac{7}{10}&\frac{7}{10}&x_{2}\\
0&0&0&-\frac{1}{5}&1&\frac{7}{10}&\frac{23}{10}&u_{2}\\
0&1&0&\frac{1}{5}&0&-\frac{1}{5}&\frac{11}{5}&x_{1}\\
\hline
\end{array}
$\par
\paragraph{Tableau 4 : }
$
\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{4}{7}&\frac{1}{7}&0&\frac{59}{7}&z\\
\hline
0&0&1&0&1&0&3&x_{2}\\
0&0&0&-\frac{2}{7}&\frac{10}{7}&1&\frac{23}{7}&u_{3}\\
0&1&0&\frac{1}{7}&\frac{2}{7}&0&\frac{20}{7}&x_{1}\\
\hline
\end{array}
$\par
\paragraph{Conclusion : }L'unique solution optimale est trouv�\par
\section{Sous-probl� $S_1$}
\subsection{R�lution graphique}
\begin{tabular}{cc}
\begin{minipage}{6.5cm}
$$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{0.5mm}
\begin{array}{ll}\max & z =
4x_{1} - x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcr}
& 7x_{1} &-& 2x_{2} &\le& 14\\
& & & x_{2} &\le& 3\\
& 2x_{1} &-& 2x_{2} &\le& 3\\
& x_{1} & & &\le& 2\\
\multicolumn{4}{r}{x_1 , x_2} &\ge& 0
\end{array} \right.
\end{array}}
$$
$$(x_1,x_2)^* = (2,1/2)$$
$$z^* = 15/2$$
\end{minipage}
&
{
% PARAMETRES
\psset{unit=1.2cm}
\psset{arrowinset=0}
%\psset{arrowsize=4pt 3}
%\fontsize{7}{1}\selectfont
\begin{pspicture}[0.5](-0.25,-0.25)(4,4)
% AXES
\psaxes[tickstyle=top,labels=none]{->}(0,0)(-0.25,-0.25)(3.5,3.5)
\rput(4,0){$x_1$}\rput(0,4){$x_2$}
% CONTRAINTES
\psline(-0.25,3)(3.25,3) \psline(1.25,-0.25)(3,1.5) \psline(2,0)(3,3.5)
\pspolygon[linewidth=0pt,fillstyle=solid,fillcolor=lightgray](0,0)(0,3)(2,3)(2,0.5)(1.5,0)
% OBJECTIF
\psline[linestyle=dashed](0.31,-0.24)(1.06,3.24)
\psline{->}(1,2.5)(1.24,2.44)
% SR
\psset{dotstyle=*}\psset{dotscale=1.3}
\psdots(0,0)\psdots(1,0)
\psdots(0,1)\psdots(1,1)\psdots(2,1)
\psdots(0,2)\psdots(1,2)\psdots(2,2)
\psdots(0,3)\psdots(1,3)\psdots(2,3)
\psset{dotstyle=o}\psset{dotscale=1.3}
\psdots(2,0)
\psdots(3,0)\psdots(3,1)\psdots(3,2)\psdots(3,3)
\end{pspicture}
}
\end{tabular}
\subsection{R�lution par l'algorithme dual du simplexe}
\paragraph{Probl� : }
$
{\renewcommand{\arraystretch}{1.2}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z =
\frac{59}{7} - \frac{4}{7}u_{1} - \frac{1}{7}u_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcrcrcr}
& & & x_{2} & & &+& u_{2} & & & & & = & 3\\
& & & &-& \frac{2}{7}u_{1} &+& \frac{10}{7}u_{2} &+& u_{3} & & & = & \frac{23}{7}\\
& x_{1} & & &+& \frac{1}{7}u_{1} &+& \frac{2}{7}u_{2} & & & & & = & \frac{20}{7}\\
& x_{1} & & & & & & & & &+& 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
\paragraph{Tableau 1 : }
$
\renewcommand{\arraystretch}{1.2}\renewcommand{\arraycolsep}{2mm}
\begin{array}{rrrrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & u_{3} & u_{4} & 1\\
\hline
1&0&0&\frac{4}{7}&\frac{1}{7}&0&0&\frac{59}{7}&z\\
\hline
0&0&1&0&1&0&0&3&x_{2}\\
0&0&0&-\frac{2}{7}&\frac{10}{7}&1&0&\frac{23}{7}&u_{3}\\
0&1&0&\frac{1}{7}&\frac{2}{7}&0&0&\frac{20}{7}&x_{1}\\
0&0&0&-\frac{1}{7}&-\frac{2}{7}&0&1&-\frac{6}{7}&u_{4}\\
\hline
\end{array}
$\par
\paragraph{Tableau 2 : }
$
\renewcommand{\arraystretch}{1.2}\renewcommand{\arraycolsep}{2mm}
\begin{array}{rrrrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & u_{3} & u_{4} & 1\\
\hline
1&0&0&\frac{1}{2}&0&0&\frac{1}{2}&8&z\\
\hline
0&0&1&-\frac{1}{2}&0&0&\frac{7}{2}&0&x_{2}\\
0&0&0&-1&0&1&5&-1&u_{3}\\
0&1&0&0&0&0&1&2&x_{1}\\
0&0&0&\frac{1}{2}&1&0&-\frac{7}{2}&3&u_{2}\\
\hline
\end{array}
$\par
\paragraph{Tableau 3 : }
$
\renewcommand{\arraystretch}{1.2}\renewcommand{\arraycolsep}{2mm}
\begin{array}{rrrrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & u_{3} & u_{4} & 1\\
\hline
1&0&0&0&0&\frac{1}{2}&3&\frac{15}{2}&z\\
\hline
0&0&1&0&0&-\frac{1}{2}&1&\frac{1}{2}&x_{2}\\
0&0&0&1&0&-1&-5&1&u_{1}\\
0&1&0&0&0&0&1&2&x_{1}\\
0&0&0&0&1&\frac{1}{2}&-1&\frac{5}{2}&u_{2}\\
\hline
\end{array}
$\par
\paragraph{Conclusion : }L'unique solution optimale est trouv�\par
\section{Sous-probl� $S_{12}$}
\subsection{R�lution graphique}
\begin{tabular}{cc}
\begin{minipage}{6.5cm}
$$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{0.5mm}
\begin{array}{ll}\max & z =
4x_{1} - x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcr}
& 7x_{1} &-& 2x_{2} &\le& 14\\
& & & x_{2} &\le& 3\\
& 2x_{1} &-& 2x_{2} &\le& 3\\
& x_{1} & & &\le& 2\\
& & & x_{2} &\ge& 1\\
\multicolumn{4}{r}{x_1 , x_2} &\ge& 0
\end{array} \right.
\end{array}}
$$
$$(x_1,x_2)^* = (2,1)$$
$$z^* = 7$$
\end{minipage}
&
{
% PARAMETRES
\psset{unit=1.2cm}
\psset{arrowinset=0}
%\psset{arrowsize=4pt 3}
%\fontsize{7}{1}\selectfont
\begin{pspicture}[0.5](-0.25,-0.25)(4,4)
% AXES
\psaxes[tickstyle=top,labels=none]{->}(0,0)(-0.25,-0.25)(3.5,3.5)
\rput(4,0){$x_1$}\rput(0,4){$x_2$}
% CONTRAINTES
\psline(-0.25,3)(3.25,3) \psline(1.25,-0.25)(3,1.5) \psline(2,0)(3,3.5)
\pspolygon[linewidth=0pt,fillstyle=solid,fillcolor=lightgray](0,1)(0,3)(2,3)(2,1)
% OBJECTIF
\psline[linestyle=dashed](0.31,-0.24)(1.06,3.24)
\psline{->}(1,2.5)(1.24,2.44)
% SR
\psset{dotstyle=*}\psset{dotscale=1.3}
\psdots(0,0)\psdots(1,0)
\psdots(0,1)\psdots(1,1)\psdots(2,1)
\psdots(0,2)\psdots(1,2)\psdots(2,2)
\psdots(0,3)\psdots(1,3)\psdots(2,3)
\psset{dotstyle=o}\psset{dotscale=1.3}
\psdots(2,0)
\psdots(3,0)\psdots(3,1)\psdots(3,2)\psdots(3,3)
\end{pspicture}
}
\end{tabular}
\subsection{R�lution par l'algorithme dual du simplexe}
\paragraph{Probl� :}
$$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z =
\frac{15}{2} - \frac{1}{2}u_{3} - 3u_{4}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcrcrcrcr}
& & & x_{2} & & & & &-& \frac{1}{2}u_{3} &+& u_{4} & & & = & \frac{1}{2}\\
& & & & & u_{1} & & &-& u_{3} &-& 5u_{4} & & & = & 1\\
& x_{1} & & & & & & & & &+& u_{4} & & & = & 2\\
& & & & & & & u_{2} &+& \frac{1}{2}u_{3} &-& u_{4} & & & = & \frac{5}{2}\\
& &-& x_{2} & & & & & & & & &+& u_{5} & = & -1\\
\multicolumn{14}{r}{x_{1}, x_{2}, u_{1}, u_{2}, u_{3}, u_{4}, u_{5}} & \ge & 0
\end{array} \right.
\end{array}}
$$
\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&0&\frac{1}{2}&3&0&\frac{15}{2}&z\\
\hline
0&0&1&0&0&-\frac{1}{2}&1&0&\frac{1}{2}&x_{2}\\
0&0&0&1&0&-1&-5&0&1&u_{1}\\
0&1&0&0&0&0&1&0&2&x_{1}\\
0&0&0&0&1&\frac{1}{2}&-1&0&\frac{5}{2}&u_{2}\\
0&0&0&0&0&-\frac{1}{2}&1&1&-\frac{1}{2}&u_{5}\\
\hline
\end{array}
$$
\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&4&1&7&z\\
\hline
0&0&1&0&0&0&0&-1&1&x_{2}\\
0&0&0&1&0&0&-7&-2&2&u_{1}\\
0&1&0&0&0&0&1&0&2&x_{1}\\
0&0&0&0&1&0&0&1&2&u_{2}\\
0&0&0&0&0&1&-2&-2&1&u_{3}\\
\hline
\end{array}
$$
\paragraph{Conclusion : }L'unique solution optimale est trouv�\par
\section{Sous-probl� $S_{11}$}
\subsection{R�lution graphique}
\begin{tabular}{cc}
\begin{minipage}{6.5cm}
$$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{0.5mm}
\begin{array}{ll}\max & z =
4x_{1} - x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcr}
& 7x_{1} &-& 2x_{2} &\le& 14\\
& & & x_{2} &\le& 3\\
& 2x_{1} &-& 2x_{2} &\le& 3\\
& x_{1} & & &\le& 2\\
& & & x_{2} &\le& 0\\
\multicolumn{4}{r}{x_1 , x_2} &\ge& 0
\end{array} \right.
\end{array}}
$$
$$(x_1,x_2)^* = (3/2,0)$$
$$z^* = 6$$
\end{minipage}
&
{
% PARAMETRES
\psset{unit=1.2cm}
\psset{arrowinset=0}
%\psset{arrowsize=4pt 3}
%\fontsize{7}{1}\selectfont
\begin{pspicture}[0.5](-0.25,-0.25)(4,4)
% AXES
\psaxes[tickstyle=top,labels=none]{->}(0,0)(-0.25,-0.25)(3.5,3.5)
\rput(4,0){$x_1$}\rput(0,4){$x_2$}
% CONTRAINTES
\psline(-0.25,3)(3.25,3) \psline(1.25,-0.25)(3,1.5) \psline(2,0)(3,3.5)
\pspolygon[linewidth=3pt,linecolor=gray,fillstyle=solid,fillcolor=lightgray](0,0)(1.5,0)
% OBJECTIF
\psline[linestyle=dashed](0.31,-0.24)(1.06,3.24)
\psline{->}(1,2.5)(1.24,2.44)
% SR
\psset{dotstyle=*}\psset{dotscale=1.3}
\psdots(0,0)\psdots(1,0)
\psdots(0,1)\psdots(1,1)\psdots(2,1)
\psdots(0,2)\psdots(1,2)\psdots(2,2)
\psdots(0,3)\psdots(1,3)\psdots(2,3)
\psset{dotstyle=o}\psset{dotscale=1.3}
\psdots(2,0)
\psdots(3,0)\psdots(3,1)\psdots(3,2)\psdots(3,3)
\end{pspicture}
}
\end{tabular}
\subsection{R�lution par l'algorithme dual du simplexe}
\paragraph{Probl� :}
$$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z =
\frac{15}{2} - \frac{1}{2}u_{3} - 3u_{4}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcrcrcrcr}
& & & x_{2} & & & & &-& \frac{1}{2}u_{3} &+& u_{4} & & & = & \frac{1}{2}\\
& & & & & u_{1} & & &-& u_{3} &-& 5u_{4} & & & = & 1\\
& x_{1} & & & & & & & & &+& u_{4} & & & = & 2\\
& & & & & & & u_{2} &+& \frac{1}{2}u_{3} &-& u_{4} & & & = & \frac{5}{2}\\
& & & x_{2} & & & & & & & & &+& u_{5} & = & 0\\
\multicolumn{14}{r}{x_{1}, x_{2}, u_{1}, u_{2}, u_{3}, u_{4}, u_{5}} & \ge & 0
\end{array} \right.
\end{array}}
$$
\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&0&\frac{1}{2}&3&0&\frac{15}{2}&z\\
\hline
0&0&1&0&0&-\frac{1}{2}&1&0&\frac{1}{2}&x_{2}\\
0&0&0&1&0&-1&-5&0&1&u_{1}\\
0&1&0&0&0&0&1&0&2&x_{1}\\
0&0&0&0&1&\frac{1}{2}&-1&0&\frac{5}{2}&u_{2}\\
0&0&0&0&0&\frac{1}{2}&-1&1&-\frac{1}{2}&u_{5}\\
\hline
\end{array}
$$
\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&2&0&3&6&z\\
\hline
0&0&1&0&0&0&0&1&0&x_{2}\\
0&0&0&1&0&-\frac{7}{2}&0&-5&\frac{7}{2}&u_{1}\\
0&1&0&0&0&\frac{1}{2}&0&1&\frac{3}{2}&x_{1}\\
0&0&0&0&1&0&0&-1&3&u_{2}\\
0&0&0&0&0&-\frac{1}{2}&1&-1&\frac{1}{2}&u_{4}\\
\hline
\end{array}
$$
\paragraph{Conclusion : }L'unique solution optimale est trouv�\par
\section{Sous-probl� $S_2$}
\subsection{R�lution graphique}
\begin{tabular}{cc}
\begin{minipage}{6.5cm}
$$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{0.5mm}
\begin{array}{ll}\max & z =
4x_{1} - x_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcr}
& 7x_{1} &-& 2x_{2} &\le& 14\\
& & & x_{2} &\le& 3\\
& 2x_{1} &-& 2x_{2} &\le& 3\\
& x_{1} & & &\ge& 3\\
\multicolumn{4}{r}{x_1 , x_2} &\ge& 0
\end{array} \right.
\end{array}}
$$
\begin{center}
Le probl� est irr�isable.
\end{center}
\end{minipage}
&
{
% PARAMETRES
\psset{unit=1.2cm}
\psset{arrowinset=0}
%\psset{arrowsize=4pt 3}
%\fontsize{7}{1}\selectfont
\begin{pspicture}[0.5](-0.25,-0.25)(4,4)
% AXES
\psaxes[tickstyle=top,labels=none]{->}(0,0)(-0.25,-0.25)(3.5,3.5)
\rput(4,0){$x_1$}\rput(0,4){$x_2$}
% CONTRAINTES
\psline(-0.25,3)(3.25,3)\psline(1.25,-0.25)(3,1.5)
\psline(2,0)(3,3.5)\psline(3,-0.25)(3,3.25)
\psline{->}(0.1,1.5)(0.4,1.5)\psline{->}(1.5,2.9)(1.5,2.6)
\psline{->}(2.5,2)(2.25,2.1)\psline{->}(1.8,0.4)(1.6,0.6)
\psline{->}(0.7,0.1)(0.7,0.4)\psline{->}(3.1,1.5)(3.4,1.5)
% SR
\psset{dotstyle=*}\psset{dotscale=1.3}
\psdots(0,0)\psdots(1,0)
\psdots(0,1)\psdots(1,1)\psdots(2,1)
\psdots(0,2)\psdots(1,2)\psdots(2,2)
\psdots(0,3)\psdots(1,3)\psdots(2,3)
\psset{dotstyle=o}\psset{dotscale=1.3}
\psdots(2,0)
\psdots(3,0)\psdots(3,1)\psdots(3,2)\psdots(3,3)
\end{pspicture}
}
\end{tabular}
\subsection{R�lution par l'algorithme dual du simplexe}
\paragraph{Probl� :}
$
{\renewcommand{\arraystretch}{1.1}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z =
\frac{59}{7} - \frac{4}{7}u_{1} - \frac{1}{7}u_{2}\\
\mbox{s.c.q.} & \left\{ \begin{array}{crcrcrcrcrcrcr}
& & & x_{2} & & &+& u_{2} & & & & & = & 3\\
& & & &-& \frac{2}{7}u_{1} &+& \frac{10}{7}u_{2} &+& u_{3} & & & = & \frac{23}{7}\\
& x_{1} & & &+& \frac{1}{7}u_{1} &+& \frac{2}{7}u_{2} & & & & & = & \frac{20}{7}\\
-& x_{1} & & & & & & & & &+& u_{4} & = & -3\\
\multicolumn{12}{r}{x_{1}, x_{2}, u_{1}, u_{2}, u_{3}, u_{4}} & \ge & 0
\end{array} \right.
\end{array}}
$\par
\paragraph{Tableau 1 : }
$
\renewcommand{\arraystretch}{1.1}\renewcommand{\arraycolsep}{2mm}
\begin{array}{rrrrrrr|r|r}
z & x_{1} & x_{2} & u_{1} & u_{2} & u_{3} & u_{4} & 1\\
\hline
1&0&0&\frac{4}{7}&\frac{1}{7}&0&0&\frac{59}{7}&z\\
\hline
0&0&1&0&1&0&0&3&x_{2}\\
0&0&0&-\frac{2}{7}&\frac{10}{7}&1&0&\frac{23}{7}&u_{3}\\
0&1&0&\frac{1}{7}&\frac{2}{7}&0&0&\frac{20}{7}&x_{1}\\
0&0&0&\frac{1}{7}&\frac{2}{7}&0&1&-\frac{1}{7}&u_{4}\\
\hline
\end{array}
$\par
\paragraph{Conclusion : }Le probl� est irr�isable.\par
\section{Arbre de r�lution}
\begin{center}
\psset{levelsep=3cm,nodesep=0mm,tpos=0.5}
\pstree{\svBBNode{S}{1}{59/7}{-\infty}{ }}{
\pstree{\svBBNode{S_1}{2}{15/2}{-\infty}{ }\tlput{$x_1\le2$}}{
\svBBNode{S_{11}}{4}{6}{-\infty}{\times}\tlput{$x_2\le0$}
\svBBNode{S_{12}}{3}{7}{7}{\times}\trput{$x_2\ge1$} }
\svBBNode{S_2}{5}{-\infty}{-\infty}{\times}\trput{$x_1\ge3$} }
\end{center}
