====== Correction du Partiel de R.O de 2007-2008 ======

===== Exercice 1 =====

<latex>
\[ (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.
\]
</latex>

==== 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 :\\ \\

<latex>
\[ (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.
\]
</latex>

==== Question 1) =====

On a : 

<latex>
\[ (P_c) 
\left\{ 
\begin{aligned}
\mbox{Minimiser c}X \\
\mbox{Sous les contraintes}  :\\
AX &= b \\
X \ge 0
\end{aligned} 
\right.
\]
</latex>
\\
Avec : 
\\ \\
<latex>
\[ 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)
\]
</latex>
\\ \\
On a choisis la base constitué par les 2 premiers vecteurs colonnes de $A$ c'est à dire :\\ \\
<latex>
\left(\begin{array}{ c }
    3\\
    -3
  \end{array}\right)
,\left(\begin{array}{ c }
     2\\
     2
  \end{array}\right)
</latex>
\\ \\
Ce qui donne :\\ \\
<latex>B &= 
\left(
  \begin{array}{ c c}
     3 & 2\\
     -3 & 2
  \end{array} 
\right)
</latex>\\ \\
On inverse la matrice $B$\\ \\
<latex>B^{-1}=\frac{1}{det(B)}</latex>