Programmation Linéaire en Nombres Entiers

P-IINFO
Institut Supérieur d'Informatique et de Multimédia de Sfax

Supports du cours: Recherche Opérationnelle

2025-2026

P-IINFO (ISIM-Sfax) PLNE 2025-2026 1 / 21

Plan

1 Programmation Linéaire en Nombres Entiers

2 Modélisation de situations particulières

Contraintes logiques
Utilisation des variables binaires

P-IINFO (ISIM-Sfax) PLNE 2025-2026 2 / 21

Plan

1 Programmation Linéaire en Nombres Entiers

2 Modélisation de situations particulières

P-IINFO (ISIM-Sfax) PLNE 2025-2026 3 / 21

Introduction

Programmation Linéaire en Nombres Entiers (PLNE) : modéliser des

problèmes généralement NP-dicile
Variables de décision discrètes (entières, booléennes)
Méthode de résolution : algorithme de séparation et évaluation
(Branch-and-Bound, B&B), méthode de plans sécants (cutting planes
method), algorithme de coupes et branchement (Branch-and-Cut,
B&C),...
Optimisation combinatoire
Programmation linéaire mixte : variables discrètes et variables
continues (Mixed Integer Linear Program)

P-IINFO (ISIM-Sfax) PLNE 2025-2026 4 / 21

Forme canonique PLNE

max cT x
s.c. Ax ≤ b
x ≥0
x ∈ Zn

P-IINFO (ISIM-Sfax) PLNE 2025-2026 5 / 21

Plan

1 Programmation Linéaire en Nombres Entiers

2 Modélisation de situations particulières

Contraintes logiques
Utilisation des variables binaires

P-IINFO (ISIM-Sfax) PLNE 2025-2026 6 / 21

Contraintes logiques (1) source :S.L. Digabel

On ne peut pas exprimer de conditions logiques directement(avec des

"si", "sinon", "alors", etc.), sinon le modèle n'est plus linéaire
Par exemple la condition x = 1 ⇐⇒ y = 1 (ou x = 0 ⇐⇒ y = 0)
se modélise à l'aide de la contrainte x = y .
Pour les autres exemples, il est utile de se baser sur une table des
valeurs possibles an de déterminer les situations à éliminer à l'aide de
contraintes.

P-IINFO (ISIM-Sfax) PLNE 2025-2026 7 / 21

Conditions logiques x =1⇒y =1

Cette contrainte implique que la ligne en rouge dans le tableau suivant

correspond au cas à éliminer.

Par conséquent, ceci correspond à la contrainte y ≥ x.

P-IINFO (ISIM-Sfax) PLNE 2025-2026 8 / 21

Conditions logiques x =0⇒y =1

Cette contrainte implique que la ligne en rouge dans le tableau suivant

correspond au cas à éliminer.

Par conséquent, ceci correspond à la contrainte x + y ≥ 1.

P-IINFO (ISIM-Sfax) PLNE 2025-2026 9 / 21

Conditions logiques ( x = 1 et y = 1) ⇒ z = 1
La ligne en rouge correspond au cas à éliminer :

On ajoute donc la contrainte x +y −z ≤1

P-IINFO (ISIM-Sfax) PLNE 2025-2026 10 / 21
Conditions logiques ( x = 1 ou y = 1) ⇒ z = 1
Les lignes en rouge correspondent aux cas à éliminer :

 −x + y − z ≤ 0


On ajoute donc les contraintes x −y −z ≤0


x +y −z ≤1
La contrainte x + y − 2z ≤ 0 est aussi valable et peut remplacer les 3
dernières contraintes.
P-IINFO (ISIM-Sfax) PLNE 2025-2026 11 / 21
Conditions logiques x >0⇒y =1

1 x et y variables binaires ∈ {0, 1}

▶ Condition logique x = 1 ⇒ y = 1
▶ La contrainte linéaire est
x ≤y

2 x entière (ou réelle) et y binaire ∈ {0, 1}

▶ Condition logique x > 0 ⇒ y = 1
▶ La contrainte linéaire est
x ≤ My
avec M > 0 est une constante très grande, dite "grand M" (big M ).

P-IINFO (ISIM-Sfax) PLNE 2025-2026 12 / 21

Objectif : modélisation d'un coût xe

Un objectif à minimiser contient le terme cx avec c un coût

proportionnel à la valeur de x .
On veut ajouter un coût xe F lorsque x > 0
On introduit une variable binaire y et :
▶ On ajoute le terme Fy à l'objectif cx ← cx + Fy
▶ On ajoute la contrainte
x ≤ My
avec M > 0 est dit "grand M" (big M ).
M pourrait aussi être une borne supérieure sur x .
S'il est avantageux d'avoir x > 0, alors automatiquement y vaudra 1
et on paiera le coût xe. Sinon, y sera automatiquement mise à 0
pour ne pas payer le coût xe.

P-IINFO (ISIM-Sfax) PLNE 2025-2026 13 / 21

Contraintes : une contrainte parmi deux doit être satisfaite
(contraintes mutuellement exclusives)

