Recherche Operationelle

La programmation linéaire : une introduction
• Qu’est-ce qu’un programme linéaire ?
• Exemples :
I allocation de ressources
I problème de recouvrement
• Hypothèses de la programmation linéaire
• Pourquoi étudier la programmation linéaire ?
• Interprétation géométrique : représentation et résolution graphique
J.-F. Hêche, ROSO-DMA-EPFL 1

Qu’est-ce qu’un programme linéaire ?
Un programme linéaire (PL) est un problème d’optimisation consistant

à maximiser (ou minimiser) une fonction objectif linéaire de n variables
de décision soumises à un ensemble de contraintes exprimées sous forme
d’équations ou d’inéquations linéaires.

Qu’est-ce qu’un programme linéaire ?
Un programme linéaire (PL) est un problème d’optimisation consistant

à maximiser (ou minimiser) une fonction objectif linéaire de n variables
de décision soumises à un ensemble de contraintes exprimées sous forme
d’équations ou d’inéquations linéaires.
À l’origine, le terme programme a le sens de planification opérationnelle

mais il est aujourd’hui employé comme synomyme de problème
(d’optimisation).
La terminologie est due à G. B. Dantzig, inventeur de l’algorithme du

simplexe (1947).

Forme générale d’un programme linéaire
Pn
Max (Min) z = j=1 cj xj
Pn
s.c. j=1 aij xj ≤ bi i ∈ I ⊆ {1, . . . , m}
Pn
j=1 akj xj ≥ bk k ∈ K ⊆ {1, . . . , m}
Pn
j=1 arj xj = br r ∈ R ⊆ {1, . . . , m}
lj ≤ xj ≤ uj j = 1, . . . , n
Les ensembles I, K, et R sont disjoints, I ∪ K ∪ R = {1, . . . , m} et

lj = −∞ et uj = +∞ sont des valeurs possibles.

Pn
Max (Min) z = j=1 cj xj
Pn
s.c. j=1 aij xj ≤ bi i ∈ I ⊆ {1, . . . , m}
Pn
j=1 akj xj ≥ bk k ∈ K ⊆ {1, . . . , m}
Pn
j=1 arj xj = br r ∈ R ⊆ {1, . . . , m}
lj ≤ xj ≤ uj j = 1, . . . , n
Les ensembles I, K, et R sont disjoints, I ∪ K ∪ R = {1, . . . , m} et

lj = −∞ et uj = +∞ sont des valeurs possibles.

Terminologie
• Les variables x1, . . . , xn sont appelées variables de décision du

problème.
• La fonction linéaire à optimiser est appelée fonction objectif (ou

parfois fonction objet).
• Les contraintes prennent la forme d’équations et d’inéquations

linéaires.
• Les contraintes de bornes se résument souvent à des contraintes de

non-négativité xi ≥ 0. Elles sont généralement traı̂tées de manière
spéciale par les algorithmes de résolution.

Terminologie

problème.


linéaires.


Terminologie

problème.


linéaires.


Terminologie

problème.


linéaires.


Exemple : problème d’allocation de ressources
Vous disposez de
• 8 kg de pommes,
• 2.5 kg de pâte,
• 6 plaques.
pour confectionner des chaussons et des tartes.
Pour faire un chausson, il vous faut 150 g de pommes et 75 g de pâte.
Chaque chausson est vendu 3 frs.
Pour faire une tarte, il vous faut 1 kg de pommes, 200 g de pâte et 1
plaque. Chaque tarte est divisée en 6 parts vendues chacune 2 frs.
Que faut-il cuisiner pour maximiser le chiffre d’affaires de la vente ?

Vous disposez de
• 8 kg de pommes,
• 6 plaques.

Vous disposez de
• 8 kg de pommes,
• 6 plaques.

Définissons 2 variables de décision
x1 : le nombre de chaussons confectionnés,
x2 : le nombre de tartes confectionnées.

