THESE
présentée à
L'UN IVERSITE
PIERRE ET MAR 1ECU RIE (PARIS VI)
pour 1obtention du
DOCTORAT TROISIEME CYCLE
Spécialité: MATHEMATI QUES
APPLIQ VEES
Mention: STATI STIQUE
MATH E MATIQUE
par M. y AC 0 U B
GAFAR 0 U
Sujet de la thèse:
-
APPLIC.ATION
DE:
L'ANALVSE
FAc.;TO"R'ELL~
DES
GO'RRES -PoN DAN LES
AU
PROBLEM E
D E.S
RErRA'TE~
"'PA"R\\S \\C "-1$.
-
UN
"P"RO:&LE Me:
DE.
"'REc...H E"'R '-HE
OPE'RATIONNE.LLE : LES
:oec..ou'Pe:s
LIN~A'"RES
(UN
AL~OR\\THMe: NoU"e:AU: LAc. A F ) .
Soutenue le AB d~"c...... brc.. ..(f3:}8 devant la Commission
composée de: Prèsident
M.
D . .:où"ue:
Examinateurs: MM. _1. - 'P.
8 e: N 2.. e c, 'R \\
"R.
FAU'RE.
J.-L.
L.Au"RIe:~E

---

Je remercie Monsieur le Professeur D. DUGUE qui me
fait l'honneur de présider le jury de ma thèse.
Je suis très reconnaissant à Monsieur le Professeur
J.-P. BENZECRI de l'attention qu'il a bien voulu porter à mes
travaux, ainsi que des conseils et des encouragements qu'il
m'a prodigués régulièrement tout au long de mes études.
Je tiens à exprimer toute ma reconnaissance à
Monsieur R. FAURE, qui œ'a formé à la Recherche Opérationnelle;
je lui exprime ma gratitude pour l'intér8t qu'il a apporté à
ce travail, povr ses conseils précieax et pour avoir accepté
de participer au jury de cette thèse.
Je remercie très chaleureusement Monsieur Jean-Louis
LAURIERE qui a bien voulu, au j.gement de ce traVail, me
~rodiguer aimablement des conseils et participer au jury de
cette thèse.
Je n'oublierai pas tout ceux qui .'ont aidé et
encouragé, mes amis et en particalier mes camarades de
Strasbourg, de Paris et aussi ceux du Brésil.

---

T A BLE
DES
M A '1'- 1ER E S
Pages
INTRODUCTION.
• • •
.
.
.
.
•
• .
•
• •
• •
• •
• .
.
.
•
.
• • • •
PREMIERE PARTIE
Application de l'Analyse Factorielle des Corres-
pondances au problème des retraités parisiens •••
l
Introduction. •
• • • • • • •
A. Présentation et but de la recherche.
• • • •
B. Dépouillement de l' enqu3te ( échantillon observé ). • •
II
Etudes. • • • • •
. .
A. Introduction • •
. . . . . .
B. Questions. • •
• • • . • • • .
. . . • • •
C. Etudes classiques. .
• •
• • • • • • • •
Ao
D. Analyses multidimentionnelles • • • • • • • • •
. . .A 2..
- tableau et notation. •
• • • • • • •
.A3
- dépouillement. • • • •
• • • • • • • • • • • • •
A't-
1 • Tableau analysé.
• • • • • • • • •
.Ait
2. Dépouillement. • • •
• • • • • • • • •
Al+-
a) considérations générales
. • •.•
...14-
b) interprétation • • • • • • • •
•• •
.A~
- le_ plan • • •
• • •
.Ab
- les axes 1 et 2 • • • • •
. . . .A9
- enqu@teurs • • • •
020
- catégories socio - professionnelles
~..f
- 1ge - sexe. • • •
• • • • • •
lb
- remarque 1 • • • . . . . . . . . . .
~b
- remarque 2. •
.t,~
. . . .
Conclusion • • • . . . .
. . . .
. . . t9
Allnexe • • . . .
. . .
. . . . tSA...
Bibliographie • • • •
. . . . . . . .
3 .
... / ...

---

Pa.ges
DEUXIEME PARTIE
Un problème de recherche opérationnelle : les dé-
coupes linéaires ( un algorithme nouveau: Lagaf)
3-'1
1
Le problème posé. • • • • • • •
• •
• • •
3'L
A. Enoncé du problème • • • • • • • • • • • • • • • • • • •
31...
B. Les intéressés • • • • • • • • •
• • • • • • • •
33
n
Historique....
• • • • • • • • • •
• •
3r
A. Gilmore et Gomor,. ; Genuys • • •
. • • . • • • • • •
3,Ç
a) problème. • • • • • • • • • • •
• • • • • • • •
3S-
b) formulation mathématique. • • • • • • •
• • •
~~
B. Remarque.
Critiques • • • • • • • • • • • • •
· . . ~~
C. Re.arques.
• . .
. . .
. . . .
• . . . • .
~9
III
Heuristique personnelle • • • • • • •
. . . . . . 4-0
10 ) Premières approches • • • • • •
• • • • • •
• •
4- 0
A. Formulation 1 : en terme de"problèmes de partage".
40
B. Interprétation en terme de voyageurs de commerce.
4-lt
20 )
Problèmes de découmes "linéaires" •
• •
<.rs
~ Introduction • • •
· . .
~ Etude des bornes inférieures et supérieures et des
algorithmes qui s'y rattachent • • •
· .
1. Données. •
• • • • . • • • • • •
• •
2. Etude de la borne inférieure
1 •
.
· . .
a) longueur totale des demandes • • • · . .
b) exemple • • • • . . • • • •
· . . . .
c) interprétation • •
• • • . . . . . .
d) conclusion • • • • • . . . . . . .
3. Etude de la borne supérieure
50
Zoe
• • • •
a) introduction • • • • • •
S-o
. . . . . . • •
b) exemple. • •
• • • • • • • • •
S-....
· . .
c) heuristique du F. F. D•••
S'"~
• •
- principe • • • • • •
. . . . S1
cas pratique • • • • • • •
S-'t
S'":l
d) heuristique du F. F. D. Phélène.
- cas pratique • • • • •
S'3
5S"
- conclusion • • • • • •
· . .
!t Algorithme Lagaf.
• •
• • • • • • • . .
. . S""
1. Préliminaires.
• • • • • • • • • • . . . . . . S'"'-
... / ...

---

1~
1
1
1~
Pages
1
!!1
2. Algorithme proprement dit
si-
A. Exemple
•
• •
•
5"1-
1. construction de l'arbre •
•
s~
2. description de l'arbre. •
S"~
B. Arbre
analyse
•
'=0-4
•
•
•
C. Géntralisations • •
•
~S­
mise au point.
• •
•
•
~.ç
exemple.
•
b'-
D. AmélioratioR de la longueur Zo et opti-
misation.
•
•
•
•
E. Remarques •
•
•
•
•
IV
Conclusion
•
•
V
Annexes.
•
•
VI
Bibliographie.
•
•

---

l N T R 0 D li C T ION
Le travail q~e nous présentons ici se compose de deux
parties indépendantes.
La première est un sujet de statistique mathématique r
Application de l'Analyse factorielle des correspondances aux
problèmes des retraités parisiens.
Dans la seconde partie nous ~tudions un problème
de Recherche Opérationnelle : le problème de découpes linéaires.

---

5
PPENIf<:RE PARTIE
AP~LICATION D~ L'ANALYSE FACTORIELLE
D?S CORr~SP0N~ANCSS
AU
PROBLEME DES RETRAITES PAPTfIENS

---

,
1 - 1 N T R 0 DUC T ION
A)
Présentation et but de la recherche
Les données qui vont nous occuper proviennent d'une
enquête sur les retrai tés. I.e problème posé est de "saisir"
l'homme à la retraite, c'est-à-dire ses occupations, son
comportement, son
état psychologique, sa
vie. En un mot,
tout ce qui caractérise le
troisième âge : Est-ce un pro-
longement pur et simple de la vie menée jusqu'alors? Y-a-
t-il naissance d'un nouveau "personnage" avec des problèmes
spécifiques?
D'un pays à un autre, c1une rv.ga on '1. une autre,
les
problèmes sont différents. Au~si notre enquête ~,e limite-t-elle
à la région parisienne; et plus précisément aux retraités de
la C.R.I. de 1974.
Qui sont ces personnes de la
C.R.I. ?
Que leur
a-t-on demandé ?
B) Dépouillement de l'enqu~te (Echantillon observé)
Nos retraités d'origine parisienne sont des allocataires
de la "Caisse de Retraite 1nterentreprise Il : C.R.I. Ils ont été
interrogéE' oralement dans leur domicile "actuel ". Cela se passait
au printemps 1974. Pour
la plupart, ils ont cessé
de travailler
en 1970.
Ce sont en général de "jeunes" retraités: ils S:)'1t nés
autour ces années 1917, les femmes étant de trois à Quatre ans
plus jeunes. Leurs lieux de naissance sont assez variés : la ma-
jorité sont des provinces; les autres se répartiËsent entre la
... / ...

---

région parisienne, l'Afriaue du Nord et très peu des autres
pays de l'Europe.
L'enqu~te porte sur 342 mênages , dont ~O % de mari~s
et 20 % vivant seuls. On a ainsi vu 400 personnes. Cependant
notre ensemble des Individus dans le
"fichier" Individus x
variables, n'est pas fixé une fois pour toutes.
En effet, selon les questions notre échantillon se
divise de la manière suivantes
- La population entière
- L'ensemble des personnes présentes pendant l'enquête
- Les retraités au sens strict du mot : les personnes ayant
eu une activité rémunérée hors du foyer.
- Les ménages dont on choisit un membre, pJ.us les conjoints.
Malheureusement, certaines parties des dossiers sont narfois
inutilisables : mauvais codaf,e, mauvaise interprétation. Ce qui
ajoute à la "fluctuation" de l'échantillon.
A toutes ces personnes qu'a-t-on demandé?
Le questionnaire soumis au retraité se compose de neuf thèmes,
qui sont :
- Vie professionnelle
• formation
• carrière
m{tier : description, vie active.
- Passage l la retraite
• financier
• psychologique
• fln de carrière
- Santé
- Logement
• biographie, résidence
d
.
t·
)
•
escrl~ l0n
)
Logement actuel
• opinions
)
. . .1 ...

---

- Vie dans le auartier
- Relations avec Paris
- Occupations, loisirs
• Vie dans le logement
• occupations , distractions,
• vacanc es, résidenc es sec cndat r e s
- Relations
• familiales
)
sociales
)
• amicales
- Moral ( et psychologie)
En termes statistiques, le tableau analysé contient 342 oues-
tions. Selon que le conjoint était ou non nrésent, s'ajoutent
encore 76 autres. Naturellement, toutes ces questions ont
plusieurs~voire beaucoup/de modalités!
A travers toutes cette "batterie ll de questions person-
nelles
et communes (retraité + conjoint) , c o-unerrt arri vera-t-
on ~ cerner notre obj ct ? Que retiendrons-nous de t.a vie avant
la retraite/et de celle que l'homme parisien passe à son lieu
de retraite
?

---

II -
E T U DES
) Introduction
De l'ensemble du questionnaire, se détache un thème bien
pertiaent
: Moral et psychologique • Les autres questions,
Dour ainsi dire
sont des variables socio-administrative~, ou
bien, si on veut, elles décrivent un comportement "fig~",
ob,ervable de l'extérieur. La variable Moral, quant à elle,
présente deux degrés de distinction :
Le premier est qu'elle résume la vie du retraité:
on no peut la saisir sans discuter avec l'intfressé
lui-même; c'est son "moi" intime;
• Le second, tient du codage. Certes ici, le retraité
se juge lui-même.
Mais l'enquêteur lui ~ettra une
note de l'impre~sion que lui a fai~e le retraits.
En d'autres termes, il faut non seulement ~tre content
c~e fil' Lnt é r Leur-'! , Nais aussi C e t t e joie de vivre doit
se faire sentir. Elle doit être communicative.
) Questions
Ce thème l10ral et psychologique est apnelé "Code Neugarton".
Qu'est-ce aue c'est? C'est une série de cinq questions : ~,B,
C,D et E. Comme
cinq matières, chacune ~'elles prend des valeurs
de l à 5.
A
oppose l'enthousiasme et l'entrain à l'apathie. On
mesure par Al, AZ, A3, A4 et 45 l'échelle de valeur
du plaisir (ou déplaisir) que prend le retraité à vivre
les activités quotidiennes.
B: résolution, fermeté, force d'âme, déCision et courage •
.../ ...

---

"'<0
Est-on satisfait de sa vie ~ L'a-t-on dominée, ou bien
tout simplement, acceptêe,voire subie ~
c: Congruence : conformité entre les buts recherchés et les
buts atteints. A-t-on sinon atteint ce que l'en voulait,
d~ moins réussi les buts ~rincipaux ? La personne elle-
même juge sa réussite sociale
selon des normes ~ elle,
et non celles de la seciété
Dt
Quelle image a-t-on de soi, tant physique que psycholo-
gique ? Maitrise-t-on la situation ou bien
est-on ~ la
dérive, peu sar
de soi ?
E: Humeur: optimiste et "bon vivant" S'op"8osent à pessi-
miste et amer, en passant par indifférent.
C)
Etudes c18ssiQues
Une enqu~te générale menée aupr0s des retrait~s, à LOS
A)IG1~1SE, nous donne les réponses obtenues au Code Neugar t on ,
Aussi, dans un premier mouvement, avon~-nous comparé les deux
histogrammes: celui des Parisiens et
celui des Américains.
Total Code Neugarton
retraités
~I
améri
!
CUIlS
~ 1
/
~ 1
L
l'
~
1
retraités
parisiens
/1
1
-r-_ L
_
_
J _

---

\\!
rA> r:
1
p: Le ,c:ros lot des Parisiens semblent
beaucoup plus
llgeignardc " que l'ensemble, en moyenne, des Américains.
Cela s'expliquerait par la nature de l'Anglo-saxon : Le
1
l1Self made man", se préeente comme très dynamique. C'est
la personne aux mille projets : toujours pr~te à recommen-
1
cer, elle fait, se refait et se défait j elle se remet en
question à tout moment de son existence.
1
Nais regardant de plus près, les unes après les
autres, les questions composant ce code, oue co 'state-t-on ?
1
!
O n
01
5u/"~('rJDSe..
t"out-~s.
II~S. c.ourlo~s de.~ dl~f~re"'+e..S
~V.. .stIO"'S ~u(' li- $ ...,l:.rG.,+iS
o""'~V"; c.a.i",:'·
,,1
~~ ,-
-:
J
Q
/
-
1
»
-
/
A
Z
/
1
1
1
A
/
1
/
/
1
ILl
2
/
/
/
~
/
/
-,
/
Joie..
01 .. Vivre...
fp
..... '
;
p
(,"-odi.
N(.u'jQr rC'~)
La figure ci-dessus montre oue les moyennes fP oE'cillent
autour de
r A •
On neut aupsi regarder les pourcentages fournis par les
"tris à ulat" : (Cf. tableau ci-dessous) •
.../ ..

---

T
!questiolls ...,. A
B
C
D
E
(total)
raodalitiSl
en % . 1
~---_._-~--_ __
....•
.- - -
1
i
( 5)
:
17. r~,
16.5
17.9
7.1
4.7
1
1
w
t- '".
2
\\
4:
1
( 4)
1
32.9
37. i+
27.1
19.2
24.1
\\..Il
i
i/l
1
1
1
1
1
1
<3 )
1
34.0
21.0
40.6
42.2
4~.9
u
t.~
1
2
(2)
II.3
IS.2
7.8
18.9
16.3
u.J
1
t-
2
(1 )
4.3
6.9
[, • i+
TI. i+
11.8
CüNCLUS1cN
Les m~mes Questions appréhenderaient-elles des r(alités
différontes ? ou ce qui revient au m~me, l'enquêté Parisien enten-
drai t-il des concepts différents - de ceux de 'r.' Am' ricain - derrière
chaque notion ?
Remargue
Ici s'arrête notre comparaison des deux populations. Mais,
fortsà 0r remaroues précédentes, nous nOussons beaucoup plus en avant,
notre analyse sur lOG Parisiens
D)
- Analys~s G Itidimensionnelles
Cette observation~question ppr question, ou de tri8-~­
p Lat s "inombrables "} aboutit à un r6s;,;,r~,2 au "bon flair" de
l'analyste. ALS8i cette méthode d'étude demande-t-elle d'~tre
améliorée !
En ~'autres ter:::es,
nous allons prendre en compte l'ensemble
de toutes les questions (de ce code) : A, B, C, D,:;;. Certaines
. . .1 ...

---

de leurs
modalités
sont liées ou partiellement redondantes.
Mathématiquement, après recodage
disjonctif, chacun
de nos retraités est un point placé dans un espace ~.". Cet
espace '."1 est engendré par (5 x 5 - 1) vecteurs: e-i, , e~ , ... ,
e ~lo-
Le résumé au "flair"
r ov Len t
,\\ trouver un ensemble
de vecteurs f",
f2, , ... fp
où p e r t Detit : p = L, 2, 3 ;
TI ~
24 • Ces vecteurs ou axes factoriels sont des combinai-
sons linéaires
des ( ei , i = 1,2,•..). Ils eng endr-en t un
espace:X
qu'on veut" très peu différent" de W (au sens du
)(!
: minimisation de l'inertie non expliquée).
Cette c0nsidération de l'analyse de données comne
algorithme de réduction, nous l'utilisorons tout au long de
notre
étude.
r ABL':AU E'l' ;-.for::'Arrrmi
Remaroues
Al' A?, J\\.3' A
' A,_, sont en " intensités grandissantes".
4
De m8.e pour
B, C, D et E.
Bien oue pour chaque variable, A par exemple, les modalités
i , 2, 3, t, et 5 sont des notes d'intensité, nous avons pré-
féré un codage disjonctif.
A
B
r
3
2
~
0
1
0
0
0
1
0
0
0
>
l
l
5
1
0
0
0
0
0
0
0
0
l
-
- - - -
- -
-
-
- . - -
rdag e initial
Tableau recodé
.../ ...

---

Notons aussi qu'on aurait pu envisager de dédoubler le tableau
initial : aux "notes" A, B, C, D, et E opposer leurs compléments
à 5, A', B', CI, D, et E'.
Notre choix du tableau disjonctif complet a l'avantage de nous
permettre d'y ajouter, par exemple, les catégories socio-profession-
nelles. Et pourquoi pas, les codes des différents enqu~teurs !
"Par derrière la t3te", on aimerait aussi savoir ei ces deux
lots de variables - socio-professionnelles et " enqu~teurs " - sont
expliquées par les autres : ou les mettre en éléments supplémentai-
res.
DEPOUILLEMENT
1) Tableau analysé
(Enqu~teurs + CSP + Code Neugarton) x Individus
Dans la Il cuisine statistique " , nous avons été amenés à ilire
bien des opérations : supprimer certaines classes videe ; ras-
sembler certaines autres à cause du faible nombre de l'effectif.
Revoir le codage, mettre en éléments su~plémentaires etc •••
2) Dépouillement
a) Considérations générales
------------------------
statistiquement, comme il fallait s'y attendre de l'analyse d'un
tableau binaire, la part d'inertie extraite par les premiers
facteurs est "assez modeste" : il faut aller jusqu'au
douzième
pour obtenir 50 % de l'inertie totale.
Après les deux premiers facteurs, l'histogramme des valeurs
propres est régulier et "descend" très lentement •
.../ ...

---

Axes
Pourcentages
factoriels
-
FI
Io.6
'2
8.2
F
4.974
3
F
4.778
4
F
4.268
5
F6
4.880
Pourcentages d'inertie
(Histogramme des 6
expliqués par les 6 premiers
valeurs propres
facteurs de l'AFC
"correspondantes")
(Cf. remarques ci - dessous)
Modeste aussi est la qualité de représentation obtenue par ~es
7 premiers facteurs
ci-dessous, nous donnons les points les mieux
représentés.
Qualité de
Qualité de
Variables
Variable
représentation
représentation
Homme
7II
523
Femme
7II
590
549
662
538
578
549
647
579
565
____~'---
- - - U _ - - - - . . . 1 . - - - - - -
Tableau des points les mieux représentés
Remarg tles
Ces taux d'inertie faibles donnent une idée beaucoup trop
pessimiste de la part d'information extraite. En fait, dans
. . .1 . . .

---

