[PDF] MOD 4.4: Recherche opérationnelle

View - Download MOD 4.4: Recherche opérationnelle

Previous PDF

Next PDF

MOD 4.4: Recherche operationnelle

Nicolas Bousquet

Ecole Centrale de Lyon

1/63

Deroulement du cours

Cours 1:Programmation Lineaire.

Introduction a la Recherche Operationnelle.

Programmation lineaire.

Algorithme du Simplexe.

Cours 2:Dualite et Analyse de sensitivite.

Analyse de sensibilite.

Dual d'un programme lineaire.

Qu'est ce qu'un graphe?

Application de la dualite aux graphes.

Cours 3:Programmation Lineaire en nombre entiers.

(n novembre) 2/63

Recherche Operationnelle

La

Recherche Op erationnelle

p eut^ etred eniecomm el'ensemble des methodes et techniques rationnelles orientees vers la recherche du meilleur choix dans la facon d'operer en vue d'aboutir au resultat vise ou au meilleur resultat possible.Denition(wikipedia)Exemples:

Ordonnancement.

Routage.

Optimisation industrielle.

Aide a la decision.Dierentes approches:

Solutions exactes. (Algo.

polynomiaux...)

Solutions approchees.

Heuristiques.3/63

Recherche Operationnelle

La

Recherche Op erationnelle

p eut^ etred eniecomm el'ensemble des methodes et techniques rationnelles orientees vers la recherche du meilleur choix dans la facon d'operer en vue d'aboutir au resultat vise ou au meilleur resultat possible.Denition(wikipedia)Exemples:

Ordonnancement.

Routage.

Optimisation industrielle.

Aide a la decision.Dierentes approches:

Solutions exactes. (Algo.

polynomiaux...)

Solutions approchees.

Heuristiques.3/63

Recherche Operationnelle

La

Recherche Op erationnelle

p eut^ etred eniecomm el'ensemble des methodes et techniques rationnelles orientees vers la recherche du meilleur choix dans la facon d'operer en vue d'aboutir au resultat vise ou au meilleur resultat possible.Denition(wikipedia)Exemples:

Ordonnancement.

Routage.

Optimisation industrielle.

Aide a la decision.Dierentes approches:

Solutions exactes. (Algo.

polynomiaux...)

Solutions approchees.

Heuristiques.3/63

Programmation Lineaire (PL)

Minimisation/ maximisation d'une fonction lineaire sous des con- traintes elles-m^eme lineaires.Denition(programme lineaire)Classiquement: n= nombre de variables. x

1;:::;xn= ensemble des variables.

m= nombre de contraintes.Exemple: nX i=1a ixibn X i=1a ixib,nX i=1aixi bn X i=1a ixi=bi, (nX i=1a ixib)ANDnX i=1a ixibx i04/63

Programmation Lineaire (PL)

Minimisation/ maximisation d'une fonction lineaire sous des con- traintes elles-m^eme lineaires.Denition(programme lineaire)Classiquement: n= nombre de variables. x

1;:::;xn= ensemble des variables.

m= nombre de contraintes.Exemple: nX i=1a ixibn X i=1a ixib,nX i=1aixi bn X i=1a ixi=bi, (nX i=1a ixib)ANDnX i=1a ixibx i04/63

Programmation Lineaire (PL)

Minimisation/ maximisation d'une fonction lineaire sous des con- traintes elles-m^eme lineaires.Denition(programme lineaire)Classiquement: n= nombre de variables. x

1;:::;xn= ensemble des variables.

m= nombre de contraintes.Exemple: nX i=1a ixibn X i=1a ixib,nX i=1aixi bn X i=1a ixi=bi, (nX i=1a ixib)ANDnX i=1a ixibx i04/63

Programmation Lineaire (PL)

Minimisation/ maximisation d'une fonction lineaire sous des con- traintes elles-m^eme lineaires.Denition(programme lineaire)Classiquement: n= nombre de variables. x

1;:::;xn= ensemble des variables.

m= nombre de contraintes.Exemple: nX i=1a ixibn X i=1a ixib,nX i=1aixi bn X i=1a ixi=bi, (nX i=1a ixib)ANDnX i=1a ixibx i04/63

Programmation Lineaire (PL)

Minimisation/ maximisation d'une fonction lineaire sous des con- traintes elles-m^eme lineaires.Denition(programme lineaire)Classiquement: n= nombre de variables. x

