Modélisation Mathématique

La modélisation mathématique est essentielle dans de nombreux domaines

scientifiques et techniques. Elle permet de représenter, d’analyser et de prévoir
des phénomènes complexes en utilisant des outils mathématiques appropriés.
Elle consiste à formuler une description formelle d’un phénomène du monde
réel à l’aide de structures et d’outils mathématiques tels que les équations
différentielles, les algorithmes ou les statistiques.

Un modèle mathématique est une abstraction qui simplifie la réalité tout en

préservant ses aspects essentiels. Ce processus permet d’explorer divers
scénarios et d’en tirer des conclusions précises. Les modèles mathématiques
sont largement utilisés en physique, ingénierie, économie, biologie,
épidémiologie, informatique, sciences sociales, et bien d’autres domaines.

RAZAFINDRAIBE Fabrice

ESTI 2025
Définition et objectifs de la
modélisation
1 Définition

La modélisation mathématique consiste à formuler

une description formelle d’un phénomène du monde
réel à l’aide de structures et d’outils mathématiques
tels que les équations différentielles, les algorithmes
ou les statistiques.
Définition et objectifs de la
modélisation
2 Objectifs
L’objectif principal d’un modèle mathématique est de
fournir une description quantitative et précise d’un
phénomène afin d'expliquer, prédire, optimiser et
contrôler.

❑ En épidémiologie, les modèles permettent de prédire

la propagation d’une maladie et d’optimiser les
politiques de santé publique.
❑ En finance, ils servent à modéliser l’évolution des
marchés boursiers et à gérer les risques financiers.
❑ En ingénierie, ils permettent de simuler le
comportement des structures et des matériaux avant
leur fabrication.
Modèles déterministes vs stochastiques
Modèle déterministe Modèle stochastique
Un modèle est dit déterministe lorsque, pour un même Un modèle est stochastique s’il intègre des variables
ensemble de conditions initiales, il produit toujours le aléatoires, ce qui signifie que les résultats peuvent
même résultat. Ces modèles sont utilisés lorsque les varier pour des conditions initiales identiques. Ces
relations entre les variables sont connues avec modèles sont adaptés aux phénomènes où l’incertitude
certitude. joue un rôle important.

Exemples : La loi de Newton F=ma, qui décrit la relation Exemples : La modélisation du climat, qui incorpore
entre la force, la masse et l’accélération. L’équation de des variations aléatoires dues aux interactions
la chaleur, qui modélise la diffusion de la température atmosphériques. Les modèles financiers, qui intègrent
dans un matériau. l’incertitude des fluctuations boursières.
Modèles discrets vs continus
Modèle discret Modèle continu
Un modèle est discret lorsque les variables évoluent Un modèle est continu lorsque les variables évoluent
par étapes successives à des instants distincts. Ces de façon fluide dans le temps et l’espace, sans
modèles sont souvent utilisés pour représenter des interruption. Ces modèles sont souvent formulés à
processus en temps discret ou des systèmes l’aide d’équations différentielles.
composés d’entités distinctes.

Exemples : La croissance d’une population en Exemples : L’équation de diffusion de la chaleur, qui

générations successives (modèle de Malthus en décrit l’évolution continue de la température dans un
temps discret). Les algorithmes de simulation matériau. Les équations de Navier-Stokes en
numérique (ex : méthode d’Euler pour la résolution mécanique des fluides.
d’équations différentielles).
Formulation du modèle
Définir le problème
Quel phénomène souhaite-t-on modéliser ?

Identifier les variables et paramètres

Quels sont les paramètres influents et les variables
d’intérêt ?
Énoncer les hypothèses simplificatrices
Quelles approximations sont raisonnables ?

Traduire en langage mathématique

Utilisation d’équations, d’inégalités ou d’algorithmes
pour formaliser le modèle.

Pour modéliser la chute libre d’un objet, on peut utiliser l’équation

𝑦(𝑡) = 𝑦0 + 𝑣0 𝑡 − 12𝑔𝑡 2 . En économie, la loi de l’offre et de la demande
peut être modélisée par un système d’équations reliant prix et
quantités.
Analyse du modèle
Vérification Étude des propriétés
Vérifier si le modèle est Étudier les propriétés du
bien posé (existence et modèle (stabilité, sensibilité
unicité des solutions). aux paramètres).

Résolution
Résoudre le modèle analytiquement ou numériquement

En dynamique des populations, l’équation logistique

𝑑𝑁 𝑁
= 𝑟𝑁(1 − ) est étudiée pour analyser la stabilité
𝑑𝑡 𝐾
des populations. Une fois le modèle formulé, il doit être
analysé afin d’évaluer sa pertinence et sa robustesse.
Validation du modèle
Comparaison 1
Le modèle doit être confronté aux données
expérimentales ou réelles pour vérifier sa
capacité à reproduire correctement le phénomène 2 Prédictions
étudié. Si les prédictions du modèle sont proches des
observations, il peut être utilisé pour des
Ajustement 3 simulations et des prévisions.
Si les résultats sont incohérents, il faut ajuster les
hypothèses ou affiner le modèle.

En climatologie, les modèles de prévision sont validés en comparant les températures prédites aux observations
météorologiques. Le modèle doit être confronté aux données expérimentales ou réelles pour vérifier sa capacité à
reproduire correctement le phénomène étudié.
 Applications et perspectives

Physique et ingénierie Biologie et médecine Économie et finance

Mécanique des fluides, Modélisation des Modèles de

thermodynamique, épidémies, croissance
résistance des dynamique des économique, gestion
matériaux. populations. des risques.

Sciences sociales
Modélisation du comportement des populations, simulations
politiques.

Avec l’essor de l’intelligence artificielle et du calcul haute

performance, la modélisation devient un outil de plus en plus
puissant pour résoudre des problèmes complexes et prendre des
décisions éclairées.
 Exemple Simple

Marc souhaite investir dans une action qui lui

rapportera 10 % annuellement. Quel montant
aura‐t‐il au bout de l'année ?

Solution:
L'investissement initial de Marc est inconnu.
Définissons
𝑥 : le montant que Marc investit dans cette
action
Le montant accumulé à la fin de l'année sera

𝐱 + 𝟏𝟎%𝐱 = 𝐱 + 𝟎, 𝟏𝐱 = 𝟏, 𝟏𝐱
 Exemple 2
Le revenu annuel d’un vendeur de voiture ne peut être
obtenu que si le nombre de véhicules vendues de chaque
type est connu. Des variables doivent donc remplacer ces
quantités, toutes inconnues pour l'instant.
Définissons :
➢ 𝒙 : le nombre de camions vendues au cours de l'année
➢ 𝒚 : le nombre de voitures légères vendues au cours de
l'année
➢ 𝒛 : le nombre de voitures tout terrain vendues au
cours de l'année
Exemple 2
Chaque camion produit un revenu, en
millions, de 35. Si 𝑥 camions sont vendus,
un revenu de 35 fois 𝑥 sera obtenu. Le
même argument se répète aux autres types
de véhicule. Par conséquent :

𝒓𝒆𝒗𝒆𝒏𝒖 𝒕𝒐𝒕𝒂𝒍 = 𝟑𝟓𝒙 + 𝟐𝟎𝒚 + 𝟐𝟓𝒛

Exemple 3
Les trois phases d'un projet doivent s'effectuer de façon
séquentielle, ce qui signifie qu'une phase ne peut pas débuter
avant que la phase précédente soit terminée. On sait que le coût de
réalisation de chacune des phases se décompose en un coût fixe,
indépendant de sa durée, et en un coût variable qui en dépend. Le
tableau suivant résume la situation:
PHASE 1 2 3

COÛT FIXE 318 000 Ar 212 000 Ar 220 000 Ar

COÛT
VARIABLE
15 000 Ar/jour 14 000 Ar/jour 16 000 Ar/jour
Exemple 3
Les trois phases d'un projet doivent s'effectuer de façon
séquentielle, ce qui signifie qu'une phase ne peut pas débuter
avant que la phase précédente soit terminée. On sait que le coût de
réalisation de chacune des phases se décompose en un coût fixe,
indépendant de sa durée, et en un coût variable qui en dépend. Le
tableau suivant résume la situation:
PHASE 1 2 3

COÛT FIXE 318 000 Ar 212 000 Ar 220 000 Ar

