Recherche Opérationnelle

R.O.
Partie 2: Programmation Linéaire P.L

Pr. Abdessamad Kamouss

Cycle Ingénieur
ENSAM Casablanca

Pr. Abdessamad Kamouss 33 Recherche opérationnelle 33 / 102

Contenu du module

Pr. Abdessamad Kamouss 34 Recherche opérationnelle 34 / 102

Contenu du module

Pr. Abdessamad Kamouss 35 Recherche opérationnelle 35 / 102

Programmation linéaire - Définitions

Programmation linéaire
La programmation linéaire est une branche de la recherche opérationnelle
dont l’objectif est de minimiser ou maximiser une fonction numérique
multilinéaire (dite fonction objectif ou fonction économique) à plusieurs
variables, sachant que ces dernières sont liées moyennant des équations ou
des inéquations linéaires dites contraintes.

De nombreux problèmes concrets provenant de domaines aussi divers que

l’industrie lourde, le raffinage, les transports, l’agriculture, la gestion, la
production, l’informatique, l’ingénierie... peuvent être modélisés comme des
programmes linéaires, la résolution de ces modèles ayant permis l’obtention
de gains substantiels.

Pr. Abdessamad Kamouss 36 Recherche opérationnelle 36 / 102

Problème de production

Exemple (Production de voiture)

Un fabricant de voitures propose 2 modèles à la vente, des grosses voitures et
des petites voitures. La grosse voiture est vendue à 16000e tandis que les
petites voitures à 10000 e. Son problème vient de l’approvisionnement limité
en deux matières premières, le caoutchouc et l’acier.
La construction d’une petite voiture nécessite l’emploi d’une unité de
caoutchouc et d’une unité d’acier, tandis que celle d’une grosse voiture
nécessite une unité de caoutchouc mais deux unités d’acier.

Matière Caoutchouc Acier

Disponibilités 400 unités 600 unités

Question
Le fabriquant souhaite savoir combien de petites et de grosses voitures
doit-il produire afin de maximiser son chiffre d’affaires en prenant en
compte son stock actuel.
Pr. Abdessamad Kamouss 37 Recherche opérationnelle 37 / 102
Problème de production

Modélisation
Variables de décision :
x : nombre de grosses voitures produites
y : nombre de petites voitures produites
Fonction objectif :

[Max] z = 16000x + 10000y

Contraintes :
x + y ≤ 400 (caoutchouc)
2x + y ≤ 600 (acier)
x ≥ 0 et y ≥ 0.

Pr. Abdessamad Kamouss 38 Recherche opérationnelle 38 / 102

Problème de production

Solution optimale x∗ = 200, y∗ = 200 et z∗ = 5.200.000e.

Pr. Abdessamad Kamouss 39 Recherche opérationnelle 39 / 102
Programme linéaire - Définitions

Définition
Un programme linéaire est une modélisation mathématique en R.O dans
lequel les variables sont des réels qui doivent satisfaire un ensemble
d’équations et/ ou d’inéquations linéaires (dites contraintes) et la valeur d’une
fonction linéaire de ces variables (appelée fonction objectif) qu’on souhaite
rendre minimum ou maximum.

Ingrédients principaux :
Alternatives - variables de décision - inconnues du problème - variables
d’activité.
Restrictions - contraintes.
Fonction à optimiser - fonction objectif - fonction économique.

Pr. Abdessamad Kamouss 40 Recherche opérationnelle 40 / 102

Programme linéaire - Modélisation

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

 n


 Maximiser ou Minimiser z(x 1 , x 2 , ..., xn ) = ∑ c jx j

 j=1

  n
∑ a1i xi ≤, =, ≥ b1

 

 

  i=1
n

 


a2i xi ≤, =, ≥ b2

 

 ∑
 i=1




 Sous les contraintes ......................





 ......................

  n

∑ ami xi ≤, =, ≥ bm

 


 

 i=1

 

x1 , x2 , ..., xn ∈ R


Pr. Abdessamad Kamouss 41 Recherche opérationnelle 41 / 102

Programme linéaire - Modélisation

Pr. Abdessamad Kamouss 42 Recherche opérationnelle 42 / 102

Programme linéaire - Forme Canonique

Forme canonique d’un PL :

Un programme linéaire est dit canonique s’il est écrit sous la forme suivante :

 [Max] z = cT x


(PC) Ax ≤ b
x≥0


Remarques
Deux propriétés caractérisent la forme canonique.
Toutes les variables sont astreintes à être positives ou nulles (non
négatives).
Toutes les contraintes sont des inéquations.

Pr. Abdessamad Kamouss 43 Recherche opérationnelle 43 / 102

Programme linéaire - Forme Standard

