Forme d’un programme linéaire

© P. Lang A2009 1
 Définitions préliminaires
• Une variable est une quantité
– dont la valeur n’est pas fixée à l’avance, mais qu’on peut choisir (variable de
décision)
– qu’on convient de désigner par un nom quelconque).
Exemple: NS = le nombre de parts du fonds Sudville que je dois acheter le mois prochain.

• Un paramètre est une famille de données (ne faisant donc pas

l’objet d’un choix), désignée par un symbole.
Par exemple, il s’agit d’une quantité inconnue:
pS = le prix de la part du fonds Sudville au début du mois prochain. Ce prix,
inconnu, pourrait aller de 0 à 80 $.
ou il s’agit d’une série de données:
pSt = le prix de la part du fonds Sudville au début du mois t (1  t 
6).
© P. Lang A2009 2
 Définitions préliminaires
• Étant donné plusieurs variables (par exemple u, v, x, y, z),
une fonction de ces variables associe à chaque choix de
valeurs pour u, v, x, y, z un nombre.
• Une fonction peut être définie par une formule ou par une
table.
Exemple: u v x y z f (u , v, x, y , z )
f (u, v, x, y , z ) 2uv 2  3xyz  2 1 1 0 5 4
0 3 1 1 1 3

© P. Lang A2009 3
 Définitions (suite)
• Étant donné n variables x1, x2,…, xn,
– une fonction affine de ces variables est une fonction de la forme:
f(x1, x2,…, xn) = a1x1 + a2x2 +… + anxn + b
où: a1, a2,…, an sont des nombres connus appelés coefficients
b est un nombre connu appelé ordonnée à l’origine (ou constante)
– une fonction linéaire de ces mêmes variables est de la forme:
f(x1, x2,…, xn) = a1x1 + a2x2 +… + anxn
(où l’ordonnée à l’origine est nulle : f(0, 0,…, 0) = 0).
• Remarques: une fonction linéaire est une somme de termes :
coefficient numérique  variable. En particulier,
– elle n’a pas de terme constant (ordonnée à l’origine);
– les seules opérations sur les variables sont : multiplication par une
coefficient numérique, et addition-soustraction; il n’y a pas sur les
variables d’autres opérations (produit, division, puissance, etc.).
© P. Lang A2009 4
 Conventions d’écriture pour une fonction linéaire
• aucune variable n’est répétée;
• les coefficients numériques sont donnés (ce ne sont pas des
variables ni des expressions à calculer);
• pour simplifier l’écriture, on prend différentes conventions :
omettre les opérateurs «  »; effectuer les multiplications
avant les additions; omettre les parenthèses; omettre les
termes nuls; omettre les coefficients égaux à 1; écrire
« 2… » au lieu de « +(2)… », etc.

© P. Lang A2009 5
 Exemples
Soient les variables u, v, x, y, z. La fonction f(u, v, x, y, z)
est-elle linéaire ? Est-elle bien écrite ?
f (u , v, x, y, z ) (  1) u   0 v   1x   ( 2) y   7 z 
- elle est linéaire
- elle peut s'écrire: f (u , v, x, y, z )  u  x  2 y  7 z
f (u , v, x, y, z ) u  x  2 y  7 z  2u
f (u , v, x, y, z ) (1  2)u  x  2 y  7 z
devraient s'écrire: f (u, v, x, y, z )  u  x  2 y  7 z
f (u , v, x, y, z )  u  x  2 y  7 z  10
affine mais pas linéaire
f (u , v, x, y, z )  u  x  2 y  7 z  5 xy
xy non linéaire
f (u , v, x, y, z )  u 2  x  2 y  7 z non linéaire

© P. Lang A2009 6
 Programme linéaire
• Un programme linéaire a pour ingrédients
– des variables de décision,
– un objectif, et
– des contraintes.
• L’objectif
– est une fonction linéaire des variables;
– on doit spécifier dans quelle direction il s’améliore : il est à
maximiser ou à minimiser.
• Les contraintes sont de deux sortes:
– contraintes générales
– contrainte particulière sur une variable

© P. Lang A2009 7
 Programme linéaire (suite)
• Une contrainte générale est une égalité ou une inégalité linéaire.
– Son membre de gauche (« côté gauche ») est une fonction linéaire
des variables.
– Son membre de droite (« côté droit ») est une constante.
– Une relation , , ou = est imposée entre ces deux membres.
• Une contrainte particulière ne s’applique qu’à une seule variable
(plutôt qu’un groupe de variables).
– Contraintes d’intégralité: xj  {0, 1, 2, 3…}
– Contraintes de bornes:
• xj  constante (borne inférieure)
• xj  constante (borne supérieure)
– Cas particulier important: restriction de signe xj  0
© P. Lang A2009 8
 Programme linéaire (suite)
• Une décision (ou solution) est un choix de valeur pour toutes
les variables de décision.
• Une décision est réalisable si elle respecte toutes les
contraintes. L’ensemble des décisions réalisables est le
domaine réalisable.
• Une décision est optimale si
– elle est réalisable, et
– elle donne la meilleure valeur possible à l’objectif parmi toutes
les décisions réalisables.
• « Résoudre » un programme linéaire, c’est tenter de trouver
une décision optimale.

© P. Lang A2009 9
 Forme d’un programme linéaire pur
Variables de décision: x1 , x2 ,, xn
Coefficients de la
Fonction
objectif  Maximiser / Minimiser
Z c1 x1  c2 x2    cn xn
fonction objectif

Coefficients des
Sous les contraintes: contraintes
 a11 x1  a12 x2    a1n xn / /  b1
Contraintes  a21 x1  a22 x2    a2 n xn / /  b2 Côtés droits des
générales     contraintes
 am1 x1  am 2 x2    amn xn / /  bm
 x1  0
Restrictions  x2  0 Données du
 problème
de signes    
 xn  0

© P. Lang A2009 10
 Exemple
Variables de décision: x1, x2, x3, x4
Programme linéaire:
Max Z x1  2 x2  5 x4 Mêmes
S.l.c.: 2 x1  3 x2  5 x3 10
 x2  2 x3  5 x4 18
x3  9 x4 7 données,
x1 0
x3 0 même
Variables de décision: x, abc, longnomdevariable, chose25
programme
Programme linéaire:
Max Z x  2abc  5chose25 linéaire !
S.l.c.: 2 x  3abc  5longnomdevariable 10
 abc  2longnomdevariable  5chose 25 18
longnomdevariable  9chose 25 7
x 0
longnomdevariable 0
© P. Lang A2009 11
 Glossaire
Terme p. Terme p.
Borne 7 Programme linéaire 6
Coefficient 3 Réalisable (décision, solution) 8
Contrainte générale 7 Réalisable (domaine) 8
Contrainte particulière 7 Restriction de signe 7
Côté gauche, côté droit 7 Variable 2
Fonction 2
Fonction affine 3
Fonction linéaire 3
Objectif 6
Optimale (décision, solution) 8
Paramètre 2

© P. Lang A2009 12