Le chiffre d’affaires associé à une production (x1, x2) est
z = 3x1 + (6 × 2)x2 = 3x1 + 12x2.

z = 3x1 + (6 × 2)x2 = 3x1 + 12x2.
Il ne faut pas utiliser plus de ressources que disponibles
150x1 + 1000x2 ≤ 8000 (pommes),

z = 3x1 + (6 × 2)x2 = 3x1 + 12x2.
150x1 + 1000x2 ≤ 8000 (pommes),

75x1 + 200x2 ≤ 2500 (pâte),

z = 3x1 + (6 × 2)x2 = 3x1 + 12x2.
150x1 + 1000x2 ≤ 8000 (pommes),

75x1 + 200x2 ≤ 2500 (pâte),
x2 ≤ 6 (plaques).

z = 3x1 + (6 × 2)x2 = 3x1 + 12x2.
150x1 + 1000x2 ≤ 8000 (pommes),

75x1 + 200x2 ≤ 2500 (pâte),
x2 ≤ 6 (plaques).
On ne peut pas cuisiner des quantitées négatives : x1 ≥ 0, x2 ≥ 0.

Problème d’allocation de ressources : modèle
Pour maximiser le chiffre d’affaires de la vente, il faut déterminer les

nombres x1 et x2 de chaussons et de tartes à cuisiner, solution du
problème
Max z = 3x1 + 12x2

s.c. 150x1 + 1000x2 ≤ 8000
75x1 + 200x2 ≤ 2500
x2 ≤ 6
x1 , x2 ≥ 0

Problème d’allocation de ressources : modèle
Pour maximiser le chiffre d’affaires de la vente, il faut déterminer les

nombres x1 et x2 de chaussons et de tartes à cuisiner, solution du
problème
Max z = 3x1 + 12x2

s.c. 150x1 + 1000x2 ≤ 8000
75x1 + 200x2 ≤ 2500
x2 ≤ 6
x1 , x2 ≥ 0
En fait, il faudrait également imposer à x1 et x2 de ne prendre que des

valeurs entières.
Exemple : problème de recouvrement
Données : Les demandes journalières en chauffeurs dans une entreprise

de transport
Lu Ma Me Je Ve Sa Di
13 18 21 16 12 25 9
Les chauffeurs travaillent cinq jours d’affilée (et peuvent donc avoir leurs
deux jours adjacents de congé n’importe quand dans la semaine).
Objectifs : Déterminer les effectifs formant les sept équipes possibles de
chauffeurs de manière à
• couvrir tous les besoins,
• engager un nombre minimum de chauffeurs.
Exemple : problème de recouvrement
Données : Les demandes journalières en chauffeurs dans une entreprise

de transport
Lu Ma Me Je Ve Sa Di
13 18 21 16 12 25 9
Les chauffeurs travaillent cinq jours d’affilée (et peuvent donc avoir leurs
deux jours adjacents de congé n’importe quand dans la semaine).
Objectifs : Déterminer les effectifs formant les sept équipes possibles de
chauffeurs de manière à
• couvrir tous les besoins,
• engager un nombre minimum de chauffeurs.
Problème de recouvrement : modélisation
Variables de décision : On associe une variable de décision à chacune des

sept équipes possibles
x1 : nombre de chauffeurs dans l’équipe du lundi (repos le samedi et le
dimanche),
x2 : nombre de chauffeurs dans l’équipe du mardi,
...
x7 : nombre de chauffeurs dans l’équipe du dimanche.
Fonction objectif : On veut minimiser le nombre total de chauffeurs

engagés
z = x1 + . . . + x7
Problème de recouvrement : modélisation
Variables de décision : On associe une variable de décision à chacune des

sept équipes possibles
x1 : nombre de chauffeurs dans l’équipe du lundi (repos le samedi et le
dimanche),
x2 : nombre de chauffeurs dans l’équipe du mardi,
...
x7 : nombre de chauffeurs dans l’équipe du dimanche.
Fonction objectif : On veut minimiser le nombre total de chauffeurs