COÛT
VARIABLE
15 000 Ar/jour 14 000 Ar/jour 16 000 Ar/jour
Exemple 3
Le concepteur du projet doit proposer
un prix pour le projet. Il voudrait que ce
prix lui assure une marge de profit d'au
moins 10 %. Exprimer le coût total du
projet et le prix que le concepteur
devrait proposer en fonction de la durée
de chaque phase du projet?
Exemple 3
Solution:
La durée de chaque phase étant inconnue,
définissons les trois variables suivantes:
𝒙 = durée de la phase 1 (j)
𝒚 = durée de la phase 2 (j)
z = durée de la phase 3 (j)
Le coût de la phase 1 se décompose en un
coût fixe (318 000 Ar) et un coût variable
(15000 Ar/jour).
Le coût de chaque phase est
𝑪𝒐𝒖𝒕𝑷𝒉𝒂𝒔𝒆𝟏 = 𝟑𝟏𝟖 𝟎𝟎𝟎 + 𝟏𝟓 𝟎𝟎𝟎 𝒙
𝑪𝒐𝒖𝒕𝑷𝒉𝒂𝒔𝒆𝟐 = 𝟐𝟏𝟐 𝟎𝟎𝟎 + 𝟏𝟒 𝟎𝟎𝟎 𝒚
𝑪𝒐𝒖𝒕𝑷𝒉𝒂𝒔𝒆𝟑 = 𝟐𝟐𝟎 𝟎𝟎𝟎 + 𝟏𝟔 𝟎𝟎𝟎 𝒛
 Exemple 3
Solution:
Le coût total du projet peut s'exprimer comme la
somme des coûts des trois phases:
𝑪𝑻 = 𝑪𝒐𝒖𝒕𝑷𝒉𝒂𝒔𝒆𝟏 + 𝑪𝒐𝒖𝒕𝑷𝒉𝒂𝒔𝒆𝟐 + 𝑪𝒐𝒖𝒕𝑷𝒉𝒂𝒔𝒆𝟑

Le prix proposé pour le projet par son concepteur

doit lui assurer une marge de profit d'au moins
10%.
Le prix doit donc être au moins 10% plus élevé
que le coût total :

𝑷𝒓𝒊𝒙 ≥ 𝑪𝑻 + 𝟏𝟎% 𝑪𝑻
𝑷𝒓𝒊𝒙 ≥ 𝟏𝟔𝟓𝟎𝟎𝒙 + 𝟏𝟓𝟒𝟎𝟎𝒚 + 𝟏𝟔𝟎𝟎𝟎𝒛 + 𝟖𝟐𝟓𝟎𝟎𝟎
 Exercice
Un cultivateur cherche à diviser ses terres afin d'exploiter
différentes cultures. Traditionnellement, les champs de maïs
rapportent 3,50 Ar le mètre carré. Les champs d'avoine
rapportent 2,75 Ar le mètre carré. Les vergers produisent des
revenus de 4,50 Ar le mètre carré. L'homme dispose d'une terre
de 1 million de mètres carrés. Afin de nourrir les animaux de sa
ferme, le cultivateur doit consacrer un minimum de 300 000
mètres carrés à la culture du maïs et de l'avoine (ensemble).
Toutefois, le maïs étant plus susceptible aux longues périodes de
sécheresse, il ne veut pas que cette culture occupe plus de 200
000 mètres carrés. Dernièrement, il aimerait accorder le même
espace à la culture de l'avoine qu'à ses vergers.

1. Quelle expression représenterait correctement les revenus

du cultivateur ?
2. Modéliser toutes les contraintes que le cultivateur doit
respecter.
Modèles Algébriques et Géométriques
Les modèles algébriques et géométriques utilisent des équations mathématiques
pour représenter des phénomènes du monde réel. Ils sont largement utilisés dans
de nombreux domaines scientifiques et techniques pour analyser des relations
entre variables et résoudre des problèmes d'optimisation.
Modélisation avec des Équations Algébriques

Un modèle algébrique est une

représentation mathématique utilisant des
équations et des inégalités algébriques
pour décrire un système. Les variables et
paramètres du modèle sont reliés par des
relations définies à l'aide d'opérations
algébriques (addition, multiplication,
exponentiation, etc.).
Modélisation avec des Équations Algébriques

Exemples :
• Lois de l'électricité : 𝑽 = 𝑰𝑹
(loi d’Ohm, relation entre tension, courant
et résistance).
• Modèle économique : 𝑪 = 𝒂 + 𝒃𝒀
(fonction de consommation keynésienne,
avec 𝐶 la consommation, 𝑌 le revenu, et
𝑎, 𝑏 des paramètres).
Systèmes Linéaires et Non Linéaires
Un système d’équations est un ensemble de
plusieurs équations reliant plusieurs variables.

Systèmes Linéaires
Un système linéaire est de la forme :

𝐴𝑥 = 𝑏
où 𝐴 est une matrice de coefficients, 𝑥 un
vecteur de variables inconnues, et 𝑏 un vecteur
constant.
Systèmes Linéaires

Exemple :

2𝑥 − 3𝑦 = 5
ቊ
4𝑥 − 𝑦 = 1

​Les systèmes linéaires sont largement utilisés

en ingénierie (circuits électriques), en
économie (équilibre du marché) et en
physique (statique des forces).
Systèmes Non Linéaires
Un système est non linéaire si au moins une
des équations contient des termes non
linéaires (puissances, produits de variables,
exponentielles, etc.).
Exemple :

𝑥2 + 𝑦2 = 5
ቊ 𝑥
𝑒 +𝑦 =3

​ Les systèmes non linéaires apparaissent

souvent en dynamique des fluides, en
biologie (croissance des populations) et en
mécanique des structures.
Optimisation Linéaire
L’optimisation linéaire consiste à maximiser
ou minimiser une fonction objectif sous des
contraintes linéaires.

Problème standard :
Maximiser 𝒇(𝒙, 𝒚) = 𝒄𝟏 𝒙 + 𝒄𝟐 𝒚
sous contraintes :

𝑎1 𝑥 + 𝑏1 𝑦 ≤ 𝑑1
ቐ𝑎2 𝑥 + 𝑏2 𝑦 ≤ 𝑑2
𝑥, 𝑦 ≥ 1
 Optimisation Linéaire
Problème standard :
Maximiser 𝒇(𝒙, 𝒚) = 𝒄𝟏 𝒙 + 𝒄𝟐 𝒚
sous contraintes :

𝑎1 𝑥 + 𝑏1 𝑦 ≤ 𝑑1
ቐ𝑎2 𝑥 + 𝑏2 𝑦 ≤ 𝑑2
𝑥, 𝑦 ≥ 1
Méthodes de résolution :
•Méthode du simplexe
•Programmation linéaire par points intérieurs
Applications :
• Économie : Allocation optimale des ressources.
• Ingénierie : Optimisation des matériaux pour
structures solides et légères.
• Physique : Minimisation de l’énergie dans un système
mécanique.
Modèles Algébriques et Géométriques

La résolution des systèmes linéaires

La résolution des systèmes linéaires
Notations
La résolution des systèmes linéaires
Etude des solutions
La résolution des systèmes linéaires
Théorie

Solutions par la règles de Cramer

Calcul d’un déterminant

La résolution des systèmes linéaires

Calcul d’un déterminant

Matrice 1 x 1

Matrice 2 x 2

Matrice 3 x 3
 Exemple de système linéaire
Méthode de Gauss
Transformation d’un matrice en matrice triangulaire supérieure
 Exemple de système linéaire
Méthode de Gauss
Transformation d’un matrice en matrice triangulaire supérieure
 Exemple de système linéaire
Méthode de Gauss
Transformation d’un matrice en matrice triangulaire supérieure
 Exemple de système linéaire
Méthode de Gauss
Autre façon
 Exemple de système linéaire
Méthode de Gauss
Autre façon
 Exemple de système linéaire
Méthode de Gauss
Exemple 2
 Exemple de système linéaire
Méthode de Gauss
Exemple 3
Méthode de Gauss
Méthode de Gauss
Méthode de Gauss
Itération
Méthode de Gauss
Itération
Méthode de Gauss
Itération
Méthode de Gauss
Itération
Méthode de Gauss
Algorithme
Méthode de Gauss
Algorithme
La Méthode de Gauss-Jordan
La Méthode de Gauss-Jordan
La Méthode de Gauss-Jordan
 La Méthode de Gauss-Jordan

On a directement les racines dans la 4e colonne.

La Méthode de Gauss-Jordan
La Méthode de Gauss-Jordan
La Méthode de Gauss-Jordan - Algorithme
 Exercice
