ENP d’ORAN "Maurice Audin" OPTIMISATION & FIABILITÉ

Département de Génie Mécanique Semestre 4

ÉCOLE NATONALE POLYTECHNIQUE

ENP D’ORAN - MAURICE AUDIN

DÉPARTEMENT DE GÉNIE MÉCANIQUE

MÉTHODES NUMÉRIQUES D’OPTIMISATION

APPLICABLES EN MÉCANIQUE ET LEURS
COMPARAISONS

« MÉTHODES GRAPHIQUES »
« MÉTHODES ALGÉBRIQUES »

Enseignant : Dr. Sid Ali LITIM

I. Introduction à la recherche opérationnelle

La recherche opérationnelle aussi appelée « Aide à la décision » est une méthode d'analyse
scientifique d'un problème. Cette méthodologie est un mélange d'analyse et de méthodes
mathématique réunies pour aider un décideur à prendre une décision (Figure1).
Elle consiste à recevoir un maximum d'information sur le problème afin de proposer des
solutions mais surtout pas de décider laquelle est la meilleure. La solution choisie dépend
surtout des intérêts du décideur.

Figure 1. Processus d’aide à la décision

La modélisation mathématique peut se décliner en plusieurs types d’optimisation : la

programmation linéaire, la programmation non linéaire, le contrôle optimal...
Un modèle est une représentation mathématique d’un problème issu de la réalité. La
programmation linéaire est un outil qui permet de résoudre différents problèmes
d’optimisation, le but essentiel est d’introduire le principe de modélisation et le rôle de la
programmation mathématique (Figure 2 et 3).

Figure 2. Étapes de la modélisation

1
 Figure 3. Étapes détaillés de la modélisation (décrire le problème, prescrire une solution,
actualiser la solution)

I.1 Concept de modèle en Aide à la Décision :

Représentation abstraite (relations, équations...) d’un problème de décision en trois étapes :

1. Identification du problème et modélisation

2. Conception et application de méthodes de résolution.
3. Intégration et mise en œuvre dans le processus de décision

II. Historique de la Recherche Opérationnelle (RO) :

La RO est apparue en Grande-Bretagne durant la Seconde Guerre mondiale, lorsqu’on décida

d'employer des méthodes scientifiques pour étudier divers aspects des opérations militaires
(placements de radar, gestion des convois, etc.).
Depuis lors, la RO est devenue un élément important du processus de prise de décision dans
de nombreux contextes commerciaux, industriels et gouvernementaux, car elle permet
d'appréhender de façon systématique la complexité toujours grandissante des problèmes de
gestion auxquels est confronté tant dans le secteur privé que public.

A la suite des succès obtenus dans le domaine militaire durant la Seconde Guerre mondiale, la
RO a été appliquée durant de nombreuses années à des problèmes de nature opérationnelle
dans l'industrie et le secteur public. Depuis une dizaine d'années, le champ d'application de la
RO s'est élargi à des domaines comme l'économie, la finance, le marketing et la planification
d'entreprise. Plus récemment, la RO a été utilisée pour la gestion des systèmes de santé et de
recherche, pour la résolution de problèmes environnementaux et dans d'autres domaines
d'intérêt public .

2
III. La programmation linéaire.

III.1. Introduction

En général, un programme linéaire (PL) est un problème d'optimisation consistant à

maximiser (ou minimiser) une fonction objectif linéaire de n variables de décision
soumises à un ensemble de contraintes exprimées sous forme d'équations ou d'inéquations
linéaires.
A l’origine, le terme programme a le sens de planification opérationnelle mais il est
aujourd'hui employé comme synonyme de problème (d'optimisation).

Nous commencerons par le cas des problèmes linéaires, c’est-à-dire les problèmes où la
fonction objectif et les contraintes sont purement linéaires. Lorsqu’il n’y à que deux variables
de décision, un problème linéaire peut être résolu de manière purement graphique. Lorsqu’il y
a un plus grand nombre de variables, un algorithme mis en œuvre sous la forme d’un
programme informatique s’avère nécessaire, Il s’agit de l’algorithme du Simplexe, nous
examinerons une question très importante : à savoir la sensibilité de la solution à des
modifications de données [1].

III.2. Mise en forme mathématique d’un PL (Modélisation) :

III.2.1. Définir les variables de décision

