Recherche Operationnelle

RECHERCHE OPERATIONNELLE

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

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 :

A B Stocks

M1 2 1 8

M2 1 2 7

M3 0 1 3

Gain / unité 4 5

Mise en équation

Soit x1 la quantité de A et x2 la quantité de B, avec et .

- bilan de M1 :

- bilan de M2 :

- bilan de M3 :

- Critère :

Formulation générale

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

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

-

-

- et

-

Forme standard

Un problème est dit sous forme standard si et seulement si toutes les vraies contraintes, autre que , sont des égalités. Il est souvent nécessaire d’introduire des variables d’écart pour transformer des inégalités en égalité.

Forme 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.

, ce qui donne la matrice et .

Bases, bases réalisables, solutions de base

On suppose que le problème P s’écrit avec A une matrice de dimension m x n.

...