Chapitre 1 :

Programma-
tion
Linéaire

Abdelaziz
CHE-
TOUANI

Sommaire
Chapitre 1 : Programmation Linéaire
Introduction

Programmation
Linéaire
Abdelaziz CHETOUANI
Résolution
des
programmes École Nationale de Commerce et de Gestion - Oujda
linéaires
Département de commerce
Méthode
Graphique Recherche opérationnelle

16 novembre 2020

1/29
 Sommaire

Chapitre 1 :
Programma-
tion
Linéaire

Abdelaziz
CHE-
TOUANI
1 Introduction
Sommaire

Introduction

Programmation
Linéaire 2 Programmation Linéaire
Résolution
des
programmes
linéaires
Méthode
Graphique 3 Résolution des programmes linéaires
Méthode Graphique

2/29
 Introduction

Chapitre 1 :
Programma-
tion
Linéaire

Abdelaziz
CHE-
• La programmation linéaire est une technique mathématique
TOUANI
permettant de résoudre des problèmes de gestion,
Sommaire
particulièrement ceux où le gestionnaire doit déterminer, face à
Introduction
diérentes possibilités, l'utilisation optimale des ressources de
Programmation
l'entreprise pour atteindre un objectif spécique comme la
Linéaire maximisation des bénéces ou la minimisation des coûts.
Résolution
des • Dans la plupart des cas, les problèmes de l'entreprise pouvant
programmes
linéaires
être traités par la programmation linéaire comportent un certain
Méthode
Graphique
nombre de ressources comme par exemple, main-d'oeuvre,
matières premières, capitaux, espace, ... qui sont disponibles en
quantité limitée et qu'on veut répartir d'une façon optimale
entre un certain nombre de processus de fabrication.

3/29
 Introduction

Chapitre 1 :
Programma-
tion
Linéaire
L'approche pour résoudre ce type de problèmes sera divisée en deux
Abdelaziz
étapes principales :
CHE-
TOUANI • La modélisation du problème sous forme d'équations ou
d'inéquations linéaires qui permettra ainsi de bien identier et
Sommaire
structurer les contraintes que doivent respecter les variables du
Introduction
modèle ; de plus, on doit dénir l'apport de chaque variable à
Programmation
Linéaire
l'atteinte de l'objectif poursuivi par l'entreprise, ce qui se
Résolution
traduira par une fonction à optimiser.
des
programmes • La détermination de l'optimum mathématique à l'aide de
linéaires
Méthode certaines techniques propres à la programmation linéaire.
Graphique
On étudiera 2 méthodes pour résoudre les diérents types de
problèmes de programmation linéaire ; la première est basée sur une
résolution graphique, elle est donc limitée à 2 variables. La deuxième
méthode est plus algébrique et elle justiera la troisième qui porte le
nom de méthode (ou algorithme) du simplexe.

4/29
 Programmation Linéaire

Chapitre 1 :
Programma-
tion
Linéaire • La programmation linéaire est un problème d'optimisation
Abdelaziz (Maximisation ou minimisation) : permet de dénir un
CHE-
TOUANI
programme d'allocation optimale de ressources limités en tenant
compte d'un objectif xé.
Sommaire

Introduction
• Ceci est traduit par une formulation mathématique du
Programmation
programme qui permet de trouver la solution optimale.
Linéaire
• Il y a trois composante principales du modèle d'optimisation :
Résolution
des
programmes
• Variables de décision : Elles représente les composantes du
linéaires modèle qui peuvent être modie pour créer de
Méthode
Graphique congurations diérentes.
• Contraintes : Elles représentent les limitations sur les
variables.
• Fonction objective (Fonction économique ) : Elle identie
l'objectif du problème sous forme linéaire en fonction de
variables de décision.

5/29
 Programmation Linéaire

Chapitre 1 :
Programma-
tion
Linéaire

Abdelaziz Exemple introductif

