Cours Plne

USTHB-Info |2024
Programmation linéaire en variables

entières et mixtes (PLNE/PLNM)
Par:
Dr. Kerkache Med Hassen
Formulation des programmes linéaires en nombre entier
Objectifs:
• Comprendre les bases de la PLNE.
• Identifier les différences entre programmation linéaire
classique et PLNE.
• Explorer les applications typiques de la PLNE
2
Introduction à la Programmation Linéaire en Nombres Entiers
Définition : La PLNE est une branche des mathématiques et de l'informatique qui consiste
à optimiser (maximiser ou minimiser) une fonction linéaire sous un ensemble de
contraintes linéaires, tout en imposant que certaines ou toutes les variables de décision
prennent des valeurs entières.
En d'autres termes la PLNE est particulièrement utile lorsque :

• Fonction Objectif linéaire: On cherche la meilleure solution (maximale ou minimale)
parmi toutes les solutions possibles.
• Contraintes linéaires: Les relations entre les variables sont exprimées sous forme
d'équations ou d'inéquations linéaires.
• Variables en nombres entiers: Certaines ou toutes les variables ne peuvent prendre
que des valeurs entières (0, 1, 2, ...N), contrairement à la programmation linéaire
classique où les variables peuvent prendre n'importe quelle valeur réelle.
3
Pourquoi la PLNE ?
La PLNE est particulièrement utile pour modéliser des problèmes réels où les solutions
ne peuvent être fractionnées, comme :
Planification des trains.
• Certains horaires de train se répètent toutes les heures.
• Les temps de parcours entre les gares sont connus et le temps passé dans une gare
doit être inclus dans un intervalle de temps donné.
• Deux trains sur la même ligne doivent être séparés d'au moins un certain nombre de
minutes.
• La différence entre l'heure d'arrivée et l'heure de départ doit être suffisamment
longue pour que les passagers puissent changer de train, mais suffisamment courte
pour ne pas dépasser le temps d'attente.
• Le défi consiste à trouver un planning réalisable.
4
Pourquoi la PLNE ?
La PLNE est particulièrement utile pour modéliser des problèmes réels où les solutions ne
peuvent être fractionnées, comme :
Planification de la production:
• Réunion mensuelle de planification d'une multinationale pour l’élaboration d'un plan
de production et d'expédition sur trois mois sur la base des estimations de ventes.
• Couvre 200 à 400 produits répartis dans cinq usines.
• Expédition vers 50 zones de vente.
• Solutions générées sur place, nécessitant un temps de calcul de 15 minutes.
• Quantité de production minimale par produit.
• Production par lots pour maximiser la contribution.
5
Pourquoi la PLNE ?
La PLNE est particulièrement utile pour modéliser des problèmes réels où les solutions ne
peuvent être fractionnées, comme :
Télécommunications:
• Problème d'installation de transmission de données, de voix et de vidéo
• L'explosion de la demande nécessite l'installation de nouvelles capacités.
• L'estimation des besoins, de la capacité existante et des coûts de la nouvelle capacité
est cruciale.
• La minimisation des coûts est cruciale compte tenu des défaillances potentielles des
lignes ou des centres dues à des pannes ou à des accidents.
6
Formulation mathématique:
7
Exemple:
Considérons le programme en nombres entiers :
8
Exemple:
Considérons le programme en nombres entiers :
Comme le montre la figure , la solution

376 950
de programmation linéaire ( 193 , 193 )
est très éloignée de la solution
optimale en nombres entiers (5, 0).
9
Types de PLNE
Si certaines variables, mais pas toutes, sont entières, nous avons un:
Programme (linéaire) en nombres entiers mixtes, écrit sous la forme suivante:
Où:
• A est une matrice m × 𝑛, G est m × 𝑝,
• c est un vecteur à n lignes,
• h est un vecteur à p lignes,
• x est un vecteur à n colonnes de variables entières,
• et y est un vecteur à p colonnes de variables réelles.
10
Types de PLNE
Si toutes les variables sont limitées à des valeurs de 0 ou 1, nous avons un:
0-1 PL ou Programme Linéaire de nombres entiers binaires, écrit sous la forme suivante:
Où:
• A est une matrice m × 𝑛
• c est un vecteur à n lignes,
• b un vecteur colonne à m colonnes,
• x est un vecteur à n colonnes de variables entières {0, 1}
11
Exemples de (PLNE)
Problème du Sac à Dos
Énoncé : On dispose d'un ensemble d'objets, chacun ayant un poids et une valeur. Le but
est de maximiser la valeur totale des objets choisis sans dépasser une capacité maximale.
Formulation mathématique :
12
Exemples de (PLNE)
Problème du Sac à Dos
Modèle :
13
Exemples de (PLNE)
Problème d'Affectation
Énoncé : On doit affecter un ensemble de tâches à un ensemble d’agents, de manière à
minimiser le coût total d’affectation ou à maximiser l’efficacité, en respectant des
contraintes de capacité ou de disponibilité.
14
Exemples de (PLNE)
Problème d'Affectation
Modèle :
Sous
contraintes :
15
Exemples de (PLNE)
Problème du Voyageur de Commerce (TSP)
Énoncé : Un voyageur doit visiter un ensemble de villes exactement une fois, en
minimisant la distance totale parcourue. Il doit retourner à sa ville de départ après avoir
visité toutes les autres.
16
Exemples de (PLNE)
Problème du Voyageur de Commerce (TSP)
Modèle :
17
Optimisation combinatoire
Problème d'optimisation combinatoire:

Un problème d'optimisation combinatoire consiste à trouver la meilleure solution
parmi un ensemble fini (mais potentiellement très grand) de solutions possibles.
Caractéristiques principales:
• Ensemble discret de solutions: Les solutions ne peuvent prendre que certaines
valeurs spécifiques (entiers, booléens), et non toutes les valeurs réelles.
• Fonction objectif: C'est la quantité que l'on cherche à optimiser (maximiser ou
minimiser).
• Contraintes: Ce sont les règles que les solutions doivent respecter.
18
Optimisation et complexité
Explosion combinatoire:
Les trois problèmes que nous avons examinés jusqu'à présent sont tous combinatoires
dans le sens où la solution optimale est un sous-ensemble d'un ensemble fini. En
principe, ces problèmes peuvent donc être résolus par énumération. Pour savoir pour
quelle taille d'instances de problèmes cette approche est réalisable, nous devons
compter le nombre de solutions possibles.
• Le problème de Sac à dos (Knapsack):

