REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE

Ministère de l’Enseignement Supérieur et de la Recherche Scientifique

Université MOULOUD MAMMERI de Tizi-Ouzou

FACULTE DES SCIENCES

DEPARTEMMENT DES MATHEMATIQUES

En vue de l’obtention du Diplôme de Master

Spécialité : Recherche Opérationnelle

Thème
Optimisation d’un problème de programmation
linéaire en nombres entiers par la méthode
Branch and Bound

Présenté par : Encadrées par :

 ZIDANE THANINA
 Mme Abderhmani Amel
 HAMDAD KAHINA

Promotion
2016-2017
Résumé :
Quelques problèmes de la vie courante peuvent être modélisés comme des
problèmes combinatoires. Dans notre travail, nous nous intéressons à la
résolution des problèmes de programmation linéaire en nombres entiers par la
méthode : " Séparation et Évaluation", "Branch and Bound".

Nous présentons les méthodes de résolutions de problèmes d’optimisation

proposées dans la littérature. Notre travail est devisé en trois chapitres :
Le premier chapitre présente quelques définitions dont : la programmation
mathématique, la programmation linéaire et quelques généralités sur la
classification des problèmes et les méthodes de résolutions de problèmes
d’optimisation.

Dans le deuxième chapitre, on se focalise sur les méthodes de résolutions

exactes. Nous avons illustré avec un exemple chacune de ces méthodes : la
méthode graphique, la méthode du simplexe et la méthode dual du simplexe.
On présente aussi les deux algorithmes : L’algorithme du simplexe et
l’algorithme dual du simplexe.

Le troisième chapitre est consacré à la méthode de Séparation et Évaluation

"Branch and Bound". Nous avons présenté la méthode, son principe, ces trois
procédures essentielles et les trois stratégies de parcours, ainsi que l’algorithme
général de la méthode et un exemple d’application avec une implémentation
informatique en utilisant le logiciel MATLAB version 2014 et le LpSolve IDE.

Mots clés :
Programmation linéaire, programmation mathématique, simplexe, dual du
simplexe, la méthode Branch and Bound, programmation en nombres entiers .
Table des matières

Remerciements 2

Dédicaces 3

Introduction générale 4

1 Définitions et Généralités 2
1.1 Quelques définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 La programmation mathématique . . . . . . . . . . . . . . . . . . . . 2
1.1.2 La programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.3 Forme générale d’un programme linéaire . . . . . . . . . . . . . . . . 3
1.1.4 Polyèdre et polytope . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.5 Optimum global . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.6 Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Classification des problèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Les contraints et l’objectif . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 La complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Méthodes d’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 Les méthodes exactes . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.2 Les méthodes approchées(heuristiques) . . . . . . . . . . . . . . . . . 8
1.3.3 Comparaison entre les méthodes exactes et les méthodes approchées 9

2 Méthodes de résolution 10
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Résolution graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Méthode du Simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3.1 L’algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4 Méthode dual du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4.1 Principe de la dualité . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4.2 L’algorithme dual du simplexe . . . . . . . . . . . . . . . . . . . . . 17
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3 La méthode de Séparation et Évaluation(BRANCH AND BOUND) 21

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Principe de la méthode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.1 Stratèges de parcours . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3 Algorithme général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.4 Exemple d’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1
 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

Conclusion générale 39

Bibliographie 40

2
Remerciements

Nous remercions tout d’abord  DIEU  tout puissant de nous avoir donné suffisamment
de force et surtout de courage et de persévérance pour mener notre travail à terme.
Nous tenons a adresser toutes les reconnaissances et notre gratitudes a notre promotrice :
"Abderehmani Amel" , ses précieux conseils et son suivi.
Que les membres du jury trouvent ici nos remerciements les plus vifs pour avoir
aimablement accepté de juger notre travail.
Sans oublier d’exprimer notre reconnaissance et gratitude à tous nos enseignants durant
notre cursus au département Mathématiques.
Enfin, nous tenons a remercier tous ceux qui ont contribué de près ou de loin a la
réalisation de ce travail.

Kahina et Thanina

3
Dédicaces

Je tiens très respectueusement à dédier ce modeste travail à :

Mes très chers parents qui ont toujours été là pour moi, et qui m’ont donné un honorable
modèle de labeur et de persévérance,qu’ils trouvent ici l’expression de toute ma profonde
reconnaissance et ma parfaite considération.
Mes frères et sœurs .
Mes beaux frères et belles sœurs .
Mes chers nièces et neveux.
toute ma famille, du plus vieux jusqu’au plus jeune.
Ma binôme et à toute sa famille .
Je désire le dédier à tous mes amis et camarades .

Kahina

Je dédie ce travail à :
La mémoire de mon très cher KHALI BEZZAOU SADDEK, que dieu l’accueille dans son
éternel paradis.
Ma très chère mère, que dieu lui accord une longue vie.
Mon petit cher frère YOUVA à qui je souhaite la réussite au baccalauréat.Que dieu le
protège .
Ma petite sœur THINHINANE, que j’adore énormément.
Tous mes amis et camarades, que j’ai connu tout au long de mes études (lycée
BENI-DOUALA ; la fac et la résidence universitaire M.M.T.O).
Ma chère binôme et toute sa famille .

Thanina

4
Introduction générale

La Recherche Opérationnelle est la discipline utilisée pour élaborer de meilleures décisions.

Elle permet d’optimiser le fonctionnement des systèmes de production ou d’organisation ou
autres.
Une des parties essentielles de la recherche opérationnelle est la programmation linéaire, qui
est introduite par les russes Kontorovitch en (1939) et résolue par l’Américain G.B .Dantzig
en (1947).[3]
La programmation linéaire est l’un des principaux outils de modélisation en recherche opéra-
tionnelle. C’est aussi la source des méthodes avancées de la programmation mathématique,
qui permettent de résoudre les programmes quadratiques, entiers, stochastiques . . . etc. On
distingue dans la programmation linéaire, la programmation linéaire continue (PLC) et la
programmation linéaire en nombres entiers (PLNE), comme il est possible d’avoir les deux
en même temps, ce qu’on appelle la programmation linéaire en variables mixtes (PLM).

Dans notre travail, nous nous intéressons à la résolution des problèmes de programmation
linéaire en nombres entiers par la méthode :
" Séparation et Évaluation " , "Branch and Bound" .
Nous présentons les méthodes de résolutions de problèmes d’optimisation proposées dans la
littérature. Notre travail est devisé en trois chapitres :

Le premier chapitre présente quelques définitions dont : la programmation mathéma-

tique,la programmation linéaire et quelques généralités sur la classification des problèmes et
les méthodes de résolutions de problèmes d’optimisation .

Dans le deuxième chapitre, on se focalise sur les méthodes de résolutions exactes.

Nous avons illustré avec un exemple chacune de ces méthodes : la méthode graphique, la mé-
thode du simplexe et la méthode dual du simplexe.On présente aussi les deux algorithmes :
L’algorithme du simplexe et l’algorithme dual du simplexe.

Le troisième chapitre est consacré à la la méthode de Séparation et Évaluation "Branch

and Bound" .
Nous avons présenté la méthode ,son principe ,ces trois procédures essentielles et les trois
stratégies de parcours ,ainsi que l’algorithme général de la méthode et un exemple d’appli-
cation avec une implémentation informatique en utilisant le logiciel Matlab version 2014 et
le LpSolve IDE.

1
Chapitre 1

Définitions et Généralités

1.1 Quelques définitions

1.1.1 La programmation mathématique
La programmation mathématique est un ensemble de méthodes ou processus mathéma-
tiques dont le but est de trouver un optimum pour un problème décisionnel donné. C’est à
dire il s’agit de rechercher l’optimum d’une fonction de n variables et de m contraintes .

La programmation mathématique englobe des outils comme :