engagés
z = x1 + . . . + x7
Contraintes : Le nombre de chauffeurs présents chaque jour doit être
suffisant
x1 + x4 + x5 + x6 + x7 ≥ 13 (lundi)
x1 + x2 + x5 + x6 + x7 ≥ 18 (mardi)
...
x3 + x4 + x5 + x6 + x7 ≥ 9 (dimanche)
Contraintes de bornes : Le nombre de chauffeurs dans chaque équipe

doit non seulement être non négatif mais également entier !
xj ≥ 0 et entier, i = 1, . . . , 7.

Contraintes : Le nombre de chauffeurs présents chaque jour doit être
suffisant
x1 + x4 + x5 + x6 + x7 ≥ 13 (lundi)
x1 + x2 + x5 + x6 + x7 ≥ 18 (mardi)
...
x3 + x4 + x5 + x6 + x7 ≥ 9 (dimanche)
Contraintes de bornes : Le nombre de chauffeurs dans chaque équipe

doit non seulement être non négatif mais également entier !
xj ≥ 0 et entier, i = 1, . . . , 7.

Problème de recouvrement : formulation
Min z = x1 + x2 + x3 + x4 + x5 + x6 + x7
s.c. x1 + x4 + x5 + x6 + x7 ≥ 13
x1 + x2 + x5 + x6 + x7 ≥ 18
x1 + x2 + x3 + x6 + x7 ≥ 21
x1 + x2 + x3 + x4 + x7 ≥ 16
x1 + x2 + x3 + x4 + x5 ≥ 12
x2 + x3 + x4 + x5 + x6 ≥ 25
x3 + x4 + x5 + x6 + x7 ≥ 9
x1 , x2 , x3 , x4 , x5 , x6 , x7 ≥ 0 entiers
Ce problème n’est pas un PL mais un programme linéaire en nombres

entiers (PLNE) !

Les hypothèses de la programmation linéaire
1. La linéarité des contraintes et de la fonction objectif.
2. La proportionnalité des gains/coûts et des consommation de ressources.
3. La divisibilité des variables.
4. Le déterminisme des données.
Lors de la modélisation d’un problème réel, l’impact de ces hypothèses

sur la validité du modèle mathématique doit être étudié. Cette analyse
peut mener à choisir un modèle différent (non linéaire, stochastique, ...)
et est essentielle pour la phase d’interprétation des résultats fournis par
le modèle.

Pourquoi étudier la programmation linéaire ?
1. Malgré les hypothèses sous-jacentes assez restrictives, de nombreux

problèmes peuvent être modélisés par des programmes linéaires. Ces
problèmes apparaissent dans des domaines aussi variés que
• la gestion de production,
• l’économie,
• la distributique,
• les télécommunications,
• ...
2. Il existe des algorithmes généraux (et des codes les mettant en œuvre)
permettant de résoudre efficacement des programmes linéaires (même
lorsque le nombre de variables et de contraintes est important).
Interprétation géométrique
• L’ensemble des solutions d’une inéquation (linéaire) correspond à un

demi-espace dans Rn (un demi-plan dans R2).
• L’ensemble des solutions d’une équation (linéaire) correspond à un

hyperplan dans Rn (une droite dans R2).
• L’ensemble des solutions d’un système d’équations et d’inéquations

(linéaires) correspond à l’intersection des demi-espaces et des hyper-
plans associés à chaque élément du système.
• Cette intersection, appelée domaine admissible, est convexe et définit

un polyèdre dans Rn (une région polygonale dans R2).
















Terminologie
• Une solution est une affectation de valeurs aux variables du problème.
• Une solution est admissible si elle satisfait toutes les contraintes du

problème (y compris les contraintes de bornes).
• La valeur d’une solution est la valeur de la fonction objectif en cette

solution.
• Le domaine admissible D d’un PL est l’ensemble des solutions

