%%%%%%%%%%%%%%%%%%%%% ENSAE 1990 MATH II - CORRIGE %%%%%%%%%%%%%%%%%%%%%%%%%
% par Robert CABANE
% 19 rue de Lyon 33000 BORDEAUX
% EMAIL: rcabane@free.fr
%
% Format: PLAIN TEX
% collection de macros
\input math3.sty
% mise en page (a rectifier si besoin)
\input frpage.sty
\def\E{{\cal E}}
\def\H{{\cal H}}
\gdef\P{{\cal P}}
\hyphenation{coef-fi-cient coef-fi-cients}
%
\grostitre{ENSAE 1990 Math. II - Corrig\'e: programmation lin\'eaire}

Dans ce probl\`eme, conform\'ement au vocabulaire traditionnel de 
la Programmation Lin\'eaire, on appelle \og programme\fg{} tout
probl\`eme consistant \`a d\'ecrire l'ensemble des solutions d'un
syst\`emes d'\'equations et d'in\'equations lin\'eaires (en fait,
affines).

\partie %I
\question %1
Pour toute in\'egalit\'e de la forme $b_1x_1+\cdots+b_nx_n\le 0$ 
il nous suffit d'introduire une variable suppl\'ementaire
$x_{n+1}$ et de la lier aux autres par une relation de la forme
$b_1x_1+\cdots+b_nx_n+1.x_{n+1}=0$, o\`u l'on peut bien poser
$b_{n+1}=0$. Il reste \`a imposer $x_{n+1}\le 0$ pour traduire
correctement le programme initial.

\question %2
Tout nombre r\'eel est d\'ecomposable en diff\'erence de deux 
nombres positifs.

\question %3
Il suffit de changer $f$ en $-f$ pour passer d'une maximisation \`a 
une minimisation et vice-versa.

\question[Mise sous forme canonique.] %4
On proc\`ede de la mani\`ere suivante: 
\sousquestion
On change \'eventuellement $f$ en $-f$ pour avoir un probl\`eme de
maximisation.

\sousquestion 
On remplace ensuite toutes les contraintes affines par des
contraintes lin\'eaires en introduisant une variable auxiliaire 
$x_0$ valant 1; ainsi, une contrainte $a_1x_1+\cdots+a_nx_n+c\le
0$ peut \^etre transform\'ee en $a_1x_1+\cdots+a_nx_n+cx_0\le 0$,
et on transforme de m\^eme une contrainte d'\'egalit\'e.

\sousquestion
On remplace ensuite les contraintes d'in\'egalit\'e par des 
contraintes d'\'egalit\'e et des contraintes de signes de
variables, selon la m\'ethode vue en I1.

\sousquestion
Pour toutes les variables non encore soumises \`a une contrainte 
de signe, on remplace celles-ci par deux nouvelles variables
soumises \`a une contrainte de positivit\'e.

A l'issue de ces transformations successives, le programme initial se
trouve sous forme canonique. Le processus n'est pas du tout unique.

\question %5
On introduit $x_4$ de sorte que $x_1+2x_3\ge 2$ devienne 
$x_1+2x_3-x_4=2$ avec $x_4\ge 0$. Puis on d\'edouble les
variables $x_2$ et $x_3$ en $x_2=x'_2-x''_2$ et $x_3$ de m\^eme,
avec une condition de positivit\'e sur les variables nouvellement
introduites.

%%%%%%%%%%%%%%%%%%% PARTIE II %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\partie[Quelques techniques d'analyse convexe] %II

\centerline{\bf Pr\'eliminaire: les th\'eor\`emes de Carath\'eodory et 
Krein-Milman.}

Le r\'esultat que l'\'enonc\'e propose d'admettre est faux, car 
il aurait d\^u utiliser un point de plus (cela ne g\^ene pas la
suite du probl\`eme) et supposer le convexe compact.

Voici comment l'on proc\`ede pour \'etablir de tels r\'esultats.

\sousquestion
On montre qu'une intersection quelconque de convexes est convexe.
C'est fait ci-dessous (II2).

\sousquestion
Soit $A$ une partie non vide de $E=\RR^n$. Alors l'intersection 
des convexes contenant $A$ est la plus petite partie convexe
contenant $A$ (notion de \og convexe engendr\'e\fg ). On l'appelle
{\bf l'enveloppe convexe de $A$}, not\'ee $c(A)$.

\sousquestion
On montre que $c(A)$ est l'ensemble des barycentres \`a 
coefficients positifs ou nuls d'\'el\'ements de $A$, pris en
quantit\'e quelconque. La preuve est analogue \`a celle qui 
montre que le sous-espace vectoriel engendr\'e par $A$ est
l'ensemble des combinaisons lin\'eaires d'\'el\'ements de $A$; il
suffit de se restreindre aux combinaisons convexes au lieu des
combinaisons lin\'eaires quelconques (c'est le principe dit de
l'associativit\'e du barycentre, mais il faut utiliser une
notation vectorielle pour que ce soit facile \`a \'ecrire).

\sousquestion
On montre alors le {\bf th\'eor\`eme de Carath\'eodory}: l'enveloppe 
convexe $c(A)$ de $A$ est l'ensemble des barycentres \`a
coefficients positifs ou nuls des parties de $A$ ayant au plus
$n+1$ \'el\'ements.

Pour ce faire, on prouve que toute combinaison convexe de $p$ 
\'el\'ements de $A$, avec $p>n+1$, peut se r\'e\'ecrire en une
combinaison convexe de $p-1$ \'el\'ements de $A$. En effet,
consid\'erons $m=\sum_{k=1}^p\lambda _ka_k$ avec $\lambda _k\in 
[0,1]$ et $\sum_{k=1}^p\lambda _k=1$. Si l'un des $\lambda _k$
est nul il n'y a rien \`a faire. Sinon, on peut par exemple
supposer que $\lambda _p\ne 0$. Les vecteurs $a_k-a_p$, pris pour
$k<p$, sont en nombre $p-1>n$, donc sont li\'es. On \'ecrit cette 
d\'ependance: $\sum_{k=1}^{p-1}\mu _k(a_k-a_p)=0$ soit
$\sum_{k=1}^{p-1}\mu _ka_k=\Bigl(\sum_{k=1}^{p-1}\mu _k\Bigr)a_p$. 
Posons $\mu _p=-\sum_1^{p-1}\mu _i$; on a alors
$\sum_1^p\mu _ia_i=0$ avec $I=\{i\ /\ \mu _i>0\}\ne \emptyset $
puisque ces coefficients ne sont pas tous nuls et ont une somme
nulle. Soit alors $t=\Min_{i\in I}\,\Frac{\lambda _i}{\mu _i}$.
On a $\lambda _i-t\,\mu _i\ge 0$ pour tout $i\in I$ (avec un cas
de nullit\'e) et $\sum_1^p\lambda _i-t\mu _i=1$ ainsi que
$m=\sum_{i=1}^p\,(\lambda _i-t\,\mu _i)\,a_i,$ relation du m\^eme 
type que la premi\`ere avec en fait au plus $p-1$ coefficients
strictement positifs. Par r\'ecurrence descendante, on est ainsi
conduit \`a une expression mettant en jeu au plus $n+1$ vecteurs
de $E$. Quitte \`a dupliquer certains points, on peut m\^eme
\'enoncer que tout point de l'enveloppe convexe de $A$ est 
barycentre \`a coefficients positifs ou nuls de $n+1$
\'el\'ements de $A$.

\sousquestion
On peut en d\'eduire que l'enveloppe convexe d'une partie 
compacte est elle-m\^eme compacte. En effet, $A^{n+1}\times 
[0,1]^{n+1}$ est une partie compacte de $E^{n+1}\times \RR^{n+1}$
et l'ensemble des $(2n+2)$-uplets de la forme
$(a_0,\dots,a_n,\lambda _0,\dots,\lambda _n)$ et tels que $a_j\in 
A$, $\lambda _j\in [0,1]$ et $\sum_{j=0}^n\lambda _j=1$ en est un
sous-ensemble ferm\'e donc compact. L'image de ce (grand) compact
par la fonction continue $$(a_0,\dots,a_n,\lambda 
_0,\dots,\lambda _n)\mapsto \sum_{j=0}^n\lambda _ja_j$$ est donc
compacte, et c'est l'enveloppe convexe de $A$.

\sousquestion
Il reste \`a montrer le {\bf th\'eor\`eme de Krein-Milman}: tout 
convexe {\bf compact} est l'enveloppe convexe de l'ensemble des
points extr\'emaux (=sommets). On le d\'emontre par r\'ecurrence
sur la dimension et en mettant une structure euclidienne sur
$\RR^n$. En dimension 1 c'est \'evident. Expliquons comment l'on
fait pour poursuivre en traitant par exemple la dimension 2. On 
prend un convexe compact $A$ de $\RR^2$, un point de $A$, on fait
passer une droite $D$ par $A$; l'ensemble $D\cap A$ est un
convexe compact de $D$, donc un segment $[a,b]$. Ses
extr\'emit\'es, points-fronti\`ere de $A$, sont de nature \`a
\^etre des sommets de $A$, \`a ceci pr\`es que dans la 
fronti\`ere de $A$ l'on peut trouver des segments.
Pr\'ecis\'ement, si $b$ n'est pas extr\'emal alors on peut
trouver $b=\alpha b_1+(1-\alpha )b_2$ avec $\alpha \in [0,1]$ et 
$b_1,b_2\in A$. La droite $(b_1b_2)$ recoupe encore $A$ selon un
segment contenant $b$ et les extr\'emit\'es de ce segment sont
des sommets en dimension 2. Pour des dimensions sup\'erieures il
mettre au point une notion de \og face\fg{} ou \og hyperplan
d'appui\fg.

{\it Ce th\'eor\`eme est faux pour les convexes ferm\'es: } il suffit de 
consid\'erer un demi-espace pour lequel l'ensemble des sommets
est vide !

{\it Dans la suite nous n'utiliserons pas ce r\'esultat.}

\question[Convexit\'e des demi-espaces.] %1
Pour toute forme lin\'eaire $\varphi $ sur $\RR^n$, l'image 
r\'eciproque d'un ensemble convexe $A\subset \RR$ est convexe. En
effet, si $x$ et $y$ ont des images dans $A$ alors $\varphi 
(\lambda x+(1-\lambda )y)=\lambda \varphi (x)+(1-\lambda )\varphi 
(y)\in A$ pour tout $\lambda \in [0,1]$. Ceci s'applique
notamment lorsque $A=[a,+\infty [$, et alors $\varphi ^{-1}(A)$ 
est un \og demi-espace\fg.

\question[Intersections de convexes.] %2
Si $A_i$ est convexe pour tout $i\in I$, alors pour tous $x$ et 
$y$ appartenant \`a $\cap  A_i$ et $\lambda \in [0,1]$ l'on a
$\lambda x+(1-\lambda )y\in A_i$ pour tout $i$, donc $\lambda 
x+(1-\lambda )y\in \cap A_i$.

\question %3
Les in\'egalit\'es $x_j\ge 0$ d\'efinissent des demi-espaces, 
donc des convexes, tandis que les \'egalit\'es $AX=b$
d\'efinissent des hyperplans, \'egalement convexes. Il n'y a plus
qu'\`a intersecter. On note au passage que $\E$ est aussi un
ensemble ferm\'e ne contenant aucune droite (\`a cause de la
positivit\'e des composantes).

\question %4
Cette question est d\'elicate si on veut traiter le cas o\`u $\E$ 
n'est pas born\'e.

\Lemme.
L'ensemble des r\'ealisables $\E$ d'un programme lin\'eaire $\P$
poss\`ede au moins un sommet.
\Preuve
Nous proc\'ederons par r\'ecurrence sur la dimension $n$.
Pour $n=1$ on a soit $m=0$ et pour seule condition $x_1\ge 0$ 
(sommet en 0), soit $m=1$ et pour condition $x_1=\frac{b}{a}$ 
(sommet = le seul point).

\parindent8mm
Supposons que tout programme sous forme canonique et \`a $n-1$ 
variables admette un sommet dans l'ensemble des r\'ealisables.
Consid\'erons le programme canonique $\P$ associ\'e \`a $A$, 
$b$ et $c$, $A$ ayant $n$ colonnes, et montrons que dans
l'ensemble des r\'ealisables $\E$ il existe au moins un point
admettant une coordonn\'ee nulle. Choisissons deux r\'ealisables
distincts $X$ et $Y$ et consid\'erons $Z=\alpha X+(1-\alpha )Y$; 
$Z$ est dans $\E$ au moins pour $\alpha \in [0,1]$. La droite
$(XY)$ va couper l'un des hyperplans $x_i=0$; en effet, si ce
n'\'etait pas le cas, il viendrait $\alpha x_i+(1-\alpha )y_i>0$
pour tout r\'eel $\alpha $ et tout $i\le n$, ce qui exige 
$x_i=y_i>0$, soit $X=Y$, exclu. L'ensemble des $\alpha $ tels que 
$Z$ soit r\'ealisable est certainement un intervalle de $\R$ (par
convexit\'e), diff\'erent de $\R$, et en prenant pour $\alpha $ 
une extr\'emit\'e finie de cet intervalle, on obtient un
r\'ealisable ayant une coordonn\'ee nulle. Pour simplifier,
nommons $X$ ce point et supposons que $x_1=0$.

Consid\'erons alors le programme $\P'$ d\'efini par les 
m\^emes conditions, avec en plus $x_1=0$; il peut \^etre vu comme
un programme lin\'eaire en dimension $n-1$ (exprim\'e avec
$x_2,\dots,x_n$). L'hypoth\`ese de r\'ecurrence s'applique et
nous donne un sommet $X'$ v\'erifiant $\P'$ et ayant une
coordonn\'ee $x'_1=0$. Bien entendu, $X'$ est dans $\E$. Si $X'$
pouvait s'\'ecrit sous la forme $X'=\lambda Y+\lambda 'Y'$, avec
$Y$ et $Y'$ dans $\E$ et $\lambda \ge 0,\lambda '\ge 0,\lambda 
+\lambda '=1$, alors sur la premi\`ere composante on a 
$0=x'_1=\lambda y_1+\lambda 'y'_1$; cette derni\`ere \'equation 
oblige $y_1$ et $y'_1$ \`a \^etre nuls, et $Y,Y'$ \`a se situer
dans l'ensemble des r\'ealisables $\E'$ de $\P'$. Comme
$X'$ est un sommet de $\E'$, on doit avoir $X'=Y=Y'$, et $X'$ est
un sommet de $\E$\qed \medskip

Revenons \`a l'optimisation de $cX$. Comme on suppose qu'il 
existe un maximum fini, un point $X^*$ de $\E$ existe, tel que
pour tout $X\in \E$ l'on ait $cX\le \gamma =cX^*$. Consid\'erons
l'hyperplan $H$ d'\'equation $cX=\gamma $. Cet hyperplan coupe
$\E$ en un ensemble non vide (il contient $X^*$), convexe, et
c'est un ensemble de r\'ealisables pour un programme ${\P''}$
ayant une condition suppl\'ementaire. Nous pouvons lui appliquer
ce qui pr\'ec\`ede; ainsi, $\E\cap H$ admet un sommet $X'$ tel
que $cX'=\gamma $. Si l'on pouvait \'ecrire $X'=\lambda 
_1X'_1+\lambda _2X'_2$ avec $\lambda _1$ et $\lambda _2$ positifs 
et de somme 1, et $X'_1,X'_2$ dans $\E$, alors on aurait $\gamma 
=cX'=\lambda _1cX'_1+\lambda _2cX'_2\le \lambda _1\gamma +\lambda 
_2\gamma =\gamma $, ce qui oblige \`a avoir $X'_1=X'_2=X'$.
Ainsi, $X'$ est aussi un sommet de $\E$, ce qu'il fallait.
\Reponse
{Tout programme lin\'eaire qui admet un optimum fini, atteint cet} 
{optimum en au moins un sommet de l'ensemble des r\'ealisables.} 
\parindent0mm

\question %5
Si $X_1$ et $X_2$ sont deux sommets en lesquels
$cX_1=cX_2=M=\Max_{Y\in \E} cY$: $c(\alpha _1X_1+\alpha 
_2X_2)=\alpha _1(cX_1)+\alpha _2(cX_2)=(\alpha _1+\alpha _2)M=M$.

%%%%%%%%%%%%%%%%%%% PARTIE III %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\partie %III
\question %1
Notons tout d'abord que si $X=\pmatrix{x_1\cr\vdots\cr x_n}$ 
alors $AX=x_1P_1+\cdots+x_nP_n$. D'autre part, ayant suppos\'e
que $A$ poss\`ede $m$ lignes et $n>m$ colonnes, et est de rang
$m$, les vecteurs $P_1,\dots,P_n$ forment une famille
g\'en\'eratrice de l'espace $\RR^m$. Pour cette raison, le
vecteur $b$ se d\'ecompose sur cette famille g\'en\'eratrice. 
Toute d\'ecomposition de $b$ sur les $P_i$ peut a priori se faire
sur des vecteurs ind\'ependants: il suffit d'extraire une base
form\'ee de $m$ vecteurs; il n'y a cependant pas de raison a
priori qu'une telle d\'ecomposition se fasse avec des
coefficients positifs. Ainsi, l'hypoth\`ese de d\'ecomposition
$b=\sum_{k=1}^Kx_{j_k}P_{j_k}$ est plausible mais non triviale.

\parindent8mm
Le vecteur $X$ de composantes $x_i$ (nulles hormis les
$x_{j_1},\dots,x_{j_K}$) est bien \`a composantes positives et 
d'apr\`es les remarques pr\'ec\'edentes v\'erifie
$AX=\sum_{k=1}^Kx_{j_k}P_{j_k}=b$; il est donc r\'ealisable.

Il nous sera d\'esormais pratique de noter $\H(X)=\{i\in 
\[1,n\]\ /\ x_i>0\}$. Supposons qu'on puisse d\'ecomposer $X$ en
$X=\alpha X'+(1-\alpha )X"$ avec $\alpha \in ]0,1[$ et $X',X"$ 
r\'ealisables. Si $i$ n'est pas dans $\H(X)$ on obtient
$0=\alpha x'_i+(1-\alpha )x"_i$ qui entra\^\i ne $x'_i=x"_i=0$; 
donc $\H(X')\subset \H(X)$ et de m\^eme $\cur
H(X")\subset \H(X)$. On \'ecrira donc les trois vecteurs \`a
partir des indices de $\H(X)=\{j_1,\dots,j_K\}$. Comme $X'$ 
et $X"$ sont suppos\'es r\'ealisables, on a $AX'=AX"=AX=b$,
d'o\`u $A(X'-X")=0=\sum_{k=1}^K(x'_{j_k}-x"_{j_k})P_{j_k}$.
L'ind\'ependance des vecteurs $P_{j_k}$ entra\^\i ne
$x'_{j_k}=x"_{j_k}$, soit $X'=X"$, ce qui assure que $X$ est un
sommet de $\E$.

\question %2
Soit $\H(X)=\{j_1,\dots,j_K\}$ avec les notations 
pr\'ec\'edentes. Il va de soi que les composantes de $X$ ayant
leurs indices hors de $\H(X)$ sont nulles. Supposons une
relation du genre $\sum_{j\in \H(X)}\gamma _jP_j=0$. Posons
$\gamma _i=0$ pour $i\not\in \H(X)$, puis $V=\pmatrix{\gamma 
_1\cr\vdots\cr \gamma _n}$, puis $X'=X-tV,\ X"=X+tV$. On a bien
$X=\frac12X'+\frac12X"$. De plus, les composantes de $X'$ sont de
la forme $x_i-t\gamma _i$. Si $i$ ne se trouve pas dans $\cur
H(X)$ alors $x_i=\gamma _i=0$. Sinon, on a $x_i>0$ donc en 
choisissant $t$ assez petit on aura $x_i-t\gamma _i>0$, et on 
peut le faire simultan\'ement pour tous les indices concern\'es.
La m\^eme d\'emarche s'applique \`a $X"$, fournissant deux
vecteurs r\'ealisables. $X$ \'etant un sommet, on doit avoir
$X=X'=X"$ soit $\gamma _i=0$ pour tout $i$, ce qui assure
l'ind\'ependance des $P_j$ pour $j\in \H(X)$.

\question %3
Une sommet $X$ de l'ensemble des r\'ealisables n'est pas nul car 
alors $b$ est nul, ce qui n'a pas d'int\'er\^et. Il admet donc au
moins une composante strictement positive. On peut alors
introduire $\H(X)$ comme ci-dessus, puis la famille
$(P_j)_{j\in \H(X)}$ qui est libre selon la question
pr\'ec\'edente. Comme la matrice $A$ est de rang $m$, il est 
possible de compl\'eter cette famille libre en une base de
$\RR^m$ avec quelques vecteurs extraits de la famille
$(P_1,\dots,P_n)$ (d'apr\`es le th\'eor\`eme de la base 
incompl\`ete); enfin, $X$ se d\'ecompose sur les $(P_j)_{j\in \H(X)}$ 
avec des coefficients positifs (question {\bf III2\hbox{$^\circ$}}).

\parindent8mm
Supposons que deux sommets $X$ et $X'$ fournissent la m\^eme base
$(P_j)_{j\in J}$ ($J$ ayant \'evidemment $m$ \'el\'ements), sur laquelle 
$b$ admet des composantes positives ou nulles. L'unicit\'e de la 
d\'ecomposition d'un vecteur sur une base entra\^\i ne l'\'egalit\'e de $X$ 
et $X'$. On peut donc cr\'eer une injection de l'ensemble des 
sommets vers l'ensemble des bases extraites des colonnes de $A$.

Le nombre de sous-ensembles de $m$ \'el\'ements que l'on peut former
\`a partir de $n$ objets est de $\binome nm$; c'est pourquoi le 
nombre de familles libres qu'on peut extraire de la famille des
$P_i$ ne d\'epasse pas $\binome nm$. Quant au nombre de sommets, il 
est major\'e par le nombre de bases, donc fini.

\question %4
On peut introduire de nouvelles variables $x_4$ telle que $x_4\ge 
0$ et $x_1+x_2+x_4=1$, puis $x_5$ et $x_6$ telles que
$2x_1+x_2-x_3+x_5=2$ avec $x_5\ge 0$ et enfin
$-x_1+2x_2+x_3+x_6=1$ avec $x_6\ge 0$.

La matrice s'\'ecrit $A=\pmatrix{
1&1&0&1&0&0\cr
2&1&-1&0&1&0\cr
-1&2&1&0&0&1}$
et le vecteur est $b=\pmatrix{1\cr2\cr1}$. Le sommet \'evident 
est d\'eduit de $P_4+2P_5+P_6=b$, donc vaut $X=(0,0,0,1,2,1)$.

%%%%%%%%%%%%%%%%%%% PARTIE IV %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\partie %IV
\questiona %1a
On pose $b=x_1^*P_1+\cdots+x_m^*P_m$ et, comme $(P_1,\dots,P_m)$ 
est une base, $P_k=x_{k1}P_1+\cdots+x_{km}P_m$. Le sommet $X$
consid\'er\'e a pour composantes $(x_1^*,\dots,x_m^*,0,\dots,0)$.
A priori les composantes $x_{kj}$ n'ont aucune raison d'\^etre
positives, tandis que les $x_i^*$ sont positivres ou nulles et que 
certaines sont strictement positives.

\parindent8mm
Envisageons un vecteur $v$ r\'ealisable et de composantes 
$(\xi _1,\dots,\xi _m,0,\dots,\xi _k,0,\dots,0)$. On a par d\'efinition 
$\xi _i\ge 0$ pour tout $i$ et $Av=b$, ce qui s'\'ecrit 
$b=\xi _1P_1+\cdots+\xi _mP_m+\xi _kP_k$. On d\'ecompose $b$ et $P_k$
sur la base $(P_1,\dots,P_m)$, ce qui donne: 
$$
x_1^*P_1+\cdots+x_m^*P_m
=\xi _1P_1+\cdots+\xi _mP_m+\xi _k\bigl(x_{k1}P_1+\cdots+x_{km}P_m\bigr)
$$
soit encore $x_i^*=\xi _i+\xi _kx_{ki}$ pour tout $i$. Si $\xi _k$ est nul, on 
retrouve le sommet $X$. Sinon, on trouve $\xi _i=x_i^*-\xi _kx_{ki}$. 
R\'eciproquement, le vecteur $v$ d\'efini par $\xi _k>0$ et les
formules pr\'ec\'edentes pour les $\xi _i$ ($i\le m$) ne sera r\'ealisable que 
dans la mesure o\`u l'on a $\xi _i\ge 0$, ce qui revient \`a la condition
$x_i^*\ge \xi _kx_{ki}$.

\sousquestion %1b
Pour satisfaire l'ensemble de ces conditions, on peut penser \`a 
prendre $\xi _k$ assez petit si $x_{ki}$ est positif (si $x_{ki}$
est n\'egatif ou nul il n'y a pas de probl\`eme).  
L'op\'eration va \'echouer si on a en m\^eme temps $x_i^*=0$ et
$x_{ki}>0$ pour au moins une valeur de $i$. Ce sont l\`a les 
conditions qui assurent qu'il est possible d'introduire $P_k$ en
sus de $P_1,\dots,P_m$. De surcro\^\i t, pour esp\'erer obtenir
un nouveau sommet, adjacent \`a $X$, il convient d'annuler l'une
des composantes $\xi _j$ sans avoir $x_{kj}=0$; de la sorte, on
passera \`a une base de la forme
$(P_1,\dots,P_{j-1},P_{j+1},\dots,P_m,P_k)$ (cela reste un 
syst\`eme libre parce que $x_{kj}\ne 0$). Ce probl\`eme nous
am\`ene \`a avoir $x_j^*=\xi _kx_{kj}$, ce qui \'echouera
certainement si $x_j^*>0$ et $x_{kj}\le 0$. On peut tenter
l'op\'eration avec une valeur diff\'erente de $j$, mais l'\'echec 
demeurera si on a $x_i^*>0$ et $x_{ki}\le 0$ pour tout $i\le m$.
En r\'esum\'e, notre op\'eration de recherche d'un sommet
adjacent ne peut r\'eussir que si l'on a 
$$ 
\cases{\forall i\le m,\ x_i^*=0\Rightarrow x_{ki}\le 0\cr 
\exists i\le m,\ x_i^*=0=x_{ki}\hbox{ ou }x_i^*>0,\ x_{ki}>0\cr} 
$$ 
La situation $x_i^*=0=x_{ki}$ est tr\`es particuli\`ere: toute
base obtenue en compl\'etant
$(P_1,\dots,P_{i-1},P_{i+1},\dots,P_m)$ convient mais conduit au
m\^eme sommet $X$. 
%%La m\'ethode ci-dessus va construire une infinit\'e de sommets ?

\sousquestion %1c
Soit $\xi _k=\theta _0=\Min_{i\ /\ x_{ki}>0}\Frac{x_i^*}{x_{ki}}>0$ 
(selon la discussion pr\'ec\'edente). Il existe donc un indice $h$ 
tel que $x_h^*=\xi _kx_{kh}$, et pour $i\ne h$ tel que $x_{ki}>0$ on a
comme pr\'evu $x_i^*\ge \xi _kx_{ki}>0$. Ce choix est donc le bon. Si on n'a
pas satisfaction avec $P_k$ il est possible de tenter de
recommencer avec une valeur diff\'erente de $k$.

\question %2
Comme on cherche \`a maximiser $cX=c_1x_1+\cdots+c_nx_n$, pour 
que la m\'ethode ci-dessus conduise \`a un r\'esultat
int\'eressant il faut s'assurer que 
$cX<c_1\xi _1+\cdots+c_m\xi _m+c_k\xi _k$ soit 
$\sum_{i=1}^mc_i(\xi _i-x_i^*)=\sum_{i=1}^mc_i\xi _kx_{ki}<c_k\xi _k$ et $\xi _k$
n'est pas nul; donc on a $\sum_{i=1}^mc_ix_{ki}<c_k$.

\questiona %3a
Il s'agit de d\'ecomposer $b=(1,2,1)$ sur divers choix de colonnes 
de $A$. On d\'eduit de la question {\bf III4\hbox{$^\circ$}}:
$b=P_4+2P_5+P_6$, d'o\`u le sommet $(0,0,0,1,2,1)$. 
On \og introduit\fg{} alors la colonne $P_2$; c'est possible car
$P_2=P_4+P_5+2P_6$, $b$ n'a que des composantes $x_i^*$ strictement 
positives, et il en est de m\^eme des composantes de $P_2$. 
Les quotients $\Frac{x_i^*}{x_{2i}}$ valent ici 
$1,2,\frac12$ et le plus faible est celui qui est relatif \`a 
$P_6$. C'est donc $P_6$ qui va \^etre abandonn\'e pour laisser la 
place \`a $P_2$. On red\'ecompose $b$:
$b=\frac12(P_2+P_4+3P_5)$ (la valeur de la composante 
sur $P_2$ a \'et\'e pr\'evue \`a la question {\bf III1\hbox{$^\circ$}c}). Le sommet 
correspondant est $(0,\frac12,0,\frac12,\frac32,0)$.

\parindent8mm
On va poursuivre de la m\^eme fa\c con. On tente d'introduire $P_1$, se 
basant sur la d\'ecomposition 
$P_1=P_2+P_4-P_5$. Les quotients $\Frac{x_i^*}{x_{1i}}$ valent 
$\frac12,\frac12,-\frac32$ (ce dernier non retenu).
Suivant l'indication de l'\'enonc\'e, on choisit d'abandonner $P_4$.
On red\'ecompose $b=\frac13(P_1+2P_2+2P_5)$, ce qui donne le sommet 
$(\frac13,\frac23,0,0,\frac23,0)$.
Enfin, on tente d'introduire $P_3$ avec $P_3=-P_1+P_2-2P_5$, avec
$b=P_1+2P_2+2P_5$, sommet $(1,0,2,0,2,0)$.
 
\sousquestion %3b
La valeur de $cX$ sur chacun des sommets pr\'ec\'edents est 
respectivement $0,2,3,5$. Il appara\^\i t donc que le choix des 
colonnes de $A$ successivement introduites et abandonn\'ees 
correspondait bien \`a une augmentation de l'objectif.

\sousquestion %3c
Il reste \`a s'assurer que l'on a $cX\le 5$ pour tout $X$ de $\E$.
On peut tenter le faire de mani\`ere directe en revenant \`a 
l'origine du probl\`eme, vue \`a la question {\bf III4\hbox{$^\circ$}} - en prenant 
garde au fait que les coordonn\'ees n'ont plus la m\^eme 
signification. Consid\'erons donc les formes lin\'eaires
$\varphi (X)=x_1+4x_2+2x_3$ (qu'il s'agit d'optimiser), $\ell _1(X)=x_1+x_2\le 1$,
$\ell _2=2x_1+x_2-x_3\le 2$, $\ell _3=-x_1+2x_2+x_3\le 1$. Il nous faut minorer $\ell _2$.
Pour ce faire, on majore $x_3$ \`a l'aide de $\ell _3$ qui est la seule
forme \`a permettre une telle majoration:
$$
\eqalign{-x_1+2x_2+x_3\le 1
&\Rightarrow x_3\le x_1-2x_2+1\\
&\Rightarrow x_1+4x_2+2x_3\le x_1+4x_2+2x_1-4x_2+2=3x_1+2
 \le 3(x_1+x_2)+2\le 5
\>.\\}$$
Finalement, on a bien $\varphi (X)=cX\le 5$. De surcro\^\i t, $cX$ n'atteint 
son maximum que si $x_2=0,\,x_1=1,\,x_3=x_1-2x_2+1=2$, c'est-\`a-dire en 
un seul point. La r\'eponse trouv\'ee ci-dessus en {\bf IV3\hbox{$^\circ$}b} \'etait 
donc unique.

%%%%%%%%%%%%%%%%%%% PARTIE V %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\partie %V
\question %1
On a $AX=b$ et $~AY\ge ~c$, ce qui am\`ene
$~bY=~Yb=~YAX\ge cX$.

\question %2
La question pr\'ec\'edente montre que l'optimum de $cX$ ne peut 
d\'epasser $~bY_0$, ce maximum \'etant atteint pour $X_0$. En inversant 
les r\^oles, $X_0$ joue le r\^ole de \og chien de garde\fg{} pour les $Y$ et 
assure que $Y_0$ r\'ealise le minimum d\'esir\'e.

\question %3
On a $(~Y_0A-c)X_0=~Y_0AX_0-cX_0=~Y_0b-cX_0=0$, et en d\'eveloppant le 
premier produit il vient, avec les composantes $w_j$ de $~AY_0$,
$\sum_{j=1}^nx_j(w_j-c_j)=0$; mais on sait que $~Y_0A\ge c$, soit 
$w_j\ge c_j$; en cons\'equence, on a $w_j=c_j$ pour tout $j$ tel que 
$c_j>0$.

\questiona %4a                                  
Posons $Y=(u,v,w)$:
\def\q{\hphantom{2}}
$$
\min(u+2v+w)
\hbox{\quad sachant que\quad}
\cases{
 u+ 2 v-\q w\ge 1\\
 u+\q v+ 2 w\ge 4\\
\q-\q v+\q w\ge 2\\
u\ge 0,\,v\ge 0,\,w\ge 0\\
}
\leqno\quad({\cal P}II):
$$

\sousquestion %4b
On prend $X_0=(1,0,2,0,2,0)$, correspondant \`a $b=P_1+2P_3+2P_5$.
Les composantes de num\'eros 1,3,5 de ce vecteur sont strictement positives,
donc les contraintes de num\'eros 1,3,5 de $({\cal P}II)$ sont \`a 
l'\'egalit\'e, ce qui devrait permettre de trouver $Y_0$. 
Pratiquement:
$$
\cases{
 u+ 2 v-\q w=1\\
 u+\q v+ 2 w\ge 4\\
\q-\q v+\q w=2\\
u\ge 0,\,v=0,\,w\ge 0\\
}
\Longrightarrow 
Y_0=(u,v,w)=(3,0,2)
\>.$$

\bye

% ancienne solution II4, conforme \`a l'\'enonc\'e mais ...
Dans cette question nous sommes oblig\'es d'accepter qu'en un 
point $X\in \cal E$ au moins la fonction $cX$ atteint son maximum
et que ce point appartient \`a l'enveloppe convexe de l'ensemble
des sommets de $\E$. Si $\E$ est compact c'est garanti, alors que
si $\E$ n'est pas compact il y a un doute.

Dans les conditions ainsi pos\'ees on a $X=\sum_{i=0}^n\alpha _iX_i$, 
$X_i$ \'etant un sommet de $\E$ et $\alpha _i\in [0,1]$,
avec $\sum_{i=0}^n\alpha _i=1$. Il vient $cX=\Max_{Y\in \E}
cY=\sum_{i=0}^n\alpha _icX_i\le \sum_{i=0}^n\alpha _icX=cX$; 
ayant \'egalit\'e toutes les in\'egalit\'es sous-entendues sont
des \'egalit\'es et l'on a $cX_i=cX$ ou bien $\alpha _i=0$; ce
dernier cas ne se produit pas pour tout $i$. D\`es lors,
l'objectif est aussi atteint en tous les sommets $X_i$ tels que 
$\alpha _i\ne 0$, et il en existe.



%%% Local Variables: 
%%% mode: plain-tex
%%% TeX-master: "m90em2c"
%%% End: 