– La programmation linéaire :
Un problème linéaire (PL) est un problème d’optimisation maximisant ou minimisant
une fonction objectif linéaire à n variables de décision supposées non négatives soumises
à un ensemble de contraintes exprimées sous forme d’équations ou inéquations linéaires.

– La programmation linéaire en nombres entiers :

C’est une extension de la méthode précédente qui permet de travailler aussi sur des
petites quantités entières (nombre de bus, nombre d’ avions) et décisions binaires (telle
action est effectuée ou non).

– La programmation non linéaire :

Elle est utilisée lorsque les relations entre les décisions ne peuvent pas être exprimées
de façon linéaire, même avec des hypothèses simplificatrices. Elle est plus générale que
la programmation linéaire mais a le défaut de ne pas garantir l’obtention de meilleures
décisions.

– La programmation dynamique :
Adaptée aux problèmes décisionnels possédant une propriété de sous-optimalité, c’est-
à-dire que des décisions bonnes pour le problème global sont aussi bonnes pour des
sous-problèmes.

2
1.1.2 La programmation linéaire
Le problème le plus simple de la programmation mathématique est celui de programma-
tion linéaire.
La programmation linéaire peut être définie comme un outil mathématique qui permet d’ana-
lyser divers types de situations dans lesquelles nous retrouvons une fonction linéaire d’un
certain nombre de variables, appelée Fonction Objectif que l’on désire optimiser ( maximiser
ou minimiser).
Ces variables appelées variables de décision (dont on veut déterminer les valeurs optimales)
sont soumises à des contraintes qui sont linéaires.[3]

1.1.3 Forme générale d’un programme linéaire

Lors de la modélisation d’un problème de programmation linéaire on est amené à déter-
miner trois éléments importants :

1. Les variables de décision :

C’est la première étape dans le processus de modélisation qui consiste à identifier cor-
rectement toutes les variables de décision (inconnues) de la situation à modéliser.

2. Les contraintes linéaires :

Dans la problématique de la situation, il faut être en mesure d’identifier tout genre de
restriction qui peut limiter les valeurs que peuvent prendre les variables de décision.

3. La fonction objectif :
On associe à chaque variable de décision du modèle correspond ,un coefficient éco-
nomique indiquant la contribution unitaire de la variable correspondante à l’objectif
poursuivi. Par la suite, on pourra en déduire la fonction objectif que l’on veut optimiser
(soit à maximiser soit à minimiser).

La forme la plus générale d’un problème de (P.L) est :

 n
P


 opt Z= max(minZ) = cj x j (1, 1)

 j=1
n



i ∈ I ⊂ {1, ..., m}
P



 aij xj < bi (1, 2)

 j=1

 n
l ∈ L ⊂ {1, ..., m}
P
alj xj = bl (1, 2)



(P L) j=1
n

k ∈ K ⊂ {1, ..., m}
P
akj xj > bk (1, 2)






 j=1
xj ∈ R+ , j ∈ {1, .., n} (1, 3)





I ∩L∩K =∅





I ∪ L ∪ K = {1, ..., m}


avec cj ,aij ,bi des constantes et xj variables.

(1,1)fonction économique ou fonction objectif.
(1,2)contrainte réelle .

3
(1,3)contrainte de non-négativité.

Remarque :
• Un programme linéaire est dit sous forme canonique si toutes les inégalités sont dans le
même sens, les variables de décision sont positives ou nulles et les contraintes d’égalité en
sont absentes.
n

P



 opt z= max(minZ) = cj x j

 j=1
n
(P L) P
aij xj ≥ bi i= 1,...,m

j=1



xj ≥ 0 j= 1,...,n



ou sous la forme :
n

P



 opt z= cj x j

 j=1
n
(P L)  P
aij xj ≤ bi i= 1,...,m
j=1



xj ≥ 0 j= 1,...,n



• Un programme linéaire est dit sous forme standard s’il est sous forme :
n

P



 optz= cj x j

 j=1
n
(P L) P
aij xj = bi i= 1,...,m

j=1



xj ≥ 0 j= 1,...,n



• Toute inégalité ≥ (resp ≤) peut être transformée en égalité ,on rajoutant des variables
d’écart.
• Toute inégalité ≥ est équivalente à une inégalité ≤ en multipliant ses termes par (-1).

1.1.4 Polyèdre et polytope

1. Définitions :

•H={x ∈ Rn /ax = b,a ∈ Rn } définie un hyperplan H de dimension (n-1) et divise Rn

en deux demi-espaces convexes :
H+ ={x ∈ Rn /ax ≥ b}= {x ∈ Rn /ai1 x1 + ... + aij xj + ... + ain xn ≥ bi }.
i= 1,...,m et j= 1,...,n.
H− ={x ∈ Rn /ax ≤ b}= {x ∈ Rn / ai1 x1 + ... + aij xj + ... + ain xn ≤ bi }.
i= 1,...,m et j= 1,...,n. [7]
• Un ensemble E est dit convexe si :
∀x, y ∈ E, [λx + (1 − λ)y] ∈ E pour tout λ,0 ≤ λ ≤ 1.
Géométriquement :
V est dit convexe si tout segment de droite dont les extrémités appartiennent à V est
inclus dans V .
Considérons les deux ensembles illustrés ci-dessous :

4
 W est non convexe,car les points P et P’ sont les extrémités d’un segment dont au
moins un point n’appartient pas à W.

2. Polyèdre :
Un polyèdre P ⊂ Rn est l’ensemble des solutions d’un système fini d’inégalités
linéaires .
P={x ∈ Rn /Ax ≤ b}.
C’est l’intersection d’un nombre fini de demi-espaces
H− ={x ∈ Rn /ax ≤ b}= {x ∈ Rn / ai1 x1 + ... + aij xj + ... + ain xn ≤ bi }.a ∈ Rn , b ∈ Rn
3. polytope :
Un polytope convexe est un polyèdre convexe et borné .

1.1.5 Optimum global

Une solution x∗ est dite optimale (ou optimum global) si les deux contraintes suivantes
sont vérifiées :
1. Elle est réalisable : tirée de l’ensemble de solutions possibles et respecte toutes les contraintes
du problème posé.
2. on a :
 f (x∗ ) = max{f (x)} en cas de problème de maximisation.

x∈X
 f (x∗ ) = min{f (x)} en cas de problème de minimisation.
x∈X

Où X est l’ensemble des solutions réalisables .

