SOMMAIRE :

CHAP 1 : DEFINTION D’UN PROGRAMME LINEAIRE (PL)

1) DEFINTION D’UN PL
2) DIFFERENTES ECRITURE D’UN PL
3) FORMULATION OU MODELISATION D’UN PROBLEME
EN PROGRAMMATION LINEAIRE
EXERCICES

CH2 : RESOLUTION GRAPHIQUE D’UN PL

1) RESULTATS THEORIQUES
2) METHODE DE REFERENSEMENT
3) METHODE DES DROITES PARALLELES
EXERCICES

CH 3 : RESOLUTION NUMERIQUES
1) VOCABULAIRE
2) METHODES SIMPLEXE
3) METHODE DU GRAND M
EXERCICES

CH4 : DUALITE
1) DEFINITIONS
2) THEOREME DES ECARTS COMPLEMENTAIRES
EXERCICES
CH1 : DEFINITIONS D’UN PROGRAMME LINEAIRE

*L’optimisation linéaire est une branche des mathématiques qui consiste à

trouver la meilleure solution tout en respectant les exigences définies. Cette
recherche de solutions se fait en utilisant un programme appelé
programmation linéaire.

*Fonction objectif

On appelle fonction objectif d’un problème d’optimisation linéaire le critère de

choix entre diverses solutions possibles. Elle est toujours accompagnée de
l’objectif (minimiser ou maximiser)

*variables de décision

On appelle variable en optimisation linéaire toute quantité utile à la résolution

du problème dont le modèle doit déterminer la valeur. Cette définition permet
de faire la différence entre variables et paramètres (qui sont des données) du
modèle.

*Contraintes

On appelle contrainte en optimisation linéaire toute relation limitant le choix

des valeurs possibles de variables.

En résumé, un programme linéaire s’écrit sous la forme :

Fonction objectif

Contraintes
*

On appelle programme linéaire ou une programmation linéaire tout problème

d’optimisation ou la fonction objectif et les contraintes sont linéaires

1-2) Différentes écritures d’un PL

Il existe plusieurs manières d’écrire un programme linéaire

a) Forme algébrique

C’est la forme la plus utilisée. On y trouve plusieurs équations ou inéquations à

l’intérieur desquelles chaque variable a un coefficient réel.

Autrement la forme générale d’un problème de programmation linéaire de n

variables à m contraintes est :

Min/Max Z(x) = C x + C x +…+C x

1 1 2 2 n n

a11x1 + A12X2 +…+ A1Xn ≥ ou ≤ ou = B1

A21X1 + A22X2 +…+ A2Xn ≥ ou ≤ ou = B2

Am1X1 + Am2X2 +…+ AmXn ≥ ou ≤ ou = Bn

X1, X2,…, Xn ≥ 0

*Les Cj (avec j=1…n) sont les coefficients de la fonction objectif

*Les Aij (avec i=1…m et j= 1…n) sont les coefficients du premier membre des
contraintes

*Les bi (avec i=1…m) sont les seconds membres des contraintes

Avec Cj, Aij, Bi sont des réels

Forme Matricielle
La propriété de linéaire de la fonction objectif et des contraintes permet de
représenter un programme linéaire sous forme matricielle en posant :

C t = ( c1 , c2,.., cn)

Bt = ( b1 , b2,.., bn)

Xt = ( x1 , x2,.., xn)

A11 A12 … A1N

A11 A12 … A1N

A= .

Am1 Am2 … Amn

Alors le PL ci-dessus s’écrit matriciellement :

Min/Max Z(x) = Ct X

A x ≥ ou ≤ ou = b

X ≥ 0 (Tous les X1, X2,.., Xn ≥ 0)

Forme Standard

Ecrire un PL sous forme standard c’est l’écrire en transformant tous les signes
des contraintes en égalité sauf la contrainte de signe. Pour se faire on ajoute de
nouvelles variables appelés variables d’écart qui est supérieur ou égale à 0.
Forme canonique d’un PL

Un PL est sous forme canonique lorsqu’aucune de ses contraintes n’a le signe

égal

Ex : Considérons le PL suivant :

Min Z = 3 x1 + x2

2 x1 – x2 ≤ 4

-X1 + 3X2 ≥ 2

FORME MATRICIELLE DE PL

Modélisation d’un problème en PL en programmation linéaire

La modélisation d’un problème en optimisation linéaire comporte toujours 4

étapes.

