6.

1 Introduction

Dans le problème général de la programmation linéaire, toutes les inconnues peuvent

varier de façon continue. Si, en revanche, on impose à toutes les variables du problème
d'avoir des valeurs entières à l'optimum, on se trouve devant un problème de
programmation linéaire à variables «entières» ou en «nombres entiers» pur. Si une partie
seulement des variables est soumise à cette contrainte supplémentaire d'intégralité, il s'agit
alors d'un problème de programmation linéaire en variables «mixtes».

Le problème général se formule donc:

Min ctx
Sujet à Ax = b programme continu associé. (6.1.1)
x≥0
xj entier j J,

où c, xn, bm, A Mmxn.

 CHAPITRE VII

La programmation linéaire en variables entières est très importante, car la plupart des
problèmes réels comportent des variables qui doivent, par nature, prendre nécessairement
une valeur entière. Si, par exemple, on recherche le nombre de personnes qui doivent
travailler sur une certaine tâche à un instant donné, il importe peu que la solution optimale
du problème en variables continues indique que 342.35 personnes sont nécessaires, car la
partie fractionnaire est négligeable par rapport à la partie entière. Par contre, si une
variable représente l'existence ou l'absence d'une usine, ou un nombre faible de navires
destinés au transport de certaines marchandises, la solution d'un problème de
programmation linéaire qui donnerait 0,44 usine ou 3,55 navires n'est pas satisfaisante; si
on essaie alors d'arrondir à une valeur entière voisine, il se peut que la solution ainsi
trouvée soit éloignée de la solution optimale, ou même ne soit pas réalisable. Dans de
telles situations, il est donc souhaitable de pouvoir utiliser une méthode plus raffinée que la
méthode du simplexe.

Exemple 6.1.1

Considérons le problème de programmation linéaire en nombres entiers suivant:

Min -10x1 -11x2

Sujet à 10x1 +12x2 ≤ 59
x1≥ 0, x2 ≥ 0
x1 et x2 entiers.

L'optimum est (1,4) alors que la solution du problème continu associé est (5.9,0).
Remarquez la nette différence entre les 2 solutions :


Cette première idée pour résoudre le problème (6.1.1), qui consiste à résoudre le problème
continu associé et d'arrondir la solution, n'est pas exploitable. La solution arrondie n'est
pas toujours réalisable; si elle l'est, elle peut se trouver très loin de l'optimum.

Une deuxième idée consiste à prendre la solution entière réalisable qui se trouve le plus
près possible de l'optimum continu. Or, on peut construire des exemples où la solution
optimale entière se trouve aussi loin que l'on veut de la solution entière la plus proche de
l'optimum continu, autant en distance que pour la valeur de la fonction objective.
PROGRAMMATION LINÉAIRE EN NOMBRES ENTIERS (PLE) 3

Théoriquement, tout problème de programmation linéaire en nombres entiers peut être

résolu. Par exemple, comme il n'y a qu'un nombre fini de solutions entières, il suffit de
toutes les énumérer et de choisir la meilleure. Toutefois, en pratique, il y a souvent plus
de solutions entières réalisables que d'atomes dans l'univers (1000 variables binaires
21000 solutions possibles).

En fait, il n'existe aucun algorithme universel efficace. La performance de chaque

technique dépend de la structure du problème à traiter et de notre capacité à adapter cette
technique à cette structure particulière.

En fait, il existe de nombreux algorithmes qui conduisent à la solution optimale par une
suite finie de calculs. Cependant, les facteurs qui peuvent limiter l'utilisation de
l'algorithme du simplexe dans la résolution d'un problème de programmation linéaire
jouent de façon beaucoup plus nette encore dans le cas de la programmation linéaire en
nombres entiers. Bien que l'on soit assuré de trouver l'optimum en un nombre fini
d'opérations, la résolution peut se révéler extrêmement longue, même sur les ordinateurs
les plus puissants. Par ailleurs, les erreurs d'arrondi et la taille du calculateur peuvent
gêner ou même, rendre impossible un déroulement acceptable des calculs. Contrairement
à la programmation linéaire où le nombre de contraintes joue un rôle important en terme
d'efficacité, la programmation linéaire en nombres entiers est influencée davantage par le
nombre de variables et, plus spécifiquement, par le nombre de variables entières. Il arrive
même dans certains cas qu'une augmentation du nombre de contraintes entraîne une
diminution des temps de calcul; ceci s'expliquerait par une réduction du nombre de
solutions réalisables.