Forme standard d’un PL :

Un programme linéaire est dit standard s’il est écrit sous la forme suivante :

 [Max] z = cT x


(PC) Ax = b
x≥0


Remarques
Deux propriétés caractérisent la forme canonique.
Toutes les variables sont astreintes à être positives ou nulles.
Toutes les autres contraintes sont des équations.

Pr. Abdessamad Kamouss 44 Recherche opérationnelle 44 / 102

Programme linéaire - Passage entre Formes

Et-il possible de passer d’une forme à une autre forme d’un programme
linéaire quelconque ?

Théorème

Tout programme linéaire sous forme standard peut être écrit sous forme
canonique, et

tout programme linéaire sous forme canonique peut être écrit sous
forme standard.

Pr. Abdessamad Kamouss 45 Recherche opérationnelle 45 / 102

Programme linéaire - Passage entre Formes

équation → inéquation


ax ≤ b
ax = b ⇐⇒
ax ≥ b

inéquation → équation : ajouter une variable d’écart ou d’excédent

ax ≤ b ⇐⇒ ax + e = b, e≥0
ax ≥ b ⇐⇒ ax − e = b, e≥0

variable non contrainte → variables positives


x = e1 − e2
x ≶ 0 ⇐⇒
e1 , e2 ≥ 0

max ↔ min : * min f (x) = − max(− f (x))

Pr. Abdessamad Kamouss 46 Recherche opérationnelle 46 / 102
 Algorithme pour construire le programme linéaire

Afin de transformer un problème en un programme linéaire, on suit l’algorithme

suivant :

Algorithme de construction de programme linéaire

1 Identifier les variables de décision nécessaires ;
2 Identifier les contraintes du problème et les exprimer en fonction des
variables d’activités ;
3 Identifier la fonction objectif ;
4 Ecrire le programme linéaire et spécifier si le critère de sélection est à
maximiser ou à minimiser.

Pr. Abdessamad Kamouss 47 Recherche opérationnelle 47 / 102

Exemple d’un PL d’optimisation de production

Exemple (Problème de production)

Une usine fabrique deux produits P1 et P2 . Chacun de ces produits demande pour son
usinage, des heures de fabrications unitaires sur les machines A, B,C, D, E comme
indiqué dans le tableau suivant :
A B C D E
P1 0 1,5 2 3 3
P2 3 4 3 2 0
Disponiblité de chaque machine 39h 60h 57h 70h 57h
Les marges brutes de chaque produit sont respectivement :
M1 = 1700 UM M2 = 3200 UM

Question
Ecrire le programme linéaire qui détermine les nombres de produits de type P1
et de type P2 à fabriquer pour maximiser sa marge brute.

Pr. Abdessamad Kamouss 48 Recherche opérationnelle 48 / 102

Exemple d’un PL d’optimisation de production

Les variables : x1 quantité à fabriquer de P1 et x2 quantité à fabriquer de

P2
L’objectif :
Maximiser z = 1700x1 + 3200x2
Les contraintes suivantes

3x2 ≤ 39
1, 5x1 + 4x2 ≤ 60
2x1 + 3x2 ≤ 57
3x1 + 2x2 ≤ 70
3x1 ≤ 57
x1 ≥ 0, x2 ≥ 0

Pr. Abdessamad Kamouss 49 Recherche opérationnelle 49 / 102

Exemple d’un PL d’optimisation de production

Le PL correspondant

[Max] z = 1700x1 + 3200x2



 3x2 ≤ 39



 1, 5x1 + 4x2 ≤ 60
2x1 + 3x2 ≤ 57


 3x1 + 2x2 ≤ 70
 3x1 ≤ 57



x1 ≥ 0, x2 ≥ 0


Pr. Abdessamad Kamouss 50 Recherche opérationnelle 50 / 102

Exemple d’un PL d’optimisation de transport

Exemple (Problème de transport)

Une entreprise de construction d’automobiles possède trois usines situées
respectivement à Tanger, Kénitra et Agadir. Un certain métal nécessaire à la
construction des véhicules est disponible aux stocks de Casa et El Jadida. Les
quantités de ce métal nécessaires aux usines sont 400, 300 et 200 tonnes
respectivement pour les usines de Tanger, Kénitra et Agadir chaque semaine,
tandis que les quantités disponibles sont 550 et 350 tonnes par semaines
respectivement à Casa et à El Jadida. Les coûts de transport unitaires sont
comme suit :

Tanger Kénitra Agadir

Casa 5 6 3
El Jadida 3 5 4

Pr. Abdessamad Kamouss 51 Recherche opérationnelle 51 / 102

Exemple d’un PL d’optimisation de transport