admissibles du problème.
• La solution optimale d’un PL (si elle existe) est formée des valeurs
optimales des variables du problème et de la valeur associée de la
fonction objectif.

Terminologie


solution.

fonction objectif.

Terminologie


solution.

fonction objectif.

Terminologie


solution.

fonction objectif.

Terminologie


solution.

fonction objectif.

Résolution graphique dans le plan
• Les lignes de niveau de la fonction objectif sont des droites parallèles

dans R2.
• Il existe des solutions admissibles de valeur z si la ligne de niveau

associée à cette valeur intersecte le domaine admissible D du problème.
• Pour déterminer la valeur maximale atteignable par une solution ad-

missible, il suffit de faire glisser le plus loin possible une ligne de niveau
de la fonction objectif, dans le sens du gradient, jusqu’à ce qu’elle
touche encore tout juste D.
• Les points de contact ainsi obtenus correspondent aux solutions opti-

males du PL.


dans R2.



males du PL.


dans R2.



males du PL.


dans R2.



males du PL.

Résultat d’une optimisation linéaire
Le domaine admissible d’un PL peut être

• vide. Dans un tel cas le problème est sans solution admissible (et ne
possède évidemment pas de solution optimale).
• borné (et non vide). Le problème possède toujours au moins une

solution optimale, quelle que soit la fonction objectif.
• non borné. Selon la fonction objectif choisie,
I le problème peut posséder des solutions optimales ;

I il peut exister des solutions admissibles de valeur arbitrairement
grande (ou petite). Dans un tel cas le PL n’admet pas de solution
optimale finie et est dit non borné.













Les différentes formes d’un programme linéaire
• Formes générale, canonique et standard
• Notations matricielles
• Pourquoi des formes particulières ?
• Équivalence des formulations canonique et standard
• Règles de transformation particulières
• Exemple : approximation de Chebychev

Pn
Opt z = j=1 cj xj
Pn
s.c. j=1 aij xj ≤ bi i ∈ I ⊆ {1, . . . , m}
Pn
j=1 akj xj ≥ bk k ∈ K ⊆ {1, . . . , m}
Pn
j=1 arj xj = br r ∈ R ⊆ {1, . . . , m}
lj ≤ xj ≤ uj j = 1, . . . , n
Opt = Max ou Min, I, K et R disjoints et I ∪ K ∪ R = {1, . . . , m},

lj = −∞ et uj = +∞ possibles.

Forme canonique d’un programme linéaire
n
X
Max z = cj xj
j=1
Xn
s.c. aij xj ≤ bi i = 1, . . . , m
j=1
xj ≥ 0 j = 1, . . . , n
• Problème de maximisation
• Toutes les contraintes sont du type “≤”
• Toutes les variables sont non négatives

Forme canonique d’un programme linéaire
n
X
Max z = cj xj
j=1
Xn
s.c. aij xj ≤ bi i = 1, . . . , m
j=1
xj ≥ 0 j = 1, . . . , n
• Toutes les contraintes sont du type “≤”

Forme standard d’un programme linéaire
n
X
Max z = cj xj
j=1
Xn
s.c. aij xj + xn+i = bi i = 1, . . . , m
j=1
xj ≥ 0 j = 1, . . . , n + m
• Toutes les contraintes sont des équations
• La formulation exhibe une solution particulière dite basique

Forme standard d’un programme linéaire
n
X
Max z = cj xj
j=1
Xn
s.c. aij xj + xn+i = bi i = 1, . . . , m
j=1
xj ≥ 0 j = 1, . . . , n + m
• Toutes les contraintes sont des équations
• La formulation exhibe une solution particulière dite basique

Forme standard (suite)
Autre écriture :
Max (z, s.c. x1, . . . , xn+m ≥ 0)
n
X
avec xn+i = bi − aij xj i = 1, . . . , m
j=1
Xn
z = cj xj
j=1

