RECHERCHE OPERATIONNELLE

Enseignant: Dr KOUAKOU

11 juin 2024
 Introduction Présentation

Activité

Une entreprise fabrique des tables et des chaises à partir de deux matières :
le bois et la peinture, sachant que la réalisation d’une table nécessite 3 m
de bois et 4 kg de peinture, la réalisation d’une chaise nécessite 2 m de
bois et 1 kg de peinture. Les moyens financiers de l’entreprise acceptent un
approvisionnement de 100 m de bois et 120 kg de peinture par semaine.
Les produits ainsi fabriqués fournissent un bénéfice de 500F par table et
300F par chaise vendue.
Questions
À partir de la description donnée, plusieurs questions se révèlent :
• Quelle quantité de table et quelle quantité de chaise peut produire
l’entreprise ?
• Quelles sont les ressources disponibles et les barrières à ne pas dépasser ?
• Quel est le but de l’entreprise ?

2/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 2 / 93
 Introduction Présentation

Activité

Dans ce cas plusieurs propositions intuitives peuvent avoir lieu par exemple :
• 30 tables et 0 chaise avec un bénéfice de 15000F
• 20 tables et 20 chaises avec un bénéfice de 16000F
• 0 table et 50 chaises avec un bénéfice de 15000F
• etc.

3/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 3 / 93
 Introduction Présentation

Activité

Dans ce cas plusieurs propositions intuitives peuvent avoir lieu par exemple :
• 30 tables et 0 chaise avec un bénéfice de 15000F
• 20 tables et 20 chaises avec un bénéfice de 16000F
• 0 table et 50 chaises avec un bénéfice de 15000F
• etc.
Nous remarquons qu’il y a une infinité de solutions possibles. Parmi toutes
les solutions proposées, comment choisir la meilleure ? Existe-t-il une
technique qui pointe directement sur la solution optimale ? Pour répondre à
ces questions plusieurs techniques inspirées de la recherche Opérationnelle
sont proposées.

3/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 3 / 93
 Introduction Présentation

Origine de la recherche opérationnelle

La Recherche Opérationnelle (RO) a commencé juste avant la seconde

guerre mondiale avec la constitution d’équipes de chercheurs en vue
d’étudier les problèmes stratégiques et tactiques engagées dans les
opérations militaires. L’objectif était de trouver la meilleure allocation des
ressources militaires limitées.
Après la 2GM, plusieurs applications en temps de paix ont émergé,
engendrant l’utilisation de la RO.

4/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 4 / 93
 Introduction Présentation

Définition

Recherche opérationnelle :

La recherche opérationnelle (RO) est l’ensemble des méthodes

mathématiques et algorithmiques qui permettent de résoudre un problème
donné de la meilleure façon possible.

5/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 5 / 93
 Introduction Présentation

Définition

Recherche opérationnelle :

La recherche opérationnelle (RO) est l’ensemble des méthodes

mathématiques et algorithmiques qui permettent de résoudre un problème
donné de la meilleure façon possible.

Son domaine reservé est celui des situations dans lesquelles, pour une
raison quelconque, le bon sens se révèle faible ou impuissant.

5/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 5 / 93
 Introduction Présentation

Définition

Recherche opérationnelle :

La recherche opérationnelle (RO) est l’ensemble des méthodes

mathématiques et algorithmiques qui permettent de résoudre un problème
donné de la meilleure façon possible.

Son domaine reservé est celui des situations dans lesquelles, pour une
raison quelconque, le bon sens se révèle faible ou [Link] RO est
avant tout un outil d’aide à la décision.

5/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 5 / 93
 Introduction Présentation

La recherche opérationnelle se présente comme point d’intersection de

plusieurs disciplines car elle fait appel à des connaissances en
mathématiques, en informatique et aussi en économie de l’entreprise.

6/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 6 / 93
 Introduction Présentation

La procédure utilisée par la recherche Opérationnelle RO peut être

schématisée comme suit :

7/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 7 / 93
 Introduction Présentation

La recherche opérationnelle (RO) est utilisée dans les domaines où la prise

de décision fait appel à la résolution des problèmes d’optimisation telle que
les problèmes de :
Dimensionnement ;
Gestion de ressources ;
Rentabilisation des investissements ;
Détection de dysfonctionnements : diagnostics, réparation,
maintenance ;
Partage des ressources ;
Etc.

8/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 8 / 93
 Introduction Présentation

Enjeux de la recherche opérationnelle RO

L’utilisation de la recherche opérationnelle devient de plus en plus sollicitée

dans la vie quotidienne et à différents niveaux puisqu’elle offre plusieurs
avantages et traite plusieurs points tels que :
l’amélioration de la compétitivité des entreprises
l’accession à l’innovation
la proposition des meilleures décisions stratégiques
une meilleure gestion des ressources
Etc.

9/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 9 / 93
 Introduction Présentation

Formulation d’un problème d’optimisation

La modélisation du problème ou le passage du texte vers les équations

mathématiques ne se fait pas de manière aléatoire. Il doit vérifier certaines
conditions et doit passer par plusieurs étapes : l’analyse, la modélisation
des contraintes et du critère à optimiser décrit comme suit :

10/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 10 / 93
 Introduction Présentation

Analyse

Dans cette phase, on commence toujours par l’identification des données

nécessaires à la résolution du problème, les valeurs de consommations
ou les fiches techniques des articles, la quantité des ressources disponibles,
les coûts de transport, la capacité de production, les gains engendrés par
chaque article ou les dépenses établies pour la réalisation d’une
action. Dans cette phase, on détermine les composantes, les enjeux et
les limites du problème. Toutes ces informations sont primordiales pour
la formulation des problèmes.

11/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 11 / 93
 Introduction Présentation

Modélisation

L’optimisation repose toujours sur des modèles mathématiques qui sont

généralement simples. Pour définir le modèle du système, on définit :
XLes variables

12/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 12 / 93
 Introduction Présentation

Modélisation

L’optimisation repose toujours sur des modèles mathématiques qui sont

généralement simples. Pour définir le modèle du système, on définit :
XLes variables
Les variables représentent les inconnues du système.

12/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 12 / 93
 Introduction Présentation

Modélisation

L’optimisation repose toujours sur des modèles mathématiques qui sont

généralement simples. Pour définir le modèle du système, on définit :
XLes variables
Les variables représentent les inconnues du système.
XLes contraintes

12/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 12 / 93
 Introduction Présentation

Modélisation

L’optimisation repose toujours sur des modèles mathématiques qui sont

généralement simples. Pour définir le modèle du système, on définit :
XLes variables
Les variables représentent les inconnues du système.
XLes contraintes
Les objets mathématiques qui assurent l’interaction et la liaison des
variables par rapport aux ressources disponibles et aux données du
problème sont appelées contraintes.

12/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 12 / 93
 Introduction Présentation

Critère à optimiser

Critère à optimiser

13/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 13 / 93
 Introduction Présentation

Critère à optimiser

Critère à optimiser
Représente l’objectif ou le but attendu du problème. Il peut être une
fonction de minimisation lorsqu’il s’agit d’une dépense, d’un investissement
ou une fonction de maximisation lorsqu’il s’agit d’un profit ou de gain.

13/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 13 / 93
 Introduction Présentation

Application

