RECHERCHE OPERATIONNELLE

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

[PDF] cours de recherche operationnelle gratuit pdf

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

[PDF] examen recherche opérationnelle corrigé

[PDF] exercice corrigé methode simplexe pdf

[PDF] multiples et sous multiples physique

[PDF] multiples et sous multiples physique exercices

[PDF] multiples et sous multiples du gramme

[PDF] multiple et sous multiple exercice

[PDF] multiples et sous multiples du litre

[PDF] multiplicateur fiscal formule

[PDF] multiplicateur fiscal macroéconomie

[PDF] cobb douglas explication

[PDF] revenu d'équilibre formule

[PDF] multiplicateur des dépenses publiques macroéconomi

RECHERCHE OPERATIONNELLE - Site de Mohamed Amine EL AFRIT

Esnard Aurélien Recherche opérationnelle ENSERB informatique page 1 sur 20 16/04/04

Esnard Aurélien Recherche opérationnelle ENSERB informatique page 2 sur 20 16/04/04

Sommaire

RECHERCHE OPéRATIONNELLE ..................................................................................................................... 1

Sommaire................................................................................................................................................................ 2

Programmation linéaire........................................................................................................................................... 3

Exemple classique............................................................................................................................................... 3

Mise en équation............................................................................................................................................. 3

Formulation générale ...................................................................................................................................... 3

Propositions..................................................................................................................................................... 3

Forme canonique & standard.............................................................................................................................. 3

Transformation d'écriture ............................................................................................................................... 3

Forme standard................................................................................................................................................ 3

Forme canonique............................................................................................................................................. 4

Exemple .......................................................................................................................................................... 4

Bases, bases réalisables, solutions de base.......................................................................................................... 4

Base & hors-base ............................................................................................................................................ 4

Solution de base.............................................................................................................................................. 4

Exemple .......................................................................................................................................................... 4

Caractérisation d'une base réalisable.............................................................................................................. 4

Théorème ........................................................................................................................................................ 4

Solutions optimales......................................................................................................................................... 5

Caractérisation des bases optimales.................................................................................................................... 5

Théorème ........................................................................................................................................................ 5

Exemple classique........................................................................................................................................... 5

Algorithme du simplexe - Méthode des tableaux............................................................................................... 5

Méthode .......................................................................................................................................................... 5

Exemple classique........................................................................................................................................... 6

Analyse du tableau final du simplexe.............................................................................................................. 7

Méthode révisée du simplexe.............................................................................................................................. 8

Convergence & Initialisation du simplexe.......................................................................................................... 8

Théorème : Convergence de l'algorithme....................................................................................................... 8

Initialisation .................................................................................................................................................... 8

Initialisation : Méthode du gros M.................................................................................................................. 9

Initialisation : Méthode des deux phases......................................................................................................... 9

Perturbation verticale & horizontale................................................................................................................. 10

Perturbation verticale.................................................................................................................................... 10

Exemple de perturbation verticale................................................................................................................. 10

Perturbation horizontale................................................................................................................................ 11

Exemple de perturbation horizontale ............................................................................................................ 11

Ajout d'un nouveau produit C dans l'exemple classique.............................................................................. 11

Dualité............................................................................................................................................................... 12

Exemple : Problème du restaurant et du pharmacien concurrents................................................................. 12

Modélisation du problème............................................................................................................................. 13

Mise en équation sur quelques exemples.......................................................................................................... 13

Problème de transport ................................................................................................................................... 13

Ordonnancement à contraintes disjonctives.................................................................................................. 13

Prise en compte de puissance........................................................................................................................ 14

Programmation linéaire combinatoire (entiers)................................................................................................. 15

Algorithme du B&B...................................................................................................................................... 15

Illustration de l'algorithme............................................................................................................................ 15

Exemple de modélisation : Localisation d'usines......................................................................................... 16

Processus aléatoire : chaînes de Markov............................................................................................................... 17

Généralités .................................................................................................................................................... 17

Classification des états.................................................................................................................................. 17

Comportement asymptotique et distribution stationnaire.............................................................................. 17

Décisions et Chaînes de Markov................................................................................................................... 18

Exemple du confectionneur........................................................................................................................... 19

Décisions multiples....................................................................................................................................... 19

Exemple du confectionneur (suite et fin)...................................................................................................... 20

Esnard Aurélien Recherche opérationnelle ENSERB informatique page 3 sur 20 16/04/04

Programmation linéaire

Exemple classique

Soit une firme produisant du A et du B avec du M1, du M2 et du M3, selon le tableau suivant :

ABStocks

M1 2 1 8

M2 1 2 7

M3 0 1 3

Gain / unité 4 5

Mise en équation

Soit x

1 la quantité de A et x 2 la quantité de B, avec0 1 x et 0 2 x. - bilan de M1 : 82
21
xx - bilan de M2 : 72 21
xx - bilan de M3 : 3 2 x - Critère : 21
54xxZ

Formulation générale

Le problème (P) revient de chercher x tel que la fonction économique Z soit maximum. t d 0, x bAxxcxZ P

bAxx,0 est un polyèdre, qui représente l'ensemble des solutions. Si est vide, le problème n'a

pas de solution réalisable. Sinon le problème possède une solution optimale, à moins que Z ne soit pas borné sur

. On distingue les contraintes lâches et saturées.

Propositions

- est un polyèdre convexe (par construction). - S'il existe une solution optimale finie, c'est un sommet de

Forme canonique & standard

Transformation d'écriture

0,xxxxxRx

baxbaxbax

0sbsaxbax

- ZMaxZMin

Forme standard

Un problème est dit sous forme standard si et seulement si toutes les vraies contraintes, autre que0

i x, sont

des égalités. Il est souvent nécessaire d'introduire des variables d'écart pour transformer des inégalités en

égalité.

Esnard Aurélien Recherche opérationnelle ENSERB informatique page 4 sur 20 16/04/04Forme canonique Quant à la forme canonique, elle fait intervenir exclusivement des inégalités. Remarque : Notons que pour ces deux formes, il faut se ramener à un problème de maximum.

Exemple

Écrivons l'exemple sous forme standard.

30007002x8002x

52421321

i xxxxxxx P , ce qui donne la matrice

100100102100112

A et 378
b

Bases, bases réalisables, solutions de base

On suppose que le problème P s'écrit

t 0, x bAxxcxZ avec A une matrice de dimension m x n.

Base & hors-base

Considérons un m-uplet B. On dit que B forme un base si et seulement si la matrice A B m x m, constituée par les colonnes de A d'indice dans B, est régulière. Le complément de B dans n,,1est le hors-base associé HB.

On a :

bxAxAbAx

HBHBBB

quotesdbs_dbs2.pdfusesText_2

[PDF] RECHERCHE OPERATIONNELLE - Site de Mohamed Amine EL AFRIT

Recherche Opérationnelle - LORIA