Par contraste avec l'algorithme du simplexe en programmation linéaire, il y a une grande

variété d'algorithmes généraux pour la programmation linéaire en nombres entiers, et ils
offrent des possibilités très inégales.

6.2 Situations générales donnant lieu à des modèles de programmation linéaire en

nombres entiers

La programmation linéaire en nombres entiers ouvre la voie à une solution de nombreux

problèmes qui se trouvaient jusqu'alors exclus du champ d'application de la programmation
 CHAPITRE VII

linéaire ordinaire et pour lesquels, en général, on ne connaissait aucune méthode de

solution. Nous donnons ci-dessous quelques types importants de tels problèmes.

La programmation linéaire en variables entières permet, par l'emploi des variables

booléennes (variables qui ne peuvent prendre que les valeurs 0 ou 1), l'introduction de
relations logiques dans un modèle.

Parmi les contraintes logiques, nous avons d'abord les contraintes avec interrupteur.
Considérons une contrainte quelconque f(x1, x2, ..., xn) ≤ b laquelle doit être satisfaite dans
certains cas, mais pas toujours. Soit

y= 0 si la contrainte doit être satisfaite

1 sinon.

B: une très grande constante, certainement supérieure à f.

Alors, on écrira: f(x1, x2, ..., xn) ≤ b + By.

Considérons maintenant les contraintes alternatives. Soit l'alternative

f1(x1, x2, ..., xn) ≤ b1 et/ou f2(x1, x2, ..., xn) ≤ b2

laquelle peut être modélisée par:

f1(x1, x2, ..., xn) ≤ b1+ B1y1; f2(x1, x2, ..., xn) ≤ b2+ B2y2

y1 + y2 ≤ 1; y1, y2 {0, 1}.

Ceci peut être généralisé au cas où il y a au moins K contraintes parmi p contraintes qui
doivent être satisfaites:

fi(x1, x2, ..., xn) ≤ bi+ Biyi, i = 1, 2, ..., p

y1 + y2 + ... + yp ≤ p - K

yi {0, 1}, i = 1, 2, ..., p.

PROGRAMMATION LINÉAIRE EN NOMBRES ENTIERS (PLE) 5

yi = 0 lorsque la contrainte i est satisfaite,

1 sinon.

Envisageons maintenant une relation d'implication. Soit la relation

f1(x1, x2, ..., xn) > b1  f2(x1, x2, ..., xn) ≤ b2,

on peut voir facilement que cela est équivalent aux contraintes alternatives:

f1(x1, x2, ..., xn) ≤ b1 et/ou f2(x1, x2, ..., xn) ≤ b2.

De manière plus générale, étudions les contraintes mutuellement exclusives. Supposons

que les variables d'un problème de programmation linéaire soient soumises à une
contrainte de la forme:

f1(x1, x2, ..., xn) ≤ b1 ou f2(x1, x2, ..., xn) ≤ b2 ou ... ou fp(x1, x2, ..., xn) ≤ bp.

Ce système est équivalent à:

fi(x1, x2, ..., xn) ≤ bi + Biyi, i = 1, 2, ..., p

p
 yi = p - 1
i=1

yi{0, 1}, i = 1, 2, ..., p.

yi : 0 lorsque la contrainte i est satisfaite,

1 sinon.

Ceci peut facilement être généralisé à des ensembles mutuellement exclusifs de

contraintes. Dans ce cas, fi et bi sont vectoriels.

Exemple 6.2.1

Supposons que n variables xj soient astreintes à prendre chacune l'une des k j valeurs aji
(i = 1, 2, ..., kj) données à l'avance.
 CHAPITRE VII

Une approche possible est:

kj
xj =  ji aji, j = 1, 2, ..., n
i=1

kj
 ji = 1 j = 1, 2, ..., n
i=1

0 ≤ ji ≤ 1, entier, j = 1, 2, ..., kj;

