28/09/2021

Chapitre 1 :
Formulation d’un programme
Linéaire

Plan du chapitre 1
I. Introduction
Exemple introductif
II. Hypothèses de la programmation linéaire
III. Formulation d’un programme linéaire :
1.Variables de Décision
2.Paramètres
3.Fonction objectif
4.Contraintes

IV. Exemples : (production, transport,

composition, stockage, finance, découpage … )
V. Programmation Linéaire en Nombre Entier

1
 28/09/2021

I- Introduction

Un programme linéaire est un problème

d’optimisation de n variables de décision
réelles qui doivent satisfaire un ensemble
de m équations ou/et inéquations linéaires
dites contraintes et où la valeur d’une
fonction linéaire de ces variables appelée
fonction objectif ou fonction économique
doit être rendue maximale ou minimale.

Exemple introductif de production

Une société cherche à décider les quantités à fabriquer de
deux types P1 et P2.
Les prix de vente unitaires sont respectivement de 1
dinar pour P1 et de 3 dinars pour P2.

La différence respective entre les quantités de P2 et le

double des quantités de P1 ne doit pas excéder 1
Chaque unité de P1 nécessite 2 unités de matières
premières et 1 heure ouvrier. Tandis que chaque unité de
P2 nécessite 1 unité de matières premières et 2 heures
ouvrier.

Tous les jours, la société dispose de 12 unités de

matières première et de 3 ouvriers qui travaillent chacun 4
heures par jour.

Modéliser ce problème sous forme d’un programme

linéaire.

2
 28/09/2021

Q1) : La décision porte sur quoi ??

à Réponse : Les variables de décision :
X1 Le nombre de P1 à fabriquer
X2 Le nombre de P2 à fabriquer
Q2) : Quel est le but du décideur ??
à Réponse :La fonction objectif
Max Z = 1 X1 + 3 X2
Q3) : Quelles sont les restrictions imposées ?
à Réponse : Les contraintes :
-2X1 + X2 ≤ 1 (contrainte de production)
2 X1 + X2. ≤ 12 (Quantité de MP )
1 X1 + 2X2 ≤ 12 (Nb heures ouvrier )
X1 , X2 ≥0
27/09/2021

Le coefficient économique c1

Le coefficient économique c2
Max Z = 1 X1 + 3 X2

-2X1 + 1 X2 ≤ 1 La ressource b1
La ressource b2
2X1 + 1 X2 ≤ 12
La ressource b3
1 X1 + 2 X2 ≤ 12
Le coefficient
X1, X2 ≥ 0
technique a11
Le coefficient Le coefficient
Le coefficient technique a22 technique a12
technique a21

Le coefficient
technique a 31 Le coefficient
technique a32
27/09/2021

3
 28/09/2021

II- Hypothèses de la
Programmation Linéaire :

Tout modèle linéaire suppose les

hypothèses suivantes:
ØLa proportionnalité
ØL’additivité
ØLa divisibilité
ØLa certitude

• Proportionnalité: La contribution des variables de

décision à la fonction objectif et aux contraintes est
proportionnelle à leur valeur.
Ex: 3 x1 3/4 x2 1/x1 X Log x1 X
• Additivité:
– La contribution des variables de décision à la fonction
objectif et aux contraintes est indépendante des
valeurs prises par les autres variables,
– Ex: Z=3x1+x2 Z=2x1x2 X
– La fonction objectif et le terme gauche des contraintes
sont composés de la somme des contributions
individuelles de chaque variable de décision.

Si elles sont violées :

Programmation non linéaire
8

4
 28/09/2021

Divisibilité: Les variables peuvent prendre des

valeurs non entières (fractionnaires).

Si elle est violée :

Programmation en nombres entiers

Certitude: Les paramètres du problème (en dehors

des variables de décisions) ont des valeurs
connues avec certitude.

Si elle est violée :

Programmation stochastique

Remarque

