Cours 2

Programmation Linéaire

Mr. B. Benaïssa
Centre Universitaire – Nâama-

1
Plan

1. Programmation linéaire,
2. Programmation linéaire en nombres entiers,
3. Programmation par contraintes.
La programmation mathématique

englobe des outils comme :

• La programmation linéaire (encore appelée optimisation linéaire) : elle est utilisé

lorsque de grands volumes sont en jeu et lorsque les relations entre ces quantités
sont 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 du tout ê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 d’avoir les meilleures décisions.

• La programmation dynamique : adaptée aux cas où le problème décisionnel

possède 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.
 Définition de la Recherche Opérationnelle

 Operations Research (OR) is a discipline that deals with application of

advanced analytical methods to help make better decisions. (Wikipédia).

 Advanced analytical methods include mathematical logic, graph, network

analysis, Petri net, queuing theory, simulation etc.

Concevoir et implémenter des approches pour résoudre des problématiques liées

à des domaines diverses (informatique, médecine, économie, finance, militaire
etc.) jusqu’à satisfaction du (des) décideur (s).

4 Centre Universitaire Nâama

 Formulation d’un problème

 Objectifs du système (minimisation de coût, minimisation de

l’énergie dans les réseaux de capteurs, etc.)
 Facteurs contrôlables: Variables de décisions

 Facteurs non contrôlables: Contraintes et ceux imposés par

l’environnement

Exemple voyageur de commerce:

Objectif: Minimiser la longueur totale parcourue
Contraintes: Cycle Hamiltonien (pas de cycles parasites), les distances entre les sommets.

5
 Modélisation d’un problème
 Un modèle est une représentation d’une réalité.

Forme d’un modèle:

Mathématique (linéaire et non linéaire), graphe (toutes ses topologies:

arbre, arborescence, biparti etc.), réseau (toutes ses formes: Transport,
Pétri, Automate à états finis etc.), simulation, théorie des jeux etc.

• Traduire les objectifs et contraintes en termes de variables de

décision.

6
 Exemple de Modélisation
Soit le problème qu’on associe à un réseau R=(X, U, l)
Où:
X: L’ensemble des villes,
U: Les liens entre ces villes
l : la longueur entre ces villes
 Variables de décision: xij = 1 si l’arc (i, j) est emprunté et 0 sinon

7
Approches de résolution
 Méthodes exactes:
 Programmation linéaire (Simplexe et ses variantes)
 Programmation non linéaire avec ou sans contraintes (relaxation de Lagrange,
Khun Tecker)
 Programmation en nombres entiers (Branch and Bound)
 Arbre recouvrant (Algorithme Glouton: Kruskal)
 Cheminement (Algorithme Glouton:Djikstra, Bellman, Ford)
 Flôt (Ford et Fulkerson)
 Etc…

8
 Approches de résolution (2/2)

 Méthodes approchées
 Heuristiques (recherche locale)
 Algorithmes de construction (plus proche voisin, plus proche
insertion, meilleure insertion)
- Métaheuristiques (recherche globale)
 Algorithmes génétiques
 Recherche Taboo
 Recuit simulé
 Colonies de fournies etc.

9
 Classification naïve de problèmes
- Problème facile ou problème difficile

 Si le problème est "facile": Trouver un algorithme efficace.

 Si le problème est « difficile» et de "grande taille": Chercher une

solution approchée et garantir l’efficacité de cette solution.

10
 Quelques Applications(1/3)

 Parcours d’un graphe

(existence de chaîne, chemin, cycle et circuit)

 Programmation linéaire
(recherche d’une solution de base réalisable optimale parmi toutes les solutions de
bases réalisables)

 Problèmes de routage
dans les réseaux (ad-hoc, capteurs, DTN etc.): entre deux nœuds particuliers (facile), entre
n’importe quel couple de nœud du réseau (difficile).

 Découverte sémantique de services web:

Pour une requête d’un utilisateur, il s’agit de trouver un service (atomique ou virtuel)
parmi un nombre important de services celui qui satisfait cette requête .

11
Quelques Applications(2/3)

 Emplois du temps :
 Planifier n cours en un minimum de temps, certains cours ne
pouvant avoir lieu en parallèle (partage des ressources: classe
ou prof).

 Localisation d’entrepôts :