Une entreprise fabrique des tables et des chaises à partir de deux matières :
le bois et la peinture, sachant que la réalisation d’une table nécessite 3 m
de bois et 4 kg de peinture, la réalisation d’une chaise nécessite 2 m de
bois et 1 kg de peinture. Les moyens financiers de l’entreprise acceptent un
approvisionnement de 100 m de bois et 120 kg de peinture par semaine.
Les produits ainsi fabriqués fournissent un bénéfice de 500F par table et
300F par chaise vendue.
1 Question : Formuler le problème

14/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 14 / 93
 Introduction Présentation

1 Solution : Mettre les données dans un tableau

XLes variables
x1 : représente la quantité des tables ;
x2 : représente la quantité des chaises.

15/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 15 / 93
 Introduction Présentation

XLes contraintes
Ṗour le bois : 3x1 + 2x2 ≤ 100 (1)
Ṗour la peinture : 4x1 + x2 ≤ 120 (2)
Pour soulever le problème de la non-négativité des variables, puisqu’on ne
peut pas produire moins deux (-2) tables ou moins vingt (-20) chaises,
nous supposons que les variables sont positives, en ajoutant une contrainte
supplémentaire au problème : x1 , x2 ≥ 0 (3)

16/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 16 / 93
 Introduction Présentation

⇒ Les contraintes :

3x1 + 2x2 ≤ 100 (1)

4x1 + x2 ≤ 120 (2)
x1 , x2 ≥ 0 (3)

17/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 17 / 93
 Introduction Présentation

XFonction objective : Le gain :

z = 500x1 + 300x2

⇒ L’objectif : max z = 500x1 + 300x2

18/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 18 / 93
 Introduction Présentation

Solutions d’un problème

XSolution admissible
On appelle solution admissible (ou solution) d’un problème tout vecteur
x ∈ S qui satisfait toutes les contraintes du problème.
XSolution optimale
On appelle solution optimale x ∗ , la solution parmi toutes les solutions
admissibles qui fournit le meilleur résultat, c’est à dire de trouver le max
pour un problème de maximisation ou trouver le min pour un problème de
minimisation.

19/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 19 / 93
 Introduction Présentation

Application 2
Problème de Production
Une usine fabrique 2 produits P1 et P2 en utilisant un certain nombre de
ressources : post opératoire (machine), main-d’œuvre et emballage. Ces
besoins sont indiqués dans le tableau ci-dessous. Par ailleurs, chaque
ressource est disponible en quantités limitées (cf. tableau).

Les deux produits P1 et P2 rapportent à la vente respectivement des

bénéfices de 600F et 400F par unité. Quelles quantités de produits P1 et
P2, doit produire l’usine afin de maximiser le bénéfice total venant de la
vente des 2 produits ?
20/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 20 / 93
 Introduction Présentation

1 Choix des variables (les inconnues)

2 Choix de la fonction objectif à maximiser
3 Détermination des contraintes

21/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 21 / 93
 Introduction Présentation

Choix des variables (les inconnues)

x1 et x2 sont respectivement les quantités des produits P1 et P2 à fabriquer
(x1 , x2 ∈ N).
Choix de la fonction objectif à maximiser
La fonction objective F correspond au bénéfice total. Elle vaut :

F (x1 , x2 ) = 600x1 + 400x2 .

Le problème se traduit donc par :

max F (x1 , x2 ) = 600x1 + 400x2 .

22/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 22 / 93
 Introduction Présentation

Détermination des contraintes

a) La disponibilité de chacune des ressources s’écrit sous la forme suivante :

3x1 + 9x2 ≤ 81
4x1 + 5x2 ≤ 55
2x1 + x2 ≤ 20

b) Positivité des variables : x1 , x2 ≥ 0.

23/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 23 / 93
 Introduction Présentation

En résumé, le problème de production se modélise sous la forme :

max F (x1 , x2 ) = 600x1 + 400x2




 3x1 + 9x2 ≤ 81

4x + 5x ≤ 55
1 2
sc


 2x 1 + x2 ≤ 20

x , x ≥ 0
1 2

24/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 24 / 93
 Programmation linéaire

Chapitre 1 : Programmation linéaire

Définition
Programmation linéaire sous domaine de la recherche opérationnelle.

C’est le domaine de la recherche opérationnelle qui consiste à chercher

l’optimum d’une fonction économique linéaire de plusieurs variables
F (x1 , x2 , ...) soumises à des contraintes exprimées par des équations ou
inéquations qui sont également linéaires.
Les problèmes de programmation linéaire (PL) sont des problèmes
d’optimisation où la fonction objective et les contraintes sont toutes
linéaires.

25/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 25 / 93
 Programmation linéaire

Formulations mathématiques
Pour un problème de maximisation on a un système de la forme :

26/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 26 / 93
 Programmation linéaire

Formulations mathématiques
Pour un problème de maximisation on a un système de la forme :

26/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 26 / 93
 Programmation linéaire

Formulations mathématiques
Pour un problème de maximisation on a un système de la forme :

Pour un problème de minimisation, on a un système de la forme :

26/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 26 / 93
 Programmation linéaire

Formulations mathématiques
Pour un problème de maximisation on a un système de la forme :

Pour un problème de minimisation, on a un système de la forme :

A ∈ Mm,n (R)
26/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 26 / 93
 Programmation linéaire

Les étapes de la formulation d’un programme linéaire

1 Identifier les variables du problème à valeur inconnue et représenter de

manière symbolique.

27/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 27 / 93
 Programmation linéaire

Les étapes de la formulation d’un programme linéaire

1 Identifier les variables du problème à valeur inconnue et représenter de

manière symbolique.
2 Identifier l’objectif et le représenter sous forme de fonctions linéaires
des variables de décision. Spécifier si l’objectif est de maximiser ou de
minimiser.

27/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 27 / 93
 Programmation linéaire

Les étapes de la formulation d’un programme linéaire

1 Identifier les variables du problème à valeur inconnue et représenter de

manière symbolique.
2 Identifier l’objectif et le représenter sous forme de fonctions linéaires
des variables de décision. Spécifier si l’objectif est de maximiser ou de
minimiser.
3 Identifier les restrictions du problème et les exprimer par un système
d’équation ou d’inéquations linéaires

27/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 27 / 93
 Programmation linéaire

28/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 28 / 93
 Programmation linéaire Forme standard et forme canonique d’un programme linéaire

Définition
Un programme linéaire est sous forme standard lorsque toutes ses
contraintes sont des égalités et toutes ses variables sont non-négatives.

29/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 29 / 93
 Programmation linéaire Forme standard et forme canonique d’un programme linéaire

Définition
Un programme linéaire est sous forme standard lorsque toutes ses
contraintes sont des égalités et toutes ses variables sont non-négatives.