En plus de ces hypothèses, un modèle

linéaire ne doit pas contenir des
inégalités strictes

5
 28/09/2021

III- Formulation d’un

Programme Linéaire :

Tout programme linéaire suppose les

définitions suivantes:
ØLes variables de décision
ØLes paramètres
ØLa fonction objectif
ØLes contraintes

Les n variables de décision

Pour les déterminer, on se pose la question : La
décision porte sur quoi ?

C ‘est le preneur de décision qui choisit

ces variables qui expriment des
quantités. On les note :
xj pour j : 1 .. n

6
 28/09/2021

Les paramètres (connus avec certitude)

On appelle paramètres du modèle toutes les données
numériques présentes dans l’énoncé ou qui se calculent à
partir de ces dernières.
• 3 types de paramètres:
– Les coefficients économiques: degré de réalisation de
l’objectif de l’entreprise associé à une valeur unitaire de
chacune des variables (prix de vente, coût variable
unitaire…):
(cj ) pour j : 1 .. n
– Les ressources: les capacités de production limitées, les
normes à respecter, les potentiels de vente….
(bi) pour i : 1 ..m
– Les coefficients techniques: le degré de consommation
d’une ressource par une activité. A la ressource i et à
l’activité j correspondra le coefficient :
(aij ) pour i : 1 .. m et j : 1 ..n

La fonction objectif
Pour la déterminer, on se pose la question : Quel est le but ?

Peut être de type maximisation en cas de calcul de

recette ou de profit, comme elle peut être de type
minimisation en cas de calcul de coût. Il s’agit
d’une équation linéaire. On la note :

Max Z= 2x1 + 5 x2 +…..+3xn

Ou bien Min Z= 2x1 + 5 x2 +…..+3xn

7
 28/09/2021

Les m contraintes

Ø Les contraintes sont de deux types :

ØLes contraintes fonctionnelles : qui expriment les
restrictions imposées par le problème sur les
variables . Il y a :
des contraintes de type ≤
des contraintes de type ≥
des contraintes de type =
ØLes contraintes de signe : appelées aussi des
contraintes de positivité ou de non négativité. Elles
expriment le signe des variables de décision (qui est
toujours positif ou nul)

IV- Exemples
v Exemple 1 : Problème de production
Une société cherche à décider les quantités à fabriquer
de deux types P1 et P2. Les prix de vente unitaires sont
respectivement de 15 dinars pour P1 et de 8 dinars pour
P2. Chaque unité de P1 nécessite 2 unités de matières
premières et 0,75 heures ouvrier. Tandis que chaque
unité de P2 nécessite 1 unité de matières premières et 0,5
heures ouvrier. Toutes les semaines, la société dispose de
400 unités de matières première et de 6 ouvriers qui
travaillent chacun 40 heures par semaine.
Modéliser ce problème sous forme d’un programme
linéaire.

8
 28/09/2021

Les variables de décision :

X1 Le nombre de P1 à fabriquer

X2 Le nombre de P2 à fabriquer

La fonction objectif

Max Z = 15 X1 + 8 X2

Les contraintes :

2X1 + X2 ≤ 400 (Matière première)

0,75 X1 + 0,5 X2 ≤ 240 (heures ouvriers)

X1, X2 ≥ 0

27/09/2021

v Exemple 2:
Problème de production. (suite exemple1)
Dans le soucis de contrôler ses dépenses, la société a décidé d'acheter
uniquement la quantité de matière première nécessaire pour sa
producti on et de réduire le nombre d'ouvriers à 4 seulement. Ces
ouvriers peuvent travailler des heures supplémentaires à raison de 5
dinars l'heure . (leurs salaires de base sont considérés comme coûts
fixes pour la société). Afin de répondre à la demande de la semaine à
venir, la société sait qu'il faut fabriquer au moins 350 unités des deux
produits P1 et P2 ensembles. Chaque semaine, 400 unités de matière
première sont disponibles sur le marché à un prix unitaire de 2,5
dinars.
1) Quelles sont les nouvelles variables de décision ?
2) Quel est le nouveau but de la société ?
3) quelles sont les nouvelles contraintes ?
Formuler alors ce nouveau problème.