1ère étape : choix des variables de décisions. Cette étape est importante car la
connaissance des variables de décisions permettent de répondre aux
préoccupations posées

2ème étape : formulation des contraintes.

Elle permet de tenir compte des exigences ou des limites de l’entreprise. Plus
les contraintes sont bien définies mieux on a les meilleurs résultats possibles

3ème étape : Choix de la fonction objectif.

En utilisant les variables de décisions la fonction objectif permet de
sélectionner la meilleure solution.

4ème étape : Résumé

Il s’agit de faire le résumé de la fonction objectif et des contraintes obtenues en

respectant la forme générale d’un programme linéaire.
CH2 : METHODE DE RESOLUTION GRAPHIQUE

2-1) Résultats théoriques

Propriété 1

L’ensemble des solutions réalisables d’un PL est un polyèdre convers. C'est-à-

dire si deux éléments sont de ce domaine alors le segment qui les relie est du
domaine.

X Y

P1 est convexe P2 n’est pas convexe

car a € [x,y]

Propriété 2

L’ensemble des solutions réalisables d’un PL est un convexe fermé ssi :

Il est vide ou non vide et non borné. On désigne par P le domaine des solutions
réalisables

II-2) Le principe de la méthode

La résolution d’un PL par la méthode graphique se déroule ainsi :

1) Réaliser un repère orthonormé

2) Déterminer le domaine réalisable ou admissible (P)
3) Si (P) est borné alors la solution existe. Mais si (P) est non borné on
distingue 2 cas :
-Si le problème est a maximisé alors pas de solution ;
-Si le problème est à minimiser alors il existe une solution optimale
4) Chercher tous les points sommets de (P) et choisir parmi ceux-ci la le
point qui rend l’objectif optimal. Il y a 2 méthodes :
-Méthode de recensement des sommets
-Méthodes des droites parallèles

II-3) Méthode de recensement des sommets

Elle consiste à comparer les valeurs de l’objectif à chacun des points

sommets. La plus grande valeur est le maximum et la plus petite valeur
réalise le minimum

II-4) Méthode des droites parallèles

Elle consiste à tracer la droite relative de la fonction objectif noté
(delta)A déplacer parallèlement delta vers le point du domaine réalisable
le plus éloigné de l’origine
CH 3 : RESOLUTION NUMERIQUES D’UN PL

3-1) Vocabulaires

Considérons le PL sous forme standard :

Min Z =cx
Ax =b
x e Rn, x ≥ 0

Avec A : la matrice associée aux contraintes

-Base solutions de bases

On appelle base de PL toutes sous matrices B carré
inversible et extraite de A.

-On appelle solution de base de PL associée à la base B

la solution noté x(B) du système Ax = b obtenus en
fixant les variables hors base à 0.
 B -1
X(B) = 0

Par ailleurs si B est une base de PL, les variables

associées aux colonnes de B sont appelées les variables
de bases et les autres variables sont appelés variables
hors base.

Exemple : Considérons le PL suivant

Min Z = 3 x1 + 2x2 + x3
x1 – x2 + 2x3 + x4 = 4
P(L) 2x1 + x2 – 3x3

On peut avoir une infinité de sous matrice carré

extraite inversible de A. Mais pour le choix de la base il
est conseillé de choisir les variables d’écart car leur
matrice est une matrice triangulaire

Par exemple la matrice B

1 0 0
B= 0 1 0 est une base du PL
0 0 1

Et comme les variables associées aux colonnes de cette

base sont x 4 , x 5 et x 6 on les appelle les variables de
bases

-On dit que B est une base réalisable si et seulement

B-1 b ≥ 0

Si B est une base réalisable alors x(B) est une solution

réalisable avec x(B)
 B -1
X(B) = 0

-Une base réalisable B est dite dégénérée si la solution

de base de x(B) contient au moins un 0. Mais en PL la
base est considérée dégénérée ssi le vecteur B-1 b
contient au moins une composante nulle.

Remarque : Soit PL sous forme standard et A la matrice

associée aux contraintes. On note N la sous matrice de
A constitué des colonnes variables hors base. Si B est
une base de PL alors

A= (B,N)
Et
Xb
x = xn
Où xb est constitué des variables de bases et xn est
constitué des variables hors bases.

Dans l’exemple si dessus on a

x4 x1
XB = x5 et XN = x2
x6 x3

3-2) Méthode des tableaux simplexes