Autrement dit, l’optimum global est le meilleur optimum local. Ainsi, une solution est dite
optimum global si :
(
f (x∗ ) ≥ f (x)∀x ∈ E(X) en cas de problème de maximisation..
f (x∗ ) ≤ f (x)∀x ∈ E(X) en cas de problème de minimisation.
Où E(X) est l’ensemble d’optimums locaux.
Il est à noter que l’optimum global est aussi nommé maximum global au cas de problème de
maximisation et minimum global au cas de problème de minimisation.

5
La figure suivante représente une courbe représentant les optimums locaux et les optimums
globaux d’une fonction d’évaluation. [2]

1.1.6 Relaxation
La relaxation d’un problème P (i) consiste à l’élargir en un autre problème tel que :
( (
(i) Fi = minF (x) FiR = minF (x)
P ⇒ (P R(i) )
x ∈ Z+n n
x ∈ R+
De sorte que FiR ≤ Fi pour un problème de minimisation et respectivement FiR ≥ Fi pour
un problème de maximisation.
En général dans notre problème ,la relaxation linéaire (PR)de (P) est obtenue par relâche-
ment des contraintes d’intégrité .[4]

1.2 Classification des problèmes

1.2.1 Les contraints et l’objectif
Parmi les problèmes de la programmation linéaire on trouve :

– Les problèmes linéaires en variables mixtes :

Un problème linaire en variables mixtes est un problème d’optimisation pour lequel
certaines variables sont entières et d’autres sont réelles .

6
 n

P



 opt Z= max(minZ) = cj x j

 j=1

 n
aij xj S bi , i ∈ {1, ..., m}

 P

(P L) j=1



 ∀j ∈ J1 , xj ∈ R+ , j ∈ {1, ..., n}
∀j ∈ J2 , xj ∈ N, j ∈ {1, ..., n}





J = J1 ∪ J2 , card(J) = n.



– Les problèmes linéaires en nombres entiers(PLNE) :

Un problème linéaires en nombres entiers est un problème d’optimisation dont toutes
les variables sont entières .
n

P



 opt Z= max(minZ) = cj x j

 j=1
n
(P L) P
aij xj T bi , i ∈ {1, ..., m}

j=1



xj ∈ N j ∈ {1, ..., n}



– Les problèmes linéaires en variables binaires :

Un problèmes linéaire en variables binaires ou (0 et 1) est un problème d’optimisation
en nombres entiers ,telle que les variables entières prennent leurs valeurs dans l’en-
semble {0, 1}.
n

P



 opt Z= max(minZ) = cj x j

 j=1
n
(P L) P
aij xj T bi , i ∈ {1, ..., m}

j=1



xj ∈ {0, 1} j ∈ {1, ..., n}



1.2.2 La complexité
Afin de mesurer la difficulté d’un problème donné et la comparer avec celles des autres
problèmes , nous pouvons calculer la complexité algorithmique de chacun d’entre eux.
La complexité d’un problème donné est discutée sur deux cotés :
Le coté temporel "complexité temporelle".
Le coté spatial "complexité spatiale".
Bien que la théorie de la complexité se concentre sur des problèmes de décision, elle peut
être étendue aux problèmes d’optimisation ,elle classe les problèmes selon leurs complexités
en deux classes principales :
– La classe P (Polynomial time) :
Un problème est dit polynomial s’il existe un algorithme polynomial pour le résoudre,la
classe P est une classe d’algorithme efficace et facile à résoudre .
Exemple :le problème du plus court chemin .
– La classe NP (Non déterministe Polynomial time) :
Un problème P est dit NP s’il peut être résolu par une machine de Turing non déter-
ministe .
Exemple :la recherche d’un cycle hamiltonien .

7
 En outre, la classe NP partage les problèmes de la classe NP en deux sous classes :

– La classe NP-complet :
Un problème est dit NP-complet lorsqu’il est dans la classe NP et si on peut le ramener
par une transformation polynomial à un problème de la classe NP.
Exemple :problème de voyageur de commerce .
– La classe NP-difficile :
Un problème P est dit NP-difficile s’il existe une réduction polynomial de problème de
satis fiabilité à P .
Exemple :les PLNE (problèmes linéaire en nombres entiers ).[2]

1.3 Méthodes d’optimisation

1.3.1 Les méthodes exactes
La méthode de résolution exacte doit permettre l’obtention d’au moins une solution opti-
male . Ce genre de méthode demande en général des temps d’exécution très élevés ainsi que
des ressources mémoire importantes sur les instances de grande taille
Nous citons quelques méthodes de la classe des algorithmes exacts, ces méthodes donnent
une garantie de trouver la solution optimale pour une instance de taille finie dans un temps
limité et de prouver son optimalité .

– La méthode de séparation et d’evaluation Branche and Bound.

– La méthode des coupes planes (cutting-plane).
– La méthode (Branch and Cut).

1.3.2 Les méthodes approchées(heuristiques)

En optimisation combinatoire, une heuristique est un algorithme approché qui permet
d’identifier en un temps polynomial au moins une solution réalisable rapide, pas obligatoi-
rement optimale. L’usage d’une heuristique est efficace pour calculer une solution approchée
d’un problème et ainsi accélérer le processus de résolution . Généralement une heuristique est
conçue pour un problème particulier, en s’appuyant sur sa structure propre sans offrir aucune
garantit quant à la qualité de la solution calculée. Les heuristiques peuvent être classées en
deux catégories :
– Méthodes constructives qui génèrent des solutions à partir d’une solution initiale en
essayant d’en ajouter petit à petit des éléments jusqu’à ce qu’une solution complète
soit obtenue.
– Méthodes de fouilles locales qui démarrent avec une solution initialement complète
(probablement moins intéressante) et de manière répétitive essaie d’améliorer cette so-
lution en explorant son voisinage.

8
1.3.3 Comparaison entre les méthodes exactes et les méthodes ap-
prochées
1. Les méthodes exactes :
– Elles trouvent la solution optimale.
– Elles peuvent prendre un nombre exponentiel d’itérations.
2. Les heuristiques :
– Elles produisent une solution sous-optimale.
– Elles ne produisent pas de mesure de qualité de la solution.
– En général, elles ne prennent pas un nombre exponentiel d’itérations.

9
Chapitre 2

Méthodes de résolution

2.1 Introduction
La résolution de différentes sortes de problèmes rencontrés dans notre vie quotidienne a
poussé les chercheurs à proposer des méthodes de résolution et à réaliser de grands efforts
pour améliorer leurs performances en termes de temps de calcul nécessaire et de la qualité de
la solution proposée. Au fil des années, de nombreuses méthodes de résolution de problèmes
de différentes complexités ont été proposées.
Les méthodes de résolution exactes sont nombreuses et se caractérisent par le fait qu’elles
permettent d’obtenir une ou plusieurs solutions dont l’optimalité est garantie.
Parmi ces méthodes, on peut citer la méthode graphique ,l’algorithme du simplexe et l’algo-
rithme dual du simplexe.

2.2 Résolution graphique

La méthode graphique permet la résolution de problèmes linéaires simples .
Cette méthode est limitée aux problèmes à deux ou trois variables de décision puisqu’il n’est
pas possible d’illustrer graphiquement plus de trois dimensions. Bien qu’en général on puisse
difficilement trouver des problèmes avec seulement deux ou trois variables de décision, cette
méthodologie de résolution est cependant très utile. Lors de la reproduction graphique de
situations possibles, tels que :
L’existence d’une solution optimale unique, des solutions optimales alternatives.
La non -existence de solution et l’absence de partie bornée.
La méthode graphique nous offre une aide visuelle pour interpréter et comprendre l’algo-
rithme de la méthode du Simplexe.
Les étapes de résolution, de problèmes par la méthode graphique sont les suivantes :

– Créer un système de coordonnées cartésiennes, dans lequel chaque variable de décision

est représentée par un axe.

– Établir une échelle de mesure pour chacun des axes appropriés à sa variable associée.

– Dessiner dans le système de coordonnées les contraintes du problème,y compris celles

10
 des variables de décision .

– Remarquer qu’une inéquation précise une région qui sera le demi-plan limité par la ligne
droite, qui représente la contrainte qu’on considère comme une contrainte d’égalité alors
que si une équation linéaire détermine une région c’est la ligne droite, elle-même .

– L’intersection de toutes les régions détermine la région ou l’espace faisable (qui est un
ensemble convexe).
Si non , si il n’y a pas de point qui satisfait toutes les contraintes simultanément de
sorte que le problème ne sera pas résolu,on dit que le problème est infaisable .

– Déterminer les points extrêmes ou les sommets du polyèdre qui forme la région faisable.

– Ces points seront les candidats à la solution optimale.

– Évaluer la fonction objectif à chaque sommet et celui qui maximise la fonction objectif
définie la solution optimale (pour un problème de maximisation) .[8]

• Exemple 01 :
Soit le problème suivant :




max Z= 6x1 + 4x2
3x1 + 9x2 ≤ 81




(P ) 4x1 + 5x2 ≤ 55
≤ 20




 2x1 + x2
x1 , x2 ≥ 0



– Les contraintes où apparaissent des inégalités correspondent géométriquement à des

demi-plans.

– L’intersection des demi-plans est un polyèdre qui représente l’ensemble de solutions

réalisables du problème .

11
•Notations :
JB :Ensemble des indices de variables de base.
JH :Ensemble des indices hors base.
AB :Sous matrice de A d’ordre m*m.
AH :Sous matrice de A d’ordre m*(n-m).
min f (x)=− max(−f (x)).
x∈X x∈X

2.3 Méthode du Simplexe

Dans la plupart des problèmes réels on a plus de deux variables à déterminer .
Une procédure algébrique pour résoudre les programmes linéaires avec plus de deux variables
fera l’objet de cette section.C’est la méthode du simplexe.
La méthode du simplexe est une méthode itérative,elle démarre d’un point réalisable ( sommet
de départ) et passe de ce point à un autre en augmentant la valeur de la fonction objectif
dans le cas de maximisation .
On arrête le déroulement de l’algorithme lorsqu’il n’est plus possible d’augmenter la valeur
de la fonction objectif .

2.3.1 L’algorithme du simplexe

Le principe de résolution nécessite un certain nombre d’étapes dont la démarche est la
suivante :
On l’applique pour un problème de maximisation :

1. Écrire le système sous la forme standard.

2. Le point de départ de l’algorithme est l’existence d’une solution réalisable soit :

x = (xB , xH ) =(xB , 0) et A−1
B :La matrice inversible de AB .
3. Construire le premier tableau correspondant à la forme standard.

12
 4. Calculer les Ej = zj − cj , tq : Zj = CBT ∗ A−1
B .
(critère d’optimalité).

5. Si tous les Ej ≥ 0,∀j ∈ JH ,1 ≤ j ≤ (n − m).La solution (xB , 0) est optimale.

Si non :
– Si ∃k ∈ JH tel que :Ek < 0 et A−1B ak < 0 .
Le (PL) n’admet pas un maximum (non borné), arrêt .
– Sinon si ∃k ∈ JH tel que :Ek < 0 et A−1B ak > 0 alors ,aller à 6) :

6. Choisir la variable xk qui entre dans la base tq :Ek =min Ej , Ej < 0 .

j∈JH

7. Choisir la variable xl qui sort de la base tel que :

bi
θl =min{ , aik > 0, 1 ≤ i ≤ m},la variable sortante se trouve sur la léme ligne .
aik

8. Encadrer le pivot alk .

1
9. Multiplier la ligne du pivot par le rapport : .
alk

10. Calculer les valeurs a0ij des autres lignes :

aik ∗ alj
a0ij =aij − ( )
alk
Aller à 4).

• Exemple 02 :
On prend un exemple et on applique le simplexe .

1. Écrire le système sous la forme standard :

Il s’agit de convertir le programme établi sous la forme canonique (système d’inéqua-

tion) a la forme standard (système d’équation avec variables d’écarts).

• La forme canonique est :





max Z= 30x1 + 50x2
3x1 + 2x2 ≤ 1800




(P ) x1 ≤ 400
≤ 600




 x2
x1 ≥ 0, x2 ≥ 0.



• La forme standard est :

x3 ,x4 ,x5 représentent les variables d’écarts.

13
 



max Z= 30x1 + 50x2
3x1 + 2x2 + x3 = 1800




(P )  x1 + x 4 = 400



 x1 + x 5 = 600
xj ≥ 0, j = 1, .., 5.



2. La solution de départ est :

X=(0,0,1800,400,600).

3. Construire le premier tableau correspondant à la forme standard :

ci 30 50 0 0 0
cb base b x1 x2 x3 x4 x5
0 x3 1800 3 2 1 0 0
0 x4 400 1 0 0 1 0
0 x5 600 0 1 0 0 1

4. Calculer les Ej = zj − cj .

ci 30 50 0 0 0
cb base b x1 x2 x3 x4 x5
0 x3 1800 3 2 1 0 0
0 x4 400 1 0 0 1 0
0 x5 600 0 1 0 0 1
Ej -30 -50 0 0 0

5. test d’optimalité .
∃Ej ≤ 0 d’où aller à 6).