le nombre de sous-ensembles est de 2𝑛 . Pour le problème du sac à dos avec
b = σ𝑛𝑗=1 𝑎𝑗 /2, au moins la moitié des sous-ensembles sont réalisables et il y a
donc au moins 2𝑛−1 sous-ensembles réalisables.
19
Le problème d’affectation:
Si nous avons n taches, il y a n ! (n factoriel) façons de les disposer parmi les agents. En
effet, chaque permutation représente une solution, donc:
• En effet, pour la première tâche, il y a n choix d'agent.
• Pour la deuxième tâche, il reste n-1 choix possibles.
• Ainsi, le nombre total de permutations (et donc le nombre d'affectations possibles)
est:
n * (n-1) * (n-2) * ... * 1 = n !.
20
Le problème de voyageurs de commerce (TSP):

En commençant par la ville 1, le vendeur a n - 1 choix. Pour le choix suivant, n - 2 villes
sont possibles, et ainsi de suite. Il y a donc (n - 1) ! tournées possibles.
Dans le tableau, nous montrons la rapidité avec laquelle certaines fonctions

progressent. Ainsi, un problème de voyageur de commerce (TSP) avec n = 101
comporte environ 9,33 × 10157 tours.
21
Optimalité, relaxation et bornes
Objectifs:
• Comprendre les conditions d’optimalités.
• Les bornes et la relaxation.
22
Optimalité
Étant donné un PLNE ou un problème d’OC:
La question porte sur la démonstration de l'optimalité d'un point 𝑥 ∗ , et plus précisément

sur la recherche de conditions d'optimalité qui servent de critères d'arrêt dans un
algorithme PLNE.
La réponse « naïve » mais néanmoins importante est que nous devons trouver une limite
inférieure 𝑍 ≤ 𝑍 et une limite supérieure 𝑍 ≥ 𝑍 telle que 𝑍 = 𝑍 = 𝑍.
En pratique, cela signifie que n'importe quel algorithme trouvera une séquence
décroissante:
de bornes supérieures,
23
Optimalité
et une séquence croissante
de bornes inférieures, et s'arrêter lorsque
où 𝜖 est une petite valeur non négative convenablement choisie. Nous

devons donc trouver des moyens de dériver de telles limites
supérieures et inférieures.
24
Optimalité
Bornes primales:
Chaque solution réalisable x ∗ ∈ X fournit une borne inférieure Z = c(x ∗ ) ≤ Z. C'est

essentiellement la seule façon que nous connaissons d'obtenir des bornes inférieures.
Pour certains problèmes de PLNE, il est facile de trouver des solutions réalisables (TSP), et
la vraie question est de savoir comment trouver de bonnes solutions.
Pour d'autres PLNE, il peut être très difficile de trouver des solutions réalisables (aussi
difficiles que le PLNE lui-même).
25
Optimalité
Bornes duales:
La recherche de bornes supérieures pour un problème de maximisation (ou de bornes
inférieures pour un problème de minimisation) présente un défi différent. Ces bornes sont
appelées bornes duales.
L'approche la plus importante est la « relaxation », l'idée étant de remplacer un problème

d'optimisation max(min) « difficile » par un problème d'optimisation plus simple dont la
valeur optimale est au moins aussi grande (petite) que Z.
Pour que le problème « relaxé » ait cette propriété, il y a deux possibilités évidentes :
• Élargir l'ensemble des solutions réalisables afin d'optimiser sur un plus grand
ensemble, ou
• Remplacer la fonction objective max(min) par une fonction qui a la même valeur ou
une valeur plus grande (plus petite) sur toutes les solutions réalisables d'origine.
26
Relaxation
Définition : Un problème (PR) Z PR = max { f(x) ∶ x ∈ T ⊆ Rn } est une relaxation de (PLNE)

Z = max { c(x) ∶ x ∈ X ⊆ Z n } si:
• X ⊆ T, et
• (x) ≥ c(x) pour tout x ∈ X.
Proposition : Si PR (problème relaxé) est une relaxation de PLNE, Z PR ≥ Z.
La question se pose alors de savoir comment construire des relaxations intéressantes.

L'une des plus utiles et des plus naturelles est la relaxation d’un programme linéaire.
27
Relaxation d’un programme linéaire
Définition : Pour le programme en nombres entiers Z = max{cx ∶ x ∈ P ∩ Z n } avec la

formulation P = {x ∈ Rn+ ∶ Ax ≤ b}, la relaxation de programmation linéaire est le
programme linéaire Z PL = max{cx ∶ x ∈ P}.
Comme P ∩ Z n ⊆ P et que la fonction objective est inchangée, il s'agit clairement d'une

relaxation.
Exemple : Considérons le programme entier (PLNE)
28
Relaxation de la programmation linéaire
Pour obtenir une borne primale (inférieure), observons que (2, 1) est une solution
réalisable, nous avons donc la borne inférieure Z ≥ 7.
Pour obtenir une borne duale (supérieure), considérons la relaxation de programmation
linéaire. La solution optimale est x ∗ = (20
7
, 3) avec la valeur Z PL = 59.
7
59
On obtient donc une borne supérieure Z ≤ 7 . En observant que la valeur optimale doit
être entière, on peut arrondir à l'entier inférieur et ainsi obtenir Z ≤ 8.
29
30
31
Proposition :
• Si une relaxation PR est infaisable, le problème original PLNE est infaisable.
• Soit x ∗ une solution optimale de RP. Si x ∗ ∈ X et f(x ∗ ) = c(x ∗ ), alors x ∗ est une solution
optimale du PLNE.
a pour solution optimale x ∗ = (1, 1, 0, 0). Comme x ∗ est intégral, il résout le programme
en nombres entiers.
32
Relaxation lagrangienne:
La relaxation lagrangienne est une technique utilisée pour résoudre des problèmes
d'optimisation difficiles, en particulier ceux impliquant des contraintes compliquées.
Elle repose sur l'idée de simplifier le problème en "relaxant" certaines contraintes en les
intégrant directement dans la fonction objectif, moyennant des multiplicateurs appelés
multiplicateurs de Lagrange.
33
34
35
36
37
4. Propriétés et avantages
• Borne supérieure : La relaxation lagrangienne fournit une borne supérieure (dans le

cas de la maximisation) sur la valeur optimale du problème original. Cela est utile
dans les algorithmes de type Branch and Bound.
• Simplification : Le problème relaxé est souvent plus simple à résoudre, car les
contraintes difficiles sont remplacées par des termes dans la fonction objectif.
• Flexibilité : On peut choisir les contraintes à relaxer en fonction de leur complexité.
38
Branch and Bound
Objectifs:
• Trouver la solution optimale entière.
• Réduire l’espace de recherche.
• Utiliser les relaxations continues pour guider la
recherche.
• S’adapter à divers types de problèmes.
39
Introduction
Définition : La méthode Branch and Bound (B&B) est une technique algorithmique
utilisée pour résoudre les problèmes d'optimisation combinatoire, notamment en
programmation linéaire en nombres entiers (PLNE).
Les algorithmes de Branch and Bound sont largement considérés comme les méthodes
les plus efficaces pour résoudre les problèmes de programmation générale en nombres
entiers de taille moyenne.
Ces algorithmes ne font aucune hypothèse sur la structure d'un problème, si ce n'est que
la fonction objective et les contraintes doivent être linéaires.
Même ces restrictions peuvent être assouplies sans modifier le cadre de base de la
technique.
40
Introduction
Dans sa forme la plus simple, le Branch-and-Bound est simplement une manière

organisée de prendre un problème difficile et de le diviser en deux ou plusieurs sous-
problèmes plus petits (et donc plus faciles).
Si ces sous-problèmes sont encore trop difficiles, nous procédons à un nouveau

