مسابقة دكتوراه 2025 — Université Abderrahmane Mira - Béjaïa — الموضوع 02

Considérons le problème linéaire suivant :

$$(1)\quad\begin{cases} \min Z = 3x_1 + 2x_2 \\ 5x_1 + 2x_2 \geq 5 \\ -2x_1 + 4x_2 \geq 2 \\ 4x_1 + 3x_2 \geq 5 \\ x_1, x_2 \geq 0. \end{cases}$$

1. Quelles sont les solutions qui sont réalisables basiques pour le problème (1), parmi les solutions suivantes ? Justifier votre réponse.

$$x = \left(\tfrac{1}{2}, \tfrac{5}{4}\right), \quad x = \left(\tfrac{1}{5}, 2\right), \quad x = \left(2, \tfrac{3}{2}\right), \quad x = \left(0, \tfrac{5}{2}\right).$$

2. Résoudre le problème (1) par la méthode duale du simplexe en identifiant la matrice basique inverse à chaque itération.
3. Ecrire le problème dual du problème (1). Justifier qu'il possède ou non une solution optimale.
4. Déduire la solution optimale du problème dual si elle existe.

On considère le problème $(P)$ de programmation quadratique suivant :

$$\min F(x) = F(x_1, x_2, x_3) = x_1^2 + x_2^2 + x_3^2 - 2x_1 x_2 + 2x_1 - 2x_2 + 2x_3$$ $$\begin{cases} x_1 + 2x_2 \leq 4, \\ 2x_1 + x_2 \leq 2, \\ x_1 \geq 0,\ x_2 \geq 0,\ x_3 \geq 0. \end{cases}$$

1. Trouver l'ensemble des vecteurs $x^0$ qui réalisent le minimum global de $F(x)$ sur $\mathbb{R}^3$. Justifier votre réponse.
2. Ecrire le problème $(P)$ sous forme standard et déduire son système d'optimalité de Karush-Kuhn-Tucker (KKT).
3. Montrer que le vecteur nul $v = (0, 0, 0)^T$ n'est pas une solution optimale du problème $(P)$.
4. Trouver alors une solution optimale de $(P)$ en utilisant la méthode du simplexe quadratique de Wolfe.