6. Choisir la variable xk qui entre dans la base tq :Ek =min Ej .

min Ej =-50 d’où xk = x2 entre dans la base.

7. Choisir la variable xl qui sort de la base tq :

bi
θl =min{ , aik > 0}.
aik
ci 30 50 0 0 0
cb base b x1 x2 x3 x4 x5 θ
0 x3 1800 3 2 1 0 0 1800/2
0 x4 400 1 0 0 1 0 /
0 x5 600 0 1 0 0 1 600/1
Ej -30 -50 0 0 0
θl = θ3 =600/1 d’où xl = x5 sort de la base(car elle se trouve à la 3éme ligne).

14
 8. Encadrer le pivot :a32

1
9. Multiplier la ligne du pivot par le rapport : :
alk
ci 30 50 0 0 0
cb base b x1 x2 x3 x4 x5
0 x3
0 x4
50 x2 600 0 1 0 0 1

10. Calculer les valeurs a0ij des autres lignes :

Cette opération consiste à transformer aij des autres lignes en aij 0 , nous effectuons un
calcul matriciel.
aik ∗ alj
a0ij =aij − ( ).
alk
ci 30 50 0 0 0
cb base b x1 x2 x3 x4 x5
0 x3 600 3 0 1 0 -2
0 x4 400 1 0 0 1 0
50 x2 600 0 1 0 0 1

Aller à l’étape 4).

•Nouveau passage :
On refait les même étapes et on aura les résultats suivants :

ci 30 50 0 0 0
cb base b x1 x2 x3 x4 x5 θ
0 x3 600 3 0 1 0 -2 200
0 x4 400 1 0 0 1 0 400
50 x2 600 0 1 0 0 1 /
Ej -30 0 0 0 50
x1 entre dans la base.
x3 sort de la base.

15
 ci 30 50 0 0 0
cb base b x1 x2 x3 x4 x5
30 x1 200 1 0 1/3 0 -2/3
0 x4 200 0 0 -1/3 1 2/3
50 x2 600 0 1 0 0 1
Ej 0 0 10 0 30
• Test d’optimalité :
Tous les Ej sont positifs . La solution de ce problème est :
 
max Z=36000
 x1 =200
 

x2 =600
• Remarque :
L’optimisation d’un programme linéaire à l’aide de l’algorithme du simplexe nous oblige
parfois à introduire des variables artificielles pour obtenir une solution de départ lorsque
les contraintes sont de type :
n
aij xj ≥ bi , i ∈ {1, ..., m}.
P
j=1
On applique la M-méthode ou la méthode de deux phases.

2.4 Méthode dual du simplexe

Pour éviter l’utilisation des variables artificielles ,quand on a un problème avec des
contraintes
n
sous forme :
aij xj ≥ bi , i ∈ {1, ..., m}.
P
j=1
On utilise l’algorithme dual du simplexe afin de réduire la taille du (PL) et le nombre d’ité-
ration .[6]

2.4.1 Principe de la dualité

Son principe est de garder le critère d’optimalité satisfait à chaque itération et de rendre
positifs les bi qui sont négatifs.

• Au programme linéaire primal :

max Z= cT x



(P L)  Ax ≤ b

x≥0

On associe le programme linéaire dual :

minZ’= bT y



(P LD)  AT y ≥ c

y≥0

•Les différentes transformations sont résumées dans le tableau suivant :[1]

16
 Primal Dual
maxZ minZ’
coefficient c de Z second membre c
second membre b coefficient b de Z’
i-éme contrainte = yi ∈ R
i-éme contraintes ≥ yi ≥ 0
i-éme contraintes ≤ yi ≤ 0
xj ∈ R j-éme contraintes =
xj ≥ 0 j-éme contraintes ≤
xj ≤ 0 j-éme contraintes≥
• Exemple 03 :

Programme linéaire primal :





max Z= 6x1 + 4x2
3x1 + 9x2 ≤ 81




(P L) 4x1 + 5x2 ≤ 55
≤ 20




 2x1 + x2
x1 , x2 ≥ 0



On associe le programme linéaire dual :



min Z’= 81y1 + 55y2 + 20y3
3y1 + 4y2 + 2y3 ≥6


(P LD)
 9y1 + 5y2 + y3

 ≥4
y1 , y2 , y3 ≥ 0