Autre écriture :
Max (z, s.c. x1, . . . , xn+m ≥ 0)
n
X
j=1
Xn
z = cj xj
j=1
• On passe de la forme canonique à la forme standard en ajoutant dans

chaque contrainte i une variable d’écart xn+i.

Autre écriture :
Max (z, s.c. x1, . . . , xn+m ≥ 0)
n
X
j=1
Xn
z = cj xj
j=1
• On passe de la forme canonique à la forme standard en ajoutant dans

chaque contrainte i une variable d’écart xn+i.
• La solution particulière obtenue en fixant les variables de décision

x1, . . . , xn à zéro joue un rôle important (voir solutions basiques).
Notation matricielle : forme canonique
Max z = cx
s.c. Ax ≤ b
x ≥ 0

Notation matricielle : forme canonique
 
Max z = cx Max z = cD xD
s.c. Ax ≤ b  s.c. AxD ≤ b 
 
x ≥ 0 xD ≥ 0
où  
x1
 . 
c = cD = (c1 . . . cn) , x = xD =  . ,
xn
   
a11 . . . a1n b1
A =  .. ..  et b =  ..  .
  

am1 . . . amn bm

Notation matricielle : forme standard
Max z = cx
s.c. [A | I] x = b
x ≥ 0

Notation matricielle : forme standard
 
Max z = cx Max z = cD xD + 0xE
s.c. [A | I] x = b  s.c. AxD + IxE = b 
 
x ≥ 0 xD , xE ≥ 0
où
c = (cD | cE ) = (cD | 0) = (c1 . . . cn | 0 . . . 0)
 
x1

  .. 
    
xD 
xn
 a11 . . . a1n b1
  . . .. 

x= − = −  A=
 . .  b=
  

xE

 xn+1 
 am1 . . . amn bm

 .. 

xn+m

Notation matricielle : exemple
Pour le problème d’allocation de ressources
Max z = 3x1 + 12x2
s.c. 150x1 + 1000x2 ≤ 8000
75x1 + 200x2 ≤ 2500
x2 ≤ 6
x1 , x2 ≥ 0

Notation matricielle : exemple
Pour le problème d’allocation de ressources
Max z = 3x1 + 12x2
s.c. 150x1 + 1000x2 ≤ 8000
75x1 + 200x2 ≤ 2500
x2 ≤ 6
x1 , x2 ≥ 0
on a
x1
c=
3 12 , x= ,
x2
   
150 1000 8000
A =  75 200  et b =  2500  .
   
0 1 6

Remarques sur les notations
• Les symboles en gras (A, x, 0, . . .) sont réservés pour les matrices
(majuscules) et les vecteurs (minuscules).

• Les vecteurs doivent être interprétés comme des vecteurs-colonnes ou

des vecteurs-lignes selon le contexte (pas ou peu de signes transposés).
Ax : x vecteur-colonne yA : y vecteur-ligne
xy : produit scalaire

• Les vecteurs doivent être interprétés comme des vecteurs-colonnes ou

des vecteurs-lignes selon le contexte (pas ou peu de signes transposés).
Ax : x vecteur-colonne yA : y vecteur-ligne
xy : produit scalaire
• Les inégalités entre vecteurs (matrices) doivent être comprises compo-

santes par composantes :
x ≥ 0 ⇐⇒ x1 ≥ 0, . . . , xn ≥ 0
Mais x 6≥ 0 ⇐⇒ ∃ i t.q. xi < 0.

Pourquoi des formes particulières ?
• Vérifier les hypothèses des méthodes de résolution.
I La méthode du simplexe et ses variantes supposent des problèmes

sous forme standard.
I Les méthodes de points intérieurs supposent des problèmes sous

forme canonique.
• Simplifier la présentation des algorithmes.

Pourquoi des formes particulières ?
• Vérifier les hypothèses des méthodes de résolution.
I La méthode du simplexe et ses variantes supposent des problèmes

sous forme standard.
I Les méthodes de points intérieurs supposent des problèmes sous