j = 1, 2, ..., n.

Exemple 6.2.2 - Maximum ou minimum de deux ou plusieurs variables

Supposons que l'on veuille exprimer par une variable x la plus grande des deux variables
x1 et x2:

si x1 ≥ x2 alors x = x1

sinon x = x2.

On posera:
x ≥ x1 , x ≥ x 2

x ≤ x1 + B(1- )

x ≤ x2 + B  où B est un nombre arbitrairement grand,

 {0, 1}.
Si  = 1, on a x2 ≤ x = x1. Si  = 0, on a x1 ≤ x = x2.

Si l'on veut que x soit la plus petite de n variables xj, on écrira:

x ≤ xj, j = 1, 2, ..., n

x ≥ xj - B(1 - j), j = 1, 2, ...,n

PROGRAMMATION LINÉAIRE EN NOMBRES ENTIERS (PLE) 7

n
j = 1
j=1

j {0, 1}.


Exemple 6.2.3 - Décomposition de variables entières en variables booléennes.

Bien que, dans un grand nombre de problèmes de PLE, les variables «entières» ne puissent
prendre que les valeurs 0 ou 1, il en existe aussi où les variables «entières» peuvent
prendre d'autres valeurs non négatives (entre 0 et 15 par exemple). La plage de variation
de ces variables n'est généralement pas très grande, car traiter comme «entière» une
variable qui peut prendre des valeurs très élevées n'apporte généralement aucune précision
supplémentaire. Or, d'une part certains algorithmes ne sont applicables qu'aux problèmes
de PLE où les variables sont booléennes, d'autre part les algorithmes utilisables pour
n'importe quel type de variables «entières» sont souvent plus efficaces si les variables ne
sont que booléennes. Il peut donc être intéressant de savoir transformer des variables
«entières» quelconques en variables booléennes. On peut supposer que toute variable
«entière» non négative a une borne supérieure N (0 ≤ x ≤ N).

Soit p l'entier positif tel que 2p-1 ≤ N < 2p. On sait qu'on peut toujours écrire un nombre
entier sous forme d'une somme de puissances de 2:
p
x =  2p-i i.
(6.2.1)
i=1

La variable x est alors remplacée par p variables booléennes i. On obtient une solution
entière en x lorsque les p variables i prennent simultanément l'une des valeurs 0 ou 1.

En réalité l'équation (6.2.1) définit une variable x qui peut prendre une valeur entière entre
0 et 2p - 1, c'est-à-dire bien supérieure, peut-être, à la borne supérieure N de x. Certaines
combinaisons de i égales à 1 peuvent donc généralement être exclues.

Si N = 2p - 1, toutes les combinaisons sont possibles.

 CHAPITRE VII

Si N = 2p - 1, on a une contrainte d'implication:

1 = 1 i = 0 2 ≤ i ≤ p,

ce qui peut d'ailleurs s'écrire

1 + i ≤ 1 2 ≤ i ≤ p.

Si 2p-1 < N < 2p -1, il peut aussi exister des contraintes d'implication. En effet, définissons
N' par:

N' = N - 2p-1 > 0,

d'où N' < 2p-1, puisque N < 2p. Soit q l'entier positif tel que:

2q-1 ≤ N' < 2q;

l'indice q est bien défini par la condition ci-dessus et on a nécessairement q ≤ p - 1.

Appelons I l'ensemble des indices i tels que q ≤ p - i, c'est-à-dire i ≤ p - q (noter que
1 I).

N' < 2p-i pour tout i ≤ p - q,

soit N < 2p-i + 2p-1 pour tout i ≤ p - q.

En comparant cette expression de la borne supérieure de x avec (6.2.1), on a (sauf lorsque

q = p - 1) les contraintes d'implication:

1 = 1 i = 0 2 ≤ i ≤ p - q, (6.2.2)

ce qui peut aussi s'écrire:

1 + i ≤ 1 2 ≤ i ≤ p - q.

Trois cas peuvent se produire:

a) N' = 2q -1: le recensement des implications est terminé.

b) N' = 2q -1 = 2p-(p-q+1),
PROGRAMMATION LINÉAIRE EN NOMBRES ENTIERS (PLE) 9