2.4.2 L’algorithme dual du simplexe

Le principe de résolution nécessite un certain nombre d’étapes contenues au travers de
l’algorithme dual du simplexe dont la démarche est la suivante ici on l’applique pour un
problème de maximisation :

1. Écrire le système sous la forme standard avec les cj ≥ 0,∀j = 1, ..., n.

2. Construire le premier tableau correspondant à la forme standard.

3. Calculer les Ej = Zj − cj .

17
 4. Choisir la variable xr qui sort de la base :
br = min bi tq : bi < 0, i ∈ JB .
Si br n’existe pas alors fin,l’optimum est atteint.
Sinon aller à 5).

5. Choisir la variable xk qui entre dans la base :

Ek zj − cj
= max { } tq :arj < 0, j ∈ JH
ark arj
Le pivot doit être négatif, sinon fin,le (PL)est non borné.

6. Encadrer le pivot .

1
7. Multiplier la ligne du pivot par le rapport : .
ark

8. Calculer les valeurs a0ij des autres lignes :

aik ∗ arj
a0ij =aij − ( )
ark
Aller à 3).

• Exemple 04 :
On prend un exemple et on applique le dual du simplexe .

1. Écrire le système :
• Sous la forme canonique :

max Z= −2x1 − x3



x1 + x2 − x3 ≥5


(P )


 x1 − 2x2 + 4x3 ≥8
xj ≥ 0, ∀j=1..3


•Sous la forme standard :

x4 ;x5 représentent les variables d’écart.

max Z= −2x1 − x3



x1 + x2 − x3 − x4 =5


(P ) 

 x1 − 2x2 + 4x3 − x5 =8
xj ≥ 0, ∀j=1..5


• On multiplie par (-1).

max Z= −2x1 − x3



−x1 − x2 + x3 + x4 = −5


(P )


 −x1 + 2x2 − 4x3 + x5 = −8
xj ≥ 0, ∀j=1..5


2. Construire le premier tableau correspondant à la forme standard :

18
 ci -2 0 -1 0 0
cb base b x1 x2 x3 x4 x5
0 x4 -5 -1 -1 1 1 0
0 x5 -8 -1 2 -4 0 1

3. Calculer les Ej = zj − cj .

ci -2 0 -1 0 0
cb base b x1 x2 x3 x4 x5
0 x4 -5 -1 -1 1 1 0
0 x5 -8 -1 2 -4 0 1
Ej 2 0 1 0 0

4. Choisir la variable xr qui sort de la base :

br = min bi =-8.
D’où xr = x5 sort de la base(x5 qui se trouve à la 2éme ligne).

5. Choisir la variable xk qui entre dans la base :

Ek zj − cj 2 1
= max { } =} = max{ , }.
ark arj −1 −4
D’où xk = x3 entre dans la base.

6. Encadrer le pivot :

1
7. Multiplier la ligne du pivot par le rapport : :
ark
ci -2 0 -1 0 0
cb base b x1 x2 x3 x4 x5
0 x4
-1 x3 2 1/4 -1/2 1 0 -1/4

8. Calculer les valeurs des autres lignes :

aik ∗ alj
a0ij =aij − ( )
ark
Cette opération consiste à transformer aij des autres lignes en aij 0 , nous effectuons un
calcul matriciel.

ci -2 0 -1 0 0
cb base b x1 x2 x3 x4 x5
0 x4 -7 -5/4 -1/2 0 1 1/4
-1 x3 2 1/4 -1/2 1 0 -1/4

19
 Aller à l’étape 3).

•Nouveau passage :
On refait les même étapes et on aura les résultats suivants :

ci -2 0 -1 0 0
cb base b x1 x2 x3 x4 x5
0 x4 -7 -5/4 -1/2 0 1 1/4
-1 x3 2 1/4 -1/2 1 0 -1/4
Ej 7/4 1/2 0 0 1/4
x4 sort de la base.
x2 entre dans la base.

ci -2 0 -1 0 0
cb base b x1 x2 x3 x4 x5
0 x2 14 5/2 1 0 -2 -1/2
-1 x3 9 3/2 0 1 -1 -1/2
Ej 1/4 0 0 1 0
• Test d’optimalité :
Tous les bi > 0.
La solution de ce problème est :

max Z=-9
 

 x1 =0 

x2 =14
 
 
x3 =9

2.5 Conclusion
Dans ce chapitre, nous avons constaté l’efficacité des deux algorithmes :le simplexe et le
dual du simplexe à déterminer la solution optimale exacte .

20
Chapitre 3

La méthode de Séparation et
Évaluation(BRANCH AND BOUND)

3.1 Introduction
Pour plusieurs problèmes , en particulier les problèmes combinatoires,l’espace de solutions
est fini (dénombrable). Il est donc possible en principe d’énumérer toutes les solutions et
ensuite de prendre la meilleure .L’inconvénient majeur de cette approche est le temps de calcul
qui est en général énorme . La méthode de branch and bound "procédure par évaluation et
séparation" est basée sur une méthode arborescente qui consiste à réduire par des découpages
l’ensemble des solutions qui ne génèrent pas de meilleures solutions. Toutes les séparations
sont permises à condition de ne perdre aucune information. La complexité algorithmique
diminue alors dans la mesure où on ne calcule pas toutes les solutions du problème.[5]

3.2 Principe de la méthode

Il est aisé en général de déterminer l’ensemble de solutions réalisables du problème.Mais
cet ensemble est généralement trop grand pour qu’il soit possible d’en extraire la solution
optimale .En conséquence ,on procède à une subdivision de cet ensemble S en un nombre fini
(i)
de sous-ensembles Si=1...p de plus en plus petits en veillant à ce que :
p
S (i) = S
[

i=1

jusqu’à l’obtention d’un sous-problème suffisamment restreint "ensemble sondé"pour qu’on

puisse extraire la solution optimale . La méthode de branch and bound ,est essentiellement
présentée par les trois procédures suivantes :

– La procédure de séparation :

La séparation consiste à diviser le problème en sous-problèmes .

Son principe doit satisfaire aux trois règles suivantes :

a)La règle de finitude :le nombre totale de nœuds engendrés doit être fini.
b)La règle de conservation : aucune solution d’un sous-problème ne peut être éliminée

21
 par la séparation c’est-à-dire
p
S (ik) = S (i)
[

k=1

et qu’il vérifie également S (ik) ∩ S (il) = ∅ k 6= l,où S (ik) k = 1, ..., p représentent les
sous-ensembles (enfants)du sous-ensemble (parent)S (i) .
c)La Règle d’arrêt :Un nœud ou sous-ensemble terminal de l’arborescence noté S (t) est
défini comme un nœud qu’il n’est plus possible de séparer ,pour un tel sous-ensemble :
-Soit S (t) = ∅
-Soit qu’il est possible de déterminer une solution optimale du problème p(i) qui est le
sous-problème réduit de (P) et qui est défini comme suit :
(
min F (x)
P (i)
x ∈ S (i)

– La procédure d’évaluation :

L’évaluation d’un sous-problème P (i) de (P) consiste à évaluer la valeur optimale de sa

fonction économique .Plus précisément à déterminer une borne supérieure si la fonction
économique est à maximiser respectivement une borne inférieure si elle est à minimiser .
L’évaluation permet de réduire l’espace de recherche en éliminant quelques sous-ensembles
qui ne contiennent pas la solution optimale et elle a pour but de déterminer le sous
problème qu’on doit séparer.
L’exploration d’une branche est éliminée si :
a) Le sommet de l’arborescence ne peut être séparé c.à.d que le sommet(nœud)de
l’arborescence est associé à une solution entière .

b) Le sous-problème est non-réalisable .

c) La valeur de Z associée au sous-problème est supérieure à Z opt si le problème est à

maximiser respectivement inférieur à Z opt si le problème est à minimiser .

d) La valeur Z d’un sommet associée à une solution non-entière inférieure ou égale à

