Accueil
slides-analpost.tex
slides-analpost.tex
—
TeX document,
18Kb
Contenu du fichier
%%%%%%%%
\chapter{Analyse de sensibilit�t param�isation}
\newpage
\minitoc
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Le probl� lin�re}
\subsection{Formulation 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{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}
\subsection{S�ction de la base optimale}
${\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}
x_1\\ x_2\\ u_3
\end{bmatrix}
$\\
\\
$
x_N=\begin{bmatrix}
u_1\\u_2
\end{bmatrix}
$
\end{tabular}
\hspace{-5mm}
\begin{tabular}{c}
$
B=\begin{bmatrix}
1 & 1 & 0\\
-2 & 3 & 0\\
2 & -1 & 1
\end{bmatrix}
$
$
N=\begin{bmatrix}
1 & 0\\
0 & 1\\
0 & 0
\end{bmatrix}
$
\\
\\
$
c_B=\begin{bmatrix}
1 & 3 & 0
\end{bmatrix}
$
$
c_N=\begin{bmatrix}
0 & 0
\end{bmatrix}
$
\end{tabular}
\subsection{Dictionnaire optimale sous forme matricielle}
$${\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}
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$
\end{center}
et
\begin{center}
$
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{center}
\paragraph{Notations : } $\pi=c_BB^{-1}$, $\bar{b}=B^{-1}b$ et $\bar{c}_N=c_N-c_BB^{-1}N$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Sensibilit� un coefficient de $c$}
\subsection{Intuition g��ique}
\begin{tabular}[c]{c}
$
{\renewcommand{\arraystretch}{1.5}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z =
(1+\theta)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,6)(13,-6)\rput[l](14,-6){$\theta=1$}
\psline[linestyle=dashed](-6,4)(13,-2)\rput[l](14,-2){$\theta=0$}
%\psline[linestyle=dashed]{->}(-5,4)(-4.5,5.5)
\psline[linestyle=dashed](-6,2)(13,2)\rput[l](14,2){$\theta=-1$}
\psline[linestyle=dashed](-6,0)(13,6)\rput[l](14,6){$\theta=-2$}
\psline[linestyle=dashed](-6,-2)(13,10)\rput[l](14,10){$\theta=-3$}
\psline[linestyle=dashed](-6,-4)(13,14)\rput[l](14,14){$\theta=-4$}
\end{pspicture}
}
\subsection{Analyse matricielle}
Si $c_B=\begin{bmatrix}1+\theta & 3 & 0\end{bmatrix} $ la valeur de l'objectif devient
\begin{center}
$c_BB^{-1}b=30+ 6\theta$
\end{center}
et le vecteur des co��its
\begin{center}
$\overline{c}_N=c_N-c_BB^{-1}N=\begin{bmatrix}-\frac{3}{5}(\theta+3) & \frac{1}{5}(\theta-2)\end{bmatrix}$
\end{center}
Pour que la solution actuelle reste optimale, il faut que $\overline{c}_N$ reste n�tif, c'est-�ire que
$$\theta\in [\underline{\theta},\overline{\theta}]=[-3 , 2]$$
ou
$$ c_1\in[1+\underline{\theta},1+\overline{\theta}]=[-2 , 3].$$
\paragraph{Remarque :} On notera que $\underline{\theta}=-\infty$ et $\overline{\theta}=-\overline{c}_k$ lorsque $x_k$ est une variable hors base (d'un probl� de maximisation).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Programmation param�ique de $c_1$}
\subsection{Analyse graphique}
\begin{tabular}[c]{c}
$
{\renewcommand{\arraystretch}{1.2}\renewcommand{\arraycolsep}{1mm}
\begin{array}{ll}\max & z =
(1+\theta)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}}
$\\
\\
$
{\renewcommand{\arraystretch}{1.1}
\begin{array}{lcl}
\theta\in]-\infty,-3]&\Rightarrow&
\left\{\begin{array}{l}
(x_1,x_2)^*=(0,4)\\
z^*=12
\end{array}\right.\\
\theta\in[-3,2]&\Rightarrow&
\left\{\begin{array}{l}
(x_1,x_2)^*=(6,8)\\
z^*=30+6\theta
\end{array}\right.\\
\theta\in[2,+\infty[&\Rightarrow&
\left\{\begin{array}{l}(x_1,x_2)^*=(\frac{26}{3},\frac{16}{3})\\
z^*=\frac{74}{3}+\frac{26}{3}\theta
\end{array}\right.\\
\end{array}}
$
\end{tabular}
\hspace{-5mm} {
% PARAMETRES
\psset{unit=0.22cm}
%\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,8)(13,-10)\rput[l](14,-10){$\theta=2$}
\psline[linestyle=dashed](-6,4)(13,-2)\rput[l](14,-2){$\theta=0$}
\psline[linestyle=dashed]{->}(-5,4)(-4.5,5.5)
\psline[linestyle=dashed](-6,-2)(13,10)\rput[l](14,10){$\theta=-3$}
\end{pspicture}
}
\subsection{Analyse alg�ique}
\begin{tabular}{cc}
\begin{tabular}{c}Tableau\\optimal\\pour\\$\theta=0$\end{tabular}
&
$
\renewcommand{\arraystretch}{1.4}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|c|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}
$
\\
\\
\begin{tabular}{c}Tableau\\optimal\\pour\\$\theta\in[-3,2]$\end{tabular}
&
$
\renewcommand{\arraystretch}{1.4}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|c|r}
z&x_{1}&x_{2}&u_{1}&u_{2}&u_{3}&1\\
\hline
1&0&0&\frac{3}{5}(3+\theta)&\frac{1}{5}(2-\theta)&0&30+6\theta&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}
$
\end{tabular}
\noindent
\begin{tabular}{cc}
\begin{tabular}{c}Tableau\\optimal\\pour\\$\theta\in]-\infty,-3]$\end{tabular}
&
$
\renewcommand{\arraystretch}{1.4}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|c|r}
z&x_{1}&x_{2}&u_{1}&u_{2}&u_{3}&1\\
\hline
1&-(3+\theta)&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}
$
\\
\\
\begin{tabular}{c}Tableau\\optimal\\pour\\$\theta\in[2,+\infty[$\end{tabular}
&
$
\renewcommand{\arraystretch}{1.4}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|c|r}
z&x_{1}&x_{2}&u_{1}&u_{2}&u_{3}&1\\
\hline
1&0&0&\frac{1}{3}(7+\theta)&0&-\frac{1}{3}(2-\theta)&\frac{74}{3}+\frac{26}{3}\theta&z\\
\hline
0&1&0&\frac{1}{3}&0&\frac{1}{3}&\frac{26}{3}&x_{1}\\
0&0&1&\frac{2}{3}&0&-\frac{1}{3}&\frac{16}{3}&x_{2}\\
0&0&0&-\frac{4}{3}&1&\frac{5}{3}&\frac{40}{3}&u_{2}\\
\hline
\end{array}
$
\\
\end{tabular}
\subsection{Valeur de $z$ en fonction de $\theta$}
\begin{center}
% PARAMETRES
{ \psset{unit=0.10cm}
%\psset{arrowsize=3pt 3}
\psset{arrowinset=0} \fontsize{8}{1}\selectfont
\begin{pspicture}[0.5](-60,-5)(60,70)
% AXES
\psaxes[labels=none,ticks=none]{->}(0,0)(-60,0)(60,70)
\rput(58,-3){$\theta$}\rput(58,-7){$c_1$}\rput(-3,68){$z$}
% POINTS
\psdots*[dotstyle=*,dotscale=1.5](-30,12)(20,42)
\rput(-50,-3){$-5$}\rput(-30,-3){$-3$}\rput(0,-3){$0$}\rput(20,-3){$2$}\rput(40,-3){$4$}
\rput(-50,-7){$-4$}\rput(-30,-7){$-2$}\rput(0,-7){$1$}\rput(20,-7){$3$}\rput(40,-7){$5$}
\psline[linestyle=dashed](-50,0)(-50,12)\psline[linestyle=dashed](-30,0)(-30,12)
\psline[linestyle=dashed](20,0)(20,42)\psline[linestyle=dashed](40,0)(40,59.33)
\rput(3,12){$12$}\rput(-3,42){$42$}\rput(-3,59.33){$59\frac{1}{3}$}
\psline[linestyle=dashed](-30,12)(0,12)\psline[linestyle=dashed](0,42)(20,42)\psline[linestyle=dashed](0,59.33)(40,59.33)
% COURBE
\psline[linestyle=dotted](-60,12)(-55,12)\psline(-55,12)(-30,12)
\psline(-30,12)(20,42)
\psline(20,42)(45,63.66)\psline[linestyle=dotted](45,63.66)(50,68)
\end{pspicture}
}
\end{center}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Sensibilit� un coefficient de $b$}
\subsection{Intuition g��ique}
\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}{crcrcc}
& x_{1} &+& x_{2} &\le& 14\\
-& 2x_{1} &+& 3x_{2} &\le& 12+\theta\\
& 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,-11)(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(0,-12)(12,12)
\psline(-6,4)(12,16)\rput[l](13,16){$\theta=12$}
\psline(-6,2)(12,14)\rput[l](13,14){$\theta=6$}
\psline(-6,0)(12,12)\rput[l](13,12){$\theta=0$}
\psline(-6,-2)(12,10)\rput[l](13,10){$\theta=-6$}
\psline(-6,-4)(12,8)\rput[l](13,8){$\theta=-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{Analyse matricielle}
Si
$
b=\begin{bmatrix}
14\\ 12+\theta\\ 12
\end{bmatrix}
$
la solution devient
$
x_B=\begin{bmatrix}
x_1\\ x_2\\ u_3
\end{bmatrix}
=B^{-1}b=\begin{bmatrix}
6-\frac{1}{5}\theta\\ 8+\frac{1}{5}\theta\\ 8+\frac{3}{5}\theta
\end{bmatrix}
$\\
et l'objectif
$z=c_BB^{-1}b=30+\frac{2}{5}\theta$.
Pour que la solution de base actuelle reste r�isable (et optimale), il faut que $x_B$ reste positif, c'est-�ire que
$$\theta\in [\underline{\theta},\overline{\theta}]=[-\frac{40}{3} , 30 ]$$
ou
$$ b_2\in[12+\underline{\theta},12+\overline{\theta}]=[-\frac{4}{3} , 42].$$
\paragraph{Remarque :} Le prix cach�$\pi_k$ (valeur de la variable duale associ��a contrainte $k$) du vecteur des prix cach�$\pi=c_BB^{-1}=\begin{bmatrix}\frac{9}{5} & \frac{2}{5} & 0\end{bmatrix}$ donne l'augmentation de la valeur de l'objectif $z$ pour une augmentation d'une unit�u membre de droite $b_k$ (si la base reste optimale).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Programmation param�ique de $b_2$}
\subsection{Analyse 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}{crcrcc}
& x_{1} &+& x_{2} &\le& 14\\
-& 2x_{1} &+& 3x_{2} &\le& 12+\theta\\
& 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(0,-12)(12,12)
\psline(-6,10)(12,22)\rput[l](13,22){$\theta=30$}
\psline(-6,0)(12,12)\rput[l](13,12){$\theta=0$}
\psline(-6,-4.45)(12,7.55)\rput[l](13,7.55){$\theta=-\frac{40}{3}$}
\psline(-6,-8)(12,4)\rput[l](13,4){$\theta=-24$}
%\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{Analyse alg�ique}
\begin{tabular}{cc}
\begin{tabular}{c}Tableau\\optimal\\pour\\$\theta=0$\end{tabular}
&
$
\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}
$
\\
\\
\begin{tabular}{c}Tableau\\optimal\\pour\\$\theta\in[-\frac{40}{3},30]$\end{tabular}
&
$
\renewcommand{\arraystretch}{1.4}\renewcommand{\arraycolsep}{3mm}
\begin{array}{rrrrrr|c|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+\frac{2}{5}\theta&z\\
\hline
0&1&0&\frac{3}{5}&-\frac{1}{5}&0&6-\frac{1}{5}\theta&x_{1}\\
0&0&1&\frac{2}{5}&\frac{1}{5}&0&8+\frac{1}{5}\theta&x_{2}\\
0&0&0&-\frac{4}{5}&\frac{3}{5}&1&8+\frac{3}{5}\theta&u_{3}\\
\hline
\end{array}
$
\end{tabular}
\noindent
\begin{tabular}{cc}
\begin{tabular}{c}Tableau\\optimal\\pour\\$\theta\in[30,+\infty]$\end{tabular}
&
$
\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&2&0&3&0&0&42&z\\
\hline
0&-5&0&-3&1&0&-30+\theta&u_{2}\\
0&0&1&1&0&0&14&x_{2}\\
0&3&0&1&0&1&26&u_{3}\\
\hline
\end{array}
$
\\
\\
\begin{tabular}{c}Tableau\\optimal\\pour\\$\theta\in[-24,-\frac{40}{3}]$\end{tabular}
&
$
\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&0&\frac{7}{4}&\frac{9}{4}&48+\frac{7}{4}\theta&z\\
\hline
0&1&0&0&\frac{1}{4}&\frac{3}{4}&12+\frac{1}{4}\theta&x_{1}\\
0&0&1&0&\frac{1}{2}&\frac{1}{2}&12+\frac{1}{2}\theta&x_{2}\\
0&0&0&1&-\frac{3}{4}&-\frac{5}{4}&-10-\frac{3}{4}\theta&u_{1}\\
\hline
\end{array}
$
\\
\\
\begin{tabular}{c}Pour\\$\theta\in]-\infty,-24[$\end{tabular}
&
\begin{tabular}{l}Le probl� est non r�isable.\\(Le tableau pr�dent montre que le dual est non born�\end{tabular}
\end{tabular}
\subsection{Valeur de $z$ en fonction de $\theta$}
\begin{center}
% PARAMETRES
{ \psset{unit=0.12cm}
%\psset{arrowsize=3pt 3}
\psset{arrowinset=0} \fontsize{7}{1}\selectfont
\begin{pspicture}[0.5](-30,-2)(48,50)
% AXES
\psaxes[labels=none,ticks=none]{->}(-28,0)(-28,0)(43,45)
\rput(46,-2){$\theta$}\rput(46,-5){$b_2$}\rput(-30,48){$z$}
% POINTS
\psdots*[dotstyle=*,dotscale=1.5](-24,6)(-13.33,24.66)(30,42)
\rput(-24,-2){$-24$}\rput(-13.33,-2){$-\frac{40}{3}$}\rput(0,-2){$0$}\rput(30,-2){$30$}
\rput(-24,-5){$-12$}\rput(-13.33,-5){$-\frac{4}{3}$}\rput(0,-5){$12$}\rput(30,-5){$42$}
\psline[linestyle=dashed](-24,0)(-24,6)\psline[linestyle=dashed](-13.33,0)(-13.33,24.66)
\psline[linestyle=dashed](0,0)(0,30)\psline[linestyle=dashed](30,0)(30,42)
\rput(-30,6){$6$}\rput(-30,24.66){$\frac{74}{3}$}\rput(-30,30){$30$}\rput(-30,42){$42$}
\psline[linestyle=dashed](-28,6)(-24,6)\psline[linestyle=dashed](-28,24.66)(-13.33,24.66)
\psline[linestyle=dashed](-28,30)(0,30)\psline[linestyle=dashed](-28,42)(30,42)
% COURBE
\psline(-24,6)(-13.33,24.66) \psline(-13.33,24.66)(30,42)
\psline(30,42)(40,42)\psline[linestyle=dotted](40,42)(45,42)
\end{pspicture}
}
\end{center}
\newpage