• ensemble des variables qui régissent la situation à modéliser
• variables réelles, entières, binaires
III.2.2. Préciser la fonction objectif
• fonction mathématique composée des variables de décision qui représente le
modèle physique modélisé
• fonction linéaire, non-linéaire
III.2.3. Préciser les contraintes du problème
• ensemble des paramètres qui limitent le modèle réalisable
• équations ou inéquations composées des variables de décision
III.2.4. Préciser les paramètres du modèle
• Constantes associées aux contraintes et à la fonction objectif.
III.3. Formulation d’un problème de programmation linéaire (P.L.):

Dans le cas d’un Programme Linéaire la fonction à optimiser et les contraintes à respecter
sont linéaires (variables au premier degré).Une représentation courante d'un programme
linéaire, appelée forme canonique, correspond à la formulation suivante :

III.3.1. Fonction objectif (économique) :

Maximiser ou minimiser
z = c1 x1 + c2 x2 + c3 x3 + ….… + cn xn

Sous contraintes (explicites)

a11 x1 + a12 x2 + a13 x3 + …....+ a1n xn (≤, =, ≥) b1
a21 x1 + a22 x2 + a23 x3 + …...+ a2n xn (≤, =, ≥) b2
am1 x1 + am2 x2 + am3 x3 + ….+ amn xn (≤, =, ≥) bm

3
 Contraintes de non-négativité (Signes / implicites)
xj≥ 0 ; j = 1, 2, 3, … n
Avec
xj : variables de décision (inconnues)
aij, bi, cj : paramètres du programme linéaire

• Les a ij sont des coefficients techniques, issus du processus étudié ; les bi représentent le
plus souvent des seuils d’activité ou des quantités de ressources disponibles.
• les c j sont des bénéfices ou des coûts issus de la comptabilité.

En bref :
Un Programme Linéaire ( PL )
Problème d’optimisation consistant à :
- Maximiser (ou minimiser) une fonction objectif linéaire
- de n variables de décision
- Soumises à un ensemble de contraintes (explicites) exprimées sous forme d’équations ou
d’inéquations linéaires
La terminologie est due à George B. Dantzig, inventeur de l’algorithme du simplexe (1947)

III.4. Rappels de géométrie

III.4.1. Ensembles convexes [2] :

Un ensemble D⊆IRn est convexe si pour tout x1, x2 ∈D

xλ= λx1 + (1 − λ)x2∈D quel que soit λ ∈[0, 1].
Autrement dit, un ensemble D est convexe si et seulement si tout segment de droite reliant
deux points de D est entièrement contenu dans D.

Figure 4. Domaine convexe Figure 5. Domaine non convexe

4
Théorème 1
Un ensemble D est convexe si et seulement si toute combinaison convexe de points de D
appartient à D.
Autrement dit, un ensemble D est convexe si et seulement s’il est égal à l’enveloppe convexe
de ses points, c’est-à-dire à l’ensemble de toutes les combinaisons convexes de ses points.

Théorème 2
Soit {Di, i ∈I } une famille d’ensembles convexes, alors leur intersection D ∩ Di est un
ensemble convexe.

III.4.2 Polyèdres et polytopes

Un polyèdre
P ⊆Rn est l’intersection d’un nombre fini de demi-espaces fermés.
Un polyèdre est un ensemble convexe fermé et peut s’écrire :
P = {x ∈IRn | aix ≤ bi, i = 1, . . . ,m} = {x ∈Rn | Ax ≤ b} .

Un polytope est un polyèdre borné.

Figure 6. Polyèdre Figure 7. Polytope

III.4.3. Caractérisation géométrique des solutions optimales

Théorème 1

1. Si D est un polytope:

• soit la solution optimale est unique et est située en un sommet de D

• soit il existe une infinité de solutions optimales qui sont les points d’une face de D, ces
solutions optimales sont donc combinaisons convexe d’un nombre fini de sommets

2. Si D est un polyèdre convexe, non vide mais borné, en plus des situations décrites ci-
dessus, il est possible que le problème n’ait pas de solution optimale à distance finie, il existe
alors une solution admissible (à l’infini) telle que z = 1.

3. Si D est un ensemble vide, le problème n’a pas de solution optimale.

5
III.5. Solution graphique d’un PL

Comme annoncé dans l’introduction, dans le cas de deux variables de décision, un problème
linéaire peut être résolu de manière purement graphique en suivant le processus en trois étapes
qui suit.

La première étape de la résolution consiste à choisir les variables de décision du problème.

- Définition 5.1 : On appelle variable de décision toute quantité utile à la

résolution du problème dont le modèle doit déterminer la valeur.

- La deuxième étape consiste à formuler mathématiquement l’objectif (fonction

objectif).

- Définition 5.2 : On appelle fonction objectif d’un problème d’optimisation le

critère de choix entre les diverses solutions possibles.

- La troisième étape est la formulation les contraintes du problème.

