Connectez-vous pour consulter le corrigé.
Ce problème a pour objet l’étude des points en lesquels une application linéaire de \(\mathbb{R}^{p}\) dans \(\mathbb{R}\) atteint son maximum sur l’ensemble des solutions d’un système d’inéquations linéaires.
Pour tout entier \(p\) strictement positif, on identifiera \(\mathbb{R}^{p}\) et \(\mathcal M_{p, 1}(\mathbb{R})\).
Rappels et notations
Pour tout réel \(r\) strictement positifs et tout élément \(a\) de \(\mathbb{R}^2\), on note \(\mathcal{B}_o(a,r )\) la boule ouverte de centre \(a\) et de rayon \(r\), c’est-à-dire : \[\mathcal{B}_o(a,r) = \left\lbrace x\in \mathbb{R}^2 \ / \ \left\| x-a \right\| < r \right\rbrace\]
On dit qu’une partie non vide \(\mathcal{O}\) de \(\mathbb{R}^2\) est une partie ouverte si tout élément \(a\) de \(\mathcal{O}\) est le centre d’une boule ouverte incluse dans \(\mathcal{O}\), i.e. si : \[\forall a \in \mathcal{O},\ \exists r\in\mathbb{R}_+^\ast\ / \ \mathcal{B}_o(a,r ) \subset \mathcal{O}\]
On dit qu’une partie \(\mathcal{F}\) de \(\mathbb{R}^2\) est fermée si son complémentaire \(\mathbb{R}^2\setminus \mathcal{F}\) est une partie ouverte.
On dit qu’une partie \(K\) non vide de \(\mathbb{R}\) est majorée lorsqu’il existe un réel \(M\) tel que \[\forall x \in K, \ x \leqslant M\]
Un réel \(M\) vérifiant ces inégalités s’appelle un majorant de \(K\); on dit aussi que \(M\) majore \(K\).
Dans ce qui suit on suppose que \(K\) est une partie non vide et majorée de \(\mathbb{R}\).
Soit \(M\) un majorant de \(K\) et \(a\) un élément de \(K\). On définit les suites \(\left(u_{n}\right)_{n \in \mathbb{N}}\) et \(\left(v_{n}\right)_{n \in \mathbb{N}}\) par : \[u_{0}=a, \quad v_{0}=M\] et par les relations : \[\forall n \in \mathbb{N}, \ \left(u_{n+1}, v_{n+1}\right)= \begin{cases} \displaystyle \left(\frac{u_{n}+v_{n}}{2}, v_{n}\right) & \text { si } \frac{u_{n}+v_{n}}{2} \text { ne majore pas K } \\ \displaystyle \left(u_{n}, \frac{u_{n}+v_{n}}{2}\right) & \text { sinon } \rule[0pt]{0pt}{20pt}\end{cases}\]
On suppose, dans cette question seulement, que \(K= \left[ 0,1 \right[ \cup \left[ 3,4 \right[\), \(a=0\) et que \(M=10\).
Déterminer \(\left(u_{n}, v_{n}\right)\) pour tout entier \(n\) appartenant à \(\{1,2,3,4\}\).
On revient désormais au cas général.
Montrer que: \(\forall n \in \mathbb{N}, \ u_{n} \leqslant v_{n}\).
Montrer que les deux suites \(\left(u_{n}\right)_{n \in \mathbb{N}}\) et \(\left(v_{n}\right)_{n \in \mathbb{N}}\) sont adjacentes et convergent vers un réel \(b\).
Montrer que pour tout entier positif \(n\), \(v_{n}\) est un majorant de \(K\), puis que \(b\) majore \(K\).
Montrer qu’il existe une suite d’éléments de \(K\) qui converge vers \(b\).
On suppose que \(b^{\prime}\) est un majorant de \(K\).
Montrer que \(b^{\prime} \geqslant b\).
En déduire que \(b\) ne dépend pas des choix initiaux de \(a\) et \(M\) pourvu que \(a\) appartienne à \(K\) et que \(M\) majore \(K\).
Désormais, on notera \(\alpha_{K}\) le majorant \(b\) de \(K\) ainsi obtenu.
On munit \(\mathbb{R}^{2}\) de sa norme euclidienne définie par \(\|(x, y)\|=\sqrt{x^{2}+y^{2}}\) pour tout \((x, y)\) appartenant à \(\mathbb{R}^{2}\).
On considère trois nombres réels \(a, b, c\), tels que \((a, b) \neq(0,0)\). On définit alors les trois ensembles: \[\begin{gathered} \mathscr{D}=\left\{(x, y) \in \mathbb{R}^{2} ,\ a x+b y+c=0\right\} \\ \mathscr{R}_{+}=\left\{(x, y) \in \mathbb{R}^{2} ,\ a x+b y+c>0\right\} \\ \mathscr{R}_{-}=\left\{(x, y) \in \mathbb{R}^{2} ,\ a x+b y+c<0\right\} \end{gathered}\]
Montrer que \(\mathscr{R}_{+}\) est une partie ouverte de \(\mathbb{R}^{2}\).
On pourra montrer, en utilisant la continuité de \((x, y) \longmapsto a x+b y+c\) en un point \(\left(x_{0}, y_{0}\right)\) appartenant à \(\mathscr{R}_{+}\), qu’il existe une boule ouverte centrée en \(\left(x_{0}, y_{0}\right)\) et incluse dans \(\mathscr{R}_{+}\).
Il s’ensuit, mutatis mutandis, que \(\mathscr{R}_{-}\) est également une partie ouverte de \(\mathbb{R}^{2}\), ce que l’on admettra.
Soit \((x, y)\) et \(\left(x^{\prime}, y^{\prime}\right)\) deux éléments de \(\mathscr{R}_{+}\). Montrer que, pour tout réel \(\lambda\) appartenant à \([0,1]\), le couple \(\left(\lambda x+(1-\lambda) x^{\prime}, \lambda y+ \left( 1-\lambda \right) y^{\prime}\right)\) appartient à \(\mathscr{R}_{+}\).
On suppose que \((x, y)\) et \(\left(x^{\prime}, y^{\prime}\right)\) appartiennent respectivement à \(\mathscr{R}_{+}\) et \(\mathscr{R}_{-}\).
En considérant la fonction \(\lambda \mapsto a\left(\lambda x+ \left( 1-\lambda \right) x^{\prime}\right)+b\left(\lambda y+ \left( 1-\lambda \right) y^{\prime}\right)+c\), montrer qu’il existe \(\lambda\) dans \([0,1]\) tel que \(\left(\lambda x+ \left( 1-\lambda \right) x^{\prime}, \lambda y+ \left( 1-\lambda \right) y^{\prime}\right)\) appartient à \(\mathscr{D}\).
Soit \(k\) un entier strictement positif. On considère des parties non vides et ouvertes de \(\mathbb{R}^{2}\), notées \(A_{1}, \ldots, A_{k}\).
On suppose dans cette sous-question que \(A_{1} \cap \ldots \cap A_{k}\) est non vide. Montrer que \(A_{1} \cap \ldots \cap A_{k}\) est une partie ouverte de \(\mathbb{R}^{2}\).
Si \(\left(x_{0}, y_{0}\right)\) est un élément de \(A_{1} \cap \ldots \cap A_{k}\), on montrera qu’il existe un réel \(r\) strictement positif tel que la boule de centre \(\left(x_{0}, y_{0}\right)\) et de rayon \(r\) soit incluse dans \(A_{1} \cap \ldots \cap A_{k}\).
Montrer que \(A_{1} \cup \ldots \cup A_{k}\) est une partie ouverte de \(\mathbb{R}^{2}\).
On note \(\Delta\) l’ensemble \(\left\{(x, y) \in \mathbb{R}^{2} ,\ x \geqslant 0, y \geqslant 0,1-2 x+y \geqslant 0\right.\) et \(\left.1+x-2 y \geqslant 0\right\}\) et \(g\) l’application définie sur \(\Delta\) par: \[\forall(x, y) \in \Delta, \ g(x, y)=3 x-y+4\]
Représenter graphiquement \(\Delta\) dans un plan \(\mathscr{P}\) muni d’un repère orthonormé \((O, \vec{\imath}, \vec{\jmath})\).
Montrer que \(\Delta\) est une partie fermée et bornée de \(\mathbb{R}^{2}\).
Montrer que \(g\) admet un maximum sur \(\Delta\).
Ce maximum peut-il être atteint en un point de l’ensemble \(\Delta^{\prime}\) défini par: \[\Delta^{\prime}=\left\{(x, y) \in \mathbb{R}^{2} ,\ x>0, y>0,1-2 x+y>0 \text { et } 1+x-2 y>0\right\}\]
Déterminer l’ensemble des points de \(\Delta\) où ce maximum est atteint.
On considère la matrice \(A= \begin{pmatrix} 2 & -1 & 1 & 0 \\ -1 & 2 & 0 & 1 \end{pmatrix}\) et la matrice colonne \(B= \begin{pmatrix} 1 \\ 1 \end{pmatrix}\).
On note \(\mathscr{C}\) l’ensemble \(\left\{X= (x_i)_{1\leqslant i \leqslant 4}\in \mathcal{M}_{4,1}(\mathbb{R}) ,\ x_{1} \geqslant 0, x_{2} \geqslant 0, x_{3} \geqslant 0, x_{4} \geqslant 0 \text{ et } A X=B\right\}\).
Montrer que \(X= (x_i)_{1\leqslant i \leqslant 4}\) appartient à \(\mathscr{C}\) si et seulement si \(x_{1}, x_{2}, x_{3}, x_{4}\) satisfont : \[\begin{cases} x_{3}=1-2 x_{1}+x_{2} \\ x_{4}=1+x_{1}-2 x_{2} \\ \left(x_{1}, x_{2}\right) \in \Delta \end{cases}\]
On considère l’élément \(W= \begin{pmatrix} 2 \\ 4 \\ 1 \\ 3 \end{pmatrix}\) appartenant à \(\mathbb{R}^{4}\) (que l’on confond ici avec \(\mathcal{M}_{4,1}(\mathbb{R})\)).
On munit \(\mathbb{R}^{4}\) de son produit scalaire canonique : \(\langle X, Y\rangle= {}^t\!XY\). On considère également la fonction \(f\) définie sur \(\mathscr{E}\) par: \[\forall X \in \mathscr{C}, \ f(X)=\langle X, W\rangle\]
Montrer que \(f(X)=g\left(x_{1}, x_{2}\right)\) pour tout élément \(X= \begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{pmatrix}\) appartenant à \(\mathscr{C}\).
Déterminer l’ensemble des points en lesquels \(f\) atteint son maximum sur \(\mathscr{C}\).
Désormais \(n\) et \(p\) désigneront des entiers strictement positifs.
On considère une matrice \(A\) appartenant à \(\mathcal{M}_{n, p}(\mathbb{R})\), et deux matrices colonnes \(B\) et \(W\) appartenant respectivement à \(\mathbb{R}^{n}\) et \(\mathbb{R}^{p}\).
Pour tout élément \(X\) de \(\mathbb{R}^{p}\) et pour tout \(i\) appartenant à \(\{1, \ldots, p\}\), nous noterons \(X_{i}\) sa \(i\)-ième composante, et ainsi \(X= \begin{pmatrix} X_{1} \\ \vdots \\ X_{p} \end{pmatrix}\).
On dira qu’un élément \(X\) de \(\mathbb{R}^{p}\) est positif et on écrira \(X \geqslant 0\), lorsque toutes ses composantes sont positives.
On munit \(\mathbb{R}^{p}\) de son produit scalaire canonique : \(\langle X, Y\rangle= {}^t\!XY\).
On considère l’ensemble \(\mathscr{C}=\left\{X \in \mathbb{R}^{p} ,\ X \geqslant 0 \text{ et } A X=B\right\}\) et l’application \(f\) définie sur \(\mathscr{C}\) par : \[\forall X \in \mathscr{C}, \ f(X)=\langle X, W\rangle\]
On dit qu’un élément \(Z\) de \(\mathscr{C}\) est un sommet de \(\mathscr{C}\) lorsque : \[\forall\left(Z^{\prime}, Z^{\prime \prime}\right) \in \mathscr{C}^{2}, \ \forall \lambda \in\left] 0,1\right[,\ \left(Z=\lambda Z^{\prime}+(1-\lambda) Z^{\prime \prime}\right) \Rightarrow \left(Z^{\prime}=Z^{\prime \prime}\right)\]
Si \(X= \begin{pmatrix} X_{1} \\ \vdots \\ X_{p} \end{pmatrix}\) est un élément de \(\mathbb{R}^{p}\), on notera \(s(X)\) l’ensemble \(\left\{i \in\{1, \ldots, p\} ,\ X_{i} \neq 0\right\}\); cet ensemble sera appelé le support de \(X\).
Enfin, on notera \(C^{1}, C^{2}, \ldots, C^{p}\) les colonnes de \(A\).
Toutes ces notations seront utilisées jusqu’à la fin du problème.
Vérifier que si l’élément nul de \(\mathbb{R}^{p}\) appartient à \(\mathscr{C}\), alors il est un sommet de \(\mathscr{C}\).
On revient au cas général et on suppose dans ce qui suit que \(\mathscr{C}\) est non vide et que \(f\) atteint son maximum sur \(\mathscr{C}\) en \(U\). Ce maximum sera noté \(M_{0}\). Le but de ce qui va suivre est de construire un sommet de \(\mathscr{C}\) en lequel \(f\) atteint son maximum. On suppose donc que \(U\) n’est pas un sommet de \(\mathscr{C}\) et on considère deux éléments distincts \(U^{\prime}, U^{\prime \prime}\) appartenant à \(\mathscr{C}\) et un réel \(\lambda\) appartenant à \(] 0,1 [\) tels que \(U=\lambda U^{\prime}+ \left( 1-\lambda \right) U^{\prime \prime}\).
Vérifier que \(f(U^{\prime})=f(U^{\prime \prime})=f(U)\) et en déduire que le vecteur \(V=U^{\prime \prime}-U^{\prime}\) est orthogonal à \(W\).
Le vecteur \(U^{\prime \prime}-U^{\prime}\) étant non nul, il a au moins une composante non nulle et quitte a échanger \(U^{\prime}\) et \(U^{\prime \prime}\) on peut supposer que le vecteur \(V\) égal à \(U^{\prime \prime}-U^{\prime}\) admet une composante strictement négative. C’est ce que nous supposons désormais.
Montrer que : \(s(U^{\prime}) \subset s(U)\), \(s(U^{\prime \prime}) \subset s(U)\) et \(s(V) \subset s(U)\).
Pour tout réel \(\mu\), calculer : \(A \left( U+\mu V \right)\).
Montrer que \(s(U+\mu V) \subset s(U)\) pour tout réel \(\mu\).
Montrer que la famille \(\left(C^{i}\right)_{i \in s(U)}\) est liée. On pourra considérer \(A V\).
On considère \(K=\{\mu \in \mathbb{R}, \ U+\mu V \in \mathscr{C}\}\).
Montrer que \(K\) est une partie non vide et majorée de \(\mathbb{R}\).
Montrer que \(U+\alpha_{K} V\) appartient à \(\mathscr{C}\) et que \(f(U+\alpha_{K} V)=M_{0}\).
Le nombre \(\alpha_{K}\) a été défini dans la partie \(I\).
On suppose que, pour tout \(i\) appartenant à \(s(U)\), la \(i\)-ième composante \(Y_{i}\) de la colonne \(Y\) égale à \(U+\alpha_{K} V\) est non nulle.
En remarquant que pour tout \(i\) appartenant à \(s(U)\), \(\displaystyle \lim _{\mu \rightarrow 0}\left(U_{i}+\left(\alpha_{K}+\mu\right) V_{i}\right)=U_{i}+\alpha_{K} V_{i}\), justifier l’existence d’un réel \(\eta\), strictement positif, tel que \(U+\left(\alpha_{K}+\eta\right) V\) appartienne à \(\mathscr{C}\).
En déduire que \(s(U+\alpha_{K} V)\) est strictement inclus dans \(s(U)\).
Nous noterons désormais \(U^{(1)}=U+\alpha_{K} V\) et nous supposons que \(U^{(1)}\) n’est pas un sommet de \(\mathscr{C}\).
En se servant des questions précédentes, montrer que l’on peut construire un élément \(U^{(2)}\) de \(\mathscr{C}\) tel que \(f(U^{(2)})=M_{0}\) et tel que \(s(U^{(2)})\) soit strictement inclus dans \(s(U^{(1)})\).
Déduire de ce qui précède l’existence d’un sommet de \(\mathscr{C}\) en lequel \(f\) atteint son maximum sur \(\mathscr{C}\).
Dans cette partie nous reprenons les mêmes notations que dans la partie précédente et nous noterons par \(\left\langle X, X^{\prime}\right\rangle\) aussi bien le produit scalaire canonique de deux vecteurs \(X\) et \(X^{\prime}\) de \(\mathbb{R}^{p}\), que le produit scalaire canonique de deux vecteurs \(X\) et \(X^{\prime}\) de \(\mathbb{R}^{n}\).
Montrer qu’il existe une matrice \(A^{\prime}\) appartenant à \(\mathcal M_{p, n}(\mathbb{R})\) telle que : \[\forall(X, Y) \in \mathbb{R}^{p} \times \mathbb{R}^{n}, \ \langle A X, Y\rangle=\left\langle X, A^{\prime} Y\right\rangle\]
On note \(r\) le rang de la matrice \(A\). On suppose d’une part que \(r\) est non nul, et d’autre part que la famille \(\left(C^{1}, C^{2}, \ldots, C^{r}\right)\) est libre.
On note \(E\) l’espace vectoriel engendré par les colonnes \(C^{1}, \ldots, C^{p}\) de \(A\).
Montrer que l’application \(\theta: Y \mapsto \begin{pmatrix} \left\langle Y, C^{1}\right\rangle \\ \vdots \\ \left\langle Y, C^{r}\right\rangle \end{pmatrix}\) est un isomorphisme de \(E\) dans \(\mathbb{R}^{r}\).
Montrer qu’il existe un unique vecteur colonne \(Z\) appartenant à \(E\) tel que, pour tout \(i\) appartenant à \(\{1, \ldots, r\}\), on a \(\left\langle Z, C^{i}\right\rangle=W_{i}\). On rappelle que \(W_{i}\) représente la \(i\)-ième composante du vecteur \(W\) introduit dans le préambule de la partie III.
Exprimer les composantes dans la base canonique de \(\mathbb{R}^{p}\) du vecteur colonne \(A^{\prime} Z\), à l’aide des produits scalaires \(\left\langle Z, C^{i}\right\rangle\), \((i=1, \ldots, p)\).
Dans cette sous-question on suppose en outre que : \(\forall i \in\{r+1, \ldots, p\}, \ \left\langle Z, C^{i}\right\rangle \geqslant W_{i}\).
Soit \(X\) un élément appartenant à \(\mathscr{C}\), montrer que \(\langle Z, B\rangle \geqslant\langle X, W\rangle\).
On suppose qu’il existe un vecteur \(U\) appartenant à \(\mathscr{C}\) tel que \(s(U)=\{1, \ldots, r\}\).
Prouver que la fonction \(f: X \mapsto\langle X, W\rangle\) atteint son maximum sur \(\mathscr{C}\) en \(U\) et que \(U\) est un sommet de \(\mathscr C\).
Dans cette question \(A\) et \(W\) sont respectivement la matrice et le vecteur introduits dans la partie II.
Déterminer la valeur de \(r\).
Déterminer le vecteur \(Z\).
Est-ce que \(A^{\prime} Z-W \geqslant 0\) ?
Retrouve-t-on les résultats de la partie II ?
Le corrigé pas à pas, les aides et les explications sont disponibles dans la plateforme.