l'analyse des tableaux sous forme de codage disjonctif, il convient
de considérer non les valeurs propres A0(
,
mais leur carré
r~ :::)..} · Les rI)(
correspondent à l'analyse du tableau BURT.
On sait qu'à un changement d'échelle près, le tableau BURT donne
les m@mes vecteurs. Et cela avec des pourcentages d'inertie diffé-
rents. La considération de ces nouveaux
pourcentages d'inertie se
justifie très simplement: ceux-ci s'accordent avec le cas limite
d'un codage continu des variables ; ainsi les"..o< donnent un pour-
centage
de
loin plus favorable qui est plus conforme aux faits.
(d'ailleurs le dépouillement ci-dessous sanctionnera très bien ces
dires, comme on le verra).
.
--- _
--
.._..
... _.. ---
-------~-_ ....------
_.. ' "1
-~.~-_.~-~
-.•.
Axes
Pourcentages
Pourcentage
factoriels
cumulés
-- ~--
--
FI
30 350
30 350
F
13 976
2
44 326
F
9.539
53 855
3
F
5 758
59 613
4
F
5 245
64 858
5
F6
4 807
69 665
Pourcentages d'inertie calculés à partir
du tableau BURT
b) !~!~EEE~!~!!2~
Le plan (1-2)
Le plan (1-2) explique "au mieux" les différentes
correspondances entre les variables. Ce plan extrait 18.5 %
de l'inertie dont 10.6
pour le premier axe.
Ici le nuage des points s'amasse en un croissant de lune,
c'est-à-dire que les facteurs 1 et 2 sont liés par une rela-
2
tion du second degré " du style " : y = ax
+ bx + c ; on
parle d'effet GUTTM~~.
... / ...

---

..- - - '-~----1
""O~I-z.o"JT... ,-l~)-- Alle: "E:~""Ic::.A,- (~) - _ T'ITIilE :1(E.,..QA,.,I"&S, c:.OJlI: "iEuC;AollTeN (~('u'- Le C.59 E'" EL'
~ltulf • :!..9~ &'cl+
H"'UT~Uj( = 3 .....~9QO - "Jo ..... "."-!!:
.Pc
l'o,,~'T!. = 45'
SU""Le"'~"'"",
._------
Fe.
--...,\\
----------------------~-+-----'-'----'
..... -~-+-.....-- ~-\\
'T--=~-
"-----
-
..
"
@
1
--_.- _._---
~""@
:, 1!>~: 1
"
'
1
... '
1 ,
~
:B.o4,:
, .,

---

ïiiii.....
"
_
....
- - _ , _ _ - , .
_ t À ~
•
'--------~
..........
,~'
-JI-
".
~
F'A
-
>~
i
l~jn
0't-~"
~~-------------------------"------------------------~---~---~-_!_-----~~-~---~---
._- - -
1
)
FI;
1
,
. .
~PI
"-.:- ---_:...:_.~- ..:..~.=-:-......:.--:-~:::=--
:~-t 'Ji ~ ::"E7:~ ~~::.r.r-:-
1
-',
l'S
~-=--"7 ~=--:~ --1
1
- - ---_._-~=--='-
1
f/7~
/
/
•. ~I'
P? t~.:~.-
-~
-'
--
rn
1
~,;.,,"
•
1
~Q.~-'';;~~';'-~--~-----------_.:.- - - ------------------ -------------------_: -----------------------------
ji---
- f t -
· n
mF-TZY"
R

---