d'où N = 2p -1 + 2p-(p-q+1)

Aux contraintes (6.2.2), il faut alors adjoindre les autres contraintes

1 = 1
 i = 0 p - q + 2 ≤ i ≤ p,
p-q+1 = 1

soit
1 + p-q+1 + i ≤ 2 p - q + 2 ≤ i ≤ p.

c) 2q -1 < N' < 2q -1.

On définit

N" = N' - 2q-1 > 0

et on applique à N" un raisonnement analogue à celui employé ci-dessus pour N'',

déterminant ainsi si la conjonction (1 = 1, p-q +1 = 1) implique l'annulation d'un certain
nombre de variables .

On poursuit ainsi le recensement des implications jusqu'à ce que l'on se trouve dans un cas
tel que a) ou b), qui termine le processus de recensement.

Souvent on n'a qu'une idée imprécise des bornes supérieures des variables «entières». On
est alors conduit en pratique à prendre des bornes suffisamment grandes, ce qui risque
d'amener la génération d'un nombre élevé de variables booléennes.


Nous avons vu que l'introduction de telles contraintes logiques permet même de résoudre
des problèmes dans lesquels l'ensemble des programmes n'est ni convexe, ni connexe.
Nous pouvons aussi résoudre certains types de problème dans lesquels la fonction à
optimiser est non linéaire ou dans lesquels certaines contraintes sont non linéaires.

Un problème dans lequel une variable apparaît sous forme non linéaire dans les
contraintes et, éventuellement, dans la forme à optimiser, peut être ramené à un problème
linéaire, avec une approximation aussi bonne que l'on veut.
 CHAPITRE VII

Considérons une fonction quelconque f(x). On peut toujours approximer f(x) par une
ligne polygonale:

f(x)

Les segments de la ligne polygonale correspondent, pour la variable x, à une suite

d'intervalles [uj, uj+1], j = 1, 2, ..., k. Soit a j + bjx l'équation du segment correspondant à
l'intervalle j, c'est-à-dire une approximation linéaire de f(x) sur cet intervalle. Si les j sont
des variables booléennes dont une seule est égale à 1,

k
f(x) =  j (aj + bj x)
j=1

k k
 j (aj + bj uj) +  b j wj
j=1 j=1
PROGRAMMATION LINÉAIRE EN NOMBRES ENTIERS (PLE) 11

où wj = j (x - uj),

c'est-à-dire,
k k k
j x = x =  wj +   j uj
j=1 j=1 j=1

Quand j = 1, x [uj, uj+1] et wj  [0, uj+1 - uj].

En résumé, on a le système suivant:

k k
f(x) =  j (aj + bj uj) +  b j wj
j=1 j=1

k k
x=  wj +   j uj
j=1 j=1

0 ≤ wj ≤ j (uj+1 - u j), j = 1, 2, ..., k,

k
 j = 1
j=1

j ≥ 0, entier.

Exemple 6.2.4

Le problème consiste à localiser dans une ville des postes de pompiers (ou de police, ou de
bureaux de poste, ou des CLSC, etc.).

La ville est divisée en I zones et il y a J localisations (sites) possibles pour les postes.

Posons

pi  population de la zone i,
 CHAPITRE VII

dij  distance moyenne de la zone i au site j,

yj  1 si le site j est choisi,

0 sinon.

xij  1 si la zone i est assignée au site j,

0 sinon.

J
di   dij xij  distance de la zone i à son site.
j=1

I
sj   pi xij  population desservie par le site j.
i=1

fj(sj)  coût au site j pour servir une population de taille sj

B  budget total.

De plus, les contraintes suivantes doivent être satisfaites: les sites 1 et 2 ou encore les sites
3 et 4 doivent être choisis.

L'objectif consiste à minimiser la distance moyenne maximale entre une zone et son poste
affecté c'est-à-dire, le maximum des di.

Le problème peut alors s'écrire:

Min D

J
Sujet à  dij xij ≤D  i = 1, 2, ..., I
j=1

J
 xij = 1  i = 1, 2, ..., I * un et un seul site par zone*