9
 28/09/2021

Les variables de décision :

X1 Le nombre de P1 à fabriquer
X2 Le nombre de P2 à fabriquer
X3 Le nombre d’heures supp utilisées par semaine
X4 La quantité de MP achetée

La fonction objectif
Max Z = 15 X1 + 8 X2 - 5 X3 – 2,5 X4
Les contraintes :
X1 + X2 ≥ 350 (demande sur le marché)
0,75 X1 + 0,5 X2 ≤ 160 + X3 (heures ouvriers)
2X1 + X2 = X4 (utilisation de la matière première)
X4 ≤ 400 ( Disponibilité de la matière première)
Xi ≥ 0 pour i : 1 ..4

27/09/2021

v Exemple 3 : problème de production

• Une usine fabrique deux produits P1 et P2. La fabrication de
10 unités de P1 nécessite 40 heures machine., alors que la
fabrication de 10 unités de P2 ne prend que 30 heures. Une
unité de P1 nécessite 2 fois plus de main d’œuvre qu’une
unité de P2. Enfin, une unité de P1 nécessite 3 unités de
matière première, alors qu’une unité de P2 nécessite 4 unités
de matière première. Afin de maximiser sa productivité, la
machine doit fonctionner pendant 15 heures par jour, 6 jours
par semaine. Si les ouvriers s’occupent uniquement de P1,
alors ils pourraient en produire 32 unités par semaine. La
matière première existe en quantité abondante sur le marché.
Enfin, le marché exige au minimum 10 unités par semaine de
P2. Les profits unitaires nets sont de 15 dinars pour P1 et 12
dinars pour P2.

Formuler le problème sous forme d’un programme linéaire.

10
 28/09/2021

VD :

X1 Le nombre de P1 à fabriquer

X2 Le nombre de P2 à fabriquer

FO:
Max Z = 15 X1 + 12 X2
Les contraintes :

4X1 + 3X2 = 90 (Utilisation de la machine)

2 X1 + X2 ≤ 64 (main d’œuvre)
X2 ≥ 10 ( Demande sur le marché)

Xi ≥ 0 pour i : 1 ..2
27/09/2021

vExemple 4 : problème de marketing

Une entreprise veut faire de la campagne publicitaire
dans la télévision, la radio et les journaux pour un
produit lancé récemment sur le marché. Le but de la
campagne est d’attirer le maximum possible de clients.
Les résultats d’une étude de marché sont donnés dans le
tableau suivant :

11
 28/09/2021

Télévision Télévision Radio Journaux

locale par
satellite
Coût d’une 40 75 30 15
annonce en DT
Nombre de 400 000 900 000 500 000 200 000
clients potentiels
par annonce
Nombre des 300 000 400 000 200 000 10 000
clients potentiels
femmes par
annonce

La campagne ne veut pas payer plus que 800 000 DT pour toute la
campagne et demande que ces objectifs soient atteints :
a) Au minimum 2 000 000 de femmes regardent, entendent ou lisent la
publicité.
b) La campagne publicitaire dans la télévision ne doit pas dépasser 500
000 DT
c) Au moins 3 spots publicitaires seront assurés dans la télévision
locale et au moins de 2 spots pour la télévision par satellite.
d) Le nombre des publicités dans la radio ou dans les journaux sont
pour chacun entre 5 et 10.

1) Modéliser alors ce problème sous forme d’un programme linéaire.

2) Reformuler le problème si cette entreprise veut maintenant minimiser
ses coûts.

12
 28/09/2021

1) VD :

Xi Le nombre d’annonces de pub dans le média i ; i:1..4