Exemple (Suite)
Ce tableau signifie que pour envoyer x tonnes de Casa à Kénitra, par exemple,
il en coûte 6x UM. Le problème consiste à déterminer un plan de transport
optimal, c’est-à- dire à trouver quels sont les poids de métal à envoyer de
chaque stock à chaque usine de sorte que :
(i) Les demandes soient satisfaites (chaque usine reçoit au moins la
quantité de métal qui lui est nécessaire).
(ii) Les quantités demandées à chaque stock n’excèdent pas les quantités
disponibles.
(iii) Les quantités envoyées sont positives ou nulles.
(iv) Le coût total du transport est rendu minimum compte tenu des
contraintes ci-dessus.

Pr. Abdessamad Kamouss 52 Recherche opérationnelle 52 / 102

Exemple d’un PL d’optimisation de transport

Le PL correspondant
Affectant au stock de Casa l’indice 1, au stock d’El Jadida l’indice 2 et aux trois
usines les indices 1,2 et 3 respectivement pour Tanger, Kénitra et Agadir, on
conviendra que xi j représentera le nombre de tonnes de métal qui sont
acheminées chaque semaine depuis le stock d’indice i vers l’usine d’indice j.
Le programme linéaire s’écrit alors :

[Min]z = 5x11 + 6x12 + 3x13 + 3x21 + 5x22 + 4x23



 x11 + x21 ≥ 400
 x + x ≥ 300


 12 22
x13 + x23 ≥ 200


 x11 + x12 + x13 ≤ 550
x + x22 + x23 ≤ 350


 21


x11 , x12 , x13 , x21 , x22 , x23 ≥ 0

Pr. Abdessamad Kamouss 53 Recherche opérationnelle 53 / 102

Contenu du module

Pr. Abdessamad Kamouss 54 Recherche opérationnelle 54 / 102

Résolution d’un programme linéaire

Méthodes de résolution de programme linéaire

Les méthodes suivantes sont les plus utilisées :
Méthode graphique
Méthode algébrique
Méthode Simplexe
Fonction Solveur
Python en utilisant PuLP

Pr. Abdessamad Kamouss 55 Recherche opérationnelle 55 / 102

Programme linéaire - Solutions

Définition (Solution admissible)

Une solution admissible est un ensemble de valeurs données aux variables
qui satisfait toutes les contraintes.

Définition (Solution optimale)

Une solution optimale est une solution admissible qui optimise la fonction
objectif.

Pr. Abdessamad Kamouss 56 Recherche opérationnelle 56 / 102

Résolution de PL - Méthode Graphique

Description de la méthode
1 On trace les droites représentant les contraintes. Chaque inéquation est
satisfaite dans un demi-plan limité par la droite d’équation
correspondante.
2 Après avoir hachuré les parties du plan ne respectant pas les contraintes,
il reste une zone non hachurée qui représente l’ensemble des solutions
possibles (ensemble admissible).
3 Une solution optimale du programme linéaire est située en un sommet du
domaine de l’ensemble des solutions possibles.

Pr. Abdessamad Kamouss 57 Recherche opérationnelle 57 / 102

Résolution de PL - Méthode Graphique

Résolution du PL du problème de l’optimisation de la production



 [Max] z = 1700x1 + 3200x2







 3x2 ≤ 39
1, 5x1 + 4x2 ≤ 60

 2x1 + 3x2 ≤ 57

3x1 + 2x2 ≤ 70




3x ≤ 57


 1


x1 ≥ 0, x2 ≥ 0

Pr. Abdessamad Kamouss 58 Recherche opérationnelle 58 / 102

Résolution de PL - Méthode Graphique

A B
C
10

F E
10 20

 
L’optimum se trouve au point C x1 = 96 69
7 et x2 = 7 . Donc

384000
zmax = .
7
Pr. Abdessamad Kamouss 59 Recherche opérationnelle 59 / 102
Résolution de PL - Méthode Graphique

L’ensemble des solutions réalisables est toujours un

polyèdre (intersection de demi-espaces)
Les lignes de niveau { f = constante } de la
fonction-objectif z = f (x1 , x2 , . . . , xn ) sont des
hyperplans affines (n = 2 ⇒ droite, n = 3 ⇒ plan...)

Optimum atteint au bord

L’optimum de la fonction-objectif, s’il existe, est atteint en un ou plusieurs
sommets du polyèdre.

Justification mathématique :
Les dérivées partielles de f (X) = c.X ne s’annulent jamais, et le domaine
X/ ∑nj=1 ai j x j ≤ bi , i ∈ {1, . . . , m} est un compact.


Donc l’optimum est atteint au bord.