j=1
PROGRAMMATION LINÉAIRE EN NOMBRES ENTIERS (PLE) 13

I
 xij ≤ I yj  j = 1, 2, ..., J * Le nombre de zones assignées
i=1 au site j est ≤ I en autant que le
site j a été choisi.*
J I
 fj  pi xij ≤B
j=1 i=1

y1 + y2 ≥ 2y
y3 + y4 ≥ 2 - 2y

xij, yj, y {0, 1} pour tout i, j.

Nous avons I J + J + 1 variables binaires.

6.3 Applications de la programmation linéaire en nombres entiers.

Nous avons vu que pour bien des problèmes, la programmation linéaire ne donne, en fait,
que des approximations de la réalité. L'utilisation de la programmation en nombres entiers
pourra, dans de tels cas, être préférable.

Nous allons présenter quelques types de problèmes que l'on rencontre fréquemment.

Problème d'investissement

Soient xj   si on choisit le projet j

0 sinon.

aij  niveau de ressource i nécessaire pour le projet j,

bi  niveau de ressource i disponible,

cj  bénéfice dû à la réalisation du projet j,

 CHAPITRE VII

il s'agit de maximiser le bénéfice total où un projet peut être la construction d'un aéroport,
la localisation d'une usine ou d'un entrepôt à un endroit donné, etc. tandis que b i pourrait
être par exemple le montant d'argent disponible à la période i.

Le problème s'écrit alors:

Max ctx

sujet à A x ≤ b

xj{0, 1} pour tout j.

Variantes :

i) Supposons par exemple que l'on ne peut choisir le projet i que si le projet j est choisi:

xj ≥ xi