1;:::;xn= ensemble des variables.

m= nombre de contraintes.Exemple: nX i=1a ixibn X i=1a ixib,nX i=1aixi bn X i=1a ixi=bi, (nX i=1a ixib)ANDnX i=1a ixibx i04/63

Programmation Lineaire (PL)

Minimisation/ maximisation d'une fonction lineaire sous des con- traintes elles-m^eme lineaires.Denition(programme lineaire)Classiquement: n= nombre de variables. x

1;:::;xn= ensemble des variables.

m= nombre de contraintes.Exemple: nX i=1a ixibn X i=1a ixib,nX i=1aixi bn X i=1a ixi=bi, (nX i=1a ixib)ANDnX i=1a ixibx i04/63

Forme normale d'un PL

max Xc ixi soumis a8j;nX i=1a ixibj

8i;xi0A= Matrice desai;j.

c= vecteur desci. b= vecteur desbi.

Un programme lineaire est sous

fo rmeno rmale s'il s' ecrit: maxctx soumis aAxb x0 La contraintex0 s'appellec ontraintede p ositivite.5/63

Forme normale d'un PL

max Xc ixi soumis a8j;nX i=1a ixibj

8i;xi0A= Matrice desai;j.

c= vecteur desci. b= vecteur desbi.

Un programme lineaire est sous

fo rmeno rmale s'il s' ecrit: maxctx soumis aAxb x0 La contraintex0 s'appellec ontraintede p ositivite.5/63

Exemple

Une usine fabrique des chaises et des tables. Chaque semaine l'usine commande la m^eme quantite de bois, conna^t le temps de travail de ses employes et la duree de fonctionnement de ses machines. Sachant qu'une table rapporte 6 euros et une chaise 4, quel est le mix chaises-tables qui maximise le revenu de l'usine?TableChaiseQuantite disponible

Equipement3981

Main d'oeuvre4555

Bois2120

6/63

Exemple

Une usine fabrique des chaises et des tables. Chaque semaine l'usine commande la m^eme quantite de bois, conna^t le temps de travail de ses employes et la duree de fonctionnement de ses machines. Sachant qu'une table rapporte 6 euros et une chaise 4, quel est le mix chaises-tables qui maximise le revenu de l'usine?TableChaiseQuantite disponible

Equipement3981

Main d'oeuvre4555

Bois2120

6/63

Mise en equation

TableChaiseQuantite disponible

Equipement3981

Main d'oeuvre4555

Bois2120

Creation de deux variables:xtetxc.

Creation de trois contraintes: equipement, main d'oeuvre, bois:

3xt+ 9xc81

4xt+ 5xc55

2xt+xc20

x t;xc0

Creation de la fonction objectif.

z= max(6xt+ 4xc)7/63

Mise en equation

TableChaiseQuantite disponible

Equipement3981

Main d'oeuvre4555

Bois2120

Creation de deux variables:xtetxc.

Creation de trois contraintes: equipement, main d'oeuvre, bois:

3xt+ 9xc81

4xt+ 5xc55

2xt+xc20

x t;xc0

Creation de la fonction objectif.

z= max(6xt+ 4xc)7/63

Mise en equation

TableChaiseQuantite disponible

Equipement3981

Main d'oeuvre4555

Bois2120

Creation de deux variables:xtetxc.

Creation de trois contraintes: equipement, main d'oeuvre, bois:

3xt+ 9xc81

4xt+ 5xc55

2xt+xc20

x t;xc0

Creation de la fonction objectif.

z= max(6xt+ 4xc)7/63

Mise en equation

TableChaiseQuantite disponible

Equipement3981

Main d'oeuvre4555

Bois2120

Creation de deux variables:xtetxc.

Creation de trois contraintes: equipement, main d'oeuvre, bois:

3xt+ 9xc81

4xt+ 5xc55

2xt+xc20

x t;xc0

Creation de la fonction objectif.

z= max(6xt+ 4xc)7/63

Resolution du systeme

Quand on resout le systeme, on obtient la solution optimale suivante: (xt;xc) = (15=2;5): Cette solution peut ^etre obtenue de plusieurs facons:

En dimension 2: graphiquement.

En toute dimension: comment faire?x

tx cBoisMaind'o euvre515=2Equipement 8/63

Resolution du systeme

