Cours Programmation Linéaire 2 1 .pdf



Nom original: Cours Programmation Linéaire 2-1.pdf
Titre: Concepts de base en probabilité et statistiques
Auteur: khaled

Ce document au format PDF 1.5 a été généré par Microsoft® Office PowerPoint® 2007, et a été envoyé sur fichier-pdf.fr le 03/02/2013 à 15:07, depuis l'adresse IP 197.15.x.x. La présente page de téléchargement du fichier a été vue 1989 fois.
Taille du document: 569 Ko (22 pages).
Confidentialité: fichier public


Aperçu du document


Chapitre 1

Programme linéaire : Forme
générale et transformations
d’objectif



Forme générale d’un programme linéaire
Transformations possibles de la fonction  Objectif 

© Khaled Jabeur 2012

Cours Programmation Linéaire

1

Plan
1. Forme générale d’un programme linéaire
2. Transformations possibles de la fonction  Objectif 

Cours Programmation Linéaire

2

Plan
1. Forme générale d’un programme linéaire
2. Transformations possibles de la fonction  Objectif 

Cours Programmation Linéaire

3

Forme générale d’un programme linéaire
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 (qui peut
être quelconque).

 Un paramètre est une quantité dont la valeur
n’est pas fixée à l’avance, mais qui ne fait pas
l’objet d’un choix.

Cours Programmation Linéaire

4

Forme générale d’un programme linéaire
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.
Exemple:

u v x y z
f (u, v, x, y, z )  2uv 2  3xyz  2 1 1 0 5
0 3 1 1 1

Cours Programmation Linéaire

f (u , v, x, y, z )
4
3

5

Forme générale d’un programme linéaire
Définitions préliminaires …
 É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 et 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).
Cours Programmation Linéaire

6

Forme générale d’un programme linéaire
Définitions préliminaires …
 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.).

Cours Programmation Linéaire

7

Forme générale d’un programme linéaire
Conventions d’écriture d’un Programme 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.

Cours Programmation Linéaire

8

Forme générale d’un programme linéaire
Exemple
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 non linéaire
non linéaire
f (u, v, x, y, z )  u 2  x  2 y  7 z
Cours Programmation Linéaire

9

Forme générale d’un programme linéaire
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
Cours Programmation Linéaire

10

Forme générale d’un programme linéaire
Programme linéaire …
• 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
Cours Programmation Linéaire

11

Forme générale d’un programme linéaire
Programme linéaire …
 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.
Cours Programmation Linéaire

12

Forme générale d’un programme linéaire
Variables de décision: x1 , x2 ,
Fonction
objectif

, xn



Maximiser / Minimiser
Z  c1 x1  c2 x2   cn xn

Sous les contraintes:
Contraintes
générales

Restrictions
de signes







a11 x1  a12 x2 
a21 x1  a22 x2 

 a1n xn  /  /  b1
 a2 n xn  /  /  b2

am1 x1  am 2 x2 

 amn xn  /  /  bm







x1  0
x2  0

Coefficients de la
fonction objectif
Coefficients des
contraintes

Côtés droits des
contraintes

Données du
problème

xn  0
Cours Programmation Linéaire

13

Forme générale d’un programme linéaire
Programme linéaire: Variables de décision: x1, x2, x3, x4

Max Z  x1  2 x2  5 x4
S.l.c.: 2 x1  3 x2  5 x3  10
 x2  2 x3  5 x4  18
x3  9 x4  7
x1  0
x3  0
Variables de décision: x, abc, longnomdevariable, chose25
Programme linéaire:

Mêmes
données,

même
programme
linéaire !

Max Z  x  2abc  5chose25
S.l.c.: 2 x  3abc  5longnomdevariable  10
abc  2longnomdevariable  5chose25  18
longnomdevariable  9chose25  7
x0
longnomdevariable  0
Cours Programmation Linéaire

14

Plan
1. Forme générale d’un programme linéaire
2. Transformations possibles de la fonction  Objectif 

Cours Programmation Linéaire

15

Transformations possibles de la fonction Objectif 
 Un programme linéaire est un cas particulier de programme
mathématique. Tout programme mathématique peut être
représenté de façon abstraite comme:

Maximiser / Minimiser :
Sous les contraintes :
Où: –



f ( x)
x X

x est un vecteur (ensemble ordonné) de variables de décision
X est le domaine réalisable
f(x) est la fonction objectif

Cours Programmation Linéaire

16

Transformations possibles de la fonction Objectif 
Soit le programme mathématique :

Min
S.l.c.:

f ( x)
x X

f ( x)

Z

x



x

X

Soient: – x* une décision optimale
– Z* = f (x*) la valeur optimale de la fonction objectif
Question: Quelles transformations de l’objectif ne changent pas la (les)
décision(s) optimale(s) ?
Cours Programmation Linéaire

17

Transformations possibles de la fonction Objectif 
Ajouter une constante
Min
S.l.c.:

f ( x)  c
x X

f ( x)
f ( x)  c

Z

x

x



X



x* reste optimale



Z*  Z* + c
Cours Programmation Linéaire

18

Transformations possibles de la fonction Objectif 
Multiplier par nombre strictement positif
Min
af ( x)
S.l.c.: x  X

(a  0)

f ( x)
af ( x)

Z

x





x* reste optimale



Z*  aZ*

x

X

Cours Programmation Linéaire

19

Transformations possibles de la fonction Objectif 
f ( x)

Z

Multiplier par -1



Z

x





x

X

 f ( x)
Max  f ( x)
S.l.c.: x  X


x* reste optimale



Z*  Z*

Cours Programmation Linéaire

20

Transformations possibles de la fonction Objectif 
 Raisonnement similaire pour un problème initial de
maximisation
 Ces différentes opérations peuvent être combinées.
Exemple: si a < 0
Max
S.l.c.:




f ( x)
x X



Min
af ( x)  c
S.l.c.: x  X

x* reste optimale
Z*  aZ*+ c

Cours Programmation Linéaire

21

Transformations possibles de la fonction Objectif 
Les transformations suivantes sur l’objectif produisent un
problème équivalent (ne changent pas la ou les solutions
optimales):
– ajouter une constante (> 0 ou < 0) à l’objectif;
– multiplier l’objectif par un nombre strictement positif;
– multiplier l’objectif par un nombre strictement négatif et changer
• « min » en « max » ou
• « max » en « min »;

– et toute combinaison de ces opérations.

Cours Programmation Linéaire

22



Télécharger le fichier (PDF)









Documents similaires


cours programmation lineaire 2 1
r vision
184787880 programmation lineaire ppt
cours programmation lineaire 4 1
cours7 imp
ro