ii) Supposons que, parmi les projets j, j+1, ..., j+k, on ne peut en choisir qu'un seul
(exemple: localisation d'une usine):

xj + xj+1 + ... + xj+k ≤ 1.

Problème de localisation d'entrepôts

Il s'agit de placer des centres de distribution pour servir des clients.

Soient n  nombre de localisations possibles,

m  nombre de clients à servir,

fi  coût fixe s'il existe un entrepôt à la localisation i,

cij  coût unitaire (par unité de bien) pour servir le client j à partir
de l'entrepôt i (transport, manutention, etc.)

dj  demande du client j

xij  quantité à envoyer de l'entrepôt i au client j

PROGRAMMATION LINÉAIRE EN NOMBRES ENTIERS (PLE) 15

yi  1 si l'entrepôt i est utilisé

0 sinon

Il s'agit de minimiser le coût total de l'entreprise.

Le problème s'écrit alors:

Min  cij xij +  f i yi

i, j i

Sujet à  xij = dj j
i

 xij - yi  dj ≤ 0 i
j j

xij ≥ 0 i, j

yi = 0 ou 1 i.

Problèmes d'ordonnancement, de routage et d'horaires

Considérons par exemple le problème de la conception des horaires des équipages des
avions d'AIR CANADA.

1 étape  le vol direct d'une ville à une autre,

1 route  une suite d'étapes

(par exemple, Montréal  Toronto  Chicago  Los Angeles avec
attente possible entre les vols).
Soient

xj  1 si la route j est choisie (on lui assigne donc un équipage)

0 sinon

aij  1 si l'étape i fait partie de la route j

0 sinon
 CHAPITRE VII

cj  coût d'affectation d'un équipage à la route j

Le problème consiste à minimiser le coût total d'affectation des équipages tout en

assurant l'ensemble des vols (étapes).

On peut donc écrire:

Min  cj xj
j

Sujet à  aij xj = 1 i
j

xj {0, 1} j.

Le problème précédent est connu sous le nom de problème du partitionnement

d'ensembles. Si on remplace la contrainte

 aij xj = 1 par  aij xj ≥ 1,

j j
on obtient un problème de recouvrement d'ensembles.

Ces problèmes se retrouvent dans plusieurs contextes: divisions des comtés, routes des
camions de livraison, horaires d'autobus, horaires des camions postaux, etc.

Problème du voyageur de commerce

Un voyageur veut visiter les villes 0 à n, en partant de la ville 0 et en revenant à la

ville 0, en passant une et une seule fois dans chaque ville, tout en minimisant ses coûts
de transport ou la distance parcourue.

Soient

cij  coût (ou la distance) de transport de la ville i à la ville j,

xij  1 si le voyageur décide d'emprunter le chemin allant de i à j directement,

0 sinon

On peut donc formuler le problème ainsi:

PROGRAMMATION LINÉAIRE EN NOMBRES ENTIERS (PLE) 17

Min   cij xij (6.3.1)

i j

Sujet à  xij = 1 j
i

 xij = 1 i
j

xij ≥ 0 i, j.

Il faut s'assurer que la solution obtenue est un seul circuit continu de longueur
minimale commençant et se terminant au même sommet et qui passe une et une seule
fois par chacun des sommets.

Il peut arriver que la solution obtenue soit un ensemble de sous-tours disjoints:

1
5

0 3

2
6

Pour éliminer ces possibilités, il faut ajouter des contraintes du type:

  xij ≥ 1.
i j 
 CHAPITRE VII

Problème de stockage

Une usine peut avoir à stocker m produits liquides (qui ne doivent pas être mélangés)
dans n réservoirs.

Soient

ai  quantité du produit liquide i i = 1, 2, ..., m

bj  capacité du réservoir j j = 1, 2, ..., n

xij  1 si le réservoir j est affecté au liquide i,

0 sinon

mij  min {ai, bj}.

Le volume des réservoirs affectés au liquide i doit être au moins égal au volume a i:

n
 mij xij ≥ ai, i = 1, 2, ..., m.
j=1

Puisque les liquides ne peuvent être mélangés, nous avons:

m
 xij ≤ 1, j = 1, 2, ..., n.
i=1

L'objectif peut consister à minimiser le nombre de réservoirs utilisés:

Min  xij .
i, j
PROGRAMMATION LINÉAIRE EN NOMBRES ENTIERS (PLE) 19

Problème d'implantation d'usines avec coûts fixes

Considérons un problème de transport classique:

n
 xij ≤ ai, i = 1, 2, ..., m (disponibilités) (1)
j=1

m
 xij ≥ bj, j = 1, 2, ..., n (demande) (2)
i=1

xij ≥ 0, pour tout i, j (3)

n m
  cijxij = Z(min) (4)
j=1 i=1

où xij est la quantité de bien expédiée depuis l'entrepôt (ou usine) i vers le marché (ou
client) j. On se souvient qu'une interprétation économique est qu'il y a m usines à partir
desquelles on peut expédier au plus ai unités pour l'usine i (1) et que le client j doit en
recevoir au moins bj(2), le coût d'expédition d'une unité de l'usine i au client j étant c ij
pour tout i, j. Il n'est pas nécessaire de placer la contrainte d'intégrité car la matrice A est
totalement unimodulaire.

L'objectif (4) est de trouver un plan routier qui minimise les coûts totaux de transport.

Il arrive assez fréquemment en pratique dans les problèmes de transport, qu'une partie de
ce problème soit de déterminer quelles usines ou quels entrepôts doivent être en opération
pour minimiser le coût total. Cela revient à dire que, parmi m lieux possibles pour y
installer des usines (ou entrepôts), il faut déterminer où placer les usines (au plus m) pour
minimiser le coût total. Mais l'implantation de ces usines nécessite des dépenses fixes qui
doivent être ajoutés aux coûts de transport pour maximiser le profit de la compagnie.

Le dilemme dans lequel nous sommes placés est le suivant:

 CHAPITRE VII

i) réduire les coûts fixes d'opérations en diminuant le nombre d'usines et en augmentant

les coûts de transport

ou

ii) augmenter le nombre d'usines et donc les coûts fixes d'opérations en diminuant les
coûts de transport.

Évidemment, pour maximiser le profit de la compagnie, il faut minimiser le coût total

induit par les coûts fixes et par les coûts de transport. Voyons comment construire ce
modèle à partir du problème de transport indiqué ci-dessus.

