---
title: "[Cours] Introduction à la Recherche Opérationnelle - Séance 1"
tags: Recherche Opérationnelle, Cours, ICE, 2022
---
# [Cours] Introduction à la Recherche Opérationnelle - Séance 1

Intervenant : 
    Mehdi Charles
    [e-mail]
Entreprise : 
    DecisionBrain

Qu'est-ce que la RO?

## Sommaire
- La Recherche Opérationnelle
- La Recherche Opérationnelle chez DecisionBrain
- Utilisation d'un solveur d'optimisation
- Introduction au projet

## La Recherche Opérationnelle
### Qu'est-ce que c'est ?

C'est le fait de prendre la meilleure décision. On a un problème avec des contraintes, des variables, etc... Ainsi il faut trouver la meilleure solution pour ce problème.

Donc comment peut-on évaluer la qualité de la solution et comment peut-on choisir la meilleure ?

La RO est une matière mathématique mais aussi très ancrée dans l'informatique grâce à son côté algorithmique très poussé (ainsi que le côté financier, le but est d'économiser/gagner de l'argent).

### Formulation générale d'un problème de RO
Un problème de RO est constitué de :
- Un ensemble de **données** connues en avance
- Un ensemble de **variables** dont il faut déterminer les valeurs optimales

Résoudre un problème de RO c'est :
- Optimiser une **fonction objectif**
- Respecter un ensemble de **contraintes**

Par exemple, le problème du Sac à Dos :
- un sac à dos possède une capacité maximale
- on souhaite le remplir avec divers objets
- chaque objet possède un poids et une utilité

-> L'objectif est de maximiser l'**utilité totale**.


On va équilibrer en fonction du niveau de précision que l'on veut obtenir de la part de notre modèle. Plus on veut se rapprocher de la réalité, plus le modèle va être complexe jusqu'à pouvoir devenir impossible à appliquer/résoudre.

### Résoudre un problème de Recherche Opérationnelle
Plusieurs options :


Ne pas avoir la solution optimale n'est pas très grave, il suffit d'une solution "très bonne", soit une solution qui résout son problème et permet à l'entreprise d'obtenir un profit.

Exemple :


Il faut être capable de trouver des solutions dans des temps raisonnables. Cependant dans certains cas ce n'est pas le cas (ex: EDF avec des problèmes quadratiques au lieu de linéaires).
On ne s'interesse pas que aux problèmes avec des variables discrètes mais aussi des variables continues

## Utilisation d'un solveur d'optimisation
### S C I P Y I S C O M I N G
Librairie *SciPy* de Python.
CAMA flashbacks
- fonction *linProg* de Python (solver d'optimisation)
- télécharger Anaconda de préférence pour éviter le DL des librairies

scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None,
    bounds=None, method='interior-point', callback=None, options=None,
    x0=None)

- Modélisation du problème :

### Différents Domaines d'application
![Uploading file..._851pbum90]()

## La Recherche Opérationnelle chez DecisionBrain
### DecisionBrain
Une startup en Recherche Opérationnelle qui fait du conseil en optimisation et développe des solutions de visualisations/traitement des données.

Ils sont spécialisés dans le *Manufacturing* et le *Workforce*.

Bureaux à Paris, Montpellier et Hong Kong (35 employés) et des clients divers et variés par delà les montagnes :mount_fuji: .

Ils sont partenaires avec IBM et utilisent leur solveur pour leurs clients.

Toujours ramener la solution qu'on a, au problème à résoudre. Il faut aussi savoir communiquer avec des personnes qui ne vont pas forcément faire de la RO et savoir de quoi vous parlez.

### Manufacturing Optimization

**Le lot sizing par un exemple** :
[insert slides]

### Workforce optimization
[insert slides]

### Problème d'affectation des resources
[insert slides]

## Introduction au projet
### Présentation du projet: *Véhicule Routing Problem*
[insert slides]

### Modalités
[insert slides]

## Exercises
### Exo 1

$y_{ij} ∈ \{0,1\}$ : on applique la tâche $i$ à la machine $j$

**Contraintes** :

- $(1) \sum_{i=1}^{N} y_{ij}b_{ij} ≤ C_j$ , $\forall j$ => capacité maximale

- $(2) \sum_{i=1}^{N} y_{ij} = 1$ , $\forall i$ => une tâche doit être effectuée une et une seule fois

Fct. objectif Obj :

$min \sum_{i=1}^{N}\sum_{j=1}^M y_{ij}p_{ij}$ => minimiser les coûts d'affectation

#### Question 1

##### Possibilité 1

$\sum_{i=1}^{N} y_{ij}b_{ij} < C_j$ , $\forall j$ => capacité maximale

$\sum_{i=1}^{N} y_{ij} \le 1$ , $\forall i$ => une tâche doit être effectuée

$\left\{
\begin{array}{ll}
(2) => \sum_j{y_{ij}} ≤ 1 & \forall i \\
Obj => Obj + \sum_i{(1 - \sum_j{y_{ij}})l_i}
\end{array}
\right.$

Donc la fct. objectif Obj devient :
$min \sum_{i=1}^{N}\sum_{j=1}^M y_{ij}p_{ij} - \sum_{i=1}^{N}(1-\sum_{j=1})$

##### Possibilité 2
2e possibilité :
$A_i ∈ \{0, 1\}$ => est-ce que la tâche $i$ est affectée ? 1 si pas affectée

$\left\{
\begin{array}{ll}
Obj => Obj + \sum_i{A_i×l_i}\\
(2) => \sum_j{y_{ij}} = (1-A_i) & \forall i
\end{array}
\right.$

### Exo 2
#### Question 1

Sac à dos :
- $N$ objets
- Utilité $u_i$ ; poids $p_i$
- Capacité $c^{max}$

**Exploration exhaustive** :

On teste chaque possibilité =>
1. fonction récursive (on considère le fait de prendre ou pas un objet)
2. Si on prend l'objet $i$ : problème de sac à dos avec $c^{max} = c^{max} - p_i$

**Heuristique** :

On trie par $\frac{u_i}{p_i}$ décroissant : on rajoute les objets 1 par 1.