Représentation matricielle
T
max
( Z =c x
Ax = b
sc
x ≥0

n variables, m contraintes, c, x ∈ Rn , b ∈ Rm et A ∈ Mm,n (R)

29/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 29 / 93
 Programmation linéaire Forme standard et forme canonique d’un programme linéaire

Définition
Un programme linéaire est sous forme canonique lorsque toutes ses
contraintes sont des inégalités et toutes ses variables sont non-négatives.

30/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 30 / 93
 Programmation linéaire Forme standard et forme canonique d’un programme linéaire

Définition
Un programme linéaire est sous forme canonique lorsque toutes ses
contraintes sont des inégalités et toutes ses variables sont non-négatives.
Représentation matricielle
T
max
( Z =c x
Ax ≤ b
sc
x ≥0

n variables, m contraintes, c, x ∈ Rn , b ∈ Rm et A ∈ Mm,n (R)

30/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 30 / 93
 Programmation linéaire Forme standard et forme canonique d’un programme linéaire

Tout programme linéaire peut s’écrire sous forme standard et sous forme
canonique.

31/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 31 / 93
 Programmation linéaire Forme standard et forme canonique d’un programme linéaire

Tout programme linéaire peut s’écrire sous forme standard et sous forme
canonique.

preuve
•Une contrainte d’inégalité Ax ≤ b peut être transformée en égalité par
l’introduction d’une variable d’écart :

Ax + s = b
s ≥ 0

• Une contrainte d’égalité Ax = b peut être remplacée par deux inégalités :

Ax ≤ b
−Ax ≤ −b

31/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 31 / 93
 Programmation linéaire Forme standard et forme canonique d’un programme linéaire

Application 2
Reprenons l’exemple du problème de production de l’introduction.
Problème de Production
Une usine fabrique 2 produits P1 et P2 en utilisant un certain nombre de
ressources : post opératoire (machine), main-d’œuvre et emballage. Ces
besoins sont indiqués dans le tableau ci-dessous. Par ailleurs, chaque
ressource est disponible en quantités limitées (cf. tableau).

Les deux produits P1 et P2 rapportent à la vente respectivement des

bénéfices de 600F et 400F par unité. Quelles quantités de produits P1 et
P2, doit produire l’usine afin de maximiser le bénéfice total venant de la
vente des 2 produits ?
32/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 32 / 93
 Programmation linéaire Forme standard et forme canonique d’un programme linéaire

On rappelle que, le problème de production se modélise sous la forme :

Maximiser F (x1 , x2 ) = 600x1 + 400x2




 4x1 + 5x2 ≤ 55

x + 3x ≤ 27
1 2
sc


 2x 1 + x2 ≤ 20

x , x ≥ 0
1 2

33/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 33 / 93
 Programmation linéaire Forme standard et forme canonique d’un programme linéaire

Sous forme standard (en introduisant des variables d’écart), le PL s’écrit :

Maximiser F (x1 , x2 ) = 600x1 + 400x2




 4x1 + 5x2 + x3 = 55

x + 3x + x = 27
1 2 4
sc


 2x 1 + x2 + x5 = 20

x , x , x , x , x ≥ 0
1 2 3 4 5

34/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 34 / 93
 Programmation linéaire Résolution de programmes linéaires

Résolution graphique

La résolution graphique d’un problème linéaire consiste à tracer la droite

qui sépare les demi-plans pour chaque contrainte tout en conservant le
demi-plan acceptable, c’est-à-dire le demi-plan des solutions réalisables
pour la contrainte. L’intersection des différents demi-plans de toutes les
contraintes sans oublier les contraintes de positivité forme le polygone des
solutions, appelé aussi "région des solutions admissibles".

35/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 35 / 93
 Programmation linéaire Résolution de programmes linéaires

Exemple

Exemple Considérons le problème suivant :

Maximiser F (x1 , x2 ) = 600x1 + 400x2




 4x1 + 5x2 ≤ 55

x + 3x ≤ 27
1 2
sc


 2x1 + x2 ≤ 20

x , x ≥ 0
1 2

36/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 36 / 93
 Programmation linéaire Résolution de programmes linéaires

On commence à tracer chaque contrainte séparément

4x1 + 5x2 ≤ 55

37/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 37 / 93
 Programmation linéaire Résolution de programmes linéaires

On commence à tracer chaque contrainte séparément

4x1 + 5x2 ≤ 55

37/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 37 / 93
 Programmation linéaire Résolution de programmes linéaires

38/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 38 / 93
 Programmation linéaire Résolution de programmes linéaires

39/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 39 / 93
 Programmation linéaire La méthode du simplexe

La méthode de Simplexe

La méthode de Simplexe
Cette méthode est l’outil principal de résolution des problèmes de
programmation linéaire. Elle consiste à suivre un certain nombre d’étapes
avant d’obtenir la solution d’un problème donné.

40/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 40 / 93
 Programmation linéaire La méthode du simplexe

La méthode de Simplexe

La méthode de Simplexe
Cette méthode est l’outil principal de résolution des problèmes de
programmation linéaire. Elle consiste à suivre un certain nombre d’étapes
avant d’obtenir la solution d’un problème donné. Il s’agit d’une méthode
algébrique itérative qui permet de trouver la solution exacte d’un problème
de programmation linéaire en un nombre fini d’étapes.

40/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 40 / 93
 Programmation linéaire La méthode du simplexe

La méthode de Simplexe

La méthode de Simplexe
Cette méthode est l’outil principal de résolution des problèmes de
programmation linéaire. Elle consiste à suivre un certain nombre d’étapes
avant d’obtenir la solution d’un problème donné. Il s’agit d’une méthode
algébrique itérative qui permet de trouver la solution exacte d’un problème
de programmation linéaire en un nombre fini d’étapes. Une implémentation
de cette procédure a permis de résoudre des programmes avec un peu plus
de quelques milliers de variables.

40/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 40 / 93
 Programmation linéaire La méthode du simplexe

Principes de l’algorithme du simplexe

Le principe de l’algorithme du simplexe comprend un certains nombres

d’étapes à suivre :
Modifier la forme canonique et en introduisant une variable d’écart
positive ou nulle permettant d’écrire les contraintes avec égalités.
A partir de la forme standard obtenue de la forme canonique, il est
possible d’utiliser soit la résolution algébrique soit la représentation en
tableau (méthode privilégiée).

41/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 41 / 93
 Programmation linéaire La méthode du simplexe

Démarche

Démarche 1 : On démarre l’application de l’approche (méthode du

simplexe) par la transformation des contraintes d’inégalité en contraintes
d’égalité en ajoutant les variables d’écart.

42/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 42 / 93
 Programmation linéaire La méthode du simplexe

Démarche

Démarche 1 : On démarre l’application de l’approche (méthode du

simplexe) par la transformation des contraintes d’inégalité en contraintes
d’égalité en ajoutant les variables d’écart.
Démarche 2 : Dans un second temps nous sélectionnons les variables
originales comme variables hors-base et les variables d’écarts comme
variable basique. puis nous effectuerons une permutation entre une variable
hors-base de notre choix qui sera remplacée par une variable de base
(entrante). Le choix de la variable entrante repose sur la variable dont le
coefficient est le plus élevé dans la fonction objective.

42/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 42 / 93
 Programmation linéaire La méthode du simplexe

Démarche

Démarche 1 : On démarre l’application de l’approche (méthode du

simplexe) par la transformation des contraintes d’inégalité en contraintes
d’égalité en ajoutant les variables d’écart.
Démarche 2 : Dans un second temps nous sélectionnons les variables
originales comme variables hors-base et les variables d’écarts comme
variable basique. puis nous effectuerons une permutation entre une variable
hors-base de notre choix qui sera remplacée par une variable de base
(entrante). Le choix de la variable entrante repose sur la variable dont le
coefficient est le plus élevé dans la fonction objective.
Démarche 3 : La variable sortante est la première à s’annuler. On répète le
processus jusqu’à ce que tous les coefficients de fonction objective soient
négatifs ou nuls. Dans ce cas, on arrête et la solution optimale est trouvée.

42/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 42 / 93
 Programmation linéaire La méthode du simplexe

Exemple

Considérons le problème suivant :

Maximiser F (= 40x1 + 60x2 )




 2x1 + x2 ≤ 70

x + x ≤ 40
1 2
sc


 x1 + 3x2 ≤ 90

x , x ≥ 0
1 2

43/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 43 / 93
 Programmation linéaire La méthode du simplexe

Soit e1 , e2 , e3 , les variables d’écart relatif respectivement aux contraintes,

qui pertmettent de transformer contraintes d’inégalité pour obtenir les
égalités suivantes :

2x1 + x2 + e1 = 70

x1 + x2 + e2 = 40

x1 + 3x2 + e3 = 90


44/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 44 / 93
 Programmation linéaire La méthode du simplexe

Pour trouver la solution on impose deux des variables à zéro et on déduit

les valeurs des trois variables restantes. Ce qui donne :
Pour les variables hors base, on a :

45/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 45 / 93
 Programmation linéaire La méthode du simplexe

Pour trouver la solution on impose deux des variables à zéro et on déduit

les valeurs des trois variables restantes. Ce qui donne :
Pour les variables hors base, on a :

x1 = 0
x2 = 0

Pour les variables de base, on a :

45/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 45 / 93
 Programmation linéaire La méthode du simplexe

Pour trouver la solution on impose deux des variables à zéro et on déduit

les valeurs des trois variables restantes. Ce qui donne :
Pour les variables hors base, on a :

x1 = 0
x2 = 0

Pour les variables de base, on a :

e1 = 70
e2 = 40
e3 = 90

45/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 45 / 93
 Programmation linéaire La méthode du simplexe

Pour trouver la solution on impose deux des variables à zéro et on déduit

les valeurs des trois variables restantes. Ce qui donne :
Pour les variables hors base, on a :

x1 = 0
x2 = 0

Pour les variables de base, on a :

e1 = 70
e2 = 40
e3 = 90

Et la valeur de la fonction objective F = 40x1 + 60x2 = 0

45/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 45 / 93
 Programmation linéaire La méthode du simplexe

La question qui se pose est : Est-il possible d’augmenter F ?

46/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 46 / 93
 Programmation linéaire La méthode du simplexe

La question qui se pose est : Est-il possible d’augmenter F ? Pour répondre

à cette question, on vérifie la fonction objective.

46/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 46 / 93
 Programmation linéaire La méthode du simplexe

La question qui se pose est : Est-il possible d’augmenter F ? Pour répondre

à cette question, on vérifie la fonction objective. Si les coefficients sont
positifs, ce qui est le cas, on a donc la possibilité d’augmenter F.

46/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 46 / 93
 Programmation linéaire La méthode du simplexe

La question qui se pose est : Est-il possible d’augmenter F ? Pour répondre

à cette question, on vérifie la fonction objective. Si les coefficients sont
positifs, ce qui est le cas, on a donc la possibilité d’augmenter F.
On favorise l’augmentation de la variable qui a le plus grand coefficient
dans la fonction objective.
Donc on choisit x2 en maintenant x1 = 0.

46/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 46 / 93
 Programmation linéaire La méthode du simplexe

On remplace x1 = 0 dans les équations contenant les variables d’écart

2x1 + x2 + e1 = 70 =⇒ x2 + e1 = 70 (1)
x1 + x2 + e2 = 40 =⇒ x2 + e2 = 40 (2)
x1 + 3x2 + e3 = 90 =⇒ 3x2 + e3 = 90 (3)

On réécrit les variables restantes en fonction de x2 pour chaque équation.

47/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 47 / 93
 Programmation linéaire La méthode du simplexe

On remplace x1 = 0 dans les équations contenant les variables d’écart

2x1 + x2 + e1 = 70 =⇒ x2 + e1 = 70 (1)
x1 + x2 + e2 = 40 =⇒ x2 + e2 = 40 (2)
x1 + 3x2 + e3 = 90 =⇒ 3x2 + e3 = 90 (3)

On réécrit les variables restantes en fonction de x2 pour chaque équation.

e1 = 70 − x2 ≥ 0 =⇒ x2 ≤ 70 (4)
e2 = 40 − x2 ≥ 0 =⇒ x2 ≤ 40 (5)
e3 = 90 − 3x2 ≥ 0 =⇒ x2 ≤ 30 (6)

47/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 47 / 93
 Programmation linéaire La méthode du simplexe

On remplace x1 = 0 dans les équations contenant les variables d’écart

2x1 + x2 + e1 = 70 =⇒ x2 + e1 = 70 (1)
x1 + x2 + e2 = 40 =⇒ x2 + e2 = 40 (2)
x1 + 3x2 + e3 = 90 =⇒ 3x2 + e3 = 90 (3)

On réécrit les variables restantes en fonction de x2 pour chaque équation.

e1 = 70 − x2 ≥ 0 =⇒ x2 ≤ 70 (4)
e2 = 40 − x2 ≥ 0 =⇒ x2 ≤ 40 (5)
e3 = 90 − 3x2 ≥ 0 =⇒ x2 ≤ 30 (6)

On peut augmenter le valeur de x2 au maximum à 30 puisque c’est la

valeur qui permet de satisfaire les équations ci-dessus.

47/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 47 / 93
 Programmation linéaire La méthode du simplexe

Nouvelle solution admissible :

48/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 48 / 93
 Programmation linéaire La méthode du simplexe

Nouvelle solution admissible :

x1 = 0

48/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 48 / 93
 Programmation linéaire La méthode du simplexe

Nouvelle solution admissible :

x1 = 0 x2 = 30

48/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 48 / 93
 Programmation linéaire La méthode du simplexe

Nouvelle solution admissible :

x1 = 0 x2 = 30 e1 = 40

48/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 48 / 93
 Programmation linéaire La méthode du simplexe

Nouvelle solution admissible :

x1 = 0 x2 = 30 e1 = 40 e2 = 10

48/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 48 / 93
 Programmation linéaire La méthode du simplexe

Nouvelle solution admissible :

x1 = 0 x2 = 30 e1 = 40 e2 = 10 e3 = 0

On remarque bien que x1 = 0 est toujours maintenu à zéro. Par ailleurs, e3

est passé de 90 à 0 et x2 est passé de 0 à 30. Donc on déduit que pour
cette étape la variable sortante de la base est e3 et la variable entrante
dans la base est x2 .
la valeur de la fonction objective F = 40x1 + 60x2 = 1800

48/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 48 / 93
 Programmation linéaire La méthode du simplexe

Les coefficients de la fonction objective sont positifs. On va donc remplacer

l’expression de x2 obtenu à partir de (3) dans les autres équations, on
obtient :

49/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 49 / 93
 Programmation linéaire La méthode du simplexe

Les coefficients de la fonction objective sont positifs. On va donc remplacer

l’expression de x2 obtenu à partir de (3) dans les autres équations, on
obtient :
5 1
x1 + e1 − e3 = 40 (7)
3 3
2 1
x1 + e2 − e3 = 10 (8)
3 3
1 1
x1 + x2 + e3 = 30 (9)
3 3
Nouvelle expression de la fonction objective

49/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 49 / 93
 Programmation linéaire La méthode du simplexe

Les coefficients de la fonction objective sont positifs. On va donc remplacer

l’expression de x2 obtenu à partir de (3) dans les autres équations, on
obtient :
5 1
x1 + e1 − e3 = 40 (7)
3 3
2 1
x1 + e2 − e3 = 10 (8)
3 3
1 1
x1 + x2 + e3 = 30 (9)
3 3
Nouvelle expression de la fonction objective F = 1800 + 20x1 − 20e3

49/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 49 / 93
 Programmation linéaire La méthode du simplexe

Les coefficients de la fonction objective sont positifs. On va donc remplacer

l’expression de x2 obtenu à partir de (3) dans les autres équations, on
obtient :
5 1
x1 + e1 − e3 = 40 (7)
3 3
2 1
x1 + e2 − e3 = 10 (8)
3 3
1 1
x1 + x2 + e3 = 30 (9)
3 3
Nouvelle expression de la fonction objective F = 1800 + 20x1 − 20e3
D’après l’expression de la fonction objective de l’étape précédente on
choisit d’augmenter x1 en gardant e3 = 0

49/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 49 / 93
 Programmation linéaire La méthode du simplexe

5 1 5
x1 + e1 − e3 = 40 e1 = 40 − x1 ≥ 0 =⇒ x1 ≤ 24 (10)
3 3 3
2 1 2
x1 + e2 − e3 = 10 e2 = 10 − x1 ≥ 0 =⇒ x1 ≤ 15 (11)
3 3 3
1 1 1
x1 + x2 + e3 = 30 e3 = 30 − x1 ≥ 0 =⇒ x1 ≤ 90 (12)
3 3 3
(13)

La valeur maximale admissible pour x1 = 15.

50/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 50 / 93
 Programmation linéaire La méthode du simplexe

Nouvelle solution admissible :

x1 = 15

51/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 51 / 93
 Programmation linéaire La méthode du simplexe

Nouvelle solution admissible :

x1 = 15 x2 = 25

51/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 51 / 93
 Programmation linéaire La méthode du simplexe

Nouvelle solution admissible :

x1 = 15 x2 = 25 e1 = 15

51/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 51 / 93
 Programmation linéaire La méthode du simplexe

Nouvelle solution admissible :

x1 = 15 x2 = 25 e1 = 15 e2 = 0

51/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 51 / 93
 Programmation linéaire La méthode du simplexe

Nouvelle solution admissible :

x1 = 15 x2 = 25 e1 = 15 e2 = 0 e3 = 0

L’expression de la nouvelle valeur du critère est :

51/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 51 / 93
 Programmation linéaire La méthode du simplexe

Nouvelle solution admissible :

x1 = 15 x2 = 25 e1 = 15 e2 = 0 e3 = 0

L’expression de la nouvelle valeur du critère est :

F = 2100 − 30e2 − 10e3

Les coefficients de e2 et e3 dans la fonction objective de la dernière étape

sont négatifs. Donc augmenter la valeur de e2 et e3 implique une
diminution de la valeur du critère F.
Il n’existe donc plus d’augmentation et d’amélioration possible. La dernière
solution obtenue représente la solution optimale qui est égale à 2100.

51/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 51 / 93
 Programmation linéaire La méthode du simplexe

Résolution par Tableaux de simplexe

On commence par la transformation des contraintes d’inégalité en

contraintes d’égalité en introduisant des variables d’écart.
XÉtape 1

52/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 52 / 93
 Programmation linéaire La méthode du simplexe

Résolution par Tableaux de simplexe

On commence par la transformation des contraintes d’inégalité en

contraintes d’égalité en introduisant des variables d’écart.
XÉtape 1
On construit un tableau à deux dimensions n × m où le nombre de colonnes
m est égal au nombre de variables (les variables de décision plus les
variables d’écart) dans le système plus une colonne de solution. Le nombre
de lignes est égal au nombre d’équation dans le système sans considération
des contraintes de positivité.

52/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 52 / 93
 Programmation linéaire La méthode du simplexe

Résolution par Tableaux de simplexe

On commence par la transformation des contraintes d’inégalité en

contraintes d’égalité en introduisant des variables d’écart.
XÉtape 1
On construit un tableau à deux dimensions n × m où le nombre de colonnes
m est égal au nombre de variables (les variables de décision plus les
variables d’écart) dans le système plus une colonne de solution. Le nombre
de lignes est égal au nombre d’équation dans le système sans considération
des contraintes de positivité.
A la première itération, on sélectionne la variable qui a le coefficient le plus
élevé dans la ligne objective (fonction objective). On encadre la colonne de
la variable entrante que l’on appelle " colonne pivot".

52/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 52 / 93
 Programmation linéaire La méthode du simplexe

XÉtape 2
On détermine le minimum du rapport du coefficient du second membre
(membre de droite) de chaque contrainte sur le coefficient correspondant à
la colonne. Dans le cas où le coefficient dans la colonne entrante est
négatif ou infini, on ne le compte pas dans le calcul du minimum. On
encadre alors la ligne où le minimum se produit. Cette ligne reçoit le nom
de "ligne pivot".

53/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 53 / 93
 Programmation linéaire La méthode du simplexe

XÉtape 2
On détermine le minimum du rapport du coefficient du second membre
(membre de droite) de chaque contrainte sur le coefficient correspondant à
la colonne. Dans le cas où le coefficient dans la colonne entrante est
négatif ou infini, on ne le compte pas dans le calcul du minimum. On
encadre alors la ligne où le minimum se produit. Cette ligne reçoit le nom
de "ligne pivot".
Le coefficient qui se trouve à l’intersection de la colonne pivot et de la ligne
pivot est appelé "élément pivot".

53/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 53 / 93
 Programmation linéaire La méthode du simplexe

XÉtape 3
On reconstruit le tableau du simplexe (il faut conserver la même dimension
du tableau). On commence, d’abord, par construire la nouvelle ligne pivot
qui se calcule de la manière suivante :

Ancienne ligne pivot

Nouvelle ligne pivot =
Element pivot

Puis, on calcule les autres lignes par la formule suivante :

54/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 54 / 93
 Programmation linéaire La méthode du simplexe

Exemple

Une entreprise disposant de 10 000 m2 de planches de bois en réserve

fabrique et commercialise 2 types de boîtes en bois. La fabrication d’une
boîte en bois de type 1 et de type 2 requiert, respectivement, 1 et 2 m2 de
bois ainsi que 2 et 3 minutes de temps d’assemblage. Seules 200 heures de
travail sont disponibles pendant la semaine à venir. Les boites sont clouées
et, il faut quatre fois plus de clou pour une boîte du second type que pour
une du premier. Le stock de clous disponible permet d’assembler au
maximum 15 000 boîtes du premier type. Les boîtes sont vendues,
respectivement, 3 et 5 du chiffre d’affaires.

55/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 55 / 93
 Programmation linéaire La méthode du simplexe

Formalisation du problème
x1 quantité de boîtes en bois de type 1
x2 : quantité de boîtes en bois de type 2

Maximiser Z = 3x1 + 5x2


x1 + 2x2 ≤ 10.000



2x + 3x ≤ 12.000
1 2
sc


x1 + 4x2 ≤ 15.000

x , x ≥ 0
1 2

56/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 56 / 93
 Programmation linéaire La méthode du simplexe

On met le programme linéaire sous sa forme standard

Maximiser Z = 3x1 + 5x2




x1 + 2x2 + x3 = 10.000

2x + 3x + x = 12.000
1 2 4
sc


x1 + 4x2 + x5 = 15.000

x , x ≥ 0
1 2

57/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 57 / 93
 Programmation linéaire La méthode du simplexe

On peut réecrire le pogramme linéaire en fonction de toutes les variables du

systèmes (variables de décision et variables d’écarts)

58/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 58 / 93
 Programmation linéaire La méthode du simplexe

On peut réecrire le pogramme linéaire en fonction de toutes les variables du

systèmes (variables de décision et variables d’écarts)

Maximiser Z = 3x1 + 5x2 + 0x3 + 0x4 + 0x5


x1 + 2x2 + x3 + 0x4 + 0x5 = 10.000



2x + 3x + 0x + x + 0x = 12.000
1 2 3 4 5
sc


x1 + 4x2 + 0x3 + 0x4 + x5 = 15.000

x , x x x x ≥ 0
1 2 3 4 5

58/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 58 / 93
 Programmation linéaire La méthode du simplexe

On obtient le tableau suivant

59/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 59 / 93
 Programmation linéaire La méthode du simplexe

On obtient le tableau suivant

59/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 59 / 93
 Programmation linéaire La méthode du simplexe

Itération 2
Une fois l’élément pivot déterminé, on calcule la nouvelle ligne pivot en
divisant l’ancienne ligne par l’élément pivot, ce qui donne :

On la place dans le nouveau tableau en conservant la même position que

dans le premier tableau sauf que la variable dans la colonne pivot prend la
place de la variable de la ligne pivot comme suit :

60/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 60 / 93
 Programmation linéaire La méthode du simplexe

61/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 61 / 93
 Programmation linéaire La méthode du simplexe

Et de la même manière, on applique le même calcule pour les lignes de x3

et de Z . On les place dans les zones appropriées dans le tableau de la
deuxième itération.

61/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 61 / 93
 Programmation linéaire La méthode du simplexe

62/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 62 / 93
 Programmation linéaire La méthode du simplexe

62/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 62 / 93
 Programmation linéaire La méthode du simplexe

À la fin de cette itération, on vérifie tous les coefficients de ligne Z . S’ils

sont négatifs ou nuls on s’arrête. On a trouvé la solution optimale. Ce n’est
pas le cas ici, le coefficient de x1 est positif. On construit donc une nouvelle
itération et un nouveau tableau de la même manière que pour l’itération 2.

63/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 63 / 93
 Programmation linéaire La méthode du simplexe

À la fin de cette itération, on vérifie tous les coefficients de ligne Z . S’ils

sont négatifs ou nuls on s’arrête. On a trouvé la solution optimale. Ce n’est
pas le cas ici, le coefficient de x1 est positif. On construit donc une nouvelle
itération et un nouveau tableau de la même manière que pour l’itération 2.
Itération 3

63/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 63 / 93
 Programmation linéaire La méthode du simplexe

À la fin de cette itération, on vérifie tous les coefficients de ligne Z . S’ils

sont négatifs ou nuls on s’arrête. On a trouvé la solution optimale. Ce n’est
pas le cas ici, le coefficient de x1 est positif. On construit donc une nouvelle
itération et un nouveau tableau de la même manière que pour l’itération 2.
Itération 3

D’après le tableau de l’itération 3, on remarque que les coefficients de la

ligne Z , sont négatifs ou nuls. Donc on s’arrête. On a trouvé la solution
optimale avec :
x1 = 600 x2 = 3.600 et Z = 19.800
63/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 63 / 93
Programmation linéaire Dualité
 Programmation linéaire Dualité

Exemple introductif

Une entreprise dispose de deux machine M1 et M2 pour fabriquer deux

produits A et B. La production de A nécessite 1h de M1 et 2h de M2 . La
production de B nécessite 1h de M1 et 1h de M2 .
Capacité horaire de 70h et 90h respectivement pour M1 et M2 . La marge
sur coût variable unitaire est de 30 euros et 20 euros respectivement pour
A et B.

Maximiser F (x1 , x2 ) = 30x1 + 20x2


x1 + x2 ≤ 70

sc 2x1 + x2 ≤ 90

x1 , x2 ≥ 0


64/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 64 / 93
 Programmation linéaire Dualité

Problème de production

Une entreprise dispose de deux machines M1 et M2 pour fabriquer deux

produits A et B. La production de A nécessite 1h de M1 et 2h de M2 . La
production de B nécessite 1h de M1 et 1h de M2 .
Capacité horaire de 70h et 90h respectivement pour M1 et M2 . La marge
sur coût variable unitaire est de 30 euros et 20 euros respectivement pour
A et B.

65/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 65 / 93
 Programmation linéaire Dualité

Problème de production

Une entreprise dispose de deux machines M1 et M2 pour fabriquer deux

produits A et B. La production de A nécessite 1h de M1 et 2h de M2 . La
production de B nécessite 1h de M1 et 1h de M2 .
Capacité horaire de 70h et 90h respectivement pour M1 et M2 . La marge
sur coût variable unitaire est de 30 euros et 20 euros respectivement pour
A et B.
Pour certaines raisons, l’entreprise décide de vendre toutes ses ressources.
Un acheteur se présente et propose à l’entreprise les prix unitaires y1 et y2
pour chacune des ressources (heures machines). L’entreprise acceptera de
lui vendre toutes ses ressources uniquement si le prix de vente est au moins
égal au profit qu’elle ferait en vendant ses produits. De son coté, l’acheteur
cherche à minimiser ses dépenses. Quels prix unitaires y1 et y2 l’acheteur
doit-il proposer à l’entreprise pour qu’elle accepte de vendre toutes ses
ressources ?

65/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 65 / 93
 Programmation linéaire Dualité

Programme dual

Minimiser Z (x1 , x2 ) = 70y1 + 90y2


y1 + 2y2 ≥ 30

sc y1 + y2 ≥ 20

y1 , y2 ≥ 0


66/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 66 / 93
 Programmation linéaire Dualité

La dualité est une façon de visualiser un problème donné sous un autre

angle. La dualité d’un problème, peut-être assimilé à l’effet miroir où on
arrive à voir la même chose sauf que les coordonnées de la base utilisée ne
sont pas les mêmes.
La dualité est un concept important en recherche opérationnelle. Tout
programme linéaire admet un programme dual. Autrement dit, à tout
problème de maximisation peut être associé un problème de minimisation
et à tout problème de minimisation peut être associé un problème de
maximisation. Le premier est appelé : primal, le second étant son dual.

67/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 67 / 93
 Programmation linéaire Dualité

Les coefficients de la fonction économique du problème 1 sont les

seconds membres des contraintes du problème 2 et vice-versa.
Les variables des deux problèmes sont positives ou nulles.
Les inégalités d’infériorité deviennent des inégalités de supériorité et
inversement.
Les variables de décisions du problème primal deviennent des variables
d’écarts dans le problème dual et les variables d’écarts deviennent les
variables de décisions.

Le problème 2 est le dual du problème 1 et le problème 1 est appelé

problème primal. Les rôles peuvent être inversés, d’où le dual du dual est le
primal.

68/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 68 / 93
 Programmation linéaire Dualité

L’intérêt du passage au problème dual est de pouvoir dans certains cas

résoudre le problème dual à partir de la solution du problème primal.

69/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 69 / 93
 Programmation linéaire Dualité

L’intérêt du passage au problème dual est de pouvoir dans certains cas

résoudre le problème dual à partir de la solution du problème primal.
Théorème 1
Si le primal admet une solution, le dual en admet une également et le max
de l’un est le min de l’autre.

69/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 69 / 93
 Programmation linéaire Dualité

Nous voulons résoudre notre programme dual.

Minimiser Z (y1 , y2 ) = 70y1 + 90y2


y1 + 2y2 ≥ 30

sc y1 + y2 ≥ 20

y1 , y2 ≥ 0


70/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 70 / 93
 Programmation linéaire Dualité

Nous appellerons notre programme dual, le programme primal. Donc notre

nouveau dual est l’ancien primal.

71/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 71 / 93
 Programmation linéaire Dualité

Nous appellerons notre programme dual, le programme primal. Donc notre

nouveau dual est l’ancien primal.

Maximiser F (x1 , x2 ) = 30x1 + 20x2


x1 + x2 ≤ 70

sc 2x1 + x2 ≤ 90

x1 , x2 ≥ 0


71/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 71 / 93
 Programmation linéaire Dualité

Forme canonique de notre primal,

72/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 72 / 93
 Programmation linéaire Dualité

Forme canonique de notre primal,

Minimiser Z (y1 , y2 ) = 70y1 + 90y2


y1 + 2y2 ≥ 30

sc y1 + y2 ≥ 20

y1 , y2 ≥ 0


72/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 72 / 93
 Programmation linéaire Dualité

Forme canonique de notre primal,

Minimiser Z (y1 , y2 ) = 70y1 + 90y2


y1 + 2y2 ≥ 30

sc y1 + y2 ≥ 20

y1 , y2 ≥ 0


Forme standart du primal,

72/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 72 / 93
 Programmation linéaire Dualité

Forme canonique de notre primal,

Minimiser Z (y1 , y2 ) = 70y1 + 90y2


y1 + 2y2 ≥ 30

sc y1 + y2 ≥ 20

y1 , y2 ≥ 0


Forme standart du primal,

Minimiser Z (y1 , y2 ) = 70y1 + 90y2


y1 + 2y2 − u1 = 30

sc y1 + y2 − u2 = 20

y1 , y2 , u1 , u2 ≥ 0


72/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 72 / 93
 Programmation linéaire Dualité

Forme standart du dual,

73/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 73 / 93
 Programmation linéaire Dualité

Forme standart du dual,

Maximiser F (x1 , x2 ) = 30x1 + 20x2


x1 + x2 + e1 = 70

sc 2x1 + x2 + e2 = 90

x1 , x2 , e1 , e2 ≥ 0


73/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 73 / 93
 Programmation linéaire Dualité

x1 x2 e1 e2 2nd membre rapport

70
e1 1 1 1 0 70 1
90
e2 2 1 0 1 90 2
F 30 20 0 0 0

74/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 74 / 93
 Programmation linéaire Dualité

x1 x2 e1 e2 2nd membre rapport

70
e1 1 1 1 0 70 1
90
e2 2 1 0 1 90 2
F 30 20 0 0 0
1
e1 0 2 1 − 12 25 50
1 1
x1 1 2 0 2 45 90
F 0 5 0 -15 -1350

74/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 74 / 93
 Programmation linéaire Dualité

x1 x2 e1 e2 2nd membre rapport

70
e1 1 1 1 0 70 1
90
e2 2 1 0 1 90 2
F 30 20 0 0 0
1
e1 0 2 1 − 12 25 50
1 1
x1 1 2 0 2 45 90
F 0 5 0 -15 -1350
x2 0 1 2 -1 50
x1 1 0 -1 1 20
F 0 0 -10 -10 -1600

74/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 74 / 93
 Programmation linéaire Dualité




y1 ←→ e1

y ←→ e
2 2


u1 ←→ x1

u ←→ x
2 2

75/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 75 / 93
 Programmation linéaire Dualité




y1 ←→ e1

y ←→ e
2 2


u1 ←→ x1

u ←→ x
2 2


e = 10 ←→ y1 = 10
 1


e2 = 10 ←→ y2 = 10



x1 = 0 ←→ u1 = 0

x2 = 0 ←→ u2 = 0





F = 1600 ←→ Z = 1600


75/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 75 / 93
 Programmation linéaire Dualité

Exemple 2
Résoudre le programme suivant :
min Z = 2x1 + 5x2 + 3x3


x1 ≥ 10

x2 ≥ 15



SC x1 + 2x2 + x3 ≥ 60

2x1 + x2 + 2x3 ≥ 95





x1 ; x2 ; x3 ≥ 0.


76/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 76 / 93
 Programmation linéaire Dualité

Exemple 2
Résoudre le programme suivant :
min Z = 2x1 + 5x2 + 3x3


x1 ≥ 10

x2 ≥ 15



SC x1 + 2x2 + x3 ≥ 60

2x1 + x2 + 2x3 ≥ 95





x1 ; x2 ; x3 ≥ 0.


Le dual de notre problème est

Maximiser F (x1 , x2 , x3 , x4 ) = 10x1 + 15x2 + 60x3 + 95x4

x1 + x3 + 2x4 ≤ 2


x2 + 2x3 + x4 ≤ 5



sc x3 + 2x4 ≤ 3

x1 ≥ 0, x3 ≥ 0


76/93


Dr KOUAKOU ()

RECHERCHE OPERATIONNELLE
 11 juin 2024 76 / 93
 Programmation linéaire Dualité

x1 x2 x3 x4 e1 e2 e3 2nd membre rapport

e1 1 0 1 2 1 0 0 2 1
e2 0 1 2 1 0 1 0 5 5
e3 0 0 1 2 0 0 1 3
F 10 15 60 95 0 0 0 0
1 1 1
x4 2 0 2 1 2 0 0 1 ∞
e2 − 12 1 3
2 0 − 21 1 0 4 4
e3 -1 0 0 0 -1 0 1 1 ∞
F − 75
2 15 25
2 0 − 95
2 0 0 -95
1 1 1
x4 2 0 2 1 2 0 0 1
x2 − 12 1 3
2 0 − 21 1 0 4
e3 -1 0 0 0 -1 0 1 1
F -30 0 -10 0 -40 -15 0 -155

77/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 77 / 93
 Programmation linéaire Dualité

On obtient




y1 = 40




y2 = 15




y3 = 0

u = 30
1
u2 = 0






u3 = 10




u4 = 0

Z = 155

78/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 78 / 93
 Programmation linéaire Dualité

Vérification

79/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 79 / 93
 Programmation linéaire Dualité

Vérification




y1 − u1 = 10

y − u = 15
2 2


y1 + 2y 2 + y3 − u3 = 60

2y + y + 2y − u = 95
1 2 3 4

79/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 79 / 93
 Programmation linéaire Grand M

Formes non usuelles d’un programme linéaire

contrainte n’est pas de type ≤

On distingue deux cas : la contrainte est de type "≥" ou de type "=".

- Contrainte de type "≥" : il suffit d’ajouter une variable d’écart

non-négative.

- Contrainte de type "≥ " dans un problème de maximisation.

Ici la présence du signe "-" ne permet plus de prendre les variables
d’écart comme des variables de la base. Pour résoudre un tel problème
on introduit de nouvelles variables appelées variables artificielles.

80/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 80 / 93
 Programmation linéaire Grand M

Formes non usuelles d’un programme linéaire

Une variable artificielle est une variable fictive introduite spécialement pour
engendrer une solution de base accessible. Elle n’a pas de signification
économique.

81/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 81 / 93
 Programmation linéaire Grand M

Formes non usuelles d’un programme linéaire

Les variables artificielles permettent simplement d’écrire la forme standard

et ne sont pas donné dans le problème. Elles doivent donc être nulles à
l’optimum. Pour cela on les fait sortir de la base en leur affectant un grand
coefficient dans la fonction économique.
S’il s’agit d’un problème de maximisation ce coefficient est affecté du
signe "-" dans la fonction économique
S’il s’agit d’une minimisation, le coefficient affecté est positif

82/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 82 / 93
 Programmation linéaire Grand M

Formes non usuelles d’un programme linéaire

Pour un Max, on construit un objectif z =t cx − ni=1 Mai . M est une

P
constante positive abritaire qui tend à réduire la fonction économique tant
que les variables artificielles sont dans la base. On dit qu’on pénalise la
fonction objectif.

83/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 83 / 93
 Programmation linéaire Grand M

Formes non usuelles d’un programme linéaire

Pour un Max, on construit un objectif z =t cx − ni=1 Mai . M est une

P
constante positive abritaire qui tend à réduire la fonction économique tant
que les variables artificielles sont dans la base. On dit qu’on pénalise la
fonction objectif.
Pour un min, on construit un objectif w =t cx + ni=1 Mai . M est une
P
constante positive abritaire qui tend à augmenter la fonction économique
tant que les variables artificielles sont dans la base.

83/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 83 / 93
 Programmation linéaire Grand M

Application

max z = 40x + 30y


x + y ≤ 5

−2x + 3y ≥ 12

x ≥ 0; y ≥ 0


84/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 84 / 93
 Programmation linéaire Grand M

Application

max z = 40x + 30y


x + y ≤ 5

−2x + 3y ≥ 12

x ≥ 0; y ≥ 0


Forme standard du problème

max z = 40x + 30y + 0e1 + 0e2 − Ma1


x + y + e1 = 5

−2x + 3y − e2 + a1 = 12

x ≥ 0; y ≥ 0; e1 ≥ 0; e2 ≥ 0; a1 ≥ 0


84/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 84 / 93
 Programmation linéaire Grand M

Application
Premier tableau
cj 40 30 0 0 -M
x y e1 e2 a1 2nd rap
5
0 e1 1 1 1 0 0 5 1 =5
12
-M a1 -2 3 0 -1 1 12 3 =4
Zj 2M -3M 0 M -M
cj − Zj 40-2M 30+3M 0 -M 0

85/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 85 / 93
 Programmation linéaire Grand M

Application
Premier tableau
cj 40 30 0 0 -M
x y e1 e2 a1 2nd rap
5
0 e1 1 1 1 0 0 5 1 =5
12
-M a1 -2 3 0 -1 1 12 3 =4
Zj 2M -3M 0 M -M
cj − Zj 40-2M 30+3M 0 -M 0

Deuxième tableau
cj 40 30 0 0 -M
x y e1 e2 a1 2m rap
3
0 e1 5/3 0 1 1/3 -1/3 1 5
30 y -2/3 1 0 -1/3 1/3 4 -6
Zi -20 30 0 -10 10
cj − Zj 60 0 0 10 -M-10
85/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 85 / 93
 Programmation linéaire Grand M

Application
Troisième tableau

cj 40 30 0 0 -M
x y e1 e2 a1 2nd
3
40 x 1 0 3/5 1/5 -1/5 5
22
30 y 0 1 2/5 -1/5 1/5 5
Zj 40 30 36 2 -2 156
cj − Zj 0 0 -36 -2 -M+2

La solution du problème de maximisation se présente comme suit :

x = 3/5, y = 22/5 et Z = 156

Vérification
à faire chez vous
86/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 86 / 93
 Programmation linéaire Grand M

Pour un min, on construit un objectif w =t cx + ni=1 Mai . M est une

P
constante positive abritaire qui tend à augmenter la fonction économique
tant que les variables artificielles sont dans la base.

87/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 87 / 93
 Programmation linéaire Grand M

Comment passer d’un tableau à un autre ?

Toutes les règles et principes de calcul dans la méthode du simplexe restent
valables, sauf la règle du choix de la variable entrante qui devient :
Dans un problème de minimisation, la variable entrante est la variable
hors base qui a le coefficient " le plus négatif " dans la fonction
économique.

88/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 88 / 93
 Programmation linéaire Grand M

Comment passer d’un tableau à un autre ?

Toutes les règles et principes de calcul dans la méthode du simplexe restent
valables, sauf la règle du choix de la variable entrante qui devient :
Dans un problème de minimisation, la variable entrante est la variable
hors base qui a le coefficient " le plus négatif " dans la fonction
économique.
Tableau optimal et solution optimale
Dans un problème de minimisation, on obtient un tableau optimal dès
que tous les coefficients de la fonction économique sont positifs ou
nuls.

88/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 88 / 93
 Programmation linéaire Grand M

Application :cas de la minimisation

Le principe de résolution est le même que celui de la maximisation à

l’exception du critère de choix de la variable entrante :
La variable entrante est celle qui de la fonction économique qui le
coefficient le plus négatif (le plus petit).
Dans un problème de minimisation, on obtient un tableau optimal
dès que tous les coefficients de la fonction économique sont positifs
ou nuls.

89/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 89 / 93
 Programmation linéaire Grand M

Exercice

min z = x + y

7x + 5y ≥ 40

x + 4y ≥ 9

x ≥ 0, y ≥ 0


90/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 90 / 93
 Programmation linéaire Grand M

Exercice

min z = x + y + 0e1 + 0e2 + Ma1 + Ma2




 7x + 5y − e1 + a1 = 40

x + 4y − e + a = 9
2 2


x ≥ 0, y ≥ 0, e1 ≥ 0, e2 ≥ 0

a ≥ 0, a ≥ 0
1 2

91/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 91 / 93
 Programmation linéaire Grand M

cj 1 1 0 0 M M 2nd m rap
x y e1 e2 a1 a2
40
M a1 7 5 -1 0 1 0 40 5
9
M a2 1 4 0 -1 0 1 9 4
Zj 8M 9M -M -M M M
cj − Zj 1- 8M 1-9M M M 0 0
23 5
M a1 4 0 -1 4 1 − 54 − 115
4 5
1
1 y 4 1 0 − 41 0 1
4
9
4
1
Zj 4 + 23M
4 1 -M − 41 + 5M 4 M − 5M
4 + 4
1
3
cj − Zj 4 − 23M
4 0 M 14 − 5M 4 0 1
−4 + 4 9M

4 5 4 5
1 x 1 0 -1 − 23 23 23 − 23 5
1 7 1 7
1 y 0 1 23 − 23 − 23 23 1
3 2 3 2
Zj 1 1 − 23 − 23 23 23
3 2 3 2
cj − Zj 0 0 23 23 M − 23 M − 23

92/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 92 / 93
 Programmation linéaire Grand M

.
Tous les coefficients cj − Zj sont tous positifs donc nous sommes à
l’optimum

On a : x = 5 y = 1 Z = x + y = 6

93/93
Dr KOUAKOU () RECHERCHE OPERATIONNELLE 11 juin 2024 93 / 93