Considérons une compagnie qui désire développer son industrie en servant des clients ou
marchés nouveaux dans l'Ouest du pays et le Nord-Ouest des États-Unis. Pour
accommoder cette extension de son marché global, la compagnie prévoit ouvrir de
nouvelles usines. On suppose que le site i représente un lieu potentiel pour l'implantation
d'une nouvelle usine qui aura un coût fixe d'opération Fi ≥ 0 (amortissement, équipement,
taxes foncières, ...) et une capacité maximale de production ai; le coût d'opération étant
indépendant de la production, i = 1, 2, ..., m. Il y a m sites potentiels pour ces usines, mais
les coûts fixes Fi sont tels qu'il est trop onéreux d'ouvrir une usine sur chacun de ces sites.

Soit maintenant, cij ≥ 0 le coût de fabrication et de transport d'une unité de produit

fabriqué à l'usine i et expédiée au marché j. Par exemple, on pourrait avoir c ij = c'i + c'ij
où c'i serait le coût unitaire de fabrication à l'usine i et c' ij le coût de transport d'une unité
de l'usine i au marché j. De plus, on suppose, ce qui est très naturel qu'il y a un coût fixe
Fij ≥ 0, associé au maintien d'une route de livraison de l'usine i au marché j. Ce montant
Fij est indépendant de la valeur de xij si xij > 0, mais il n'est pas encouru lorsque x ij = 0
car alors, il n'est pas utile de maintenir cette route de livraison.

Afin de formuler ce problème sous forme mathématique, il faut introduire les variables de
décision:

yi = 1 si l'usine i est construite, i = 1, 2, ..., m

0 sinon
PROGRAMMATION LINÉAIRE EN NOMBRES ENTIERS (PLE) 21

zij = 1 si une route de livraison va du site i au marché j, i = 1, 2, ..., m

0 sinon j = 1, 2, ..., n

Ainsi, à la place de la fonction objective (4), on prendra comme fonction objective

m m n m n
 Fi yi +   cij xij +   Fij zij = Z(min) (5)
i=1 i=1 j=1 i=1 j=1

Au lieu d'imposer les contraintes (1) de disponibilités, il faut tenir compte du fait que
l'usine est construite, on doit donc imposer la contrainte de capacité

n
 xij - ai yi ≤ 0, i = 1, 2, ..., m (capacité) (6)
j=1

En effet, s'il n'y a pas d'usines sur le site i, yi = 0 et les contraintes (3) et (6) impliquent que
xij = 0 pour tout j, ce qui est naturel. Les contraintes (2) et (3) demeurent évidemment les
mêmes. Pour certains algorithmes de programmation en nombres entiers, il suffit de poser
en addition que yi et zij sont des variables bivalentes 0-1. Mais pour d'autres, ces
restrictions doivent être exprimées sous la forme

0 ≤ yi ≤ 1, 0 ≤ zij ≤ 1, pour tout i, j (7)

yi et zij entiers pour tout i, j (8)

Le modèle de formulation n'est pas encore tout à fait exact. En effet, si z ij = 0, il n'y a pas
de route de livraison allant de l'usine i au marché j et il faut donc que dans ce cas x ij = 0
sans limiter les autres solutions réalisables données par les contraintes (6) et (2). Pour ce
faire, nous ajoutons les contraintes

xij - Uij zij ≤ 0, pour tout i, j (9)

où Uij est un nombre suffisamment grand pour ne pas enlever de solutions réalisables à x ij
si zij =1. Par exemple, on pourra prendre

Uij = ai
 CHAPITRE VII