une valeur Z d’une solution entière respectivement supérieure pour un problème
de minimisation .
– La procédure de cheminement :

Cette procédure indique le sous-ensemble à analyser et dans quel ordre.

Bien évidemment,il est souhaitable d’examiner le moins possible de sous-problèmes
selon la stratégie choisie , certains d’entre eux pourront ne pas être séparés car, par
exemple,leurs analyse mettra en évidence qu’ils ne contiennent pas de solutions meilleures
que celles déjà trouvées .Nous dirons qu’un tel sous-ensemble ou le nœud correspondant
de l’arborescence est sondé.C’est parce que certains sous-ensembles de solutions ne de-
vront pas être examinés explicitement, que la méthode «B and B» est parfois appelée
méthode d’énumération implicite.

22
 Lorsqu’un nœud de l’arborescence est sondé,il conviendra de remonter dans l’arbores-
cence vers un autre nœud situé à un niveau inférieure ou égale .

3.2.1 Stratèges de parcours

Il est évident d’examiner la totalité des sommets de l’arborescence pour réaliser une
énumération implicite efficace .
Pour savoir quel sommet doit-on séparer on utilise des stratégies ,on peut distinguer trois
d’entre elles :
La largeur d’abord :
Cette stratégie favorise les sommets les plus proches de la racine (nœud père) en faisant moins
de séparations du problème initial. Elle est moins efficace que les deux autres stratégies .
La profondeur d’abord :
Cette stratégie avantage les sommets les plus éloignés de la racine (de profondeur la plus
élevée) en appliquant plus de séparations au problème initial. Cette voie mène rapidement à
une solution optimale en économisant la mémoire.
Le meilleur d’abord :
Cette stratégie consiste à explorer les sous-problèmes possédant la meilleure borne. Elle
permet aussi d’éviter l’exploration de tous les sous-problèmes qui possèdent une mauvaise
évaluation par rapport à la valeur optimale.

3.3 Algorithme général

X ∗ : la solution du (P ) → problème (PLNE)
X opt :la solution du (P R) → problème (PLNR)
Z ∗ : la fonction économique du (P ) → problème (PLNE)
Z opt :la fonction économique du (P R) → problème (PLNR)
1)Résolution du problème relaxé(PR) par la méthode du simplexe :
-Si X opt est entier :fin.
-Sinon, aller à 2).
2)Initialisation :
Soit Z opt obtenu dans(PR) une borne supérieure pour un problème de maximisation
respectivement (borne inférieure pour un problème de minimisation )pour (Pi ).
Soit n1 le sommet initial de l’arborescence et son ensemble(S1 = S).
Z1 = Z opt .
3)Séparation(k ième itération) :
Choisir une variable non entière xl ,créer deux branches (deux sommets fils ni+1 et ni+2 ),on
obtient deux sous-problèmes sous la forme :


 Pi+1,k :Pi + la contrainte xl ≤ [xl ]
Pi+2,k :Pi + la contrainte xl ≥ [xl ] + 1



Avec [xl ] : la partie entiére de xl

23
4)Résolution des sous-problèmes :
Résoudre chaque sous-problème en utilisant le simplexe ou le dual simplexe.
5)Évaluation :
Examiner chaque sous-ensemble :
On peux tailler un sommet si :
* La solution est non réalisable.
* Z1 ≤Z pour un problème de maximisation (Z1 ≥Z pour un problème de minimisation),
avec Z la solution du sous-problème.
* La solution est non entière et son Z inférieur ou égale à une solution entière pour un
problème de maximisation (supérieure ou égale pour un problème de minimisation) .
Il est inutile de sépare si :
* La solution est entière.
6)test :
S’il y a plus de sous-ensembles à séparer ,alors :
On compare tous les Z des solutions entières et on prend la plus grande d’entre elles soit Z ∗
pour un problème de maximisation (la plus petite pour un problème de minimisation). Elle
sera la valeur de la fonction économique de la solution optimale X ∗ de notre problème (P).
Sinon retour à 3).
Remarque :

Z ∗ ≤ Z opt pour un problème de maximisation (Z ∗ ≥ Z opt pour un problème de minimi-

sation ).
Dans l’itération 3)pour séparer les sous-problèmes on utilise l’une des stratégies cités précé-
demment.

3.4 Exemple d’application

Forme générale du problème :
 

 


max Z= x1 + 2x2
4x1 − 3x2 ≤2

 


 


(P R) −2x1 + x2 ≤1


(P )
−6x1 + 14x2 ≤ 35



 

 

  x ,x ≥ 0



 1 2
x1 , x2 ∈ N


1)Résolution du problème (PR) :

• Sa forme standard :




maxZ = x1 + 2x2
4x1 − 3x2 + x3 =2




(P R) −2x1 + x2 + x4 =1
−6x1 + 14x2 + x5 = 35





xj ≥ 0, j = 1, ..., 5.



24
• Résoudre le(PR)par la méthode du simplexe :

ci 1 2 0 0 0
cb base b x1 x2 x3 x4 x5 θ
0 x3 2 4 -3 1 0 0 /
0 x4 1 -2 1 0 1 0 1
0 x5 35 -6 14 0 0 1 35/14
Ej -1 -2 0 0 0

•x4 sort de la base.

•x2 entre dans la base.
ci 1 2 0 0 0
cb base b x 1 x2 x3 x4 x5 θ
0 x3 5 -2 0 1 3 0 /
2 x2 1 -2 1 0 1 0 /
0 x5 21 22 0 0 -14 1 21/22
Ej -5 0 0 2 0

•x5 sort de la base.

•x1 entre dans la base.
ci 1 2 0 0 0
cb base b x1 x2 x3 x4 x5 θ
0 x3 76/11 0 0 1 19/11 1/11 76/19
2 x2 32/11 0 1 0 -3/11 1/19 /
1 x1 21/22 1 0 0 -7/11 1/22 /
Ej 0 0 0 -13/11 5/22

•x3 sort de la base.

•x4 entre dans la base.
ci 1 2 0 0 0
cb base b x1 x2 x3 x4 x5 θ
0 x4 4 0 0 11/19 1 1/19 /
2 x2 4 0 1 3/19 0 2/19 /
1 x1 7/2 1 0 7/19 0 3/38 /
Ej 0 0 13/19 0 11/38

• tous les Ej ≥ 0 ⇒ X opt = (7/2, 4).

• Z opt
(=(7/2)+2(4)=23/2.
xopt =(3.5,4).
d0 ou
Z opt =11.5.
• Résolution graphique de (PR) :

25
2)Initialisation :
• Z opt est la borne supérieure de (P).
• Soit (P1 ) le problème initial (le sommet initial de l’arborescence) tel que :

Z1 =Z opt =11.5.
 

 X1 =3.5.
 

X2 =4.

(P1 ) a des variables qui ne vérifient pas les contraintes d’intégrités d’où on passe à
l’étape 3).

3)Séparation :

x1 n’est pas entier on aura le modèle linéaire courant, ici (P1 ) est divisé en deux sous-
problèmes sous la forme :
(
(P2 ) = (P1 ) + contrainte x1 ≤ [x1 ].
(P3 ) = (P1 ) + contrainte x1 ≥ [x1 ] + 1.

avec [x1 ] la partie entière de x1 .

4)Résolution des sous-problèmes :

a)On résout (P2 ) tq :

(P2 ) = (P1 )+ la contrainte x1 ≤ [x1 ] c-à-d :
(P1 )+ la contrainte x1 ≤ 3 ⇒ x1 +x6 =3......F.
On rajoute au dernier tableau de (PR)la contrainteFet on applique le dual du simplexe :

26
 ci 1 2 0 0 0 0
cb base b x1 x2 x3 x4 x5 x6
0 x4 4 0 0 11/19 1 1/19 0
2 x2 4 0 1 3/19 0 2/19 0
1 x1 7/2 1 0 7/19 0 3/38 0
0 x6 3 1 0 0 0 0 1
•x1 est une variable de base,on multiplie la 3éme ligne par(-1) , on l’additionne à la
4éme ligne . On obtient le tableau suivant :

