[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

quotesdbs_dbs47.pdfusesText_47

[PDF] maximisation des provisions

[PDF] maximisation du profit

[PDF] maximisation du profit en cpp

[PDF] maximisation du profit exercice corrigé

[PDF] maximisation maths

[PDF] Maximiser les bénéfices d'un fermier

[PDF] maximum et minimum d'une fonction du second degré

[PDF] maximum et minimum d'une fonction exercices

[PDF] maximum minimum fonction seconde

[PDF] Maximum ou minimum d'un polynôme

[PDF] maxwell equation derivation

[PDF] maxwell equation in differential form

[PDF] maxwell equations pdf

[PDF] maxwell's equations differential forms

[PDF] maxwell's equations electromagnetic waves