Combien faut-il créer d'entrepôts et où faut-il les installer de
façon à satisfaire tous les clients avec un coût total minimal?

Application réelle:
Algérie-Télecom où les entrepôts sont les stations de téléphonie

 Etc.

12
 Quelques Applications(3/3)
 Optimisation des tournées de véhicules dans les problèmes de
distribution, organisation des centres logistiques.

 Bin packing: est un problème algorithmique. Il s'agit de ranger

des objets avec un nombre minimum de boîtes.
- Problèmes de chargement en conteneurs des bateaux,
- Problème de stockage de l’information sur des supports.

 Voyageur de commerce, postier chinois

 Ordonnancement d’ateliers : Ordonnancer les passages sur les

machines(Facile: Aspect temporel, difficile: aspect ressources
 Etc.
13
 Programmation Linéaire

L'objectif de la P.L. est de trouver la valeur optimale d'une

fonction linéaire sous un système d'équations d'inégalités

de contraintes linéaires. La fonction à optimiser est
baptisée « fonction Objectif » et on la résout en utilisant
la "méthode simplexe" dont la représentation graphique
consiste en un "polygone des contraintes".

14
 Remarques
La programmation linéaire est beaucoup utilisée dans la
logistique, la finance d'entreprise ou encore en théorie de la
décision lorsque nous devons résoudre un jeu à stratégie mixte.
C'est pour cette raison que MS Excel intègre un outil appelé le
"solveur" dans lequel il existe une option appelée "modèle
supposé linéaire" qui alors impose l'utilisation du modèle du
simplexe.

15
 Exemple
Considérons un agriculteur qui possède des
terres, de superficie égale à H hectares, dans
lesquelles il peut planter du blé et du maïs.

L'agriculteur possède une quantité E d'engrais

et I la quantité totale d'insecticide.
Le blé nécessite une quantité E1 d'engrais par
hectare et I1 d'insecticide par hectare. Les
quantités correspondantes pour le maïs sont
notées E2 et I2.

Soit P1 le prix de vente du blé et P2 celui du maïs. Si l'on note

par x1 et x2 le nombre d'hectares à planter en blé et en maïs, alors le
nombre optimal d'hectares à planter en blé et en maïs peut être
exprimé comme un programme linéaire:
16
 Exemple (suite)
Soit P1 le prix de vente du blé et P2 celui du maïs. Si l'on note
par x1 et x2 le nombre d'hectares à planter en blé et en maïs, alors le
nombre optimal d'hectares à planter en blé et en maïs peut être
exprimé comme un programme linéaire:

Max P1x1 + P2x2 (maximiser le revenue Net)

Sous
Contrainte x1 + x2 ≤ H (borne sur le nombre total d’hectares)
E1x1 + E2x2 ≤ E (borne sur la quantité d’engrais)
I1x1 + I2x2 ≤ I (borne sur la quantité d’insecticides)
x1 ≥ 0, x2 ≥ 0 (on ne peut pas planter un nombre négatif d’hectares)

17
 Exemple

Une usine fabrique 2 pièces P1 et P2 usinées dans deux

ateliers A1 et A2. Les temps d'usinage sont pourP1 de 3 heures
dans l'atelier A1 et de 6 heures dans l'atelier A2 et pour P2 de 4
heures dans l'atelier A1 et de 3 heures dans l'atelier A2.

Le temps de disponibilité hebdomadaire de l'atelier A1 est de 160

heures et celui de l'atelier A2 de 180 heures.

La marge bénéficiaire est de :

-1200 pour une pièce P1
-1000 pour une pièce P2.

Quelle production de chaque type

doit-on fabriquer pour maximiser
la marge hebdomadaire?
18
 Exemple : Modélisation
Une usine fabrique 2 pièces P1 et P2 usinées dans deux ateliers A1 et A2. Les temps d'usinage sont
pourP1 de 3 heures dans l'atelier A1 et de 6 heures dans l'atelier A2 et pour P2 de 4 heures dans
l'atelier A1 et de 3 heures dans l'atelier A2.
Le temps de disponibilité hebdomadaire de l'atelier A1 est de 160 heures et celui de l'atelier A2 de 180
heures.
La marge bénéficiaire est de :1200.- pour une pièce P1 et 1000.- pour une pièce P2.
Quelle production de chaque type doit-on fabriquer pour maximiser la marge hebdomadaire?

 Le problème peut se formaliser de la façon suivante:

A1: 3x1 + 4x2 ≤ 160
A2: 6x1 + 3x2 ≤ 180
x1,x2 ≥ 0
La fonction économique ou « Objectif » à maximiser étant:

Max Z = 1200 x1 + 1000x2

19
 Résolution graphique

Résolution graphique du problème (ou méthode du "polygone des

contraintes") :
• Les contraintes économiques et de signe sont représentées
graphiquement par des demi-plans. Les solutions, si elles existent
appartiennent donc à cet ensemble appelé "région des solutions
admissibles"

20
Résolution graphique
Pour trouver les coordonnées des sommets, on peut utiliser le graphique si
les points sont faciles à déterminer.
Il s'agit donc de chercher à l'intérieur de ce domaine (connexe), le couple
(x1,x2) maximisant la fonction économique.
Or, l'équation Z est représentée par une droite de pente constante (-1.2)
dont tous les points (x1,x2) fournissent la même valeur Z pour la fonction
économique.
En particulier, la droite 1200x1 + 1000x2
passe par l'origine et donne une valeur
nulle à la fonction économique. Pour
augmenter la valeur de Z et donc la
fonction économique, il suffit d'éloigner
de l'origine (dans le quart de plan x1≥0,
x2 ≥0) la droite de pente (-1.2).

21
 Résolution analytique

 Voyons maintenant comment résoudre ce problème de manière

analytique avant de passer à la partie théorique.
 Nous avons donc le « système canonique » (exact)

A1: 3x1 + 4x2 ≤ 160

A2: 6x1 + 3x2 ≤ 180
x1,x2 ≥ 0
Max Z = 1200 x1 + 1000x2

Nous introduisons d'abord les "variables d'écarts" e1, e 2 afin de

transformer les 3 inégalités par des égalités. Le système d'équations
devient alors une "forme standard" :

22
 Résolution analytique
Algorithme

23
 Résolution analytique
1- Ajouter les variables d’écarts
Remarque: Il y a autant de variables d'écarts que d'inéquations!
A1: 3x1 + 4x2 + e1 = 160
Forme standard A2: 6x1 + 3x2 + e2 = 180
x1,x2,e1,e2 ≥ 0
Max Z = 1200 x1 + 1000x2
2- Déterminer une solution de base réalisable :
on pose : x1 = 0 ; x2 = 0
on a alors : e1 = 160
e2 = 180
 Z=0
donc Z n’est pas optimale on doit trouver une solution admissible

24
 Résolution analytique = Simplexe
Pour trouver cette solution on passe la méthode des tableaux :
Algorithme
1- Tracer le tableau
2- chercher la variable entrante A1: 3x1 + 4x2 + 1.e1 + 0. e2 = 160
3- chercher la variable sortante A2: 6x1 + 3x2 + 0.e1 + 1.e2 = 180
4- Mise à jours du tableau x1,x2,e1,e2 ≥ 0
5-Vérifier le critère de sortie
Max Z = 1200 x1 + 1000x2
 Tracer le tableau :
Variable hors base
Variable de base

x1 x2 e1 e2 Contraintes Rapport (K)

e1 3 4 1 0 160
e2 6 3 0 1 180
Fonction
Économique
1200 1000 0 0 0
Z
25
 Résolution analytique = Simplexe
 Trouver la variable entrante : Colonne de pivot

x1 x2 e1 e2 Contraintes Rapport (K)

e1 3 4 1 0 160
e2 6 3 0 1 180
Z 1200 1000 0 0 0
Pour trouver la colonne pivot, on remarque les coefficients de Z, et on prend le maximum.

Donc ici, la colonne 1 comporte le pivot  x1 est la variable entrante .

 Trouver la variable sortante : ligne de pivot
Pour trouver cette ligne, on calcule le rapport K

26
 Résolution analytique
On a :

x1 x2 e1 e2 Contraintes Rapport (K)

e1 3 4 1 0 160 160/3 =53,33
e2 6 3 0 1 180 180/6 = 30
Fonction
économique 1200 1000 0 0 0
Une fois le rapport K calculé, on prend le minimum pour chercher la ligne pivot :
ici la valeur est 30

L’intersection de la ligne et de la colonne nous donne le pivot = 6

x1 x2 e1 e2 Contraintes Rapport (K)
e1 3 4 1 0 160 160
e2 6 3 0 1 180 180
Z 1200 1000 0 0 0

27  Donc e2 est la variable sortante donc x1 prend la place de e2

 Résolution analytique
 mettre à jours la table :
C-à-dire : diviser la ligne du pivot par le pivot ; le pivot = 6
1. Ligne pivot/pivot
2. colonne pivot = 0 sauf la case du pivot reste = 1 même la ligne F.O. « Z »
x1 x2 e1 e2 Contraintes Rapport (K)
e1 3 4 1 0 160 160
x1 6/6
/6 3/6
/6 0/6
/6 1/6
/6 180/6
/6 180//6=30006
= 30
Z 1200 1000 0 0 0

x1 x2 e1 e2 Contraintes Rapport (K)

e1 3 4 1 0 160
x1 1 1/2 0 1/6 30
Z 1200 1000 0 0 0

28
 Résolution analytique
 Mettre à jours la table :
1. Ligne pivot/pivot 2. colonne pivot = 0 sauf le pivot reste = 1
x1 x2 e1 e2 Ct Rapport (K)
Li
-3Lp+Li e1 3 0 -3(1/2)+4 -3(0)+1 -3(1/6)+0 -3(30)+160

x1 1 1/2 0 1/6 30 Lp
Z -1200(1) +
1200 = -1200(1/2) -1200(1/6)
-1200Lp+Li
0 -1200(30) + 0
0 + 1000 +0
Lp : ligne de pivot Li : Ligne en cours

x1 x2 e1 e2 Ct Rapport (K)

e1 0 5/2 1 -1/2 70

x1 1 1/2 0 1/6 30
Z 0 400 0 -200 -36000

29
 Résolution analytique
On doit vérifier si la fonction est optimal ?
Comment ?
 Quelque soit les coefficient de Z ; il faut qu’ils soit ≤ 0
On remarque que pour x2 on a 400 > 0 donc la solution n’est pas optimale

x1 x2 e1 e2 Ct Rapport (K)

e1 0 5/2 1 -1/2 70 70/(5/2)=28

x1 1 1/2 0 1/6 30 30/(1/2) =60

Z 0 400 0 -200 -36000

Col Pivot
Max (Coef. (Z)) =400 >0 donc x2 est une variable entrante = colonne pivot.
Cherchons la ligne du pivot en calculons le rapport K = Ct/ColP

30
 Résolution analytique
On prend alors le min (K) = 28 >0

x1 x2 e1 e2 Ct Rapport (K)
Pivot = 5/2
Lpivot
e1 0 5/2 1 -1/2 70 70/(5/2)=28

x1 1 1/2 0 1/6 30 5/(1/2) =60

Z 0 400 0 -200 -36000

 Donc e1 est la variable sortante donc x2 prend la place de e1

 mettre à jours la table :
C-à-dire : diviser la ligne du pivot par le pivot ;
1. Ligne pivot/pivot 2. colonne pivot = 0 sauf le pivot reste = 1

x1 x2 e1 e2 Ct Rapport (K)
On divise par 5/2
Lp x2 0 1 2/5 -1/5 28

Li x1 1 0 -1/5 4/15 16 (-1/2)Lp+Li

Z 0 0 -160
(-400)(-1/5)-200
-47200 -400.28 -36000 (-400Lp+Li
=-120
31
 Résolution analytique
Le nouvel tableau est :

x1 x2 e1 e2 Ct Rapport (K)

x2 0 1 2/5 -1/5 28 19200

x1 1 0 -1/5 5/12 16 28000

Z 0 0 -160 -120 - 47200 47200

On remarque que pour cœf (Z) < 0 donc la solution est optimale

Ainsi les valeurs de

x1 = 16
x2 = 28
Z = 47200

Max Z = 1200 x1 + 1000x2

32
 Exercice
Soit le système d’inéquation suivant : Max Z = x1 + 2 x2
-3 x1 + 2 x2 ≤ 2
- x1 + 2 x2 ≤ 4
x1 + x2 ≤ 5 x1 ≥ 0 ; x2 ≥ 0

x1 x2 e1 e2 e3 Ct Rapport (K)
e1 -3 2 1 0 0 2 2/2 = 1

e2 -1 2 0 1 0 4 4/2 = 2

e3 1 1 0 0 1 5 5/1 = 5

Z 1 2 0 0 0

x1 x2 e1 e2 e3 Ct Rapport (K)
x2 -3/2 1 1/2 0 0 1

e2 -1 2 0 1 0 2

e3 1 1 0 0 1 5

33 Z 1 2 0 0 0
 solution
x1 x2 e1 e2 e3 Ct Rapport (K)
x2 -3/2 1 1/2 0 0 1 Lp

e2 2 0 -1 1 0 2 (-2)Lp+Li

e3 5/2 0 -1/2 0 1 4 -Lp+Li

Z 4 0 -1 0 0 (-2)Lp+Li

x1 x2 e1 e2 e3 Ct Rapport (K)
x2 -3/2 1 1/2 0 0 1 -2/3= -0.66

Lp
e2 2 0 -1 1 0 2 2/2 = 1

e3 5/2 0 -1/2 0 1 4 8/5

Z 4 0 -1 0 0 -2

On prend min(K) > 0 -> e2 sortante

solution

x1 x2 e1 e2 e3 Ct Rapport (K)
x2 -3/2 1 1/2 0 0 1 -2/3= -0.66

Lp
e2 2 0 -1 1 0 2 2/2 = 1

e3 5/2 0 -1/2 0 1 4 8/5

Z 4 0 -1 0 0 -2

x1 x2 e1 e2 e3 Ct Rapport (K)
x2 -3/2 1 1/2 0 0 1
Lp
e2 2/2=1 0/2=0 -1/2 1/2 0/2=0 2/2=1

e3 5/2 0 -1/2 0 1 4

Z 4 0 -1 0 0 -2
solution
x1 x2 e1 e2 e3 Ct Rapport (K)
x2 -3/2 1 1/2 0 0 1 3/2Lp+Li

Lp
x1 1 0 -1 1/2 0 1
(-5/2Lp+Li)
e3 5/2 0 -1/2 0 1 4

Z 4 0 -1 0 0 -2 (-4)Lp+Li

x1 x2 e1 e2 E3 Ct Rapport (K)
x2 0 1 -1/4 3/4 0 5/2

x1 1 0 -1/2 1/2 0 1

e3 0 0 3/4 -5/4 1 3/2

Z 0 0 1 -2 0 -6

On remarque que pour cœf (Z) > 0 donc la solution n’est pas optimale
solution

x1 x2 e1 e2 e3 Ct Rapport (K)
x2 0 1 -1/4 3/4 0 5/2 5/2  ¼ = 10

x1 1 0 -1/2 1/2 0 1 -2

e3 0 0 3/4 -5/4 1 3/2 2

Z 0 0 1 -2 0 -6

On prend la ligne du Min(Cœf (K)) > 0

Rapport
x1 x2 e1 e2 e3 Ct
(K)
x2 0 1 -1/4 3/4 0 5/2

x1 1 0 -1/2 1/2 0 1

e1 0 0 1 -5/4x4/3= -5/3 1x4/3=4/3 3/2x4/3=2

Z 0 0 1 -2 0 -6
solution

x1 x2 e1 e2 e3 Ct Rapport (K)
¼ Lp+Li
x2 0 1 -1/4 3/4 0 5/2

x1 1 0 -1/2 1/2 0 1 ½ Lp+Li

Lp
e1 0 0 1 - 5/3 4/3 2

Z 0 0 1 -2 0 -6 (-Lp+Li

x1 x2 e1 e2 e3 Ct Rapport (K)
x2 0 1 0 1/3 1/3 3

x1 1 0 0 -2/3 2/3 2

e1 0 0 1 - 5/3 4/3 2

Z 0 0 0 -1/3 -4/3 -8

On remarque que pour Cœf. (Z) ≤ 0 donc la solution est optimale

 Solution:

x1 x2 e1 e2 e3 Ct Rapport (K)
x2 0 1 0 1/3 1/3 3

x1 1 0 0 -2/3 2/3 2

e1 0 0 1 - 5/3 4/3 2

Z 0 0 0 -1/3 -4/3 -8

x2 = 3
Max Z = x1 + 2 x2
x1 = 2
Z=8

39
 Mr. B. Benaïssa
 Centre Universitaire – Nâama-