La résolution d’un PL à l’aide des tableaux simplexes
repose sur le principe suivant :

Etape 1 : Mettre le PL sous forme standard

Etape 2 : Déterminer une base réalisable et évidente du
PL.
S’il y a des variables d’écarts il est conseillé de les
choisir comme la base.
Etape 3 : Mettre le PL sous forme canonique par
rapport à la base.
Etape 4 : Déterminer le 1er tableau du simplexe. Si nous
sommes à l’optimum alors conclure à partir de ce
premier sinon on construit le 2e tableau simplexe ainsi
de suite jusqu’à atteindre l’optimum

a) Choix de la base

Pour le choix de la base une infinité de choix s’offre à

nous mais de préférence les variables d’écart.
Par convention la base B est l’ensemble des variables
de base.

Exemple : B = x4, x5, x6, est une base du PL ci-dessus

b)
Il existe 2 méthodes

-Soit :
A = (B , N) une matrice du PL
xB
X= x N l’ensemble des variables
Posons :

B^ = B-1 b
c^ = C – CB B-1 A
Z^ = CB B-1 A

Avec CB : les coefficients des variables de base dans la

fonction objectif.
Alors la base canonique par rapport à la base B est

Min Z = C^ x + Z^
A^ x = b^
x ≥0

-Ecrire un PL sous forme canonique par rapport à une

base réalisable c’est écrire sa fonction objectif ainsi que
ses variables de base en fonction des seules variables
hors base en d’autres termes il s’agit d’écrire la
fonction objectif à l’aide des seules variables hors base
et transformer le système des vraies contraintes en 1
seul équivalent dans lequel chaque variable
n’intervient que dans une seule équation et dans cette
équation son coefficient est plus un (+1).

Le PL est sous forme canonique est déjà sous forme

canonique par rapport à la base B

c) Premier tableau Simplexe

Après avoir écris le PL sous forme canonique par
rapport à la b, le premier de la forme simplexe est :

xj

xi A^ = B-1 b b^
CJ^ -Z^

Avec I les indices des variables de base

J : Les indices des variables hors base

Exemple :
 TS1 x1 x2 x3

x4 1 -1 2 4
x5 2 1 -3 1
x6 1 0 2 2
3 2 1 0

Remarque : le 0 est obtenus lorsqu’on remplace les

variables de Z par 0 et on met l’opposé

d) Tableau optimal
Les caractéristiques des solutions de base réalisable
optimale sont les suivantes :

-Pour un problème de minimisation, une condition

suffisante pour que B soit une base réalisable optimale
est que tous les coefficients Cj^ soient ≥ 0

-Pour un problème de maximisation, une condition

suffisante pour que B soit une base réalisable optimale
est que tous les coefficients Cj^ soient ≤ 0
Remarque : il peut arriver que nous soyons forcer de
nous arrêter. Dans ce cas il n’y a pas de solutions
optimales

e) Passage d’un tableau à un autre

Lorsqu’on n’est pas à l’optimum et qu’on doit passer au
tableau suivant, le principe est le suivant :

Etape 1 : Déterminer la colonne du pivot

Etape 2 : Déterminer la ligne du pivot
A l’intersection de la ligne et de la colonne se
trouve le pivot lui-même
Une fois le pivot connu on commence à remplir le
tableau suivant :

Etape 3 : On permute les variables

Etape 4 : A la place du pivot on met son inverse
Etape 5 :
-On divise les autres membres de la colonne du pivot
par le pivot et on change leur signe
- On divise les autres membres de la ligne du pivot par
le pivot sans changer leur signe

Etape 6 : Pour compléter le tableau on utilise la règle

du rectangle

Enfin on continue ce processus jusqu’à l’obtention de

l’optimum

f) Algorithme primal de Simplexe

L’algorithme se déroule en 2 phases :

*Cas d’un problème de minimisation

Phase 1 : Après avoir mis le PL sous la forme standard,

on détermine une base réalisable évidente. Si cela
échoue alors le problème est non borné.
Phase 2 : On suppose qu’on dispose d’une base
réalisable évidente B

-Mettre le PL sous forme canonique par rapport à B

-Si tous les coefficients Cj^ ≥ 0, «STOP» alors on est à
l’optimum

-S’il existe k dans j tel Ck < 0, avec Ak^ ≤ 0 alors, «STOP»

le problème est non borné

-Autrement effectué un changement de base dans le