Créer le code python des algorithmes de
résolution de système linéaires

Bonus : Etudier la complexité algorithmique

de chaque méthode
Exercice 1 : Répartition des investissements
Un entrepreneur investit dans trois projets différents : un
projet technologique, un projet immobilier et un projet de
transport. Il décide de répartir un budget total de 200 000 Ar
selon les contraintes suivantes :
1. Il investit autant dans le projet technologique que dans le
projet immobilier.
2. L’investissement dans le projet technologique représente
le double de celui du projet de transport.
3. La somme des trois investissements doit être égale à 200
000 Ar.
Questions :
1. Modéliser ce problème sous forme d’un système
d’équations linéaires.
2. Résoudre ce système en utilisant l’algorithme de Gauss.
3. Vérifier la solution en appliquant l’algorithme de Gauss-
Jordan.
Exercice 2 : Production industrielle
Une usine fabrique trois types de produits : A, B et C. Pour
produire ces articles, elle utilise trois matières premières
différentes (X, Y, Z). Le coût de chaque matière première par
unité est donné dans le tableau suivant :
Quantité de Quantité de Quantité de Coût total par
Produit
X Y Z unité (Ar)
A 2 1 3 50

B 1 2 2 40

C 3 2 1 60
L’objectif est de trouver le coût unitaire de chaque matière première
(soit 𝑥, 𝑦 et 𝑧 les coûts des matières premières X, Y et Z).
Questions :
1. Écrire le système d’équations correspondant.
2. Résoudre ce système en appliquant l’élimination de Gauss.
3. Appliquer la méthode de Gauss-Jordan pour vérifier la solution.
Exercice 3 : Alimentation et nutrition
Un nutritionniste souhaite composer un menu équilibré en
utilisant trois aliments différents : légumes, viande et féculents.
La quantité de protéines, glucides et lipides apportée par
chaque aliment est donnée dans le tableau suivant :
Aliment Protéines (g) Glucides (g) Lipides (g)
Légumes 2 10 0.5
Viande 25 0 10
Féculents 5 30 1

Le nutritionniste souhaite composer un repas apportant 50 g de

protéines, 100 g de glucides et 20 g de lipides.
Questions :
1. Écrire le système d’équations correspondant.
2. Résoudre ce système en appliquant l’élimination de Gauss.
3. Appliquer la méthode de Gauss-Jordan pour vérifier la
solution.
Modèles Algébriques et Géométriques

L’optimisation linéaire (ou Programmation linéaire)

Principe de la programmation linéaire

Identification des variables associées au problème

Formulation des contraintes
Formulation de la fonction linéaire dite fonction objectif
Résolution du problème théorique
Formulation Solution
mathématique théorique
(3)
Formulation Détermination d’une
du problème réel (2) (4) solution réelle
Problème réel en
Solution réelle
programmation linéaire

(1) (5) Vérification

Identification du problème

Situation réelle
PROGRAMME LINÉAIRE
• Programmation linéaire
– 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

• Différentes programmations linéaires

– Programmation Linéaire classique
– Programmation Linéaire en Nombre Entiers
– Programmation Linéaire en 0-1
– Programmation Linéaire Mixte

• La terminologie est due à George B. Dantzig,

inventeur de l’algorithme du simplexe (1947)
MISE EN FORME MATHÉMATIQUE
• Définir les variables de décision
– ensemble des variables qui régissent la situation à
modéliser
– variables réelles, entières, binaires
• 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
• 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
• Préciser les paramètres du modèle
– constantes associées aux contraintes et à la fonction
objective
MODELE LINEAIRE

• Exemple :
Caractéristiques des produits & machines
Disponibilité
Type de Produits
hebdomadaire de
machine I II III IV chaque machines
A 1,5 1 2,4 1 2000
B 1 5 1 3,5 8000
C 1,5 3 3,5 1 5000
Profit par unité 5,24 7,30 8,34 4,18
 MODELE LINEAIRE

▪Exemple :
•But : établir la production hebdomadaire de chaque
produit de façon à maximiser le profit.

▪Le modèle :
𝒙𝒋 - production hebdomadaire du produit 𝑗.

But : trouver les valeurs de 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 et 𝒙𝟒 qui

maximisent le profit, considérant la limite de
temps d’utilisation de chaque machine
 MODELE LINEAIRE
• Exemple :
– But : 𝒎𝒂𝒙 𝒛 = 𝟓, 𝟐𝟒 𝒙𝟏 + 𝟕, 𝟑𝟎 𝒙𝟐 + 𝟖, 𝟑𝟒 𝒙𝟑 +
𝟒, 𝟏𝟖 𝒙𝟒

– Contraintes des machines :

𝐴 ∶ 1,5 𝒙𝟏 + 𝒙𝟐 + 2,4 𝒙𝟑 + 𝒙𝟒 ≤ 2000
𝐵: 𝒙𝟏 + 5 𝒙𝟐 + 𝒙𝟑 + + 3,5 𝒙𝟒  8000
𝐶 ∶ 1,5 𝒙𝟏 + 3 𝒙𝟐 + 3,5 𝒙𝟑 + 𝒙𝟒 ≤ 5000

– Contraintes de non négativité :

𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 , 𝒙𝟒 ≥ 0
MODELE LINEAIRE

• Validation du modèle et des résultats

– S’assurer
• que le modèle développé est conforme à la
réalité
• que les résultats sont valides dans toutes les
conditions
• Conception du système d’application
– Possibilité d’utiliser des logiciels
spécialisés
• Implantation
FORMULATION MATHÉMATIQUE D’UN PROGRAMME
LINÉAIRE

• FONCTION OBJECTIF (f.o.)

– Maximiser ou minimiser
– 𝑧 = 𝑐1𝑥1 + 𝑐2𝑥2 + 𝑐3𝑥3 + … + + 𝑐𝑛𝑥𝑛
• Contraintes
– 𝑎11𝑥1 + 𝑎12𝑥2 + 𝑎13𝑥3 + … + 𝑎1𝑛𝑥𝑛 (, =, ) 𝑏1
– 𝑎21𝑥1 + 𝑎22𝑥2 + 𝑎23𝑥3 + … + 𝑎2𝑛𝑥𝑛 (, =, ) 𝑏2
– 𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 + 𝑎𝑚3𝑥3 + … + 𝑎𝑚𝑛𝑥𝑛 (, =
, ) 𝑏𝑚
• Contraintes de non-négativité
– 𝑥𝑗  0 ; 𝑗 = 1, 2, 3, … 𝑛
• avec
– 𝑥𝑗 variables de décision (inconnues)
– 𝑎𝑖𝑗, 𝑏𝑖, 𝑐𝑗 paramètres du programme linéaire
TERMINOLOGIE DE LA SOLUTION

• Solution réalisable
➢ Solution où toutes les contraintes du
modèle sont satisfaites
• Zone de solutions
➢ Ensemble de toutes les solutions
réalisables
• Solution optimale
➢ Solution réalisable où la fonction objectif
atteint la meilleure valeur, maximum ou
minimum
➢ Plusieurs solutions optimales possibles
 RESOLUTION GRAPHIQUE
• Problème à deux variables de décision 𝑥1 et 𝑥2 :
–fonction objective - droite dans  2
–contraintes - hemi-plans de  2

–𝑃 = (𝑥𝟏 , 𝑥𝟐 ) - solution admissible (réalisable)

si P satisfait toutes les contraintes
–région admissible - l’ensemble des solutions
admissibles
–solution optimale - solution admissible qui
optimise la f.o.
PROGRAMMATION LINÉAIRE
• Résolution selon les techniques
appropriées
–Exemple
•MAXIMISER 𝑧 = 3𝑥1 + 5𝑥2
•SUJET À

𝑥1  4
2𝑥2  12
3𝑥1 + 2𝑥2  18
𝑥1  0 ; 𝑥2  0
PROGRAMMATION LINÉAIRE
• Résolution selon les techniques
appropriées

–Solutions optimales
•programmation linéaire: simplexe
•programmation en nombre entier:
branch-and-bound
•programmation dynamique
–Solutions sous-optimales:
heuristiques
ZONE DE SOLUTION RÉALISABLE
Zone limitée par l’ensemble des équations de
contraintes du problème et par les limites des
variables de décision
POLYTOPE ET POINTS EXTREMES
▪ Un polygone est dit convexe si toutes ses diagonales sont
entièrement à l'intérieur de la surface délimitée par le
polygone
▪ Un polytope est la généralisation à toutes dimensions de la
notion de polygone pour 2 dim.
x2
▪ Polytope convexe: 𝑋 = { 𝑥|𝐴𝑥 = 𝑏, 𝑥 ≥ 0}
Points
8 extrêmes
Polytope
convexe
6

