Correction du Partiel de R.O de 2007-2008

<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>

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>

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>