Quand on resout le systeme, on obtient la solution optimale suivante: (xt;xc) = (15=2;5): Cette solution peut ^etre obtenue de plusieurs facons:

En dimension 2: graphiquement.

En toute dimension: comment faire?x

tx cBoisMaind'o euvre515=2Equipement 8/63

Points extr^emes et recherche de solution

optimalex tx cBoisMaind'o euvre515=2Equipement

Une contrainte

Paixibdenit undemi-espace .

La contraintePaixibests erreep ourun p ointzsiPaizi=b.Unp ointextr ^emezest un point tel que: zsoit une solution, zest l'unique point a l'intersection d'un ensembleCde contraintes serrees. 9/63

Points extr^emes et recherche de solution

optimalex tx cBoisMaind'o euvre515=2Equipement

Une contrainte

Paixibdenit undemi-espace .

La contraintePaixibests erreep ourun p ointzsiPaizi=b.Unp ointextr ^emezest un point tel que: zsoit une solution, zest l'unique point a l'intersection d'un ensembleCde contraintes serrees. 9/63

A quoi ressemble une solution optimale?

Remarque:

L'ensemble des solutions est une intersection de demi-espaces fermes.

En particulier c'est un espace

convexe et ferm e .Theoreme 1: On optimise une fonction lineaire (donc convexe et concave) dans un convexe )Un maximum (resp. minimum) local est unmaximum (resp. minimum) global .Theoreme 2:

Si la valeur optimale est nie alors il existe un

p ointextr ^emequi atteint le maximum .Principe de l'algorithme du simplexe:Se promener de points extr^emes en points extr^emes. 10/63

A quoi ressemble une solution optimale?

Remarque:

L'ensemble des solutions est une intersection de demi-espaces fermes.

En particulier c'est un espace

convexe et ferm e .Theoreme 1: On optimise une fonction lineaire (donc convexe et concave) dans un convexe )Un maximum (resp. minimum) local est unmaximum (resp. minimum) global .Theoreme 2:

Si la valeur optimale est nie alors il existe un

p ointextr ^emequi atteint le maximum .Principe de l'algorithme du simplexe:Se promener de points extr^emes en points extr^emes. 10/63

A quoi ressemble une solution optimale?

Remarque:

L'ensemble des solutions est une intersection de demi-espaces fermes.

En particulier c'est un espace

convexe et ferm e .Theoreme 1: On optimise une fonction lineaire (donc convexe et concave) dans un convexe )Un maximum (resp. minimum) local est unmaximum (resp. minimum) global .Theoreme 2:

Si la valeur optimale est nie alors il existe un

p ointextr ^emequi atteint le maximum .Principe de l'algorithme du simplexe:Se promener de points extr^emes en points extr^emes. 10/63

A quoi ressemble une solution optimale?

Remarque:

L'ensemble des solutions est une intersection de demi-espaces fermes.

En particulier c'est un espace

convexe et ferm e .Theoreme 1: On optimise une fonction lineaire (donc convexe et concave) dans un convexe )Un maximum (resp. minimum) local est unmaximum (resp. minimum) global .Theoreme 2:

Si la valeur optimale est nie alors il existe un

p ointextr ^emequi atteint le maximum .Principe de l'algorithme du simplexe:Se promener de points extr^emes en points extr^emes. 10/63

Etape 1: Mettre le PL sous forme standard

Forme standard:maxctx

soumis aAx=b x0Idee:rajouter desva riablesd' ecart. n X i=1a ixib

Creer une variableyet poser:

y=bnX i=1a ixi

Notez quey0 etPn

quotesdbs_dbs33.pdfusesText_39

[PDF] programmation lineaire methode simplexe

[PDF] programmation linéaire recherche opérationnelle

[PDF] interprétation droite de henry

[PDF] principe droite de henry

[PDF] exercice corrigé droite de henry

[PDF] courbe de henry excel

[PDF] droite de henry pdf

[PDF] programmation linéaire exercices corrigés pdf

[PDF] programmation linéaire exercices corrigés

[PDF] programmation linéaire simplexe

[PDF] recherche opérationnelle programmation linéaire exercices corrigés pdf

[PDF] exercices recherche operationnelle

[PDF] theme astral chinois complet gratuit interpretation

[PDF] cours recherche opérationnelle methode de simplexe

[PDF] recherche opérationnelle simplexe exercices corrigés