CHE-
TOUANI Un fabricant de bonbons possède en inventaire 90kg de chocolat,
Sommaire
80kg de noix et 50kg de fruits. Il produit deux sortes de bonbons.
La boîte de bonbons de type A est confectionnée à partir de 2kg de
Introduction
chocolat, 1kg de noix et 1kg de fruits et son prot de revient est de
Programmation
Linéaire 12dhs.
Résolution La boîte de bonbons de type B est confectionnée à partir de 1kg de
des
programmes
chocolat, 2kg de noix et 1 kg de fruits et son prot de revient est de
linéaires 10dhs.
Méthode
Graphique Le problème du fabricant est de déterminer le nombre de boîtes des
deux types à produire pour maximiser son prot tout en respectant
les contraintes liées à la quantité des matières premières. (Déterminer
le programme de production optimale)

6/29
 Programmation Linéaire

Chapitre 1 :
Programma-
tion
Linéaire

Abdelaziz
CHE-
TOUANI

Modélisation : Formulation mathématique du problème réel

Sommaire

Introduction
Variables de décision :
Programmation
Linéaire Soient :
Résolution
des x : la quantité des boîtes de type A à fabriquer
programmes
linéaires
Méthode y : la quantité des boîtes de type B à fabriquer
Graphique

7/29
 Programmation Linéaire

Chapitre 1 :
Programma-
tion Modélisation : Formulation mathématique du problème réel
Linéaire

Abdelaziz
Contraintes :
CHE-
TOUANI
• Les contraintes de positivité (contraintes de signe)
Sommaire Les valeurs de x et y ne peuvent être que positives ou nulles :
Introduction x, y ≥ 0 (contraintes dites évidentes ou implicites)
Programmation
Linéaire • Les contraintes de production
Résolution • La quantité totale du chocolat utilisée (dans la fabrication
des
programmes de toutes les boîtes) est 2x + y . Cette quantité ne doit
linéaires
Méthode pas dépasser 90, d'où la première contrainte : 2x + y ≤ 90
Graphique
• La quantité totale de la noix utilisée est x + 2y . Cette
quantité ne doit pas dépasser 80 , d'où la deuxième
contrainte. x + 2y ≤ 80
• La quantité totale des fruits utilisée est x + y . Cette
quantité ne doit pas dépasser 50, d'où la troisième
contrainte. x + y ≤ 50

8/29
 Programmation Linéaire

Chapitre 1 :
Programma-
tion
Linéaire

Abdelaziz
CHE-
TOUANI

Sommaire Modélisation (Formulation mathématique du problème réel)

Introduction
Fonction objectif : fonction économique : L'objectif consiste à trouver
Programmation
Linéaire
les valeurs des variables x et y qui maximisent le prot z qui est le
Résolution
total des bénéces sur la vente des boîtes A et B d'où la fonction
des objectif :
programmes
linéaires Max z = 12x + 10y
Méthode
Graphique

9/29
 Programmation Linéaire

Chapitre 1 :
Programma-
tion
Linéaire

Abdelaziz
CHE-
TOUANI Modélisation (Formulation mathématique du problème réel)
Sommaire
Le Programme linéaire nal est donc le suivant :
Introduction
max z = 12x + 10y
Programmation
Linéaire

Résolution
sous les contraines :
des
2x + y ≤ 90 (A)

programmes 
linéaires
x + 2y ≤ 80 (B)


Méthode
Graphique
 x + y ≤ 50 (B)
x ≥ 0, y ≥ 0 (C )



10/29
 Programmation Linéaire

Chapitre 1 :
Programma-
tion
Linéaire
Formulation du programme linéaire
Abdelaziz
CHE- Généralement, il y a quatre étapes à suivre pour pourvoir modéliser
TOUANI
un programme linéaire :
Sommaire
• Identier les variables du problème à valeur non connues
Introduction
(variables de décision) et les représenter sous forme symbolique
Programmation
Linéaire
(exp : x, y, . . .)
Résolution • Identier les restrictions (contraintes) du problème et les
des
programmes exprimer par un système d'équations ou d'inéquations linéaires.
linéaires
Méthode • Identier l'objectif ( critère de sélection) et le représenter sous
Graphique
forme linéaire en fonction des variables de décision. La fonction
qui représente le critère de sélection est dite fonction objective
où fonction coût.
• Spécier si le critère de sélection est à maximiser ou à minimiser.