Pr. Abdessamad Kamouss 60 Recherche opérationnelle 60 / 102

Résolution de PL - Méthode Simplexe

Solution de base
Considérons un PL dans sa forme standard qui sera noté (PLS) :
 n


 Maximiser z(x1 , x2 , ..., xn ) = ∑ c j x j

 j=1
 
a 11 1 + a12 x2 + ... + a1n xn ± e1 = b1
x



 

 


 a21 x1 + a22 x2 + ... + a2n xn ± e2 = b2
......................

Sous les contraintes


......................



 

a x + am2 x2 + ... + amn xn ± em = bm
 

 m1 1

 
 
x1 , x2 , ..., xn ∈ R+


n désigne le nombre de variables de décision x1 , x2 , ..., xn .

m le nombre des contraintes = le nombre de variables d’écart ou
d’excédent e1 , e2 , ..., em .
On obtient donc un système de m équations linéaires à n′ = n + m
inconnues (m < n′ ) : infinité de solutions possible.
Pr. Abdessamad Kamouss 61 Recherche opérationnelle 61 / 102
Résolution de PL - Méthode Simplexe

Définition (Solutions de base)

Une solution (x1 , x2 , ..., xn , e1 , e2 , ..., em ) vérifiant les m contraintes de (PLS)
est dite solution de base de (PLS) si au moins (n′ − m) de ses variables sont
égales à 0.
Les variables fixées à zéro sont appelées variables hors base et les autres
variables en base.

Remarque
Une solution de base est dites dégénérée lorsque certaines variables de base
sont nulles.

Définition (Solutions de base admissible)

Une solution de base dont tout les coordonnées sont non négatives est dite
solution de base admissible de (PLS).

Pr. Abdessamad Kamouss 62 Recherche opérationnelle 62 / 102

Résolution de PL - Méthode Simplexe

PLS - Bases et points extrêmes

Considérons l’exemple suivant :
 

 2x + y ≤8 
 2x + y + e1 =8
x + 2y ≤7 x + 2y + e2 =7
 
(PL) =⇒ (PLS)

 y ≤3 
 y + e3 =3
x, y ≥0 x, y, e1 , e2 , e3 ≥ 0
 

Pr. Abdessamad Kamouss 63 Recherche opérationnelle 63 / 102

Résolution de PL - Méthode Simplexe

PLS - Bases et points extrêmes

x y e1 e2 e3 sol de base admiss. pt extrême

0 0 8 7 3 ✓ ✓ (0, 0)
0 8 0 -9 -5 ✓ ×
0 3.5 4.5 0 -0.5 ✓ ×
0 3 5 1 0 ✓ ✓ (0, 3)
4 0 0 3 3 ✓ ✓ (4, 0)
7 0 -6 0 3 ✓ ×
0 0 × ×
3 2 0 0 1 ✓ ✓ (3, 2)
2.5 3 0 -1.5 0 ✓ ×
1 3 3 0 0 ✓ ✓ (1, 3)

Pr. Abdessamad Kamouss 64 Recherche opérationnelle 64 / 102

Résolution de PL - Méthode Simplexe

PLS - Bases et points extrêmes

Base voisine et pivotage

Bases voisines

Deux sommets voisins correspondent à deux

bases B et B′ telles qu’on remplace une va-
riable de B pour obtenir B′

=⇒ passer à un sommet voisin = changer de base (base voisine).

C’est le principe du pivotage.

Pr. Abdessamad Kamouss 65 Recherche opérationnelle 65 / 102

Résolution de PL - Méthode Simplexe

PLS - Simplexe

Algorithme du simplexe
Dantzig, 1947.
Algorithme itératif de résolution de problème de programmation linéaire.

Principe
A partir d’un sommet, chercher un sommet voisin qui améliore la fonction
objectif.

Propriété du problème
Soit X0 un sommet non optimum.
Alors il existe X , un sommet voisin de X0 , tel que f (X) > f (X0 ).

=⇒ On peut procéder d’une manière itérative jusqu’à l’obtention d’une

solution optimale
Pr. Abdessamad Kamouss 66 Recherche opérationnelle 66 / 102
Résolution de PL - Méthode Simplexe : Exemple

Transformer le (PL) sous sa forme standard (PLS) .

 

 Maximizer z = 4x + 5y 
 Maximizer z = 4x + 5y
2x + y ≤8  2x + y + e1 =8

 


x + 2y ≤7 ⇔ x + 2y + e2 =7
y ≤3 y + e3 =3

 


 

≥0 x, y, e1 , e2 , e3 ≥0
 
x, y

Trouver une solution de base admissible initiale. Par exemple {e1 , e2 , e3 }

 
 2x + y + e1 = 8  e1 = 8 − 2x − y