4
X
2

0 x1
2 4 6 8 10
 FONCTION OBJECTIVE
Déplacement de la fonction objective à l’intérieur
de la zone de solution réalisable pour atteindre un
extremum x
2

4
𝒛 = 𝟏𝟎 = 𝟑𝒙𝟏 + 𝟓𝒙𝟐
2

0 x1
2 4 6 8 10
FONCTION OBJECTIVE
Déplacement de la fonction objective à
l’intérieur de la zone de solution réalisable
pour atteindre un extremum
x2

6
z = 20 = 3 x1 + 5 x 2
4

0 x1
2 4 6 8 10
FONCTION OBJECTIVE
Déplacement de la fonction objective à
l’intérieur de la zone de solution réalisable
pour atteindre un extremum
x2

Solution
z = 36 = 3 x1 + 5 x 2 8
(un des points extrême)
(2,6) x1 = 2
6
x2 = 6
4
z = 36

0 x1
2 4 6 8 10
FONCTION OBJECTIVE
Déplacement de la fonction objective à
l’intérieur de la zone de solution réalisable
pour atteindre un extremum
x2

z = 36 = 3 x1 + 5 x 2 8
Solution
(2,6) x1 = 2
6
x2 = 6
z = 20 = 3 x1 + 5 x 2
z = 36
4

z = 10 = 3 x1 + 5 x 2
2

0 x1
2 4 6 8 10
PROBLÈME DE MAXIMISATION

• Maximiser 𝑍 = 𝑥1 + 2𝑥2
Sujet à
2𝑥1 + 𝑥2  4
𝑥1 + 𝑥2  8
−𝑥1 + 𝑥2  4
𝑥1  5
𝑥1  0, 𝑥2  0
 PROBLÈME DE MAXIMISATION

x2

-x1 + x2 = 4
𝑋1 = 2
8 𝑋2 = 6
𝑍 = 14
6 x1 = 5
2x1 + x2 = 4
4

2 x1 + x2 = 8

Z=x1 + 2x2
0 x1
2 4 6 8 10
PROBLÈME DE MINIMISATION

Minimiser 𝑍 = 𝑥1 − 𝑥2
Sujet à
½𝑥1 + 𝑥2  8
−𝑥1 + 8𝑥2  40
𝑥1  8
𝑥2  8
𝑥1  0, 𝑥2  0
 PROBLÈME DE MINIMISATION
X1 = 8
x2
X2 = 6
x2 = 8 Z=2
8

6
-x1 + 8x2 = 40
4

x1 = 8
2 ½x1 + x2 = 8

0 2 4 6 8 10 12 14 16 18 20 x1
RÉSULTAT D’UNE OPTIMISATION LINÉAIRE
Le domaine admissible d’un PL peut être
• vide: dans un tel cas, le problème est sans solution
admissible (pas de solution optimale)
• borné (et non vide): le problème possède toujours
au moins une solution optimale
• non borné: dans ce cas, selon la fonction objectif
❑ le problème peut posséder des solutions
optimales
❑ il peut exister des solutions admissibles de valeur
arbitrairement grande (ou petite)
❑ dans un tel cas, le PL n'admet pas de solution
optimale finie et est dit non borné
EXEMPLE 1
max 𝒛 = 𝟓 𝒙𝟏 + 𝟑 𝒙𝟐
sc
x2 𝟑 𝒙𝟏 + 𝟓 𝒙𝟐  𝟏𝟓
𝟓 𝒙𝟏 + 𝟐 𝒙𝟐 ≤ 𝟏𝟎
𝒙𝟏 , 𝒙 𝟐  𝟎

O
x1
3x1 + 5x2 = 15

5x1 + 2x2 = 10
 EXEMPLE 1
max 𝒛 = 𝟓 𝒙𝟏 + 𝟑 𝒙𝟐
A  z3 ; sc
z1 x A  intersection des 𝟑 𝒙𝟏 + 𝟓 𝒙𝟐  𝟏𝟓
z2 z3 2
deux contraintes 𝟓 𝒙𝟏 + 𝟐 𝒙𝟐 ≤ 𝟏𝟎
𝒙𝟏 , 𝒙𝟐  𝟎
z = 5x1 + 3x2

x1
 z
O direction = - c1 / c2
3x1 + 5x2 = 15
= -5/3
5x1 + 2x2 = 10
 EXEMPLE 2
z1
z2
x2 max 𝒛 = 𝟐, 𝟓 𝒙𝟏 + 𝒙𝟐
sc
AB z2
𝟑 𝒙𝟏 + 𝟓 𝒙𝟐  𝟏𝟓
𝟓 𝒙𝟏 + 𝟐 𝒙𝟐 ≤ 𝟏𝟎
z = 2,5x1 + x2
𝒙𝟏 , 𝒙𝟐  𝟎
A

B x1
O
3x1 + 5x2 = 15
 z
direction = - c1 / c2
5x1 + 2x2 = 10
= -2,5
RESUME
• Région admissible borné :
–polygone dont les côtés sont des
segments des droites représentant les
contraintes linéaires du problème
–un point P  à l ’intersection de 2 côtés
du polygone est un point extrême
–solution optimale:
• point extrême  solution optimale unique
• côté du polygone  infinité de solutions
optimales ( la valeur de la f. o. est unique )
CAS SPECIAUX
• Région admissible non borné
contraintes : Une solution
unique
x2 x1 − x2 = − 1 z3
max 𝒛 = −𝟑 𝒙𝟏 + 𝟒 𝒙𝟐
z2 − 0,5x1 + x2 = 2
sc
𝒙 𝟏 − 𝒙𝟐  − 𝟏 z1
−𝟎, 𝟓 𝒙𝟏 + 𝒙𝟐 𝟐
A
𝒙𝟏 , 𝒙𝟐  𝟎

x1
CAS SPECIAUX
• Région admissible non borné
contraintes : Une infinité
de solutions
x2 x1 − x2 = − 1
max 𝒛 = −𝒙𝟏 + 𝟐 𝒙𝟐
sc z1 − 0,5x1 + x2 = 2
𝒙𝟏 − 𝒙𝟐  − 𝟏 z3
−𝟎, 𝟓 𝒙𝟏 + 𝒙𝟐 ≥ 𝟐 z2

𝒙𝟏 , 𝒙𝟐  𝟎

x1
CAS SPECIAUX
• Région admissible non borné
contraintes :
Pas de solution
finie
x2 x1 − x2 = − 1
max 𝒛 = 𝒙𝟏 + 𝒙𝟐
sc z3 − 0,5x1 + x2 = 2
𝒙𝟏 − 𝒙𝟐  − 𝟏 z2
−𝟎, 𝟓 𝒙𝟏 + 𝒙𝟐 ≥ 𝟐
z1
𝒙𝟏 , 𝒙𝟐  𝟎

x1
RESUME

• Région admissible non borné :

– solution optimale:
• point extrême  solution optimale unique
• côté de la région admissible
 infinité de solutions optimales
( la valeur de la f. o. est unique )
• pas de solution optimale finie
UN DERNIER CAS SPECIAL
▪ Région admissible vide 
contraintes incompatibles

er
1 cas :
x2 − 2x1 + 3x2 = 6  des hemi
x1 + x2 = 5 plans est vide
x1 − x2 = 1
𝒙𝟏 + 𝒙𝟐  𝟓
− 𝟐 𝒙𝟏 + 𝟑 𝒙𝟐 ≤ 𝟔
𝒙𝟏 − 𝒙𝟐  𝟏
x1
𝒙𝟏 , 𝒙𝟐  𝟎
UN DERNIER CAS SPECIAL
• Région admissible vide  contraintes incompatibles

x2 ème
2 cas :
− x1 + x2 = 1 contrainte de
x1 + x2 = − 1 non négativité
pas satisfaite

𝒙𝟏 + 𝒙𝟐  − 𝟏
x1
− 𝒙𝟏 + 𝒙𝟐 ≤ 𝟏
𝒙𝟏 , 𝒙𝟐  𝟎
CONCLUSION
Pour chaque problème PL :
•Solution optimale unique
•Infinité de solutions optimales
•Solution optimale infinie
•Aucune solution
 GENERALISATION