11/29
 Programmation Linéaire

Chapitre 1 :
Programma-
tion Conditions de formulation d'un PL
Linéaire
Le PL admet des hypothèses (des conditions) que le décideur doit vérier avant
Abdelaziz
de pouvoir les utiliser pour modéliser son problème :
CHE-
TOUANI
• Les variables de décision du problème sont positives et elles prennent des
valeurs réelles. Si elle est violée on parle de la programmation en nombres
Sommaire
entiers.
Introduction

Programmation
• Le critère de sélection ( fonction objectif ) de la meilleur décision est décrit
Linéaire par une fonction linéaire de ces variables. c.à.d, dans l'expression de la
fonction objective on peut pas obtenir un produit de deux variables.
Résolution
des
programmes
• Les restrictions relatives aux variables de décision (limitation de ressources )
linéaires peuvent être exprimées par un ensemble d'équations linéaires. Ces
Méthode équations forment l'ensemble des contraintes.
Graphique
• La contribution de chaque variable est indépendante de la valeur des autres
variables et est proportionnelle à leur valeur. Si elle est violée on parle de la
programmation non linéaire.

• Les paramètres du problème en dehors des variables de décision ont une

valeur connue avec certitude. Si elle est violée on parle de la
programmation stochastique.

12/29
 Programmation Linéaire

Chapitre 1 : Programme linéaire : dénition

Programma-
tion En général, un programme linéaire est déni par :
Linéaire
• Des variables réelles se sont les variables de décision : x1 , x2 , ..., xn
Abdelaziz
CHE-
TOUANI
• Contraintes linéaires (égalités ou inégalités) :

Sommaire a11 x1 + a12 x2 + ... + a1n xn ≤ b1

a21 x 1 + a22 x 2 + ... + a2n xn ≥ b2
Introduction
···
Programmation am1 x1 + am2 x2 + ... + amn xn = bm
Linéaire

Résolution
des
• Une fonction objectif linéaire (fonction de coût ou fonction économique), à
programmes optimiser (min ou max) donnée par :
linéaires
Méthode
Graphique F (x1 , x2 , ..., xn ) = c1 x1 + c2 x2 + ... + cn xn

• P = (x1 , x2 , ..., xn ) est appelée solution admissible d'un PL : si P satisfait

toutes les contraintes.

• On appelle solution optimale d'un PL : toute solution admissible qui

optimise (maximise ou minimise) la fonction objectif.

• Domaine admissible = l'ensemble des solutions admissibles. On le note D.

• Il y a plusieurs manières d'exprimer un programme linéaire :

13/29
 Programmation Linéaire

Chapitre 1 :
Programma-
tion
Linéaire

Abdelaziz Forme canonique

CHE-
TOUANI Un programme linéaire (P.L.) est dit canonique s'il est de la forme

n
Sommaire X
Max F (x1 , x2 , ..., xn ) = cj xj
Introduction
j=1
n
Programmation X
Linéaire s.c aij xj ≤ bi , i = 1, ..., m
j=1
Résolution
des xj ≥ 0, j = 1, ..., n
programmes
linéaires
Donc, un (P.L) est dit canonique lorsqu'on a :
Méthode
Graphique
• Un problème de maximisation

• Toutes les variables de décision sont positives

• Toutes les contraintes sont des inéquations du type  ≤

14/29
 Programmation Linéaire

Chapitre 1 :
Programma-
tion
Linéaire

Abdelaziz Forme standard

CHE-
TOUANI Un programme linéaire (P.L.) est dit standard s'il est de la forme

n
Sommaire X
Max F (x1 , x2 , ..., xn ) = cj xj
Introduction
j=1
n
Programmation X
Linéaire s.c aij xj = bi , i = 1, ..., m
j=1
Résolution
des xj ≥ 0, j = 1, ..., n
programmes
linéaires
Donc, un (P.L) est dit standard lorsqu'on a :
Méthode
Graphique
• Un problème de maximisation

