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 - 3 x_1 + 2 x_1 g e 0$ . Donc si on pose : $x\_3 &= 6 - 3x\_1 + 2x\_1$ , nous avons :

$x_3 g e 0$ et $3x\_1 + 2x\_2 + x\_3 &= 6$

De même :

$- 3 x_1 + 2 x_2 l e 0$ Si on pose $x\_4 &= 3x\_1 - 2x\_2$ on a :

$x_4 g e 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$