On vérifie que si zij = 0, les conditions (3) et (9) impliquent que x ij = 0. Par contre si
zij = 1, alors la condition (9) est superflue étant donnée la contrainte correspondante dans
(6) sous la restriction (2). De plus, il est facile de voir (vu que l'on minimise) que la
solution optimale est atteinte pour z ij = 0 lorsque xij = 0. Ce problème se généralise
facilement au cas où un coût fixe est associé à une variable x j si xj > 0 dans un programme
non linéaire quelconque.

Ainsi, notre problème se traduit par le programme linéaire mixte (que nous savons
résoudre) :

n
 xij - ai yi ≤ 0, i = 1, 2, ..., m
j=1

m
 xij ≥ bj, j = 1, 2, ..., n
i=1

xij - ai zij ≤ 0, pour tout i, j

xij ≥ 0, pour tout i, j

0 ≤ yi ≤ 1, 0 ≤ zij ≤ 1, entiers pour tout i, j

m m n m n
MIN Z =  F i yi +   cij xij +   Fij zij
i=1 i=1 j=1 i=1 j=1


6.4 Classement des méthodes de résolution

Un très grand nombre d'algorithmes ont été proposés pour résoudre les problèmes de
programmation linéaire en nombres entiers, mais la plupart d'entre eux ne se sont pas
révélés suffisamment efficaces pour traiter, dans des temps raisonnables, des problèmes
concrets variés. C'est pourquoi, de nombreux travaux ont conduit à proposer plutôt des
algorithmes spécifiques capables de résoudre certaines classes de problèmes de PLE.
PROGRAMMATION LINÉAIRE EN NOMBRES ENTIERS (PLE) 23

Une première façon de classer les algorithmes serait de distinguer d'une part, ceux qui ne
traitent que les PLE où toutes les variables sont entières et, d'autre part, ceux qui traitent
les PLE dans lesquels certaines variables sont continues. À l'intérieur de chacune de ces
deux classes, on pourrait distinguer les algorithmes qui ne prennent en compte que des
variables booléennes de ceux qui acceptent n'importe quelles variables entières. Nous
allons plutôt considérer les familles de méthodes suivantes (M. Simonnard, 1973).

A) La méthode du simplexe

Nous considérons la sous-classe des problèmes de programmation linéaire qui

admettent une solution optimale entière laquelle est aussi optimale pour le problème
PLE correspondant.

B) Les méthodes de troncature

Soit D le domaine formé par l'ensemble des solutions réalisables du problème de

programmation linéaire associé (PL), on cherche à construire un domaine convexe D',
contenu dans D, qui admette la solution de PLE cherchée comme sommet optimal: la
solution de PLE peut alors s'obtenir facilement en résolvant un problème PL sur le
domaine D'.

En pratique, D' est construit par adjonctions successives de contraintes linéaires qui
tronquent D, donnant ainsi naissance à une suite de polyèdres D1, D2, ..., Di, ..., D':
D'  ... D1 D.

Si l'on minimise z sur Di par la méthode du simplexe, ou bien les coordonnées du

sommet optimal sont entières et constituent alors la solution du problème PLE, ou bien
il existe, au voisinage du sommet optimal de D i, une région qui ne contient aucun point
à coordonnées entières et que l'on pourra donc soustraire de D i, par une troncature
convenable, pour former Di+1 Di.

C) Les méthodes d'exploration des stratégies globales

On examine une suite de stratégies S lesquelles représentent chacune une combinaison

de n valeurs entières admissibles de x: 0 ≤ j ≤ xj ≤ j, j = 1, 2, ..., n entier. Pour
chacune de ces stratégies, on détermine, par la résolution d'un problème de
 CHAPITRE VII

programmation linéaire, si D(S) est vide ou s'il ne l'est pas, et la valeur z(S) attachée à
cette stratégie. Les algorithmes diffèrent par la méthode de choix des stratégies à
examiner successivement, le but étant évidemment d'explorer le plus petit nombre
possible de stratégies avant d'atteindre, de façon certaine, l'optimum du problème
PLE.

D) Les méthodes d'exploration des stratégies partielles (seulement L < n composantes de x

prennent chacune une valeur entière admissible) où les contraintes d'intégralité sont
satisfaites partiellement.

Nous partitionnons progressivement l'ensemble des solutions du problème PL associé à

PLE en sous-ensembles de plus en plus restreints, de sorte que l'on arrive à obtenir des
sous-ensembles qu'il n'est plus nécessaire de partitionner parce qu'on sait résoudre le
problème relatif au sous-ensemble et que l'on soit assuré qu'une solution optimale
locale, relative à l'un des sous-ensembles considérés, est optimale pour l'ensemble des
solutions du système PLE.

Comme toute classification, celle qui est utilisée ici n'est pas parfaite: certains algorithmes
pourraient aussi bien être classés dans une famille que dans une autre. Dans les prochains
chapitres, différentes méthodes appartenant à ces familles seront examinées.

==================================