x + 2y + e2 = 7 ⇔ e2 = 7 − x − 2y
y + e3 = 3 e3 = 3 − y
 

On obtient donc x = y = 0 et (e1 , e2 , e3 ) = (8, 7, 3).

Donc {e1 , e2 , e3 } : variables de base et {x, y} variables hors base.
La valeur de la fonction objectif est z = 0.

Pr. Abdessamad Kamouss 67 Recherche opérationnelle 67 / 102

Résolution de PL - Méthode Simplexe : Exemple

Déterminer la solution de base admissible voisine (une variable entrante

et une variable sortante) qui permet d’augmenter la valeur de la fonction
objectif z :
Regardons bien : z = 4x + 5y
On peut faire augmenter z en faisant entrer x ou y dans la base. On prends y
vu qu’elle a le plus grand coefficient positif.
Quelle est la valeur maximale que pourra prendre y ?

 e1 = 8 − 2x − y ≥ 0 ⇒ y ≤ 8
e2 = 7 − x − 2y ≥ 0 ⇒ y ≤ 3.5
e3 = 3 − y ≥ 0 ⇒ y ≤ 3


Le max de y est 3 , pour y = 3, on obtenons e1 = 5 − x, e2 = 1 − x et e3 = 0.

Nouvelle base candidate :

{e1 , e2 , e3 } ∪ {y}\ {e3 } = {e1 , e2 , y}

Pr. Abdessamad Kamouss 68 Recherche opérationnelle 68 / 102

Résolution de PL - Méthode Simplexe : Exemple

 
 e1 = 8 − 2x − y  e1 = 5 − 2x + e3
e2 = 7 − x − 2y ⇔ e2 = 1 − x + 2e3
e3 = 3 − y y = 3 − e3
 

On exprime z en fonction des variables hors base :

z = 4x + 5y
z = 15 + 4x − 5e3
=⇒ Solution de base associée : x = e3 = 0

 e1 = 5 − 2x + e3 = 5
e2 = 1 − x + 2e3 = 1
y = 3 − e3 = 3


Donc (e1 , e2 , y) = (5, 1, 3) et la fonction objectif prends la valeur z = 15.

Pr. Abdessamad Kamouss 69 Recherche opérationnelle 69 / 102

Résolution de PL - Méthode Simplexe : Exemple

z = 15 + 4x − 5e3
Augmenter encore z ? Faire entrer x
Quelle est la valeur maximale que pourra avoir x ?

e1 = 5 − 2x + e3 ≥ 0 ⇒ x ≤ 2.5

e2 = 1 − x + 2e3 ≥ 0 ⇒ x ≤ 1

y = 3 − e3 ≥ 0 ⇒ pas de contrainte


Le max de x est 1, et e2 peut sortir de la base.

Nouvelle base candidate : {e1 , x, y}

e1 = 3 + 2e2 − 3e3



 x = 1 − e + 2e

2 3


 y = 3 − e3

z = 19 − 4e2 + 3e3

Pr. Abdessamad Kamouss 70 Recherche opérationnelle 70 / 102

Résolution de PL - Méthode Simplexe : Exemple

z = 19 − 4e2 + 3e3
Augmenter encore z ? Faire entrer e3
Quelle est la valeur maximale que pourra avoir e3 ?

e1 = 3 + 2e2 − 3e3 ≥ 0 ⇒ e3 ≤ 1

x = 1 − e2 + 2e3 ≥ 0 ⇒ pas de contrainte

y = 3 − e3 ≥ 0 ⇒ e3 ≤ 3


Le max de e3 est 1, et e1 peut sortir de la base.

Nouvelle base candidate : {e3 , x, y}

e3 = 1 + 2/3e2 − 1/3e1




 x = 3 + 1/3e + 2/3e
2 1


 y = 2 − 2/3e2 + 1/3e1

z = 22 − 2e2 − e1
Pr. Abdessamad Kamouss 71 Recherche opérationnelle 71 / 102
Résolution de PL - Méthode Simplexe : Exemple

Finalement, on a :
z = 22 − 2e2 − e1
donc z∗ ≤ 22.

Or la solution de base x = 3, y = 2 et e3 = 1 permet d’obtenir la valeur

optimale de la fonction objectif z∗ = 22.

=⇒ Donc on a trouvé l’optimum

Pr. Abdessamad Kamouss 72 Recherche opérationnelle 72 / 102

Contenu du module

Pr. Abdessamad Kamouss 73 Recherche opérationnelle 73 / 102

Dualité - Introduction