• Problème à r > 2 variables de décision 
solution graphique ?!?!
• Vocabulaire suggéré par la méthode graphique :
1. - région admissible : région convexe d’un espace
de dimension r ( polyèdre convexe )
2. - un point P  à l’intersection de s  2 hyperplans
représentant les contraintes est un point extrême
du polyèdre
 GENERALISATION

• Problème à r > 2 variables de décision 

solution graphique ?!?!
• Vocabulaire suggéré par la méthode graphique :
3. - solution optimale:
• unique  point extrême du polyèdre
• infinité de solutions optimales  frontière du polyèdre
= hyperplan de dimension < r ( la valeur de la f. o. est
unique )
METHODE DU SIMPLEXE

• Méthode exacte et itérative

• Parcours des points extrêmes jusqu’à trouver
la (les) solution(s) optimale(s), si en existe
• Identification des cas de contraintes
incompatibles
• Basée sur l’algèbre des matrices
METHODE DU SIMPLEXE
x2

8
Polytope
convexe
6

4
X
2

0 x1
2 4 6 8 10
INTRODUCTION

• développée initialement par George

Dantzig en 1947
• seule méthode exacte pour solutionner
des problèmes linéaires de grande taille
• méthode itérative algébrique où l’on
circule séquentiellement sur les
sommets à l’intérieur de la zone de
solution jusqu’à l’obtention de la solution
optimale
PROPRIÉTÉS DU SIMPLEXE
• Zone de solution du problème linéaire toujours convexe
• S’il existe une seule solution optimale au problème
linéaire, elle est obligatoirement localisée sur un
sommet de la zone de solution
• S’il existe de multiples solutions optimales, au moins
deux d’entre elles doivent être localisées sur des
sommets adjacents
• Le nombre de sommets de la zone de solution est fini
• Si la solution réalisable localisée à un sommet donné
n’a pas de voisin adjacent dont la solution est
supérieure, ce sommet est la solution optimale
FORME CANONIQUE
• PROBLÈME DE MAXIMISATION
n
Max c x j =1
j j

n
sujet à  aij xj  bi i = 1, ...,m
j =1

xj  0 j = 1,...,n

• PROBLÈME DE MINIMISATION
n
Min c x
j =1
j j

n
sujet à a
j =1
ij xj  bi i = 1, ...,m

xj  0 j = 1,...,n
FORME NORMALISÉE
• PROBLÈME DE MAXIMISATION
n
Max c x
j =1
j j

n
sujet à a x
j =1
ij j = bi i = 1, ...,m

xj  0 j = 1,...,n
• PROBLÈME DE MINIMISATION
n
Min c x
j =1
j j

n
sujet à a x
j =1
ij j = bi i = 1, ...,m

xj  0 j = 1,...,n
Variables de base et variables hors base

• Le passage de la forme canonique à la forme

normalisée
• en introduisant des variables d’écart (variables
supplémentaires)

• Variables de base : variables supplémentaires

+ la variable Z
• Variables hors base : variables xi du système
initial
MÉTHODE DU SIMPLEXE
DÉFINITIONS

• Systèmes d’équations équivalents

– Systèmes qui possèdent le même ensemble de solutions
• Variable de base
– Variable qui a un coefficient unitaire positif dans une des équations
du système et un coefficient nul partout ailleurs
• Opérations pivot
– Opération de Gauss-Jordan pour transformer un système
d’équations équivalent dans lequel une variable devient de base
• Système canonique
– Système d’équations où il y a une variable de base par équation
• Solution de base
– Système d’équations où les variables hors base sont fixées à zéro
résolu pour les variables de base
ALGORITHME DU SIMPLEXE
1. Déterminer une solution de base (sommet du
polytope) réalisable (vérifiant toutes les
contraintes)
2. Vérifier si la solution actuelle est optimale
3. Déterminer la variable hors base qui va devenir
variable de base (accroissement de la fonction
objectif)
4. Déterminer la variable de base qui sortira de la
solution
5. Effectuer les opérations linéaires (pivots) selon la
technique de Gauss-Jordan
6. Répéter (tant que c’est possible)
ALGORITHME
DU SIMPLEXE
MÉTHODE DU SIMPLEXE

• FORME CANONIQUE

Max Z = 3 x 1 + 5 x2

sujet à
x1 4
2 x2  12
3 x1 + 2 x2 18
et
x1  0, x2  0
MÉTHODE DU SIMPLEXE

• FORME NORMALISÉE
Max Z
Z - 3 x1 - 5 x2 = 0 (0)
x1 + x3 = 4 (1)
2 x2 + x4 = 12 (2)
3 x1 + 2 x2 + x5 = 18 (3)
avec
xj  0, pour j =1, 2, 3, 4, 5
 MÉTHODE DU SIMPLEXE
• ÉTAPE D’INITIALISATION
– Déterminer une solution de base réalisable
– Porter les variables hors base à zéro
– Solutionner les variables de base
– Exemple:
• z, x3, x4 et x5 sont les variables de base
• x1 et x2 sont les variables hors base
– On obtient:
• x1 = 0 et x2 = 0
• x3 = 4, x4 = 12 et x5 = 18
•z=0
 MÉTHODE DU SIMPLEXE

• VARIABLE ENTRANT DANS LA BASE

– Variable hors base entrant dans la base
– Celle qui sera choisie fera augmenter la valeur de
la fonction objective le plus rapidement possible
– Variable ayant le plus grand coefficient négatif
(cas de maximisation) de l’équation (0)
– Exemple:
• X2 devient variable de base
 MÉTHODE DU SIMPLEXE
• VARIABLE SORTANT DE LA BASE
– Variable qui limitera le plus rapidement la progression de la
nouvelle variable de base
– Exemple
• si x2 entre dans la base
• équation (2)
–2 x2 + x4 = 12
–x2 max = 6
• équation (3)
–3 x1 + 2 x2 + x5 = 18
–x2 max = 9
• limite maximale de x2 égale 6 sinon x4 devient négatif
MÉTHODE DU SIMPLEXE
• OPÉRATIONS PIVOT
– Système d’équations original (variables de base en gras)
Z - 3 x1 - 5 x2 = 0 (0)
x1 + x3 = 4 (1)
2 x2 + x4 = 12 (2)
3 x1 + 2 x 2 + x5 = 18 (3)
– Pour revenir à la forme canonique, il faut que les variables de base aient un
coefficient unitaire dans une équation et nul dans les autres
– Équation (2) multipliée par ½
2 x2/2 + x4/2= 12 /2 (2)
x2 + ½ x4= 6 (2)
– Il faut éliminer les termes x2 des autres équations
 MÉTHODE DU SIMPLEXE

• OPÉRATIONS PIVOT (suite)

– Nouveau système équivalent d’équations
Z - 3 x1 - 5/2 x4 = 30 (0)
x1 + x3 = 4 (1)
x2 + ½ x4 = 6 (2)
3 x1 - x4 + x 5 = 6 (3)
 MÉTHODE DU SIMPLEXE
• OPÉRATIONS PIVOT (suite)
– Équation (0) = ancienne (0) + 5 équation (2)
Z - 3 x1 - 5 x2 = 0 (0)
5 x2 + 5/2 x4 = 30 (2)
Z - 3 x1 + 5/2 x4 = 30 (0)

– Équation (3) = ancienne (3) – 2 équation (2)

3 x1 + 2 x2 + x5 = 18 (3)
- 2 x2 - x4 = -12 (2)
3 x1 - x4 + x5 =6 (3)
 MÉTHODE DU SIMPLEXE
• CRITÈRE D’OPTIMALITÉ
– Optimalité assurée lorsqu’il est impossible de faire augmenter (cas de
maximisation) la valeur de z
– Exemple:
• x1 peut faire augmenter z
• Variable entrante x1
• Variable sortante x5
– équation (1)
» x1 + x3 = 4
» x1 max = 4
– équation (3)
» 3 x1 – x4 + x5 = 6
» x1 max = 2
 MÉTHODE DU SIMPLEXE
• CRITÈRE D’OPTIMALITÉ
–Optimalité assurée lorsqu’il est impossible de faire
augmenter (cas de maximisation) la valeur de z
–Exemple:
• x1 peut faire augmenter z
• Variable entrante x1
• Variable sortante x5
– équation (1)
» x1 + x 3 = 4
» x1 max = 4
– équation (3)
» 3 x 1 – x4 + x 5 = 6
» x1 max = 2
MÉTHODE DU SIMPLEXE
• SOLUTION OPTIMALE
– Système équivalent d’équations
Z + 3/2 x4 + x5 = 36 (0)
x3 + 1/3 x4 - 1/3 x5 = 2 (1)
x2 + ½ x4 = 6 (2)
x1 - 1/3 x4 +1/3 x5 = 2 (3)
– Variables hors base
• x4 = 0, x5 = 0
– Variables de base
• x1 = 2, x2 = 6, x3 = 2
– Fonction objective
• z = 36
 SIMPLEXE SOUS FORME TABULAIRE