forme canonique.
• Simplifier la présentation des algorithmes.
Les définitions des formes canonique et standard varient parfois d’un

auteur à l’autre !

Équivalence des formulations canonique et standard
Théorème 1. Au prix éventuel de l’ajout de contraintes et/ou de variables,
tout PL peut être transformé en un PL sous forme canonique équivalent.

tout PL peut être transformé en un PL sous forme standard équivalent.

Équivalence des formulations canonique et standard
tout PL peut être transformé en un PL sous forme canonique équivalent.

tout PL peut être transformé en un PL sous forme standard équivalent.
Par programme équivalent, on entend :
• toute solution admissible (optimale) du problème équivalent correspond
à une solution admissible (optimale) du problème initial ;
• toute solution admissible (optimale) du problème initial correspond à
au moins une solution admissible (optimale) du problème équivalent ;
• l’issue de l’optimisation des deux problèmes est la même (sans solution
admissible, optimum fini, problème non borné).
Règles de transformation
• Minimisation ↔ maximisation : min f (x) = − max (−f (x))
Pour minimiser z = cx, il suffit de maximiser w = −cx = (−c)x et de

multiplier la valeur optimale de w par −1 pour obtenir celle de z.
• Inéquation “≥“ ↔ inéquation “≤“ :
ax ≥ b ⇐⇒ (−a)x ≤ −b
• Équation → inéquation “≤“ :

ax ≤ b ax ≤ b
ax = b ⇐⇒ ⇐⇒
ax ≥ b (−a)x ≤ −b


ax ≥ b ⇐⇒ (−a)x ≤ −b

ax ≤ b ax ≤ b
ax = b ⇐⇒ ⇐⇒
ax ≥ b (−a)x ≤ −b


ax ≥ b ⇐⇒ (−a)x ≤ −b

ax ≤ b ax ≤ b
ax = b ⇐⇒ ⇐⇒
ax ≥ b (−a)x ≤ −b

Règles de transformation (suite)
• Inéquation → équation : On ajoute une variable d’écart (de surplus)
ax ≤ b ⇐⇒ ax + s = b, s ≥ 0
ax ≥ b ⇐⇒ ax − s = b, s ≥ 0
• Variable libre (réelle) → variable non négative : Tout nombre réel peut
être écrit comme la différence de deux nombres non négatifs.
x = x+ − x−

x∈R→
x+, x− ≥ 0
• ...
ax ≤ b ⇐⇒ ax + s = b, s ≥ 0
ax ≥ b ⇐⇒ ax − s = b, s ≥ 0
x = x+ − x−

x∈R→
x+, x− ≥ 0
• ...
ax ≤ b ⇐⇒ ax + s = b, s ≥ 0
ax ≥ b ⇐⇒ ax − s = b, s ≥ 0
x = x+ − x−

x∈R→
x+, x− ≥ 0
• ...
Exemple de mise sous forme canonique
Min z = −3x1 + 4x2

s.c. x1 + x2 = 6
x1 − 2x2 ≥ 4 PL initial
x1 ∈ R
x2 ≥ 0
Min z = −3x1 + 4x2 → Max w = 3x1 − 4x2

x1 + x2 ≤ 6
x1 + x2 = 6 →
−x1 − x2 ≤ −6
Modifications
x1 − 2x2 ≥ 4 → −x1 + 2x2 ≤ −4
−
x1 = x+

1 − x1
x1 ∈ R → + −
x1 , x1 ≥ 0

PL initial
Min z = −3x1 + 4x2
s.c. x1 + x2 = 6
x1 − 2x2 ≥ 4
x1 ∈ R
x2 ≥ 0
PL canonique équivalent
Max w = 3x+
1 − 3x−
1 − 4x2
s.c. x+
1 − x−1 + x2 ≤ 6
−x+
1 + x−1 − x2 ≤ −6
−x+
1 + x−1 + 2x2 ≤ −4
x+
1 , x−
1 , x2 ≥ 0
Ne pas oublier que zopt = −wopt ! !