Définition (Dualité)
La dualité fait référence à la relation entre un problème d’optimisation
appelé "problème primal" et un autre problème associé appelé
"problème dual".
Chaque problème est formulé de manière complémentaire, et les
solutions des deux problèmes sont liées.
Cela permet :
d’obtenir des informations supplémentaires
de simplifier la résolution du problème primal.
avoir une autre vision du problème.
réaliser un équilibre sur un marché.
...

Pr. Abdessamad Kamouss 74 Recherche opérationnelle 74 / 102

Problème Dual - Vision économique

Exemple (Vision du Primal)

Une societé META fabrique, deux articles P1 et P2 qu’elle vend à des
grossistes aux prix respectifs de 320 et 550 UM.
La fabrication de ces deux produits P1 et P2 nécessite l’utilisation de trois
machines différentes M1 , M2 et M3 pendant des temps exprimés en heures
dans le tableau suivant :

M1 M2 M3 Prix
P1 50 30 20 320
P2 10 20 15 550
Disponibilités 600 500 300 -

But
Maximiser le profit obtenu par la fabrication et la vente des produits P1 et P2 .

Pr. Abdessamad Kamouss 75 Recherche opérationnelle 75 / 102

Problème Primal

Exemple (Vision du Primal)

On considère les variables suivantes :
x1 la quantité produite de P1 .
x2 la quantité produite de P2 .
On peut modiliser le problème PRIMAL de la manière suivante :

[Max]z = 320x1 + 550x2


 50x1 + 10x2 ≤ 600
sc 30x1 + 20x2 ≤ 500
20x1 + 15x2 ≤ 300

x1 ≥ 0, x2 ≥ 0.

Pr. Abdessamad Kamouss 76 Recherche opérationnelle 76 / 102

Problème Dual - Vision économique

Exemple (Vision du Dual)

Maintenant un autre fabriquant VISION souhaite produire les mêmes
produits P1 et P2 mais ne dispose pas des disponibilités nécessaires au
niveau de ses ateliers.
Pour cela, il souhaite acheter l’utilisation des disponibilités 600h, 500h et
300h des machines M1 , M2 et M3 respectivement pour produire P1 et P2 .
Il cherche à déterminer le prix unitaire d’achat de chaque heure de ces
machines afin de faire une proposition minimale convaincante au
fabriquant META.

But
Minimiser le coût d’acquisition des ressources M1 , M2 et M3 tout en restons
concurrentiel.

Pr. Abdessamad Kamouss 77 Recherche opérationnelle 77 / 102

Problème Dual - Vision économique

Exemple (Vision du Dual)

Pour cela on considère les variables suivantes :
y1 le coût d’achat d’une heure d’utilisation de M1 .
y2 le coût d’achat d’une heure d’utilisation de M2 .
y3 le coût d’achat d’une heure d’utilisation de M3 .
On peut modéliser donc le problème DUAL comme suit :

[Min]w = 600y1 + 500y2 + 300y3


50y1 + 30y2 + 20y3 ≥ 320
sc
10y1 + 20y2 + 15y3 ≥ 550
y1 , y2 , y3 ≥ 0.

Pr. Abdessamad Kamouss 78 Recherche opérationnelle 78 / 102

Problèmes Primal - Dual - Vision économique

Pour le fabriquant META : On cherche à déterminer le plan de fabrication

permettant de maximiser le profit.

Pour le fabriquant VISION : On cherche à déterminer l’offre d’achat

permettant de minimiser le coût de sa production.

PRIMAL vs DUAL
[Max]z
 = 320x1 + 550x2 [Min]w
 = 600y1 + 500y2 + 300y3
 50x1 + 10x2 ≤ 600
50y1 + 30y2 + 20y3 ≥ 320
sc 30x1 + 20x2 ≤ 500 sc
10y1 + 20y2 + 15y3 ≥ 550
20x1 + 15x2 ≤ 300

y1 , y2 , y3 ≥ 0.
x1 ≥ 0, x2 ≥ 0,

Pr. Abdessamad Kamouss 79 Recherche opérationnelle 79 / 102

Problèmes Primal - Dual

Dualité
La dualité est un concept important en Recherche Opérationnelle.
Tout programme linéaire admet un programme dual. Le premier est alors
appelé PRIMAL et le second est son DUAL.
Le DUAL a une interprétation économique différente du PRIMAL .
Le DUAL et le PRIMAL sont liés et on peut trouver la solution de l’un dès
que la solution de l’autre est bien connue.
La recherche du DUAL peut souvent s’imposer si l’on voit que le PRIMAL
parait difficile à résoudre.

Pr. Abdessamad Kamouss 80 Recherche opérationnelle 80 / 102

Problèmes Primal - Dual : Définition

Matrice A de taille m × n
Vecteurs c ∈ Rn et b ∈ Rm .
Définition (problème dual)
Au programme linéaire primal