FO:
Max Z = 400000 X1 + 900000 X2 + 500000 X3 + 200000 X4
Les contraintes :
40 X1 + 75 X2 + 30 X3 + 15 X4 ≤ 800000
300000 X1 + 400000 X2 + 200000 X3 + 10000 X4 ≥ 2000000
40X1 + 75X2 ≤ 500000
X1 ≥ 3 ; X2 ≥ 2 ; X3 ≤ 10
X3 ≥ 5 ; X4 ≤ 10 ; X4 ≥ 5 Xi ≥ 0 pour i : 1 ..4

2) Juste la fo change : Min Z=40 X1 + 75 X2 + 30 X3 + 15 X4

27/09/2021

vExemple 5 : problème de finance

Une entreprise a la possibilité d’investir dans 4

sortes de titres A, B, C et D rapportant chacun un intérêt
respectif de 8,5%, 10%, 11%et 9%.
Pour des considérations financières au moins 25% de la
somme totale doit être investie dans des titres de type A
et B. Au plus 60% de la somme totale doit être investie
dans les titres de type A, B et D. Il est aussi nécessaire
que la somme investie dans le titre C soit plus
importante que celle investie dans le titre B.
Formuler ce problème sous forme d’un PL.

13
 28/09/2021

VD :

Xi La somme investie dans le titre i : A..D

FO:
Max Z = 0,085 X1 + 0,1 X2 + 0,11 X3+ 0,09 X4

Les contraintes :
X1 + X2 ≥ 0,25 (X1 + X2 + X3 + X4 )

X1 + X2 + X4 ≤ 0,6 (X1 + X2 + X3 + X4 )
X3 ≥ X2
Xi ≥ 0 pour i : A ..D

28/09/2021

vExemple 6 : problème d’investissement

Un financier dispose d’un capital de 10000 dinars et cherche

conseil sur les possibilités d’investir son argent. Deux alternatives
lui sont proposées : des actions et des obligations. Les actions sont
disponibles tous les ans et rapportent un intérêt de 15% par an.
Les obligations nécessitent un placement pour 2 années et
rapportent un intérêt de 50%. Le financier désire récupérer son
capital après trois ans.

Formuler ce problème sous la forme d’un programme linéaire

permettant de trouver le plan d’investissement optimal.

14
 28/09/2021

VD :
X i montant investi en action au début de l’année i ; i:=1..3
Y i montant investi en obligation au début de l’année i ; i:=1..2
Ei montant non investi chaque année i ; i:=1..3
FO:
Max Z = 1,15 X 3 + 1,5 Y 2 + E3

Les contraintes :
X 1 + Y 1 + E1 = 10000
X 2 + Y 2 + E2 = 1,15 X 1 + E1
X 3 + E3 = 1,15 X 2 + 1,5 Y1 +E2
X i ; Ei ≥ 0 pour i : 1 ..3
Y i ≥ 0 pour i : 1 ..2

28/09/2021

vExemple 7 : Problème de transport

Une entreprise de production dispose de

trois usines 1, 2 et 3 dans des endroits
différents. Elle cherche à transporter sa
production mensuelle dans les entrepôts
situés dans les villes 1, 2, 3 et 4. Les coûts de
transports dépendent du trajet suivi et sont
consignés dans le tableau suivant :

15
 28/09/2021

Entrepôt

Usine 1 2 3 4

1 4 6 9 13

2 16 12 15 14

3 6 5 8 7

Sachant que les usines produisent respectivement 10, 8

et 9 tonnes par mois et que la capacité de stockage de
chaque entrepôt est de 6 tonnes, formuler ce problème
sous forme d’un Programme Linéaire.

VD : X ij : Quantités transportées de Ui (i:1..3) vers l’entrepôt Ej (j:1..4)

FO: Min Z = 4 X 11 + 6 X 12 + 9 X 13 + 13 X 14
+ 16 X 21 + 12X 22 + 15 X 23 + 14 X 24
+ 6 X 31 + 5X 32 + 8 X 33 + 7 X 34

