RI~SOLUTION DES P R O G R A M M E S LINt~AIRES

A V A R I A B L E S M I X T E S PAR LA PROCI~DURE S.E.P. (**)

Philippe Herv~ *

Traba/o presentado al H Coloquio Fran- co-Espaaol de Investigaci6n Operativa y I V Reuni6n Nacional de lnvestigaci6n Operativa

La m6thode de r6solution d6velopp6e et exp6riment6e ici a 6t6 sugg6r6e darts un article de B. Roy, P. Bertier et Nghiem P.T. [14]. Elle consiste essentiellement

prendre pour 6valuation par d6faut, en chaque sommet de l'arborescence S.E.P. une valeur fournier par la r6solution d'un programme lin6aire classique.

Dans la premiere partie, l'auteur expose la m6thode en d6tail et developpe

quelques points sur lesquels la proc6dure g6n6rale laisse une certaine libert6 d'adap- tation pratique.

Darts la deuxi6me partie, il d6crit et commente les r6sultats exp&imentaux obtenus sur des exemples num6dques issus de probl~mes 6conomiques r6els.

La troisi6me partie, en guise de conclusion, contient quelques r6flexions sur la raise en oeuvre pratique de la m6thode, sur la mod61isation des probl6mes variables mixtes et sur l'analyse post-optimale de la solution.

(**} Ce papier a et~ publid en France dans la revue METRA, vol V1, n ~ 1, 196Z

(*} Compagnie de Raffinage Shell-Berre, Paris.

85

I--DESCRIPTION DE LA METHODE

1. Introduct ion