• Toutes les variables de décision sont positives

• Toutes les contraintes sont des inéquations du type  =

15/29
 Programmation Linéaire

Chapitre 1 : Règles de transformation

Programma-
tion
Linéaire
• Tout P.L. peut se mettre au choix sous forme canonique ou standard.

Abdelaziz • Quelques règles de transformation :

CHE-
TOUANI
• Inéquation ⇒ équation : ajouter une variable d' écart
Sommaire
ax ≤ b ⇔ ax + e = b, e ≥ 0
Introduction

Programmation
Linéaire
ax ≥ b ⇔ ax − e = b, e ≥ 0
Résolution • Equation ⇒ inéquation
des
programmes
linéaires
Méthode
ax = b ⇔ ax ≤ b et ax ≥ b ⇔ ax ≤ b et − ax ≤ −b
Graphique
• Variable libre :

x ∈ R ⇔ x = x + − x −, avec x + , x − ≥ 0

• Cas variable négative

x ≤ 0 ⇔ x = −x + , avec x + ≥ 0

16/29
 Programmation Linéaire

Chapitre 1 : Exemple de conversion

Programma-
tion Soit le programme linéaire suivant :
Linéaire

Abdelaziz 
 Minimiser F (x, y ) = −2x + 3y
CHE- s.c x +y =7

TOUANI

 x − 2y ≤ 4
x ≥0

Sommaire

Introduction

Programmation • Minimiser une fonction ⇔ maximiser la fonction opposée (fois -1)

Linéaire

Résolution • Minimisation > maximisation : min f (x) = −max(−f (x))

des
programmes
• Pour minimiser F = cx , il sut de maximiser
linéaires
W = −cx = (−c)x
Méthode
Graphique • multiplier la valeur optimale de W par -1 pour obtenir celle
de F .
• Les contraintes de positivités :

y = y 0 − y 00 avec y 0, y ” ≥ 0

• Transformation des égalités en deux contraintes :

x + y0 − y” ≤ 7 x + y0 − y” ≤ 7
 
x +y =7⇔ ⇔
17/29 x + y0 − y” ≥ 7 −x − y 0 + y ” ≤ −7
 Programmation Linéaire

Chapitre 1 :
Programma-
tion
Linéaire

Abdelaziz
Exemple de conversion
CHE-
TOUANI Le programme linéaire devient le programme suivant :

Sommaire
F (x, y ) = 2x − 3y 0 + 3y 00

 Max
x +0 y − y 00 = 7

s.c

Introduction

Programmation
 x − 2y 0 + 2y 00 ≤ 4
x, y 0 , y 00 ≥ 0


Linéaire

Résolution
des Dont la version canonique est
programmes
linéaires
Max F (x, y ) = 2x − 3y 0 + 3y 00

Méthode
Graphique x +0 y − y 00 ≤ 7

s.c



−x −0 y + y 00 ≤ −7
x − 2y 0 + 2y 00 ≤ 4



x, y 0 , y 00 ≥ 0


18/29
 Programmation Linéaire

Chapitre 1 :
Programma-
tion
Récupitulatif
Linéaire
• Chaque programme linéaire en forme standard s'écrit en forme canonique et
Abdelaziz
inversement
CHE-
TOUANI
• Pour convertir un PL de sa forme canonique en forme standard on introduit

Sommaire
des variables positives appelé variables d'écart. Si dans un PL on a m
contraintes de type :
Introduction

n
Programmation X
Linéaire aij xj ≤ bi , i = 1, .., m
Résolution
j=1
des
programmes On introduit dans la ième contrainte la variable d'écart ei
linéaires
Méthode
Graphique ⇓

Donc la ième contrainte sera sous la forme d'une égalité :

n
X
aij xj + ei = bi , avec ei ≥ 0
j=1

19/29
 Programmation Linéaire

Chapitre 1 :
Programma-
tion
Linéaire

Abdelaziz
CHE-
TOUANI