tableau suivant :

-Changement de base :
°calculer Ck^ = min {Cj^/Cj^ >=0}
¿
e
b ¿
° ¿
Aek =min {
bi
¿

¿ ¿¿
/ aik^ > 0}
Aik ¿

La ligne de Bl^ est la ligne du pivot

Ces 2 formules permettent de connaître le pivot.
-Connaissant le pivot on passe au tableau suivant

Remarque : Dans le cas d’un problème de

maximisation, il n’est pas nécessaire de transformer le
problème en un cas de minimisation. Il est suffit de
considérer les modifications suivantes dans
l’algorithme

4)Règle du rectangle

Remarque : Il arrive souvent que nous ayons plusieurs

choix de variables possibles à notre disposition. Si tel
est le cas on applique la règle du « bland » qui dit :
S’il y a un choix de variables à faire parmi plusieurs on
prend celle qui a le plus petit indice.

Ex :
III) Méthode du grand M

On fait appelle à cette méthode lorsque nous n’avons

pas de base réalisable évidente avec la méthode des
tableaux simplexes.

Ex :

Max Z = x1 + 2 x2
x1 – x2 ≤ 4
2x1 + 3x2 ≤ 5
x1 , x2

*Forme standard :
 Max Z = x1 + 2 x2
x1 – x2 + x3 = 4
2x1 + 3x2 –x4 = 5
x1, x2, x3, x4 ≥0

Les variables d’écart ne donnent pas de base réalisable

évidente d’où l’utilisation de la méthode de Grand M.
Son objectif est de contourner ce problème de base
réalisable évidente. Le principe est le suivant :

Etape 1 : On s’assure que le programme est sous forme

standard et que tous les B^ sont positifs ou nuls

Etape 2 : On considère chaque contrainte de PL et

qu’on ajoute au premier membre une autre variable (si
nécessaire) appelé variable artificielle qui est non
négative

Etape 3 : On considère le nouveau programme

auxiliaire noté (Pm) et qui est de la forme :
Après une résolution du programme auxiliaire PM :

*Si ZM* = ∞ alors il en est de même pour PM

*Si PM possède une solution optimale, on a les cas
suivants :
a) si dans cette solution il existe encore des variables
artificielles dans la base, alors le PL est impossible
b) Si toutes les variables artificielles sont nulles la partie
formée des variables structurelles est une solution de
base optimal

Remarque 2 : Dans la résolution de PM lorsqu’une

variable artificielle sort de la base il est certain qu’elle
n’y reviendra plus car sa colonne est supprimée dans le
tableau suivant.

Remarque 3 :
-Etant donné que l’introduction de variables artificielles
sert à créer une base réalisable évidente, il n’est pas
nécessaire d’en arriver à chaque équation (contraintes)

-Si une variable n’intervient que dans une seule

équation et si le signe de son coefficient est positif,
alors il n’est pas nécessaire d’ajouter une variable
artificielle à cette équation. Cette variable est
considérée comme variable de bases associé à cette
équation.
Résoudre le PL suivant par la méthode du grand M
CH4 : DUALITE EN PROGRAMMATION LINEAIRE
1)Définition
On sait que dans un problème de minimisation, les
contraintes d’inégalités sont du type « ≥ » et pour
un problème de maximisation, les contraintes
d’inégalités sont du type « ≤ ». Alors pour un
problème de minimisation, les inégalités de la
forme « ≥ » sont appelés les vraies inégalités et
celle de la forme « ≤ » sont appelés les fausses
inégalités. De même pour un problème de
maximisation, les inégalités de la forme « ≤ » sont
appelés les vraies inégalités et celle de la forme
« ≥ » sont appelés les fausses inégalités.

C'est-à-dire :

Min Z = 3 x1 + x2
x1 - 2x2≤ 2
3 x1 + 4x2
x1,x2
Ou

Max Z = x1 - 2x2
Etant donné un PL sous la forme générale ci-
dessous

Alors on appelle programme dual de P, le

programme linéaire D ci-dessous
Pour passer d’un programme linéaire P à son dual
D on suit les règles suivantes

- Par un programme primal P de minimisation

(maximisation) correspond un programme dual de
maximisation (minimisation).

La fonction objectif du programme dual est noté W

*A toutes vraies contraintes du primal P
correspond une variable dual noté Y :
-Si cette contrainte est une vraie inégalité, la
variable dual associée est définie positive (≥).

