====== Correction du Partiel de R.O de 2007-2008 ======
===== Exercice 1 =====
\[ (P)
\left\{
\begin{aligned}
\mbox{Minimiser} -x_2 \\
\mbox{Sous les contraintes} :\\
3x_1 + 2x_2 \le 6 \\
-3x_1 + 2x_2 \le 0 \\
x_1,x_2 \in \mathbb{N}
\end{aligned}
\right.
\]
==== Question 1) =====
Pour $x_1,x_2$ vérifiant $(P)$ on a :\\
$6 - 3x_1 + 2x_1 \ge 0$. Donc si on pose : $x_3 &= 6 - 3x_1 + 2x_1$, nous avons :\\
$x_3 \ge 0$ et $3x_1 + 2x_2 + x_3 &= 6$\\ \\
De même :\\
$-3x_1 + 2x_2 \le 0$
Si on pose $x_4 &= 3x_1 - 2x_2$ on a :\\
$x_4 \ge 0$ et $-3x_1 + 2x_2 + x_4 &= 0$\\ \\
Ainsi nous avons $(P_c)$ défini par :\\ \\
\[ (P_c)
\left\{
\begin{aligned}
\mbox{Minimiser} -x_2 \\
\mbox{Sous les contraintes} :\\
3x_1 + 2x_2 + x_3 &= 6 \\
-3x_1 + 2x_2 +x_4 &= 0 \\
x_1,x_2,x_3,x_4 \in \mathbb{N}
\end{aligned}
\right.
\]
==== Question 1) =====
On a :
\[ (P_c)
\left\{
\begin{aligned}
\mbox{Minimiser c}X \\
\mbox{Sous les contraintes} :\\
AX &= b \\
X \ge 0
\end{aligned}
\right.
\]
\\
Avec :
\\ \\
\[ A &=
\left(
\begin{array}{ c c c c }
3 & 2 & 1 & 0\\
-3 & 2 & 0 & 1
\end{array}
\right)
\]
\\
\[ b &=
\left(
\begin{array}{ c }
6\\
0
\end{array}
\right)
\]
\\
\[ c &=
\left(
\begin{array}{ c c c c}
0 & -1 & 0 & 0
\end{array}
\right)
\]
\\ \\
On a choisis la base constitué par les 2 premiers vecteurs colonnes de $A$ c'est à dire :\\ \\
\left(\begin{array}{ c }
3\\
-3
\end{array}\right)
,\left(\begin{array}{ c }
2\\
2
\end{array}\right)
\\ \\
Ce qui donne :\\ \\
B &=
\left(
\begin{array}{ c c}
3 & 2\\
-3 & 2
\end{array}
\right)
\\ \\
On inverse la matrice $B$\\ \\
B^{-1}=\frac{1}{det(B)}