4. Solutions optimales

Sun Woong Kim, Steven G. Heeringa et Peter W. Solenberger

Précédent | Suivant

Étant donné l’ensemble de $L$  tableaux possibles dans $\mathfrak{B}$ , considérons le sous-ensemble ${\mathfrak{B}}^{\text{'}}(\subseteq \mathfrak{B})$  où

$$p\left(B_k\right)>0.$$

Un ensemble de solutions d’un problème de sélection contrôlée $A$  désigné par

$$\left\{\left(B_k,p\left(B_k\right)\right),B_k\in {\mathfrak{B}}^{\text{'}}\right\}$$

est l’ensemble des tableaux qui possèdent les probabilités de sélection positives requises $\left(p\left(B_k\right)>0\right)$ . Cet ensemble de solutions, ou simplement une « solution » du problème de sélection contrôlée, est habituellement obtenu en se servant d’un algorithme pour appliquer les contraintes (3.1) à (3.6). Comme il est décrit dans l’introduction, depuis Goodman et Kish (1950), de nombreux algorithmes ont été élaborés pour trouver des solutions aux problèmes de sélection contrôlée.

Jusqu’à ce que Groves et Hess (1975) proposent un algorithme informatique, la plupart des solutions étaient obtenues manuellement selon un processus qui ressemble à la résolution d’un casse-tête mathématique. En outre, pour la plupart des problèmes, il se peut que les contraintes soient satisfaites par plus d’un ensemble de solutions. Depuis les années 1980, on a élaboré des algorithmes de sélection contrôlée, exigeants du point de vue informatique, qui s’appuient sur la théorie du transport, le cheminement dans les réseaux, la programmation par nombres entiers et la programmation linéaire. Ces algorithmes dépendent parfois de logiciels hautement spécialisés ou peuvent être programmés pour être exécutés dans les grands systèmes logiciels.

Cependant, les solutions antérieures allant des algorithmes manuels aux algorithmes exigeants du point de vue informatique ont rarement été comparées empiriquement en appliquant un jeu normalisé de critères de performance. Par conséquent, nous commençons ici par décrire un concept appelé ensembles de solutions optimaux, ou plus simplement, solutions optimales.

Le problème de sélection contrôlée $A$  ne comporte qu’un seul tableau, mais il pourrait exister de nombreux tableaux possibles dans $\mathfrak{B}.$ En outre, un seul tableau $B_k$  provenant de toute solution de $A$  est choisi aléatoirement en appliquant $p\left(B_k\right)$  comme fondement de la sélection de l’échantillon stratifié. Donc, en général, nous pourrions définir une solution optimale comme étant celle qui satisfait les exigences suivantes (E1 et E2) :

E1. La solution est obtenue en se basant sur des mesures appropriées et objectives de la proximité de $A$  par rapport à chaque tableau individuel $B_k$  dans $\mathfrak{B}$ .

E2. La solution maximise, dans la mesure du possible, les probabilités de sélection sur les tableaux les plus proches de $A$  sous des mesures telles que celles mentionnées en E1.

La suite de la présente section porte sur la façon de spécifier E1 et E2 pour obtenir des solutions optimales. Premièrement, afin de définir la proximité dans E1, on peut considérer un nombre réel $d(B_k:A)$  représentant la distance entre $A$  et $B_k$ , où $d$  est une fonction de distance qui satisfait les axiomes suivants :

L’axiome (iii) porte le nom d’axiome d’inégalité triangulaire. Les fonctions de distance qui satisfont (i), (ii) et (iii) peuvent être définies en utilisant les deux $RC\text{-tuples}$  ordonnés $\left(a_{11},a_{12},\cdot \cdot \cdot ,a_{RC}\right)$  et $\left(b_{11k},b_{12k},\cdot \cdot \cdot ,b_{RCk}\right)$  pour $A$  et $B_k$ . Nous commençons par définir la distance ordinaire ou distance euclidienne (distance définie par la norme 2) :

$$d_2\left(B_k,A\right)={\left[{\displaystyle \sum _{i=1}^R{\displaystyle \sum _{j=1}^C{\left(b_{ijk}-a_{ij}\right)}^2}}\right]}^{\frac{1}{2}},k=1,\dots ,L.(4.1)$$

Cette fonction est probablement la mesure la plus connue pour définir la distance entre $B_k$  et $A$ .

Nous pouvons aussi définir la fonction appelée distance de Chebyshev (distance définie par la norme infinie) :

$$d_{\infty }\left(B_k,A\right)=\max \left\{\left|b_{ijk}-a_{ij}\right|:i=1,\dots ,R,j=1,\dots ,C\right\},k=1,\dots ,L.(4.2)$$

Ces fonctions de distance donnent naissance à deux espaces de distances distincts. En vertu de (3.2), pour tout $B_k$ , les expressions qui suivent sont vérifiées.

$$0\le d_2\left(B_k,A\right)<{\left(RC\right)}^{1/2}(4.3)$$

et

$$0\le d_{\infty }\left(B_k,A\right)<1.(4.4)$$

Par exemple, pour le tableau de dimensions $3\times 3$  dans le problème 2.1 et le tableau de dimensions $8\times 3$  dans le problème 2.3, $0<d_2\left(B_k,A\right)<3$  et $0<d_2\left(B_k,A\right)<4,9$ , respectivement.

Deuxièmement, comme il est mentionné dans E2, en ce qui concerne les tableaux les plus proches de $A$  sous de mesures telles que celles décrites en E1, considérons l’ensemble de tableaux dans $\mathfrak{B}$  possédant la valeur de $d_2$  ou $d_{\infty }$  minimale par rapport à $A$ . Soit ${\mathfrak{B}}_2(\subseteq {\mathfrak{B}}^{\prime })$  l’ensemble des tableaux ayant la valeur de $d_2$  minimale par rapport à $A$  et ${\mathfrak{B}}_{\infty }(\subseteq {\mathfrak{B}}^{\prime })$  l’ensemble des tableaux ayant la valeur de $d_{\infty }$  minimale par rapport à $A$ .

En supposant que tous les tableaux possibles dans $\mathfrak{B}$  sont connus, nous définissons les tableaux optimaux comme il suit.

Définition. Les tableaux compris dans ${\mathfrak{B}}_2\cup {\mathfrak{B}}_{\infty }$  sont appelés tableaux optimaux.

Notons que, dans le nouvel algorithme pour la sélection contrôlée qui sera décrit à la section 6, $d_2$  ou $d_{\infty }$  sont choisies en fonction des préférences. Nous évitons de définir l’intersection de ${\mathfrak{B}}_2$  et ${\mathfrak{B}}_{\infty }$  comme étant les tableaux optimaux, parce que cela pourrait exclure les autres tableaux non compris dans ${\mathfrak{B}}_2\cap {\mathfrak{B}}_{\infty }$  ayant la même valeur de $d_2$  ( $d_{\infty }$  ) minimale. Nous illustrons ci-après le fait qu’il pourrait exister un très petit nombre de tableaux optimaux relativement au nombre total de tableaux possibles dans $\mathfrak{B}$  pour tout $A$ . La façon de trouver tous les tableaux possibles sera décrite en détail aux sections 6 et 7.

Illustrations

Pour les problèmes 2.1 à 2.4, nous notons que ${\mathfrak{B}}_2\subseteq {\mathfrak{B}}_{\infty }$ . Donc, nous pouvons utiliser $d_{\infty }$  seulement pour illustrer les tableaux optimaux.

1. Pour le problème 2.1, il existe six tableaux possibles satisfaisant (3.1), (3.2), (3.3) et (3.4). Autrement dit, $\mathfrak{B}=\left\{B_k,k=1,\dots ,6\right\}$ , tel que donné dans le tableau 4.1. Il n’existe qu’un seul tableau optimal, $B_2$ , ayant la valeur minimale de $d_{\infty }=0,5$ .

Tableau 4.1
Problème de sélection contrôlée de dimensions $3\times 3$, tableau optimal avec $d_{\infty }=0,5$ et les autres tableaux
Sommaire du tableau
Le tableau montre les résultats de Problème de sélection contrôlée de dimensions $3\times 3$, tableau optimal avec $d_{\infty }=0,5$ . Les données sont présentées selon Catégorie (titres de rangée) et $A$, ${{\displaystyle B}}_1$, ${{\displaystyle B}}_2$, ${{\displaystyle B}}_3$, ${{\displaystyle B}}_4$, ${{\displaystyle B}}_5$, et ${{\displaystyle B}}_6$ (figurant comme en-tête de colonne).

$A$	$B_1$	$B_2$	$B_3$	$B_4$	$B_5$	$B_6$
$$\begin{array}{ccc}\mathrm{0,8}& \mathrm{0,5}& \mathrm{0,7}\\ \mathrm{0,7}& \mathrm{0,8}& \mathrm{0,5}\\ \mathrm{0,5}& \mathrm{0,7}& \mathrm{0,8}\end{array}$$	$$\begin{array}{ccc}0& 1& 1\\ 1& 0& 1\\ 1& 1& 0\end{array}$$	$$\begin{array}{ccc}1& 0& 1\\ 1& 1& 0\\ 0& 1& 1\end{array}$$	$$\begin{array}{ccc}1& 1& 0\\ 0& 1& 1\\ 1& 0& 1\end{array}$$	$$\begin{array}{ccc}0& 1& 1\\ 1& 1& 0\\ 1& 0& 1\end{array}$$	$$\begin{array}{ccc}1& 0& 1\\ 0& 1& 1\\ 1& 1& 0\end{array}$$	$$\begin{array}{ccc}1& 1& 0\\ 1& 0& 1\\ 0& 1& 1\end{array}$$
$d_{\infty }$	0,8	0,5	0,7	0,8	0,8	0,8

2. Pour le problème 2.2, il existe 30 tableaux possibles, et trois tableaux optimaux illustrés au tableau 4.2.

Tableau 4.2
Tableaux optimaux de dimensions $4\times 4$ avec $d_{\infty }=0,6$

3. Pour le problème 2.3, il existe 141 tableaux possibles. Il y a six tableaux optimaux, ayant tous la même distance $d_{\infty }=0,6$ . L’un d’eux est illustré au tableau 4.3.

Tableau 4.3
Un des six tableaux optimaux avec $d_{\infty }=0,6$

4. Pour le problème 2.4, il existe 159 tableaux possibles et il n’y a qu’un seul tableau optimal donné au tableau 4.4.

Tableau 4.4
Tableau optimal de dimensions $5\times 5$ avec $d_{\infty }=0,517$

Par conséquent, en nous fondant sur la définition des tableaux optimaux, et sur le fait que $d_2$  et $d_{\infty }$  satisfont les axiomes (i), (ii) et (iii), nous proposons les spécifications suivantes (S1 et S2) de E1 et E2 des solutions optimales :

S1. La solution est basée sur les valeurs de la distance $d_2\left(d_{\infty }\right)$  entre $A$  et chaque tableau individuel $B_k$  dans $\mathfrak{B}$ .

S2. La solution maximise les probabilités de sélection des tableaux optimaux.

S1 et S2 représenteront les rudiments d’un nouvel algorithme présenté à la section 6, et à la section suivante, nous passons à la discussion des algorithmes antérieurs dans la perspective des solutions optimales.

Précédent | Suivant