branchement et subdivisons encore les problèmes.
Lorsque l'approche Branch and Bound est appliquée à un problème de programmation
linéaire en nombres entiers, elle est utilisée en conjonction avec l'approche normale de la
solution en nombres non entiers
Le processus est répété jusqu'à ce que chaque sous-problème puisse être facilement
résolu. Le branchement est effectué de telle sorte que la résolution de chaque sous-
problème (et la sélection de la meilleure réponse trouvée) équivaut à la résolution du
problème d'origine.
41
Branch and Bound: Principe de base
Principes de base
1. Division de l’espace de recherche ("Branching") :

• Le problème initial est décomposé en sous-problèmes en fixant une ou plusieurs
variables à des valeurs spécifiques.
• Cela crée une arborescence de sous-problèmes à explorer.
2. Calcul de bornes ("Bounding") :

• Chaque sous-problème est résolu en le relaxant (par exemple, en retirant les
contraintes d'intégralité).
• La solution relaxée fournit une borne supérieure (si c'est un problème de
maximisation) ou une borne inférieure (si c'est un problème de minimisation).
• Si cette borne indique que le sous-problème ne peut pas contenir une meilleure
solution que celle déjà trouvée, il est éliminé.
42
Principes de base
3. Élagage de l’arborescence ("Pruning"):

• Si un sous-problème est éliminé (parce qu’il est inutile ou infructueux), l’algorithme
n’explore pas ses descendants.
• Cela réduit considérablement l’espace de recherche.
4. Solution optimale :
• L’algorithme termine lorsque tous les sous-problèmes sont soit explorés, soit
éliminés.
• La meilleure solution entière rencontrée pendant le processus est déclarée comme
solution optimale.
43
Diviser pour régner :

Considérons le problème :
Comment pouvons-nous décomposer le problème en une série de problèmes plus petits

et plus faciles à résoudre, résoudre les problèmes plus petits et ensuite rassembler les
informations pour résoudre le problème d'origine ?
Proposition : Soit S = 𝑆1 ∪ ⋯ ∪ 𝑆𝑘 une décomposition de S en ensembles plus petits, et

soit Z k = max{𝑐𝑥: 𝑥 ∈ 𝑆𝑘 } pour k = 1,..., K. Alors Z = maxk Z k .
44
Un arbre d'énumération est une façon typique de représenter une telle approche
« diviser pour régner ». Par exemple, si S ⊆ {0, 1}3 , nous pouvons construire l'arbre
d'énumération illustré à la figure suivante :
45
Énumération implicite :
Nous avons vu que l'énumération complète est totalement impossible pour la plupart des
problèmes dès que le nombre de variables dans un programme en nombres entiers ou de
nœuds dans un graphe dépasse 20 ou 30. Nous devons donc faire plus que diviser
indéfiniment.
• Comment pouvons-nous utiliser intelligemment certaines limites sur les valeurs de

{Z k }?
• Tout d'abord, comment pouvons-nous rassembler des informations sur les bornes ?
k
Notez que, comme nous maximisons, nous prenons 𝑍 = -∞ lorsque 𝑆𝑘 = ∅ et 𝑍 k = -∞
lorsqu'aucune solution réalisable dans 𝑆𝑘 n'a été trouvée.
46
Proposition : Soit S = 𝑆1 ∪ ⋯ ∪ 𝑆𝑘 une décomposition de S en ensembles plus petits, et

k
soit Z k = max{𝑐𝑥: 𝑥 ∈ 𝑆𝑘 } pour k = 1,..., K, 𝑍 une borne supérieure sur Z k et 𝑍 k une
k
borne inférieure sur Z k . Alors 𝑍 = maxk 𝑍 est une borne supérieure de Z et 𝑍 = maxk
𝑍 k est une borne inférieure de Z.
Nous allons maintenant examiner trois exemples hypothétiques pour voir comment les
informations sur les bornes ou les informations partielles sur un sous-problème peuvent
être utilisées.
Que peut-on déduire des bornes inférieures et supérieures de la valeur optimale Z et
quels ensembles doivent être examinés plus en détail pour trouver la valeur optimale ?
47
Exemple 01 : nous montrons une décomposition de S en deux ensembles S1 et S2 ainsi

que des bornes supérieures et inférieures sur les problèmes correspondants.
Nous notons tout d'abord que

k
𝑍 = maxk 𝑍 = max{20, 25} = 25
et 𝑍 = maxk = max {20, 15} = 20. Il
s'agit clairement d'une amélioration
par rapport aux limites inférieure et
supérieure initiales de 13 et 27,
respectivement.
Deuxièmement, nous observons que les bornes inférieure et supérieure de 𝑍1 étant

égales, 𝑍1 = 20, il n'y a plus de raison d'examiner l'ensemble S1. Par conséquent, la
branche S1 de l'arbre d'énumération peut être élaguée par optimalité.
48
Exemple 02 : nous décomposons à nouveau S en deux ensembles S1 et S2 et montrent les

bornes supérieures et inférieures pour les problèmes correspondants.
Nous notons d'abord que

k
𝑍 = maxk 𝑍 = max{20, 26} = 26
et 𝑍 = maxk = max {18, 21} = 21.
Deuxièmement, nous observons que, comme la valeur optimale a une valeur d'au
1
moins 21 et que la borne supérieure 𝑍 = 20, aucune solution optimale ne peut se
trouver dans l'ensemble S1. Par conséquent, la branche S1 de l'arbre d'énumération
peut être élaguée par la borne.
49
Exemple 03 : nous décomposons à nouveau S en deux ensembles S1 et S2 avec

différentes bornes supérieures et inférieures.
Nous notons d'abord que

k
𝑍 = maxk 𝑍 = max{24, 37} = 37
et 𝑍 = maxk = max {13, −∞} = 13.
Ici, aucune autre conclusion ne peut être tirée et nous devons explorer davantage les
deux ensembles S1 et S2.
50
Sur la base de ces exemples, nous pouvons énumérer au moins trois raisons qui
permettent d'élaguer l'arbre et donc d'énumérer un grand nombre de solutions de
manière implicite.
1. Élagage par optimalité : Z t = max{𝑐𝑥: 𝑥 ∈ 𝑆𝑡 } a été résolu.

2. Élagage par la borne : Z t ≤ 𝑍 .
3. Élagage par infaisabilité : St = 𝜙.
Si nous demandons maintenant comment les bornes doivent être obtenues.

Les bornes primaires (inférieures) sont fournies par les solutions réalisables et les bornes
duales (supérieures) par la relaxation ou la dualité.
51
Procédure Branch & Bound
Les étapes de la méthode Branch and Bound pour déterminer une solution optimale en
nombres entiers pour un modèle de maximisation (avec des contraintes ≤) peuvent être
résumées comme suit:
1. Trouver la solution optimale du modèle de programmation linéaire avec les restrictions en

nombres entiers relaxées.
2. Au nœud 1, la solution relaxée est la borne supérieure et la solution entière arrondie est la
borne inférieure.
3. Sélectionnez la variable dont la partie fractionnaire est la plus grande pour le branchement.
Créer deux nouvelles contraintes pour cette variable reflétant les valeurs entières partitionnées.
Le résultat sera une nouvelle contrainte ≤ et une nouvelle contrainte ≥.
4. Créer deux nouveaux nœuds, l'un pour la contrainte ≤ et l'autre pour la contrainte ≥.
5. Résoudre le modèle de programmation linéaire relaxé avec la nouvelle contrainte ajoutée à
chacun de ces nœuds.
6. La solution relaxée est la borne supérieure à chaque nœud, et la solution maximale en nombres
entiers existante (à n'importe quel nœud) est la borne inférieure.
52
Procédure Branch & Bound
Les étapes de la méthode Branch and Bound pour déterminer une solution optimale en
nombres entiers pour un modèle de maximisation (avec des contraintes ≤) peuvent être
résumées comme suit:
7. Si le processus produit une solution en nombres entiers réalisable dont la borne supérieure est
la plus élevée de tous les nœuds finaux, la solution en nombres entiers optimale a été atteinte.
Si aucune solution réalisable en nombres entiers n'est trouvée, il faut passer au nœud dont la
borne supérieure est la plus élevée.
8. Retourner au point 3.
Pour un modèle de minimisation, les solutions relaxées sont arrondies à l'unité supérieure, et les
bornes supérieures et inférieures sont inversées
53
Branch & Bound
Exemple:
• Le propriétaire d'un atelier d'usinage envisage de se développer en achetant de
nouvelles machines, des presses et des tours.
• Le propriétaire a estimé que chaque presse achetée augmentera ses bénéfices de
100$ par jour et que chaque tour augmentera ses bénéfices de 150$ par jour.
• Le propriétaire dispose d'un budget de 40 000$ pour l'achat de machines et d'une
surface disponible de 200 m².
• Le propriétaire souhaite savoir combien de machines de chaque type il doit acheter
pour maximiser l'augmentation quotidienne de ses bénéfices.
Machine Surface de plancher Prix d'achat

requise (m²)
Presse 15 8000$
Tour 30 4000$
54
Branch & Bound
Exemple:
𝑥1 : nombre de presses.
𝑥2 : nombre de tours.
Maximiser Z = 100 𝑥1 + 150 𝑥2

Sous contraintes:
8000 𝑥1 + 4000 𝑥2 ≤ 40 000
15 𝑥1 + 30 𝑥2 ≤ 200
𝑥1 , 𝑥2 ≥ 0 et entiers.
Nous commençons la méthode Branch and Bound en résolvant d'abord le problème

comme un modèle de programmation linéaire régulier sans restrictions sur les nombres
entiers (c'est-à-dire que les restrictions sur les nombres entiers sont relaxées).
55
Branch & Bound
Exemple:
56
Branch & Bound
Exemple:
une borne supérieure - la valeur Z de la solution

relaxée
La solution optimale en
nombres entiers se situera
entre ces deux bornes.
La limite inférieure est la valeur Z de la solution

arrondie à la baisse.
57
Branch & Bound
Exemple:
Voir laquelle est la plus éloignée

de la valeur entière arrondie
(c'est-à-dire quelle variable a la
plus grande partie fractionnaire).
La partie 0,56 de 5,56 est la partie

fractionnaire la plus grande ;
x2 sera donc la variable sur
laquelle nous allons « brancher ».
58
Branch & Bound
Exemple:
Max Z = 100 𝒙𝟏 + 150 𝒙𝟐 Max Z = 100 𝒙𝟏 + 150 𝒙𝟐

S. C: S. C:
8000 𝒙𝟏 + 4000 𝒙𝟐 ≤ 40 000 8000 𝒙𝟏 + 4000 𝒙𝟐 ≤ 40 000
15 𝒙𝟏 + 30 𝒙𝟐 ≤ 200 15 𝒙𝟏 + 30 𝒙𝟐 ≤ 200
𝒙𝟐 ≤ 5 𝒙𝟐 ≥ 6
𝒙𝟏 , 𝒙𝟐 ≥ 0 𝒙𝟏 , 𝒙𝟐 ≥ 0
59
Branch & Bound
60
Branch & Bound
Exemple:
• Comme nous ne disposons pas encore d'une solution optimale et réalisable en

nombres entiers, nous devons continuer à brancher (c'est-à-dire à partitionner) le
modèle, à partir du nœud 2 ou du nœud 3.
• En général, il faut toujours partir du nœud dont la borne supérieure est la plus élevée.
61
Branch & Bound
Exemple:
Max Z = 100 𝒙𝟏 + 150 𝒙𝟐 Max Z = 100 𝒙𝟏 + 150 𝒙𝟐

S. C: S. C:
8000 𝒙𝟏 + 4000 𝒙𝟐 ≤ 40 000 8000 𝒙𝟏 + 4000 𝒙𝟐 ≤ 40 000
15 𝒙𝟏 + 30 𝒙𝟐 ≤ 200 15 𝒙𝟏 + 30 𝒙𝟐 ≤ 200
𝒙𝟐 ≥ 6 𝒙𝟐 ≥ 6
𝒙𝟏 ≤ 1 𝒙𝟏 ≥ 2
𝒙𝟏 , 𝒙𝟐 ≥ 0 𝒙𝟏 , 𝒙𝟐 ≥ 0
62
Branch & Bound
Exemple:
Nœud 5:
Max Z = 100 𝒙𝟏 + 150 𝒙𝟐

S. C:
8000 𝒙𝟏 + 4000 𝒙𝟐 ≤ 40 000
15 𝒙𝟏 + 30 𝒙𝟐 ≤ 200
𝒙𝟐 ≥ 6
𝒙𝟏 ≥ 2
𝒙𝟏 , 𝒙𝟐 ≥ 0
Pas de solution
63
Branch & Bound
Exemple:
Nœud 4:
Max Z = 100 𝒙𝟏 + 150 𝒙𝟐

S. C:
8000 𝒙𝟏 + 4000 𝒙𝟐 ≤ 40 000
15 𝒙𝟏 + 30 𝒙𝟐 ≤ 200
𝒙𝟐 ≥ 6
𝒙𝟏 ≤ 1
𝒙𝟏 , 𝒙𝟐 ≥ 0
Solution optimale :
x1 = 1.0 , x2 = 6.166666666666667
Valeur optimale (Z) = 1025.0
64
Branch & Bound
On va continuer
de brancher sur
le nœud 4 en
résolvant ses
deux problèmes.
65
Branch & Bound
66
Branch & Bound
Max Z = 100 𝒙𝟏 + 150 𝒙𝟐 Max Z = 100 𝒙𝟏 + 150 𝒙𝟐

S. C: S. C:
8000 𝒙𝟏 + 4000 𝒙𝟐 ≤ 40 000 8000 𝒙𝟏 + 4000 𝒙𝟐 ≤ 40 000
15 𝒙𝟏 + 30 𝒙𝟐 ≤ 200 15 𝒙𝟏 + 30 𝒙𝟐 ≤ 200
𝒙𝟐 ≥ 6 𝒙𝟐 ≥ 7
𝒙𝟐 ≤ 6 𝒙𝟏 ≤ 1
𝒙𝟏 ≤ 1 𝒙𝟏 , 𝒙𝟐 ≥ 0
𝒙𝟏 , 𝒙𝟐 ≥ 0 67
Branch & Bound
Exemple:
Nœud 6:
Max Z = 100 𝒙𝟏 + 150 𝒙𝟐

S. C:
8000 𝒙𝟏 + 4000 𝒙𝟐 ≤ 40 000
15 𝒙𝟏 + 30 𝒙𝟐 ≤ 200
𝒙𝟐 = 6
𝒙𝟏 ≤ 1
𝒙𝟏 , 𝒙𝟐 ≥ 0
Solution optimale :
x1 = 1 , x2 = 6
Valeur optimale (Z) = 1000
68
Branch & Bound
Exemple:
Nœud 7:
Max Z = 100 𝒙𝟏 + 150 𝒙𝟐

S. C:
8000 𝒙𝟏 + 4000 𝒙𝟐 ≤ 40 000
15 𝒙𝟏 + 30 𝒙𝟐 ≤ 200
𝒙𝟐 ≥ 7
𝒙𝟏 ≤ 1
𝒙𝟏 , 𝒙𝟐 ≥ 0
Pas de solution
69
Branch & Bound
On arrête car on
a obtenu une
solution entière.
Cette solution
est optimale
pour le PLNE.
Fin de
l’algorithme
70
Branch & Bound avec simplexe
On considère le programme suivant:

Max z = 13 x1 + 8 x2
x1 + 2 x2 ≤ 10
5 x1 + 2 x2 ≤ 20
x1 , x 2 ∈ 𝑁
La forme standard est :

Max z = 13 x1 + 8 x2
x1 + 2 x2 + 𝑒1 = 10
5 x1 + 2 x2 + 𝑒2 = 20
x1 , x2 , 𝑒1 , 𝑒2 ≥ 0
71
Max 𝑪𝒊 13 8 O 0
Max z = 13 x1 + 8 x2
𝑪𝑩 B b 𝐱𝟏 𝐱𝟐 𝒆𝟏 𝒆𝟐
x1 + 2 x2 + 𝑒1 = 10
5 x1 + 2 x2 + 𝑒2 = 20 𝟎 𝒆𝟏 10 1 2 1 0
x1 , x2 , 𝑒1 , 𝑒2 ≥ 0 𝟎 20 5 2 0 1
𝒆𝟐
𝒁𝒊 0 0 0 0 0
Tableau initial
𝑪𝒊 - 𝒁 𝒊 13 8 0 0
𝟎 𝒆𝟏 6 0 𝟓ൗ 1 −𝟏ൗ
Itération 1 𝟖 𝟓
𝟏𝟑 𝒙𝟏 4 1 𝟐ൗ 0 𝟏ൗ
𝟓 𝟓
𝒁𝒊 0 13 𝟐𝟔ൗ 0 𝟏𝟑ൗ
𝟓 𝟓
𝑪𝒊 - 𝒁 𝒊 0 𝟏𝟒ൗ 0 −𝟏𝟑ൗ 72
𝟓 𝟓
Max z = 13 x1 + 8 x2
x1 + 2 x2 + 𝑒1 = 10
5 x1 + 2 x2 + 𝑒2 = 20 𝟎 𝒆𝟏 6 0 𝟓ൗ 1 −𝟏ൗ
𝟖 𝟓
x1 , x2 , 𝑒1 , 𝑒2 ≥ 0 𝟏𝟑 𝒙𝟏 4 1 𝟐ൗ 0 𝟏ൗ
𝟓 𝟓
𝒁𝒊 52 13 𝟐𝟔ൗ 0 𝟏𝟑ൗ
Tableau 1 𝟓 𝟓
𝑪𝒊 -𝒁𝒊 0 𝟏𝟒ൗ 0 −𝟏𝟑ൗ
𝟓 𝟓
Itération 2
Critères d'arrêt atteint 𝟖 𝒙𝟐 𝟏𝟓ൗ 0 1 𝟓ൗ −𝟏ൗ
𝟒 𝟖 𝟖
Z = 62,5
𝟏𝟑 𝒙𝟏 𝟓ൗ 1 0 −𝟏ൗ 𝟏ൗ
x1 = 2. 5 𝟐 𝟒 𝟒
x2 = 3.75 𝒁𝒊 62.5 13 8 𝟕ൗ
𝟒
𝟒𝟓ൗ
𝟐𝟎
𝑪𝒊 -𝒁𝒊 0 0 −𝟕ൗ −𝟒𝟓ൗ 73
𝟒 𝟐𝟎
La solution relaxé est: x1 = 2. 5 ; x2 = 3.75
Les 2 variables sont pas des entiers donc on résout avec l’algorithme de Branch and Bound.
La borne sup est 62.5

La borne inf est 50 Z0 =
62.5
x1 ≤ 2 x1 ≥ 3
Z1 = Z2 =
74
On résout le sous-problème P1 Max 𝑪𝒊 13 8 O 0

On prend la ligne concernant la
variable sur laquelle on branche
𝟖 𝒙𝟐 𝟏𝟓ൗ 0 1 𝟓ൗ −𝟏ൗ
𝟒 𝟖 𝟖
➢ 𝟓Τ𝟐 = 𝒙𝟏 − 𝟏Τ𝟒 𝒆𝟏 + 𝟏Τ𝟒 𝒆𝟐 𝟏𝟑 𝒙𝟏 𝟓ൗ 1 0 −𝟏ൗ 𝟏ൗ
𝟐 𝟒 𝟒
𝒁𝒊 0 13 8 𝟕ൗ 𝟒𝟓ൗ
➢ 𝒙𝟏 = 𝟏Τ𝟒 𝒆𝟏 − 𝟏Τ𝟒 𝒆𝟐 + 𝟓Τ𝟐 𝟒 𝟐𝟎
𝑪𝒊 -𝒁𝒊 0 0 −𝟕ൗ −𝟒𝟓ൗ
➢ 𝟏Τ𝟒 𝒆𝟏 − 𝟏Τ𝟒 𝒆𝟐 + 𝟓Τ𝟐 ≤ 2 𝟒 𝟐𝟎
➢ 𝟏Τ𝟒 𝒆𝟏 − 𝟏Τ𝟒 𝒆𝟐 ≤ − 𝟏Τ𝟐
On ajoute une variable d’écart pour avoir la forme standard de la contrainte:

➢ 𝟏Τ𝟒 𝒆𝟏 − 𝟏Τ𝟒 𝒆𝟐 + 𝐬 = − 𝟏Τ𝟐
75
𝑪𝒊 13 8 O 0 0
➢ 𝟏Τ𝟒 𝒆𝟏 − 𝟏Τ𝟒 𝒆𝟐 + 𝐬 = − 𝟏Τ𝟐
𝑪𝑩 B b 𝐱𝟏 𝐱𝟐 𝒆𝟏 𝒆𝟐 s
𝟖 𝒙𝟐 𝟏𝟓ൗ 0 1 𝟓ൗ −𝟏ൗ 0
𝟒 𝟖 𝟖
𝟏𝟑 𝒙𝟏 𝟓ൗ 1 0 −𝟏ൗ 𝟏ൗ 0
𝟐 𝟒 𝟒
VS 0 s −𝟏ൗ 0 0 𝟏ൗ −𝟏ൗ 1
𝟐 𝟒 𝟒
𝒁𝒊 0 13 8 𝟕ൗ 𝟒𝟓ൗ 0
𝟒 𝟐𝟎
𝑪𝒊 -𝒁𝒊 0 0 −𝟕ൗ −𝟒𝟓ൗ 0
𝟒 𝟐𝟎
VE
76
𝑪𝒊 13 8 O 0 0
𝑪𝑩 B b 𝐱𝟏 𝐱𝟐 𝒆𝟏 𝒆𝟐 s
𝟖 𝒙𝟐 𝟏𝟓ൗ 0 1 𝟓ൗ −𝟏ൗ 0
𝟒 𝟖 𝟖
𝟏𝟑 𝒙𝟏 𝟓ൗ 1 0 −𝟏ൗ 𝟏ൗ 0
𝟐 𝟒 𝟒
0 s −𝟏ൗ 0 0 𝟏ൗ −𝟏ൗ 1
𝟐 𝟒 𝟒
𝒁𝒊 0 13 8 𝟕ൗ 𝟒𝟓ൗ 0
𝟒 𝟐𝟎
𝑪𝒊 -𝒁𝒊 0 0 −𝟕ൗ −𝟒𝟓ൗ 0
𝟒 𝟐𝟎
𝑪𝒊 13 8 O 0 0
Critères d'arrêt pour le simplex DUAL 𝑪𝑩 B b 𝐱𝟏 𝐱𝟐 𝒆𝟏 𝒆𝟐 s
Les 𝒃𝒊 sont tous ≥ 𝟎 𝟖 𝒙𝟐 4 0 1 𝟏ൗ 𝟎 −𝟏ൗ
Donc on a atteint l’optimalité et la 𝟐 𝟐
solution est: 𝟏𝟑 𝒙𝟏 2 1 0 0 𝟎 1
Z = 58 0 𝒆𝟐 2 0 0 -1 1 -4
𝐱𝟏 = 2
𝐱𝟐 = 4 𝒁𝒊 58 13 8 4 0 9
𝑪𝒊 -𝒁𝒊 0 0 -4 0 -977
La solution de P1 entière est: x1 = 2 ; x2 = 4
La borne sup est 62.5

La nouvelle borne inf est 58
On continue sur l’autre branche avec x1 ≥ 3

Z0 =
62.5
x1 ≤ 2 x1 ≥ 3
Z1= Z2 =
58
78
On résout le sous-problème P2 avec la Max 13 8 O 0

𝑪𝒊
Nouvelle contrainte x1 ≥ 3
𝟖 𝒙𝟐 𝟏𝟓ൗ 0 1 𝟓ൗ −𝟏ൗ
➢ 𝟓Τ𝟐 = 𝒙𝟏 − 𝟏Τ𝟒 𝒆𝟏 + 𝟏Τ𝟒 𝒆𝟐 𝟒 𝟖 𝟖
𝟏𝟑 𝒙𝟏 𝟓ൗ 1 0 −𝟏ൗ 𝟏ൗ
➢ 𝒙𝟏 = 𝟏Τ𝟒 𝒆𝟏 − 𝟏Τ𝟒 𝒆𝟐 + 𝟓Τ𝟐 𝟐 𝟒 𝟒
𝒁𝒊 0 13 8 𝟕ൗ 𝟒𝟓ൗ
➢ 𝟏Τ𝟒 𝒆𝟏 − 𝟏Τ𝟒 𝒆𝟐 + 𝟓Τ𝟐 ≥ 3 𝟒 𝟐𝟎
𝑪𝒊 -𝒁𝒊 0 0 −𝟕ൗ −𝟒𝟓ൗ
𝟒 𝟐𝟎
➢ −𝟏Τ 𝒆
𝟒 𝟏 + 𝟏Τ 𝒆
𝟒 𝟐 − 𝟓Τ
𝟐 ≤ −3
➢ −𝟏Τ 𝒆
𝟒 𝟏 + 𝟏Τ𝟒 𝒆𝟐 ≤ − 𝟏Τ𝟐
➢ −𝟏Τ 𝒆
𝟒 𝟏 + 𝟏Τ𝟒 𝒆𝟐 + t = − 𝟏Τ𝟐
79
𝑪𝒊 13 8 O 0 0
➢ −𝟏Τ 𝒆
𝟒 𝟏 + 𝟏Τ𝟒 𝒆𝟐 + t = − 𝟏Τ𝟐
𝑪𝑩 B b 𝐱𝟏 𝐱𝟐 𝒆𝟏 𝒆𝟐 t
𝟖 𝒙𝟐 𝟏𝟓ൗ 0 1 𝟓ൗ −𝟏ൗ 0
𝟒 𝟖 𝟖
𝟏𝟑 𝒙𝟏 𝟓ൗ 1 0 −𝟏ൗ 𝟏ൗ 0
𝟐 𝟒 𝟒
VS 0 t −𝟏ൗ 0 0 −𝟏ൗ 𝟏ൗ 1
𝟐 𝟒 𝟒
𝒁𝒊 0 13 8 𝟕ൗ 𝟒𝟓ൗ 0
𝟒 𝟐𝟎
𝑪𝒊 -𝒁𝒊 0 0 −𝟕ൗ −𝟒𝟓ൗ 0
𝟒 𝟐𝟎
VE
80
𝑪𝒊 13 8 O 0 0
𝑪𝑩 B b 𝐱𝟏 𝐱𝟐 𝒆𝟏 𝒆𝟐 t
𝟖 𝒙𝟐 𝟏𝟓ൗ 0 1 𝟓ൗ −𝟏ൗ 0
𝟒 𝟖 𝟖
𝟏𝟑 𝒙𝟏 𝟓ൗ 1 0 −𝟏ൗ 𝟏ൗ 0
𝟐 𝟒 𝟒
0 t −𝟏ൗ 0 0 −𝟏ൗ 𝟏ൗ 1
𝟐 𝟒 𝟒
𝒁𝒊 0 13 8 𝟕ൗ 𝟒𝟓ൗ 0
𝟒 𝟐𝟎
𝑪𝒊 -𝒁𝒊 0 0 −𝟕ൗ −𝟒𝟓ൗ 0
𝟒 𝟐𝟎 𝑪𝒊 13 8 O 0 0
Critères d'arrêt pour le dual simplex 𝑪𝑩 B b 𝐱𝟏 𝐱𝟐 𝒆𝟏 𝒆𝟐 t
Les 𝒃𝒊 sont tous ≥ 𝟎 𝟖 𝒙𝟐 𝟓ൗ 0 1 𝟎 𝟏ൗ 𝟓ൗ
Donc on a atteint l’optimalité et la 𝟐 𝟐 𝟐
solution est: 𝟏𝟑 𝒙𝟏 3 1 0 0 𝟎 -1
Z = 59
0 𝒆𝟏 2 0 0 1 -1 -4
x_1 = 3
x_2 = 2.5 𝒁𝒊 59 13 8 0 4 7
𝑪𝒊 -𝒁𝒊 0 0 0 -4 -781
La solution de P2 n’est pas entière est: Z0 =

x1 = 3 ; x2 = 2.5 62.5
La borne sup est 59 x1 ≤ 2 x1 ≥ 3

La nouvelle borne inf est 58
Z1= Z2=
On continue d’explorer la variable x2 59
58
sur le nœud 2
x2 ≤ 2 x2 ≥ 3
Z3= Z4=
82
On résout le sous-problème P3 avec 𝑪𝒊 13 8 O 0 0

la nouvelle contrainte x2 ≤ 2 𝑪𝑩 B b 𝐱𝟏 𝐱𝟐 𝒆𝟏 𝒆𝟐 t
𝟖 𝒙𝟐 𝟓ൗ 0 1 𝟎 𝟏ൗ 𝟓ൗ
𝟐 𝟐 𝟐
𝟏𝟑 𝒙𝟏 3 1 0 0 𝟎 -1
➢ 𝟓Τ
𝟐 = 𝐱 𝟐 + 𝟏Τ𝟐 𝐞𝟐 + 𝟓Τ 𝐭
𝟐 0 𝒆𝟏 2 0 0 1 -1 -4
➢ 𝐱 𝟐 = −𝟏Τ𝟐 𝐞𝟐 − 𝟓Τ𝟐 𝐭 + 𝟓Τ𝟐 𝒁𝒊 59 13 8 0 4 7
𝑪𝒊 -𝒁𝒊 0 0 0 -4 -7
➢ −𝟏Τ 𝐞
𝟐 𝟐 − 𝟓Τ𝟐 𝐭 + 𝟓Τ𝟐 ≤ 𝟐
➢ −𝟏Τ 𝐞
𝟐 𝟐 − 𝟓Τ𝟐 𝐭 ≤ − 𝟏Τ𝟐

➢ −𝟏Τ 𝐞
𝟐 𝟐 − 𝟓Τ𝟐 𝐭 + 𝐭 𝟏 = − 𝟏Τ𝟐
83
𝑪𝒊 13 8 O 0 0 0
𝑪𝑩 B b 𝐱𝟏 𝐱𝟐 𝒆𝟏 𝒆𝟐 t 𝐭𝟏
8 𝒙𝟐 𝟓ൗ 0 1 𝟎 𝟏ൗ 𝟓ൗ 0
𝟐 𝟐 𝟐
13 𝒙𝟏 3 1 0 0 𝟎 -1 0
0 𝒆𝟏 2 0 0 1 -1 -4 0
0 𝐭𝟏 −𝟏ൗ 0 0 0 −𝟏ൗ −𝟓ൗ 1
𝟐 𝟐 𝟐
𝒁𝒊 59 13 8 0 4 7 0
𝑪𝒊 13 8 O 0 0 0
𝑪𝒊 -𝒁𝒊 0 0 0 -4 -7 0
𝑪𝑩 B b 𝐱𝟏 𝐱𝟐 𝒆𝟏 𝒆𝟐 t 𝐭𝟏
Critères d'arrêt pour le dual simplex
8 𝒙𝟐 2 0 1 0 0 0 1
Les 𝒃𝒊 sont tous ≥ 𝟎
Donc on a atteint l’optimalité et la 13 𝒙𝟏 3 1 0 0 0 -1 0
solution est: 0 𝒆𝟏 2 0 0 1 0 -4 -2
Z = 55
𝒙𝟏 = 3 0 𝐭𝟏 1 0 0 0 1 5 -2
𝒙𝟐 = 2 𝒁𝒊 55 13 8 0 0 -13 8
𝑪𝒊 -𝒁𝒊 0 0 0 0 13 84
-8
La solution de P3 est entière : x1 = 3 ; x2 = 2 Z0 =

62.5
La borne sup est 59
La nouvelle borne inf est 58 x1 ≤ 2 x1 ≥ 3
Z1= Z2=
58 59
x2 ≤ 2 x2 ≥ 3
On élague le nœud 3 car on a une solution entière Z3= Z4=

55
On résout maintenant le sous-problème du nœud 4
85
On résout le sous-problème P4 avec 𝑪𝒊 13 8 O 0 0

la nouvelle contrainte x2 ≥ 3 𝑪𝑩 B b 𝐱𝟏 𝐱𝟐 𝒆𝟏 𝒆𝟐 t
𝟖 𝒙𝟐 𝟓ൗ 0 1 𝟎 𝟏ൗ 𝟓ൗ
𝟐 𝟐 𝟐
➢ 𝟓Τ𝟐 = 𝐱 𝟐 + 𝟏Τ𝟐 𝐞𝟐 + 𝟓Τ𝟐 𝐭 𝟏𝟑 𝒙𝟏 3 1 0 0 𝟎 -1
0 𝒆𝟏 2 0 0 1 -1 -4
➢ 𝐱 𝟐 = −𝟏Τ𝟐 𝐞𝟐 − 𝟓Τ𝟐 𝐭 + 𝟓Τ𝟐
𝒁𝒊 59 13 8 0 4 7
➢ −𝟏Τ 𝐞
𝟐 𝟐 − 𝟓Τ 𝐭 + 𝟓Τ
𝟐 𝟐 ≥𝟑 𝑪𝒊 -𝒁𝒊 0 0 0 -4 -7
➢ 𝟏Τ𝟐 𝐞𝟐 + 𝟓Τ𝟐 𝐭 − 𝟓Τ𝟐 ≤ −𝟑
➢ 𝟏Τ𝟐 𝐞𝟐 + 𝟓Τ𝟐 𝐭 ≤ − 𝟏Τ𝟐

➢ 𝟏Τ𝟐 𝐞𝟐 + 𝟓Τ𝟐 𝐭 + 𝐭 𝟐 = − 𝟏Τ𝟐
86
𝑪𝒊 13 8 O 0 0 0
𝑪𝑩 B b 𝐱𝟏 𝐱𝟐 𝒆𝟏 𝒆𝟐 t 𝐭𝟐
8 𝒙𝟐 𝟓ൗ 0 1 𝟎 𝟏ൗ 𝟓ൗ 0
𝟐 𝟐 𝟐
13 𝒙𝟏 3 1 0 0 𝟎 -1 0
0 𝒆𝟏 2 0 0 1 -1 -4 0
On ne peut pas choisir une variable entrante 0 𝐭𝟐 −𝟏ൗ 0 0 0 𝟏ൗ 𝟓ൗ 1
donc solution non-réalisable 𝟐 𝟐 𝟐
𝒁𝒊 59 13 8 0 4 7 0
𝑪𝒊 -𝒁𝒊 0 0 0 -4 -7 0
87
La solution de P4 est non-réalisable Z0 =

62.5
Donc la solution optimale est la meilleure
solution entière parmi les solutions trouvées x1 ≤ 2 x1 ≥ 3
Z1 = 58
x1 = 2 ;
x2 = 4 Z2=
Z1=
58 59
x2 ≤ 2 x2 ≥ 3
Z3= Z4=
55
élagué par optimalité non-réalisable
88
USTHB-Info |2024
Unimodularité et problèmes faciles à

résoudre
Matrices totalement unimodulaires dans la programmation linéaire
Définition : Une matrice carrée U est unimodulaire si det (u) = 1 ou -1
Définition : Une matrice A est totalement unimodulaire
• Si toute sous-matrice carrée non singulière est unimodulaire

• i.e : toute sous-matrice carrée de M a un déterminant +1, -1 ou 0.
Example:
Matrices qui ne sont pas TU.

Matrices qui sont TU.
90
Propriétés : Si M est TU (totalement unimodulaire)
1. chaque élément de A est 0, 1 ou -1

2. -A, At sont TU
3. [A I] est TU
Example:
A= I=
91
Théorème : Soit A une matrice m × n (m<n), de plain rang et TU, b ∈ ℤm , c ∈ ℝn alors

le programme linéaire
Min c T𝐱
s. c Ax = b
a une solution optimale entière x ∗ ∈ ℤn
Corollaire : Soit A une matrice m × n TU, b ∈ ℤm , c ∈ ℝn alors la solution optimale x ∗ de
Min c T𝐱
s. c Ax ≤ b
x≥0
Est aussi entière
92
Théorème : Soit G =(V, E) un graphe avec une matrice d’adjacence A, ou A est de

dimension |V| × |E|
−1, si le noeud i est la source de l′ arc j

aij = ቐ 1, si le noeud i est destination de l′ arc j
0, sinon
alors A est TU.
93
Example : Problème du plus court chemin

Le problème du plus court chemin consiste à trouver le chemin de coût minimal entre
deux nœuds dans un graphe pondéré (orienté ou non). Ce problème peut être modélisé
sous forme d'un programme linéaire (PL).
94
95
Contrainte :
96
Example : couplage maximum d’un graphe biparti

Le problème de couplage maximum dans un graphe biparti consiste à trouver un sous-
ensemble d'arêtes dans un graphe biparti tel que chaque sommet est incident à au plus
une arête du sous-ensemble, et que le nombre d'arêtes dans ce sous-ensemble est
maximal.
97
98
Contrainte :
99
Merci pour votre
attention!

Cours Plne

Transféré par

Droits d'auteur :

Formats disponibles

Cours Plne

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours Plne

Transféré par

Droits d'auteur :

Formats disponibles

USTHB-Info |2024

Programmation linéaire en variables

En d'autres termes la PLNE est particulièrement utile lorsque :

Considérons le programme en nombres entiers :

Considérons le programme en nombres entiers :

Comme le montre la figure , la solution

Problème d'optimisation combinatoire:

• Le problème de Sac à dos (Knapsack):

Le problème de voyageurs de commerce (TSP):

Dans le tableau, nous montrons la rapidité avec laquelle certaines fonctions

Étant donné un PLNE ou un problème d’OC:

La question porte sur la démonstration de l'optimalité d'un point 𝑥 ∗ , et plus précisément

et une séquence croissante

de bornes inférieures, et s'arrêter lorsque

où 𝜖 est une petite valeur non négative convenablement choisie. Nous

Chaque solution réalisable x ∗ ∈ X fournit une borne inférieure Z = c(x ∗ ) ≤ Z. C'est

L'approche la plus importante est la « relaxation », l'idée étant de remplacer un problème

Définition : Un problème (PR) Z PR = max { f(x) ∶ x ∈ T ⊆ Rn } est une relaxation de (PLNE)

Proposition : Si PR (problème relaxé) est une relaxation de PLNE, Z PR ≥ Z.

La question se pose alors de savoir comment construire des relaxations intéressantes.

Définition : Pour le programme en nombres entiers Z = max{cx ∶ x ∈ P ∩ Z n } avec la

Comme P ∩ Z n ⊆ P et que la fonction objective est inchangée, il s'agit clairement d'une

Exemple : Considérons le programme entier (PLNE)

Exemple : Considérons le programme entier (PLNE)

Exemple : Considérons le programme entier (PLNE)

Exemple : Considérons le programme entier (PLNE)

• Borne supérieure : La relaxation lagrangienne fournit une borne supérieure (dans le

• Flexibilité : On peut choisir les contraintes à relaxer en fonction de leur complexité.

Dans sa forme la plus simple, le Branch-and-Bound est simplement une manière

Si ces sous-problèmes sont encore trop difficiles, nous procédons à un nouveau

1. Division de l’espace de recherche ("Branching") :

2. Calcul de bornes ("Bounding") :

3. Élagage de l’arborescence ("Pruning"):

Diviser pour régner :

Comment pouvons-nous décomposer le problème en une série de problèmes plus petits

Proposition : Soit S = 𝑆1 ∪ ⋯ ∪ 𝑆𝑘 une décomposition de S en ensembles plus petits, et

• Comment pouvons-nous utiliser intelligemment certaines limites sur les valeurs de

Proposition : Soit S = 𝑆1 ∪ ⋯ ∪ 𝑆𝑘 une décomposition de S en ensembles plus petits, et

Exemple 01 : nous montrons une décomposition de S en deux ensembles S1 et S2 ainsi

Nous notons tout d'abord que

Deuxièmement, nous observons que les bornes inférieure et supérieure de 𝑍1 étant

Exemple 02 : nous décomposons à nouveau S en deux ensembles S1 et S2 et montrent les

Nous notons d'abord que

Exemple 03 : nous décomposons à nouveau S en deux ensembles S1 et S2 avec

Nous notons d'abord que

1. Élagage par optimalité : Z t = max{𝑐𝑥: 𝑥 ∈ 𝑆𝑡 } a été résolu.

Si nous demandons maintenant comment les bornes doivent être obtenues.

1. Trouver la solution optimale du modèle de programmation linéaire avec les restrictions en

Machine Surface de plancher Prix d'achat

Maximiser Z = 100 𝑥1 + 150 𝑥2

Nous commençons la méthode Branch and Bound en résolvant d'abord le problème

une borne supérieure - la valeur Z de la solution

La limite inférieure est la valeur Z de la solution

Voir laquelle est la plus éloignée

La partie 0,56 de 5,56 est la partie

Max Z = 100 𝒙𝟏 + 150 𝒙𝟐 Max Z = 100 𝒙𝟏 + 150 𝒙𝟐

• Comme nous ne disposons pas encore d'une solution optimale et réalisable en

Max Z = 100 𝒙𝟏 + 150 𝒙𝟐 Max Z = 100 𝒙𝟏 + 150 𝒙𝟐

Max Z = 100 𝒙𝟏 + 150 𝒙𝟐

Max Z = 100 𝒙𝟏 + 150 𝒙𝟐