ci 1 2 0 0 0 0
cb base b x1 x2 x3 x4 x5 x6
0 x4 4 0 0 11/19 1 1/19 0
2 x2 4 0 1 3/19 0 2/19 0
1 x1 7/2 1 0 7/19 0 3/38 0
0 x6 -1/2 0 0 -7/19 0 -3/38 1
Ej 0 0 13/19 0 11/38 0

•x6 sort de la base.

•x3 entre dans la base.
ci 1 2 0 0 0 0
cb base b x1 x2 x3 x4 x5 x6
0 x4 45/14 0 0 0 1 -1/14 11/7
2 x2 53/14 0 1 0 0 1/14 3/7
1 x1 3 1 0 0 0 0 1
0 x3 19/14 0 0 1 0 3/14 -19/7
Ej 0 0 0 0 1/7 13/7

• Tous les bj ≥ 0 ,la solution de (P2 ) est :

 
Z2 =10.57.
 X1 =3.
 

X2 =3.79.
b)On résout (P3 ) tq :
(P3 )=(P1 ) +la contrainte x1 ≥ [x1 ]+1 c-à-d :
(P1 ) +la contrainte x1 ≥ 4 ⇒ x1 -x6 =4
−x1 +x6 = −4....F.
On rajoute la contrainte F au dernier tableau de (PR)et on applique le dual simplexe :

ci 1 2 0 0 0 0
cb base b x1 x2 x3 x4 x5 x6
0 x4 4 0 0 11/19 1 1/19 0
2 x2 4 0 1 3/19 0 2/19 0
1 x1 7/2 1 0 7/19 0 3/38 0
0 x6 -4 -1 0 0 0 0 1

•x1 est une variable de base,on additionne la 3éme ligne à la 4éme ligne.On obtient le
tableau suivant :

27
 ci 1 2 0 0 0 0
cb base b x1 x2 x3 x4 x5 x6
0 x4 4 0 0 11/19 1 1/19 0
2 x2 4 0 1 3/19 0 2/19 0
1 x1 7/2 1 0 7/19 0 3/38 0
0 x6 -1/2 0 0 7/19 0 3/38 1
Ej 0 0 13/19 0 11/38 0

• Pas de pivot négatif ,(P3 ) est non-réalisable .

5)Évaluation :

•(P2 )admet une solution non-entière et la valeur de Z2 = 10.75 ≤ Z1 donc on peut

séparer le sommet S2 .
•(P3 ) non réalisable donc on taille le sommet S3 .
6) Test :

Il existe un sous-ensemble qui peut être séparé donc on retourne à 3).

• Interprétation graphique de la séparation à partir de(P1 ) :

28
3)Séparation :

x2 n’est pas entier d’où le modèle linéaire courant ici (P2 )est divisé en deux sous-problèmes
sous la forme :
(
(P4 ) = (P2 ) + contrainte x2 ≤ [x2 ].
(P5 ) = (P2 ) + contrainte x2 ≥ [x2 ] + 1.
avec [x2 ] la partie entière de x2 .

4)Résolution des sous-problèmes :

a)On résout (P4 ) tq :

(P4 ) = (P2 ) + contrainte x2 ≤ [x2 ] c-à-d :
(P2 ) + contrainte x2 ≤ 3 =⇒ x2 + x7 = 3......F.
On rajoute au dernier tableau de(P2 ) la contrainteF et on applique le dual simplexe :

ci 1 2 0 0 0 0 0
cb base b x1 x2 x3 x4 x5 x6 x7
0 x4 45/14 0 0 0 1 -1/14 11/7 0
2 x2 53/14 0 1 0 0 1/14 3/7 0
1 x1 3 1 0 0 0 0 1 0
0 x3 19/14 0 0 1 0 3/14 -19/7 0
0 x7 3 0 1 0 0 0 0 1

•x2 est une variable de base on multiplie la 2éme ligne par (-1),on l’additionne à la 5éme
ligne.On obtient le tableau suivant :

29
 ci 1 2 0 0 0 0 0
cb base b x1 x2 x3 x4 x5 x6 x7
0 x4 45/14 0 0 0 1 -1/14 11/7 0
2 x2 53/14 0 1 0 0 1/14 3/7 0
1 x1 3 1 0 0 0 0 1 0
0 x3 19/14 0 0 1 0 3/14 -19/7 0
0 x7 -11/14 0 0 0 0 -1/14 -3/7 1
Ej 0 0 0 0 1/7 13/7 0

•x7 sort de la base.

•x5 entre dans la base .
ci 1 2 0 0 0 0 0
cb base b x1 x2 x3 x4 x5 x6 x7
0 x4 4 0 0 0 1 0 2 -1
2 x2 3 0 1 0 0 0 0 1
1 x1 3 1 0 0 0 0 1 0
0 x3 -1 0 0 1 0 0 -4 3
0 x5 11 0 0 0 0 1 6 -14
Ej 0 0 0 0 0 1 2

•x3 sort de la base.

•x6 entre dans la base .
ci 1 2 0 0 0 0 0
cb base b x1 x2 x3 x4 x5 x6 x7
0 x4 7/2 0 0 1/2 1 0 0 1/2
2 x2 3 0 1 0 0 0 0 1
1 x1 11/4 1 0 1/4 0 0 0 3/4
0 x6 1/4 0 0 -1/4 0 0 1 -3/4
0 x5 19/2 0 0 3/2 0 1 0 -19/2
Ej 0 0 1/4 0 0 0 11/4

• tous les bj ≥ 0.La solution de (P4 ) est :

 
Z4 =8.75.
 X1 =2.75. 
 

X2 =3.
b)On résout (P5 ) tq : (P5 ) = (P2 )+la contrainte x2 ≥ [x2 ] +1 c-à-d :
(P2 ) +la contrainte x2 ≥ 4 =⇒ x2 − x7 = 4 =⇒ −x2 + x7 = −4......F.
on rajoute au dernier tableau de(P2 ) la contrainteF et on applique le dual simplexe :
ci 1 2 0 0 0 0 0
cb base b x1 x2 x3 x4 x5 x6 x7
0 x4 45/14 0 0 0 1 -1/14 11/7 0
2 x2 53/14 0 1 0 0 1/14 3/7 0
1 x1 3 1 0 0 0 0 1 0
0 x3 19/14 0 0 1 0 3/14 -19/7 0
0 x7 -4 0 -1 0 0 0 0 1

30
•x2 est une variable de base on additionne la 2éme ligne à la 5éme ligne.On obtient le tableau
suivant :
ci 1 2 0 0 0 0 0
cb base b x1 x2 x3 x4 x5 x6 x7
0 x4 45/14 0 0 0 1 -1/14 11/7 0
2 x2 53/14 0 1 0 0 1/14 3/7 0
1 x1 3 1 0 0 0 0 1 0
0 x3 19/14 0 0 1 0 3/14 -19/7 0
0 x7 -3/14 0 0 0 0 1/14 3/7 1
Ej 0 0 0 0 1/7 13/7 0

• Pas de pivot négatif.(P5 ) n’admet pas de solution .

5)Évaluation :
•(P4 ) a une solution non entière et la valeur de Z4 ≤ Z1 donc on peut le séparer .
•(P5 ) non réalisable donc on peut le tailler .

6)Test :
Il existe un sous-ensemble qui peut être séparé donc retour à 3).

• Interprétation graphique de la séparation à partir de (P2 ) :

31
3)Séparation :
x1 n’est pas entier d’où le modèle linéaire courant ici (P4 ) est divisé en deux sous-problèmes
sous la forme :
(
(P6 ) = (P4 ) + contrainte x1 ≤ [x1 ].
(P7 ) = (P4 ) + contrainte x1 ≥ [x1 ] + 1.
avec [x1 ] la partie entière de x1 .

4)Résolution des sous-problèmes :