Les contraintes :
X 11 + X 12 + X 13 + X 14 ≤ 10 (contraintes de
X 21 + X 22 + X 23 + X 24 ≤ 8 production)
X 31 + X 32 + X 33 + X 34 ≤ 9
X 11 + X 21 + X 31 ≤ 6 (contraintes de
X 12 + X 22 + X 32 ≤ 6 stockage)
X 13 + X 23 + X 33 ≤ 6
X 14 + X 24 + X 34 ≤ 6

27/09/2021
X ij ≥ 0 pour i : 1 ..3 et j : 1.. 4

16
 28/09/2021

Ecriture abrégée
• La fonction objectif s’écrit :
3 4
MinZ = ∑∑ c ij xij
i=1 j=1

• Les contraintes : 4
Pour i : 1!3 ∑x ij ≤ pi
j=1
3
Pour j : 1! 4 ∑x ij ≤ Sj
i=1

v Exemple 8 :
Problème de transport
Un avion cargo possède trois compartiments pour le chargement de frêt :
un à l’avant, un au centre et un dernier à l’arrière. Les limites de capacité
en poids et en volume sont résumées dans le tableau suivant :

Compartiment Capacités
Poids (en tonne) Volume (en m3)
Avant 12 1000
Centre 18 1300
Arrière 10 700

Pour des raisons de stabilité de l’avion en vol, le chargement doit être

équilibré dans chaque compartiment, c’est-à-dire que, pour les trois
compartiments, le chargement doit représenter la même proportion, en
poids, de la limite de charge

17
 28/09/2021

L’avion a la possibilité de charger les quatre frêts suivant :

Frêt Poids Encombrement Bénéfice

(m3 / Tonne) (euro/ Tonne)
1 20 70 220
2 16 100 280
3 25 85 250
4 13 60 200

On peut prendre n’importe quelle portion de ces frêts. En d’autres

termes, on peut choisir de ne pas transporter l’intégralité d’un frêt.

Ecrire un programme linéaire qui consiste à trouver un chargement de

cet avion qui maximise le bénéfice

VD : xij : quantité en tonnes de fret i (1..4) transportée dans

le compartiment j (avant, centre, arrière)
FO : Max Z= 220 (x11 +x12 +x13 ) + 280 (x21 +x22 +x23 )
+ 250 (x31 +x32 +x33 ) +200 (x41 +x42 +x43 )

Contraintes :
x11 +x12 +x13 ≤ 20
x21 +x22 +x23 ≤ 16
x31 +x32 +x33 ≤ 25
x41 +x42 +x43 ≤ 13
x11 +x21 +x31 +x41 ≤ 12
x12 +x22 +x32 +x42 ≤ 18
x13 +x23 +x33 +x43 ≤ 10
70 x11 + 100x21 + 85x31 + 60x41 ≤ 1000
70x12 +100 x22 + 85x32 + 60 x42 ≤ 1300
70x13 + 100x23 + 85x33 + 60x43 ≤ 700
4 4 4

∑X i1 ∑X i2 ∑X i3
i=1 i=1 i=1
= =
12 18 10

xij ≥ 0 i :1..4 ; j : 1 .. 3

18
 28/09/2021

V- Programmation
linéaire en nombres entiers
• Un programme linéaire en nombres
entiers PLNE est un programme dont
les variables sont contraintes à ne
prendre que des valeurs entières. (il
s’agit donc d’un cas particulier de la
programmation linéaire)

• Souvent, elles sont contraintes à

prendre les valeurs 0 ou 1. On parle
alors d’un programme linéaire binaire
ou programme linéaire en 0-1
37

vExemple 1: problème d’affectation

Un directeur a 4 subordonnés et 3 projets à étudier.
Chaque projet doit être affecté à un seul subordonné.
Les estimations du directeur pour le temps nécessaire (par
jours) pour l’étude de chaque projet sont résumées dans le
tableau suivant :
Sub projet 1 2 3