- Définition 5.3 On appelle contraintes du problème toutes les relations limitant le

choix des valeurs possibles des variables.

- Enfin, et c’est la troisième tape de la résolution, l’optimum sera déterminé

graphiquement comme le plan de production situé sur la droite d’isoprofit
(Isomarges) la plus élevée, c’est-à-dire celle qui donne le profit le plus élevé.

III.5.1. Problème d’optimisation à 2 variables :

Exemple d’application :

Une usine produit deux modèles de machines, l’une que l’on appellera modèle A exige 2kg de
matière première et de 30 heures de fabrication et donne un bénéfice de 7 UM. L’autre que
l’on appellera B exige 4kg de matière première et de 15 heures de fabrication et donne un
bénéfice de 6 UM. On dispose de 200kg de matière première et de 1200 h de travail.
Quelle production doit-on avoir pour obtenir un bénéfice maximal ?

Mise en équations:

La production dépend de deux paramètres

– Le nombre de machine de modèle A

– Le nombre de machine de modèle B
On veut déterminer le nombre de machines de chaque modèle afin d’obtenir un bénéfice
maximal.

Solution :

– Soit x le nombre de machines de modèle A à produire

– Soit y le nombre de machines de modèle B à produire

6
Une première contrainte évidente : x et y sont tout deux positifs et plus exactement ce sont des
entiers naturels : x ≥ 0 et y ≥ 0. Il s’agit dans un premier temps de traduire l’énoncé en un
système

– Le modèle A exige 2kg de matière première et de 30 heures de fabrication et donne un

bénéfice de 7 UM :

x machines de modèle A représente 2x kg de matière première, 30x heures de fabrication et

un bénéfice de 7x UM.

– Le modèle B exige 4 kg de matière première et de 15 heures de fabrication et donne un

bénéfice de 6 UM :

y machines de modèle A représente 4y kg de matière première, 15y heures de fabrication et

un bénéfice de 6y UM

On pose x = x 1 et y = x 2

– On dispose de 200 kg de matière première : 2 x1 + 4 x 2 ≤ 200

– On dispose de 1200 h de travail : 30 x1 + 15 x 2 ≤ 1200
– Bénéfice z = 7 x 1 + 6 x 2

Les couples (x1, x2) d’entiers naturels doivent vérifier :

 2 x1 + 4 x 2 ≤ 200

 30 x1 + 15 x 2 ≤ 1200
 x1 ≥ 0 ; x 2 ≥ 0


Et doivent rendre maximum le nombre z = 7x1+ 6 x2.

Solution graphique :

Le programme Linéaire est donc comme suit :

Max z = 7 x1 + 6 x 2
 2 x1 + 4 x 2 ≤ 200 ......(∆1 )

SC  30 x1 + 15 x 2 ≤ 1200 ......(∆ 2 )
 x1 ≥ 0 ; x 2 ≥ 0


7
 Figure 8. Interprétation graphique de la solution optimale
(Exemple d’application à 2 variables de décision)

Le bénéfice maximum est donc atteint pour x1=20 et x2= 40 il est de :

z = 7 x1 + 6 x2 = 140 + 240 = 380 UM.

III.5.2. Problème d’optimisation à 3 variables :

III.5.2.1. Exemple d’application n° 1 [3] :

Une entreprise a la faculté de fabriquer, sur une machine donnée travaillant 45 heures par
semaine, trois types de produits différents P1, P2 et P3. Une unité du produit P1 laisse un profit
net de 4 UM, une de P2 un profit de 12 UM, et enfin, pour P3 de 3 UM. Les rendements de la
machine sont, respectivement pour les trois produits : 50, 25 et 75 articles par heure. On sait,
grâce à une étude de marché que les possibilités de vente ne dépassent pas 1000 unités de P1,
500 unités de P2 et 1500 unités de P3, par semaine.
1) Formuler le problème comme programme linéaire en définissant précisément les
variables de décision, la fonction objectif et les contraintes.
2) Quelle est la meilleure répartition de la capacité de production entre les trois produits, de
manière à maximiser le profit hebdomadaire.

Solution du PL :

Puisque notre exemple, ne comporte que trois variables, nous allons recourir à une méthode
géométrique en nous plaçant dans l’espace à 3 dimensions :

8
Données du problème

Un atelier fabrique 3 produits P1, P2 et P3 avec les cadences par produits suivantes :
P1 : 50 unités par heures
P2 : 25 unités par heures
P3 : 75 unités par heures

L’étude a permis de fixer un certain nombre de contraintes :