Sommaire Dans l'exemple précédent, le nombre de contraintes dans la forme canonique est

Introduction
m = 3. Sa forme standard est donnée par :

Programmation
Max F (x, y ) = 2x − 3y 0 + 3y 00

Linéaire
x +0 y − y 00 + e1 = 7

s.c



Résolution
des
−x −0 y + y 00 + e2 = −7
x − 2y 0 + 2y 00 + e3 = 4

programmes


x, y 0 , y 00 , e1 , e2 , e3 ≥ 0

linéaires
Méthode
Graphique

20/29
 Résolution des programmes linéaires Méthode Graphique

Chapitre 1 :
Programma-
tion
Linéaire Méthode Graphique

Abdelaziz Elle ne peut être utilisée que lorsque les inconnues du problème se limitent à deux
CHE-
variables.
TOUANI

• Détermination du domaine des solutions admissibles : Le domaine des

Sommaire
solutions admissibles est déterminé par l'ensemble des contraintes où
Introduction chaque contrainte partage le plan en deux demi plan ( deux parties). La

Programmation
position du point (0, 0) permet de le dénir.
Linéaire
• A Chacune des inéquations on peut associer une droite dont l' équation
Résolution
correspond à l'égalité entre les deux membres.
des
programmes
linéaires
• Prenons l'exemple de programme de production suivant :
Méthode
Graphique 
Maximiser F (x, y ) = 12x + 10y

2x + y ≤ 90



x + 2y ≤ 80
x + y ≤ 50




x, y ≥ 0

21/29
 Résolution des programmes linéaires Méthode Graphique

Chapitre 1 :
Programma-
tion
Etape 1
Linéaire

Abdelaziz
Représenter dans un espace orthogonal (ox, oy ), à 2 dimensions, le domaine des
CHE- contraintes D où
TOUANI

D = {(x, y ) ∈ R2 /x et y vérient les contraintes}

Sommaire

Introduction 2x + y ≤ 90 (A)


 x + 2y ≤ 80 (B)


Programmation
Linéaire x + y ≤ 50 (C )
x ≥ 0 (D)


Résolution 

des y ≥ 0 (E )
programmes
linéaires Le domaine des solutions admissibles est déterminé par les droites d'équations
Méthode
Graphique suivantes : 

 2x
+ y = 90
x + 2y = 80


 x + y = 50
x, y ≥ 0


Ce domaine de contraintes détermine alors le domaine de dénition et d'existence

des solutions possibles (admissibles)

22/29
 Résolution des programmes linéaires Méthode Graphique

Chapitre 1 :
Programma-
tion
Linéaire

Abdelaziz
CHE- Remarques
TOUANI

• Le domaine des solutions admissibles est déterminé par l'ensemble des

Sommaire contraintes où chaque contrainte partage le plan en deux demi-plans.
Introduction
• L'étude du point (0, 0) permet de le dénir.
Programmation
Linéaire • A chacune des contraintes, on peut associer une droite dont l'équation

Résolution
correspond à l'égalité entre les deux membres.
des
programmes • L'ensemble des solutions admissibles est un polygone convexe, avec
linéaires
Méthode
Graphique • Polygone : ensemble délimité par des segments de droites.
• Un ensemble est dit convexe ssi pour tous points A et B
appartenant à D , le segment [A, B] est inclus dans D .

23/29
 Résolution des programmes linéaires Méthode Graphique

Chapitre 1 :
Programma- Etape 1
tion
Linéaire

Abdelaziz
CHE-
TOUANI

Sommaire

Introduction

Programmation
Linéaire

Résolution
des
programmes
linéaires
Méthode
Graphique

24/29
 Résolution des programmes linéaires Méthode Graphique

Chapitre 1 :
Programma-
tion
Linéaire
Etape 2
Abdelaziz
CHE- • On représente graphiquement la fonction économique Z = 12x + 10y
TOUANI

• Pour cela on lui aecte provisoirement une valeur xée strictement positive.
Sommaire