Une des deux contraintes suivantes doit être satisfaite

Soit 3x1 + 2x2 ≤ 18
Soit x1 + 4x2 ≤ 16
Soit M une constante très grande (big M ), le système précédent est
équivalent à :

 3x1 + 2x2 ≤ 18


Soit et

x1 + 4x2 ≤ 16 + M
 3x1 + 2x2 ≤ 18 + M


Soit et

x1 + 4x2 ≤ 16

P-IINFO (ISIM-Sfax) PLNE 2025-2026 14 / 21

Contraintes : deux contraintes mutuellement exclusives

Soit la variable binaire y ∈ {0, 1} dénit par :

1 si la contrainte 1 est retenue (satisfaite)

y= 0 si la contrainte 2 est retenue (satisfaite)

Le système ci-dessus est alors équivalent à

 3x1 + 2x2 ≤ 18 + M (1 − y )


Soit et

x1 + 4x2 ≤ 16 + My

P-IINFO (ISIM-Sfax) PLNE 2025-2026 15 / 21

Contraintes : K contraintes parmi N
Soit N contraintes
a1 x ≤ b1
a2 x ≤ b2
..
.
aN x ≤ bN
Supposons que seulement K contraintes parmi les N contraintes doivent
être satisfaites.
Soit les variables binaires yi ∈ {0, 1}, i = 1, . . . , N .
Le système est donc équivalent à :
a1 x ≤ b1 + M (1 − y1 )
a2 x ≤ b2 + M (1 − y2 )
..
.
a x ≤ bN + M (1 − yN )
N
N
i =1 yi = K
P

P-IINFO (ISIM-Sfax) PLNE 2025-2026 16 / 21

Exemple

Une compagnie a développé 3 nouveaux produits et pour limiter les frais de commercialisation,
elle impose les contraintes suivantes :
1 Parmi les 3 nouveaux produits, exactement 2 doivent être choisis pour la fabrication.

2 Un des deux systèmes de production de l'usine peut être utilisé dans la fabrication.

Le coût de production unitaire pour chaque produit est le même dans les deux systèmes. Par
contre le temps nécessaire pour fabriquer une unité de chaque produit peut être diérente d'un
système à l'autre.
Objectif : Comment organiser la production pour que le coût soit minimum
Données :

Temps nécessaire à la production

d'une unité de produit sur
Système 1 Système 2 Qtés Max Coût Unitaire
P1 3 5 7 5
P2 4 6 5 7
P3 2 2 9 3
Temps
Total 30 40
Disponible

P-IINFO (ISIM-Sfax) PLNE 2025-2026 17 / 21

PLNE (sans contraintes (1) et (2))

xi : quantité du produit i fabriqué.

min 5x1 + 7x2 + 3x3
3x1 + 4x2 + 2x3 ≤ 30
5x1 + 6x2 + 2x3 ≤ 40
x1 ≤ 7
x2 ≤ 5
x3 ≤ 9
x1 , x2 , x3 ∈ N

P-IINFO (ISIM-Sfax) PLNE 2025-2026 18 / 21

PLNE (sans contrainte (1))

xi : quantité du produit i fabriqué.

y : 1 si système 2 est retenu, 0 si système 1 est retenu.
min 5x1 + 7x2 + 3x3
3x1 + 4x2 + 2x3 ≤ 30 + My
5x1 + 6x2 + 2x3 ≤ 40 + M (1 − y )
x1 ≤ 7
x2 ≤ 5
x3 ≤ 9
x1 , x2 , x3 ∈ N
y ∈ {0, 1}

P-IINFO (ISIM-Sfax) PLNE 2025-2026 19 / 21

PLNE

xi : quantité du produit i fabriqué.

y : 1 si système 2 est retenu, 0 si système 1 est retenu.
zi : 1 si xi > 0, 0 sinon.
min 5x1 + 7x2 + 3x3
3x1 + 4x2 + 2x3 ≤ 30 + M y
5x1 + 6x2 + 2x3 ≤ 40 + M (1 − y )
x1 ≤ 7, x2 ≤ 5, x3 ≤ 9
x1 ≤ M z1
x2 ≤ M z2
x3 ≤ M z3
z1 + z2 + z3 = 2
x1 , x2 , x3 ∈ N
z1 , z2 , z3 , y ∈ {0, 1}
P-IINFO (ISIM-Sfax) PLNE 2025-2026 20 / 21
PLNE optimisé

xi : quantité du produit i fabriqué.

y : 1 si système 2 est retenu, 0 si système 1 est retenu.
zi : 1 si xi > 0, 0 sinon.
min 5x1 + 7x2 + 3x3
3x1 + 4x2 + 2x3 ≤ 30 + M y
5x1 + 6x2 + 2x3 ≤ 40 + M (1 − y )
x1 ≤ 7 z1
x2 ≤ 5 z2
x3 ≤ 9 z3
z1 + z2 + z3 = 2
x1 , x2 , x3 ∈ N
z1 , z2 , z3 , y ∈ {0, 1}

P-IINFO (ISIM-Sfax) PLNE 2025-2026 21 / 21