Règles de transformation particulières
• Problème Min-Max ou Max-Min :

Min z = t
s.c. t ≥ c1 x
Min z = max{c1x, . . . , ckx} ⇐⇒ ...
t ≥ ck x
t ∈ R


Min z = t
s.c. t ≥ c1 x
Min z = max{c1x, . . . , ckx} ⇐⇒ ...
t ≥ ck x
t ∈ R

x ≤ b
• Valeurs absolues : |x| ≤ b ⇐⇒
x ≥ −b
|x| ≤ b |x| ≥ b
Convexe Non convexe


Min z = t
s.c. t ≥ c1 x
Min z = max{c1x, . . . , ckx} ⇐⇒ ...
t ≥ ck x
t ∈ R

x ≤ b
• Valeurs absolues : |x| ≤ b ⇐⇒
x ≥ −b
|x| ≤ b |x| ≥ b i r e
é a
n lin
Convexe o
N convexe
Non

Exemple : approximation de Chebychev
Données : m mesures y
(xi, yi) ∈ Rn+1, i = 1, . . . , m
yi
xi x

y = ax + b
(xi, yi) ∈ Rn+1, i = 1, . . . , m
|yi − axi − b|
Objectif : Déterminer une ap- yi
proximation linéaire y = ax + b
minimisant la plus grand erreur
xi x
d’estimation.

y = ax + b
(xi, yi) ∈ Rn+1, i = 1, . . . , m
|yi − axi − b|
Objectif : Déterminer une ap- yi
proximation linéaire y = ax + b
minimisant la plus grand erreur
xi x
d’estimation.
Formulation :

Min z = max |yi − axi − b|
i=1,...,m
Les variables de décision de ce problème sont a ∈ Rn et b ∈ R !

On peut récrire le problème comme

Min z = max ∆i
i=1,...,m
s.c. ∆i = |yi − axi − b| i = 1, . . . , m
puis
Min z = t
s.c. t ≥ |yi − axi − b| i = 1, . . . , m
pour finalement obtenir une formulation linéaire
Min z = t
s.c. t ≥ yi − axi − b i = 1, . . . , m
t ≥ −yi + axi + b i = 1, . . . , m
avec a ∈ Rn, b ∈ R et t ≥ 0.

Min z = max ∆i
i=1,...,m
s.c. ∆i = |yi − axi − b| i = 1, . . . , m
puis
Min z = t
s.c. t ≥ |yi − axi − b| i = 1, . . . , m
Min z = t
s.c. t ≥ yi − axi − b i = 1, . . . , m
t ≥ −yi + axi + b i = 1, . . . , m

Min z = max ∆i
i=1,...,m
s.c. ∆i = |yi − axi − b| i = 1, . . . , m
puis
Min z = t
s.c. t ≥ |yi − axi − b| i = 1, . . . , m
Min z = t
s.c. t ≥ yi − axi − b i = 1, . . . , m
t ≥ −yi + axi + b i = 1, . . . , m
Objectifs
• Connaı̂tre les différents éléments d’un PL : variables de décision, d’écart,

fonction objectif, contraintes, contraintes de bornes.
• Être capable de modéliser de petits problèmes : identifier les variables
de décision, écrire la fonction objectif et les contraintes, discuter les
hypothèses de la PL.
• Être capable de résoudre graphiquement un PL à 2 ou 3 variables de
décision : déterminer le domaine admissible et les lignes (surfaces) de
niveau de la fonction objectif, identifier la solution optimale.
• Connaı̂tre les formes canonique et standard et être capable de mettre
un PL sous l’une ou l’autre de ces deux formes.

Recherche Operationelle

Transféré par

Droits d'auteur :

Formats disponibles

Recherche Operationelle

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Recherche Operationelle

Transféré par

Droits d'auteur :

Formats disponibles

La programmation linéaire : une introduction

• Qu’est-ce qu’un programme linéaire ?