• Méthode essentiellement identique
• Informations
– Coefficients des variables
– Constantes des équations
– Variables de base de chaque équation

Variables de décision (x1, x2)

 SIMPLEXE SOUS FORME TABULAIRE
• Initialisation
• Critère d’optimalité
– Coefficients de l’équation (0) non négatifs ?
• Itération # 1
– Dans la dernière ligne, on a 2 coefficients négatifs. On prends le plus grands en
valeur absolue c’est-à-dire –5, et on définit la variable entrante
– Variable entrante x2
• Entourer la colonne pivot
– Variable sortante x4
• Entourer la ligne pivot
• Point pivot à l’intersection
– Transformation de Gauss-Jordan
 SIMPLEXE SOUS FORME TABULAIRE
• Itération #1 (suite)
✓ Diviser la ligne pivot par le nombre pivot
✓ Appliquer les transformations
✓ Nouvelle solution
z = 30
Solution (0, 6, 4, 0, 6)
 SIMPLEXE SOUS FORME
• Itération # 2 TABULAIRE
– Dans la dernière ligne, on trouve encore un coefficient négatif (-3)
– Cette colonne nous donne x1 comme variable entrante
– La variable x5 est sortante
– Le pivot est 3
 SIMPLEXE SOUS FORME TABULAIRE
• Ensemble complet

▪ Solution
• (2, 6, 2, 0, 0)

• z = 36
SITUATIONS PARTICULIÈRES
• Égalité des profits relatifs
– Choix aléatoire de la variable
• Égalité des ratios
– Choix aléatoire
– Situation de dégénérescence: remonter à l’étape des ratios
identiques
• Solution non bornée
– En pratique, une contrainte est absente
• Solutions multiples
– Variables hors base avec des coefficients nuls dans la fonction
objective
• Présence de cyclage
– Certaines variables de base sont nulles
Règle de Blanc : choisir comme colonne entrante celle de profit
marginal positif de plus petit indice
SIMPLEXE SOUS FORME MATRICIELLE
Max Z = cx
• Forme canonique
sujet à
Ax  b
x0
où
 x1  b1  0 
x  b  0 
x=  2
b=  2 
0= 
...  ...  ...
     
 xn  bm  0 
a11 a12 ..... a1n 
a a ..... a 
A =  21 22 2n 

..... ..... ..... ..... 

 
am1 am 2 ..... amn 
SIMPLEXE SOUS FORME MATRICIELLE
Max Z = cx
• Forme normalisée sujet à
x 
A, I   = b
x s 
x 
x   0
 s
où
I = matrice identitée m  m
 xn +1 
x 
xs =  n+2 
... 
 
 xn + m 
SIMPLEXE SOUS FORME MATRICIELLE
• Problème
c = 3 5
1 0 1 0 0

A, I = 0 2 0 1 0 
3 2 0 0 1
4  x3 
   x1   
b = 12 x=  x s =  x4 
18  x2 
 x5 
SIMPLEXE SOUS FORME MATRICIELLE

• Itération 0
x3  1 0 0 1 0 0

xB = x 4   
B = 0 1 0   −1  
B = 0 1 0 
 x 5  0 0 1 0 0 1
• X2 entre
 x 3  1 0 0  4   4 
• X4 sort
     
x B =  x 4  = 0 1 0 12 = 12 
 x 5  0 0 1 18 18
4
c B = 0 0 0   
Z = 0 0 0 12 = 0
18
 SIMPLEXE
SOUS FORME MATRICIELLE
• Itération 1

x3  1 0 0 1 0 0

xB = x 2   
B = 0 2 0  −1 
B = 0 0,5 0 

• X1 entre 
 x 5

 
0 2 1 0 − 1 1
• X5 sort  x 3  1 0 0  4   4
x B =  x 2  = 0 0,5 0 12 = 6
 x 5  0 − 1 1 18 6
 4
c B = 0 5 0  
Z = 0 5 06 = 30
6
SIMPLEXE SOUS FORME MATRICIELLE

• Itération 2

x3  1 0 1 1 0,33 − 0,33

x B =  x 2  B = 0 2 0 B −1 = 0 0,50 0 
 x1  0 2 3 0 − 0,33 0,33 
 x 3  1 0,33 − 0,33  4  2
x B =  x 2  = 0 0,50 0  12 = 6
 x1  0 − 0,33 0,33  18 2
 2
c B = 0 5 3 Z = 0 5 36 = 36
2
Modèles Algébriques et Géométriques

Programmation linéaire : Variables artificielles et pénalités

 VARIABLES ARTIFICIELLES

Cas 
• ai1 x1 + ai2 x2 + ai3 x3 + … + ain xn  bi
• Ajout d’une variable d’écart
• ai1 x1 + ai2 x2 + ai3 x3 + … + ain xn – xm = bi
• Coefficient de la variable d’écart négatif ne
peut servir comme variable de base
• Ajout d’une variable artificielle
• ai1 x1 + ai2 x2 + ai3 x3 + … + ain xn – xm + xa = bi
 VARIABLES ARTIFICIELLES

Cas =
• L’ajout d’une variable artificielle permet
l’insertion d’une variable de base dans
la solution de départ
• Les variables artificielles sont éliminées
de la solution en leur assignant une
pénalité importante dans la fonction
objective
 RÉSOLUTION
Méthode du grand M
Pénaliser les variables artificielles en leur affectant un
coefficient de valeur très élevée dans la fonction économique
• - M pour un problème à maximum,
• + M pour un problème à minimum.
Les pénalités ont pour objet de provoquer l'élimination des
variables artificielles au fil des itérations.
Normalement, à l'optimum (s'il existe) les variables artificielles
sont hors base. Si celles-ci sont à l'optimum dans la base, avec
une valeur non nulle, le
programme n'a pas de solution.
Méthode des deux phases
Phase 1 : résolution du problème auxiliaire pour
trouver une solution de base réalisable
Phase 2 : Partir de cette solution pour résoudre le problème original
 Rappel
Forme canonique Forme standard

max 𝒛 = 𝒄𝒙 max 𝒛 = 𝒄 𝒙 + 𝟎𝒔
𝐬𝐜 𝐬𝐜
𝑨𝒙 ≤ 𝒃 𝑨𝒙 + 𝑰𝒔 = 𝒃
𝒙≥ 𝟎 𝒙 ,𝒔 ≥ 𝟎

Question : Contraintes  ou = → forme standard ??

 RESOLUTION DU PL STANDARD

Analyse d’un exemple :

• Canonique
• Standard
max 𝒛 = − 𝟐 𝒙𝟏 − 𝟒 𝒙𝟐
max 𝒛 = − 𝟐 𝒙𝟏 − 𝟒 𝒙𝟐 + 𝟎𝒔𝟏 + 𝟎𝒔𝟐
Sc
Sc
𝒙𝟏 + 𝟓𝒙𝟐 ≤ 𝟖𝟎
𝒙𝟏 + 𝟓𝒙𝟐 + 𝒔𝟏 = 𝟖𝟎
𝟒𝒙𝟏 + 𝟐𝒙𝟐 ≥ 𝟐𝟎
𝟒𝒙𝟏 + 𝟐𝒙𝟐 − 𝒔𝟐 = 𝟐𝟎
𝒙𝟏 + 𝒙𝟐 = 𝟏𝟎
𝒙𝟏 + 𝒙𝟐 = 𝟏𝟎
𝒙𝟏 , 𝒙𝟐 ≥ 𝟎
𝒙𝟏 , 𝒙𝟐 , 𝒔𝟏 , 𝒔𝟐 ≥ 𝟎
 RESOLUTION DU PL STANDARD
Analyse d’un exemple :
x1 Standard
max z = ( -2 -4 0 0 )
x2
sc s1 max z = - 2 x1 - 4 x2+ 0s1 + 0s2
s2
1 5 1 0 x1 80 sc
4 2 0 -1 x2 = 20 x1 + 5 x2 + s1 = 80
1 1 0 0 s1 10
s2 4 x1 + 2 x2 - s2 = 20
x , s 0 x1 + x2 = 10
x1 , x 2 , s1 , s 2  0
 RESOLUTION DU PL STANDARD