a)On résout (P6 ) tq :

(P6 ) = (P4 ) + contrainte x1 ≤ [x1 ] c-à-d :
(P4 ) +la contrainte x1 ≤ 2 =⇒ x1 + x8 = 2......F.
On rajoute au dernier tableau de(P4 ) la contrainteF et on applique le dual simplexe :

ci 1 2 0 0 0 0 0 0
cb base b x1 x2 x3 x4 x5 x6 x7 x8
0 x4 7/2 0 0 1/2 1 0 0 1/2 0
2 x2 3 0 1 0 0 0 0 1 0
1 x1 11/4 1 0 1/4 0 0 0 3/4 0
0 x6 1/4 0 0 -1/4 0 0 1 -3/4 0
0 x5 19/2 0 0 3/2 0 1 0 -19/2 0
0 x8 2 1 0 0 0 0 0 0 1
•x1 est une variable de base on multiplie la 3éme ligne par (-1) et on l’additionne à la 6éme
ligne.On obtient le tableau suivant :

32
 ci 1 2 0 0 0 0 0 0
cb base b x1 x2 x3 x4 x5 x6 x7 x8
0 x4 7/2 0 0 1/2 1 0 0 1/2 0
2 x2 3 0 1 0 0 0 0 1 0
1 x1 11/4 1 0 1/4 0 0 0 3/4 0
0 x6 1/4 0 0 -1/4 0 0 1 -3/4 0
0 x5 19/2 0 0 3/2 0 1 0 -19/2 0
0 x8 -3/4 0 0 -1/4 0 0 0 -3/4 1
Ej 0 0 1/4 0 0 0 11/4 0

•x8 sort de la base.

•x3 entre dans la base.

ci 1 2 0 0 0 0 0 0
cb base b x1 x2 x3 x4 x5 x6 x7 x8
0 x4 2 0 0 0 1 0 0 -1 2
2 x2 3 0 1 0 0 0 0 1 0
1 x1 2 1 0 0 0 0 0 0 1
0 x6 1 0 0 0 0 0 1 0 -1
0 x5 5 0 0 0 0 1 0 14 6
0 x3 3 0 0 1 0 0 0 3 -4
Ej 0 0 0 0 0 0 2 1

• Tous les bj ≥ 0.La solution de (P6 ) est :

 
Z6 =8.
 X1 =2. 
 

X2 =3.

b)On résout (P7 ) telle que :

(P7 ) = (P4 )+ la contrainte x1 ≥ [x1 ] +1 c-à-d :
(P4 )+ la contrainte x1 ≥ 3 =⇒ x1 − x8 = 3 =⇒ −x1 + x8 = −3......F.
On rajoute au dernier tableau de(P4 ) la contrainte F et on applique le dual simplexe :

ci 1 2 0 0 0 0 0 0
cb base b x1 x2 x3 x4 x5 x6 x7 x8
0 x4 7/2 0 0 1/2 1 0 0 1/2 0
2 x2 3 0 1 0 0 0 0 1 0
1 x1 11/4 1 0 1/4 0 0 0 3/4 0
0 x6 1/4 0 0 -1/4 0 0 1 -3/4 0
0 x5 19/2 0 0 3/2 0 1 0 -19/2 0
0 x8 -3 -1 0 0 0 0 0 0 1

•x1 est une variable de base d’où on additionne la 3éme ligne à la 6éme ligne.On obtient le
tableau suivant :

33
 ci 1 2 0 0 0 0 0 0
cb base b x1 x2 x3 x4 x5 x6 x7 x8
0 x4 7/2 0 0 1/2 1 0 0 1/2 0
2 x2 3 0 1 0 0 0 0 1 0
1 x1 11/4 1 0 1/4 0 0 0 3/4 0
0 x6 1/4 0 0 -1/4 0 0 1 -3/4 0
0 x5 19/2 0 0 3/2 0 1 0 -19/2 0
0 x8 -1/4 0 0 1/4 0 0 0 3/4 1
Ej 0 0 1/4 0 0 0 11/4 0

• Pas de pivot négatif .(P7 ) non-réalisable.

5)évaluation :
• On a (P6 ) a une solution entière et son Z6 ≤ Z1 donc inutile de le séparer.
• On a (P7 ) non réalisable donc on peut le tailler.
6)Test :
Il n’y a plus de sous-ensembles à séparer alors on compare tous les Z des solutions entières et
on prend la plus grande car on a un problème de maximisation .Ici on a Z6 = 8 est la seule
qui a une solution entière .
D’où la solution de notre problème est :
X ∗ =(2,3)et son Z ∗ = 8.

34
• Interprétation graphique de la séparation à partir de (P4 ) :

35
Remarque :
On a utilisé la stratégie :
Le meilleur d’abord.

• En utilisant Matlab 2014 :

Le problème correspondant est le suivant :
f=[-1 ;-2 ;0 ;0 ;0] ;
Aeq=[4 -3 1 0 0 ; -2 1 0 1 0 ; -6 14 0 0 1] ;
beq=[2 ;1 ;35] ;
ub=[Inf ;Inf ;Inf ;Inf ;Inf] ;
lb=[0 ;0 ;0 ;0 ;0] ;
intcon=[1,2] ;
x=intlinprog(f,intcon,[ ],[ ],Aeq,beq,ub,lb) ;
Le résultat obtenu par ce programme est :

36
 • En utilisant( LP Solve IDE) :
Le problème correspondant est le suivant :

/* objective function */
max :x1 +2x2 ;
/* Variable bounds */
4x1 − 32 + x3 = 2 ;
-2x1 + x2 + x4 =1 ;
-6x1 + 14x2 + x5 = 35;
x3 >= 0 ;
x4 >= 0 ;
x5 >= 0 ;
int x1 ,x2 ;

Le résultat obtenu par ce programme est :

37
3.5 Conclusion
Dans ce chapitre nous nous sommes intéressés à la résolution des programmes linéaires
en nombres entiers avec la méthode de Séparation et d’Évaluation "Branch and Bound "qui
se repose sur le principe d’énumération.
Son efficacité est liée directement au principe d’élagage qui permet de diminuer l’espace de

38
recherche des solutions.

P6 : Z6 =8
X1 =2
X2 =3

39
Conclusion générale

Quelques problèmes de la vie courante peuvent être modélisés comme des problèmes
combinatoires .
Dans notre travail,on a présenté un état de l’art des méthodes de résolutions des problèmes
de programmation linéaire en nombres entiers .
On a défini les concepts de base de la programmation linéaire ensuite on a présenté la méthode
Branch and Bound en appliquant un exemple numérique.
Nous espérons que ce travail sera utile pour tous ceux qui sont concernés par le développement
des systèmes de programmation linéaire, de modélisation et d’optimisation.

40
Bibliographie

[1] Aidene M. Oukacha B., « les manuels de l’étudiant Recherche Opérationnelle, Program-
mation Linéaire ». Copyright Eurl Pages Bleues internationales, Maison d’Edition pour
l’enseignement et la formation, 2005.
[2] Amira Gherboudj ,thèse pour l’obtention du diplôme de Doctorat 3éme cycle LMD Spé-
cialité informatique,2013.
[3] Dantzig ,Linear programming and extensions, Princeton University Press, Princeton,
1963.
[4] Jaques Teghem,RECHERCHE OPÉRATIONNELLE TOME 1,Septembre 2012.
[5] Land A.H., Doig A.G., An automatic method of solving discrete programming problems
, Econometrica 28 (3), 497-520, 1960.
[6] Lemke C.E., « The dual method for solving the linear programming problem », Naval
Research Logistic Quarterly 1, 36-47, 1954.
[7] P.Fouilhoux,Programmation mathématique discrète et modèle linéaire ,Université Pierre
et Marie Cunie ,2012.
[8] Yves Nobert , Roch Ouellet,Régis parent,La recherche opérationnelle3e édition,2001.

41