AI
Ce croissant est "orienté" : on part des modalités de faible
intensité de toutes les variables
A, B,C,D, E - vers les plus
fortes. Le sommet de la parabole est occupé par les "modalités
moyennes".
(Cf. fig.)
)
____ .
----~ Cl >( e, 2,
~;
.-1 --
------ 1

---

A9
Regardons les projections sur les Qeux axes l et 2. On s'appuiera
sur les points les mieux représentés sur ces axes, c'est-à-dire
ceux dont le cosinus, dans cette analyse, sera» 0,2, ou bien,
ce qui
revient au m~me, les points qui auront une contributioD
> r 000
,
45
= 22 a la formatiqn de cet axe (car on a 45 variables
ou modalités de variable~
L'axe l : les points qui contribuent le plus à cet axe sont
Variables
CTR
Variables
CTR
contribution
Qs
23
B
64
5
Q
23
Cl
62
TECH
36
C
60
5
Al
40
Dl
70
A
51
2
57
D4
A
73
D
40
5
5
BI
53
El
76
B2
50
L'axe l apparait comme un axe d'intensité:
•
•
1
,
f
l
2
3
4
5
!L'axe 2
il oppose les moyens au groupe des "forts et très faibles".
. . .1 ...

---

Axe 2
,
1 1
1
l
,
l
,
f
,
1 5 5 1 1 5 5 2 5
2 4 2 3
En9u~teurs
On a craint, un mo.ent, que parmi les enqu~teurs certains
aient tendance à "noter" "haut" ou "bas". Cette crainte est non
justifiée : les points variables enquêteurs se répartissent égale-
ment et très près du centre de gravité G du nuage.
~
Ec..
~
G-
~
c..R
<:'AW'
l'
Autrement dit, dans l'ensemble, leur comportement est le m~me.
D'ailleurs une analyse faite en les mettant en éléments supplémen-
taires laisse le nuage pratiquement inchangé.

---

f§E
(catégorie socio-professionnelle)
L'Analyse
Factorielle des correspondances voudrait par une
représentation simultanée des nuages individus-variables, mettre,
à une homothétie près, tel individu au centre de gravité de l'en-
semble des variables qui le"caractérisent".
Ici le problème ne se pose pas : on étudie notre population
seulement par son comportement sur les variables. Les individus
sont purement "fictifs" ou "abstraits" ; c'est-à-dire qu'on se
place dans l'espace des individus: profil des variables. Les po-
sitions des variables les unes par rapport aux autres dét~rminent
leurs tendances.
Ainsi les techniciens viennent au haut de la hiérarchie,
avec les plus "grandes" qualités.
(
E S"
1>5"
~
lT€<~
'-.
AS
< ,--.,
-~'--_.
~.
I!.- 5
Cs
,\\
\\
1--
;
/
(
')
~----
--------.. - _._-
- '>
1
Reprenons la comparaison de notre échantillon à une salle
de classe: les variables A, B, C, D et E sont les différentes
matières.
Les meilleurs élèves sont les lesTechniciens
qui sont bons
dans toutes les matières : variables TECH, entourée des modalités
A , B ; C , D et E •
5
5
5
5
5
.../ ...

---

Le
technicien
parle
avec enthousiasme de son
passé
"Je le referai si c'était il. refaire" : A
•
5
Il Y a de quoi ! Sa profession lui a permis de tirer le
meilleur parti de lui-m~me. Il se fait facilement des amis et est
très heureux d'en parler. Il a fait de sa vie ce qu'il voulait,
en homme résolu, quoiqu'à la retraite, il se croit toujours très
utile.
A ce moral de fer, s'ajoute une Bolide santé: physiquement
bien portant. Ceci l'amène à être toujours de bonne humeur.
Les seconds de la classe sont les Q (qualifiés). En compa-
raison, leurs caractéristiques les plus voisines sont D et E •
4
4
Ils sont beaucoup attirés vers A
C
et B
que vers les autres
5,
5
5
modalités de ces variables A, B et C. En d'autres termes, ils sont
moins doués que les TECH pour les "matières " D et E. TECH et Q
se comportent, ~ns l'ensemble, de la même manière dans les'~at1~res"
A,
B et C.
Les Q reconnaissent yolontiers les deux faces de la vie.
Mais ils en prennent le bon c5té :
" Si vous cherchez le bon cô t ê de la vie, vous le trouverez".
Pendant l'entretien, ils apparaissent avoir des centres
d'intér~t bien précis, et parlent seulement de certaines périodes
de leur vie. Certes, des occasions leur ont passées sous le nez,
au
Q. Mais ils ma1triseBt les situations.
Ils saTent qu'avec r~gE\\LeursypossibilitésTont baisser.Ce tlODt les
"débrouillar~', cependant : "quant je prenrirai ma retraite, je n' au-
rai qu''à changer d'activités ", prévoient - ils t
OQ, ('QI et OP sont dans cet ordre les élèves "troisièmes",
en termes de rang, dans la classe. Ils ne sont pas ex-aequo : OQ
"se stabiliserait" à 3, tandis que OP regarde vers les 3 moins.
Ici, c'est l'indifférence, le " cinquante pour cent" (50 %):"
on le fait, pas plus ; on est là, sans plus ft.
Cette attitude de non engagé ne permet
ni satisfaction, ni
déception. On referait certains choses. On n'y met jamais toute son
énergie; on se sent diminué au fur et à mesure que l'âge avance:
. . .1 ...

---

t3
les années de retraite verront une perte sérieuse du statut social,
mais non totale. La santé va "couçi - couça". Ce sont les"occupants"
du sommet de la parabole.
1., bo~,» i
<.
/o-~ \\
(
'-
"\\
"
'/0 Q -1 '<..
• COMM, PS, QS. Les commerçants (COMM) regardent plus vers
la moyenne que vers le bas : attitude prudente. Le commerçant tra-
vaille beaucoup pour pas grand chose; mais il le fait. Il sent
une sérieuse différence entre sa vie de retraité et celle de quand
il avait 45 ans. Les occasions étaient très rares. Sa santé physique
est plutôt bien "entamée".
Avec 1& PS, la vie est bien monotone. Il a "travaillé
dur pour n'arriver à rien". Aussi voit-il d'un mauvais oeil les
années à venir. Il se dénigre m3me ; physiquement ça ne Va plus
il a pas mal de dépressioDs.
QS, quant à lui, il crot t porter tous les IDaux du monde l "la
vie ne vaut rien". Il est dépassé et se sent vieux. Pessimiste, il
a le sentiment de n'8tre plus qu'une charge sociale: "La
retraite,
r V~\\..
~mort sociale" , s'écrie ADne Guillemard. Physiquement, tout est
malade en lui. Quand on y ajoute le cafard, son lot habituel, ce
n'est pas étonnant qu'il se croit maudit sur terre et demande à en
finir.
(Pour ceux qui ont vu le film ou lu le roman, cela fait
penser à "La vie devant sol", d'Emile Ajar) •
. . .1 . . .

---

1
~!!
~~ ~- --- - +-~ --- ---
1
1
1
1
1
1
1
1
i1
w
Œl
!
x
w
~
Πrn10
V1
01
)(
d
z
2
LJ
0
(JI
4:
A
Z
.J
r
F[l
1
!
12::
1
1
®
l O~
~

---

rfl\\- (~)--AlCE. VEj(T 1c:.Al,. (.A)--"T'"TlI't; :~"T'1.A'TES :
c:.OJlE
N~c.Jc;A~T~""
2.l-1"I+2.
IolAlJTEU~ .. 3.1+'ll'3QO
-
NOMf1<C:E
J)f:
'POINTS
..
4S
---------.
- ~ ------
@/
~--._-
\\
@)\\
""\\
\\\\,
F'c.
\\\\
~~'.
\\
,
,
t
•
\\
~ -
---
m
' -
.............. _---~-
'111
Dt """\\
X}
/
/
1
"".~
~
:lU:
#, , '
/
1
/
ENq"CTauo«s _
1
c:.!-'P
C )
A~1t
c:::J
.liDI ,
CI
A
_..., " ...
I!l
.,.
'1AIr,AlSL.cJ
1
i
c.
0
./
:D
X-
i
e:
@
•

---

ifii,Tfu :fi ••ixr- v!fiyrnT1i~~m~c;iFm\\F ~'~l!t;'t1Tnl' .-J.
.. --
.__ ..
;!~:~!E'ij!~~:~~:~~~::~~:::~.~.~f_!·~: ..:......-:=~~.•..•---.-._~~.;:-~ _.._~~
. /
:io:
Pl Il •
.L.
- ;
\\
\\
1 \\ li4
@
~_.
-
=-
.:--~:\\.
- ~
' .
.~~--------------------------~~~---~~. ~--~~~-~-------_._-----------------------------------------.---.
,
; Ai
.F-~~~ ~
•
i
-=;~~'-._
<:)
[
'>.
1'1
-
fC~~W
1- .
1:
r:?
l'Il
(
rI
......--
.
•
5~
_.--,-- _~:ç------~----
------~-~
""'---...---~--_-----.---
~_ ._.ï
-,&. __ 5

---

Age-sexe
On analyse simultanément les plans (1-2) et
(1-3). Pour
l'âge, l'axe l est encore un axe d'intensité.
)
N9
N7
NO
La majorité de nos retraités est née en 1917. Aussi a-t-on
pris cette année comme origine: année 0 : 1917 (N7). On a fait
trois classes : les plus jeunes sont dans la classe NO et les plus
vieux N9 : nés avant 1917.
L'axe 2 oppose les vieux aux autres.
De plus
dans le plan (1-3), l'axe 3 oppose les deux ense_-
bles de groupes suivants
1er
TECH - Q - OQ
et
NO - N7
et
Hommes
(C.S.P.)
(âge)
2ème
OP - COMM - PS - QS
et
N9
et Femmes
Les
femmes sont plus âgées, et ont occupé les moins intéres-
santes
professions: QS, CüMM OP, OQI plutôt femmes de ménage.
1
!
Les hommes étaient par contre les TECH, Q
et OQ.
\\
!
Remarqlle l
llj
Le troisième axe,dans son ensemble, ara guère apporté de sur-
1
i
prise. Le nuage sur le plan ( 1 - 3 ) "reproduit" le graphe de la
11
3
courbe
Il
r
y • x •
/
Il'l
Il
1
t
1
1
1i
1
\\
Allure du nuage dans le plan ( l - 3 ).
i

---

li-
Reaarque 2
Nous nous sommes interessés jusqu'à présent à l'espace des
variables. Que donne le nuage des individus?
Pour cela, nous aVons projeté eD éléments s~pplémentaires tous
les individus. C'est-à-dire que nous avons fait la transformation
ci-dessous :
l
l _._-'>
r
1
,
'"Y\\.. '
,
~l~"-'L~~~
!;v Jo"(~""'c "+-:>,',,,,~;;
Si on désigne par l l'ensemble des individus, nous avons:
r = Il U
12
avec Il = 12
Quand on exaJlline ce aouveau "listing't ( ou nuage ), les indi-
vidus semblent se rassembler par catégorie socio-professionnelles.
Cela tendrait à prouver q~'il y a an comportement de groupe : les
retraités d'un m8me groupe social verraient, à la retraite, la vie
d'une m8me façon. Naturellement, la discrimination n'est pas aussi
prolloncée sur les"bords" : les "derniers" éléments d'une: classe
"empiètent" sur les premiers d'une autre. (Rous avons fait une classi-
fication automatique dont les résultats n'ont été qu'une confirmation
de ce que Doas attendions ).
Bo~s avons doIle encore utilisé ce c8té purement prévisionnel
de l'Analyse factorielle des eorrespondances. En mettant en éléments
supplémentaires les catégories socio - professionnelles, nous retrou-
vons toujours la mAme stabilité ( du Iluage ).
Ici on a
J = J1LJ J2
où
Jl = ensemble des variables de base
J2 = ensemble des variables supplémentaires

---

Ainsi, les différentes études, à savoir les analyses des
différents tableaux
•
11
)C.,
( J1 U J2 )
111 = ensemble des retraités
•
( 11 V
12 ) )(
J1
J1 :Il etllsemble des modalités
•
11
1<
J1
représentant les Tar1ables
socio - professionnelles
+ sexe
( + ellquitelll's )
aboutissent aux mftmes conclusions.
Que peut - on alors dire de la population des retraités?

---

i
CON C L li S ION
1!
1
La population du troisième âge connait exactement la
même discrimination que l'ensemble de la société. Le clivage est
toujours
le m~me : riche - moyen - pauvre, et homme - femme.
La jeunesse, quand on est vieux,semble être un bon atout. (Cepen-
dant, il faut être très réservé, œns les
conclusions sur l'âge:
nos retraités sont dans l'ensemble très jeunes.
Pourquoi, de l'étude, se détache t-il une catégorie plus
favorisâe ,
EnthousIasme, bonne jumeur, santé aussi bien physique
que morale semblent les distinguer des autres
Est-ce là une idée que l'on reçoit de par son éducation? Ou
bien cela serait-il tout simplement dO à la f8rmation de chacun ?
Singeant un proverbe français, ne pourrait-on pas dire à l'enfant
qui Ba!t : ft Dis-moi qui sont tes parents, je te dirais qui tu
,
seras "1
l1
1
1
1
1J
j,1
11
\\
\\
t

---

ANNEXE
Idée du fichier des données.
- Programmes de recodage
d'histogramme.
" Listings " de sortie de Bentab.
( variables
facteurs
contributions
qualité de représentation ).

---

---------~~~-==~.
.-.---- --~------
Z'!i 6
e51312381310011000722071~20J5333051132121011111123123C2611~320000000250310100212
0513231122COCùl0111211331~83031515320000000005721113~1008910c52~~5~~111133110000
05133~222223113005000~12111423323114143140114C1121117217501200111322110003110100
0513~232151111111113231313241211107701233311133111211003223030221J32~44433c521CO
0513511322312111055912111323220004211140071111111121221221249023290391233321 4000
0513bOOOOOOOOC~0000000000000COOOOOOOOOOOOOOOOOOOOCOOOO00000000000000000000000000
0514122~2310aC151000107242006322052133141912112100000100112430000000200320033212
051~231111C201'811121153212203233612329433251571?22413125~020212241~112532311000
051~33232313313001000011?1123113211413113403150101107213001290011214010531112200
051~~233000000~OùOOOOOoooc24133311870233141444111333322332233321232043~444?42200
05145233333133332339113213232100042221504524211111211100000010239151115444421000
05146621024999195~000311300000000000099100000099q909qo99999900099901999909900000
05151424134000106Q00110420006332042122142913214110001010012520000000009320030 413
051523112112011427121151223221031000021500001272223415005~0707325544233~31431000
05153313321122110100043549223131313111116003281101227220001353111112010332211300
0515~231100210000000131001332100100000221~14433111313222
311223221226033000253100
0515523333312411922112311323110002444352474121191221310000003013220312433331 6000
c515662214299919540009999101131990999991000000999999Q999 Q39900099929999909900000
05161239131000142000207141002332032123541011111100000200126232012710057000000112
0516232231002015141333514531010239528282222992722234110000C3C 3 3 25513111133240000
0516323331131130030003321131311921121330900090010240721200112002131211000132 2 200
0516411200COOOOOOOOOOOOO(10100211008509123222221111121002911133221230000000010200
0516522132312211055111921222020004242320100000003101110000005012122391332221200C
05166000000000 ooo 000000000 000000 0 0 0000 000000 ·)000 00 0 O~IO 00000 0 0 00 00 0 0000000 0000 OOc
05111240130001137045207141003333022123141011111110001030012530000009999420200313
05172300101001?82722333114631 31517121000000005723114410080040424221411143335200C
0517332322231130010002111111311331124311900190010121721800118001123211000211130C
0517412210C113C0000033132424210030570313342443331133100133132122~310441413C5210C
0517511233332C33043112221313110003441150734245~11321121221441013211111545442200C
0517bJOOOOOOoo~00000oooouoooooooooooooooooooooooooocaoOOOOOOOOOOOOOOOOOOOOOOOOOC
05181237339000126000207420006321052123142322111100000200012520000000051420030212
0518231111130115121231332211110423225282322111692134150023010126111311243232100C
0518342222~1223105667211152742~12312212022017801012070072C215002?23301000112110C
0518~12200cooonooooooOOOo031123211660512321112111121~21390COC02112~000001005310C
0518521112312~1115513331111323000491211165~2214111311100C0007312099393322321200C
0518661061~2~22~236671411000000580~1212000000c3212959331199~000111C13199929000CC
05191~23331002n7~0001065~053632202299914323221113321?031228122051030009000000312
0519231111C12018112131133501110426119535222213732124170022080821111721000201000C
05193~23201314J036687422167633213114~43060006C9312.373100C300092211101030111110C
0519~11110C21233331323322223210010990913391~~~111123100231000111?223~~~~143~120C
0519502112311211955910121321010003445145.6.1~111~031~1000C001023190311~23331500C
0519662085~1~33922687311~10123399091q323~4~~1~12113510123112000514514139431~333~
05211139231000161000207~3000732105213314112211110000010012332200903000900000021ê
052123110103101~1212311~?3221103?832128232131272?134110023070732~214111132~3300C
052134311111110001721212132131323113121100027301012072090c12~001121301000321330C
0521~332000000nCQo0000000010032203571~13311~~4332223322133123122231000333005310C
05215231122~101155991231131321000214115156~15342113941000C007013211111S~.542200C
052167107~~1~129237213113000C007~2~111300003033323351231332300011319~1311115~45~
Ob01113713~2001350002101.90063210222321~2122111110002060021732014010009000C0011ê
06012311210001(J~1212315~1~2101031362100000000172?1141~312301C13611121111311100CC
06013~32321123~1027J6212427723~121321110.00203010121720530220011133301000311130C
06C1~0110513b2~OOOo03333~~212100105503133311~~3111111002210002211930~1~23~05320C
0601521133312~11955911211213110004121120461121191231310000001013239221343~.1800C
0601661084~142?9237061231056333770113390~2~2~~3313251111231100021~5131319190000C
06021~403310001680002071~100632202212214122211110000C200022632025030070000000213
060223212111111612223134155303051512100000000572213411002~10051~~523112~123~100C
06023~21222111300~732313113231323114231200033101011072248C1375011231C1000121110C
0602~12300000000200000000033210010580~212~24~333122313323123?2221310~~~11~0~1~oC

---

c PG RE.CllDA-ÛL PaUR. --CaDt__ M:Uf4RI[~L
C
L ( l_:l1t..JAL1 ILS
.. _ _
__ _
__
r,
Ir~c() ~nfJ IDENTIE.lCATHH\\ Î
VALEURS EN HHE~SLIE
C
~.t~; l i,L-.J.Y l G:.JS
lw.iIlLlSAbLES
c..
~ib H\\lu :.lE RE re l.5_:.till .TIlTAL l ND. l- 2E Mt. Fe 1S NB l "D LTIL 1SAaLE S
c.er-:11eL~ L (15.)..LiliD..( 15+~LA, Z.-}4 1T, NBl NC~ ~1M
7~
READ_ (5.A 7611 LtlL.l--L-1.1,)
.;.t.'t-
uRlfu-b~··7b)'-l..!~l~ 1-1-)
9'
7 b F§Ht1A T (l t t 2 ~
-ila.
~iol1J.;~
---- - - -----.- .-
- l t ..
rlM.=-O- -
--
---_ .___ ___ _
_
-12-'
99 I"<[Au{5~2a.LENU~.).+lhQ("';)~ -1-~ 11)
. _~3.1
28 F eRtlA T ~ l 4~ 1 ,ü-ll.s.l1r:ÜLt-".-12/ # 45X#-11111 1. 7 CX~ 5 11'# J ê 1 )
--J..q;L-
~JB IllLaL.l.d-NO..l
-- ---
-
j,.~
9d CALL REC§D
_
. lb.!
ûGTti 9:3
-17·
SG9 t'iR l LE Ctu U NBl.ND__
_l~J
1 rO:·{tU.T(19)
19 ..
.-.RITECl)173)
_ZQ~
7.i Ftl[·d1ATClII~l)O-­
2l'
t~gINCatiü IND-t111 __
. 22'
hR l TE (tu l f NBIND..
23_'
"R l TE Cf.J1 1) NBIND_
2i,t'
f\\L..dl\\ 1) 18
25'
Utt 13 lal1NB4.D-
z.t~
- ~< EAQ!.1 ë 1Kl DL1J A.1 K l-'-K ~ 1.1 4 U 1
-21.
PlJLiCJ-I 2~.t KI D~_.{J À.(K) .l-K--l~ ~1:d
_
_2&~..
25 n)Rt'tAT(l~-,2xI__~6l.1J __.. _ . __
2.g~
13 r~R II!: C(JI 36) KliiLilA.(1Ù~K.i.l-4~ }
.3l} ,
. .itJ FGR!iA T, lx, I 'tLZXL~61 U
~31' i'lRlTEctlI73)
~~:
kb~lLC 15
De 14 r-11 ~.. BI~D
_.~~-­
kEAl,) 051 APJ K l DLtl A.LK l~K"ll 4.6)
35,
P~NC~ 35JAPIKID~(IA{K)JK=1146)
~6~-
~5 FaRMAT'Al/I3,2XL4~11)
37-.
14
I,R I TE (6~ 4b) AP ~ KIO~-(lA.{.i() IX-lI 46)
--3-8'-
46 FOPl1A T {--l ÀI A1~..lû2~éLll }
3S.te
ri RIT E ( CI '3 )
.WL
STC1P
4Üt._
fNu_
t -----
~----- -----
~- ----
~---- .
~---
-
r
- - -
r---
l---·-- .

---

r
'-
S\\,ÎL~f(t!L- TI rj[ f"ŒCüC
ce 1-1 ~1 rm L ( 15 ) 1 rr~ C ( 1~; ) 1 l A ( 7 j, ) 1 l T, Nb 1ND1 t1l",
Clr'Lt,Srer, AP(4)
JATA
(AreJ)/J:=1/4)J'A"
'13"
'C', 'U'I
J b
7 S i',:= 11 5",
7':J IA(K)=:
1-1..= ....
J8
d0J v=2, if)
lA:; r r,,1.) ( V )
Jll1...J-l
LL=LL+-L (...Jl )
IF(J.NE.4)GBTB 103
C
t'A 1SSAtKE.
Ix.lx-7
IF(IX).l.2 .. 23~15
1~ IX.J.
LJOTü 1CJ
23 li\\:=2
ueTli 10]
15 Ir(Ix,GT.2ü)GOTe 12
Il,:= j
E3 KI'.;aIX+LL
Ir'Ix.l~'~)GuT~ bOu
IF(IX'GT.L(~»G5Te 8eo
r J, ( r,K ) ;::
é<.L
CS~,TINl.J[
L. f~~,L.rŒ
: 1H;' .. lH~1 SUl. 1 M'I CSI AI 0 .. C, D.. l l T
C
v'lklF IC.ATltlt'-i Avt.c
lT.Set1tlE DES 1
l T• (;,
~e 7 K=1.15(;
7IT;;1;\\(t.i.IT
c
"RITE ((.11120) (H~O( 1) .. 1.1,11)1 (IA(K),K.1146), IT
2..; f· (j f"~.1 Î AT ( ~ X~ 1 Jt1 le; ( I 21 1.1.. ) 1 8 X, ~ 6 111 1À 1 1Jt )
IF(IT-~)44166166
'+ 't .. fd TL e01 G4 ) H., L. ( U
84 FeRMAT(/ .. l1XI'ATTE~TI~: '116)
Ilr1~1 (~* l
ûBTe 99
ct,;,
C{j~'-I TI t.. LL.
c
i, R1 TE ( L,.. 11 7 ) ( I~., C ( l ) , 1&-11 l i ) 1 ( 1 A( K ) 1 K& 11 46 )
11 7 F (j hl'. AT ~ ~ X, l 't 1 ., X.. 2 ( 1 1.1 1X) ~ 12.16 ( 1 X, Il ~ 1 1 ~h 46 1 1 )
I\\rr.;.I~4L( 1)
,J,rTE e lu lKI[;, (IA(Kl.lKa..ll ~6)
C
L.F,EP,1 IU~l
DEs
EL TS
SUPPLEMEtH/qRE.S
l.
r, /\\ K r.
: l,I\\ F1\\r:; eu
C
~U:'tJ[;Au[ POUR PASSEF': Tes LES INClvILJUS Et" SL-PPLEMt-.TAIRES : B~ LES A
L
P.U.U(;ES AVE.( AIE"
C.. O FRECEDAt\\iT L'1L1E.IHIFICATIBr-. CES If\\lC.(REMPLACANT
C
CI11~'~)' TA~ET ~~'A PAS L t5PTIôN
'IPRÔJETER U~IQLEME~T LES ELEMNT5
C
SLPPLU"f. TJ\\ 1RES' , •
Ir(KIG.G~'lCCC)GeT~ ~~
-.1 ~ 1
lie Te
991
1
3<+
IF ("'-ID'~['2:'CG )c/He 5.8-
l
-.1.2
::s::: _ .._
_
_
b~--5a--?:~tG~it!t~u71~--_~c~~. _-~~~-~-_
-
t--n -::-:-~ ~ë10-99-1-----
:
•
-
77 u;:'"
591 KID.KID-l0c~*(~·1)
hRITE(15)AP(...J),KID,tIA(K),K_1146)
99 KETURN
ç' r:, .

---

- - _ . - - -
2
....
8
' ,
""'"
'è
iw'
14
t'
f,
,e.0.. r -t.e,':>
-.lJ'~:D llJ ( ~ V ~
16
W'
mQ..L
c:..od ~fè.~ •
18
~'
70
' 0
~
L_
24
Iw'
~6
28
'w!
-30
('+2~
-...
42'+
."
ln2
lCOOüJJ1JG1JOJOOC~00QJClüOo1QOOCa108co10000100
-..
1~3
lCC0wC:~lclc~lJ~C~~~~CC10COJ~100G1C~CClCCDC10C
O ·
~-
lr.4
lCGOCOClJCG1COOlCococono1aC00100001:0COC100C10
1r-5
OCCl CCC:' 1-: 1 JL1CCCJo-oc~':::lCCC01-oI.JOol ~JG1GCCO-1.COO
16
1~6
OCC1GCCJllUO~Joo100000ao1CC001GOo10;OClC000010
1
~
lc:7
ù;:c1c.;c:: I1J.,j.10~lC0C~OC::'-001CC01Ù()CC
1.:CO 1 coco lac
i
78
lr-b
OCG1:;OCJIC1QIOC.o-UOco.OOolDOOOlnü001CJC1DCOOlOOO
1cs
acui.c Gec. lcl'.I.f~GlCCû.D-8 J::1 OCD011) COQ 1(. ::: 010-0 cere 0 0
1
~ 41.
1 H)'
cccocc ic 10ûL:1CMOO.o.oo.Lc.o..c.ol00G01c;or.10AlCOlCOO
i
--111~O-CC :1(; 1c.c..l-.:.10-0J..COCOC 1C.J-C l.oCCOO.1 :J.(}OO l";ç.c lOCCCClr;
L
; 4~
112
ccurcccc lC0l...10CD.o.oc.oO.o.e-C..1C-CD1.ouOQl 0(;01 ccooc 100
J.i3,)C iccr.c 1 ~l':'CiJOl-2.G-.JCDDC L.lOCCûlDGOOOC:C 1~OG01CQG
1
44
261
lCOOCC0101UOCOüo:ûoi000ûüOl_CCOO10DOc1coclCOCCl û
i
-21"2
1c.(;,GCCCl jL:;':'i,; ccccarccccc.icccoc 1 COO::; 1 ecce 1 OC10C
L 46
2(13
lOCQOCG1JC10LOQUCO-l0DOCC1Q0001G0001CC0010Q010C
I~
I 4~v8.,
2c~ ùlCDCCJ1JC1.lCl:J.C-Jl.illOQ2-o.1CQC01CQG1~C1GQOaCl-O
-- --
__2r5 C1CC;CCGC1C10cCOQ.01COGCaCD1000IG0001GCQDIQQOOQl
2~Li
)COOlJc1~11J.JLQC.l.cJLCi;JÜÜlQCOOo1QQOlJ(;.oc1.cOGC10
2r7
OCQ01CCC1C1Jl0CûCOCDGOCC1COOOléOOlûCCQ10000C10
i
1
2c:b
ocCl cc0(..11::' llL'O~'}C ~.JJOÛCC CDl 00 JO 1 cal :JCc10000IJC 1 Ù
r 5:'
2r:S
\\J~QQ0LUC ic: (;u08 l..OOQQCOC 1000001ÙOQC lQCOO 1000 100
1
2 i.c, _Ql.c..o.cCJ..:~1c., 100"':: 1CJ..:JJ.D:JGC 1 CCQQ.1COOO lecce 1000010
1
54
.a.t-1. ~lOLi.'::CQ1J010c..cc-o-cl.ü.c.eo.(101CC00.1LiCC01~coo10nOC10
~.
ZiZ
.ic c~OCi:: lCJ.1CG.G..O-1G.G(';f1C:C-1CCCC1.oLOOl ecceo.iocc 100
!
"r,.
:kl
_lCc.;cccLJ1C:.;coco.co.l000ùc.c.lOOOOloCcclcco1000010
13r2_1C-CO~CC-l J.C1...:.-::;c:o.c.1CQG~C-CUOC 1nG.-OO1 cccLeCccc laC
t'l".;8
3r-3
1 ecce CDG 1 cl 01 OCG.Coooooc1CC.CC 1 000-01 cc cl occciccc
,
3r.4
QCOûL le 1 ~c: L::LCo..c.lUOUO-C-lDCDOO-ICO-C lC~CC:: 100-0100
B',
a- S
0 lDDOCC lGG 1 ütJùC1C0C.-oOo..cCl1100 lQlJQO 100000 10.c.o100
jr 5i
3.l'é.l
L64
- _.0luneccCl.;lGl-Cr:(")c'c'CCCCCJo-i.JCCCci.ecceicccciocc.ioo
-
-
-

---

,iAFT tP1tor.P.iM~Ft4FJtJ7[C~'I~FTH('lnr e;TAT;e;TTOlJf
~rTQi TT~C; :rnn[ "rlJ(;a"'TF~
n .Nf
NJ .. ,~ ~Ù~
NF' tOQ L'r. tr:-r Own i~F' nuT ...i.T Tr:-S ,t,,~ Tr.g
4i1~
4'"
1
1
7
~
1:;
; 1:;
f')
;-7
n
1
1
1
l
Fi
_(1
;~
?,
..lil
"
F/\\
4'
~Q
~,
;.~W
.,
yn
1
71
"
0'
F
(
Q'
NO
(
10\\
,,;
III
"Q
i?1
p~
; 'J
M
lit,
nn
l~'
nO
,.,
Ol}
'1
171
n
10)
Tr:-t":H(
lQI
t:o__"'. ~O 1
~ï
"1
A~
?11
A'
?4'
i..
~I
.~
? I
Dl
?71
P?
il ?P)
A1
?Ql
P4
(
)0)
P5
1 )1 )
~l
;;1
0
111
h
'4'
~4
''''
;.~
1.1
"i
1 "Tl
n?
,(
'13)
n1
1QI
"4
1 40'
,,~
1 411
....,
1
"
(.~I
~?
41)
F1
44)
Fi,
,;")
F"
,<Q
?1'
i
n(j:~~iI~~.4"Fi .nl
1
- - - ~-:-:----- -- -- -- -~ .. - -- ---- -- ~_ .. - _ ...~- -- -
~~-._- ---- -- '='- - - -- -- -- - .. -- -- - ........ -- -- -- ---,' ---- _ ...- - - - - - - -- -- -- -- -- ---- -- - - ---- ---- -~ -- ---
'11'l~ JI ,.11 'r~
Fr
~ n
Fr.
.cp
r:AW
ln
~
r:-
~I)
~,7
NQ
1
pc;
ne;
nt")
I)P
(JO
t")
TrrH
-..------------,..---------.._.----------::J~-------••-----.......~-.....-..----..-------,-------'i----- -- -.........------ ---- --------------------- ---
PJCJJ
1
Qf').
'".
101:;.
\\17.
ln"
'9.
~.
" , .
,n,.
7'.
?1n.
12l.
1
47.
7"'.
"'4.
pe;.
4'-.
41.
3~. lAI".
::::::::::::::::::::::::::::::::::::::::::::::::::::::::~:::::::::~:::~:::::::::::i::::::::::::::::::::::::::: :::::::::::::::::::
N~jC:il.'- CO"II
Ai
A?
A)
A4••.. 45
.• Al
A?
01
~~.
A~
C l i C ?
0
C4
~~
rq
OZ
1))
------------------------..----P--------r-----------------r·---
~--------
·I..
..
...
...__ -.--------------------
~JfJ).
,
)4.
17.
4A..
14"'.
1'9,
14.
~Q.
,~.
Qft.
P:;;Q.
1n.
21.
i Jit. 114. 1111.
1e;.
SOit
1Q.
1.g0. 3"l~.
:::::::::::::::::::::::::::::::::::::;;::::::::::::~:.::::::::::::~::::~::~::::::::I'::::::::::::::::::::::::::::::::::::::::::::::
Nn~Jc.n ' .... n4
n..
~1
':"it
r:-1 ...... r:-4
•• r..
t:'e;9...
. . . _ .
-~----- ------•• ---- --- - ------ -- - ---"'-.r - ....-----~- - - - - ~~-- ---,..-- - -- -.-- -- ---- -- - 1- --- --- -- - - - - --- ----- - - - - -- ------ -- -------- ---
P.J(.JJ
1
Ae;.
3n.
I:;n.
liA.
1 Al. ...
ln2'.
~n.
n ,
'''''''.
1
TIRl FAU nr:-S VII FUQe; PltnPDlr" !T nr.~ VFr-Tlr""t; ~qnPf:We;
,
:~~~~:~:~;~:~~~~~~:~:~:~~~:~~~~~~:~~!:~~:~~~:~:~:~~~:~~~I~:~;~:~~~~:~I:~:~~~:~~~~~~:~:~:~~~::~~~;~:~:~:~~~:~~~~~:~:~:
V'éT,Ù.~1
J.gnnnoiqi
1
.4;>4AM ....
1
.. )t~-l.'~?
1
·.!q8Cl1l~q,
1
.lq1lZ811 Il
.170nO.4
1
.)"511117.1
1
.14A04640)
1
n~.lFT
11
- ...11i,e;74A'
1
.n"'j'\\Q~n,.,n,
-.ll~·91A""
1
.. n~C;Q~l'Q
1
- •.1nC;11434
r
.1'4n"q~
!
-.1 01'PIIioC;7
!
.it4~1Iio7"34
1
OlllJ'T
?I
-.qq?qq.,,,
1
•••• "Q.,'
1
.O~~I"TQ
•
- .. ~T4"q6q~
1
.'Q.)q5~'
•
-.,?n?Q.?7
1
-.04QIII~1II7.
1
.lq<jI?"14T
1
nAlJF'T
1t
-.tnAIIioQit""
.n,,.,.. e;c:itit
1
-.01i7C;'4'~
?
-.n~l,.q"11
1
.nn'\\Al1lil
1
-.n140'tn~
1
-.,on~"'1.?3
1
•• 4MIIl7Q-;~
t
OIitJ"
41
-.17"10;.4
- . . .",lIIli..
.1";,Tn""
~.~l?q:>o" 1
.0.""0."
1
.nO•• 7.q
1
.,n44".23
1
-.0"0.4841
nAJFY
~I
-.1.,4Q?1?
- •• 7?n1.,q
-.OqQ,,,,,4
.lnOQ.4.
-.OTOT"0.7
1
-.?1.,,4'1
1
.lnql7.7~
1
.noq))z••
noJn
••
-.0.T\\75.1
-.04?lA41115
.~Olllnllll,i
_.!1II4~'iI.i
-.~0Iq4qOQ
1
.n44.,A.0
1
-.lnIll06??1
1
.1399.277
nR,."T
71
-.n411io7A71l
-.nitn'7n~A
_.00,,"A14
.1n1'..,C;1'
.1''''470'10
f
-.OQ1Q4)e;o
,
-.1c.it-;IIn7l
1
-.~2'74J2lq
OI\\.Jf'T
1111
-.P417.0IT
.0"T~4Q;n
-.054l1'''OQ
~·.117,,7"71
-.?7.955"7'
.017.7717
1
•• 4qATl?,
1
.0127956?
nRJFT
QI
-.?ilQe;nflt;»e;
-.n~n"'1"''''7
'.OIll'''C;""
."4';nC;c;n
.itRq .... l..,"'Q'
-
-.nCi21i~QbA
l t n l A I I \\ Q , , . .
1
-.Ol)4743~
OA.Jf'T iOI
-.1J.)lïT.
..?Q"""l"
•• I ••;6M4
•• 0111'0"1.
.oiO"2T4~
1
.1?P9""
-.nQA""ZI
1
-.4605.70)
(uÎl.t'T 111
-.'411i.C;n4A.'"
.n;»ql,~7C;
'.n"'4ï4',1Iio
.';'70QQQ.,
-.n~A'\\02"n
(-.it1QQ7440
.n:"170it70
.IQ4C;S24A
"".1FT p l
-.jTIIIO.9A9
-.D.'4'411
- .•OO'ri:>T?>
- .. ~4"lï"7
.0'0.")1'
1
.?0"1l~~
.n1nZ",ZO
.Ollq.T4)1l
OAJFT 1'1
-.IIDqAOOQ
-.O •• 'IOQ~
• no 11 ...09Q
.?Q4Q.0".
.1~0754.~
1
-.???~?4~?
-.1?47Q740
-.00?10951
/lII,!!'T )41
-.I.ll~TIII
-.1"?~14~'"
.o,,~o!••"
.• n.4S?".
- •.,'''.901'
1
.ln90147q
.n.56,n.6
.10?7?)18
f'JAJfT
It;1
-.l;»Qc,nc;;ln
.nlliln"l.ll
.n..,itn'4"'7
_."Qlo.444",
-,."QC;l?~;t
1
-.nA'QQ7Ql
-.n'404f1.77
-.01";»1'1)1
~Jn 1"1
·.14Q?471T
-.O?' 1Q'04
.. 00!l90~Q
.~,o;Q1n?
.j 7~e;86?5
.ln""I))
-. l?"IJQ92
.OQ91789T
n'~q~T 1!1
-.lft7J7Q7'
.n'5",?.,n4
.OIlio11"Qe;II
... ll;»..,' ....Ii.,.
.1'14QnI:;7
.nI:;4'\\Ot.n4
-.n41li7""'Z
-.74nllll164
(lRJn 11111
-.IO'.'I".A
.1"'774"
-,O.'HI"14
~ .•1004.?1?
-.~0.19Q'4
-.IQT,,)909
.?"q77"ZO
-.05)75030
nA.~T I~I
-.nQitQ04;»1
.1AQI:;0,C.t;
-.71.,n4;»Ql
-.nn~A"71t.
".l~qlZq~~
.1"lQln1 13
-.n,nS~?'-J
-.073,077ft
OAJfT in,
-.n94,Q'4i1
-.n-;7liC;cnl
.01","8,.;»
-'.11n4C; __ ""
-.11."7'''''
.n'li7non3
.n1A.l1.7"'1
.lI1itt;A27
nA.JFT iil
-.0~~7411io4~
-.itoi"l3ifo
_.;»..,;'t1I;»"'~
:.1';n4liQllIIo
.;;ft41"~;»'
.1'7A",711
-.nQillnQC;"
.n"'1"7A74
o.,J:! lli
-.il?I".).
-.?1AQI?4~
-.P!lMDQ
.. Q174Q9~"
-.n.S.8)?1
-.191~?1~4
.,nQ~.AO'
-.00lll3T461
OA,J"T ~1t
-.J91i-.nit'~
-,.l'J41AAnn;>>
.lQ'Ânt;7A
_,.1"~~~"74
-."4411!)~
-.nl,.,74t:;;14
-.'1-.,);»C;3
.OOA5~224
OAJn ?~I·
-,1'10111""".
.n"QIAQ~9
.13All'l.9?
.n6"47)~?
.l Q??8T'0
.07?4?C;Q
.?~23144C;
-.033011154
l')PJ'T ;'';1
-.ï1Q,t;II113
.''''0'F1~4~
;;.;?':;)5,,:>4
·.l01'4;'l,:.
.nnA"73.,Q
-.nn",71.471
.nc.4QO..,37
.OA2'IQ9421
Ci P8J;T ?"I
-.' 0.71 754Q
-.?'01l •• 1
~l.~jV.A
-,P.~.?'.
.!p'?1n
. . . . , •• ?O
-."IOZT88
-.01'8<I.Z.'
nIllJJ"T ".,..
-.L~11'4~1
~;.""IIioQ\\l~
=.tI',=~n~4
.1 '~1QI ~
.... '~~1
-.1 q"Q.,QOI
-.n374n'43
-.Oï2'IQ"2f1
~.
-.Q";QOO7,T
;a;.OÏ!J;T !III' -.1~'~740"
• "1 ~~097i
.• ~71"i ?')
-.nnnl0A7~ ~
.II3AQ41Q#!
.it'7'4022
.1174",)87()"
.1
. ,J[ T ;»QI
".lnt.l?~Cil
~Q~4C:"
.1 '~QI q~A
-. 1~OQl ~~4
.1~~731~1
-.1 n'Ii~IQO
-.113~~1.":-1
- ••• ?510)1
.
..
"
-.13".40")
.71i'''1C:7~
•• 74' it,.Q4C;
~·T '".
..~ i 1Q!1II4?~
-.074045"4
.1 on11101 0
.I1QIIQIi724
.0'930994
-.il40410o,
':'·.;»7;,~..,.it4
... n~on"1'"
.1""'"97"7
-.nil"'C;itnC;5
.l1n77c;t.O 1
.05107Z41
-.i:-OQ91,.,4
d";~ ~~: ::~~~~~:~
-'.oOTi"",,7
~ 'I,~;III"'
-. '~"254Qi?
-.'711"e;frtQ8
-.1" ....'QQ)4
.n?7~'724
f\\JlIJFT "1
-.ill ,~'''o~
-.tl7C;1Iioe;1:;,;»
.1~71IQ"
• 11 71ll;»77,
• "n'~Q"AP
.1~1"1?1
.itl.)40Q75
-.n?"?479~
nil,ln";'l
-.i7';,~ïQ9
."AQnI3AA"
.10io~III'.
: .. 11.7)42j
.IA'4l41,..
-.";»lilA41~
- ."Q~~~it)3
.103fl520?
noJET '0;1
-o\\4.'Q}7.
.;4e;"A~",7
~.. lq~~.'?1
- .. n~"'L-;Oit4
-.''''it';»1}11
-.nnlio'\\?itllio
.! 04 071)e;
-.23904Iq?
OIIJf:T , . ,
-.1144""';>
-.~AlIionAI3~~
-.Z611.,,)0
: .. ?nO~"fII;
• 1n 1"3~9~
.OA70;»7~7
.nM?1009
.0"."417
n~.'ET'7I
-.)4'"011~
-.1 ~1 A;»,,,,l.
·.07"Qitt1~Q
.•it7nlAe;itQ
-. ~it19A7"'"
-. i "n~n t n1
• 1e;A..,;» 745
-.0~7)7)~)
GIlA' 3111'
-.~11Io.'11
.on:ln4 c"l3
.n'.T4?)
-:. ~~Qn4'lio
.ne;,j:llq711io
01471479)
-.IT64'486
-.0;>01604T
.~oIET ~91
-.14Q?47.~
.;'''''1341'''
_'. nfr.A;;~~~4
-.177111io",'0
.1"11 ).?
-.'A.71Ql1n;»
• 1"'1 oon,."
-.044"147
"""ltT tRI
-.' p~ ••••~1II
.?n"n'UI7~
~.~?·?&??t1
. ,'4·lln~
-. 1 ' ....c;03i?~
.'04Q-770
-.!An"I)?
.1"10'95.
OR.IFT tJ 1
-.1144.71.
-.'1'''''4nc.1.
-.?1419!0.
_.• n""·'''1 q
."nOQ11?
-.onlQf')lnl
• 'lQIi"~..)Q)
.nl"'Q340-'
-.Ic'II)nc;IIioC:;»
of,T ~",
-.n14QnlllO
.•0)_1 9,01
.n'f'i'.:;"cn
-. ""l. 1),.liO
.J!I.!JFT.,.
-.?IQ"0~11
1:
.O'~44~12'
.on7A?1 ])
-.n5~266
• n;te; 7i1'n4
.lQQ,Cin.4
:.nl:;~c;'A1':'
-.n,.,C;7I1A40
• nAQD~41 0
-.lnqJ4l)43
i.J'"
~.I
-.I",.Q;>.?
-~0.~?11II51
~,. 0401OQ~i
-.0941'814
,."t,n4jl10Q
.?n71"5Q6
1
-.17"'."1
.)3Ab?371
.10'~17
""-1fT ."1
-.07?'95.0
.""'""'~P"'''
-.;»n7n'lilA
• ;»C;11?"1i'
-.0f\\?1715"
.n'7"'711)4"
-,.1411t;Ql97
-'f ' " ....
VA' Ilh·j
,·~I"'.. POnp.....
.;"~l'\\nitlQl
.OQ'109e;5
1
1

---

. .
.....• • • • •
. . . . . : . .
. .
_ _
o
_
~
~
. - . . . _ ~
1d0llll0"
'1':;'
!';";"'~'~'''''''''''''''''"'~--'''''~'-'''--
----------------------------------------------------------------------------------------------------------------------------------
!M~ !iT~D , V~I_ ppnp~f
Dnt IlJ(, •• 'T'
r11U111
! 0 ~
Hl<;T("Ir.p~ .. '-4~
~<-<; VAl ,"V<:' pr~'1D""" ~ ,'c 1 t
-'AT01('1'
---------------------------------------------------------------------------------------------------------------------.------------
? !
O!
.~?4Pf,(\\Of_!
]n.F-.'?l!
ln."'i'l
!oflo~ .. UO ..... ·IH:H.ctOOOOct!""~Qu<Qooooo~oo
• • • !v..,..-o,oooouooooo*1 ()OOOOCHHHt."OOOUU
1 !
l '
.11~in1~~!
7.on~ ~
iq.~'?4 !~IO*OOO.~*ooOOOO*!4.UOO.O~~ouo~UOOOO!O~~406~~O~Ooot~o;
4 !
f'l!
.1QAOI..C:::Ql!
4 . 0 7 4
~
:>'.411~ !tt'o~OO*U.l)OO~OO.O*~~.U.OO*O,UOUOOO
~!
? !
.1<111?Q1)!
1.... 77,:1'
.,q.~7/-.
~01*OOOOOOOO<)06000100
.. 00 • .I)OOUOU(H,.
f.,!
1 !
.17n7?nf,4!
4.;>1;,:1!
.,..,.t;,44
!OIO.q.oooooooo~oo.O!~~oo.ooo.(!.o
7 !
1 !
.1~~1~7~]!
1.QRn
~
'~.~?1 !O!o.oooo.~o*ooo.O!~uo.oo*
I l !
1 !
.. 141l04<'43!
1.70)!
;'0;.1;:>4
!"'''
"''"
"
!"
",, ..
Q
t
1 !
.14e;.,E;4A7!
1.1,14
~
41.7Cict
!O!o
oa- .. ooo
uo .. OO!~
ooo
l n !
? !
~11Q~7Q77!
~.4QQ
Z7.~4~ !O,
fto
oo~~O~OO!~.. o.o
1 1 !
? !
~11SQC;Q~1!
1.~CQ
~~.~4~ !~!OOO~
~fl ...... *~OO!~~Oô
1?!
1 !
.1,?~pc;494!
1.n~~
~'.74~ !OIOOOOUOOOÔ.*OO"'O!~O
1~!
? !
.1?11?~47!
~.(\\?Q
~".771
!O'oo.ooo ......... .,*ooo .. !UO
' 4 !
~ t
~il~Q411~!
'.QQQ
~o.I..~Q !O,
oo*Oô
OO!OUO
le;.'
,
.1nQnQnFq!
").7?7
~':Ii.1Q7
!ft~.ft• • *oooooo
oo!
I~!
?
.lnRl7A91!
:>.704
ë:.l0l
, .. ,
"",,
,,!
1'1!
l
.1"1~;:,n71!
'>.t:.Qn
1;7.I;Q1
!OI
O.OO~H) ~oOOOOô!
IR!
i
.ln14;:>;:>19'
;>.~~~
7n.:>;:>7
' ' ' ' " .. "" .. ""
"
lQ,
4
.iOnR~n14'
;>.~;:>J'
~;.74A !"'''''''"
" .. " .. "
"
;:>n!
?
:.nQ47)054!
?V-,,"
,
70;.11<'
!"!"
"
" .. "
..
? l '
?
.nQ;:><.;:>n"~
:>.·lJ~!
7-7.411
, .. , .. " .. ""
"" ..
:>;:>!
?
."q4C;A~?O
:>.1I<;!
:;O.~/o'" !",."...... ""
"
..
;:>:\\!
1
.nq?~...7A/o
:>.l'~O!
QI .... n~ ! ",
""".. "" .. ,,
..
;:>4'
;:>
.II1<;C;Q;:>RR
\\.A911'
A;.40<;
! .. ,
" .. "
..
.,~!
,
·.n7'Q47~1
1·.A4Q!
QC:.144! O! O • • • OU"'ofloOO
;:>",
1
;:>,
0.II7n07~(14
1 • .,<:?!
A7°.nQ~ ''', .. " .. "'',, e e e e.
; ) 7 '
? !
.n~7R.~Qt;u
l .~ql;
1
QQ. "JQ?
! O!*.oo .. *o~~o
;>Q'
4 '
o. ""'4~"4Q7
1
l ~!
<:>;".411",
l"! "
" .. "
='0
1
1 !
.~~nn7~?"!
l.t;!";>!
n' .onA !O,*.oa-*u·~c·
'111'
1 !
.n<;7\\70p.2!
'.4:>Q'
O'l. ~"7
! .. ,
"
1 1 !
? !
'.rtCj;?nnOQh!
1.1"O!
oZ.~,~ !O!uoooo~*
' l ? '
;>!
."474<:Q7"',
1.1"""
CI".";:>/o
l''''''HI''''''''
" !
? !
.~h"~~'0?!
1."14'
n~.Q'~ !O!OOOOO~
' 4 !
1
."17QC:7 Q l
1
.Q4q
t
O"J.7~7
IO!tIo~-a-O-lj.
,e:;'
?
.1l41C;"lQ
t
. Q t ; 4 '
nQ.~41 !oCH0004Ht
1""
;>
.";:>11 0 1 '- 7 6
'
.7;>11'
"<"l.~""
!"'"''''''
~7!
1
.~:>~'S.."!'J'~ ~_
....'l0! ','''.''nll , .. , .... " ..
'lA'
i
-.lIn(\\(\\0(125!
-.000
1
11I1I.lInn
! .. ,
'0
t
?
-.n~Onnn4~!
_.nnn!
l~~~nnn !*!
4(1'
;:>
-.IIII(lO(lM'I?!
- . " n n ! , nn.nnn
!"!
4 \\ '
4
-."lInOol n ? ,
-.0'1"!
,oo .. nnll
! .. ,
4 ? '
4
-.IIOOOn14\\!
-.OOO!
111".I\\On
, .. !
~1!
:>
_.nllllno\\~;:>!
_."'1 0
,
lno.l'nn
!"!
44
1
"
-.nlllll)n~1q,
_.1I01l!
Inn~nnn , .. ,
!
l.~
1
n !
_."n('\\nn~7:'\\!
_."nn!
lnn.nn(\\
!Ol
l----.----.--------.-~--.--------------.--------------
0 -
0
•
• •
•
0
-
l:'&
~
.n

---

~._I
.....
""H
*
*I.rtri~""·~
1t'
P '
:tlli
?:fi>,,'
*
_ ..• **.....--,.......~""
1----~-~~-;-~f~~~ji-;;~7--~;;--;~~-~;~7--;;;--~~~-~;~7--;;;--;~~-~~7--=;;--;~~-~;~;--~;;--;~~-~;~;--~;;--~~~-~;;7--;;;--;~~-~;~,~
____
.
o
.~
.-------------o-------------~o--------------*
~_.
0
_
l!~A
1 2 c t 4 " 4
2?1
?c;o
1"
4!
-41'1
4~
11!
'"4
':11 -3l)'l
;>4
111
1~1
3<;
lAI
-490
f,<;
:'l7!
~I!\\
10.)
l'-1I
;>!f";;
l
"fiCi
0
261
4~7
1"
41
io"
3
1!
':'.';'7
11
~'"
Q14
71
3f<!-14;>:)
171
101!
-?10
4
?I
A;>4
<;7
401
31"'li\\_L.)9H-l2
2S!
qQ
1
IH
-;>9?
._ll
11
.:.!~!'
;>
~1
15
0
01
-<;1')
0
O!
-flol
<;7
3('I-l"<;R
:'l?72191
4Î;r.-T-4~q-·'\\j -;>"o!
-10
0
'"
<;11
110
;>CII
-1;>
0
III
lf,4
10
41
f,<;A
lf,<;
7R
f,Re;
179
931
-110
e;
31
5IlO __ ct~~~]7 '?11 -?"Ft
;>"
s!
-141
:\\'Y
lO!
.1!1~
10
t:31
~?11'
14
f>1
-5"1
107
'51
ï'''''
è2
1?1
2?
0
01
"!rAW
!
Je;1
R
2~! -314
7
::"
'51'>~
;>4
'II
::-04;>
,,<;
~~! -41(\\
12
7!?1?
1
» -4A7
IR
I;>!
1'>1"
;>R
?n!
7J!nc:-1-~c::}::_"'"Z1! -;>9'$
;>
IH
~40
0
n!
!~0'5
19
n !
1.('1.
33
l'l'
-P?O
11
"-nI;>
l1
;>3!-101(1
70
'5?!
RIH
1 711
e;R
13!
lc;e;
?7
"-1'111
;>1
4!
-0:::,,<;
1111
1~1!
-40 ...
~74
76
'0
1
0
III
7
?I
?O
n
0
..\\lJf_~-J=ZlL,_~'}
is: -171
;>7
fI
lCi4
?1
_4!
"51'
.111
lf?1
<;<;;>
';)74
1\\4
-"
1
0
-RO
7
1!
-??
0
0
10!~10
! 410
1 0
?3!
110
4
l '
-4?<;
"'"
111
?7
0
-01
:n
0
0
:'\\A"
11
17
-;>Rn
1"
In!-pp.n
141
;>1?
1l,iIt11:lf1.
~(I
131
7"
7
1!
1,,7
?"
4!
C;1
:\\
~11
-40
3
1
-1M
1";>
4R
<;4
3
1!
'305
110
,R
1~!",q T fi~ -"~.?
20f -?1ï
n
4'':';>;>
0
n!
':,1';)
<;
~"-"
7"
~
1
471
ACl
41
"7
;>
1!
lQ:'l
"
Il
ljofPs' t ~F.
l ' ; ? S 1 -Soc;
~;>
:;!
17
0
01
1; ",.
17"
~7 1
"?,
49
?~
-Rn
RFt
50
-44?
24
1 f,!
-"
0
(l
14-,0';
f ;>OQ
;>0
23!
-7(\\4
lno
;>.1
;>;,
Iii
1!
i41
4
=;>!
-4;>0
30
18
V';)
';):'\\
I;>
lR:'\\
7
4!
?AO
17
Il
~i"i~! ,'nt
·11-1-4!
7Ft
ï
n' ;>Ft9
1.
41-1'''"
';)4'3 fi.:;1 -40;>
29
14
-?"7
, .
7
-4';)
0
O!
-?r:;11
12
A
îl'>Tno
!
f(;;'--;>;>
n !
-q;'
;>
Ô'
1Ci
0
ili
;'i!7
~1
=Q!
c;n"
(,5
jLJ
1<;4
,1
1"
_:\\?O
;>7
l''!
';)""
II',
10
l7!nQ
1 l~QtI
l~
251
?1'"
0:::
i!
nI
SI
11
4"11
';)e;
i11
701-
e;R
30
;>0'0
e;
3
-1"';)
1
;>!
-<\\"1
RI;
5R
fA!'"
I j M " n
~S!
0"1
QO
;>-l'
-;>47
7
;.!
':'4"
';)0
lO!
-?e;
0
0
-7A"
M.,
39
9P7
104
f,71
-100
4
:\\
lQlrrOH _:';~_"q l6! 13;>q
, 4Q
J~!':'l ?A7
ÏAD
4~ 1
':'.7
0
~ 1] 1 -7p.o
53
<'l'I
C;II"
?Q
17
-44
n
0
-,04
~
'1
-~()!rniiM! 114 -- q
?(,j
-"II'>;>
1 î
-l,
OQ
-' ï
n!
':'';;>;
'4
l;>!
-e;e;1'
z«
14
'1""
»
1
I<;Q
»
1
RRf,
Ml
47!
2h~j
f c;l;"Q
tt
:rr!-lCJFt4t
,,,'
4,;!-;>?06
,~ "Q!-ïonc;
42
j31
1337
75
"2
i lnl
e;1
37
-'541
1?
"
3<;"
'5
'"
??IÎÎ?
f-420- -1'-
?'i!-13R7
;>4"
C;7!
-I;71-t;Q
lRI
14Q
1
':'1!
-1,.
14
7
-70C;
l'-4
H
:'lRe;
10
Il'
-'1"
15
IOr"
nt""ijtC~~ -PH -;'14«;
t i
;.!
S'i'f-:C-H,1l
''11 ''';;4?
11
i l l -47R
1?1
46
-34
1
n
-f,37
?}4 1(\\0
17
0
O!
;>4164
"1-3'>4
16
19!
-"0;>
;>n
4!
i.nq--'~? 101
ï"-1
il
~-4!
44n
95
37
157
ï;>
c;.
5?i
i a>
f,4
-f,f:.
2
11
25-I~-.".h~9
~- 231 lZl'il
3:\\"
7-l1
-qn!r "m, «;t!
1?t.
'7 i\\Dl
?,.
6
0
-IQ
0
01
155
5
3
2?Q
r:t
H
?f,jRl"-t'-~n4-c '-A=-26!~1720
?17
c;"!-îC;~O=lRi. "n! ':'''44
.i 1~!
AlI.
49
26
~AI'>
~
4!
-?7"
'"
4
-,9;>
11
RI
n~7::C1'~
-~nl',.r:o'~
;>1'
Sn!
-14\\ -~-':<4
i!
4"
37
VI -7fè7
136
65
-S'lR
"R
3'"
-103
2
1
-32
0
cr
?s:\\f~,,-~"y-3t4 -~?4~' ff!;"-~C;3 '17
Z!
771'-,1;0
44!
~no
;;.
=~!
l'
1)
01
~OA
70
31'>!
59"
q",4
lRR
9
f,!
)
~l~ 'Lm-~:C,:-~,'~l" ~lA
JO~
1?1,'H=~~ !7r ':''ri~
A3
~I
114
67
2'"
-:'07
?fI
III
-36~
70
3~ -117
A
"1
1nlqo:::
1 C;7q
IR
2311?';)0
;>04
1'>4'-Ionl ',-cf"
e;A!
.Ql.
.1
'14!
_;>'<1
Il
5!
~o'"
,q 10 ?RII
1"
10
??,
11]
~!
3l!n
f t:;.Ê.~
t
~",IQ~
;>t;4
"'~!-lA'2
m
74!
':'1"~
9
~5!
f:.C;~
?9
Ihl
-1?Q
1
1
34
0
0
n 4
4
11
'::'Ir:>
j1':Q - i l
21'-' ;'Qoe;
III
;.n!
-4~
"'0
tir
C;4Q
;><;
='f'!-1()~C;
93
50!-1;;4<;
1;>7
7"
-714
4;>;>11
117
1
I!
13!n
1 4nlf
loI'>
1"6!, -;:t'Il
n
~!
4}4
Tilt ~5! .?4'"
42:i41
"
f)
01
?97
~1
24
440
140
'591
-44
1
Il
14!I'4
! 41)
10
201
31~
4;>
Q!
3?jl;
'41\\
10!
_';)I:IR
"14 T4!
4"n
~O
34!
-"0
1
1
-f,74
17?
l'l91
40"
~2
]41
~"I~ lJ;§t!-
~1î'Z3t 1141
;>M
",n!
-7A6
Ïn
1-cl! ':',ro
10
==-41 -e;I)"
'5'5
2b!
-16
(l
0
;>90:::
lQ
III
-"""
9]
"7!
,<,!,;1
! 1.1:;'"
1,
25!~f'5op 1n<;
7n'~-'?0~ '-,-,i
"9!
':~1?
"A
"431
1~7
;>0
10!
1ï7
h
Il
,;)?A
7
4!
?17
"
4!
371A;>
!
4'12
?\\
2J"!
-6A1
101'1
?1!
3tH
_71
"'!
"~Il
1"'1
~I -"7.
104
49!
-14'"
';)"
1<;
414
41
;>e;! -170
7
e;1
'p.li1'-
!"4?1
-47
1"'!
0
(\\
~,
~oc;
,,.~
è;~! ':',,,1'
7 =?!
10"
~
3!
;>lIn
<;11
n
-11Q
7"
311
-1<;
1
O!
~Qln4
!
~'A
;>~
22!
9~q
i'4~
Ci'!
-?~6 ,'11
,,!
':~?R
70 ~11
]91'
3~
18!
-794
Ie;o
A?
4?7
4"
?é!
-114
J
';)!
4oin~
! -"47"
Il
26!
14711"'''
4';!~lS11 l~ii
e;o!
ï;.e;.
l,n " j !
':''''?1
30
16!
oc;e;
l'>Q
4?
-RI'
e;o
14!
<,,,<;
11
';)3!
4Ùn
!
c;~
1:'1
25!-}57'
11}
7~!-lit;2 17A
C;~! ':'?41
~ B!
Son
33
171
-1'>
0
O.
3~"
14
O!
91
1
1!
4;?Ti=',;>
!
;>'1
lA
l3!
;',?C;~
100
?4'
1"C;'
Ci
;>!
;>."
" - " i !
-73.
,0,
Su!
A;>
1
1!
?1
(\\
O!
-14<;
4
1!
4j"fF"
1 ~~:o
. 4A
16!
71'>
4
il
'Hl
~1
40!
~11<;
ln ~"JI -11(\\
13
"!
''''0
~~
R!
-IQe;
<!o
P!
-'''4
';)1
01
44~rF'4'!4';1,
?7
21!
1140
;>;>0
4C;!
':'1';1
7
::'r.:.ï1ï
,,=;.!
e;e;i.
97
43!
-44';)
,,?
31!
114
1<;
10!
;>"4
?O
Ill1
.' ~~~:':.'!~~u.-
__
•
-o-
o
--_~.
~~._~~
1;
nt! 1414
ln"
2~!-1"(J7 - ï;>~
.-----~_~
411 'ï~47
11 0 ~~I
~ _ .
-17,.
7
4!~
441
10
"!
-707
32
?110
40<;
,?
9!
_
.
! ,-
_ f
~\\~.o 11\\00!•
1111)~!
1(01)1
Iftn!
1(\\00!
1000!
1001'!
10001
- - - - .__
o
o--
0
_
~ ~ . ~ ~ ~ ~
~--------------.-
~;_.
l----.--~._~~&A---~.-------------.---.--------------.-----------~-o--------------.--------------o
)
O
a
_
r:~,'pf~oon'-"pi)Tn'TNR!
ï.~
r(\\PI'TOI~lIt èOQCTQl
311~ .tf!o mPI
4!E'
eoR eTH!
'iM-L C= cnu
U~ r-no l"'TQL"UIr__rna L-_Tia."o,
-----:~_~.~~~.~~~~~~~~~~~~~--~~.~-;~~~ ..~-~-~.--~:-
~~-.--------------o--------------.--------------*
-- ------- -----
~
t.~iC~o-!~-'O~
0'
lE'
Il
i1
~!
il
Ô
n!
.
l'
0,".0!
Il
0
O!
n
0
01
0
n
O! __
0
O,~I
(j)
.;...~·.:.~~f;:F-"*:..~--.;.-----~~~!'"~~~,--:
..--..~': ~~----:-~-:---- ~~i--~----------~7-------------~~-------~-----~~------------; !U, %
:~---~~.~-::.-----;;.--=---~:-~~----~--~.:::~-~~--;:-..::~---...;.-----_.=~----::;.---_:::.~_
_."'-~-- ~..:...... ~~--_:-
_... . -.
- - -- - --..&.-- ----_. _. --- .. -
-

---

1
B l B LlO G R A P BlE
BENZECRI
J.- P.
" L'ana11se des doan'es "
~G.e l
- " La Taxinomie "
To•• II - " L'analyse des correspondances"
( D1laod, 1973 )
BERZECRI
J.- P. :"S.r l'ABalyse des tableaux Biaaires associ's
l uae correspoad. .ce .ultiple ". ( 1972 )
( Rote aultigraphi'e, Lab. Stat. Math. , tour
45 - 55, UBiTersit' Pierre et Marie Curie, 4
Pla.e Jussie., 75000 Parie ).
CRIBlER
Françoise
et Collaborateurs : " La a1«ratio. de retraite ",
( 1973, Laboratoire de «éographie humaiDe, Paris )
GUILLEMARD
Anne - Marie : M La retraite, ...e aort sociale " (Paris,
Mo.to., La Baye, 1972 ).
BOTELLIKG
B.
' t
W Relatio. Betweea Two Sets of Variables ".
(1936)
Bio.etrika YOle 28, pp. 129 - 149 •
DUiTB
D. E.
W The art of Coaputer Programmia« ". Sortia&
aDd Searcbias , YOle 3, Addiso. - Wesle7, (1973 ).
LEBART
LudoY!c
et FERELOB
Jean-Pierre : " Statistique et Iator-
a.tio. appliqu6es w, ( Editioas Daaod, 1971 )
LEBART
L., MORlIEAU
A., TABARD
R. : "TeehDiques de la description
statistique W ( Paris, Du.od, 1977 ).
1
1
et aassi la reTue trimestrielle: " Les cahiers de l'Analyse des
Do. .'es N, présid'e par J.-P. BERZECRI, LaBoratoire
d. statistique de l' Ua!Yersité Pierre et Marie
\\
Cari. ( Paris, n...od ).

---

tk
tt,t
1
t
1
,i
1
i
i
1
!
DEUXIEME PARTIE
UN PROBLEME DE RECHERCHE OPERATIONNELLE
1
LES DECOUPES LINEAIRES
1
t
1
( UN ALGORITHME NOUVEAU : LAGAF )
i
1
1
1
1
1
1
1
t
t
i11
\\
1
1
1

---

3l...
l -
LE
PROBLEME
POSE
A) - Enoncé du
problème
Il s'agit de satisfaire une demande donnée à un
coat minimal. Plus précisément, le problème posé est le
suivant : On dispose de grandes barres de longueur connue
L : barres standard ou FORMATS. On cherche à découper dans
ces formats, des morceaux plus petits appelés FLANS. Ces
flans sont en nombre Ni
et de longueurs
li
données;
il yaN sortes de flans différents •
• ) Barres demandées ou flans:
{
( l i ' Ni i .
i
= i , N J
•• ) Barres standard ou Formats:
L (en nombre non limité)
1) - Les demandes sont toujours : t(li' Ni)' i = i , N }
La barre standard a toujours la m~me longueur L ;
Cependant les barres standard L ou formats sont faites
de métaux différents : par exemple, or , acier, cuivre,
etc •••
D'où :
acier
)
) même longueur et
) coOts différents
cuivre
)
2) Soient Cl' ~)., Ci ' i différentes coupes dans un m~me
format L. L'énergie
dépens~e pour effectuer Cl' peut ~tre
différente de celle utilisée pour C
' ou pour C , C
2
3
4,
ainsi de suite. A chaque dépense d'énergie, on associe
une valeur. Autrement dit, la coupe Cl coOtera
VI' C2
vaudra V
et
Ci
aura pour valeur Vi
2
. . .1 ...

---

r-
format L
I
1
l'
liil 1
li ri:
t
t
t
~
coupe l
coupe ')
r
coupe 3
C4
valeur
l
V
V
V
2
3
4
Les différentes coupes sur une m~me barre standard peuvpnt avoir
des valeurs différentes.
Résumons-nous
En d'autres termes, le nombre de coupes
par barre est inconnu ; les valeurs de deux coupes distinctes
sont différentes. Les valeurs de deux barres peuvent être
différentes bien que ces barres soient de même longueur.
~~~~!~~~ : Combien de formats de tel ou tel métal, et combien
de coupes dans tel ou tel format
nous
faut - il
pour cette
opération? Naturellement, il faut minimiser le cont total !
B ) - Les intéressés
Dans la présentation ci-dessus, nous utilisons
les termes barres, formats, flans. Ces termes ne doivent
pas nous emp3cher de voir toute l'ét;ndue des applications
du problème.
Sont confrontés à ce problème de découpes liné-
1
aire
certains utilisateurs de métaux précieux - Cf. les
références données par Monsieur R. FAURE (du CNAM) -)de
1
pipelines etc •••
~
La plupart du temps, les problèmes de surface
1
s'y ramènent assez aisément : problèmes de découpes de
~1
tapis, de tôles •
i1!
Cf. Ascinter OTIS
fabrique d'ascenseurs -
Exemples concrets
Cf. leçons sur la programmation mathéma-
1
tiques de VAJDA, Dunod page IOO à I06.
Les demandes li
peuvent aussi s'interpréter en termes de
1
poids. Et cela quant il s'agit de capacité, de"contenance" •
. . .1 . . .

---

Précisons
par exemple :
Soit L le tonnage maximal d'une remorque. On veut transporter
des cuves d'une ville à l'autre. Il yaN sortes de cuves: Ni
cuves de poids li • On demande combien de voyages devra
effectuer
un routier disposant d'un seul poids-lourd?
Un très bel exemple est donné en termes de processeurs.
Soit N sortes de tâches de durées connues li
en nombre Ni.
C'est-à-dire qu'on a :
NI
tâches de durée
Il
"
"
"
"
"
"
N
l
t
n
"
"
"
n
1
1
~j
Ces tâches sont à effectuer par des processeurs.
Î
Un processeur peut être aussi bien un ouvrier dans une chatne
i
1
de montage, qu'un appareil physique comme ,-n
microprocesseur
~
électronique.
1
1
On suppose que les processeurs sont identiques et en nombre très
t~
grand. De plus, il faut ajouter qu'un processeur ne peut effec-
i
tuer qu'une seule tâche à la fois. Et toute tâche entreprise
l1
1
doit ~tre terminée avant que le processeur ne passe à ufte
11
autre.
1
On se propose de termine~l'opération dans un temps limite L.
1
Combien faudrait-il de processeurs?
1j
1
Ce problème de découpes linéaires, comme nous le voyons,
J
englobe
de nombreuses activités de tous les jours. Inutile de
1
dire que, naturellement,les .chercheurs
opérationnels ou mathéma-
ticiens des applicati lns s'y sont attaqués!
1
j
!
Voyons rapidement quelles formulations et quelles solu-
1
tions ont été proposées à ce genre de problèmes.
...1 ...
\\

---

1
II -
HISTORIQUE
1!
A) - Gilmore et Gomory (1964)
Genuys (1972)
1
L'une des présentations les plus anciennes du
problème de découpe est donnée par Gilmore et Gomory. Avec
1
G~more et Gomory, revoyons le problème dans toute sa géné-
ralit ë ,
a) - Problème
Soient LI ' L
'
L
-
Lx les longueurs standards
2
3
(ou Formats) d'un certain matériau. On veut en prendre des
longueurs données. Pour chaque longueur standard, on a en
stock un nombre illimité de pièces. Le problème est le sui-
vant : on veut des morceaux ou flans : N.
nombre de pièces
~
de longueur li' de m sortes. Et chaque"longueur
standard"
a un coat. Le coat de la demande est simplement le cont
total du nombre de formats utilisés. On se propose de
satisfaire la demande au moindre cont.
Données : .Formats
,
j
= i , K J
en nombre illimité
et de
coûts
,
j
= i , K
associés
~
• Flans
Problème :
Minimiser le coftt (car on peut avoir à minimiser les pertes,
les coupes, le nombre de barres standard utilisées
etc •• )
.../ ...
J
1
1

---

Désignons par "activité" la manière de couper un
format L. Par exemple, on coupe le format 20 en trois mor-
.
ceaux, un flan IO et deux flans 4 . c'est une activité.
.
Alors le problème peut se poser comme suit
Soit
le nombre de flans 1. demandés
a
Soit
le nombre de fois qu'une activité j a eu lieu
a
:
nombre de flans l i ' créés par la ji~~e acti-
i j
vité.
On a :
- ail xl = nombre total de flans li créés par toutes
les activités l
a
x
= idem pour les activités 2.
i 2
2
et ainsi de suite.
ai~ xl + a
x
x
i 2
+ ..
+ a
2
i n
> N. i =l, m
n
.i,
Le coat
Cl xl
+
C
x
+ ..
+ C
x
2
2
n
n
avec
C
est le coat du format L dans lequel a été effectuée la
i~me activité.
En d'autres termes, le problème de découpe est
n
Min
L-
C.
x.
J
J
j
\\
n
î
, i =l , m
1
~ a..lJ
11
.../ ...
1
j

---

B) - Remarques - Critiques
Même en relâchant la condition d'intégrité - (métho-
de de relaxation) - , cette formulation demeure peu prati-
que, en raison du nombre très grand, n , d'activités possi-
bles. Il suffit d'avoir
k ou m très
grands. Par exemple,
avec
le seul format 200, et 40 sortes de flans, de longueur
variant entre 20 et 00, on atteint un nombre d'activités de
l'ordre de 10 à 100 millions!
:
i
~
Toujours, en "continu", de nouvelles procédurbs sont
1
proposées. Dans tous les cas, s'y attachent de très diffi-
1
ciles problèmes annexes: on peut citer la résolution de
"Knapsacks" :
~axJ
C,x, + C2%2 + C3X
1
3 • • • C.xn
a,x, + a2x2 + • • • anXn~ b
Xi E: IN , '" i
•
; ( ai et Ci donn6s i.
1
Du problème de découpe posé au départ, dan s N, on
1
est amené à accepter une solution approchée • Pour atteindre
~
la solution réelle dans N, on fait souvent appel aux méthodes de
î'1
troncatures ou de congruences décroissantes.
~
Cependant, le problème de l'arTondi demeure toujours
posé.
Considérons la rigure de la pase suivante. Les
solutions en nombre entiers sont indiquées par des points.
Les contraintes délia1tent le polyèdre des réalisables. On
voit ici, que la solution dans le cas entier peut Itre à
l'intérieur du polyèdre. Parroie .8me cette solution ~
est "très loin" de la solution M"
obtenue après utilisation
des méthodes de congruences décroissantes.
( Botons seulement que ni la fonction économique
Bi les contraintes ne sont linéaires ).

---

'X.~1'
1
1
i1
•
M.
•
M...
GJ
r
Mit
•
•
•
/ '
•
•
.,J
•
•
.'
Io-----....a,:~~.--~.-----~--.....--.-.--
.........--
. /
Représentation "très grossière" de la méthode du
simplexe et des problèmes posés par un optimu.,
en entiers.
Légende
Mo : optimum ( aTec relaxation ) en continu.
- Ml : arrondi, ou solution après troncatures.
( Les droites en pointillés symbolisent la
méthode de troncatures partant de la solution
Mo da programme en continu ).
- M*: optimum en enti er •

---

c. Remarques J
Nous aTO.S Tou1u faire .a paaoraaa rapide des
méthodes qui existeat à ce jo~r.
Certa1as cherchellrs - Malsr-..ge , Fave -
se seat iatéress'. déjà a. problème. cep.adaat les articles
l et II, de G11aore et Gomor7 sont to.jours les référ••ces
d. ~ase.
(cf. Opas. Res. 9 pages 849 - 859 J ( 1961 ) ).
Il Y a certes aussi d'autres idées - Gondran o.
GuenuY8 ( 1912 ) - J ils utilisent le dual d'ua programae et des
aéthodes de coagrll.ace décroissantes, pour résoudre un srand
.ombre de problème de découpes.
DaDS sa thèse de doctorat ~s- sciences, Mo.sieur
J.-L. Lauri~re fait un tour d'hopizoa de ces prob1èaes de
découpes, bin - packing, etc ••••
Nous ae ponToas 80.S emplcher de citer l'ouTrage
re1atiTement récent de Coffman et de ses collaborateurs J
"Computer and Job - Shop Scàedu1ing Theory".
1
11t
!

---

4-0
III - HEURISTIQUE PERSONNELLF
1°)
PREMIERES APPROCHES
A) - Formulation l
Barre " standard " : L
Demandes
:(<li' Ni)
,i=1,N1
Supposons le problème résolu.
Soit P une solution quelconque du problème
Soit
Z le nombre de "barres standard" L, correspondant
à cette solution.
Cela signifie qu'on a Z fois la barre L correspondant
chacune à un partage.
l
2
3
- - - - - - - - - - - - - - - - - - - - - - 1
4
~--------------------
---------- -------i
5
I------------------J
Considérons une barre L. Sur elle on a : nI fois les
morceaux Il ' n2 fois 12, ••• , ni fois les morceaux li'
et ainsi de suite. Ajoutons-y une chute ou perte r.
C'est-à-dire:
i
"i Il + n2 12 + n.s Il'·· + ni li + •• + nn ln + r = L
j
avec
1
ni <Ni
et niE.1N
l
( ni
= 0 Possible)
1
Posons
a.
= li
l
L
. . .1 ...

---

et :
X.
=
l
Comme
r
;r 0
On a à
---. "
Max
-'
.L-
--
xl
L
C ; -
L~- ai xi _
l
)
xi E IN
xi ~ Ni \\:f i
Nous avons ici une généralisation du problème de Knapsack.
Ce problème est très complexe. Mais il n'est pas impossible de
le résoudre, par exemple si on rel~che les contraintes (3) dans
un premier temps.
Il se pourrait même que la résolution du pr-ob Lè-se se trouve
simplifiée en considérant le système posé par l'ensemble de toutes
les
Z
barres.
Formulons alors complètement le protlème sur l'ensemble
des Z barres standard.
Numérotons de Ménière arbitraire les Z barres.
...
La 1ère barre
1
'1
•
L
nll
+ n
1
+ .. + n. 1. +
+ nlo
l
2
2
" -1 L"
lr+ r =
J
J
N
1-
~
La 2ème barre L
+ n
1
+ ••• + n". l. +
+ n "l!+
~
T~
•
nll
r
l
2
2
= ,'-J
J
J
N
N
Donc
\\
e,
Â
t.
,(..
n
11 + n
1
+ .... + n.
+ .. n
+
l
2
2
lj
lN
r"<'
= Li
J
N
avec
i = l,
Z
Précisons :
...
n;E tN
n. = nombre de fois qu'on a pris l.dans la barre L
J
J
r"" €.R
chute dans la ième barre L•
.../ ...

---

Posons :
-.t"'
L = (Il' 1
, - ,
2 ' 13
IN )
trI
l
R
rd
l
=
,
E.
lNZ
"il:
,
1
l
On a
n.L
+ R
= L.rd
Soit
n.L
<:::...
Lord.
où
nI
Dl .... n . .....
n
J
N
1 nI
n2
n.
n
J
N
n =
nE NNxZ
avec
Z~fN
nI
n
....
2
n
nN
j
Z
7.
Z
Z
nI
n2
n.
.... n
J
N
avec :
Z
i
Yj
Z
nj
=
N.
fixé
J
i = l
Autrement dit ,en
termes de
programme linéaire
Max
Lon
0)
Lon
~
Lord
r
•• ) ~--- n~
~
=
(les Nj sont donnés)
J
0.0)
n
€
N
j
. . .1 ...

---

t
ti
a)
Z
Knapsacks
généralisés à résoudre f
b)
Z
non connu !
1
1
,
1
a) On peut prendre au départ comme Z, celui obtenu à
1
r
partir d'une "bonne solution"
,c'est-à-dire, par
!
1
exemple, on sait que l'algorithme du First Fit Decreasing
!
(ou l'algorithme décroissant de la première boite),
1
donne un Z Toisin de l'optimum, on prend ce Z-là.
b) Remarques
Représentons la matrice n par ses lignes.
n~
J
n
n
=
L'optimum sera obtenu pour la "matrice entière" n
satisfaisant les contraintes du programme linéaire l
avec le plus grand nombre de ni
= Q (identique au
vecteur Q = (0, 0, .. " 0)
La programmation dynamique, dans toute sa
généralité, est très "lourde". Il y aurait donc inté-
rêt à éviter d'avoir à résoudre les Z knapsacks généra-
lisés (voire avec contraintes 1).
Ceci pourrait se faire en interprétant le pro-
blème de découpe, s~pposé résolu·
,comme un problème
de partage particulier". Mais quel partage
. . .1 ...

---

1
1
Cette tentative de "résolution" en termes de "partage"
\\
semble deYoir ~tre
reconsidérée .• Pour le moment, en tout cas,
elle est sans succès. Cependant, nous en utiliserons quelques
idées dans la construction de notre algorithme définitif.
1
B) - Interprétation en termes de voyageur de commerce
Cette seconde manière de voir s'impose à l'esprit
de quiconque s'est quelque peu intéressé à l'algorithme
dit de LITTLE.
Notre voyageur a toujours un nombre fini
N de villes
à visiter. Il part d'une ville A. Il doit passer une fois
et une seule par chacune des autres villes pour enfin reve-
nir en A. ( Le graphe est complet ).
On ne demande pas ici le plus court chemin. Et il s'y
ajoute une contrainte •
Supposons que le voyageur soit un avion, avec une
'autonomie d'essence". Il faut entendre par là, que le réser-
voir de l'appareil contient une quantité maximale d'essence.
Cela lui permet, par exemple, de parcourir, au plus, 200 Km :
200 sera le format. Les distances entre deux villes quelconques
seront les flans. (L'apoareil ne peut donc être à court de
carburant entre deux villes! ).
La question est celle-ci
combien de fois doit-on
faire le plein d'essence?
Dans ce rapprochement " découpe-voyageur de commerce ",
plusieurs idées retiendront notre attention : les
notions
de "regret" et d'arcs obligés. On utilisera aussi et surtout
la référence à une solution de départ.
Il est difficile d'affirmer que l'idée d'un
algorithme
provient d'une ou deux interprétations. Nous avons eu plusieurs
démarches. Mais nous avons présenté ces deux-là
qui se rap-
proches le plus de notre solution finale.
.../ ...
1

---

2°) PROBLEME DE DECOUPES ft LINERAIRES
"
(Hésolution)
-Introduction
============
- flans
l(li' Ni)'
i = l, N}
format
L
Trouver le nombre minimum de formats L nécessaires pour
t(
satisfaire la demande
li' Ni ) , i
= i , N J
Soit Z*
ce nombre optimal de formats. z~ ne peut 3tre atteint
.directement. Aussi détermineronA>-nous un intervalle "entier",
le contenant. Nous essayerons d'avoir des bornes Z et Zo de
cet intervalle, les plus voisins possibles.
Z
z-t
zo
borne infé-
borne supérieure
rieure
Z
= Zo
=
Z*
Nous avon~irectement l' opti ·'um.
€. *0
1) ~ ) 3
: Ce seuil de 3 n'est pas absolument
indispensable. Cependant pour nous un tel
i!
intervalle ayec
e: '/ 3 eet considéré
1
i
comae trop &rand. Aussi essayera-t-on
!!l
1
de le réduire.
!j
ilij
\\îj

---

2)
L "' 3
"bonne"condition pour lancer l'algorithme.
Le problème posé est"le suivant
En quoi peut - on
résumer notre démarche ?
a)
Recherche de l'intervalle (Z
Z
)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - ,
0
Ici nous verrons les heuristiques qui nous assurent
efficacement les bornes
Z
et Z
: F - F - D et
o
F- F -
D - PRELENE
LAGAf est le nom de b~ptème de cet algorithme qui nous
assure l'optimum cherché.
Remarques
Notons qu'à la limite, l'étape a) pourrait être laissée
de côté. Mais dans ce cas, l'algorithme
peut ne pas converger
rapidement.
- Les heuristiques ci-dessus nous permettrons d'avoir pour
point de départ une solution bien particulière: Zoe
La distance de Zo à l'optimum Z· cherché est déjà
mesurée. C'est à dire que pour trouver Zo, ces heuristiques prennent
déjà en compte le but de l'étude: avoir le minimum de formats
possibles. C'est pourquoi nous dirons que Zo est une "bonne e.lutioat

---

Si ! désigne une borne inférieure de Z, on aura
Zo - Z
Z
Ceci BOUS permettra dès lors de contr81er l'erreur relatiY9
par rapport à l'optimum.

---

* Etude des bornes inférieures et supérieures et des
, algorithmes qui s'y attachent
1°) - Données
.) Format
L
(en nombre illimité)
.. ) Demandes : { (Il' Ni ) , i = l, N1 : flans
Soit Z '*"
le nombre optimal de formats cherchés
z
(
z~
zo
l'
l'
borne in-
borne supfrieur
férieure
20) _ Etude
de la borne inférieure
Z
a) La longueur totale des demandes :
N
L T 0 T
=
L....
li
Ni
i
= l
~ Nombre minimum deformats
= FTL0 T]
rarrondi à l'entier supérieur.
b) Exemple
On veut organiser sur un ordinateur multiprocesseur, le
passage d'un ensemble de tâches. Il y a quatre sortes de
tâches de durées connues, en nombre connu: Cf. ci-dessous.
Ces tAches doivent Atre exécutées avant la date limite L•
. . .1 ...

---

- f
4-9
!
,~
.) L = 18
t
f
•• ) flans
--- .._---
espèce
1
2
3
4
1durée
15
13
II
8
1
8
~iEHe~e
3
2
1
2
I,/, / /
, . . C
"
' . '
/ ' /
"
. l/ / , /
.
/
"
//' .j//
, /
, / , '
, ' ' ;
>~:// t/:>~l,/ ! • l"." ,.,' -:
/ , .
r I ' ' ;
,// <. ,/ /' ./'
cumul
partiel
!,
45
26
II
16
cumul
total
98
i
45
71
92
98
On a
L T ~
T
= 98
_.....
1
...... /
g
=
=
= 6
!
[H]
(5.04]
c) Interprétation
Ci-dessus, on a fait comme si les flans sont
placés
bout à bout, ce qui détermine une certaine longueur LT~T.
On met "par dessus" les L l'un après llautre, et on s'arr@te
1
au premier L qui dépasse ou est égal à 1a"ligne"
L T ~ T.
1
Format L = 18
1i
1
1
!
1
l
15
1
,
15
• Il ,t,ll/~
i!
15
t ',t; < 1 '1
i
13
1/1
, ( ~ p' ;
"
ll4
1
i
13
1
l'''<<(l~ .. ...,....
1
1
II
Il " 1 ~ J' ~, 1; ,1 t pi ""
l
Fig. 1
.../ ...

---

So
,
1
L'interprétation ci-dessus est certes naturelle, mais
r
la garder plus longtemps après la figure 1 n'est pas permis.
l
Car cela
suppose que les deux
flans
8 et 8 seront pris
t
dans les "chutes accolées", des 6 formats déjà utilisés.
Ce qui est impossible, car le~urées 8 et 8 doivent ~tre con-
1
tinues, c'est-à-dire d'un seul tenant.
On "voit" là que l'on doit prendre nécessairement
1
Z
IZ
7
\\,
Par définition, on dira que les flans 15, 15, 15, 13,
13, Il et 8 sont'~ncompatibles"
• Par contre, 8 et 8 ne sont
pas incompatibles permet d'améliorer la borne inférieure.
d) Conclusion
La recherche des incompatibles permet d'améliorer la borne inf~r1eu-
.
.
~'
Notation : Soit {, ( ~ A.)
, i = l, 2, 3...
l'ensemble des bornes
-.
inférieures obtenues par tel ou tel procédé. On posera pour
la suite :
Z
=
Max
{(~l.) , i = i , 2 , •••• }
3°) Etude de la borne supérieure Zo
a) Introduction
Une solution éYidente pour avoir une borne supérieu-
re est d'associer un format L à chaque flan li •
Plus Z
sera proche de l'optimum Z~ cherché et
o
plus intéressant ce sera.
Plusieurs heuristiques
proposent des solutions de départ Zoe Parmi ces
méthodes, nous nous attarderons sur l'heuristique
dite du"First Fit Decreasing" ou F.F.I. et celle
baptisée F.F.D.PHELENE.
Nous exposerons directement ces deux heuristiques
sur un exemple. Ce sera, je pense, beaucoup plus
parlant !
.../ ...

---

1
b) Exemple
1
1
Dans de grandes boites zde
capacité 396 , on désire mettre
!
11
poids différents.
1
L = 396
1
el=-
4
5
6
7
8
1
9
1
l
2
! 3
1
la
II
Z-
l
i
_-- --,,~--..- ........
---
f - ' - ' - - -"-r-- --_.
-----
r
----1-----
- - - - --'-_..
1
1
.r
1
285
188
126 II5
II2
75
60
51
12
!
10
9
l
1
\\
6
18
6
!
k
t
55
1
,
~l_
3
3
l
l
l
3
.
12
-. ---- f - - - - f-----.
..--_.- ---'--~-_=/&Z-.-
;
~l
.
~
2
-
~
.L
:>26~
!
345 336
75
60
51
c
-J.~
--ou
108
1
,.....
_._.
.'- ..._---
.
r
.. - .... --.- .- f-.
....-..
.--
-~_.
t
' - ~. -- f-.
-~--
... ,,~
r .
ot al
1. Lj.l
' /
3
368
402t 4362 4437 4497
4548
4~4
It?Cj2
- "._._.. . ___.___.___._.._ ...... _._ ._____•__.••_ 1.--._ ._.._ .•.•.•L--_.
---_..
_-_.
---
4752
Pour mémoire ,mus avons ajouté la deuxième partie du tableau
ci-dessus. De m~me, on y met la valeur de :
Zo
t
=
~ fl TJ = f4 75". /1 = 12
396
J)
• Phase Ql
: une solution évidente est donnée par le nombre
de flans demandés: ici 55.
• Phase Q2
heuristique du First Fit Decreasing.
c) Heuristiques du F - F - D
Principe :
Onmnge d'abord les différents flans,ou poids,en ordre
décroissant ; on place ensuite les poids
dans des
bottes Bl,
B
•.•
Et cela dans l'ordre où apparaissent ces poids. Pour
2,
chaque poids, on recherche la bo~te qui convient, c'est-à-dire
que le poids est placé dans la boîte Bi' b8tte qui a le plus
.../ ...
f!
!!
1
l~

---

l
1
1
!
t
petit indice i, parmi celles qui peuvent encore contenir ce poids.
l
En d'autres termes, c'est·
la première botte dont la "capacité"
reste inférieure ou égale au maximum -ici
396 kg - une fois
1
qu'on lui ajoute ce poids.
l
1
Cas pratique
1
!
ite
285
+ 12+12+12(0):
(111)
\\
+
\\
itel::
188 + 188 (20)
/
1
ites
126 + 126 + 126
1
(l8 )
')
.
\\
("
!
ite
S
115
-{(o) !
+ II5 + II5(51)
,
i
\\
ite
112
+ 112 + r12 (60)
\\ '0)
1
: +t.:> (o) {
\\
1
1
D'où
Q2
Z 0
= 12 bottes
Remarque
Cet exemple donné plus haut a été choisi car il montre un
comportement"bizarre" de cet algorithme: lorsqu'on enlève le poids
( espèce 6 ) de valeur 75 kg , l'algorithme utilise une boite de
plus !
En effet
1
e
285(11])
l....
\\
"O(Slj
)51 (0]
}
...
es
1
188 + 188(20) x 3
1
1
t
(
\\
es 126 + 126 + 126(18 ) x6 J
1
\\+-AO" ~
e 115 + 115 + 115(51)
;
(oP)""
1
l.
'te II2 + 112 + 112(60)
\\
11
i
te
tl
9
- - - - - - - -
.../ ...

---

Cet exemple très intéressant a été construit par Sylvia
Halas.
On pourrait m~me dire que cet exemple est préoccupant. Aussi
nous sommes-nous penchés sur le cas.
Que proposons-nous?
Un algorithme nouveau plus fin peut-~tre ?
En tout cas, cette nouvelle Heuristique baptisée F. F. D. PHELENE
montre que l'absence du poids 75 ne conduit pas nécessairement
à 13 formats: 12 suffisent largement !.
Reprenons l'exemple
on aboutit à
1 botte
285(111)
+
12 + 12
+ 12(0)
+
3 bottes
188 + 188(20)
10 x6(0)
x 3
~
6 boites
126 + 126 + 126(18) x 6 ~ 9 x 12(0)
1 boite
II5 + 115 + 115 (51) ~ 51(0)
1 boite
II2 + II2 + II2 (60)
~60(0)
on a bien
12 bottes ! 1 !
d) Heuristique du F. F. D. PHELENE
Principe
Le principe est le même que celui du FFD (First Fit Decrea-
sing). Mais avec la seule différence qui est ceci: dès qu'on a
une chute L'au niveau d'un format, o~eherehe les flans li tels
que :li ~ L' • Parmi ces li' on prend
le premier indice io tel
que li divise L'
•
Posons
division entière
De deux choses l'une;
s.
,
~
(= le nombre de flans 1.
restant à satisfaire)
r
10
•
on recommence la recherche d'un autre 1. divisant L'
1
tel que .••
1
.../ ...
1

---

1
ti
1
.) faire
N
N
- K
io =
io
1
L'
= a
!
!
•• ) Reprendre comme pour F.F. D. (Notons que, dans le cas
!~
{
où L' n'a pas de diviseurs parmi les li '
(li~ L'),
on se retrouve comme" au début" en l'.F.D.
1
!
1
[
Grand nombre d'exemples montrent très souvent que L' heuris-
r
tique F.F.D.PHELENE.
!t
Et ceci surtout quand on a des exemples "bizarres ".
1
Entendre par "bizarres " des exemples : L, { (li' Li ), i =
t
l, Nl, où en enlevant une demande
1.
par exemple,
1
JO
l'algorithme du First Fit Decreasing utilise un format
L
en plus, et cela par rapport à l'optimum avec tous
les flans.
1
Donnons encore un cas" bizarre".
1
1~~
'.
i
r
r
~
l
2
1
3
4
5
6
7
•
8
9
la
I I
t
1
,
.
1
;
t
1
1
1
!
t
!
441
i
l
252 ! 127 \\ 106
84
47
38
37
12
10
t
i
1
9
1
1
\\
-
:
~
l
1
7
5
4
1
l
'.
l
. _ 6 _ _
1
_'_____
____._ _ _
~_!-_.
i 2
l
l
6
2
;
1
1
L'algorithme F.F.D. utilise différents formats ; mais dès qu'on
t!
enlève, par exemple, le flan 47 , F.F.D. demande un format de
t
plus.
1
!
Dans ce dernier cas, par contre, F.F.D.PHELENE utilise
7
formats.
1
f,
L'heuristique F.F.D.PHELENE, serait-elle plus "fine" que
t
la F.F.D. (ou First Fit Decreasing) ?
Non, cela n'est pas sûr. Car on a des exemples où pour un même
problème, l'optimum du F.F.D. est meilleur.
(Cf. l'exemple de Sylvia Halas où on ccnsidère tous~s flans) •
. . .1 ...

---

Conclusion
Nous chercherons les optimums par ces deux allorithmes et
prendrons le plus
petit.
Remarques
On peut proposer une infinité de procédés pour avoir
un optimum de départ pour l'algorithme de découpe de notre
travail.
Mais l'efficacité du travail dans son ensemble demande
de ne pas "prendre trop de temps "dans
la construction de
l'intervalle
Z ,Z
-
0
Dans "Scientifique American" de Y.
1
C02f'\\1A-'T (1'176) ~
'·.e
Professeur
Ronald L. Graham montre "le bon choix" de l'algorithme
1
du F.F.D. : en fait, sauf cas particulier, ce procédé donne une
solution très proche de l'optimum. Et son temps de réalisation
inférieure à 33 % du temps optimal de réalisation lui offre un
très grand avantage !
(Confer
surtout les pages 92 - 93 - 94
: L'Organisation du
travail et l'analyse combinatoire ( page 85 à 95 ).
L'étude des cas qualifiés ci-dessus de "bizarres" ,
justifie, pour nous, la coratr uc t Lon du F.F.D.PHELENE.

---

* Algorithme LAGAF
1.
PRELIMINAIRES
Kous commencerons cette part~e par quelques remarques.
Remarque 1.
N
Soit: TOTDEM = 2-
•
R·L
-4..=1
on numérote l'ensemble de toutes les demandes ou flans ( par
l'i.ndice j ) :
1
{ BD(j), j=l, TOTDEM1
1
!
où BD(j) est le flan demandé numéro j, dans un ordre donné fixé.
La "bonne solut~on"-BS- obtenue
1
à partir de l'une quelcon-
1
que des heuristiques induit un "certain ordre": on verra cet
1
-ordre privilégié".
l
1
70ute branche quelconque de l'arbre cont~ent donc TOTDEM
segments, numérotés de 1 à !OTDEM.
1
Re.argue 2.
1
!
Pour un exposé succ~nt de LAGAF ou notre "algorithme de
1
,
découpes", on laissera de c~té un certe.in nombre de propr~étés;
en particulier :
1
- on fera comme si tous les flans sont différents,
!
- on ne tiendra pas compte de l' "ordre induit" (provenant
1
de la procédure de calcul de 'Z.a) .Les flans sont simplement
i!
numérotés par ordre décroissant des longueurs. C'est à dire
!
BD ,~»
BD (j+l) (.:- ej~,( )
e j
!
- on supposera aussi que la meilleure borne "bonne solution'
1
est donnée par F-F-D : First Fit Decreasing.
( cf. Exemple)

---

s+
Algorithme proprement d~t
1
f~1!
Mous commençons par un exemple.
t
A. EXEMPLE
r
1. Construction de l'arbre •
• ) Format ou loagueur standart : L • 20
•• ) Flans ou deaandes
,
Données
~
1
espèces
1 1
2
,
3
4
51
6
7
z--
!
_..__._.,. _._--~
longueur
1 14
13
8
7
4
3
2
1
(li)
f
--
Nb désiré
(Ni)
1
1
3
1
l!
1
5
13
1
i
--
[
l
- 1-
~
-1
,
1
1
-:Résolution
1
i
cUllul
24 1 7\\
4
3
10
partiel
cumul
51
58
62
65
75
75
total
..,....."/
«:
LTOT = L Nl l .... = 75
1
•
TOTDEM =~ M..i. = 13
1
')
.) Borne :l.nfér:l.eure l Z = (L~OT] = [~] = b. 9j =4
!
•• ) Borne supérieure : Zo = 5
( la petite des bornes supérieures obtenues par toutes
les différentes méthodes ).
1
f
... '
f
on a : 4""2..
~ 5
~
••• ) "Numérotatioa"
BD(l) = 14
.J BD(5) • 8 .J BD(9) • 2
1
BD(2) • 13
BD(6) llr 7
BD(lO) 1: 2
1

---

1!11
11
BD(3) = 8
BD(7) = 4
BD{ll) = 2
r~-
BD(4) = 8·
;
BD(8) =3
;
BD(12) = BD(13) = 2
i
~
o
r
t
i
I!>~. =(A"') 1ls~
~D2, : c·{~)
!!
1
1
!
i
i
1
!!
, •
. s s
(~) j
1
;
f
~[
!
1
1
1
!f·
1
1
1
(1.),/
!
!
1
!t1;
Légende
1
A chaque segment j est associé un sommet Sj et au départ la
f
barre demandée BD(j).

---

2. Description de l'arbre
i
L'algorithme que BOUS allons étudier est basé sur la cons-
truction particulière d'un arbre. Le cheminement dans cet arbre est
1!
aussi particulier.
f
Pour préciser ces notions. Toici un exemple détaillé d'~n
arbre à 5 tAches.
1f
1
1
i
1
~ ,
1
,
sr-
1-
(j)
\\
"l"
/'s'J '~" / l\\.
J~ t~l '--------v-----~
1
!
J ~ 1\\
;Q(c.\\N\\
f
!
!
!
i
1
1
1
Remarque 1.
On a 5 demandes flans. donc 5 tAches. PortORS notre attention
sur les ~tapes de la figure ci- dessus :
.) 50 a un seul successeur
t
1
•• ) 5", en a 4
~. 5't,. 5'i. 5 n ' t,
••• ) 52. en a 3
5~. 5~ • 5"3
(de mIme pour 5\\.) •
• • • • ) 5:!o en a 2 : 5«t- et 5 'ct-
(de mille pour 5 '3 ou 5 "3) •
1
\\
.•.•• ) s., en al: 5 s (de mIme pour 5 ',+ ) •
1
1

---

1
Le sommet s~ a 4 successeurs.
~out sommet de l'étape 2 eD a 3 • De mIme tout sommet de l'étape 3
eD a 2. Et ai_si de suite.
1
Remarque 2;
N. .érotatioD
1
i
f
t
1~t
f
f
!
,
l
1
!
il
,
i1
r
1
f
1
!
i
.) Les eucceaeeur e deCYsont 2,3,4,5. En d'autres termes les
!
frères de 2 sont 3, 4, 5.
t
f
Les successeurs de 2 sont a.ssi ses frères: 3, 4,:5.
De .I.e les frères de3 sont 4 et l 5 ; et ses s.ccesseurs 4 et 5 •
•• ) La mIme description est valable à partir de 3. Les "frires"
de 3 sont 2, 4 et5. Aussi sep successeurs seront
2, 4, 5.
Sur la mIme bruche 4 a ŒcOllJle prédécesseur. Ses frères sont 2,
5 qui deviendront ses successeurs.
Co_c1usioD
La progression daas l'arborescence est ass.rée par les frères.
Ceux-ci deviennent tous,à tour de re1e, successeurs l'.n de l'autre~
Un frère ne peut 8tre son propre successeur. Aussi d'une étape 1
à l'étape suiva_te i+1, le _ombre d'ares diminue d'un seul: le
frère évincé.

---

B • ARBRE
A càaq.e aommet SL, on associe quatre Dombres
S ... :
(i.."
iL' i~, 1~)
Re.argues
Rous allons déTelopper une partie de l'exemple de découpes
cité daas les pages précéde.tes. On y définira les q.atre nombres
i A , i~, i , i~, ci- dessus, cela aTant de les étudier de maDière
3
eXplicite dans le cas général. Les exemples de sommets préciseront
1
aussi (e.core), quelque peu les particularités de l'arborescence.
1
1
o 1 2.0 . t S AO'Q): 5.
1
1
1
i
1
~
l
i1Îi1

---

~
1
i!
Aaalyse
!
1
Bous étudierons les deux chemins suiYants :
j
S
S
S
S
et
S
- S
- S
- S'
D -
.-t -
1.- 3
•
~
t.
>
1
• )Chellia S9 - S4 - S. - S" :
j
1
So Z <0, 20; 75, 100)
C'est la phase d'initialisation:
-"" 0 Z on a utilisé 0 barre standard
- 20 : longueur de la barre standard L 2 20
- 75 : longueur totale à loger ( ou contenu)
- 100 =Zo IC. L • 5
20 : longueur totale (ou contenant)dont on
dispose ; cela par rapport à la dernière ft Bonne Solution-
obtenue j.squ'alors.
u , 6; 61, 86 )
S'"
-1 •. on a entamé la première barre standard (pour placer 14).
-6
6 = 20 - 14 : c'est ce qui reste de la première barre
standard quand on a pris 14.
-61 : 61 = 75 - 14 z longueur totale qu'il reste à placer
(ou "contenu" restant).
-86 z 86 = 100 - 14 : en se référant à la "bonne solution-
obtenue j~eq."
préeent, c'est le conteDaat qui reste ou
1
dont on dispose.
S~ : (2, 7; 48, 67)
-2 pour atteindre le sommet S~, OD est obligé de prendre . .e
deuxième barre (standard).
1
-7 : 7 = 20 - 13 z ckute dans la seconde barre.
-48
48 • 61 - 13 : reste à loger.
-67 : 67 = 86 -(6+13) : reste du contenant.
1
Le 6 Yieat de la chute dans la barre standard précédente:
1
premier format L. Dans cette chute 6, on De peut pas
t~
mettre 13. Au.ssi pour cette nouyelle acti'Y1té on se doit
J
de prendre un DOUyeaU format L z soit le deuxième.
1
La chute 6 est perdue; et l'activité 13 réussie. Mais
tout cela a été pris dans le reste du "contenant" (86),
11
les tAches étant ici ordonnées.

---

S:!l: (3,12; 40, 42 )
-3 : la tlche (8) de cette étape, ne peut se loger dans la chute 7,
reste du format précédant L. Ceci nécessite donc une nouvelle
barre standard L. On est à la 30 barre L.
-12
12 =20 - 8 : chute dans la troisième barre L.
-40
40 = 48 - 8 : reste à placer. On l'appellera "CONTENU".
-42 : 42 = 67 - (7+8) : le volume restant dont on dispose : ce sera,
pour nous, le "CONTENANT".
REMARQUE
1
L'étude du chelll1n So - S... - S~ - S:J, , nous a permis de poser
t
!
quelques définitions. On a vu les notions de CHUTE, TACHE, CONTENU
1
lj
et CONTENAIT. Nous emploierons durant tout notre exposé ces
~
différent. termes dans le . mftme sens que ci- desstts.
~l
•• ) Chemin SQ - St! - St, - S ''3
1
1
1
!
1
i
1
: (2.,"+ i 4- cf, '- ~ )
)
/
1
/ ~8)
1
/
\\
S''3 (2,0
4-- .... , '=-0)
J
S"3 ; ( "3 , ,l, ; 4-0 ,4 i. )
iî
1
]
1
1;
Remarque:
1j
- En pointillés sur la figure deux segments matérialisent les
1
deux tlches siuvantes (8) et (8).
1
J
Cela conduirait à la m8me situation qui aboutit à S~ • Aussi
1
1
on le laisse de c8té.
J
t

---

La partie 50 - 50t - 5 ~ du chemia 50 - 5", - 5'Z,. - 5 ~
a d'j' 'té
Tue: ( cf. ci- dessus).
!
Regardoas alors :
\\
5'~ : ( 2. 0; 41, 60)
1
-2 : Da utilise toujours le format standard numéro 2. Car·la ch.te
dus celui-ci (7) permet d'~ placer la tAche 7 •
1
-0
0=7-7
l
t ~nouYelle
!
tAche : pas de chute sur cette barre L.
\\
chute restaate apr's la tAche précédente.
- 41 : 41 = 48 - 7 :
"contea."
- 60 : 60 =67 - 7 :
" conteDallt"
••• ) chemin 59 - 5
51~
d
t
1
1
1
i
,,'?V
y
!
/
/
1
1
1
j
'\\
1
Remarque
En pointillé la partie 5", - 5~ a été
d'jà YUe.
1
Il en est de mSme pour 50 - 5~ •
1
5~ : (2, 12; 53, 72) et (8) la tAche coacera'••
1~
- 2 : le reste du premier format L ae permet pas d'y loger 12.
D'où la nécessité d'un aOUYeau Format.
1!

---

- 12 • 12 = 20 - 8 • "cjl.te"
•
•
- 53 ·• 53 =61 -8 : "contenu"
- 72 • 72 = 86 - (6+8) : "contenant"
•
~chute perdue dans le format précédent.
c, GENERALISATIONS
Mise au point
A chaque sommet S~ sont attachés, comme nous l'avons
YU, quatre Dombres :
S : i~, i~, i 3 , i 4 •
- i'1
: c'est le i i.~lL format.
ON est obligé d'utiliser cette i~~barre standard pour atteindre
cette étape ou ce sommet S.
- iL
: la "chate" (ou le reste de la coupe q.and on a déjà
entamé le format) :
a) soit dans un nOUYeau format
b) soit dans la chute restante due à la découpe
précédente.
Remarque :
• ) Cas a) :
i .. (S;. + "') = 1... (S..t ) + 1 : nouveau format •
•• ) Cas b) :
1.... (S t: .. ~) = 1-i. (S.-v )
: fonat déjà
entallé.
- 1 3: "ce qll1 reste à placer" : OD est à l'étape i,
sommet S.l •
1
i 3 (a ) = LT;r -
L
BD(j)
.1=1
Remargue :
Si on pose:
K= i~ (i) et K' = i
(i.l)
t
on a :
.) si K~K'
i ... (SÂ.) • 1 ... (Sl .... )
•• )
s1 K <K '
i 1 (S.4.. ) = 1 1 (S.À. +...) -1
- 1e..-: ce qui reste comme contenant si on utilisait la
bonne solution BS (on peut préférer l'indice donnant le plus grand
des ~)O associés à un sommet donné. Mais il faut faire attention

---

de ne pas perdre de solutions puisque l'ordre est très important).
Exemple :
• ) FORMA'r' s L. 18
•• ) Demandes
.
t
1
1
1
,
,
1
espèce
1
i
2
3
4
1
5
6
7
i
L
f
1
i
1
!
.
~
!
longueur
15
1
13
9
8
:
6
1
3
2
i
j
!
lIB demaJldéG
l
1
1
i,
3
l
1
1
1
9
~
,
,
~
\\
1
:
,
Cn1Ù
15
13
9
8
i
18
3
2
partiel
,
l
Cumul
15
28
37
45
63
66
68
68
.
total
1
i
--=-)'
Il
LT~~ = 68 ; If
~
:II
If ""
=9
1.1
~/
b) Zo = 4
(ct. algorithme'" - F - D en annexe ).
c)
les tIans :
BD(l) III 15
BD(2) = 13 ; BD(3) = 9 ; BD(4) =8
BD(5) = BD(6) = BD(7) =6 ; BD(8) III 3 ; BD(9) = 2
Remarque :
En principe on a:
b
~ z..~ '- Zo
l ci on a
~ = Z.. 4 =s;> Z· = 4
l
i
Mais DOUS allons taire comme si DOUS ne saYions pas que
1
l'optimum était 4.
1
1
1j
. . •1 . . .
1
1
1

---

5 ~ / $+ )
( •~ , CO-., f.to
~
,4-"')
.s'/4-
~'4-
~ IJ ,+-o-d' =- 31.
y ", 't--4 - (a + s) -; 1<f
â't-~ 6(,) -= 'i - )(
:ti--:!J2. <"0
r ....... ;0S!. i b 1e,
A chaque étape (ici S .... ), on descendra plus en "profolldeur"
en regardal'lt 1
1. 3 ~
i~?
( le "colltellu" i 1. dépasserait-il le "colltenaBt" i ct- ? )
!
- si oui 1 ae pas continuer la branche car il serait iap06sib1e
1
de trouver UDe s.lut10. meilleure.
i
- si Don : OB cODtinlle.
1
La figure ci-dessus montre que les branches empruntant S4- , S'e,.
1
ou S"~lle dolvellt pas Itre descendues plus e. profondeur.
1
En effet, par S't- par exemple, 011 a 1
1
i ~ 1:1 31 le "contenu"
1
ilf- 1:1 27 le "contellant"
j
Le contenant sera plus petit q.e le "ce.te••", ce qui est
impossible.

---

Re.argue :
Cette suppression de branches est intimement liée à l'écart
Ë entre la Bonne solution de départ Z. et la solution optimale Z" •
\\t
Plus petit est Emoi•• CI. aura de branches à explorer •
t
D'où la nécessité d'avoir unZ
1
o ,
une aoane sol_tion très
prls cie Z Il .c' es-t-â-d1re
\\
E.
1
:1:
2 0 -
~
f
a'Yec E = r , 2 ou 3
( cf. l'article sur l'6cart de la solution obtenue par First Fit
Decreasing dans Seientific American , Yoir Annexe).
\\
D. AMELIORATIOlf DE LA BORIIE 2
m'OPTIMISATION
0
t
1
\\
!
!
On pourrait appeler "solution (de base) réalisable", en réfé-
1
rence au simplexe, tout chemin allant de la racine et aboutissaat
\\
réellement à une feuille dans l'arberescence.
l
A chaque étape, la borne i~ a été obtenue à partir de la bonne
~
solution BS (OU Zo). On sait à tout 1I0moent le ft contenu" i ~ , et le
nombre de formats utilisés i~ •
Soit :
Co
= i~ ( STOT'~E"1)
C'est-à-dire le ..ombre ou formats standard cbtenus après
ayoir entièrement descendu une branche. ~t1 reTient au .&me de
remarquer :
1 ~ ( S TOTJ)~l'o1) = 0
J
Dési~ons par Beo ? ce DOUyeaU chemin ou "solution réalisable",
dont le coat est Co. Soit a_ssi Be l'ancienne solution de coat Zo •
Si
<
t
Cd
Z 0
on prendra comme solution de référence, non plus Be, mais BC• •
Il Y a donc pour la suite remise à jour de tous les indicateurs
i ... , iL' 11
et i lt- • EJl particulier i't deTient i ' 't- :
i'lot-
= i ct - (Zo-c.) L

---

E.
REMARQUES
Dans cette MaDière de procéder, nous allons toujours ell
affillant la solution. 'route solution réalisable "courute" BC~ est
sinon meilleure que la précédente, du moins équiTalente à celle-ci.
On peut sch'matiser notre démarche comme ci-dessus.
( C'est une iBterprétation en termes de ~olume ).
Lr<:'~~JJ-t--"Contellu"
"
. " ./ /,'...
_ .. _ Bonne solution Zo de départ
( chellin in! tial Be )
.) Cas d'amélioration
"=- _ - Chelll1n BC de colt Z
Nouvelle solution réalisable
~ --- de coat q, <: Zo
( chelll1n BCO )
•• ) Cas d'équivalence
___ - Sollltion"de référellce"
- .. - - - Solution équivalente
f
t
îi1
Interprétation de la démarche
1î
Ici on Toit que toute l'arborescence est explorée. Mais
nous insistons sur le fait que tous les cas sont envisagés de
manière implicite. Le coat de la solution réalisable courante est
toujours meilleur (au sens large) que celui de la précédente solution
1
____ -L.
_ J
_...L
.......
_ _
_ ..1 _ _ ..1

---

+0
Exemples résolus 1
1. Exemple
L 1:1 9
eep.
1
2
3
.)
.~
s.
=fGS2J 3
long.
4
3
2
..
4+4(1)
)
Zo l
4(5)+ 3(2)+20
n. DES.
3
3
3
~
~ 3+3(3)·2(1
2(7)
c. .ul
12
9
6
partiel
~ Zf) = 4
ï
c_lll
12
21
27
27
total
OD a : ~ f: Zo
1
~ procédare Lasaf l ( cf.
i
f1gare ci - dessus ).
1
i
Rellargues z
OD écrira désorllais 1
1
1
(9;li,x
3 , . 1 x 3 , s , . ( 3 )
t~
1
.) format
j
•• ) OD yeut trois flans de loagaeur li, pour l'espèce 1
••• ) OB veut trois .spèce de flans de long~eur li, , l , ~ en
BOllbre respectif 3 , 3 et 3.
2. Exellple 2
(9;li,x
2,J.-,,2,Sx 2 , ! . , l , s " l i " l , ! )
Ide.tique à l'exemple
avec<La ordre d'entée différent.
\\
1;
3. Exemple 3
~J
( 9 ; 1..2, l l t z . §., §.x. 3, l , s,)
ex. 4
( 9 ; l l
i,.1,!2,S,~;(2,~,~)(..2)
)
\\
ex. 5
;~
( 9 ; 12 , .1 , 12 , s, , i , §. , ~ x 3 ) 1 ordre induit par
le calcul Zo •
1
Les exemples 3, 4 ou 9 sont les m'.es. Ils montrent seulem.nt
l'i.portance de l'ordre d'entrée.

---

4. Exemple 6
(9;1l-- 5,.1 Jt
5,~..l( 5)
5. Exemple? : (Hala. )
( 524 ; l l i , 252 x. ? , 112. J(
5 , lQ§. J( 4 , .§1t 1'\\ 2 , ll,
a , .ll , g x 3 t 1Q. )( 6 ,.:i ~ 2 )
n.8
~
( ~ ; ID , 252 x?, gz x; 5 , 106 J( 4 , ~
~li
J(
1
g)(.3,1Q.J(,6.,2.
~2)
C'est ua exe.ple de cas partie.lier comme celui de S. Balas.Se.
Do.br. de flaae trop importaat ne nous a pas perais d'avoir . .
résultat e. temps liaité, dans Lagal propremeat dit. Mais F.r.D.
GU r.F.D.PHELEIE "aB. la solution: Z • Zo • Z • MI•• si OB
ealive le poids 47 ( cf. ex. 8 ) : ( temps immédiat ).
6. Exemple 9
( 9 ; l l x
4,.1)(
4,~)C 4)
7. Exe.ple 10
( 18 ; 12. , oU , 2. , ~ , ! .t( 3 , .1 , g, )
,
1
1
1
1
1
i
1
1
1
1
i
1
î1
)
1
j
!!i1!
1
1
1
!

---

---;;-""'0
.....
~
- ----
,--...
-
- ----..P"-----
- - - - -
~------..-
~.
__----l)!
_
'-"0"'\\
_
....t.Sl
_
- - .....
---~
~
---~._ --:-
..
--\\3-
--
~.
o..c
,...
---
--~--
...0\\
--
- t!-
~
- - y -
U'
~
---;;;::::-
'ë
~----
-
--~
- - '
~-
---.-0, __
--~.
o
'~
---;;;::_
---OC>
---_.~~-
~---
~
' - -
~-
- t
~
~
...--
--.9 __
_
_
_.~~
--....
- -
~--
-------u:r-
~
-
-.':"-_-
....
-
----
1>0
---
_-
~_ .•.

---

La d'aarc~e de aotre r'solutioa diY1se le8 exeaples eB deux
grandes cat'gories. La prea1ire cat6corie est celle pour laq.elle
BOUS aTons 1
S. s
Zo
~
Z ""
•
s.
( temps d'exéc.tioa ima'diat )
( Rotoas biea ' . .s cette classe l'import. .ce des heuristi-
q.es F.F.D. et F.F.D.PIELERE. )
Ce a'est que la aecoade catégorie
( ! =F Zo
Zo - ~ =1= 0
)
!
qui dea. .de l'appel de l'algorithme Lagaf. C'est - à-dire de la
procédure arboresceBte pour prouver l'optimum. Dans cette classe,
la complexité da problèae est telle qu'il nous faut distinguer
les exemples de petite taille ( TOTDEM ~ 10 ), et cewx de taille
plus importaate ( TOTDEM>
10).
Rappel 1
fldS
Z {
(
li, I l )
,
:1 = 1, li }
TOTDEM
•
•
~
Ri
i
• 1
catégorie
taille
ORDRE DE TEMPS pour a t teiBdre
l'optiaUll
sans 1aportuce
immédiat
seconde
2
petite
10 à 20 secondes
gr_de
7 ai••tes
/
pas de résultats en
teaps liaité ( très sOUTent poar
exeaples à taille
15)

---

1
1j
1
1
t
1~,
1
î1
1
1
i!
1

---

--
~....
......--_.._._- ,--_.__....•.. -.
~
d'eatrée
z*
'lri .,-
1
9
4
4-
4-
4-
0,~3
6 s.
croiss8Jlt
a'll
•
(après
2
9
4
5
5
5
0,25
laasard
5 nnutes)
:J
3
9
4
4
-
4
0
'*
(imméd.1at)
4
tri. d'-
4
9
4
4
-
4
0
2 6.
4
croiS.dt
au
5
9
4
4
-
4
0
4 s.
4
b.asard
tri d6-
~
6
minutes
15
5
6
6
6
0.20
5
croiss8Jlt F+5 second.
tri d'-
7
33
7
7
7
7
0
~roissaJlt
(n:ellp1.
•
de Halas)
]
8
33
8
7
7
7
0
t (imm~dia.t)
tri d6-
9
9
3
5
5
5
0.25
19 s.
5
croiss.at
10
9
4
4
-
4
0
(im.mêdtat)
4
.....'..•""n''''',."'.'',.•.,.~.............-.~_ •......-...........,...,,.,..''"'~. _ .......,......~,-~"............''',......,l1=''...F'''~~_" ...'.....".,~·....._ _.....--"''''''''"''''''«·.......,'~'',_·~·.",-""~",_,~,,,~.',,,,,,,.,_,.~,~_<, .._,,•.,~_....~"t"'"_''''~''',,.''''"'~1'''"''T--~''''''''''·''''''''Y'''·· _ _'W_·C''''''~''_·'''·_'''''''''U'~~''''~~P~"-;;;T;'_l>1t~'·,
....·_","'C~....._"l'U"'"'
""',,",,,,,","""~_ -
"' lA _"'".,......-..~~,'l""~.,...,'I"""i"'~_....."'"""".~..-_'''''''''',.,,''''-''''~,''''.,•..~.._- ,~"-,-,._."'._""~

---

-:K>t
!,
1
CON C LUS ION
1
1
:f
La complexité du problème de découpes est telle que les métho-I
des jusqu'alors proposées ne sont pas d'une efficacité suffisante,
!
!
quand OD cherche la solution optimale en entier.
~
i-
Les méthodes de programmation linéaire tiennent sou~ent
lieu d'approximation dans ces problèmes ( de découpes ). C'est notam-
ment le cas lorsque le noabre d'unités - formats- est très éle~é. On
considère qu'il est raisonnable de négliger les décimales, quand l'
ordinateur indique 1. 379. 245, 52 tormats. Par contre, c'est loin
d'Itre le cas pour celu~ qui doit choisir entre les 8olutio~8 avec
3 'eu 4 formats et ~u1 veut eoanaftre la meille~re.
E4 pratique, le problème de l'obten'ion de l'optimum se pose
pour de petits exemples.
Ainsi pour les problèmes de taille la que nous a~ons traités,
la conTergence de notre algorithme est très rapide : la à 20 secondes
d'Unité Centrale ( C. P. u. ).
En!in pour les problèmes dont la taille est comprise entre
la et 15, nous aTons remarqué qu'un temps de 6 minutes est suffisant
pour trouver la solution sur IBM 370/158.
La méthode que nous proposons n'a pas la prétention de résou-
dre détinitiTement les problèmes de découpes linéaires. Cependant
1
son principe peut 8tre d'une très grande importance dans l'explora-
tion de l'arborescence.
1
Avant de terminer, nous voudrions taire remarquer le rele d'
1
1
une bonne programmation dans la résolution de problèmes aussi comple-
~
xes- ( NP Complet ). Très souvent, il n'est pas vain d'épargner le
!
temps d'unité centrale de l'ordinateur quand les durées de calcul
!
dépassent la ou 15 mi.utes !
1
1
l
1
j
!
1
J
!~1i1\\lll
1
t
!j,

---

~rr
1
!
J
ANNEXE
1
f
1
-
Heuristique F. F. D.
(
811 fortran )
- Al&orithme Lagal.
( en P. L. 1 )
1l1
%
~
lJ
1
1j
j
t

---

C C C
PI.IOOOIO
I:ŒAJ..
l..
1"'1 .. (OO()20
!
DIMENSION 0UII00l
I:'J... 1.000 ~(o
5::;:'; CON;r NUl..
I::'l.. (O()()40
r~E(:1 0 (~5, ;{~ ".' l, \\' i'~
r;'l... tOOO~·.·lO
C
LECTURE DES FLANS PAR IRA~l..HES DE 10
1::'1.1000ôO
/10
3
I<A·' 1. ,,",20
1"'1.. 10(\\0/(;
JI ..'J 1-(1\\0","':1. :' *:..'\\.1
1'.'1.. roooco
1
1~.~·'I(f)*?()
,::'1... r 000';'0
1
11"'( 12 .GE, N) L!.""N
f'1.. IOOl()()
t
.5 REA/I(5.*I(DDIII,I=Il,:l.2)
1'1.. r 00 l 1(,
1
Wf( rr E ( " , :1. :1. ) 1. • N, 11> Dl [ ) " 1:":1. , N )
F'I... r 00 1.:,;
1..1
F Ui(MAT (/i' ,2:<,
l:cmt1,)]
El
IH<:' ,Fi .2,:.ïX, 14, (/ .::'X,:.'iF/ .2) 1
I:'I...JOO
f
1.i()
CAl..!.. fl"l'.(i. ,N,ln:)
l·'f \\'Oül!t()
wr, (Il'; ( ô , 1.1 ) J.. , N. ( nI' i 1 ) , J':I. • N )
,:' 1 1 () ()"
"1.;
..oID :",::i:,
',1.. i'(.i0.1.,'.(,
::;TU,'
J·'L.ld)] ..· ,
EN!)
l '1 J ()():I. ,;:.>
C
l' i 1 ()ü.l.·;.)
C
1'1... I 00;,1..0
bUBldlUT :,: NE !.1..t(J.. , N, DO)
F'l..l 00;' J 0
I([(.'d..
L.
F'L 1 00::.::'(
Ü 1 MEN::; :u:m B/I 1 :i (JO) , 1 B 1.50) ,F: Ir<I 140,:JO) , m::::,n:: 1 ;~O)
1"[.100:::',(;
r INITIALISATION
i:;'!... r OÜ:?40
,.11,'::1.
F L 1002"'iG
II'I 1 1 ) ···":l
1::'.T()0260
arm 1 1,:l) ·'''l<D 11)
1"1.. J ()O:.'/O
f(E!'TE (1 )"L ···BD 1 1 )
f'L.I002lV)
IFIN.LT.2)GOTO 9/
II..IoO:'·I!)
1.10 3/
1'<'" N
r'l...l 003(, ...
X"BDI1)
l'l.. .cOO;~1 0
r.n :;':; J,:I, ,j 1
1'1... l O() ;',:.'. o
IFIX.GT.RE5TLIJI)GOTO 25
r'L IO()T:io
r f,FSTF DU CHUT
1::':... IO()3·'~I)
l'ü ( ,.1) :" 1 El l ,.1 ) 1-1
,.' L. 1 ()O:J:, ,)
BIBII,.I,H!I.J»"'X
l'I.l()036()
l:iESTEI_J)·~rŒSIEl,J) X
i"L r 003?1)
GOTO 37
1"1.. I003BO
.2:~) CONT r NUE
1"1...10039<)
C NOUVEAU FORMAT
1'1.. IC04()ü
,.1:1 ~,.I1 +:\\
l'Li C'04i. ()
fŒSTEUI )·L)(
I::'J.. JO()4?O
1 Ü (,.11) ".:1
1"1'... 1()04.·~()
HI El1 1,';:[ , 1 ) ,"x
Fi. J 0044C
.\\' CONTINUE
FL J 004:iO
(" Bl1.:1
.. ·:·hl)
F'I...10()4é,()
1~·0
PLIOl!'!70
DU 44
"J"'.!" ..ll
Pl.. T004U()
,)2" r l.< 1 ..J)
FI.. 1004'/0
DO 41
1\\,::1, ",1;:.'
F'L.·!:(,O;:;t/(1
l
I+:I
FI.1()O::;10
t'Ii ( T ) ... B i' e 1 1,..1, l' )
F'L.. (OO~i2()
4t
LIINT INUL
1"1. 1 ()O~.'3()
I! 1':[1'; 1[(..J)
1·'1 TO{)~j40
,,1 kT r E ( (., r .1 (, ) ..J , fi , 1El[1 ( 1\\1\\ ' , 1,1'\\::':1. , ..J;> ;.
j··l.. 1OO~:.:'~·):)
u' FOf,i'lIHI /,2X, 'F(Jf(MAT NU :', J3,:'i};, " ..:HU il::. ",' ,11' .::;, l, v'
'('.',j(,.':)
).'! r O()I if! (;
44 CUNTINUE
WfnTE(b,4'i'),J1
1
"\\9
H1f(rhYll///,'
Pl'
"\\If"';'., ""
d4)
1'1...1. ()Oj"·'(j
GO1'0 'i'i'
F'"
]OOéO I
1
;
97 WRITEI(;,:')())
1··'1 .~. (JO/).J. J.)
50 Füfa1,YI ( r, ....
1..,':;"::.1.11,)
:::1 .'. (J (.J /i ~ï ()
99 CONT r NUI:,
fI... ~:Qo(j_~~(j
RFTUI,N
r'l. 1 00640
END
FL l 006:'j()
1
!
1
l
r
!
!

---

r~------.;~.:.=.::.=
,!;' ....
f'l.LOOO (0
LAGAr :
"
,.
P1.100l):',)
PI(OCEDLlfU.
Of'T iONS
(
~irdN l
;
[leL
(
lOTI1EH
•
LI
,
li)
,
NF
) SIN 1·· IX([1
PL..LO()\\),~\\:'
Pl.IO()\\)4t.\\
Del
( L
• rrrn
) Ille Il nAl
1
f-lIOül>:-,P
l)CL
(
lW(,;;:O)
•
MSI.4D(.,~O) ) ElIN FIXED
f·'L.IO(lüt'!v
nCI
1 UNG( :'~fJ)
IJLe
fLUA 1
;
üet. SI OC( ~IO) .1"1 r r ( l.) ;
."lIOOOl'l
f'l l OOOlh,
Del
(
l'AV ,
TM-
)
CHAF\\( l6)
VARYING
;.
F'LIOOQI;'1
['CL
lIME. ~UILT CN ;
PL I()()1(,(j
Del COR DLe FLUAT ;
PLIOO.lI.O
Del
1 IdN FIXED ;
F'LI00 1::."0
1*
ASSIGHMENT5 .1
PlI(}O.LJO
l.UNG ( . ) ::
0
;
f'l1(10140
STOL(')
-". '0'[1:
;
F'LI\\)O'1~)O
/ . LuHA INPUT *1
F'lIOOI60
r-u 1 SKif'
"
f'UT SKIf' LllIT
(
'FORMAT'
)
(A)
Il
PLIoOl/v
r
Gt'f
LIST
(
l
)
;
r'l100!IJO
è
PUl
sxrr EDIT ( 'NOHf1F\\E DE FLANS' ) CA;'
PUOOt90
'~
GEl
LIST
C ru 1(lEM
)
;
f'U002ùO
PlI0021';)
PU 1 SKIF' EhIT
(
'l.fS rLANS'
1 <AIl
)
;
GU
LI61
(
\\
LONliC l > LIU l
::::
1
TO
TOTDErr
)
PlIoo:~20
/k. l'RINI
OUT OF
1 HF
LNf'Ll rs
r'U00230
*1
l, ..
F'lI0024<)
PLJI SKH'
ftJl
SKIl' EnIT
(
'FOttl't.'f:'
,
L
)
(A(7},f(9,J»
F'lI00250
FUT ::Jt(1P EIIIT
(
'NOMBRE DE FLANS:'
,
TrJTflEH
)
PLI002bO
,'$~ w
f'U 1 SKIf' Er.)'
(
'LES FLANf.i:'
~
CA)
;
F'LI00270
,. ;
PlIOO~80
PU \\
SKIt"
"'UI ED11
(
( LONGe!) DO 1 :iii
1 ro TDTDEh
J
)
«S>fCl::J,3),Sl\\IP)
PLI00290
PLI00300
/* INIT lALI5ATION .1
L TOT = SUH ( LONG(.)
f'U00310
ZJ
PUOOJ:0
CEIl.
< LTOT 1 L
PU00330
ZO " T01DEH ,
1
i
PLI00340
r.OI\\: e- 0
i
PLI003:iO
1. F"lRSl' LEvEL CAL l
. /
PUOOJ60
TI\\V ~ TIME ;
CAU
ESSAI
(
1
1
0
,
1
,
L ,
LTDT
,
TotllEH'«L
)
F'lI00370
PUOOJBO
TAr- "" TIHE. f
PU00390
1 * PR l Nl OUT OF lHE RESUl. 15 .1
PU00400
PUT SKIf-'( 2)
1
PUT SKlr' EDIl
...
. . . '
)
(A)
'
SOl.UlION
OPlIHAl.E
PU004tO
PLI00420
f:'ljl
~f(IF'<;:n
•
PUT SKIP EDIl
'TEMPS AvANT:
'
,
TAV
)
(A,A)
•
PLI004Jo
PUT SKIf' EDIl
'TEMPS APRES:
'
,
TAP
~
(A,A)
;
PUOOHO
PLI004:5<i
PUf 5KIF'''~) 1
PUT SI\\.LP EDIT (
'NOMBRE MINIMUM DE FORMATS:'
,
ZO )
(A,F(~J)
;
F'Ll00460
PLl004;0
PUT SI\\lf'I21
1
lONGUEUR'
)
(x(S),A(4),X(6l,A(B»
Il
PU00480
pur St<H' EDIT ( 'FLAN' •
f'UOOHO
F'1I! SKIf'
~
f'LIOO~üO
LLO
r .::: S ro HnnE"
f'lIOü:i10
Ni"
MSllfl (1)
;
eX(6) ,F(2) ,X(9) ,FC4.0»
PUI
PU00S20
~;KH' EDIT
C Nf
1.0NGCNF)
PLIOO:)10
E-~N[I
f'lI0054(.1
r'UT
SKIf
1
r-u'r SKIf' EDII
f'LIOO~.~O
CiBI ' . '
1
(A)
1
F'LIOOS6·J
ru 1 sx rr:
PLI00570
REfUHN
;
PLIüO~B(.I
ESSAI
:
PRflC["DURE
(ANF
AN.!
• AIl , AI2 , AIJ , AI4 ) RL~URSiVE ;
f-'LIU059\\)
Dr:l
C ANF, ANJ
,
AIl
&IN FJXED
1
r'U00600
I)CL (
AI::!
,AIJ
A14
DEc
Fl.OAT
,
F'LI006l0
[JCI
(
NNF
,
NNJ ,
'J r l
BJN
FJXED
1
F'Llü06:!O
[1 Cl.
(NI2
NI3
NI·'
l.DF
,
LFP
1 l'EC
FLOAf
PLl00630
t'L1D()l.4Ci
U f'
UJIIIj(~Nf )
If
t.F'P ',,1. AI;'
PL.1G06S0
f"LI00660
THE:N no ;
NU
A{l
;
"1.1006/0
NI2
AJ2 -
LI P
1
FL 100680
F'i...I00690
NU '>AI3
[FP
F'U00100
NI4 ~ Al4 - Lf P
f'U00710
END
FUOOt:èO
1..1..3E DO ;
NU
.lII
AI 1 t
1
Il
PU00730
PLI00740
NI2
l
-
lFP
,
NIJ
~ AI3
LFP
f
PLI007~G
NI4 ~ AI4
(AI2 t LFP 1 1
PLl00760
F'LI007 Iv
[ND ;
PLl007B0
NN J
ANJ + 1
f
Pl.l0079(,
BD CNN~I)
;::. ANF
Il
PLI{.JOElO,-,
IF NN,J
f01DEH
l'LI008tO
fHEN DO ;
PLI008:0
IF Nil < ZO
1
PLH')OE30
THFN
no ;
H6BD(~)
= BD<.) 1
f'LIOO(f4û
,
f'LIOC3~0
ZO "' NIl
Il
LON
(T01DEH -
ZO ) •
L
PLlOOS60
1
END
Il
PLlOOa70
PLlOOBBO
RElURN ;
END 1
PLI00a90
l1
IF NI3 ~ (NI4-CORI
-
NIl
ZO
PLI00900
TH(I~ rŒTuRN
;
PLl00910
STOC(ANr)
~~ '1 'B Il
PLI00920
PLIOO'i'.!(J
LCJF := 0
;
110 NNF
"" 1
ru TUTLrEI"t ;
PU00940
IF
,
STUC (NNF)
&, LOfllG (HNF)
,~ LOF
F'LlOO%O
F'U0096('
THE:.N no ;
GAl.L ESSAI
l
("NF,
NNJ
,
N I l ,
N12
,
NIJ
1
N14
J
;
PL 100910
PlI009Hù
LnF = LONG(NNF)
i
PlI009'r'O
[ND'
l'Nil
h~lO)(JiIC,
F'CI01V]J
~,I 01..(ANF }
'0' El
PLI\\ilü2(J
Rf -Tl/RN ;
PLIO] (;j(,
ENIJ [SSAl
F'l IOIO'lu
ENI' LAI3AF

---

B 1 B LlO G R A PHI E
BERGE
C.
_II
Principe de combia.toire ", Paris, D1Inod, 1968.
_n Graphes et Hypergraphes" , Paris, D1lDod, 1973.
COFFMAN
E.G. et ses collaborateurs : " Computer and JOB - SHOP
Scheduling Theory ", W11ey Intersciences.
FAURE
R.
_II
Eléments de recherche opérationnelle ".
Gauthier - Villars, 1968.
_. précis de recherche opérationnelle ", Dunod
Décision.
i
FAURE
R. ,MALGRANGE
Y.
f
N
Une méthode booléenne pour la
résolution des programmes linéaires en nombres
J
entiers ". GESTION, 6, 4, Dllméro spécial sur la
f[
recherche opérationnelle, pp. 250 - 260, avril
t
1973.
1
- • Quelques aspects de la programmation linéaire
en nombres entiers " • Extrait des Actes du collo-
que de calcul numérique et mathématiques appliquée
de Lille ( 6 au 11 juillet 1964 ). Publications
scientitiques et techniques du Ministère de l'Air,
N° If. T. 157.
- "Nouvelles recherches sur la résollltion des pro-
grammes liBéaires en Dombres entiers ". GESTION,
8, 6, pp. 371 - 375, juin 1975.
GILMORE
P. C. ,GOMORY
R. E. : " A linear programming approach to
the cutting stock problem ", ( 1961 ), Ops Res. 9,
849 - 859.
- " A linear approach to the cutting stock problem ",
Part II Ops Res. 11? 863 - 888. ( 1963 ).
- The theory and computation ot knapsack tunctions n,
Ops Res. 14, 1045 - 1074. ( 1966 ).
GONDRAB
M., LAURIERE
J.-L. : n Un algorithme pour les problèmes
de recouvrement n, Rairo V 2 ,33 - 51, Juin 1~75.

---

BELP
M., KARP
R.M.' li 'flle tra~.lli.C 8ales. . . ,roDle. and minimum
spanaiag trees ., Operations Research 18,
1138 - 1162, 1970.
LAURIERE
J.-L. :
" Ua laa,a,e et ua programme pour ~.oDa.r et
r'lI!Jo.dre des probli.es combiaatoiree ", Th~ee de
Doctorat d'Etat, Uni~ereité Parie VI, 1976.
LIN
S.
" Computer Solutions of the tra~elling Sales. . .
pro'leas ", Bells System tecàB1cal jouraal,
~ol. 44,1965.
LIN S. ,KERIfIGHAlf
B.W. : " .AD heuristic algori th. for the travel-
liag Salesm. . problem ", Bell system technical
journal, Vol. 52, 1973.
LITTLE
J. D. C. ,MURTY
K. G. ,SWEEKEl
D. W. ,KAREL
C. : • AB
alcoritha for the tra~elling 8ales. . . proDle.s .,
Operation Research, Vol. 11, 1963.
RITZMAlf
L. P.
" The efficieDcy of Computer algorithme for plant
layout ", MaaagemeDt Science, Vol. 18, 1972.
.
ROY
B.
" Algèbre moderne et théorie des graphes ",
tomes 1 et 2. DUDOd , Paris, 1970.
SIMMONARD
M.
:
" Programmation l1.éaire ", Paris, Dunod, 1962.
1
i
1
1
_J

---