• Canonique • Standard
max 𝒛 = − 𝟐 𝒙𝟏 − 𝟒 𝒙𝟐 max 𝒛 = − 𝟐 𝒙𝟏 − 𝟒 𝒙𝟐 + 𝟎𝒔𝟏 + 𝟎𝒔𝟐
Sc Sc
𝒙𝟏 + 𝟓𝒙𝟐 ≤ 𝟖𝟎 𝒙𝟏 + 𝟓𝒙𝟐 + 𝒔𝟏 = 𝟖𝟎
𝟒𝒙𝟏 + 𝟐𝒙𝟐 ≥ 𝟐𝟎 𝟒𝒙𝟏 + 𝟐𝒙𝟐 − 𝒔𝟐 = 𝟐𝟎
𝒙𝟏 + 𝒙𝟐 = 𝟏𝟎 𝒙𝟏 + 𝒙𝟐 = 𝟏𝟎
𝒙𝟏 , 𝒙𝟐 ≥ 𝟎 𝒙𝟏 , 𝒙𝟐 , 𝒔𝟏 , 𝒔𝟐 ≥ 𝟎
 RESOLUTION DU PL STANDARD

Analyse d’un exemple :

x1
max z = ( -2 -4 0 0 ) x2 matrice de base ???
sc s1
s2
une matrice carrée
1 5 1 0 x1 80
inversible
4 2 0 -1 x2 = 20
1 1 0 0 s1 10
s2
x , s 0
INTRODUCTION DES PENALITES

max z = - 2 x1 - 4 x2+0s1 + 0s2

sc
x1 + 5 x2 + s1 = 80

4 x1 + 2 x2 - s2 = 20
x1 + x2 = 10
x1 , x2 , s1 , s2  0
INTRODUCTION DES PENALITES

max z = - 2 x1 - 4 x2 + 0s1 + 0s2 - M a2 - M a3

sc

x1 + 5 x2 + s1 = 80
4 x1 + 2 x2 - s2 + a2 = 20
x1 + x2 + a3 = 10
x1 , x 2 , s 1 , s 2 , a 2 , a 3  0
 GENERALISATION

max z = cx + 0s - Ma
sc
x
A | {I j } | {Ik } s = b
a

x, s, a  0
METHODE DU GRAND M
Soit à résoudre le programme linéaire suivant sous sa
forme canonique
Min z = 3 x1 + 10 x2
5 x1 + 6 x2  10
2 x1 + 7 x2  14
x1  0 ; x2  0

Forme standard

Min z = 3 x1 + 10 x2 + 0 s1 + 0 s2 + M a1 + M a2
5 x1 + 6 x2 - 1 s1 + 0 s2 + 1 a1 + 0 a2 = 10
2 x1 + 7 x2 + 0 s1 - 1 s2 + 0 a1 + 1 a2 = 14
x1  0 ; x2  0 ; s1  0 ; s2  0; a1  0 ; a2  0
 METHODE DU GRAND M
Tableau 0
hors base x1 x2 s1 s2 a1 a2 bi
base
a1 5 6 -1 0 1 0 10
a2 2 7 - -1 0 1 14
z -3 -10 0 0 -M -M 0

On les ramène à 0
Tableau 1
hors base x1 x2 s1 s2 a1 a2 bi
base
a1 5 6 -1 0 1 0 10
a2 2 7 - -1 0 1 14
z 3-7M 10-13M M M 0 0 -24M
 METHODE DU GRAND M
Puisqu’on cherche un minimum, la variable entrante est celle qui a le plus grand coefficient
négatif, c-à-d, x2. Il suffit de regarder les coefficient de M car M est très grand.

hors base x1 x2 s1 s2 a1 a2 bi ratio

base
a1 5 6 -1 0 1 0 10 5/3
a2 2 7 - -1 0 1 14 2
z 3-7M 10-13M M M 0 0 -24M
Tableau 2
hors base x1 x2 s1 s2 a1 a2 bi ratio
base
x2 5/6 1 -1/6 0 - 0 5/3 -10
a2 -23/6 0 7/6 -1 - 1 7/3 2
z -16/3 +(23/6)M 0 5/3 –(7/6)M M - 0 -50/3 –(7/3)M
 METHODE DU GRAND M
Tableau 3 hors base x1 x2 s1 s2 a1 a2 bi
base
x2 6/21 1 0 -1/7 - - 2
s1 -23/7 0 1 -6/7 - - 2
z -1/7 0 0 30/21 - - -20

On a atteint la solution réalisable qui est : x1 = 0, x2 = 2, s1 = 2, s2 = 0;

z = 20
On continue avec la méthode simplexe pour obtenir la solution optimale

Remarque : Dans le cas particulier de cet exemple qui était

sous forme standard, il aurait été plus rapide de traiter
le problème dual et d’en déduire la solution du primal initial
 METHODE A DEUX PHASES
Cette méthode permet de tenir compte des variables artificielles.

[Link] rend nulles les variables artificielles en minimisant la somme

des variables artificielles sous les contraintes du programme
initial.
• Remarque : Comme les variables artificielles sont forcément
positives ou nulles le minimum est atteint quand elles sont nulles
• (si ce n'est pas le cas, c'est qu'il n'y a pas de solution).

[Link] fois les variables artificielles annulées, on a une solution de

base admissible qui nous permet dans une seconde phase de
résoudre le programme initial.
 METHODE A DEUX PHASES

Proposition :
• Phase I : éliminer les variables artificielles et
trouver une solution de base réalisable initiale
 pour le problème originel.
Pa - maximiser une ‘‘sous-fonction objectif ’’
formée seulement des variables artificielles
• Phase II : optimiser le problème originel P en prenant
la solution finale de Pa comme la solution de base
réalisable initiale de P.
 L’EXEMPLE : Phase I

Pa : max za = - a2 - a3 xB = (s1 a2 a3 )
sc xN = (x1 x2 s2 )
x1 + 5 x2 + s1 = 80
cB = ( 0 -1 -1 )
4 x1 + 2 x2 - s2 + a2 = 20
cN = 0
x1 + x2 + a3 = 10
x1 , x 2 , s 1 , s 2 , a 2 , a 3  0 1 5 0
N= 4 2 -1
1 1 0
zN - cN = cBN - cN = ( -5 - 3 1 )
z = cBb = - 30
 L’EXEMPLE : Phase I
Tableau initial : z x1 x2 s1 s2 a2 a 3
zª 1 -5 -3 0 1 0 0 -30
s1 0 1 5 1 0 0 0 80
a2 0 4 2 0 -1 1 0 20
a3 0 1 1 0 0 0 1 10

Après 1er z x1 x2 s1 s2 a2 a3
:
pivotage zª 1 0 -1/2 0 -1/4 5/4 0 -5
s1 0 0 9/2 1 1/4 -1/4 0 75
x1 0 1 1/2 0 -1/4 1/4 0 5
a3 0 0 1/2 0 1/4 -1/4 1 5
 L’EXEMPLE : Phase I
Après 2ème pivotage : z x1 x2 s1 s2 a2 a3
zª 1 0 0 0 0 1 1 0
s1 0 0 0 1 -2 2 -9 30
x1 0 1 0 0 -1/2 1/2 -1 0
x2 0 0 1 0 1/2 -1/2 2 10

(zjN - cjN )  0,  j  solution optimale  max za = 0

xBª = (s1 x1 x2 ) = (30 0 10) pas de variable artificielle

xNª = (s2 a2 a3 ) = 0 dans la base

solution de base réalisable initiale pour P

 L’EXEMPLE : Phase II

xB = (s1 x1 x2 ) = (30 0 10) cB = ( 0 -2 -4 )

xN = (s2 ) = 0 cN = 0

-2 30 z x1 x2 s1 s2
N = -1/2 b= 0
z 1 0 0 0 -1 -40
1/2 10
s1 0 0 0 1 -2 30
x1 0 1 0 0 -1/2 0
x2 0 0 1 0 1/2 10
zN - cN = cBN - cN = ( -1 )
z = cBb = - 40
 L’EXEMPLE : Phase II
z x1 x2 s1 s2
Tableau initial :
z 1 0 0 0 -1 -40
s1 0 0 0 1 -2 30
x1 0 1 0 0 -1/2 0
x2 0 0 1 0 1/2 10