1. Contrainte de disponibilité: la machine permettant de fabriquer l'ensemble des produits

n'est disponible que 45 heures par semaine.

2. Contraintes de marché : chaque produit peut espérer se vendre, au mieux, à hauteur de :

P1 : 1000 unités
P2 : 500 unités
P3 : 1500 unités

3. Bénéfice unitaire :
P1 : 4
P2 : 12
P3 : 3

Étapes de Modélisation

1. définir les variables de décision :

x1 : nombre de produits P1
x2 : nombre de produits P2
x3 : nombre de produits P3

• Contraintes explicites :
- Contraintes de marché :
x1 ≤ 1000
x2 ≤ 500
x3 ≤ 1500

Contrainte de cadence et de disponibilité machine :

50 P1 en 1 heure 1 P1 en 1/50 d'heure
25 P2 en 1 heure 1 P2 en 1/25 d'heure
75 P3 en 1 heure 1 P3 en 1/75 d'heure

1 1 1
Avec la disponibilité machine : x1+ x2+ x 3 ≤ 45
50 25 75
Soit : 3x1 + 6x2 + 2x3≤ 6750

Fonction Économique :
z = 4x1 + 12x2 + 3x3

9
Le programme linéaire consiste à maximiser la fonction objectif z :
Max z = 4 x 1 + 12 x 2 + 3 x 3
 x1 + ≤ 1000 (1)

 x2 ≤ 500 (2)
SC  x3 ≤ 1500 (3)
3 x + 6 x + 2 x ≤ 6750 (4)
 1 2 3

x 1 , x 2 , x 3 ≥ 0

Rien ne nous empêche ici de recourir à la méthode géométrique, puisque nous n’avons que
trois variables et qu’il est facile de représenter un trièdre trirectangle dont les axes porteront
les quantités x1, x2, x3.
A priori, une solution du problème est représentée par point de l’espace, de coordonnées x1,
x2, x3, déterminées.
Les contraintes 5, 6 et 7 (non négativité) signifient d’ailleurs que nous pourrons nous centrer
de représenter le premier octant de ce système de coordonnées, puisque nous aurons ainsi x1,
x2 et x3 ≥ 0

Nous allons voir les contraintes 1 à 4 s’interprètent également d’une manière très aisée. Par
exemple, la contrainte 1 signifie que, dans l’octant positif, les points dont la coordonnée x1
excède 1000 sont exclus de l’espace des solutions. Or x1 représente un plan P1 normal à l’axe
ox1 au point x1 = 1000, x2 = 0 , x3 =0 ;toutes les solutions éventuelles du problème seront
donc comprises, dans l’octant positif , entre le plan x2Ox3 et le plan x1 = 1000.

On résonnerait de même pour les contraintes 2 et 3. En fait, les plansP1 : x1 = 1000, P2 : x2 =

500, P3 : x3 = 1500 déterminent le parallélépipède OABCDEFG, à l’intérieur ou à la surface
duquel se trouvent les solutions éventuelles.

D’autre part : 3x1 + 6x2 + 2x3 = 6750 est aussi l’équation d’un plan P4, dans l’espace à trois
dimensions et la contrainte 4 signifie que les points solutions doivent nécessairement se
retrouver à l’intérieur ou à la surface du tétraèdre OA’B’C’, fermé par les plans de
coordonnées et le plan P4 ; le plan P4 coupe Ox1 en A’ (2250, 0, 0), Ox2 en B’ (0, 1125,0) et
Ox3 en C’ (0, 0, 3375).
Il est facile de voir que le plan P4 coupe la droite FG au point P (1000, 125, 1500) ; en effet,
FG est l’intersection des droites :
 x1 = 1000

 x 3 = 1500
P4 a comme équation : 3x 1 + 6x 2 + 2x 3 = 6750
Si l’on remplace, dans cette équation x1 et x3 par leurs valeurs, on obtient :
3000 + 6x 2 + 3000 = 6750
d’où : x2 = 750 et x2 = 125

On établirait de même que P4 coupe GD en Q (250, 500, 1500) et GB en R (1000, 500, 375)
c’est le solide commun au parallélépipède OABCDEFG et au tétraèdre OA’B’C’ qui
contiendra les solutions ; on constate qu’il faut enlever au parallélépipède le petit tétraèdre
GPQR.
Finalement, pour satisfaire aux contraintes, un point solution doit nécessairement se trouver à
l’intérieur ou à la surface du polyèdre OABCDEFPQR.

10
Jusqu’à présent, nous sommes occupés que des contraintes ; pour choisir entre les solutions
que nous venons de déterminer celle (ou celles) qui est (ou sont) optimale (s), nous devons
chercher à maximiser le fonctionnelle : z = 4x 1 + 12x 2 + 3x 3