Introduction
• Pour Z = 120, on a une droite D1 : 12x + 10y = 120,
Programmation
qui représente les solutions pour lesquelles le prot vaut
Linéaire 120.
Résolution • Si Z = 240, on a une autre droite
des
programmes D2 : 12x + 10y = 240, qui représente les solutions pour
linéaires
Méthode lesquelles le prot vaut 240 et qui est parallèle à D1 .
Graphique
• on s'aperçoit facilement qu'en déplaçant la droite vers le haut on augmente
le prot Z.
• Pour résoudre graphiquement le problème, on va faire "glisser" la droite du
prot vers le haut jusqu'à ce qu'elle ait un minimum de points communs
avec le domaine des solution admissibles.

25/29
 Résolution des programmes linéaires Méthode Graphique

Chapitre 1 :
Programma- Etape 2
tion
Linéaire

Abdelaziz
CHE-
TOUANI

Sommaire

Introduction

Programmation
Linéaire

Résolution
des
programmes
linéaires
Méthode
Graphique

26/29
 Résolution des programmes linéaires Méthode Graphique

Chapitre 1 :
Programma-
tion
Linéaire

Abdelaziz Etape 3
CHE-
TOUANI • On calcule de façon rigoureuse les composantes de la solution optimale.

Sommaire • On a le point c correspond a l'intersection des deux droites (A) et (C).

Introduction • Ces coordonnées représentent donc la solution du système :

Programmation 
Linéaire 2x+ y = 90
Résolution x + y = 50
des
programmes
linéaires • On a alors : x = 40; y = 10 et max Z = 580
Méthode
Graphique • En conclusion,vla solution du problème est de produire 40 boîtes de type A
et 10 boîtes de type B pour obtenir un prot maximum de 580 dhs

• Si la droite qui représente le prot est parallèle à (A) ou (B) ou (C), il y

aura une innité de solutions. On dit qu'on a une dégénérescence.

27/29
 Résolution des programmes linéaires Méthode Graphique

Chapitre 1 :
Programma-
tion
Linéaire
Remarque
Abdelaziz
CHE- Pour trouver la solution du programme linéaire on peut aussi utiliser la méthode
TOUANI
du recensement des sommets qui consiste à :

Sommaire • Déterminer les coordonnées de tous les sommets du polygone de l'ensemble

Introduction des solutions admissibles ;

Programmation • Calculer Z en chacun de ces sommets ;

Linéaire

Résolution
• Comparer les valeurs obtenues, la plus grande de ces valeurs donne le
des maximum de Z.
programmes
linéaires
Méthode Sommet Coordonnées (x, y ) Valeurs de Z = 12x + 10y
Graphique o (0,0) 0
a (0,40) 400
b (20,30) 540
c (40,10) 580
d (45,0) 540

28/29
 Résolution des programmes linéaires Méthode Graphique

Chapitre 1 :
Programma-
tion
Application
Linéaire

Abdelaziz Une entreprise de fabrication de châssis envisage la production de deux nouveaux

CHE- modèles en fonction des capacités de ses trois ateliers. Il s'agit respectivement
TOUANI
d'un châssis en aluminium et d'un châssis en bois. Le premier produit nécessite le
passage dans le premier atelier pour fabriquer le cadre en aluminium et dans le
Sommaire
troisième atelier où le verre est monté sur le châssis. Tandis que le second produit
Introduction nécessite le passage dans le deuxième atelier pour fabriquer le cadre en bois et

Programmation
dans le troisième atelier où le verre est monté sur le châssis. Les produits unitaires,
Linéaire les temps de fabrication de chacun des produits dans chacun des ateliers ainsi que
les capacités hebdomadaires de ces ateliers sont donnés dans le tableau suivant :
Résolution
des
programmes Produit 1 Produit 2 Capacité disponible
linéaires
(heures/produit) (heures/produit) (heures/semaine)
Méthode
Graphique Atelier 1 1 0 4
Atelier 2 0 2 12
Atelier 3 3 2 18
Prot (Dh) 300 500

Combien faut-il produire de châssis de chaque type par semaine an d'obtenir un
prot maximal ?

29/29