⊤
  
 maxx∈R n F(x) = c x

(PL) Ax ≤ b
x≥0


on associe le programme linéaire dual

⊤
  
 min m G(y) = b y
 y∈R
(PLD) A⊤ y ≥ c
y≥0


Pr. Abdessamad Kamouss 81 Recherche opérationnelle 81 / 102

Problèmes Primal - Dual

Programme linéaire primal Programme linéaire dual

maxn F(x) = c⊤ x minm G(y) = b⊤ y

   
x∈R  y∈R  ⊤
Ax ≤ b A y≥c
(PL) (PLD)
x≥0 y≥0
Comparaison primal/dual.
Primal Dual
max(F) ↔ min(G)
coefficient c de F ↔ second membre c
second membre b ↔ coefficient b de G
m contraintes inégalités (Ax ≤ b) ↔ m contraintes de positivité (y ≥ 0)

n contraintes de positivité (x ≥ 0) ↔ n contraintes inégalités A⊤ y ≥ c

Pr. Abdessamad Kamouss 82 Recherche opérationnelle 82 / 102

Problèmes Primal - Dual

Règles de passage :
Min Max
Primal Dual
Dual Primal
Variable ≥ 0 Contrainte ≤
Variable ≤ 0 Contrainte ≥
Variable ≶ 0 Contrainte =
Contrainte ≤ Variable ≤ 0
Contrainte = Variable ≶ 0
Contrainte ≥ Variable ≥ 0

Pr. Abdessamad Kamouss 83 Recherche opérationnelle 83 / 102

Problèmes Primal - Dual

Exemple
Donner le proramme dual du programme primal suivant :


 [Max]z
 = 4x1 + 5x2 + 2x3



 
 2x1 + 4x2 = 3
x1 + x3 ≥ 2
 
(PL) : sc
3x + x2 + x3 ≤ 10
 1

 

x2 + x3 ≤ 1




x1 ≥ 0, x2 ≤ 0, x3 ≥ 0


Le programme dual du primal précédent est :



 [Min]w
 = 3y1 + 2y2 + 10y3 + y4
 2y1 + y2 + 3y3 ≥ 4



(PLD) : sc 4y1 + y3 + y4 ≤ 5
y2 + y3 + y4 ≥ 2

 


y1 ≶ 0, y2 ≤ 0, y3 ≥ 0, y4 ≥ 0


Pr. Abdessamad Kamouss 84 Recherche opérationnelle 84 / 102

Problèmes Primal - Dual

Exemple
Donner le proramme dual du programme primal suivant :


 [Max]z
 = 4x1 + 5x2 + 2x3



 
 2x1 + 4x2 = 3
x1 + x3 ≥ 2
 
(PL) : sc
3x + x2 + x3 ≤ 10
 1

 

x2 + x3 ≤ 1




x1 ≥ 0, x2 ≤ 0, x3 ≥ 0


Le programme dual du primal précédent est :



 [Min]w
 = 3y1 + 2y2 + 10y3 + y4
 2y1 + y2 + 3y3 ≥ 4



(PLD) : sc 4y1 + y3 + y4 ≤ 5
y 2 + y3 + y4 ≥ 2

 


y1 ≶ 0, y2 ≤ 0, y3 ≥ 0, y4 ≥ 0


Pr. Abdessamad Kamouss 84 Recherche opérationnelle 84 / 102

Dualité - Théorèmes

Propriété
Le dual du dual est le primal.

Preuve. On considère un programme linéaire (PL) sous forme canonique.

Alors son dual (PLD) est :

⊤ maxy −G(y) = (−b)⊤ y

     
 y⊤ G(y) = b y
 min  
(PLD) A y≥c ⇐⇒ (PLD) −A⊤ y ≤ −c
y≥0 y≥0
 

On prend le dual du dual :

⊤x
  