• Hypothèses de la programmation linéaire

• Pourquoi étudier la programmation linéaire ?

• Interprétation géométrique : représentation et résolution graphique

J.-F. Hêche, ROSO-DMA-EPFL 1

Un programme linéaire (PL) est un problème d’optimisation consistant

J.-F. Hêche, ROSO-DMA-EPFL 2

Un programme linéaire (PL) est un problème d’optimisation consistant

À l’origine, le terme programme a le sens de planification opérationnelle

La terminologie est due à G. B. Dantzig, inventeur de l’algorithme du

J.-F. Hêche, ROSO-DMA-EPFL 2

Les ensembles I, K, et R sont disjoints, I ∪ K ∪ R = {1, . . . , m} et

J.-F. Hêche, ROSO-DMA-EPFL 3

Les ensembles I, K, et R sont disjoints, I ∪ K ∪ R = {1, . . . , m} et

J.-F. Hêche, ROSO-DMA-EPFL 3

• Les variables x1, . . . , xn sont appelées variables de décision du

• La fonction linéaire à optimiser est appelée fonction objectif (ou

• Les contraintes prennent la forme d’équations et d’inéquations

• Les contraintes de bornes se résument souvent à des contraintes de

J.-F. Hêche, ROSO-DMA-EPFL 4

• Les variables x1, . . . , xn sont appelées variables de décision du

• La fonction linéaire à optimiser est appelée fonction objectif (ou

• Les contraintes prennent la forme d’équations et d’inéquations

• Les contraintes de bornes se résument souvent à des contraintes de

J.-F. Hêche, ROSO-DMA-EPFL 4

• Les variables x1, . . . , xn sont appelées variables de décision du

• La fonction linéaire à optimiser est appelée fonction objectif (ou

• Les contraintes prennent la forme d’équations et d’inéquations

• Les contraintes de bornes se résument souvent à des contraintes de

J.-F. Hêche, ROSO-DMA-EPFL 4

• Les variables x1, . . . , xn sont appelées variables de décision du

• La fonction linéaire à optimiser est appelée fonction objectif (ou

• Les contraintes prennent la forme d’équations et d’inéquations

• Les contraintes de bornes se résument souvent à des contraintes de

J.-F. Hêche, ROSO-DMA-EPFL 4

Que faut-il cuisiner pour maximiser le chiffre d’affaires de la vente ?

J.-F. Hêche, ROSO-DMA-EPFL 5

Que faut-il cuisiner pour maximiser le chiffre d’affaires de la vente ?

J.-F. Hêche, ROSO-DMA-EPFL 5

Que faut-il cuisiner pour maximiser le chiffre d’affaires de la vente ?

J.-F. Hêche, ROSO-DMA-EPFL 5

J.-F. Hêche, ROSO-DMA-EPFL 6

z = 3x1 + (6 × 2)x2 = 3x1 + 12x2.

J.-F. Hêche, ROSO-DMA-EPFL 6

z = 3x1 + (6 × 2)x2 = 3x1 + 12x2.

Il ne faut pas utiliser plus de ressources que disponibles

150x1 + 1000x2 ≤ 8000 (pommes),

J.-F. Hêche, ROSO-DMA-EPFL 6

z = 3x1 + (6 × 2)x2 = 3x1 + 12x2.

Il ne faut pas utiliser plus de ressources que disponibles

150x1 + 1000x2 ≤ 8000 (pommes),

J.-F. Hêche, ROSO-DMA-EPFL 6

z = 3x1 + (6 × 2)x2 = 3x1 + 12x2.

Il ne faut pas utiliser plus de ressources que disponibles

150x1 + 1000x2 ≤ 8000 (pommes),

J.-F. Hêche, ROSO-DMA-EPFL 6

z = 3x1 + (6 × 2)x2 = 3x1 + 12x2.

Il ne faut pas utiliser plus de ressources que disponibles

150x1 + 1000x2 ≤ 8000 (pommes),