Figure 9. Polyèdre des contraintes

(Exemple d’application n°1 à 3 variables de décision)

Pour chaque point M (x1 = ξ, x2 = η, x3 = θ) de l’espace des solutions, z à une valeur donnée :
z (ξ, η, θ) = 4 ξ+ 12 η+ 3 θ.

Par exemple, pour le point C (0, 500, 0), on a z = 4 x (0) + 12 x (500) + 3 x (0) = 6000.
Mais, les points qui, tels C, donnent à z la valeur 6000 forment un plan P(z=6000), d’équation :
4x 1 + 12x 2 + 3x 3 = 6000
Représentons ce plan, qui coupe les axes ox1, ox2, ox3 et aux points I (1500, 0, 0),
C (0, 500, 0) et J (0, 0, 2000) (voir figure 10).

Tout plan Pz, quelle que soit sa valeur : Z = 4x 1 + 12x 2 + 3x 3

11
Représente un plan parallèle au plan P(z=6000).

La distance de l’origine à un plan Pz est :

z z
OH = = ⇒ z = 13.OH
4 2 +12 2 +32 13

Dès lors, pour maximiser la valeur de la fonction économique z, il suffira de tracer un plan
parallèle au plan ICJ, dont la distance à l’origine soit la plus grande possible et qui ait encore
au moins un point en commun avec le polyèdre des solutions admissibles OABCDEFPQR.

Il est facile de voir (au besoin à l’aide d’une épure de géométrie descriptive) que ce plan est
obtenu pour z = 11 500.

Il coupe Ox1 en α (2875 ; 0 ; 0), Ox2 en β (0 ; 958,33 ; 0) et Ox3 en γ (0 ; 0 ; 3833,33).

Son unique point de contact avec le polyèdre des solutions est le point Q (250, 500, 1500),
d’où la solution optimale :
x1 =250, x 2 = 500 et x 3 =1500

Figure 10. Polyèdre des contraintes

(Exemple d’application n°1 à 3 variables de décision)

12
III.5.2.2. Application n° 2 [4] :

Un chimiste prépare des mélanges chimiques en sachets dont les ingrédients de base issus
de trois poudres chimiques P1, P2 et P3. Pour préparer ces mélanges, il reçoit
hebdomadairement 2400 g du produit P1, 1200 g du produit P2et 1200 g du produit P3. Les
quantités utilisées pour chaque mélange et le profit réalisé sont donnés dans le tableau
suivant:

Quantité
M1 M2 M3 disponible
Poudre P1 (g) 30 30 20 2400
Poudre P2 (g) 10 10 20 1200
Poudre P3 (g) 30 10 10 1200
Profit (UM) 2 1,50 1

Sachant que le chimiste écoule tous les mélanges qu'il peut préparer à chaque semaine,
combien doit-il en préparer pour que son profit soit maximum.

• Posons xile nombre de sachet du mélange Mi

• Fonction économique: f(x1;x2;x3) = z = 2x1+ 1,5x2+ x3
• Contraintes (simplifiée par 10):

3 x 1 + 3x 2 + 2 x 3 ≤ 240
1 x + x + 2 x ≤ 120
 1 2 3

3 x 1 + x 2 + x 3 ≤ 120
x 1 , x 2 , x 3 ≥ 0

En bref la forme canonique s’écrit sous forme :

Max z = 2x 1 + 1,5x 2 + x 3
3 x 1 + 3x 2 + 2 x 3 ≤ 240
1 x + x + 2 x ≤ 120
 1 2 3

3 x 1 + x 2 + x 3 ≤ 120
x 1 , x 2 , x 3 ≥ 0

Question :
- Trouver le profit maximum de la fonction objectif z.

13
 Polyèdre des contraintes

Figure 11 (a, b c et d). Polyèdre des contraintes et solution optimale

Exemple d’application n°2 à 3 variables de décision.

14
IV. Références bibliographiques

[1] Laurent SMOCH, "Méthodes d’Optimisation-Cours pour Licence Professionnelle

Logistique", Université du Littoral, Cote d’Opale, Pole Lamartine, Septembre 2011

[2] Daniel DEWOLF, "Cours de Recherche opérationnelle", Université du Littoral, Maîtrise

AES, Dunkerque, Septembre 2003

[3] Mathieu Le Coz, "Formulation d'un problème de Programmation Linéaire", janvier 2005

[4] Jean-Philippe Javet, "Cours de Programmation linéaire", 2ème Option spécifique",

15