# Contrôle ponctuel et contrôle en nombres entiers de systèmes distribués.

Christian Saguez

<figure><img src="image_1.png" /></figure>

## To cite this version:

Christian Saguez. Contrôle ponctuel et contrôle en nombres entiers de systèmes distribués.. [Rapport de recherche] IRIA-RR-082, IRIA. 1974, pp.97. hal-04715924

HAL Id: hal-04715924

https://inria.hal.science/hal-04715924v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
IRIA
laboria

laboratoire de recherche
en informatique
et automatique

Contrôle ponctuel
et contrôle en nombres entiers
de systèmes distribués.

C.Saguez.

<figure><img src="image_3.png" /></figure>

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n° 82

Octobre 1974
# CONTROLE PONCTUEL ET CONTROLE EN NOMBRES ENTIERS DE SYSTEMES DISTRIBUÉS

C. Saguez

## Résumé :

Dans ce travail nous étudions deux problèmes de contrôle optimal de systèmes distribués.

Dans le premier cas on contrôle un problème aux valeurs propres par l'intermédiaire de masses de Dirac. L'équation d'état est de la forme :

$$ - M^2 \Delta y + \frac{2M^2}{\lambda} y(b) \delta(x-b) + y = \mu \Phi(x)y $$

$\Phi$ étant une fonction positive, continue par morceaux.

Nous donnons une application de ce problème au positionnement optimal des barres absorbantes dans un réacteur nucléaire.

Dans le second cas, nous contrôlons une équation parabolique par un contrôle $v(t)$, fonction du temps, qui à chaque instant, ne peut prendre ses valeurs que dans un ensemble discret fini. Nous sommes alors amenés à étudier la minimisation de fonctionnelles quadratiques en variables booléennes.

## Abstract :

In this work, we study two optimal control problems of distributed systems.

In the first case, we control with Dirac measures an eigenvalue problem.
The state is given by

$$ - M^2 \Delta y + \frac{2M^2}{\lambda} y(b) \delta(x-b) + y = \mu \Phi(x)y. $$

where $\Phi(x)$ is a piecewise constant, positive function.

We give an application of this problem for the optimal position of absorbant rods in a nuclear reactor.

In the second case, we control a parabolic equation with a control $v(t)$, function of time, which at each instant $t$ takes its value in a finite discrete set. Then we are induced to study the quadratic minimization with 0-1 variables.
# PLAN

## RESUME

### CHAPITRE I

CONTROLE D'UN PROBLEME AUX VALEURS PROPRES PAR DES MASSES DE DIRAC.

APPLICATION AU POSITIONNEMENT OPTIMAL DES BARRES ABSORBANTES DANS
UN REACTEUR NUCLEAIRE.

1 - Position du problème. 2

2 - Existence de l'état du système. 5

3 - Existence d'un contrôle. 11

4 - Détermination d'un état adjoint. 14

5 - Discrétisation du problème. 18

6 - Résultats numériques. 30

### CHAPITRE II

PROBLEME EN VARIABLES TRUEENNES. APPLICATION AU CONTROLE.

1 - Etude du cas parabolique, formulation mathématique. 42

2 - Existence d'un contrôle optimal. 45

3 - Existence d'un contrôle optimal, par une méthode implémentable numériquement. 48

4 - Résolution numérique d'un problème en variables continues. 53

5 - Minimisation d'une fonctionnelle quadratique en variables booléennes. 58

6 - Application de la programmation quadratique booléenne au problème79 de contrôle.

## BIBLIOGRAPHIE

92
# CHAPITRE I

CONTROLE D'UN PROBLEME AUX VALEURS PROPRES PAR DES MASSES DE DIRAC

APPLICATION AU POSITIONNEMENT OPTIMAL DES BARRES

ABSORBANTES DANS UN REACTEUR NUCLEAIRE
Le réacteur nucléaire est supposé être à symétrie circulaire, ce qui permet
de faire l'étude en dimension 1 en choisissant les coordonnées polaires.

<figure><img src="image_4.png" /></figure>

Il se décompose en trois zones. Le flux de
neutrons, pris comme état du système, est
solution d'un problème aux valeurs propres
(* voir la mise en équation du problème
physique(1) Remarque). Le but est de rendre
ce flux le plus uniforme possible par l'inter-
médiaire de barres absorbantes qui sont
placées dans la deuxième zone. Le problème
consiste donc à déterminer l'emplacement opti-
mal de ces barres pour le critère précédent.

1 - POSITION DU PROBLEME

Nous nous plaçons dans le cas d'une seule barre absorbante, la généralisation au cas de n barres se faisant immédiatement.