z x1 x2 s1 s2
Après 1er pivotage :
z 1 0 2 0 0 -20
(z N - c N )  0,  j s1 0 0 4 1 0 70
j j
x1 0 1 1 0 0 10
 solution optimale s2 0 0 2 0 1 20
METHODE A DEUX PHASES - RESUME

max za = -a ; a  0  za  0 ou
valeur maximale de za = 0
Cas 1 : Cas 2 :
si max za < 0  si max za = 0  ak = 0, k
 ak  0   solution optimale de
P ne possède pas de Pa est une solution
solution de base réalisable de P
réalisable
(pas forcément de base)
METHODE A DEUX PHASES - RESUME

Analyse du cas 2 :
» si ak est hors base , k  solution de base
réalisable de P
si  k tel que ak est dans la base
 solution optimale de Pa n’est pas une
solution de base de P
 solution optimale de Pa est une solution de
base dégénérée
Changement de Contrainte
base (si possible) redondante
 LE PROBLEME DE MINIMISATION

min z = cx  - max z’ = -cx

OU
Condition d’arrêt :
si (zjN - cjN )  0,  j

Choix de la colonne pivot :

j telle que zj N - cj N = maxk { (zk N - ckN ) ; (zkN - ckN ) > 0 }

Choix de la ligne pivot :

i telle que bi / ai j = min l { bl / al j , al j > 0 }
Modèles Algébriques et Géométriques

Programmation linéaire : Primal - Dual

 DUALITÉ

PROBLÈME PRIMAL PROBLÈME DUAL

n m
Max Z = c
j =1
j xj Min Y0 = b y i i
i=1

sujet à sujet à
n

a
m

j =1
ij xj  bi i = 1, ...,m a ij yi cj, j = 1, ...,n
i=1
et et
xj  0 j = 1,...,n yi  0 i = 1,...,m
 Dualité

 À tout problème de PL on peut associer un

autre problème PL, son dual le primal

 Le problème dual permet de donner une autre

interprétation économique au problème
primal
 Dualité

Exemple :

régime alimentaire :
• 6 produits alimentaires comme sources
de vitamines A et C
–

• but : minimiser le coût du régime tout en

satisfaisant la valeur nutritionnelle
minimale de chaque vitamine
 Dualité
Exemple :
Valeurs nutritionnelles & coût par produit

produit ( i ) Produits demande

(unités/kg) (unité)
1 2 3 4 5 6

vitamine A 1 0 2 2 1 2 9
vitamine C 0 1 3 1 3 2 19

prix par kg 35 30 60 50 27 22
 Dualité

Le modèle :
xj = quantité consommée de chaque produit (en kg)

min z = 35 x1 + 30 x2 + 60 x3 + 50 x4 + 27 x5 + 22 x6
sc
x1 + 2 x3 + 2 x4 + x5 + 2 x6  9
x2 + 3 x3 + x4 + 3 x5 + 2 x6  19

x1 , x2 , x3 , x4 , x5 , x6  0
 Dualité
Exemple : une autre vision du problème
producteur de cachets de vitamines synthétiques :
• 6 produits alimentaires contenant
vitamines A
et C

• but : être compétitif tout en maximisant

son profit et en remplissant la demande
 Dualité
Exemple :
Prix maximum & composition de chaque produit

produit ( i ) Produits demande

(unité/kg) (unité)
1 2 3 4 5 6

vitamine A 1 0 2 2 1 2 9
vitamine C 0 1 3 1 3 2 19

prix par kg 35 30 60 50 27 22

par exemple, prix compétitif du produit 5  inférieur ou

égal à 27
 Dualité
Le modèle :
wi = prix d’une unité de chaque vitamine
produit 5 = 1 unité de vitamine A + 3 unités de vitamine C
 w1 + 3w2  27
max v = 9 w1 + 19 w2
sc
w1  35
w2  30
2 w1 + 3 w2  60
2 w1 + w2  50
w1 + 3 w2  27
2 w1 + 2 w2  22
w1 , w2  0
 Dualité

Primal Dual

min z = 35 x1 + 30 x2 + 60 x3 max v = 9 w1 + 19 w2
sc
+ 50 x4 + 27 x5 + 22 x6 w1  35
w2  30
sc 2 w1 + 3 w2  60
2 w1 + w2  50
x1 + 2x3 + 2x4 + x5 + 2x6  9 w1 + 3 w2  27
x2 + 3x3 + x4 + 3x5 + 2x6  19 2 w1 + 2 w2  22

x1 , x2 , x3 , x4 , x 5 , x6  0 w1 , w2  0
 Dualité
Primal Dual wb
cx
max v = 9 w1 + 19 w2
min z = 35 x1 + 30 x2 + 60 x 3
sc
+ 50 x4 + 27 x5 + 22 x6 w1  35
sc w2  30
x1 + 2x3 + 2x4 + x5 + 2x6  9 2 w1 + 3 w2  60
2 w1 + w2  50
x2 + 3x3 + x4 + 3x5 + 2x6  19 w1 + 3 w2  27
x1 , x2 , x3 , x4 , x5 , x6  0 2 w1 + 2 w2  22
w1 , w2  0

Ax  b wA  c
DUALITÉ
 Dualité - Généralisation

Primal ( P ) Dual ( D )

min z = cx max v = wb
1 n n1 1 m
sc sc
Ax  b wA  c
mn m1
x 0 w 0
 Primal  Dual

Primal Dual
min z = c x max v = w (-b) = (-w)b
sc sc
Ax  b  (-A) x  -b w (-A)  c  (-w) A  c
x 0 w0

-w  w  min v = wb
sc
Des contraintes primales wA  c
du type  correspondent à w 0
des variables duales wi  0
 Primal  Dual

Primal Dual
min z = c x max v = w + | w - b
sc -b
sc A b
Ax = b  -A x  -b +
w |w - A
 c (w + - w -)A  c
x 0 -A
w0 w+ , w- 0

 min v = wb
Des contraintes primales d’égalité sc
aijxj=bi correspondent à des wA  c
variables duales wi de signe w de signe quelconque
quelconque
 Primal  Dual

Primal Dual
min z = cx  max v = wb
ième contrainte  ième variable
Ai x  bi  wi  0
Ai x  bi  wi  0
Ai x = bi  wi de signe quelconque
jème variable  jème contrainte
xj  0  wA j  cj
xj  0  wA j  cj
xj  0 (de signe quelconque)  wA j = cj
 Propriétés de la dualité

1 - Le dual du dual est le primal

2 - Pour toute paire de solutions réalisables x de P et w
de D, on a cx  wb
x  0 et Ax  b  w (Ax)  wb
cx  (wA)x  wb
w  0 et wA  c  (wA) x  cx
3 - Critère d’optimalité : cx* = w*b
sinon, cx’ < cx* = w*b < w’b ???
4 - Théorème Fondamental de la Dualité : si x* et w* sont
les solutions optimales finies de P et D, respectivement,
alors z* = v*.
En effet z* = cx* = w*b = v*.
 Propriétés de la dualité

5 - Théorème des écarts complémentaires :

pour toute paire de problèmes duaux, une CNS
pour qu’une paire de solutions réalisables x de P
et w de D, soit une paire de solutions optimales
est que :

– si une contrainte i de l’un des problèmes n'est pas

saturée ou est lâche (Ai x > bi ), la variable
correspondante du dual est nulle.
– si une variable de l’un des problèmes est
positive, la contrainte correspondante du dual est
‘‘serrée’’ ( Ai x = bi ).
 Propriétés de la dualité
 Démonstration
Ax  b  Ax - s = b  wAx - ws = wb
wA  c  wA + t = c  wAx + tx = cx -
tx + ws = cx - wb
x et w optimales  cx - wb = 0  tx + ws = 0
x, s, ti > 0  x i = 0
 0  tx = ws = 0 ti x i = 0 
w, x xi > 0  ti = 0
tx, ws → somme de
s i > 0  wi = 0
produits de variables wi si = 0 
non-négatives wi > 0  si = 0
 Analyse de sensibilité
Etude de l’intervalle de variations des cj et des bi pour
lesquelles la solution optimale courante reste
optimale.

 Variation d’un coefficient de la fonction

économique :
•Calcul d’un intervalle de stabilité pour chaque coefficient

 Variation du second membre d’une contrainte :

•Pour quelles valeurs la solution de base obtenue reste-t-elle
optimale ?
 Post-optimisation

 inclusion d’une nouvelle variable de décision

ou d’une nouvelle contrainte.
 altération d’une valeur bi ou d’un coût cj.