Depuis quelques anndes, un certain nombre de mdthodes nouvelles pour r6soudre les programmes lin6aires ~ variables enti~res ou mixtes ont 6t6 propos6es, no tamment dans [21, [3], [61, [81, [1 I], et [121: la plupart d 'entre elles sont bas6es sur des proc6dures d 'exploration arbo- rescente de l 'ensemble des solutions possibles.

Ces proc6dures sont d 'un emploi tr~s g6n6ral en math6matique combinatoire, emploi qui d6passe largement le simple domaine des pro- grammes en variables enti~res. Parmi elles, un type particulier de proc6- dure a 6t6 remarquablement formalis6 par P. Bertier et B. Roy dans [4] sous le nom de S.E.P. (S6paration et Evaluation Progressives). C'est dans un article de ces m6mes auteurs que le principe de la m6thode d6ve-

lopp6e ici 6tait sugg6r6 [ 14].

2. Principe de ia m6thode

Le probl6me P ~ r6soudre est le suivant:

Minimiser a x + b y, sous les contraintes

A x + B y = c x ~ O y a des composantes 6gales ~i 0 ou 1

Ill

x et y 6tant des vecteurs ~i m e t n lignes respectivement, et A et B, des matrices (p X m) et (p X n) respectivement.

Appelons J l 'ensemble des n indices du vecteur y e t E l 'ensemble

des solutions, e'est-h-dire l 'ensemble des valeurs du vecteur (x, y) compa-

tibles avec les contraintes [ 1 ].

86

1. S6paration progressive

La m6thode de r6solution revient ~ construire une suite de parti- tions E de E, chacune d'elle se d6duisant de la pr6c6dente par dichoto-

mie d 'un des 616ments. On s'arr6te quand la solution optimale apparaft

avec 6vidence, de la faqon qu 'on verra plus loin, darts l 'un des sous-

ensembles qui consti tuent E.

Les sous-ensembles de E que l 'on consid6re sont d6finis ainsi: 6tant donn6 deux sous-ensembles disjoints J0 et J~ de J, on appelle E(Jo, Jt ) le sous-ensemble des solutions de E telles que:

y / = 0 si jEJo et y / = l si jEJ~

La skparation, c'est-/l-dire la dichotomie de E (Jo, J~) consiste

choisir un indice ]* tel que:

~*E J - (JoUJl)

et ~ remplacer dans E, E(Jo, J~ ) par les deux sous-ensembles:

E(JoUI/*~ ,J~) et E(Jo,J tuI j*})

2.2. Evaluation progressive

A l'ensemble E(Jo, J, ), associons le probl~me P (Jo, J~ ) suivant:

Minimiser a x + b y, sous les contraintes

x>>- O ) ) = 0 si iEJo y / = 1 si jcJ~ O< y<~ 1 si j E J - ( J o U J ~ )

[21

Appelons v(Jo, J~ ) la valeur de ce minimum; V(Jo. J~ ) constitue, en g6n6ral, une &aluation par dOfaut de la valeur de la solution minima-

le de E contenue dans E (Jo, J~ ). Deux cas particuliers sont/ l envisager:

1/ le domaine d~fini par les contraintes [2] est vide; alors, a for-

tiori, E(Jo, J~ ) est vide. Convenons que dans ce cas:

87

V (Jo , J~ ) = +

2/ Le probl~me P(Jo, J l ) a sa solution telle que:

g / ~ J - (JouJ~) , Yi = 0 ou 1

Alors, la solution de P /J0, J1 ) coincide avec la solution minimale de E contenue dans E(Jo, J~), et:v(Jo, Ja ) est -l"kvaluation exacte de sa valeur.

Remarque: Ce mode d'6valuation par d6faut de la solution minimale de

E contenue dans E(Jo, J~) n'est pas le seul qui se puisse envisager.

Divers autres modes d'6valuation ont 6t~ propos6s [ 14], mais la plupart

d 'entre eux ne sont applicables qu 'aux programmes lin6aires comportant

seulement des variables enti6res.

2 .3 . P r o c 6 d u r e S. E. P.

Supposons qu'~ une certaine ~tape on soit parvenu i une partition

6 de E. On choisit alors dans 6 l'616ment E (Jo, J~ ) qui a la plus petite

6valuation v (Jo, J~ ). Deux cas sont possibles:

1/ v(Jo, J~) est une 6valuation exacte; c'est alors la valeur de la

solution optimale de E, et la r6solution est termin6e.

2/ v(Jo, J~) est une 6valuation par d6faut. On choisit alors un

indice j* tel que, dans la solution de P (Jo, J1 ) on a �9 0 < y/ , < 1.

On op~re une s6paration de E(Jo, J~ ) ~ l'aide de l ' indice/*, puis on recommence la proc6dure avec la nouvelle partition E.

2.4. Adaptat ion pratique de la m6thode

La proc6dure d6crite ci-dessus laisse une grande libert6 d'adapta-

tion sur les deux points suivants:

- le mode de r6solution des problemes P (Jo, Ji ). - le choix, ~ chaque 6tape, de l ' indice/*.

Or, on l'a constat6 sur t o u s l e s exemples num6riques trait6s, la

qualit6 de la m6thode d6pend tr~s largement de cette adaptation.

88

2.5. R6solution des probl6mes P f.lo , J~ ) {*)

A) Au cours de la r6solution de P, la presquc totalit6 du temps de

calcul est consacr6 ~ la r6solution des 15robl6mes P(Jo, J, ). I1 importe

donc d'adopter un enchafnement judicieux de ces probl~mes de faqon

que chacun d'eux se r6solve en un hombre minimum de pivotages.

Une remarquc ~'impose d'embl6e: le probl~me PfJo tJ I]*}, J~ ) se

d6duit du probl6me e ~Jo, J~ ) en ajoutant aux contraintes [2] qui d6fi-

nissent ce dernier la contrainte: yj . <<. O. (I1 en est de mfme du probl6-

me P(Jo , J~ u t/*~) avec la contrainte y i . >~ 1).

En cons6quence, la base optimale du programme lin6aire P(Jo. J~) est base duale-admissible pour les deux programmes P(Jou I/*l, J~)et P~Jo, Jl u {]*1).

Cette propri6t6 sugg6re la proc6dure suivante:

- prendre pour base de d6part, pour la r6solution de ces deux

programmes, la base optimale de P(Jo, Jr). - r6soudre ces programmes par l'algoritl~me dual de simplexe.

B) En pratique, 6crivons le probl~me P (Jo, J~ ) sous la forme sui-

vante:

Minimiser a x + b y, sous les contraintes:

(y)I ' [ \ 0 , , I / t J

x ~ O , y > ~ O , z>~ 0

1 [31

(*} La lecture de ce paragraphe n "est pas indispensable pour la comprehension de la suite.

89

I repr6sentant la matrice unit6 d'ordre n, et z 6tant un vecteur de varia- bles d'6carts associ6 au vecteur y de faqon $ repr6senter la double

c o n t r a i n t e ; 0 < y i < 1 par :y / + z j = 1 , y j ~ 0 et z i /> 0.

Dans cette formulation, un probl6me P (Jo, J l ) particulier se ca- ract6rise par le fait que:

Yi est hors base si j ~ Jo z i e s t hors base si j ~ Jl

Pour r6soudre le probl6me p (Jo u I/*~, J~ ) on proc~de donc ainsi:

1/ Initialiser le probl6me darts la base optimale de P(Jo, Jl ), c'est- ~-dire faire l'inversion correspondante.

2/ "VerrouiUer", pour les maintenir hors base dans la suite du

calcul les variables (yj/j ~ Jo) et (zj/j ~ J~ ).

3/ Faire sortir la variable yio de la base par un pivotage dual appropri6.

4/ Verrouiller, pour la maintenir hors base, la variable y/o.

5/ Continuer ~ r6soudre, par la m6thode duale du simplexe, le programme lin6aire ainsi d6f'mi.

Pour r6soudre le probl6me p (Jo, J~ u I]*l) on proc6de de m6me,

mais c'est zio qu'on fait sortir de la base.

C) Si au cours de la proc6dure S.E.P., on rencontre un sous-ensem- ble de E auquel correspond une ~valuation exacte v*, on sait, de ce fait, que jamais plus, par la suite, on aura ~ explorer les sous-ensembles de E d6jh rencontr6s qui ont des 6valuations sup6rieures ~ v*: on peut donc

les oublier. De m6me,si au cours de la r6solution d'un probl6me R~(Jo ,Jr). la fonction 6conomique de ce programme lin6aire, qui augmente h cha- que pivotage duale, vient h d6passer v*, on peut arr6ter la r6solution de P (Jo, Jl ), sachant d~s lors que E (Jo, J1 ) a une ~valuation sup~ri~ure ~v*.

2.6. Choix de l ' indiee/*

I1 semble que ce choix ne peut se fonder sur aucune th6orie math6 matique rigoureuse; il pr6sente en cela une analogie avec le choix de la

90

colonne pivot dans la m6thode primale du simplexe, en programmation

lin6aire classique.

Nous avons exp6riment6 trois variantes, toutes inspir6es par des

consid6rations intuitives tr6s sommaires:

- Variante I : prendre j* tel que:

iy/ . - 1/21 = min / l y j - 1 / 2 1 / j E J - (JoUJ1) I

- Variante II : prendre /* tel que:

[b/,[= max t b j / j E J - (Jo U J1 ) , Y/4= 0 et zj 4~ 01

- Variante III: prendre j tel que:

aj. = min !aj/jEJ- (Jou J1) , y/ vS O et z/ r OI

avec a/ = min (yj , zj),

Dans ces trois cas, les valeurs de y/ et zj sont celles de la solution

du probl6me P(Jo , Jl ).

Ces trois variantes ne sauraient se justifier math6matiquement; on

peut en imaginer beaucoup d'autres. Nous les avons choisies parce

qu'elles exigent peu de calcul et sont faciles/~ mettre en oeuvre.

Dakin [6] propose un choix de j* plus 6labor6; il consiste ~ prendre

l'indice j tel que le pivotage dual pour faire sortir yj ou z! de la base

initiale (base optimale de P (Jo, J1 )) provoque la plus grande augmenta-

t ion de la fonction ~conomique. Mais, /~ supposer m~me que ce choix

soit tr~s efficace, il n'en paraft pas moins irr6alisable en pratique dans

les probl+mes de grandes dimensions, car il implique le calcul d 'un pivot

dual darts chaque ligne du tableau simplexe.

3. Autres utilisations de 1~ m6thode

La m6thode qu'on vient de d~crire, peut servir, non seulement

d~terminer la solution optimale du probl~me, mais encore:

-- une solution quasi-optimale, approchant l 'opt imum vrai fi moins

de e, seuil de pr6cision donn6 au d~part,

91

- les k meilleures solutions.

De plus, on peut utiliser la m6thode m6me dans le cas off, du fait

des limitations de m6moires sur le calculateur utilis6, on est oblig6 de t ronquer la partition, c'est-~-dire en "oubl ie r" une partie.

3.1. Calcul d'une solution quasi-optimale

Etant donn6 e, diff6rence maximale tol6r6e entre la valeur de la solution de ~-~ et ceUe de la solution cherch6e, il suffit d'arr6ter la pro- c6dure S.E.P. quand, dans la parti t ion E, on connai t un 616ment dont

l '6valuation est exacte et diff6re de moins de e de celle de l'616ment

d'6valuation minimale dans E.

3.2. Calcul des k meilleures solutions

Supposons qu 'on vient d 'at teindre la solution optimale (2, 3)) de E, en met tant sa pr6sence en 6vidence dans E (Jo, Jt ).

Pour obtenir la deuxi6me solut ion optimale de E, on op~re ainsi:

1/ On retranche de E(Jo, J~ ) la solution optimale en ajoutant une contrainte lin6aire qui 61imine le point de coordonn6s ~ dans l 'espace des y.

2/ On calcule la nouvelle 6valuation de E (Jo, Jt ).

3/ On continue la proc6dure g6n6rale jusqu'~ l 'obtent ion de la

solution optimale suivante:

I1 suffit de recommencer ainsi k lois de suite pour obtenir les k meil-

leures solutions de E.

3.3. Cas off le nombre de m6moires est limit6

Dans ce cas, le nombre d'616ment de E qu 'on peut retenir en m6-

moire est born6.A chaque fois qu 'on a at teint la saturation, pour ajouter

un nouvel 616ment E(Jo, Jl), il faut 61iminer un autre 616ment, celui

qui a la plus grande 6valuation. Ce faisant, la proc6dure de r6solution

peut rester rigoureuse et on salt quand elle l 'est; en effet:

- La proc6dure est encore licite, i une certaine 6tape, si l'616ment

92

de plus petite 6valuation en m6moire a une 6valuation inf~rieure ~ celles

des 616ments qu'on a 61imin6s jusque 1~.

II - EXPERIMENTATION

1. Aper~u G6n6ral

L'exp6rimentation de la m6thode ci-dessus a 6t6 faite au d6but de l'ann6e 1966 sur un calculateur Control Data 3600. Les programmes ont

6t6 6crits en Fortran IV (*). Les probl6mes trait6s se classent en deux

cat6gories:

- des probl+mes sans signification concr+te, obtenus en remplissant

le tableau matriciel avec des nombres pris au hasard.

- des probl~mes 6conomiques r6els de gestion et d'investissement,

fournis par diff6rents bureaux de calcul 6conomique.

2. R6sultats

Les principaux r6sultats sont repr6sent6s sur le tableau (figure 1). En face de chaque probl+me on a mentionn6 successivement dans les diff6rentes colonnes:

a) le nombre de variables continues le nombre de variables enti6res 0-1

le hombre de lignes du probl+me.

b) les nombres de sous-ensemble E(Jo, J1) 6tudi6s avant d'attein- dre la solution optimale par les variantes successives I, II et III.

c) le meiUeur temps de calcul obtenu au cours des diff6rents essais.

Remarquons que ce temps de calcul n'est pas tr+s significatif, et cela pour plusieurs raisons:

(*) Ces programmes ont dtd dcrits sous la direction de Mile M. Bonnot, de la Soci~td de Gestion Shell.

93

- les programmes sont 6crits en langage 6volu6, ce qui ne serait pas le cas pour des programmes op6rationnels,

- pour des raisons d ' encombrement des m6moires, on n'a pas pu, sauf darts quelques cas, enchafner les probl6mes p (Jo, J l ) ainsi

qu'il est propos6 au w 2.5. de la 1 6re partie.

3. Description succinte des probl6mes trait6s

- les probl6mes 1 et 2, qui ne diff6rent entre eux que par les va- leurs des coefficients de la fonction 6conomique, se rapportent fi un pro- bl6me d'investissements 6chelonn6s sur trois p6riodes de temps, avec le choix entre six possibilit6s mutueUement exclusives fi chaque p6riode.

- le probl6me 3 concerne un mod61e d'investissements 6chelonn6s

sur plusieurs ann6es dans une usine chimique. Chaque ann6e, on a la possibilit6, pour augmenter la capacit6 de production, de construire des

installations nouvelles ou d 'embaucher , temporairement , du personnel

suppl6mentaire.

- les probl6mes 4 et 5 concernent des probl+mes d'investissements d'instaUations nouvelles, au cours de plusieurs ann6es, dans plusieurs centres emplisseurs de bouteilles de gaz domest ique,qui approvisionnent les d6positaires d 'une m6me r6gion 6conomique. Chaque ann6e, dans

chaque centre, on a l e choix entre divers dispositifs techniques nouveux

pour augmenter la capacit6 de remplissage.

- les probl6mes 6, 7 et 8 qui appart iennent ~ un type tr~s diff& rent, ont 6t6 fournis par le Laboratoire d 'Economie Rurale de Grignon. I1 s'agit de modules de gestion d 'exploitat ions agricoles. Les variables

continues repr6sentent les quantit6s de biens produits (b16, avoine etc...) ou achet6s (engrais, semence etc...). Les variables enti6res repr~sentent

des grandeurs mat6rielles, discr6tes par nature: nombre d'employ6s, de tracteurs, de machines,... Pour r6soudre ces probl6mes, on a exprim6 chacune de ces variables enti6res fi l 'aide de variables 0 - 1, selon le

principe de d6composition:

y = yt + 2Y2 + . . . + 2 p'~ yp

94

- les probl6mes 9, 10 et 11 n 'ont aucune signification 6conomique notre connaissance.

- les probl~mes 12 et 13 concernent un module d' implantation, de d6p6ts de carburants dans une m~me r6gion g6ographique. Pour

chaque d6p6t on a l e choix entre diverses capacit6s de stockage possibles et le probl~me de transport d 6 p 6 t - client est d 'un type particulier: un client ne peut 6tre ravitaill6 que par un seul d6p6t. Ceci explique que

toutes les variables du module sont enti~res bivalentes.

4. Commentaires sur les r6sultats ob tenus

On n'a pas mentionn6 ici les r6sultats obtenus avec des probl~mes

sans signification concr+te, tels que ceux propos6s dans [5]; ils sont

franchement mauvais et dans la plupart des cas on a dO renoncer/ t pour-

suivre le calcul jusqu'~ son ach+vement. Mais c'est sans grande impor- tance, ~ notre avis, car en math6matiques appliqu6es, un algorithme n'a pas de valeur en soi dans l 'abstrait: il n 'en a que par rapport aux pro-

bl6mes r6els pour lesquels on peut l'utiliser.

Par contre, pour tous les probl6mes 6conomiques trait6s, on a obte- nu la solution, alors que la plupart d 'entre eux n'avaient pu 6tre r6solus

ant6rieurement par des m6thodes arithm6tiques, telles que celles de Gomory.

4.1. Arborescence explor6e

La relation d'inclusion conf~re h la famille des sous-ensemble E(Jo, Jl) 6tudi6s au cours d 'un calcul de r6solution, une structure d 'arborescence dont la racine est l 'ensemble E initial. Sur les figures 2

et 3, on a repr6sent6 deux exemples d 'arborescences ainsi obtenues.

Dans le tableau (figure 1), on peut constater qu'i l n 'y a pas de relation apparente entre le nombre de sous-ensembles E (Jo, Jl) (c'est-h-dire de sommets de l 'arborescence) explor6s au cours d 'un calcul et le nombre de variables enti~res du probl6me; le nombre de sommets d6pend beau- coup du caract~re plus ou moins contraignant des relations entre les

variables enti~res. (On reviendra sur ce point dans la troisi~me partie). C'est la raison pour laquelle la solution est relativement plus ri te atteinte

95

dans des probl6mes tels que 4 et 5, off les variables enti~res sont li6es entre elles par des relations "logiques" tr+s strictes, que dans des probl+- rues tels que 6, 7 et 8 off les variables enti6res repr~sentent des grandeurs physiques reli~es entre elles par des relations quantitatives.

C'est la variante II qui, sans ~tre toujours la meilleure, semble donner des performances les plus r6guli~res. Or, des trois variantes pro- pos6es, c'est celle qui correspond fi l'id~e sous-jacente la moins 6labor,e; ce fair tend ~i prouver que seuls des t~itonnements exp6rimentaux peu- vent guider vers une bonne m6thode de choix de l'indice ]* de s6para- tion, sauf peut ~tre dans certains probl~mes de type particulier (probl~- rues de transport avec coflts fixes par exemple).

4.2. Qualit~s de la r6solution des programmes lin6aires P(Jo, J, )

Pour des raisons pratiques li4es ~i des difficult6s de programmation et de m6morisation sur le calculateur, on a dfl essayer divers modes de r6solution des programmes lin~aires P (Jo, J1): algorithme primal et algorithme dual du simplexe, ainsi que diverses faqons d'initialiser chacun de ces calculs; on a notamment essay6 les bases de d6part suivantes:

F i g u r e 1 T a b l e a u d e s r ~ s u l t a t s

N o m b r e N o m b r e n ~ du p r o b l ~ m e de v a r i a b l e s de v a r i a b l e s

c o n t i n u e s e n t i ~ r e s 0-1

I 42 18

2 . ,i

3 21 18

4 55 40

5 63 21

6 19 25

7 20 23

8 66 28

9 7 12

10 0 32

11 0 40

12 0 53

13 0 136

N o m b r e d e l i g n e s

59

34

70

57

28

36

140

13

13

9

17

42

N o m b r e de s o u s - e n s e m b l e s c a l c u l u s p a r la v a r i a n t e

I II III

39 21 25

71 25 31

7 27 27

29

17

149 25 65

45 > 500

31

3

197

301 61 211

11 9 9

39

T e m p s le m e i l l e u r

o b t e n u

2 ' 3 8 "

2 ,47 ' '

56"

5 ,48 ' '

2'36"

3,16"

1 1 ' 2 5 "

26 '

4 I,

6'

2'

1'

17'

96

- base de d6part propos6e au w 2.5. de la premi6re partie - base de l 'opt imum du probl6me P (~ , r

- derni6re base rencontr6e au cours du calcul pr6c6dent.

Les r6sultats sont tr+s significatifs: le mode d 'enchafnement et de r6solution propos6 dans la premi6re partie est de tr~s loin le meiUeur. C'est-~-dire que, sur les exemples num6riques exp6riment6s, chaque probl6me p (Jo, J~ ) ne n6cessite, avec cette m6thode, qu 'un nombre de

pivotages tr6s faibles: de 1 ~ 5 en moyenne.

Mais la difficult6 principale qu 'on rencontre pour la mise en oeuvre de cette m6thode tient dans le fait que les 616ments qui caract6risent

chaque sous-ensemble E(Jo, J~ ) prennent une grande place en m6moire; ils comprennent en effet:

- l '6valuation v (Jo, J~ ) - les listes des indices qui d6finissent J0 et J~

- la liste des indices qui d6finit la base optimale de P (Jo, J1 ).

4.3. Solution quasi-optimale

Dans la plupart des calculs effectu6s, on constate q~a'on a rencon-

tr6 des sous-ensembles E (Jo, J1 ) d'6valuation exacte longtemps avant la

fin du calcul, et le plus souvent, au momen t de cet te rencontre, on ~tait en mesure d'affirmer que cette solution diff6rait peu de la solution opti- male cherch6e; la diff6rence relative ~tait de 5 % ou moins en g6n~ral,

ce qui, compte tenu de l'impr~cision des donn6es d 'un probl~me 6cono-

mique, constitue une bonne approximation. Ceci incline ~ penser qu'il

est souvent net tement moins couteux de chercher h obtenir une solution quasi-optimale acceptable que la solution optimale elle-m6me.

97

F

E

.i

~ o ~ ~ -~

o -~ ~ ~

0

.

o: .o . ~

. . . . . . ~ ~o~ �9 o~ o ~

~ ~ - ~ ~-~ ~ o

F-1---F

~1~ L~. ~1 ~ ~.~

F

0

i

g 8

20

19

21

20

19

21

11

Vq

11

10

i

Fq

10

12

17

m 17

I l l - C O N C L U S I O N

Pour que la m 6 t h o d e q u ' o n vient d ' e x a m i n e r pr6sen te un int6r6t

r6el en r eche rche o p 6 r a t i o n n e l l e , elle d o i t sa t i s fa i re un ce r t a in n o m b r e

de c o n d i t i o n s :

- p e r m e t t r e de r6soudre des p r o b l + m e s de g randes d imens ions .

99

- ne pas conduire A des calculs sur machine trop cofateux.

- 6tre, enfin, un outil efficace pour l'analyse post-optimale du r6sultat, c'est-fi-dire l'analyse des qualit6s pratiques que doit poss6der la solution obtenue pour qu'on puisse la consid6rer comme r6aliste et acceptable.

N'6tant pas en mesure de tirer des conclusions d6finitives sur ces trois points, ~ d6faut d'une exp6rience suffisante, nous en examinerons cependant quelques aspects.

1. R6solution des probl6mes de grandes dimensions

L'6criture d'un programme machine fond6 sur la m6thode ci-dessus se heurte h deux types de difficult6s:

1 [ Les difficult6s li6es ~ l'6criture de tout code de programmation lin6aire classique. Les progr6s techniques r6alis6s sur les r6cents mod61es de calculateurs permettend d'envisager la possibilit6 d'6crire des codes plus puissants que ceux utilis6s ~ l'heure actuelle. Remarquons cepen- dant que le choix du pivot dual n'a pratiquement pas 6t6 utilis6 jusqu'h pr6sent, car il est beaucoup plus on6reux que le choix du pivot primal, et son utilit6, en programmation lin6aire classique, ne s'est jamais impo- s6e. Pour les programmes mixtes, ~l la lueur de notre exp6rience, il parait indispensable de l'utiliser.

2/ Les difficult6s qu'entrafne la n6cessit6 de g6rer au mieux ren- semble des sommets pendants de l'arborescence de S.E.P., c'est-~-dire des ensembles E (Jo , J l ).

Etant donn6 le nombre de m6moires 616mentaires n6cessaires pour conserver tout ce qui d6ffmit un sommet, il n'est pas pensable d'utiliser pour cela les m6moires ~ ferrite de l'unit6 centrale du calculateur; il faut avoir recours aux supports d'information p6riph6riques, et tout d6pend alors de la nature de ces derniers. Jusqu'h une 6poque tr6s r6cente, on ne disposait que des bandes magn6tiques, dont on sait les graves incon- v6nients.

- temps d'acc6s tr6s long

1 0 0

- impossibilit6 de modifier partiellement un enregistrement.

Divers auteurs, comme Beale et Small [2], ou Dakin [6], on propo-

s~ des palliatifs fi ces inconv6nients, palliatifs qui sont des ent~,rses fi

la m6thode initiale et r6duisent, de ce fait, son efficacit6. Les tambours

magn6tiques n'ont plus ces inconv~nients e grfice ~ eux, la raise en oeuvre de S.E.P. pourra probablement se faire ans difficult6s majeures.

I1 est, d'autre part, certain que, quand les probl6mes P (Jo, J1) poss~dent une structure particuli6re, (probl~mes de transports, etc...)

on a int~r~t ~ utiliser cette particularit6 pour les r~soudre, ainsi que le

proposent par exemple Descamps [7] ou Efroymson [9]. De m~me,

certains programmes lin6aires en variables enti6res pures bivalentes qui

ont pour origine des probl6mes combinatoires (voir [1]) et dont le

tableau matriciel ne contient que des 0 ou des 1 peuvent donner lieu,

dans le cadre de S.E.P., fi des m6thodes de rdsolution sp6cifiques.

2. Mod61isation des programmes lin6aires mixtes

Revenons au cas gen6ral des probl~mes de forme quelconqu~ Dans

la plupart de ces probl6mes, les variables enti6res s ' introduisent pour

repr6senter des alternatives; ce sont des variables "logiques". Elles sont

reli6es entre elles par un certain nombre de relations logiques (exclusi6n

mutuelle, implication, etc.) et on traduit chacune de ces relations, darts

le module, par un ensemble de contraintes lin~aires qui ont pour effet

de retrancher du domaine des solutions admissibles les valeurs du vec-

teur y qui ne satisfont pas la relation. Formellement, cela peut se faire d'une infinit6 de facons, mais en pratique, il faut 6crire ces contraintes

de telle sorte que chaque 6valuation par d6faut v(Jo, J l ) , obtenue en r6solvant un programme lin6aire P (Jo, J~), soit la meilleure possible, c'est-~i-dire, aussi proche que l'on peut de la valeur de la meilleure

solution de E contenue dans E(Jo , Jl ).

Consid6rons, dans l'espace ~ n dimensions des variables enti~res

)'~ , Y 2 . . . , Yn, l 'hypercube dont les sommets sont les points ~ coor-

donn6es 0 ou 1. Les contraintes lin6aires consti tuent des troncatures de

cet hypercube, qu'il faut choisir de faqon qu'elles le t ronquent le plus

possible.

101

Par exemple, pour exprimer que les choix A e t B sont mutuelle- ment exclusifs, on pourrait 6crire, en leur associant les variables,

valeurs 0 ou 1, YA et YB:

0 , 1 < Y A + YB<I , 9

ce qui suffit fi traduire formellement la relation logique. Mais de route

6vidence, la forme:

Y A + Y B = I ,

qui est 6quivalente, est de beaucoup pr6f6rable pour la r6solution du

probl6me.

Pour la m6me raison, il ne faut pas craindre, quand on la connaft, d'exprimer par une relation logique une propri6t6 qualitative qu'on sait 6tre contenue implicitement dans les 6quations quantitatives du module. Supposons par exemple, que, compte tenu du capital disponible, on voit qu'on ne peut pas faire simultan6ment plus de deux des trois investis- sements A, B e t C; on a alors int6r6t ~ ajouter darts le mod61e la con-

trainte redondante:

Y4 + YB + Yc < 2

I1 serait done int~ressant de d6velopper des r6gles de traduction des expressions de la logique formelle fi l'aide de contraintes lin6aires

satisfaisant aux conditions 6nonc~es dans ce paragraphe.

3. Analyse post-optimale de la solution

En programmation lin6aire classique les proc~d6s d'analyse du voi-

sinage d'une solution sont d6sormais bien 61abor6s; ils consistent en une 6tude param6trique des diff6rentes composantes de la solution en fonc- tion des variations que peuvent subir quelques donn~es importantes du mod61e. En programmation lin6aire mixte, le probl~me est tout autre et,

notre connaissance, il a ~t6 peu abord~ jusqu'h maintenant; en effet, une solution comportant certaines coordonn6es enti+res, la notion de voisinage entre solution n'a plus de signification a priori.

102

Du point de vue 6conomique, dans la plupart des problrmes, les composantes x et y d 'une solution ont la signification suivante:

1/ x, ensemble des variables continues, drfinit le niveau optimal des diffrrentes grandeurs qui const i tuent l'activit6 ~conomique darts le

syst+me qu 'on a modrlisr.

2/ y, ensemble des variables bivalentes, caractrrise la structure qualitative optimale qu'il faut donner ~ ce syst~me.

Pour qu'une solution (Yc, p), optimale ou quasi-optimale soit ac- ceptable, elle doit possrder certaines quali trs de stabilit6 et de souplesse, compte tenu des lacunes et des imprrcisions du modrle par rapport ~ la r~alitr. On peut suggrrer deux phases dans l ' r tude de la solution.

1/ Etude de Yc

y 6tant f ixr ,on peut faire varier ~ en fonct ion de certaines donnres importantes du modrle afin de dr terminer si, darts tous les cas, il existe encore une solution et si sa valeur est toujours acceptable. Cette analyse, en tous points semblable fi une ~tude paramrtr ique en programmation

lin~aire, peut conduire ~t rejeter la solution (~, p) e t a continuer l'algo- rithme grnrral pour en d~terminer une autre.

2/Etude de p

I1 peut arriver que certaines composantes du vecteur y symbolisent des choix (investissements industriels, implantations de d~prts, etc...)

sur qui, pour des motifs varirs (sociaux, politiques, etc...) qu'il est im-

possible de reprrsenter dans le module, p~sent des incertitudes quant ~i leur possibilit6 de rralisation effective.

On ne peut alors se contenter d ' r tudier la seule solution (.~, p); il faut encore examiner ses solutions de repli possibles. Ceci revient fi drfi- nir d 'abord un voisinage de p, c'est-~-dire une famille de vecteurs y qu 'on estime concr~tement proches de .9, et ~ explorer ensuite cette

famille. Si cette famille est form~e de un ou plusieurs sous-ensembles de E du type E(Jo, J~ ) cela consistera ~ continuer la procrdure g~nrrale de rrsolution en la restreignant fi ce ou ces sous-ensembles. Si les solutions de repli sont inacceptables, il faudra alors rejeter la solution (~ , p) elle- m~me et en rechercher une autre.

103

Ces suggest ions sen t 6 v i d e m m e n t i n c o m p l 6 t e s et impar fa i t e s ; en

fai t , il f aud ra i t a d o p t e r un m o d e d ' a n a l y s e p o s t - o p t i m a l e p o u r chaque

p r o b l 6 m e part icul ier . Nous avons s e u l e m e n t vou lu m o n t r e r q u ' o n peu t

a v a n t a g e u s e m e n t uti l iser l ' i n f o r m a t i o n a c c u m u l 6 e p e n d a n t la phase de

r6so lu t ion d ' u n p rob l6me p o u r l ' ana lyse p o s t - o p t i m a l e de la so lu t ion

ob t enue . Ceci n ' e s t c e r t a i n e m e n t pas un des m o i n d r e s avan tages des

p roc6dures du t ype S.E.P.

BIBLIOGRAPHIE

1. BALINSKI M.L. - "Integer Programming: Methods, Uses, Computation" - Ma- nagement Science, Vol. 12, n ~ 3, Novembre 1965.

2. BEALE E.M.L. and SMALL R.E. - "A Branch and Bound Method for Mixed Integer Programming" - Proceedings of the Third IFIP Conference, Vol. 2, 1965.

3. BENDERS J.F. - "Partitionning Procedures for Solving Mixed Variables Pro- gramming Problemes" - Numerische Mathematik, Vol. 4, 1962.

4. BERTIER P. et ROY B. - "'Une proc6dure de r6solution pour une classe de probl6mes pouvant avoir un earact6re eombinatoire". Bulletin du Centre In- ternational de Calcul, Rome - 1965.

5. BOUVIER B. et MESSOUMIAN G. - "Programmes lindaires en variables biva- lentes, Algorithme de Balas'" - Projet de f'm d'6tudes, Facult6 des sciences de Grenoble - 1965.

6. DAKIN J.R. - "A tree-search algorithm for mixed integer programming pro- blems". The computer Journal, Vol. 8, n ~ 3 - Octobre 1965.

7. DESCAMPS R. - "Un algorithme d'optimisation pour une classe de probl6mes d'implantation" - Communication ~ la Conf6rence de rI.F.O.R.S. - Boston, 1966.

8. DRIEBECK NJ . - "An algorithm for the solution of mixed integer pro- gramming problems"-Arthur D. Little Inc., Cambridge, Massachussets.

9. EFROYMSON M.A. and RAY T.L. - "A branch and Bound algorithm for plant location" Esso Research and Engineering company.

10. GLOVER F. - "Truncated Enumeration Methods for Solving Pure and Mixed Integer Linear Programs"- Working paper, University of California at Berkeley.

11. HEALY W.C. - "A multiple choice programming" - Operations Research, Vol. 12, 1964.

104

12. L A N D A.H. and DOIG A.G. - " A n a u t o m a t i c m e t h o d for solving d iscre te

p r o g r a m m i n g p r o b l e m s " - E c o n o m e t r i c a , 28 - 1960.

13. L E M K E C.E. and S P I E L B E R G K. - " 'Direct search zero - one and m i x e d

in teger p r o g r a m m i n g " - IBM Resea rch R e p o r t n ~ 39 006 , Ju in 1966.

14. ROY B., B E R T I E R P. et N G H I E M P.T. - " P r o g r a m m e s l in6aires en n o m b r e s

en t ie r s et proc6dure S.E.P." - Metra , Vol . IV, n ~ 3. 1965.

105