D'une façon générale, nous pouvons poser le problème ainsi:
Soit Ω un ouvert de R, Ω =]0, R[

E un fermé borné de Ω

b un point de E qui correspond à l'emplacement d'une barre.

On considère alors l'équation

$$
(1.1) \qquad - M^2 \Delta y + \frac{2M^2}{\lambda} y(b) \delta(x-b) + y = \mu \Phi(x)y.
$$

Φ étant une fonction positive, continue par morceaux,
Avec les conditions aux bords :

$$
(1.2) \qquad \frac{\partial y}{\partial n} (o) = 0
$$

$$
(1.3) \quad y(R) = 0.
$$
alors **l'état du système** sera le vecteur propre y solution de (1.1) (1.2) (1.3)
associé à la plus petite valeur propre positive $\mu$ avec $y \ge 0$ ; $y(0)=1$ (1.4)
(cette dernière condition donne l'unicité de la solution, voir Théorème 1).

On se pose alors le **problème de contrôle suivant** :

Déterminer $\bar{b} \in E$ tel que

$$
(1.5) \quad J(\bar{b}) = \min_{b \in E} J(b)
$$

avec

$$
(1.6) \quad J(b) = \int_{\Omega} (y-\bar{y})^2 x \, dx ; \quad \bar{y} = \frac{2}{(R)^2} \int_{\Omega} y \, x \, dx. \blacksquare
$$

**Remarque 1** : Ce problème se généralise au cas de n barres $b_1, \dots, b_n$
$b_i \in E_i$ fermé borné de $\Omega$ avec $E_i \cap E_j = \emptyset$.

**Remarque 2** : On prend la mesure x dx, car on se place en coordonnées polaires.

Remarque 3 : Dans le cas du réacteur, le problème peut s'écrire ainsi

on prend $\Omega = ]0, R_3[$

$\Omega$ est divisé en 3 zones, par la donnée de $R_1$ et $R_2$, tels que

$0 < R_1 < R_2 < R_3.$

$$
\begin{align*}
\text{On note} \quad \Omega_1 &= ]0, R_1[ \\
\Omega_2 &= ]0, R_2[ \\
\Omega_3 &= ]0, R_3[
\end{align*}
$$

$\Phi(x) = k_i$ sur $\Omega_i$.
l'état y vérifie alors l'équation aux dérivées partielles suivante :

$$M^2 \Delta y + (\mu k-1)y=0 \quad \text{sur } \Omega_1, ]R_1,b[, ]b,R_2[, \Omega_3$$

avec les conditions de transmission suivantes :

* continuité de y en $R_1$, $b$, $R_2$

* continuité de la dérivée normale $\frac{\partial y}{\partial n}$ en $R_1$, $R_2$.

* $\frac{\partial y}{\partial x}(b^{-}) - \frac{\partial y}{\partial x}(b^{+}) = -\frac{2}{\lambda} y(b)$

et les conditions au bord :

$$\frac{\partial y}{\partial n}(0) = 0$$

$$y(R_3) = 0.$$

Physiquement nous avons un réacteur à 3 zones, avec des enrichissements différents (coefficients $k_1$, $k_2$, $k_3$).

Il s'agit d'une réaction en chaîne, dont le bilan peut être écrit ainsi :

$$- D \Delta \Phi + \sum_a \Phi = V \sum_f \Phi + s$$

fuite absorption terme dû sources naturelles.
des neutrons à la fission

L'action des sources naturelles étant faible, on se place dans la situation critique, ce qui explique la formulation sous forme d'un problème aux valeurs propres.
■
## 2 - EXISTENCE DE L'ETAT DU SYSTEME

On introduit l'espace V

$$V = \{ y \mid y \in H^1(\Omega), y(R_3) = 0 \}$$

V muni du produit scalaire de $H^1(\Omega)$ est un espace de Hilbert. Soit $a(u,v)$ la forme bilinéaire définie sur $V \times V$ par :

$$(2.1) \qquad a(u,v) = \int_{\Omega} (M^2 \operatorname{grad} u \operatorname{grad} v + u \operatorname{grad} v \cdot v) d\Omega + \frac{2M^2}{\lambda} u(b)v(b)$$

$a(u,v)$ est une forme bilinéaire symétrique sur $V \times V$

- elle est continue, l'application de $V$ dans $\mathbb{R}$ qui à $u$ associe $u(b)$ étant continue.

- elle est coercive : $a(u,u) \geq \operatorname{Inf}(M^2,1) \quad \|u\|^2_v$.

Donc il existe un isomorphisme $A$ de $V$ sur $V'$ tel que $(Au,v)=a(u,v)$.

L'état du système est alors solution de :

$$(2.2) \qquad \begin{cases} Ay = \mu ky \\ y \ge 0 \end{cases}$$

avec $y(0)=1$.

On a l'équation variationnelle

$$(2.3) \qquad a(y,v) = \mu \int_{\Omega} k y v \quad \forall v \in V$$
Pour prouver l'existence d'un tel y, nous allons démontrer que l'opérateur $A^{-1}$ est hermitien, positif, compact de V' dans V. On pourra alors utiliser la théorie spectrale des opérateurs hermitiens compacts dans les espaces hilbertiens.

**Proposition 1**

$\Omega$ étant un ouvert borné, l'injection de V dans $L^2(\Omega)$ est compacte.

En effet l'injection de V dans $H^1(\Omega)$ est continue, l'injection de $H^1(\Omega)$ dans $L^2(\Omega)$ est compacte et l'injection de V dans $L^2(\Omega)$ est la composée de ces deux applications.

■

**Proposition 2**

$A^{-1}$ est un opérateur compact de V' dans V'

Considérons V' muni de la structure hilbertienne duale de V pour la norme de $H^1(\Omega)$.

$A^{-1}$ est une application linéaire continue de V' dans V alors $A^{-1}$ de V' dans V' est composée de :

- $A^{-1}$ de V' dans V continue,

- l'injection de V dans $L^2(\Omega)$ compacte,

- l'injection de $L^2(\Omega)$ dans V' continue,

ce qui démontre le résultat.

■
De plus $A^{-1}$ est hermitien, positif. Donc on peut appliquer la théorie spectrale des opérateurs hermitiens compacts dans les espaces de Hilbert. On a en particulier les propositions suivantes :

**Proposition 3** [RIESZ - FREDHOLM]

E étant un espace de Hilbert et $u$ un opérateur compact symétrique sur $\mathbb{R}$, alors $\Lambda$, ensemble des valeurs propres de $u$, est fini ou peut être rangé en une suite convergeant vers zéro.

En appliquant ce résultat à $A^{-1}$, on en déduit que $A$ admet bien une plus petite valeur propre positive.

**Proposition 4** [COURANT - HILBERT]

Si on considère l'équation $L y - \lambda \rho y = 0$ $\rho > 0$ sur $\Omega$ où $L$ est un opérateur auto-adjoint du 2ème ordre, avec des conditions homogènes sur le bord, alors dans l'ensemble des fonctions propres, la première fonction propre est caractérisée par le fait qu'elle ne s'annule pas sur $\Omega$.

On en déduit que le problème (2.2), avec la condition $||y||_L^2 = 1$ admet une solution.

Pour avoir l'existence d'une solution, avec $y(0) = 1$, il reste à démontrer que la solution définie précédemment ne s'annule pas en 0.
On sait que pour le problème

$$ egin{cases} -\frac{\partial}{\partial x}(a(x) \frac{\partial y}{\partial x}) + b(x)y = 0 \\ \frac{\partial y}{\partial n}(0) = 0 \\ y(1) = 0 \end{cases} $$

si $y(0)=0$ alors pour des coefficients analytiques ou réguliers par morceaux, $y = 0$.
**Théorème 1 :**

Le problème (2.2) avec $y(0) = 1$ admet une solution unique, cette solution est associée à la plus petite valeur propre de $A$.

On considère $z$ solution de (2.2) avec $\|z\|_{L^2(\Omega)}^2 = 1$ on a alors $y = \frac{z}{z(0)}$ et $\|y\|_{L^2(\Omega)}^2 = \frac{1}{|z(0)|^2}$. ■

**Théorème 2 :**

L'application de $E$ dans $V$ qui à $b$ associe $y_b$ solution de (2.2) avec $\|y_b\|_{L^2(\Omega)}^2 = 1$ est continue de $E$ dans $V$ faible.

Soit $\{b_n\}$ une suite convergente vers $b$ dans $E$

$y_n$ la solution de (2.2) associée à $b_n$, avec $\|y_n\|_{L^2(\Omega)}^2 = 1$.

D'après le théorème du Mini-max, $\mu_n$, peut être caractérisée par :

$$ \mu_n = \min_{y \in V} \frac{\int_{\Omega} (M^2 |\text{grad } y|^2 + |y|^2) d\Omega + \frac{2M^2}{\lambda} |y(b_n)|^2}{\int_{\Omega} k |y|^2 d\Omega} $$

comme $b_n \in E$ fermé, borné de R, on en déduit que :

$$ |\mu_n| \le M_1. $$

D'autre part on a :

$$ \int_{\Omega} (M^2 |\text{grad } y_n|^2 + |y_n|^2) d\Omega + \frac{2M^2}{\lambda} |y_n(b_n)|^2 = \mu_n \int_{\Omega} k |y_n|^2 d\Omega $$
On en déduit donc que :

$$ \| y_n \|_V^2 \le c. $$

On peut donc extraire deux sous-suites notées encore $y_n$ et $\mu_n$ telles que

$\mu_n \to \mu$ dans $\mathbb{R}$

$y_n \to y$ dans $V$ faible

on a donc $y_n(b_n) \to y(b)$

en effet

$$ |y_n(b_n) - y(b)| \le |y_n(b_n) - y_n(b)| + |y_n(b) - y(b)|. $$

L'application $y \to y(b)$ étant une forme linéaire et continue sur $V$, comme $y_n \to y$ dans $V$ faible, on a :

$$ y_n(b) \to y(b) $$

$$ \text{d'autre part} \quad |y_n(b_n) - y_n(b)| \le |b_n - b|^{1/2} \|y_n\|_V $$

$$ \text{comme } \|y_n\|_V \text{ est borné, on a } y_n(b_n) \to y_n(b). $$

$$ \text{Donc } y_n(b_n) \to y(b). $$

Or $y_n$ vérifie l'équation variationnelle suivante :

$$ \int_{\Omega} (M^2 \operatorname{grad} y_n + \operatorname{grad} \varphi + y_n \varphi) d\Omega + \frac{2M^2}{\lambda} y_n(b_n) \varphi(b_n) = \mu_n \int_{\Omega} k y_n \varphi d\Omega \quad \forall \varphi \in V. $$
En passant à la limite on obtient alors

$$
\begin{gather*}
\int_{\Omega} (M^2 \operatorname{grad} y + \operatorname{grad} \varphi + y\varphi) d\Omega + \frac{2M^2}{\lambda} \operatorname{y(b)} \varphi(b) = \mu \int_{\Omega} \operatorname{ky} \varphi \, d\Omega \\
\text{et de plus on a } \quad y \ge 0 \quad \text{et} \quad \|y\|_{L^2(\Omega)}^2 = 1.
\end{gather*}
$$

Donc $y$ est solution du problème (2.2).

<figure><img src="image_5.png" /></figure>

Corollaire 1

L'application de E dans $\mathbb{R}^+$ qui a b associé $y_b(o)$ est continue.

Corollaire 2

L'application qui a b associé $y_b$ avec $y_b(o) = 1$ est continue de E dans V faible.
### III - EXISTENCE D'UN CONTROLE OPTIMAL

#### Théorème 3

L'application qui à b associe $J(b)$ est continue de E dans $\mathbb{R}$.

L'injection de V dans $L^2(\Omega)$ étant compacte, du Corollaire 2, on déduit que l'application qui à b associe $y_b$ avec $y_b(0)=1$ est continue de E dans $L^2(\Omega)$ fort. Soit donc $\{b_n\}$ une suite tendant vers b dans E

alors $y_{b_n} \to y_b$ dans $L^2(\Omega)$ fort

et $\left|\bar{y}_b - \bar{y}_b\right| \le \frac{1}{m(\Omega)} \int_{\Omega} \left|y_b - \bar{y}_b\right| dm \le \|y_b - \bar{y}_b\|_{L^2(\Omega)}$

donc $\bar{y}_{b_n} \to \bar{y}_b$ dans $L^2(\Omega)$

or

$$ 
\begin{align*} 
J(b_n) - J(b) &= \int_{\Omega} \left[ (y_b - \bar{y}_b)_n^2 - (y_b - \bar{y}_b)^2 \right] x \, dx \\
&= \int_{\Omega} (y_b + y_b - \bar{y}_b - \bar{y}_b) (y_b - y_b - (\bar{y}_b - \bar{y}_b)) x \, dx \\
&\le m(\Omega) \quad \left\| y_{b_n} + y_b - \bar{y}_b - \bar{y}_b \right\|_V \left\| y_{b_n} - y_b - (\bar{y}_b - \bar{y}_b) \right\|_V \\
&\text{borné}
\end{align*} 
$$

et $\| y_b - y_b - (\bar{y}_b - \bar{y}_b) \|_V \le \| y_{b_n} - y_b \|_V + \| \bar{y}_{b_n} - \bar{y}_b \|_V m(\Omega)$.

Donc on en déduit que

$J(b_n) \to J(b)$

$b_n \to b$

<figure><img src="image_6.png" /></figure>
Théorème 4

Il existe au moins une solution au problème de contrôle (1.6).

Soit {$b_n$} une suite minimisante ($b_n \in E$)

$$
(3.1) \qquad J(b_n) \underset{b \in E}{\longrightarrow} \inf J(b)
$$

à $b_n$ on associe $\mu_n$, $y_n$, $z_n$ solution de 2-2) avec $\|z_n\|_{L^2(\Omega)}^2 = 1$
et $y_n(0) = 1$.

Comme pour le Théorème 2, on démontre que

$$
(3.2) \qquad | \mu_n | \le M_1
$$

$$
(3.3) \qquad \| z_n \|_V \le c_1
$$

or on sait que $z_n$ peut être pris tel que $z_n(o) > 0$ et que l'application qui
à b associé $z_b(o)$ est continue de E compact de $\mathbb{R}$ (fermé, borné) dans $\mathbb{R}$.
On en déduit que $z_b(o)$ reste borné lorsque b décrit E et que les bornes
sont atteintes. Donc en particulier, il existe $b_o \in E$ tel que
$$z_b(o) \ge z_{b_o}(o) = c_2 \quad \forall b \in E$$

$$
\text{donc} \quad \| y_n \|_{L^2(\Omega)}^2 = \frac{1}{|z_n(o)|^2} \le C
$$

et $\|y_n\|_V \le C_2$ indépendant de n.
Donc on peut extraire des sous-suites notées encore $\mu_n, b_n, y_n$ telles que

$$b_n \to \bar{b} \quad \text{dans } E$$

$$\mu_n \to \mu \quad \text{dans } \mathbb{R}^+$$

$$y_n \to y \quad \text{dans } V \text{ faible}$$

et comme au Théorème 2 on démontre que $y, \mu$ sont solutions du problème 2-2)
avec $y \ge 0$ et $y(0)=1$

D'autre part d'après le Théorème 3 on a

$$J(b_n) \to J(\bar{b})$$

et donc avec (3.1) on a $J(\bar{b})=\text{Min}_{b \in E} J(b)$

$\bar{b}$ est donc une solution du problème (1.6), y étant l'état du système associé.
IV - DETERMINATION FORMELLE D'UN ETAT ADJOINT POUR UN PROBLEME AUX VALEURS PROPRES.

On considère l'état du système $(y, \mu)$ défini par

$$
(4.1) \qquad \begin{cases} A(b) \quad y = \mu y. \\ y \ge 0; \quad y(0)=1 \end{cases}
$$

la fonctionnelle à minimiser s'écrivant :

$$
(4.2) \quad J(b) = \int_{\Omega} (y - \bar{y})^2 x \, dx.
$$

On introduit alors le Lagrangien suivant :

$$
(4.3) \quad L(y, \mu, v, p, \lambda, w) = \int_{\Omega} (y - \bar{y})^2 x \, dx + \int_{\Omega} [p, (A(b) - \mu I)y] \, d\Omega + \int_{\Omega} \lambda y \, d\Omega \\
\phantom{(4.3) \quad L(y, \mu, v, p, \lambda, w) =} + w(y(0) - 1) \qquad \text{avec } \lambda \le 0.
$$

Nous allons déduire formellement du Lagrangien, les conditions d'optimalité

$$
\left\{
\begin{array}{ll}
\displaystyle \frac{\partial L}{\partial y} \cdot z = 0 & \forall z \in V \\[1em]
\displaystyle \frac{\partial L}{\partial \mu} \cdot \eta = 0 & \forall \eta \ge 0
\end{array}
\right.
$$

ce qui donne, après simplifications, le système : (*)

$$
\left\{
\begin{array}{l}
2 \int_{\Omega} (y-\bar{y})z \, x \, dx + \int_{\Omega} [(A(b)-\mu I)^* p, z] \, d\Omega + \int_{\Omega} \lambda z \, d\Omega + w z(0) = 0 \quad \forall z \in V \\
\\
\eta \int_{\Omega} p \cdot y = 0
\end{array}
\right.
$$

en prenant $z=y$, on en déduit que $w=-2 < (y-\bar{y})x,y > - < \lambda, y >$

<footnote>\* en particulier le terme $\bar{z}$ disparaît.</footnote>
Nous avons donc pour déterminer $p$, le choix de $\lambda$ sachant qu'on doit avoir
$\lambda \le 0$ et $\int p y d\Omega = 0$.

D'après la Remarque 1 on peut faire un choix arbitraire de $\lambda$. On a été amené
alors à prendre :

$$
\lambda = - \frac{2y \int_{\Omega} (y-\bar{y})y \, x \, dx}{\int_{\Omega} |y|^2 \, dx}
$$

ce qui donne w=0

et on a bien $\lambda \le 0$, en effet

$$
y \ge 0 \text{ et comme } \left[ \int y \, dm \right]^2 \le m(\Omega) \int_{\Omega} y^2 \, dm
$$

on a

$$
\bar{y} \int y \, dm \le \int y^2 \, dm
$$

et donc
$$
\int (y - \bar{y}) y \, x \, dx \ge 0
$$

finalement l'état adjoint $p$ est défini par :

$$
(4.5) \qquad \left\{
\begin{array}{ll}
(A(b) - \mu I)^* p = -2 & \text{Proj}_{(y) \perp (y-\bar{y})} (y-\bar{y})x \\
p \in (y) \perp &
\end{array}
\right.
$$

ce système détermine de façon unique $p$.

en effet soient $p_1$ et $p_2$ deux solutions, on a :

$$
(A(b) - \mu I)^*(p_1 - p_2) = 0
$$

donc
$$
p_1 - p_2 = \lambda y \quad \text{or} \quad p_1 - p_2 \in (y)^{\perp}
$$
ce qui entraîne $p_1=p_2$.

**Remarque 1** : Dans ce cas, en effet quelque soit la détermination de l'état adjoint (choix de $\lambda$) on a bien l'unicité du gradient.

De façon générale, supposons le système défini par

$$ (1) \qquad F(y,v) = 0 $$

et la fonctionnelle à minimiser $J(v)$ avec $\tilde{J}(y(v),v) = J(v)$.

On suppose que (1) définit de façon unique $y(v)$ et d'autre part qu'on peut appliquer le théorème des fonctions implicites.

On a alors

$$ (2) \qquad \frac{\partial L}{\partial v} \cdot w = \frac{\partial \tilde{J}}{\partial v} \cdot w + \leq p, \frac{\partial F}{\partial v} \cdot w \geq J'(v) \cdot w $$

et d'autre part on a la condition :

$$ (3) \qquad \frac{\partial \tilde{J}}{\partial y} \cdot z + \leq p, \frac{\partial F}{\partial y} \cdot z \geq 0 \quad \forall z \in V. $$

Si on considère $p_1$ et $p_2$ deux états adjoints et $\bar{p}=p_1-p_2$,

$$ \text{on a d'après (3)} \quad \langle \bar{p}, \frac{\partial F}{\partial y} \cdot z \rangle = 0 \quad \forall z \in V. $$

D'autre part d'après le théorème des fonctions implicites à tout $z \in V$ on peut associer $w \in R$ tel que :

$$ \frac{\partial F}{\partial y} \cdot z + \frac{\partial F}{\partial v} \cdot w = 0 $$
on en déduit donc que :

$$ \langle \bar{P}, \frac{\partial F}{\partial v} \cdot w \rangle = 0 \quad \forall w \in \mathbb{R}, $$

donc le gradient est bien indépendant du choix de P.

La résolution du système (4.5) est réalisée de la façon suivante : [ cf. VAN DE WIELE ].

L'opérateur linéaire $A(b)-\mu I$ appliquant $(y)^\perp$ dans lui-même, p est solution du problème de minimisation suivant :

$$ (4.6) \qquad \min_{u \in (y)^\perp} \frac{1}{2} \left( \|(A(b) - \mu I)u, u\| + 2 \operatorname{Proj}_{L^2(\Omega)} (y - \hat{y})x, u \right) + \langle y, L^2(\Omega) \rangle. $$

On résout alors (4.6) par la méthode du gradient conjugué, en initialisant $u$ à un vecteur arbitraire de $(y)^\perp$. Au bout d'un nombre fini d'itérations, on obtient alors la solution.

Pour une étude détaillée de cette méthode de résolution, nous renvoyons à VAN DE WIELE [ 1 ].

L'état adjoint étant donc défini par (4.5), si l'opérateur $A(b)$ était différentiable, on aurait alors :

$$ (4.7) \qquad \operatorname{grad} J.h = \frac{\partial L}{\partial b} \cdot h = h \int_{\Omega} \left( \frac{\partial A}{\partial b} \cdot p, y \right) d\Omega. \quad \blacksquare $$

Pour une étude complète de ce problème, nous renvoyons à MIGNOT.
# 5 - DISCRETISATION DU PROBLEME

## 5-1) Discrétisation du système direct

Nous employons des éléments finis d'ordre 1. Soit donc $(w_i)_{i=1,...,m}$ la base d'éléments finis considérés. On a alors les matrices suivantes :

$$ (5.1) \qquad A_{ij} = \int_{\Omega} (M^2 \operatorname{grad} w_i \operatorname{grad} w_j + w_i w_j) + \frac{2M^2}{\lambda} w_i (b) w_j \quad (b) $$

$$ (5.2) \qquad B_{ij} = \int_{\Omega} k w_i w_j $$

on pose $\bar{A} = (A_{ij})$ ; $\bar{B} = (B_{ij})$.

$A, B$ sont deux matrices $nxn$, tridiagonales, symétriques, définies positives.

On cherche donc $y = \sum_{i=1}^{n} y_i w_i$, solution du système suivant :

$$ (5.3) \qquad \begin{cases} \bar{A}y = \mu \bar{B} y \\ \mu \text{ étant la plus petite valeur propre positive.} \end{cases} $$

La résolution numérique de (5.3) a été réalisée d'après une méthode mise au point par VAN DE WIELE [1].

N.B. $\mu$ est en fait la plus petite valeur propre de la matrice $B^{-1} A$ qui est définie, positive, symétrique.

## 5-2) Convergence de la solution du problème (5.3)

Soit $h$ le pas de discrétisation

$(\mu_h, y_h)$ la solution de (5.3) avec $\int_{\Omega} |y_h|^2 = 1$

$$ y_h = \sum_{i=1}^{n} y_h^i w_i $$
D'après le théorème du Mini-max, $\mu_n$ est définie par :

$$ (5.4) \qquad \mu_h = \min_n \sum_i y_i w_i \leq \begin{cases} \bar{\Delta}y, & y \leq \bar{\Delta}y \\ \bar{\bar{B}}y, & y \geq \bar{\bar{B}}y \end{cases} $$

si on prend pour $y$ le vecteur unité, par définition de $\bar{A}$ et $\bar{B}$ on trouve

$$ \bar{\Delta}y, y > = K \quad \text{constante indépendante de h.} $$

$$ (5.5) \qquad \text{donc } \mu_h \text{ est bornée} \qquad |\mu_h| \le K. $$

D'autre part, de (5.3) on obtient :

$$ a(y_h, y_h) = \mu_h \int_{\Omega} k |y_h|^2 d\Omega $$

comme on a $||y_h||_L^2 = 1$ on en déduit que

$$ (5.6) \qquad \| y_h \|_V^2 \le C $$

de (5.5) et (5.6) on déduit qu'il existe deux sous-suites, notées encore $\mu_h$ et $y_h$ telles que :

$$ (5.7) \qquad \left\{ \begin{array}{r@{\quad}c@{\quad}l@{\quad}l} \mu_h & \longrightarrow & \mu & \text{dans } \mathbb{R}^+ \\ y_h & \longrightarrow & y & \text{dans } V \text{ faible} \end{array} \right. $$

or on a

$$ (5.8) \qquad a(y_h, v) = \mu_h \int_{\Omega} k y_h v \quad \forall v \in V_h \quad \text{sous-espace engendré par} \\ \qquad \qquad [w_1, \dots, w_n] $$
par passage à la limite, grâce à (5.7), on obtient

$$a(y, w_i) = \mu \int_{\Omega} k y w_i \quad \forall w_i$$

or comme les combinaisons linéaires finies des $w_i$ sont denses dans $V$ on obtient

$$(5.9) \qquad a(y,v) = \mu \int_{\Omega} k y v \quad \forall v \in V$$
avec toujours $$ \| y \|_{L^2(\Omega)} = 1.$$

Montrons maintenant que $\mu$ est la plus petite valeur propre associée à (5.9) on a d'après (5.4)

$$ \mu_h = \min_{y \in V_h} \frac{a(y,y)}{\int_{\Omega} k y^2} \quad \text{et ce minimum est atteint pour } y_h $$

$$ \text{soit} \qquad \mu^* = \min_{y \in V} \frac{a(y,y)}{\int ky^2} \quad \text{ce minimum étant atteint pour } y^* $$
avec $$ \|y^*\|_{L^2(\Omega)} = 1. $$

$$ \text{on a alors} \qquad \mu^* \le \mu_h \qquad \text{car } V_h \subset V. $$

D'autre part comme $(U \subset V)$ est dense dans $V$, il existe une suite $(y_h^*)$, $y_h^* \in V$, tel que $y_h^*$ tende vers $y^*$ dans $V$ avec $\|y_h^*\|_{L^2(\Omega)} = 1$.

On a alors :

$$ \mu^* \le \mu_h \le \frac{a(y_h^*, y_h^*)}{\int_{\Omega} k |y_h^*|^2} $$
en passant à la limite, on obtient alors $\mu^* = \mu$

$\mu$ est atteint pour $y^*$ et $y$, chacun de norme $L^2$ égale à 1, d'après l'unicité de la solution on en déduit que $y^*=y$

($\mu,y$) sont donc solutions du système direct. On a alors le résultat suivant:

**Théorème 5 :**

La solution du problème discrétisé ($y_h, \mu_h$) converge vers la solution du problème continu ($y, \mu$), avec $\|y\|_2 = 1$

$y_h \to y$ dans $L^2(\Omega)$ fort et V faible
$\mu_h \to \mu$ dans $\mathbb{R}^+$. ■

On en déduit en particulier que pour h suffisamment petit, $y_h$ a toutes ses composantes positives.

$y$ étant solution du problème (5.3) on a

$$y_h(o) \neq 0 \quad \text{sinon} \quad y_h = 0$$

On peut donc bien définir la solution $y_h$ telle que $y_h(o) = 1$.

Par la suite on notera $y_h$ la solution telle que $y_h(o) = 1$
et $z_h$ la solution telle que $\|z_h\|_{L^2(\Omega)}^2 = 1$

$$\text{donc } y_h = \frac{z_h}{z_h(o)}.$$

On a un théorème de convergence analogue au théorème 5.
### 5-3) Existence d'un contrôle optimal discrétisé

Soit $J_h$ la fonctionnelle discrétisée on a :

$$J_h(b) = \int_{\Omega} \left[ \sum_{i=1}^{n} y_i v_i(x) \right]^2 x \, dx$$

$$\text{avec} \qquad v_i(x) = w_i(x) - \frac{2}{(R_3^*)^2} \int_{\Omega} w_i(x) x \, dx$$

$$\text{soient} \qquad a_{ij} = \int_{\Omega} v_i(x) v_j(x) x \, dx \quad \text{et} \quad a = (a_{ij})$$

on a donc

$$(5.10) \qquad J_h(b) = \int_{\Omega} y_i y_j \, a$$

### Théorème 6

L'application qui a $b \in E$ associe $(y_h) \in \mathbb{R}^n$ solution de (5.3),
$y_h = \sum_i y_{i,h} \underline{w}_i$, est continue.

Soit $\{b_n\}$ une suite convergente vers $b$ dans $E$, $(z_n, \mu_n)$ la solution de (5.3) associée à $b_n$.

Pour n suffisamment grand, $b_n$ et $b$ appartiennent au même intervalle de discrétisation, et vu la forme de la matrice $\bar{A}_n$, on en déduit que $\bar{A}_n$ est uniformément continue en b.

D'autre part comme $\|z_n\|_L^2 = 1$, $z_n$ est borné dans $\mathbb{R}^n$.

$$(5.11) \quad \text{De plus} \quad \underline{b}_n = \min_{y \in V_h} \frac{\langle \bar{A}_n y, y \rangle}{\langle \bar{b}_n y, y \rangle} \quad \text{est borné dans } \mathbb{R}^+$$
on peut donc extraire deux sous-suites telles que :

$$
(5.12) \quad \left\{
\begin{array}{l}
\mu_n \xrightarrow{\quad} \mu \quad \text{dans } \mathbb{R}^+ \\[1ex]
z_n \xrightarrow{\quad} z \quad \text{dans } \mathbb{R}^n
\end{array}
\right.
$$

on a donc aussi $z_n(o) \to z(o)$.

Or, comme l'application qui a $b_n$ associé $z_n(o)$ est continue et que $b_n \in E$
compact de $\mathbb{R}$, $z_n(o)$ est borné lorsque b décrit E et ses bornes sont
atteintes donc en particulier il existe $b_o$ tel que :

$$
z_n(o) \geq z_o(o) \quad \forall b_n \in E
$$

de (5.12) on déduit que $y_n$ est borné dans $\mathbb{R}_n$ et donc

$$
y_n \rightarrow y \text{ dans } \mathbb{R}^n
$$

et on a bien

$$
y(o) = 1
$$

or $\bar{A}_n y_n = \mu_n \bar{B} y_n,$

par passage à la limite on obtient :

$$
\bar{A}y = \mu \bar{B} y
$$

de plus, d'après (5.11) et comme $\bar{A}_n$ est uniformément continue en $b$, $\mu$ est
la plus petite valeur propre.

<figure><img src="image_7.png" /></figure>
Corollaire :

L'application de E dans $\mathbb{R}$ qui à b associe $\displaystyle\int_h J(b)$ est continue.

Théorème 7

Le problème de contrôle discrétisé admet une solution.

Soit $\{b_n\}$ une suite minimisante

$$J_h(b_n) \longrightarrow \underset{b \in E}{\operatorname{Min}} J_h(b)$$

on démontre comme précédemment que $y_n, \mu_n$ solutions associées à $b_n$ sont bornées respectivement dans $\mathbb{R}^n$ et $\mathbb{R}^+$.

On en déduit qu'il existe deux sous-suites $y_n, \mu_n$ telles que :

$$y_n \longrightarrow y \text{ dans } \mathbb{R}^n$$

$$\mu_n \longrightarrow \mu \text{ dans } \mathbb{R}^+$$

avec $(y_n, \mu_n)$ solution de (5.3)

et d'après la continuité de $J_h$ en b on obtient :

$$J_h(b) = \underset{b \in E}{\operatorname{Min}} J_h(b) \quad \text{ce qui démontre le résultat.}$$

5-4) Convergence du contrôle discrétisé $b_h$

Soit $(b_h, y_h, \mu_h)$ la solution du problème discrétisé.

$b_h \in E$ fermé borné de $\Omega$
soit $z_h = \frac{y_h}{\|y_h\|_{L^2}}$, on a toujours

$$a_h(z_h, z_h) = \mu_h \int_{\Omega} k |z_h|^2 d\Omega.$$

$$\mu_h = \min_{y \in V_h} \frac{a_h(y,y)}{\int_{\Omega} k |y|^2}$$

on en déduit donc encore que :

$$\left\{ \begin{array}{l} \mu_h \text{ est borné dans } \mathbb{R}^+ \text{ (même raisonnement qu'au 5.2)} \\ z_h \text{ est borné dans } V \text{ car } \alpha \|z_h\|_V^2 \le a_h(z_h, z_h). \end{array} \right.$$

On peut donc extraire des sous-suites telles que :

$$\begin{array}{rcl@{\quad}l} \text{(5.13)} & \left. \begin{array}{l} b_h \longrightarrow b \\ \mu_h \longrightarrow \mu \end{array} \right\} & \text{dans } E & \\ & \left. \begin{array}{l} \mu_h \longrightarrow \mu \\ z_h \longrightarrow z \end{array} \right\} & \text{dans } \mathbb{R}^+ & \\ & \text{dans } V & \text{faible et } L^2 \text{ fort.} & \end{array}$$

on a d'autre part

$$a_h(z_h, v) = \mu_h \int k z_h v \quad \forall v \in V_h$$

avec

$$a_h(z_h, v) = \int_{\Omega} (M^2 \operatorname{grad} z_h + \operatorname{grad} v + z_h v) + \frac{2M^2}{\lambda} z_h (b_h) v (b_h).$$

Donc en passant à la limite on a :

$$a(z,v) = \mu \int_{\Omega} k z_v \quad \forall v \in (U V_h) \text{ h}$$
par densité on en déduit :

$$a(z,v) = \mu \int_{\Omega} k z v \quad \forall v \in V$$

$$\text{on a} \qquad \mu_h = \min_{y \in V_h} \frac{a_h(y,y)}{\int_{\Omega} k |y|^2} = \frac{a_h(z_h, z_h)}{\int_{\Omega} k |z_h|^2}$$

par passage à la limite on a :

$$\mu = \int_{\Omega} \frac{a(z,z)}{k |z|^2} \quad \text{avec} \quad \|z\|_L^2 = 1$$

$$\text{soit} \quad \mu^* = \min_{y \in V} \int_{\Omega} \frac{a(y,y)}{k y^2} \quad , \text{minimum atteint pour } z^* \quad \text{avec} \quad \|z^*\|_L^2 = 1$$

$$\text{on a} \qquad \mu^* \le \mu$$

comme $(\mu_h V_h)$ est dense dans V, il existe une suite $z_h^* \in V_h$ tendant vers $z^*$ dans V

$$\text{et on a} \qquad \mu_h \le \frac{a_h(z_h^*, z_h^*)}{\int_{\Omega} |z_h^*|^2}$$

par passage à la limite on obtient $\mu \le \mu^*$.

Donc $\mu = \mu^*$ et d'après l'unicité de la solution $z=z^*$, $(\mu, z)$ sont solutions du problème continu.

de plus on a donc $z_h(o) \to z(o)$ et comme $z(o) \ne 0$ on en déduit que $y_h \to y$ dans V faible avec $y(o)=1$.

Donc $(\mu_h, y_h) \to (\mu, y)$ solution du problème continu.

$$\text{or} \qquad \bar{y}_h = \frac{2}{(R_3)^2} \int_{\Omega} y_h(x) dx \to \frac{2}{(R_3)^2} \int_{\Omega} y(x) dx = \bar{y}.$$
car $y_h \rightarrow y$ dans $L^2$ fort, d'après la compacité de l'injection de $V$ dans $L^2(\Omega)$.

On en déduit que

$$J_h(b_h) = \int_{\Omega} (y_h - \tilde{y}_h)^2 \times dx \rightarrow J(b)$$

d'autre part $J_h(b) \rightarrow J(b)$.

Donc comme on a $0 \le J_h(b_h) \le J_h(\tilde{b})$ et $\tilde{b} \in E$

par passage à la limite on obtient :

$$J(b) \le J(\tilde{b}) \quad \tilde{b} \in E$$

$b$ est donc un contrôle optimal du problème continu. On a le résultat suivant :

**Théorème 3**

Une solution $(b_h, y_h, \mu_h)$ du problème de contrôle discrétisé, converge vers une solution $(b, y, \mu)$ du problème continu.

$b_h \rightarrow b$ dans $E$

$\mu_h \rightarrow \mu$ dans $\mathbb{R}^+$

$y_h \rightarrow y$ dans $V$ faible

$y_h \rightarrow y$ dans $L^2(\Omega)$ fort. ■

### 5-5) Détermination d'un adjoint du discrétisé

Pour $h$ suffisamment petit, on a vu que le système discrétisé peut s'écrire

$$ \begin{cases} \bar{A}y = \mu \bar{B} y \\ y \ge 0, \quad y_1=1 \end{cases} \quad y_1 \text{ correspondant à } y(0). $$
On introduit alors le Lagrangien suivant :

$$
\begin{gather*}
\mathcal{L}(y, \mu, \phi, \lambda) = \left[ \sum_{i} y_i v_i(x) \right]^2 \times \mathrm{d}x + \int (p, (\bar{A} - \mu\bar{B})y) \, \mathrm{d}R^n + \sum_i \lambda_i y_i + w(y_1^{-1}) \\
\text{avec } \lambda_i \le 0
\end{gather*}
$$

on a alors

$$
\left\{
\begin{array}{ll}
\displaystyle \frac{\partial l}{\partial y_i} \cdot z_i = 2 \int_{\Omega} z_i v_i(x) \left( \sum_{j=1}^{R} y_j v_j(x) \right) \times \mathrm{d}x + p_i \sum_{j} (A_{ij} - \mu B_{ij}) z_j \\
\displaystyle \qquad + \lambda_i z_i + w z_1 \delta_i^1 = 0 \quad \forall z_i \neq 0 & \lambda_i \neq 0 \\[1em]
\displaystyle \frac{\partial L}{\partial \mu} \cdot h = h(p, By) \quad \mathbb{R}^n = 0 & \delta_i^j \text{ symbole de Kronecker}
\end{array}
\right.
$$

(P, λ) doivent donc vérifier :

$$
\left\{
\begin{array}{l}
(\bar{A} - \mu \bar{B}) P = -ay - \lambda - w \delta_i^1 \\[1em]
(P, \bar{B}y) \mathbb{R}^n = 0 \quad \text{avec } \lambda < 0
\end{array}
\right.
$$

or $((\bar{A}-\mu\bar{B})\underline{p}, y) \in \mathbb{R}^n = 0$ ce qui permet de déterminer $w$

$$
w = -(ay+\lambda,y) \mathbb{R}^n
$$

pour $\lambda$ on peut alors choisir :

$$
\lambda = - \frac{(ay, y) \mathbb{R}^n y}{(y, y) \mathbb{R}^n} \quad \text{cf. \textit{Remarque 1}}
$$
l'adjoint du discrétisé est donc donné par :

$$
\left\{
\begin{array}{l}
(\bar{A}-\mu\bar{B})p = -ay + \displaystyle\frac{y(ay,y)\mathbb{R}^n}{(y,y)\mathbb{R}^n} \\[1em]
(P,By)_{\mathbb{R}^n} = 0
\end{array}
\right.
$$

le gradient de Jₕ(b) est alors :

$$
J'(b) = \left( p, \frac{\partial \bar{A}}{\partial b} y \right)_{\mathbb{R}^n}
$$

avec $\frac{\partial \bar{A}}{\partial b}$ la matrice de terme général $\frac{\partial}{\partial x_i} (w_i w_j)_{(b)}$.

■
# 6 - RESULTATS NUMERIQUES

Données :

R₁ = 0,80 m
k₁ = 1

R₂ = 1,13 m
k₂ = 1,2

R₃ = 1,38 m
k₃ = 1,2

$$M^2 = 50 \text{ cm}^2$$

Il y a deux types de barres, correspondant à λ = 1 m et λ = 0,50 m.

Pour le positionnement de plusieurs barres on emploie une méthode de relaxation barre par barre.

On obtient les résultats suivants :

## - Positionnement d'une barre

λ = 0,5 m
b = 1,022

λ = 1 m
b = 1,027

## - Positionnement de deux barres

λ = 0,5 m
b₁ = 0,915
b₂ = 1,057

λ = 1 m
b₁ = 0,982
b₂ = 1,049

## - Positionnement de trois barres

λ = 0,5
b₁ = 0,899
b₂ = 0,962
b₃ = 1,078

## - Positionnement de quatre barres

λ = 0,5 m
b₁ = 0,810
b₂ = 0,891
b₃ = 0,989
b₄ = 1,054.
Ces résultats semblent correspondre aux phénomènes physiques observés.
En particulier pour le cas de quatre barres, qui correspond à une distribution
de flux acceptable pour le fonctionnement du réacteur, les quatre couronnes
absorbantes étant réparties de manière régulière.

=§=§=§=§=§=§=§=
Etat du système sans barre

<figure><img src="image_8.png" /></figure>

J=65,1609

μ=0,9041
Positionnement d'une barre

Données

λ =0,5
M²=0,005
k₁=1
k₂=1,2
k₃=1,2

<figure><img src="image_9.png" /></figure>
Positionnement d'une barre

<figure><img src="image_10.png" /></figure>

Données

λ=1
M²=0,005
k₁=1
k₂=1,2
k₃=1,2

Initialisations

b=1,10
J=26,898
μ=0,9197

b=1,027
J=23,194
μ=0,9233
Positionnement de deux barres

Données

$\lambda=0,5$

$M^2=0,005$

$k_1=1$

$k_2=1,2$

$k_3=1,2$

15

10

5

<figure><img src="image_11.png" /></figure>
Positionnement de deux barres

Données

λ=1
M²=0,005
k₁=1
k₂=1,2
k₃=1,2

<figure><img src="image_12.png" /></figure>

15

10

5
Positionnement de trois barres

Données

λ=0,5
M²=0,005
k₁=1
k₂=1,2
k₃=1,2

15

10

5

<figure><img src="image_13.png" /></figure>
Positionnement de quatre barres

Données

$\lambda=0,5$

$M^2=0,005$

$k_1=1$

$k_2=1,2$

$k_3=1,2$

15.

10

5

<figure><img src="image_14.png" /></figure>
# CHAPITRE II

## PROBLEMES EN VARIABLES BOOLEENNES

### APPLICATION AU CONTROLE
POSITION DU PROBLEME

D'une façon générale, le contrôle d'un système représente l'action que l'on a sur certaines de ses parties : par exemple dans un réseau de transport d'eau, de gaz, d'électricité etc..., le contrôle s'exerce sur les pompes, les compresseurs, les alternateurs, etc... Dans de nombreux cas ces machines ne peuvent fonctionner qu'à un nombre fini de régimes (par exemple 0%, 60%, 100% de leur puissance maximale). On se trouve donc confronté au problème de choisir au cours du temps les meilleurs régimes afin d'obtenir, par exemple, le plus grand débit à la sortie, compte tenu des contraintes techniques, auxquelles est soumis le système. En particulier nous devons déterminer les instants de commutation entre les différents régimes. Nous avons donc un problème où la variable de contrôle, fonction du temps, ne peut prendre ses valeurs, à chaque instant, que dans un ensemble discret fini.

Afin d'étudier mathématiquement et numériquement un exemple de ce type,
nous avons pris le système suivant :

L'état $y(x,t)$ du système est solution de l'équation aux dérivées partielles :

$$
\left\{
\begin{array}{l}
\displaystyle \frac{\partial y}{\partial t} - \frac{\partial^2 y}{\partial x^2} = g(x,t) + B v(t) \quad \text{sur un ouvert } \Omega \text{ de } \mathbb{R}^n \text{ de frontière } \Gamma \\[1em]
\text{ydrodynamique :} \\
\displaystyle y|_{\Gamma^-} = 0 \qquad \Sigma = \Gamma x ]0,T[
\end{array}
\right.
\\
y(x,0) = y_0(x),
$$

$v(t)$, représentant le contrôle, est une fonction constante par morceaux,
$y$ est fonction de $v(t)$ et on cherche à déterminer le contrôle optimal
$v^*(t)$ qui minimise la fonctionnelle :

$$
\int_{\Omega} \int_{0}^{T} |y(x,t,v) - z_{d}(x,t)|^{2} dx dt ; z_{d}(x,t) \text{ étant une fonction donnée.}
$$
Le traitement théorique et numérique d'un tel système est l'objet
du présent chapitre. Parmi les nombreuses approches possibles d'un tel problème
nous en avons retenu deux. Une première méthode consiste à appliquer la
théorie classique du contrôle. Une autre solution consiste à se ramener à un
problème en variables entières et dans ce cadre nous développons des
algorithmes de résolution des problèmes quadratiques en variables booléennes.
Tout d'abord formulons mathématiquement le problème précis que nous venons de donner.

# I - ETUDE DU CAS PARABOLIQUE, FORMULATION MATHEMATIQUE.

Soient $V$ et $H$ deux espaces de Hilbert

$V \subset H$ avec injection continue et densité

on identifie $H$ à son dual $H'$, donc $V \subset H \subset V'$

$t$ désigne le temps, on prend $t \in ]0,T[$. $T$ fini.

Soit $a(t;\varphi,\psi)$ une famille de formes bilinéaires continues sur $V$ telles

$$ (1.1) \qquad \left\{ \begin{array}{ll} \forall \varphi, \psi \in V & \text{t} \longrightarrow a(t;\varphi,\psi) \text{ est mesurable sur } ]0,T[ \text{ et} \\ |a(t;\varphi,\psi)| \le C ||\varphi||_V ||\psi||_V & \end{array} \right. $$

$$ (1.2) \qquad \text{Il existe } \lambda \text{ tel que} $$

$$ a(t;\varphi,\varphi) + \lambda |\varphi|_H^2 \ge \alpha ||\varphi||_V^2 \qquad \alpha > 0 \qquad \forall \varphi \in V \\ t \in ]0,T[ $$

on écrit alors :

$$ a(t;\varphi,\psi) = (A(t)\varphi,\psi) \\ \qquad \xrightarrow{V' \to V} $$

$$ \text{avec } A(t) \in \mathcal{L} (L^2(0,T;V), L^2(0,T;V')). $$

$$ \text{On définit l'opérateur } B \in \mathcal{L} (U, L^2(0,T;V)). $$
u désignant l'espace des contrôles, qui sera précisé plus loin, l'état y
du système est alors solution du problème

$$
\begin{equation} \tag{1.3}
\left\{
\begin{array}{l}
\displaystyle \frac{dy}{dt} + Ay = f + Bu \\[1em]
(1.4) \qquad y(x,0) = y_o(x)
\end{array}
\right.
\end{equation}
$$

D'après LIONS [1] , sous les conditions (1.1) et (1.2), le système (1.3), (1.4)
admet une solution unique dans W(O,T)

$$
W(O,T) = \{ f \mid f \in L^2(O,T;V), \frac{df}{dt} \in L^2(O,T;V') \}
$$

d'autre part, cette solution dépend continûment de u.

Soit I un ensemble discret, fini $I=\{i_1, \dots, i_n\}$.

On définit l'ensemble u des contrôles, comme l'ensemble des classes des fonctions de L²(O,T), constantes par morceaux sur une partition finie de l'intervalle [0,T], prenant ces valeurs dans l'ensemble I.

On note S(u) le nombre d'éléments de la partition (1.7).

On définit la fonctionnelle suivante :

$$
(1.5) \qquad J(u) = \int_0^T \int_\Omega |y-z_d|^2 \, dx \, dt + v \int_0^T |u(t)|^2 \, dt + K \, S(u) \\
\qquad \qquad \text{pour } u \in \mathcal{U}.
$$

On considère alors le problème de contrôle suivant :

$$
\[
\left\{
\begin{array}{ll}
\text{Trouver } \bar{u} \in \mathcal{U} \text{ tel que} & \\
\text{J}(\bar{u}) = \text{Min } J(u) & \\
\mathcal{U} \in \mathcal{U} &
\end{array}
\right.
\]
$$
Remarque :

On peut transformer le problème (1.6) en la recherche de n contrôles

$$
\begin{array}{l}
\alpha_i(t), \dots, \alpha_n^i(t) \text{ avec } \alpha_i(t) \in \tilde{I} = \{0,1\} \quad \forall t \in ]0,T[ \\
\text{et } \sum_{i=1}^n \alpha_i(t) = 1.
\end{array}
$$

Donc par la suite au lieu d'étudier (1.6), nous considérons le problème
suivant :

$$
\begin{array}{lll}
\text{Trouver} & \bar{u} \in \mathcal{U} & \text{tel que} \\
(1.8) \qquad \qquad \qquad \qquad J(\bar{u}) = \min_{u \in \mathcal{U}} & J(u) & \text{avec} \\
& u = \{u | u(t) \in \{0,1\} \ \forall t \in ]0,T[\}. &
\end{array}
$$
## 2 - EXISTENCE D'UN CONTROLE OPTIMAL

Ecrivons : $J(u) = J_1(u) + K S(u)$.

Soit $u_n$ une suite minimisante de $J(u)$

$$J(u_n) \underset{u \in u}{\longrightarrow} \inf J(u).$$

- Nous avons $K S(u) \leq J(u)$, donc il existe une sous-suite, notée encore $u_n$, tel que $S(u_n)$ soit borné.

- $u_n(t) \in u$, donc ne peut prendre que les valeurs 0 ou 1. On en déduit : $\|u_n(t)\|_{L^2(0,T)}^2$ borné.

Grâce à ces deux estimations, nous pouvons extraire une sous-suite telle que :

$$ (2.1) \qquad S(u_n) = N \qquad N \text{ fixé} $$

$$ (2.2) \qquad u_n \underset{u}{\longrightarrow} u \qquad \text{dans } L^2(0,T) \text{ faible.} $$

D'après (2.1) $u_n$ peut s'écrire :

$$ u_n = \sum_{i=1}^{N-1} b_i^n \chi_{[a_i^n, a_{i+1}^n]} \quad \text{avec} $$

$\chi_{[\alpha, \beta]}$ fonction caractéristique de l'intervalle $[\alpha, \beta]$, $b_i^n \in \{0, 1\}; a_i^n \in ]0, T[$ on a alors

- $0 \le a_i^n \le T$ donc borné dans $\mathbb{R}$

- $b_i^n$ qui ne peut prendre que deux valeurs 0 ou 1.
Donc on peut extraire deux sous-suites telles que :

$$a_i^n \to a_i^* \quad \text{sur } (0,T)$$

$$b_i^n = b_i^*$$

On en déduit que :

$$u_n \xrightarrow[\sum_{i=1}^N]{N-1} b_i^* \quad \chi_{[a_i^n, a_{i+1}^*]} \quad \text{dans } L^2(0,T) \text{ faible.}$$

Finalement nous avons donc pu extraire une sous-suite vérifiant les trois propriétés suivantes :

$$S(u_n) = N$$

$$u_n \to u \quad \text{dans } L^2(0,T) \text{ faible}$$

$$u_n = \sum_{i=1}^{N-1} b_i^n \quad \chi_{[a_i^n, a_{i+1}^*]}$$

$$\text{et } a_i^n \to a_i^* \quad \text{dans } [0,T]$$

$$b_i^n = b_i^*$$

Alors d'après l'unicité de la limite faible, on en déduit que :

$$u = \sum_{i=1}^{N-1} b_i^* \chi_{[a_i^*, a_{i+1}^*]}$$

$$\text{et donc } u_n \to u \text{ dans } \mathcal{U} \text{ faible.}$$

D'autre part avec les hypothèses précédentes, on a $S(u) \le N$.

Donc $J(u_n) = J_1(u_n) + K N$.
or comme $J_1$ est faiblement continue, on en déduit

$$ \underline{\lim} \ J(u_n) \geq J_1(u) + KN \geq J_1(u) + S(u) = J(u). $$

$u_n$ étant une suite minimisante, on a donc

$$ J(u) = \inf_{\tilde{u} \in U} \tilde{J}(u) $$

ce qui montre que $u$ est un contrôle optimal.

On a donc le résultat suivant :

Le problème (1.7) admet au moins une solution.
### 3 - AUTRE DEMONSTRATION DE L'EXISTENCE D'UN CONTROLE OPTIMAL, PAR UNE METHODE IMPLEMENTABLE NUMERIQUEMENT.

1) s'il existe un contrôle optimal $\bar{u} \in \mathcal{U}$; alors $S(\bar{u})$ est fini.
En effet, on a

$$J(\bar{u}) \le J(o) \quad \text{et} \quad J(o) \quad \text{fini}$$

$$\text{Comme } K S(\bar{u}) \le J(o).$$

On a

$$(3.1) \qquad S(\bar{u}) \le E \left( \frac{J(o)}{K} \right) = N_o.$$

$E(x)$ désignant la partie entière de $x$.

Pour montrer l'existence d'un contrôle optimal au problème (1.7), il suffit
donc d'étudier les sous-problèmes, définis pour $S(u) = N$ avec $N=0,1,\dots,N_o$.

On est donc amené à définir les problèmes suivants :

2) N étant fixé ($0 < N < N_o$).

Soit $\chi_{[a_i, b_i]}$ la fonction caractéristique de l'intervalle $[a_i, b_i]$.
on prend alors $u$ sous la forme $u = \sum_{i=1}^{N} \chi_{[a_i, b_i]}$.

$\{ (a_i, b_i) = i=1, \dots, N \}$ seront les nouvelles variables de contrôle.

On considère alors l'équation d'état du système :

$$(3.2) \qquad \left\{ \begin{array}{l} \displaystyle \frac{\partial y}{\partial t} + Ay = f + B \left( \sum_{i=1}^{N} \chi_{[a_i, b_i]} \right) \\[1em] (3.3) \qquad \qquad \qquad \qquad \qquad \qquad y(x,o) = y_o(x). \end{array} \right.$$
On introduit l'ensemble des contrôles admissibles $K(N) \subset \mathbb{R}^{2N}$.

$$ (3.4) \qquad \begin{cases} 0 \le a_i \le T ; & 0 \le b_i \le T \\ a_i < b_i < a_{i+1} < b_{i+1} & \forall i = 1, \dots, N-1. \end{cases} $$

$K(N)$ est un convexe borné de $\mathbb{R}^{2N}$.

Notons $(a,b) = \{ (a_i, b_i) \mid i=1, \dots, N \} \in \mathbb{R}^{2N}$.

Soit $u_{ad}^{(N)} = \{ u \in L^2(0,T) \mid u = \sum_{i=1}^{N} \chi_{[a_i, b_i]} , (a,b) \in K(N) \}$

on considère la fonctionnelle :

$$ (3.5) \qquad \tilde{J}(a,b) = \int_0^T \int_\Omega |y-z_d|^2 dx dt + \nu \int_0^T |u(t)|^2 dt. $$

On prend alors le problème de contrôle suivant :

$$ (3.6) \qquad \begin{cases} \text{Trouver } (\bar{a}, \bar{b}) \in K(N) \text{ tel que} \\ \tilde{J}(\bar{a}, \bar{b}) = \text{Min} \ \tilde{J}(a, b) \\ (a, b) \in K(N). \end{cases} $$

Soit $P_N$ ce problème.

3) on considère le problème $\tilde{P}_N$ transformé de $P_N$, en remplacant $K(N)$ par son adhérence $\overline{K(N)}$.

$$ \text{Soit } \begin{cases} 0 \le a_i \le T ; & 0 \le b_i \le T \\ a_i \le b_i \le a_{i+1} \le b_{i+1} \end{cases} $$

$\tilde{P}_N$ admet au moins une solution.
En effet :

- 1'application qui à (a,b) associe $u = \sum_{i=1}^{N} \chi_{[a_i, b_i]}$ est continue de $\mathbb{R}^{2N}$ dans $L^2(0,T)$ fort.

- 1'application qui à u associe y solution de (1.3), (1.4) étant continue de $L^2(0,T)$ dans $W(0,T)$, on en déduit que $\tilde{J}(a,b)$ est continue sur $\overline{K(N)}$.

De plus $\overline{K(N)}$ est un fermé, borné de $\mathbb{R}^{2N}$, ce qui donne l'existence d'un contrôle optimal pour $\tilde{p}_N$.

4) Soit $\tilde{u}_N$ un contrôle optimal du problème $\tilde{p}_N$, donc il existe $(\tilde{a}, \tilde{b}) \in \overline{K(N)}$ tel que :

$$ \tilde{u}_N = \sum_{i=1}^{N} \chi_{[\tilde{a}_i, \tilde{b}_i]} $$

**Lemme** : si $\tilde{u}_N \in u_{ad}(N)$, alors il existe $N' < N$ tel que

$$ \tilde{u}_N \in u_{ad}(N'). $$

**Démonstration** : si $\tilde{u}_N \in u_{ad}(N)$, alors $(\tilde{a}, \tilde{b}) \in K(N)$

donc il existe au moins un $i_o$ tel que :

$$ \tilde{a}_{i_o} = \tilde{b}_{i_o} $$

ou

$$ \tilde{b}_{i_o} = \tilde{a}_{i_o+1} $$

Alors une des deux familles

$$ (\tilde{a}_0, \tilde{b}_0, \dots; \tilde{a}_{i_0-1}, \tilde{b}_{i_0-1}; \tilde{a}_{i_0+1}, \tilde{b}_{i_0+1}, \dots; \tilde{b}_N) $$

$$ (\tilde{a}_0, \tilde{b}_0, \dots; \tilde{a}_{i_0}, \tilde{b}_{i_0+1}, \dots; \tilde{b}_N) $$
appartenant à $\overline{K(\overline{N}-1)}$ définit une partition associée à $\tilde{u}_N$ et donc $\tilde{u}_N \in u_{ad}(N')$ avec $N' < N$.

D'après (1.7) on a d'autre part :

$$S(\tilde{u}_N) \le N$$

Montrons que si $\tilde{u}_N \notin u_{ad}(N)$, alors il existe $N' < N$ tel que :

$$(3.7) \qquad J(\tilde{u}_{N'}) \le J(u) \quad \forall u \in u_{ad}(N).$$

En effet, d'après le lemme précédent :

il existe $N' < N$ tel que $\tilde{u}_N \in u_{ad}(N')$ donc $J(\tilde{u}_{N'}) \le J(\tilde{u}_N)$

de plus $J(\tilde{u}_N) \le J(u) \quad \forall u \in u_{ad}(N)$ d'après la définition de $\tilde{u}_N$, ce qui démontre (3.7).

5) Il existe au moins $N \in [0, N_o]$ tel que la solution $\tilde{u}_N$ de $\tilde{P}_N$ appartienne à $u_{ad}(N)$.

En effet, sinon, par le raisonnement de 4), la meilleure valeur de $J$ se trouve dans le cas $N=0$

or

$$\overline{K}(o) = K(o).$$
et donc il existe un contrôle appartenant à $u_{ad}^{(o)}$ pour $\tilde{p}_o$ ce qui démontre la propriété.

6) On considère alors les solutions des problèmes $\tilde{p}_N$, appartenant à $u_{ad}^{(N)}$.

D'après 5) il en existe au moins une, et d'après 4) le contrôle optimal solution de (1.7) s'il existe, est parmi ces solutions.

Or celle-ci étant en nombre fini, la solution de (1.7) est celle qui donne la plus petite valeur de $J$.

On a donc le résultat suivant :

le problème de contrôle (1.6) admet au moins une solution.

■
4 - RESOLUTION D'UN PROBLEME DE CONTROLE DU TYPE (3.6)

On se place dans le cas N=1.

Nous avons pris l'exemple suivant, en dimension 1 ; Ω = ]0,1[

$$
\left\{
\begin{array}{l}
\displaystyle \frac{\partial y}{\partial t} - \frac{\partial^2 y}{\partial x^2} = g(x,t) + \bar{u} \chi_{[a,b]} \\[1em]
\qquad y(1,t) = y(0,t) = 0 \\[1em]
\qquad y(x,0) = y_o(x) .
\end{array}
\right.
$$

avec la fonction coût :

$$
J(a,b) = \int_{\Omega} \int_{0}^{T} |y(x,t) - z_d|^2 dx dt + \nu \int_{0}^{T} |\bar{u}|^2 \chi_{(a,b)} dt.
$$

Soit

$$
J(a,b) = \int_{\Omega} \int_{0}^{T} |y(x,t) - z_{d}|^{2} \, dx \, dt + \nu |\bar{u}|^{2} (b-a).
$$

On considère alors le problème de contrôle optimal suivant :

$$
\left\{
\begin{array}{l}
\text{Trouver } (\bar{a}, \bar{b}) \in K \text{ tel que} \\
J(\bar{a}, \bar{b}) = \text{Min } J(a,b) \\
(a,b) \in K
\end{array}
\right.
$$

$$
\text{avec} \quad K = \{ (a,b) \mid (a,b) \in [0,T]^2, a \le b \} .
$$

Ce problème de contrôle, admet au moins une solution

1 - Conditions nécessaires d'optimalité :

Considérons la formulation plus générale :

$$
(4.1) \qquad \left\{
\begin{array}{l}
\displaystyle \frac{\partial y}{\partial t} + Ay = f + Bu \\
\qquad y(0) = y_o(x)
\end{array}
\right.
$$
avec la fonctionnelle
$$ J(v) = \int_{\Omega} \int_{0}^{T} |y-z_d|^2 dx dt + v \int_{0}^{T} |v(t)|^2 dt $$
on prend
$$ v(t) = \bar{u} \sum_{i=1}^{n} \chi_{[a_i, b_i]} $$

$$
(4.2) \quad \text{alors} \quad J(u) = \int_{\Omega} \int_{0}^{T} |y-z_d|^2 dx dt + v \left|\bar{u}\right|^2 \sum_{i=1}^{n} (b_i - a_i).
$$

On introduit l'état adjoint :

$$
(4.3) \quad \left\{
\begin{array}{l}
- \frac{\partial p}{\partial t} + A^* p + y - z_d = 0 \\
p(T) = 0
\end{array}
\right.
$$

$A^*$ opérateur adjoint de A.

On obtient alors les conditions d'optimalité :

$$
(4.4) \quad \left\{
\begin{array}{l}
v |\bar{u}|^2 = \int_{\Omega} p(b_i) (\bar{B}u) (b_i) \\
v |\bar{u}|^2 = - \int_{\Omega} p(a_i) (\bar{B}\bar{u}) (a_i).
\end{array}
\right.
\quad \forall i=1,\dots,n
$$

■

## 2 - Résolution numérique

Le gradient de la fonctionnelle J est donné par les formules (4.4).

Bien que la fonctionnelle ne soit pas convexe, nous employons une méthode du type gradient.

Nous avons testé la méthode avec les données suivantes :

$\bar{u} = 10$

$g(x,t) = x(x-1) - 2t$

$y_0(x) = 0$
$z_d(x,t)$ étant la solution du système direct pour $a=0,50 ; b=0,60$. la
solution exacte est donc $(0,50 ; 0,60)$.

On obtient le résultat suivant :

$(0,5000315 ; 0,6019817)$

pour une valeur de la fonctionnelle : $9,968 \times 10^{-6}$.

L'état du système correspondant au contrôle optimal est donné en **Figures 1 et 2**
Etat du système pour le contrôle optimal

<figure><img src="image_15.png" /><figcaption>Figure 1</figcaption></figure>
<figure><img src="image_16.png" /><figcaption>Figure 2</figcaption></figure>
5 - MINIMISATION D'UNE FONCTIONNELLE QUADRATIQUE EN VARIABLES TRUELITES.

Nous transformons le problème de contrôle initial, en prenant le con-
trôle sous la forme Σᵢ αᵢ χ [ aᵢ, bᵢ ] aᵢ, bᵢ fixés et αᵢ ∈ {0,1} .
De plus y étant solution de :

$$
\left\{
\begin{array}{l}
\displaystyle \frac{\partial y}{\partial t} - \frac{\partial^2 y}{\partial x^2} = g(x,t) + u(t) \\[1em]
\begin{array}{l}
y|_{\Sigma} = 0 \\
y(x,o) = y_o(x).
\end{array}
\end{array}
\right.
$$

y(x,t) est fonction affine de αᵢ, et donc la fonctionnelle à minimiser est
quadratique en αᵢ.

Nous avons donc été amenés à étudier de façon générale, la minimisation quadra-
tique en variables boolèennes. Nous nous ramenons alors à un problème linéaire
de minimisation en nombres entiers.

Pour résoudre ce problème, nous employons deux méthodes :

- la première utilise la théorie des groupes (SHAPIRO [ 1 ] ).

Nous employons la programmation dynamique pour résoudre un problème
dans un groupe fini.

- La seconde utilise un algorithme du type Branch and Bound.

Dans ce chapitre, nous considérons donc le problème

$$
\left\{
\begin{array}{ll}
\text{Min} & t\alpha A \alpha + t^b \alpha = \tilde{J}(\alpha) \\
\\
& E \alpha = f \\
\\
& \alpha \text{ booléenne}
\end{array}
\right.
$$
## 5.1 - Mise du problème sous forme linéaire

Nous faisons tout d'abord la remarque suivante :

si $\alpha$ est une variable booléenne, alors $\alpha^2 = \alpha$. En conséquence $\tilde{J}(\alpha)$ s'écrit

$$ \sum_{i,j \ i \neq j} a_{i;} \alpha_{i} \alpha_{j} + \sum_{i=1}^{n} \bar{b}_{i} \alpha_{i} \quad \text{avec} \quad \bar{b}_{i} = b_{i} + a_{i} $$

faisons le changement de variables suivant :

$\gamma_{ij} = \alpha_{i} \alpha_{j}$, $\alpha_{ij}$ est encore une variable booléenne

et le problème (1.7) est équivalent à

$$ \begin{array}{ll} \text{(1.1)} & \left\{ \begin{array}{ll} \text{Min} & \sum_{i,j \ i \neq j} \gamma_{ij} (a_{ij} + a_{ji}) + \sum_{i=1}^{n} \bar{b}_i \alpha_i \\ & \gamma_{ij} = \alpha_i \alpha_j \quad \text{ pour } i,j=1,\dots,n \ i \neq j \\ & E \alpha = f \\ \\ \alpha_i, \alpha_j \in \{0,1\} & \end{array} \right. \\ & \text{et les variables booléennes, on remarque que les contraintes :} \\ & \left\{ \begin{array}{l} \gamma_{ij} = \alpha_i \alpha_j \\ \alpha_i, \alpha_j \in \{0,1\} \end{array} \right. \text{ sont équivalentes au système de contraintes :} \\ & \left\{ \begin{array}{l} \gamma_{ij} \le \alpha_i \\ \gamma_{ij} \le \alpha_j \\ \gamma_{ij} \ge \alpha_i + \alpha_j - 1 \\ \text{entier, non négatif} \\ \alpha_i, \alpha_j \text{ entiers, non négatifs} \end{array} \right. \end{array} $$

$$ \begin{array}{l} \left\{ \begin{array}{l} \gamma_{ij} \le \alpha_i \\ \gamma_{ij} \le \alpha_j \\ \gamma_{ij} \ge \alpha_i + \alpha_j - 1 \end{array} \right. \\ \text{entier, non négatif} \\ \alpha_i, \alpha_j \text{ entiers, non négatifs} \end{array} $$
Le problème (1.1) est alors équivalent au problème linéaire suivant :

$$
\begin{array}{ll}
\text{Min} & \displaystyle \sum_{\substack{i,j \\ i \neq j}} \gamma_{ij} (a_{ij} + a_{ji}) + \sum_{i} \bar{b}_i \alpha_i \\[1em]
& \gamma_{ij} \le \alpha_i \\[1em]
& \gamma_{ij} \le \alpha_j \\[1em]
& \gamma_{ij} \ge \alpha_i + \alpha_j - 1 \\[1em]
& \text{E } \alpha = \text{f} \\[1em]
& \gamma_{ij}, \alpha_i \text{ entiers, non négatifs}
\end{array}
\qquad (1.3)
$$

On est donc ramené à étudier le problème du type suivant, en introduisant
au besoin des variables d'écart

$$
\begin{array}{ll}
 & t \\
\text{Min} & c \quad x \\
Ax = b \\
x \text{ entier, non négatif.}
\end{array}
\qquad (1.4)
$$

5.2 - Étude du problème type

On ramène (1.4) à un problème de minimisation dans un groupe fini. Soit
donc le problème (1.4) avec

A une m x (m+n) matrice à coefficients entiers

b un m-vecteur à coefficients entiers

c un vecteur réel.
Sur le problème (1.4) nous effectuons la transformation suivante : si on note (1.4) bis le problème continu associé à (1.4)

$$ (1.4) \text{ bis} \quad \left\{ \begin{array}{l} \displaystyle \operatorname{Min} t \ c \ x \\[1em] \qquad Ax = b \end{array} \right. $$

Soit B une base optimale de (1.4) bis (obtenue par la méthode du simplexe)

$x = [ x_B, x_R ] \quad x_B$ les composantes de x associées aux colonnes de B

$A = [ B, R ]$

on obtient

$$ (2.1) \quad \left\{ \begin{array}{l} \displaystyle \operatorname{Min} \quad t_{c_R} \ x_R + t_{c_B} \ x_B \\[1em] \qquad R \ x_R + B \ x_B = b \\[1em] \qquad x_B, x_R \text{ entiers, non négatifs} \end{array} \right. $$

soit

$$ (2.2) \quad \left\{ \begin{array}{l} \displaystyle \operatorname{Min} \ c_R^* \ x_R \\[1em] \qquad x_B = B^{-1} \ b - B^{-1} \ R \ x_R \\[1em] \qquad x_R, x_B \text{ entiers, non négatifs} \end{array} \right. $$

$$ \text{avec} \qquad c_R^* = c_R - c_B \ B^{-1} \ R. $$

alors on remarque que les contraintes

$$ \left\{ \begin{array}{l} x_B = B^{-1} \ b - B^{-1} \ R \ x_R \\[1em] x_B \text{ entier} \end{array} \right. \qquad \text{peuvent être remplacées} $$
$$
(2.3) \quad \text{par :} \quad \mathbb{B}^{-1} \mathbb{b} - \mathbb{B}^{-1} \mathbb{R} \ x_{\mathbb{R}} = \mathcal{O} \ (\text{mod } 1).
$$

Si on note alors $\mathbb{D}$ le déterminant de $\mathbb{B}$, (2.3) peut s'écrire

$$
(2.4) \qquad \sum_{j=1}^{n} \alpha_j x_j = \alpha_b \pmod{D}.
$$

(1.4) s'écrit alors :

$$
(2.5) \quad \left\{
\begin{array}{ll}
\text{Min} & \sum_{j=1}^{n} c_j^* x_j \\
\\
& \sum_{j=1}^{n} \alpha_j x_j = \alpha_b \pmod{D} \\
\\
& x_j \text{ entier, non négatif.}
\end{array}
\right.
$$

$$
\text{On omet alors la contrainte } x_B \ge 0 (*)
$$

On considère alors l'application $f$ qui transforme les composantes d'un vecteur en leur classe module $D$.

Alors $f \in \mathcal{B}$ engendre un groupe abélien $G$, d'ordre $D$, pour l'addition modulo $D$.

si $M(B)$ représente le module sur $\mathbb{Z}$ généré par les colonnes de $B$

$$
M(I) = \left\{ \sum_{j=1}^{m} \text{De } j \ x_j \ \middle| \ x_j \in \mathbb{Z} \right\} \text{ avec } e_j \text{ ième vecteur unité dans l'espace à } m \text{ dimensions}
$$

alors $G$ est isomorphe à $M(B)/M(I)$

en effet si on considère l'application $f$ de $M(B)$ dans $G=f(M(B))$

on a $M(B)/\ker f \cong G$ et on obtient le résultat puisque

$$
\ker f = M(I) \quad M(B)/\ker f \cong f(M(B)).
$$

La contrainte d'intégrité du problème (2.5) se ramène alors dans le
groupe $G$ à une contrainte d'égalité et en appliquant $f$ à (2.5) on se trouve en
présence d'un problème dans un groupe fini $G$ d'ordre $D$.

Alors sur le groupe $G$ nous pouvons utiliser le théorème de décomposition
des groupes finis qui donne l'existence de $r$ entiers positifs

$$
q_1, \dots, q_r \text{ tels que } q_1 | q_2 | \dots | q_r ; \ D = \bigoplus_{i=1}^{r} q_i
$$
et $G \simeq Zq_1 \oplus Zq_2 \oplus \dots \oplus Zq_r$.

ce théorème donne donc en fait la structure du groupe G.

Le problème de groupe s'écrivant alors :

6)

$$
\left\{
\begin{array}{ll}
\text{Min} & \sum_{j=1}^{m} c_j^* x_j \\
\\
& \sum_j \bar{\alpha}_j x_j = \bar{\alpha}_b \\
\\
\text{x_j entier, non négatif} & \text{avec } \bar{\alpha}_j = f(\alpha_j).
\end{array}
\right.
\qquad \blacksquare
$$

On a donc comme contraintes r égalités modulo q_i (égalités dans Z/q_i)

N.B. En fait la structure du groupe G sera en pratique déterminée par la
transformation de Smith de la matrice B, ce qui permettra également d'obtenir
les coefficients $\bar{\alpha}_j$ et $\bar{\alpha}_b$ (cf. 5.3).

Le problème (2.6) est alors résolu par un algorithme du type programma-
tion dynamique ( SHAPIRO [1] ).

5.3 - Mise en oeuvre numérique de la méthode.

5.3.1) Par la méthode de simplexe, nous obtenons une base optimale du problème (1.4) bis, soit B la matrice représentant cette base. B est une matrice (mxm) entière.

Nous appliquons à B le procédé de diagonalisation de Smith, c'est-à-dire
qu'il existe deux matrices unimodulaires à coefficients entiers U et V telles
que U.B.V soit une matrice diagonale à coefficients entiers.

<footnote>* **Remarque** : Si la contrainte $x_B \ge 0$, ne se trouve pas vérifiée par la solution obtenue, on résout un nouveau problème en introduisant de nouvelles contraintes (Pour la génération de ces coupes, nous renvoyons à GONDRAN [1]) et ainsi de suite jusqu'à ce qu'on obtienne une solution x telle que $x_i \ge 0 \quad \forall i$</footnote>
$$
(3.1) \qquad \begin{array}{r@{\,}c@{\,}l@{\quad}l}
 & \multicolumn{2}{c}{\text{U.B.V =}} & \left[ \begin{array}{@{}cccc@{}}
 & d_1 & & 0 \\
 & 0 & \ddots & \\
 & & \ddots & d_m \\
 & & & \end{array} \right] \\
\text{avec } d_i \mid d_{i+1}. & \multicolumn{2}{c}{\text{d}} &
\end{array}
$$

On remarque alors que si on pose $x_B = Vy_B$, comme V est unimodulaire, $x_B$ entier équivaut à $y_B$ entier.

Alors les contraintes du problème (2.2) peuvent s'écrire :

$$
\begin{cases}
B V y_B = b - R x_R \\
x_R, y_B \text{ entiers}
\end{cases}
$$

soit

$$
\begin{cases}
U B V \quad y_B = U b - U R x_R \\
x_R, y_B \text{ entiers}
\end{cases}
$$

Mais vu la forme de la matrice U.B.V , cela équivaut à

$$
(3.2) \quad \left[ \underline{U}b - UR \mathbf{x}_R \right]_i \equiv 0 \pmod{d_i} \quad i=1,\dots,m
$$

(1) $[\underline{U}b - UR \mathbf{x}_R]_i \equiv 0 \pmod{d_i}$ et $i=1, \dots, m$ indiquant qu'on considère la ligne $i$ de la matrice $U$. Alors si les premiers nombres $d_i$ sont égaux à $1$, les $m-r$ premières égalités du type (4.2) se trouvent automatiquement vérifiées et on a riconstruit les contraintes du type (3.2).

Ces contraintes sont celles du problèmes (2.6) qui s'écrit

$$
(3.3) \quad \left\{
\begin{array}{@{}l@{\quad}l@{}}
\text{Min} & \displaystyle\sum_{j=1}^{m} c_j^* x_j \\[1em]
& \left[ \underline{U}b - UR \mathbf{x}_R \right]_i \equiv 0 \pmod{d_i} \quad i=m-r+1, \dots, m \\[1em]
\mathbf{x}_R & \text{entier, non négatif.}
\end{array}
\right.
$$
De plus on a les relations suivantes : $d_{m-r+i} = q_i \quad i=1,...,r$

et $\Pi_i d_i = D$ D déterminant de la matrice B et ordre du groupe G.

D'autre part, la matrice U permet de représenter le groupe G, en fait
elle définit un des automorphismes de ce groupe. Le problème étant alors écrit
sous la forme (4.3), on applique un algorithme du type programmation dynamique.

N.B. 1 : Dans le cas où le groupe G est cyclique, on peut utiliser la méthode des congruences décroissantes (GONDRAN [1]).

N.B. 2 : La mise sous forme canonique (3.3) n'est pas unique, mais dépend de l'automorphisme du groupe choisi.

### 5.3.2) Mise sous forme réduite de Smith :

Soit $B=(b_{ij})$ la matrice qu'on souhaite mettre sous la forme de Smith.

① Nous allons d'abord déterminer deux matrices $U_1$ et $V_1$ telles que $U_1 B V_1$ s'écrive

$$ \begin{bmatrix} d_1 & 0 & \cdots & 0 \\ 0 & B_1 & & 0 \\ \vdots & & \ddots & \vdots \\ 0 & & & 0 \end{bmatrix} $$

on collecte alors les opérations suivantes :

(1) par permutation des lignes et des colonnes de B, on amène le plus petit terme en valeur absolue de la matrice B en position (1,1), soit $b_{1,1}$ ce terme.

(2) alors nous remplaçons (par multiplication respectivement à droite et à gauche par des matrices élémentaires) chaque élément respectivement de la lère ligne et de la lère colonne par son reste dans la division euclidienne par $b_{1,1}$.
γ) Si les restes sont nuls, on a terminé la lère étape, sinon on recommence en α) avec la nouvelle matrice. Or comme à chaque itération les restes décroissent strictement, au bout d'un nombre fini d'itérations, on aura obtenu la forme souhaitée.

② On recommence alors le procédé précédent sur la matrice $B_1$ et ainsi de suite.

<figure><img src="image_17.png" /></figure>

mais on n'a pas $d_i | d_{i+1}$

alors par transformation élémentaire, on remplace $d_1$ et $d_2$ respectivement par PGCD ($d_1, d_2$) et PPCM ($d_1, d_2$) en renouvelant cette opération avec tous les couples $(d_i, d_j)$ $j > i$ on obtient la forme réduite de Smith.

## 5.4 - Exemples numériques

### 1) Cas d'une fonctionnelle linéaire

On reprend l'exemple donné par SHAPIRO (SHAPIRO [1]).

$$ \text{Min } (-78x_2 - 21x_3 + 124x_5 - 6x_7 - 17x_8 - 10x_9) $$ 
$$ \begin{cases} x_3 + x_4 - 8x_5 - 2x_7 - x_8 - 3x_9 = 33 \\ 6x_9 - x_3 + x_5 + x_6 - 2x_7 + 4x_8 = 27 \\ x_1 + 4x_2 + x_3 - 5x_5 + x_8 + x_9 = 86 \end{cases} $$

$x_i$ entier, non négatif

les vecteurs de base optimaux sont (7, 8, 9).
le problème sous sa forme canonique s'écrit :

$$
\left\{
\begin{array}{l}
\text{Min} \quad 117/6 x_1 + x_2 + 3/2 x_3 - 19/6 x_4 - 8/6 x_5 - 1/6 x_6 \\
\quad x_3 + x_5 + x_6 \equiv 1 \pmod{2} \\
\quad 3x_1 + 3x_3 + x_4 + 2x_5 + x_6 \equiv 0 \pmod{6} \\
\quad x_i \text{ entier, non négatif.}
\end{array}
\right.
$$

N.B : Ici nous n'avons pas utilisé le même automorphisme du groupe G que Shapiro.

La solution de ce problème est (0, 0, 0, 0, 1, 4).

La solution du problème global est alors

(0, 0, 0, 0, 1, 4, 101, 56, 35).

le calcul a été effectué sur CII 90-80, en 4' (compilation comprise).

2 - Cas d'une fonctionnelle quadratique sans contrainte

2.1) On considère le problème

$$
\left\{
\begin{array}{l}
\text{Min} \ (x_1 - 2x_2 + x_5 - x_3 + x_1 x_3 + x_2 x_4) \\
\quad x_i \in \{0,1\} .
\end{array}
\right.
$$

Ce problème se ramène au problème linéaire entier suivant :

$$
\text{Min} \ (x_1 - 2x_2 + x_5 - x_3 + \gamma_{13} + \gamma_{24})
$$
avec les contraintes

$$
\left\{
\begin{array}{l}
\gamma_{ij} \le x_i \\
\gamma_{ij} \le x_j \\
\gamma_{ij} \ge x_i + x_j - 1 \\
\qquad x_i; \gamma_{ij} \ge 0 \text{ entiers}
\end{array}
\right.
$$

ce qui représente 30 contraintes et 45 variables.

Dans cet exemple, le déterminant de la matrice de base optimale est 1, donc le
simplexe donne directement le résultat du problème en nombres entiers.

En effet, si $|\det B| = 1$, on a $d_i^{=1} \forall i$ et de plus B étant la matrice de base optimale $c_R^* = c_R - c_B^T B^{-1} R \ge 0$, alors le problème de groupe se ramène au problème sans contrainte

$$
\left\{
\begin{array}{l}
\text{Min } c_R^* \quad x_R \\
x_R \text{ entier, non négatif avec } c_R^* \ge 0
\end{array}
\right.
$$

qui admet la solution $x_R = 0$ (Résultat obtenu par la méthode du simplexe).

et alors $x_B = B^{-1} b$ est entier, car B est unimodulaire.

Donc, à chaque fois que $|\det B| = 1$, le programme linéaire continu donne la
solution du problème en nombres entiers.

Dans cet exemple particulier $|\det B| = 1$, et on obtient la solution $(0,1,!,0,0)$.

2.2) Nous prenons maintenant l'exemple suivant :

$$
\left\{
\begin{array}{l}
\displaystyle \text{Min} \left( -\frac{4}{3} \quad x_1 - x_2 - x_3 + x_1 x_2 + x_1 x_3 + x_2 x_3 \right. \\
\qquad \left. x_i \in \{0,1\} \right)
\end{array}
\right.
$$
Alors le programme linéaire continu admet la solution non entière

$$x_1 = 0,5 \quad x_2 = 0,5 \quad x_3 = 0,5 \quad y_{12} = 0 \quad y_{13} = 0 \quad y_{23} = 0.$$

Sous sa forme canonique le programme linéaire entier s'écrit :

$$\begin{cases} \text{Min} \ [0,5 \ (x_1 + x_2 + x_3 + x_4 + x_5 + x_6)] \\ x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 1 \ (\text{mod } 2). \end{cases}$$

On obtient alors la solution au problème initial (1, 0, 0).

N.B : Le problème admet en fait 3 solutions, ici nous obtenons l'une d'elles

### 2.3) Cas d'une fonctionnelle quadratique sans contrainte

les variables pouvant prendre les valeurs { 0, 1, 2 }

nous posons $x_i = y_{2i-1} + y_{2i}$ avec $y_i \in \{0,1\}$.

Nous obtenons alors un problème en variables booléennes. Il n'y a pas de bijection entre $x_i$ et $y_i$. Mais cependant pour $y_i$ donné on obtient un $x_i$ et un seul, qui correspondra à une solution du problème initial. Donc la non unicité en $y_i$ n'est pas génante pour résoudre le problème.

Exemple :

$$\begin{cases} \text{Min} \ x_1^2 - 4x_1 + 2x_2 + x_1 x_2 \\ x_i \in \{0,1,2\} \end{cases}$$

on pose

$$x_1 = y_1 + y_2$$

$$x_2 = y_3 + y_4$$
on a alors le problème en variables booléennes :

$$
\text{Min } \{-3y_1 - 3y_2 + 2y_3 + 2y_4 + 2y_1 y_2 + y_1 y_3 + y_1 y_4 + y_2 y_3 + y_2 y_4\} \\
y_i \in \{0,1\}.
$$

par la même méthode qu'au 2.1) on obtient la solution

$$
(1,1,0,0)
$$

$$
\text{soit pour le problème initial } \begin{cases} x_1 = 2 \\ x_2 = 0 \end{cases}
$$

N.B : De la même façon, nous pouvons traiter un problème avec x ∈ S ensemble discret fini.

3 - Cas d'une fonctionnelle quadratique avec contraintes

Dans ce cas, nous reprenons le programme général développé au §2, 3, 4.

Nous avons repris l'exemple du 2.3)

$$
\text{Min } (-3y_1 - 3y_2 + 2y_3 + 2y_4 + 2y_1 y_2 + y_1 y_3 + y_1 y_4 + y_2 y_3 + y_2 y_4) \\
y_i \in \{0, 1\}
$$

avec les contraintes

$$
(c) \left\{
\begin{array}{l}
3 y_1 \le y_2 + 2 \\
3 y_3 \le y_4 + 2.
\end{array}
\right.
$$

Alors la matrice B a un déterminant égal à 3 et le groupe G est isomorphe
à $\mathbb{Z}_3^2$.
Le problème sous forme canonique s'écrit :

$$ \begin{cases} \text{Min} & 3x_1 + 2x_2 + x_3 + x_4 + x_5 + 0,33x_7 + 2,33x_8 + x_9 + 0,33x_{10} \\ & x_7 + x_8 + x_{10} = 0 \pmod{3} \end{cases} $$

ce qui donne $x_i = 0 \quad \forall i = 1, \dots, 10$.

Le résultat final est alors :

(1,1,0,0) soit pour le programme en variables linéaires (2,0).
## 5.5 - Utilisation d'un algorithme du type Branch and Bound

On considère le système :

$$ (5.1) \qquad \left\{ \begin{array}{l} \displaystyle \operatorname{Min} \sum_{i,j} \gamma_{ij} (a_{ij}+a_{ji}) + \sum_{i} \bar{b}_{i} \alpha_{i} \\ \phantom{\operatorname{Min} \sum_{i,j} \gamma_{ij} (a_{ij}+a_{ji}) + \sum_{i} \bar{b}_{i} \alpha_{i}} \\ \quad i<j \\[2ex] \gamma_{ij} \le \alpha_{i} \\[1.5ex] \gamma_{ij} \le \alpha_{j} \\[1.5ex] \gamma_{ij} \ge \alpha_{i} + \alpha_{j} - 1 \end{array} \right. \\ \gamma_{ij}, \alpha_{i} \text{ entiers, non négatifs.} $$

et nous remplaçons la dernière contrainte par $\alpha_i$ booléen. Nous avons encore un système équivalent :

$$ (5.2) \qquad \left\{ \begin{array}{l} \displaystyle \operatorname{Min} \sum_{i,j} \gamma_{ij} (a_{ij}+a_{ji}) + \sum_{i} \bar{b}_{i} \alpha_{i} \\ \phantom{\operatorname{Min} \sum_{i,j} \gamma_{ij} (a_{ij}+a_{ji}) + \sum_{i} \bar{b}_{i} \alpha_{i} } \\ \quad i<j \\[2ex] \gamma_{ij} \le \alpha_{i} \\[1.5ex] \gamma_{ij} \le \alpha_{j} \\[1.5ex] \gamma_{ij} \ge \alpha_{i} + \alpha_{j} - 1 \end{array} \right. \\ \alpha_{i} \text{ booléen.} $$

Pour résoudre ce système nous utilisons alors l'algorithme du type Branch and Bound suivant :

On résout le problème continu par la méthode du simplexe. Si la solution est entière, c'est la solution du problème. Sinon soit $\alpha_\ell$ la première variable non entière, alors on effectue le branchement suivant $\alpha_\ell = 0$ et $\alpha_\ell = 1$.

On a l'organigramme :
<figure><img src="image_18.png" /></figure>

<footnote>(*) **Remarque** : Pour avoir une meilleure borne $J_o$, on utilise le fait qu'en mettant toutes les variables non entières à zéro, on obtient encore une solution admissible.</footnote>
Exemples numériques

On considère le problème :

$$
\begin{cases}
\min [ -x_1^{-x_2^{-x_3^{-x_4^{-x_5+x_1}}}} x_2^{+x_1} x_3^{+x_1} x_4^{+x_1} x_5^{+x_2} x_3^{+x_2} x_4^{+x_2} x_5^{+x_3} x_4^{+x_3} x_5^{+x_4} x_5 ] \\
x_i \in \{0,1\}
\end{cases}
$$

le problème linéaire continu associé admet la solution

$$
(\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
$$

Nous décrivons le graphe suivant :

<figure><img src="image_19.png" /></figure>

Nous parçons donc en fait une faible partie de l'arbre complet. De plus
nous obtenons avec cet algorithme 4 solutions équivalentes, (l'algorithme
avec les groupes ne donne qu'une solution), mais cependant nous n'avons pas
toutes les solutions.
5.6 - Applications à la programmation booléenne linéaire avec contraintes.
Utilisation de la pénalisation.

5.6.1) Principe de la pénalisation

Soit le problème suivant :

$$
(6.1) \quad \left\{
\begin{array}{ll}
\text{Min} & f(x) \\
Ax = b & \text{A étant une matrice à coefficients entiers} \\
x \in \{0,1\} & \text{b un vecteur entier.}
\end{array}
\right.
$$

Considérons alors le problème pénalisé :

$$
(6.2) \quad \left\{
\begin{array}{ll}
\text{Min} & f(x) + \frac{1}{\epsilon} [Ax-b]^2 \\
& x \in \{0,1\}
\end{array}
\right.
$$

**Théorème** : pour $\epsilon$ assez petit le problème (6.2) admet les mêmes solutions que le problème (6.1)

soit $x^*$ une solution de (6.2)

on a $Ax^*-b$ entier

supposons $Ax^*-b \neq 0$ on a alors $[Ax^*-b]^2 \geq 1$

$$
donc \quad f(x^*) + \frac{1}{\epsilon} [Ax^*-b]^2 \geq f(x^*) + \frac{1}{\epsilon}.
$$

Soit

$$
M = \min f(x) \\
x \in \{0,1\} \quad \text{tq} \quad Ax=b
$$

$$
m = \min f(x) \\
x \in \{0,1\}
$$

on a alors

$$
(6.3) \quad M \ge f(x^*) + \frac{1}{\epsilon} [Ax^*-b]^2 \ge m + \frac{1}{\epsilon}
$$
donc si on choisit $\varepsilon$ tel que $M < m + \frac{1}{\varepsilon}$ soit $\varepsilon < \frac{1}{M-m}$

on a alors une contradiction avec (6.3), ce qui démontre le Théorème.

Ainsi on ramène donc un problème en variables booléennes avec contraintes linéaires d'égalité à un problème sans contrainte.

### 5.6.2) Applications à la programmation linéaire

Soit le problème :

$$ (6.4) \quad \begin{cases} \text{Min} & c \ x \\ Ax = b \\ x \in \{0,1\} \end{cases} $$

ce problème est donc équivalent au problème :

$$ (6.5) \quad \left\{ \begin{array}{ll} \text{Min} & c \ x + \frac{1}{\varepsilon} [Ax-b]^2 \\ x \in \{0,1\} & \quad \text{pour } \varepsilon \ \text{assez petit} \end{array} \right. $$

On se ramène donc à un problème quadratique, sans contrainte comme au 4).

L'avantage de cette méthode est qu'alors le problème (6.5) est transformé en programme linéaire entier avec contraintes, mais la matrice des contraintes a une structure fixe, commune à tous les problèmes. D'autre part, comme nous l'avons remarqué au 4) dans un grand nombre de cas, vu la structure de la matrice des contraintes, le programme linéaire continu, donne la solution entière, ou tout au moins une très bonne approximation de celle-ci.

**Remarque :** Bien sûr, dans le cas quadratique avec contraintes, on pénalise les contraintes.
### 5.6.3) Généralisation à une certaine classe de fonctionnelles

Considérons une fonctionnelle de la forme $J(x) = \sum [f_i(x_i)]^2$ et le problème

$$ (6.6) \qquad \begin{cases} \text{Min} & J(x) \\ \text{Ax=b} \\ x \in \{0,1\} \end{cases} $$

On fait d'abord la remarque suivante :

$$ \text{si } x \in \{0,1\} \quad \text{on a} \quad f(x) = f(0) + x(f(1)-f(0)) $$

donc le problème (6.6) est équivalent au problème :

$$ (6.7) \qquad \begin{cases} \text{Min} & \sum_i [f_i(o) + x_i(f_i(1)-f_i(o))]^2 \\ \text{Ax=b} \\ x \in \{0,1\} \end{cases} $$

et par le procédé de pénalisation on se ramène au problème quadratique sans contrainte :

$$ (6.8) \qquad \begin{cases} \text{Min} & \sum_{i} [f_i(o) + x_i(f_i(1)-f_i(o))]^2 + \frac{1}{\epsilon} [Ax-b]^2 \\ \text{Ax} \le b \\ x \in \{0,1\} \end{cases} $$

pour $\epsilon$ assez grand.

Problème qu'on peut résoudre par une méthode donnée au §4.

### 6.4) Cas avec contraintes d'inégalité

Soit le problème

$$ (6.9) \qquad \begin{cases} \text{Min} & c \times \\ \text{Ax} \le b \\ x \in \{0,1\} \end{cases} $$
on introduit la variable d'écart s, (6.9) est alors équivalent à :

$$ (6.10) \qquad \left\{ \begin{array}{l} \text{Min } cx \\ Ax+Is = b \\ x \in \{0,1\} \quad s \ge 0. \end{array} \right. $$

Par un procédé de pénalisation semblable au cas 1), nous nous ramenons alors
au problème

$$ (6.11) \qquad \left\{ \begin{array}{l} \text{Min } cx + \frac{1}{\varepsilon} [Ax+Is-b]^2 \\ x \in \{0,1\}, s \ge 0 \end{array} \right. $$

(6.11) est alors un problème quadratique mixte.

Dans ce cas, nous devons donc employer une méthode de programmation mixte.
On peut envisager d'utiliser un algorithme sous-optimal du type de celui
exposé dans le Chap. III.

## CONCLUSION

Il apparaît donc que pour la minimisation d'une fonctionnelle quadratique en variables booléennes, la mise sous forme linéaire décrite ici est assez efficace en particulier grâce aux faits suivants :

- la structure de la matrice des contraintes du système linéaire associé est fixe (indépendante du problème traité),

- le simplexe associé donne une bonne approximation de l'enveloppe convexe des points booléens (pour n=2, on a l'enveloppe convexe). Ainsi dans de nombreux cas, le problème continu donne la solution exacte, ou une bonne approximation de celle-ci,

- le cas, avec contraintes d'égalité, se ramène au cas sans contrainte par pénalisation.
6 - APPLICATION DE LA PROGRAMMATION QUADRATIQUE BOOLEENNE AU PROBLEME DE CONTROLE.

Dans ce chapitre, nous prenons le contrôle sous la forme

$$ u = \sum_{i=1}^{n} \alpha_i \chi_{(a_i, b_i)} \quad \begin{array}{l} a_i, b_i \text{ fixés dans } [0,T] \\ \alpha_i \in \{0,1\} \end{array} $$

6.1) Position du problème

Nous nous plaçons dans le cas de la dimension 1.

Soit $\Omega$ un ouvert de $\mathbb{R}$

$$ \left\{ \begin{array}{l} a_1, \dots, a_n \\ b_1, \dots, b_n \end{array} \right. \quad \text{deux familles de points de } \Omega \text{ avec } a_i \le b_i $$

$\alpha_i$ ($i=1, \dots, n$) des variables booléennes, qui seront les variables de contrôle.

$$ \text{Soit } Q = \Omega \times ]0,T[; \quad \Sigma = \partial\Omega \times ]0,T[. $$

On considère l'état du système défini par les équations suivantes :

$$ (1.1) \qquad \left\{ \begin{array}{l} \displaystyle \frac{\partial y}{\partial t} - \frac{\partial^2 y}{\partial x^2} = g(x,t) + \bar{u} \sum_{i=1}^{n} \alpha_i \chi_{(a_i, b_i)} \\ \\ y|_{\Sigma} = 0 \end{array} \right. $$

$$ (1.2) $$

$$ (1.3) \qquad \begin{array}{l} y(x,0) = y_o(x) \end{array} $$
avec

$g(x,t) \in L^2(0,T;L^2(\Omega))$ donné

$f(t) \in L^2(0,T)$ donné

$y_o(x) \in L^2(\Omega)$ donné,

le système (1.1) (1.2) (1.3) (1.4) définit de façon unique $y$ fonction de $\alpha$.

On considère la fonctionnelle suivante :

$$ (1.5) \qquad J(\alpha) = \iint_{\Omega} \int_{T}^{0} |y(x,t)-z_{d}|^{2} dt \quad z_{d} \text{ donné dans } L^{2}(0,T;L^{2}(\Omega)) $$

On étudie alors le problème de contrôle suivant :

$$ (1.6) \qquad \begin{cases} \text{Trouver } \bar{\alpha} \in I_{ad} \text{, tel que} \\ J(\bar{\alpha}) = \begin{array}{l} \text{Min } J(\alpha) \\ \alpha \in I_{ad} \end{array} \end{cases} $$

avec $I_{ad}$ ensemble des variables booléennes admissibles pour le problème.

$I_{ad}$ n'ayant qu'un nombre fini d'éléments, le problème (1.6) admet au moins une solution. ■

## 6.2) Résolution numérique

$y(x,t)$ étant fonction affine $\alpha$

$J(\alpha)$ est quadratique en $\alpha_1, \dots, \alpha_n$.

Dans un premier temps, nous calculons donc les coefficients de la fonctionnelle $J$, ce qui correspond à $n+1$ intégrations du système (1.1)...(1.4)

Alors $J(\alpha)$ s'écrit $J(\alpha) = \int_{\alpha}^{t} \alpha A \alpha + \int_{\alpha}^{t} b \alpha + c$

$A, b$ ayant été calculés.
Dans un second temps, nous avons donc à résoudre un problème quadratique
booléen classique, par l'un des algorithmes décrit en ⁵).

Dans un grand nombre de cas, le problème linéaire continu associé donne la
solution entière, ou une bonne approximation de celle-ci (voir §5).

Exemples numériques :

Exemple 1

On considère le problème (1.6) avec

$$
\begin{cases}
\bar{u} = 10 \\
y_o(x) = 0 \\
y(x,t) = x(x-1) - 2t
\end{cases}
$$

pour z_d, nous avons pris la solution du système pour u=\bar{u} \chi_{(0,50 ; 0,60)}.

Puis nous avons considéré diverses partitions de [0,T].

Dans un premier temps nous calculons les coefficients de la fonctionnelle
quadratique à minimiser.

La résolution numérique du problème quadratique en variables booléennes a
été obtenue pour toutes les partitions choisies directement par le problème
linéaire continu associé (on se trouve donc dans le cas | det B| = 1).
## Partitions choisies

<figure><img src="image_20.png" /></figure>

①

<figure><img src="image_21.png" /></figure>

②

<figure><img src="image_22.png" /></figure>

③

<figure><img src="image_23.png" /></figure>

④

<figure><img src="image_24.png" /></figure>

⑤
$z_d(x,y)$ étant solution du problème (1.6) avec

$$
\begin{cases}
g(x,t) = - \frac{10\pi}{4h} x(x-1)\cos\left(\frac{\pi}{h}t + \Pi\right) + \frac{10}{2}\sin\left(\frac{\pi}{h}t + \Pi\right) + \frac{10}{2} \\
y_o(x) = - \frac{10}{4} x(x-1).
\end{cases}
$$

Ainsi la solution du problème continu est :

$$
v(t) = \frac{10}{2} \sin \left( \frac{\pi}{h} t + \Pi \right) + \frac{10}{2}.
$$

soit la courbe suivante :

<figure><img src="image_25.png" /></figure>

cas 1

Nous avons considéré la partition suivante :

<figure><img src="image_26.png" /></figure>

et nous cherchons le contrôle sous la forme
$$
\bar{u} = \sum_{i=1}^{5} \chi_{(a_i, b_i)}
$$
selon les valeurs de u nous avons les résultats suivants :

i=0,05

<figure><img src="image_27.png" /></figure>

(1,1,1,1,1) J=-2,288x10⁻¹

|i=0,1

<figure><img src="image_28.png" /></figure>

(1,1,1,1,1) J=-0,3697x10⁻¹

|i=1

<figure><img src="image_29.png" /></figure>

(1,1,1,1,1) J=-0,1578

|i=3

<figure><img src="image_30.png" /></figure>

(1,1,1,1,1) J=-0,2492

|i=4

<figure><img src="image_31.png" /></figure>

(1,0,1,0,1) J=-0,2299

|i=5

<figure><img src="image_32.png" /></figure>

(1,0,1,0,1) J=-0,2359

|i=7

<figure><img src="image_33.png" /></figure>

(1,0,1,0,1)
J=-0,1901

|i=8

<figure><img src="image_34.png" /></figure>

(1,0,1,0,1)
J=-0,1383

|i=9

<figure><img src="image_35.png" /></figure>

(1,0,1,0,0)
J≈0,6985x10⁻¹

|i=10

<figure><img src="image_36.png" /></figure>

(0,1,0,0,1)
J≈-0,4525x10⁻¹

|i=15

<figure><img src="image_37.png" /></figure>

(0,0,0,0,0)

τ=0
<figure><img src="image_38.png" /><figcaption>Figure 1 : Variation de $J_{opt}$ en fonction de $\bar{u}$.</figcaption></figure>
pour $\bar{u}=0,05 ; 0,1 ; 1 ; 3 ; 4 ; 5 ; 15$ nous obtenons directement la
solution optimale par le système linéaire associé

pour $\bar{u} = 7 ; 8 ; 9 ; 10$ nous devons poursuivre l'algorithme du type Branch and Bound utilisé

ainsi pour $\bar{u}=10$ nous décrivons l'arbre suivant :

<figure><img src="image_39.png" /></figure>

En Fig. 1, nous donnons les variations de $J_{opt}$ en fonction de $\bar{u}$.
Nous fixons $u=5$ et nous regardons les résultats obtenus en faisant varier la partition :

<figure><img src="image_40.png" /><figcaption>N=2</figcaption></figure>

<figure><img src="image_41.png" /><figcaption>N=3</figcaption></figure>

<figure><img src="image_42.png" /><figcaption>N=4</figcaption></figure>

<figure><img src="image_43.png" /><figcaption>N=5</figcaption></figure>

<figure><img src="image_44.png" /><figcaption>N=6</figcaption></figure>

<figure><img src="image_45.png" /></figure>

T=6s
sur CII 10070

<figure><img src="image_46.png" /><figcaption>N=8</figcaption></figure>

T=56,4s
sur CII 10070

<figure><img src="image_47.png" /><figcaption>N=10</figcaption></figure>

T=5 mn 52,8s
sur CII 10070
<figure><img src="image_48.png" /></figure>

Minimum de la fonctionnelle en fonction du nombre d'élèvements de la partition.
Exemple 3

On considère de nouveau le problème (1.6) avec

$$
\begin{cases}
g(x,t) = -\frac{10}{2} x(x-1) \\
y_o(x) = 0
\end{cases}
$$

$z_d(x,t)$ étant solution du problème (1.6) avec :

$$
\begin{cases}
g(x,t) = -\frac{10}{2} x(x-1) + 10t \\
y_o(x) = 0.
\end{cases}
$$

Ainsi la solution du problème continu est

$v(t) = 10 t.$

Nous avons alors traité les mêmes partitions que dans le cas 2 de
l'exemple 2, en prenant pour ū les 2 valeurs suivantes :

$\bar{u}=5 \quad \text{et} \quad \bar{u}=10$

Nous avons obtenu les résultats suivants :
$\bar{u}=5$

N=1

<figure><img src="image_49.png" /></figure>

N=2

<figure><img src="image_50.png" /></figure>

N=3

<figure><img src="image_51.png" /></figure>

N=4

<figure><img src="image_52.png" /></figure>

N=5

<figure><img src="image_53.png" /></figure>

N=6

<figure><img src="image_54.png" /></figure>

T=6s

sur CII 10070

N=8

<figure><img src="image_55.png" /></figure>

T=33s

sur CII 10070

N=10

<figure><img src="image_56.png" /></figure>

T=3mn 48,6s

sur CII 10070

N=12

<figure><img src="image_57.png" /></figure>
Cas 2

u=10

N=1

<figure><img src="image_58.png" /></figure>

N=2

<figure><img src="image_59.png" /></figure>

N=3

<figure><img src="image_60.png" /></figure>

N=4

<figure><img src="image_61.png" /></figure>

N=5

<figure><img src="image_62.png" /></figure>

N=6

<figure><img src="image_63.png" /></figure>

T=7,2s
sur CII 10070

N=8

<figure><img src="image_64.png" /></figure>

T=48,6s
sur CII 10070

N=10

<figure><img src="image_65.png" /></figure>

T=2mn 34s
sur CII 10070

N=12

<figure><img src="image_66.png" /></figure>
<figure><img src="image_67.png" /></figure>

Minimum de la fonctionnelle en fonction de N
BIBLIOGRAPHIE

<table>
  <tr>
    <td>BALAS</td>
    <td>: Discrete Programming by the Filter Method.</td>
  </tr>
  <tr>
    <td>COURANT - HILBERT</td>
    <td>: Methods of Mathematical Physics.</td>
  </tr>
  <tr>
    <td>DIEUDONNE</td>
    <td>: Eléments d'Analyse (Gauthier-Villars 1968).</td>
  </tr>
  <tr>
    <td>ERNIE, ZYSS</td>
    <td>: Contrôle ponctuel sur une équation de la chaleur (Janvier 1972).</td>
  </tr>
  <tr>
    <td>FIOROT</td>
    <td>: Structures d'ensembles de points entiers (Thèse Lille 1971).</td>
  </tr>
  <tr>
    <td>GARFINKEL - NEMHAUSER</td>
    <td>: Optimal set convering and partitionning a survey of applications and algorithms.</td>
  </tr>
  <tr>
    <td>GEOFFRION</td>
    <td>: Generalized Benders Decomposition (JCTA 1972).</td>
  </tr>
  <tr>
    <td>GEOFFRION - MARSTEN</td>
    <td>: Integer Programming algorithms : A framework and State of the art survey (Management Science May 1972).</td>
  </tr>
  <tr>
    <td>GONDRAN</td>
    <td>[1] : Programmation en nombres entiers (Bulletin E.D.F. N° 2 1970).</td>
  </tr>
  <tr>
    <td>GONDRAN</td>
    <td>[2] : Forte pénalité en programmation linéaire en nombres entiers par la méthodes des congruences décroissantes. (Bulletin EDF N° 2 1972).</td>
  </tr>
  <tr>
    <td>GONDRAN</td>
    <td>[3] : Programmation entière non linéaire : dualité diophantienne. (Bulletin EDF N° 1 1971).</td>
  </tr>
  <tr>
    <td>LIONS</td>
    <td>[1] : Contrôle optimal de systèmes gouvernés par des équations aux dérivées partielles. (Dunod-Gauthier-Villars 1968.)</td>
  </tr>
</table>
LIONS [2] : Some aspects of the optimal control of distributed parameter systems. (SIAM 1972).

LIONS [3] : Quelques méthodes de résolution de problèmes aux limites non linéaires (Dunod Gauthier-Villars 1969).

LIONS - MAGENES : Problèmes aux limites non homogènes et applications. (Dunod 1968).

MIGNOT : Etude d'un problème de contrôle de valeurs propres et de fonctions propres, cas linéaire. (Faculté des Sciences, Paris VI, Tour 55-65, à paraître).

SCHWARTZ : Cours d'Analyse de l'Ecole Polytechnique 1971/72.

SHAPIRO [1] : Dynamic programming algorithms of the integer programming Problem 1 : The integer programming viewed as a knapsack type problem (Operations Research 16-1968).

SHAPIRO [2] : Group theoretic algorithms for the integer programming. Problem II : Extensions to a general algorithm. (Operations Research 16-1968).

VAN DE WIELE : Thèse 3ème Cycle.

=§=§=§=§=§=§=§=