-Si cette contrainte est une fausse inégalité, la

variable dual associée est définie négative (≤).

-Si cette contrainte est une égalité, la variable

dual associée appartient à R (est libre)

*A toutes variables du primal P correspond une

contrainte duale :

-Si la variable du primal est définie positive

alors la contrainte duale associée est une vraie
inégalité

-Si la variable du primal est définie négative(≤)

alors la contrainte duale associée est une
fausse inégalité

-Si la variable du primal est libre (appartient à

R) alors la contrainte duale associée est une
égalité
 *Les coefficients de la fonction objectif du primal P
deviennent les seconds membres des contraintes
du dual D. Les seconds membres des vraies
contraintes du primal P deviennent les coefficients
de la fonction objectif du dual D

 La matrice des vraies contraintes du dual D est

la transposée de la matrice des vraies
contraintes du primal P

Exemple :

Résolution :
2)Propriétés de la dualité
Considérons le programme linéaire

Considérons les problèmes « primal et dial »

suivants :
Propriété 1

Si Z = -∞, le problème D n’admet pas de solutions

réalisable autrement dit la résolution du problème
D est impossible si le problème P est non borné
Si W = +∞, le problème primal P n’admet pas de
solutions réalisable autrement dit si le dual D est
non borné alors le primal P est impossible

Propriétés 2
Si P (respectivement D) possède une solution
optimale finale alors la il en est de même pour D
(respectivement P) et de plus Z* = W*

Propriétés 3
Soient X* et Y* respectivement des solutions
réalisables de P et de D
On a :
X* est une solution optimale de P
C x* = y*b 
Y* est une solution optimale de D
Etant donné une PL de problème en dualité il
n’existe que 4 :

1)Les 2 problèmes possèdent des solutions

optimales finies

2a) Le problème primal est non borné et le

problème dual est impossible
2b) Le problème dual est non borné et le
problème primal est impossible
3)Les 2 problèmes sont impossibles

3) Théorèmes des écarts complémentaires

Considérons les problèmes « primal » et Dual

suivants :

On a le problème suivant :
Théorèmes des écarts complémentaires

Soient X* et Y* respectivement des solutions

réalisables de P et de D. une condition est
nécessaire et suffisante pour que X* et Y* soient des
solutions optimales est qu’elles vérifient :

Il existe une autre version dite version forte du

théorème des écarts complémentaires.
Théorème fort des états complémentaires

Une solution réalisable x(p) est une solution

optimale si et seulement s’il existe y une solution
réalisable du dual tel que :

y Aj = Cj si xj > 0 pour tout j

yi = 0 si ai x > bi pour tout i

Exemple : soit (PL) :

Min Z = x1 + x2
3 x1 + x2 >= 4
x1 + 4 x2 >= 5
x1,x2 >=0

Le point x* =(1,1)t est-il une solution optimale de

(PL) ?

Pour montrer que x est une solution optimale il

suffit de montrer que :

-x* est une solution réalisable (On remplace les

coordonnées dans les contraintes)
-Déterminer le dual
-Appliquer le théorème des écarts
complémentaires
Exemple 2 : Le point x* = (3,1) est il une solution
optimale de (PL)
CH5 : PROGRAMMATION LINEAIRE
PARAMETRIQUE

1)J P

Paramétrer la fonction objectif c’est ajouter des

paramètres aux coefficients des variables de
décisions dans la fonction objectif. La
programmation linéaire paramétrique est la
résolution d’un programme linéaire dont
certains coefficients dépendent linéairement
d’un paramètre lambda. Il s’agit de déterminer
la solution lambda x en fonction de lambda.

Soit le problème :

Min Z()=∑ ¿¿
j=1

On suppose ce PL dispose d’une base réalisable

B. Soit I (respectivement J) l’ensemble des
indices des variables de base (respectivement les
variables hors base) associé à la base B

Définition :
On appelle intervalle de stabilité relatif à la
solution associée à B, l’intervalle des valeurs du
paramètre lambda pour lesquelles la solution
associée à B est une solution optimale de
PL(lambda)

Considérons la forme canonique de PL(lambda)

par rapport à B.

On montre que :

Proposition : l’intervalle de stabilité associé à B

est :

Avec
CHAP 6 : TRAVAUX STATIQUES

1) Activation du solveur
2) Résoudre un programme linéaire
3) Résoudre un programme linéaire avec
solution linéaire avec solution entière