( x (−c)
 min maxx c⊤ x
  
  

⊤
(PLDD) −A⊤ x ≥ −b ⇐⇒ (PL) Ax ≤ b
x≥0
 
 x≥0

Pr. Abdessamad Kamouss 85 Recherche opérationnelle 85 / 102

Dualité - Théorèmes

Théorème (THÉORÈME FAIBLE DE DUALITÉ)

Soit x une solution réalisable d’un (PL) sous forme canonique et y une
solution réalisable du problème dual (PLD). Alors :
1 F(x) ≤ G(y)
2 Si F(x) = G(y) alors x et y sont des solutions optimales de (PL) et
(PLD) respectivement.

Preuve.
1 On a Ax ≤ b, x ≥ 0 et A⊤ y ≥ c, y ≥ 0.
 ⊤
F(x) = c⊤ x ≤ A⊤ y x = y⊤ |{z}
Ax ≤ y⊤ b = G(y)
≤b
2 Soient x∗ et y∗
des solutions réalisables de (PL) et (PLD) telles que
F (x∗ )
= G (y∗ ).
D’après 1., pour x solution réalisable de ( PL), on a
F(x) ≤ G (y∗ ) = F (x∗ ) donc x∗ est une solution réalisable optimale.
Idem pour y∗ .
Pr. Abdessamad Kamouss 86 Recherche opérationnelle 86 / 102
Dualité - Théorèmes

Théorème (THÉORÈME FORT DE DUALITÉ)

Si le problème primal (PL) admet une solution réalisable optimale x∗ alors le
problème dual (PLD) admet lui aussi une solution réalisable optimale y∗ avec

F (x∗ ) = G (y∗ ) .

Preuve. Preuve. On suppose (PL) mis sous forme standard. S’il existe une
solution réalisable optimale, alors il existe une solution de base réalisable
optimale xB∗ = A−1B∗ b. On choisit alors

⊤
y∗ = A−1
B∗ c B∗ .
On montre que y∗ est une solution réalisable optimale pour le dual (PLD).

Pr. Abdessamad Kamouss 87 Recherche opérationnelle 87 / 102

Dualité - Théorèmes

Rappel : Il y a 3 cas possibles (et seulement 3) pour le problème primal (PL) :

1 il existe (au moins) une solution optimale.
2 l’ensemble DR des solutions réalisables n’est pas borné et l’optimum est
infini.
3 pas de solution réalisable (DR = 0)
/ .

Théorème (Relations entre solutions de (PL) et (PLD))

Etant donnés un problème primal (PL) et son dual (PLD), une et une seule
des trois situations suivantes a lieu
a les deux problèmes possèdent chacun des solutions optimales (à
l’optimum, les coûts sont égaux).
b un des problèmes possède une solution réalisable avec un optimum
infini, l’autre n’a pas de solution.
c aucun des deux problèmes ne possède de solution réalisable.

Pr. Abdessamad Kamouss 88 Recherche opérationnelle 88 / 102

Dualité - Conditions d’optimalité primal-dual (COPD)

On se place dans le cas (a) où les problèmes primal et dual possèdent chacun
des solutions optimales (optimum fini).

Théorème (COPD)
Soient x et y des solutions réalisables respectivement du problème primal
(PL) et du problème dual (PLD).
Alors x et y sont des solutions réalisables optimales si et seulement si les
conditions d’optimalité primal-dual (COPD) suivantes sont vérifiées :
Si une contrainte est satisfaite en tant qu’une inégalité stricte (PL) ou
(PLD) alors la variable correspondante de l’autre programme est nulle.
Si la valeur d’une variable dans (PL) ou (PLD) est strictement positive
alors la contrainte correspondante de l’autre programme est une
égalité.

Pr. Abdessamad Kamouss 89 Recherche opérationnelle 89 / 102

Dualité - Conditions d’optimalité primal-dual (COPD)

x∗ et y∗ solutions réalisables optimales de (PL) et (PLD) respectivement.

 n


 • ∑ ai j · x∗j < bi ⇒ y∗i = 0
j=1






 m
∑ ai j · y∗i < c j x∗j = 0

 • ⇒


i=1

 n


 • y∗i > 0 ⇒ ∑ ai j x∗j = bi
j=1






 m
 • x∗j > 0 ∑ ai j y∗i = c j

⇒


i=1

Pr. Abdessamad Kamouss 90 Recherche opérationnelle 90 / 102

Problèmes Primal - Dual

Exemple (Passage entre Primal et Dual)

Considérons le (PL) suivant et son dual (PLD) .

[Max] z = 4x1 + 5x2 
[Min] w = 8y1 + 7y2 + 3y3


 2x1 + x2 ≤8

 

2y1 + y2 ≥ 4

(PL) x1 + 2x2 ≤7 (PLD)
y + 2y2 + y3 ≥ 5
x2 ≤3  1

 

y1 , y2 , y3 ≥ 0


x1 , x2 ≥0


La solution optimale de (PL) est x1∗ = 3, x2∗ = 2 et z∗ = 22.

Vu que la 3ème contrainte du (PL) n’est pas saturée alors y3 = 0.
Vu que x1∗ > 0 et x2∗ > 0 alors 2y1 + y2 = 4 et y1 + 2y2 + y3 = 5.
On obtient alors

y∗1 = 1, y∗2 = 2, y∗3 = 0, et w∗ = 22

Pr. Abdessamad Kamouss 91 Recherche opérationnelle 91 / 102