1 10 15 9
2 9 18 5
3 6 14 3
4 12 16 8

Formuler le problème

19
 28/09/2021

VD : Xij : Subordonné i (i:1..3) affecté au projet j (j:1..4)

Xij= 1 si oui

0 sinon

FO: Min Z = 10 X11 + 15 X12 + 9 X13

+9 X21 + 18X22 + 5 X23

+ 6 X31 + 14X32 + 8 X33

+ 12 X41 + 16X42 + 8 X43

Les contraintes :

X11 + X12 + X13 <= 1 (chaque subordonné i est affecté à au plus un projet i
X21 + X22 + X23 <= 1

X31 + X32 + X33 <= 1

X41 + X42 + X43 <= 1

X11 + X21 + X31 +X41 =1 (Projet j affecté à un seul subordonné i)

X12 + X22 + X32 + X42 =1

X13 + X23 + X33 + X43 =1

Xij = 0 ou 1 ; pour i : 1 ..3 et j : 1.. 4

27/09/2021

v Exemple 2: problème du sac à dos

Un voleur dévalisant un magasin trouve n objets, le

ième objet valant vi euros et pesant wi kilogramme, vi et
wi étant des entiers. Il veut évidemment emporter un
butin de plus grande valeur possible mais il ne peut
porter que W kilogrammes dans son sac - à - dos.
On suppose dans cet exercice, qu'il n'est pas possible
de découper les objets.
Formuler ce problème sous forme d’un programme
linéaire.

40

20
 28/09/2021

VD :
X i = 1 si l’objet est mis dans le sac à dos ; pour i : 1 .. n
= 0 sinon

FO :
max ∑ v i X i

Les contraintes :
∑ w i X i <= W
X i ≥ 0 pour i :1 .. n

La somme des poids des objets pris doit être inferieure ou égal au poids
maximal admissible

En général, on ajoute les contraintes suivantes afin d'éviter les cas

singuliers :
• ∑ wi > W : on ne peut pas mettre tous les objets ;
• wi<= W : aucun objet n'est plus lourd que ce que le sac peut porter ;
• v i > 0 : tout objet a une valeur et apporte un gain ;
• wi > 0 : tout objet a un certain poids et consomme des ressources.

Exemple 3: problème du sac à dos

• On dispose d’un sac supportant 3 kg et des objets suivants :

Objet Poids Valeurs

Bague 120 g 3400 dt
Tournevis 270 g 7 dt
Ordinateur 2500 g 1234 dt
Baguette 250 g 0,2 dt

Formuler ce problème sous forme d’un programme linéaire :

VD : Xi =1 si objet i mis dans le sac
0 sinon
FO : Max Z = 3400 X1 + 7 X2 + 1234 X3 + 0,2 X4
Contraintes : 120 X1 + 270 X2 + 2500 X3 + 250 X4 <= 3000
Xi = 0,1 pour i : 1 ..4

21
 28/09/2021

v Exemple 4: sélection de projet

• 5 projets doivent être évalués sur 3 ans. Etant
donné le coût de chaque projet pour chaque
année et le profit obtenu par l’exécution d’un
projet, décider quels projets exécuter sans
dépasser le budget disponible pour chaque
année.

43

VD : X i = 1 si projet sélectionné i
0 sinon

FO : Max Z = 20 X 1 + 40 X 2 + 20 X 3 + 15 X 4 + 30 X 5

Contraintes :
5 X 1 + 4 X 2 + 3 X 3 + 7 X 4 + 8 X 5 ≤ 25
X 1 + 7 X 2 + 9 X 3 + 4 X 4 + 6 X 5 ≤ 25
8 X 1 + 10 X 2 + 2 X 3 + X 4 + 10 X 5 ≤ 25
X i =0;1

22