---
jupytext:
  text_representation:
    extension: .md
    format_name: myst
    format_version: 0.13
kernelspec:
  display_name: Python 3 (ipykernel)
  language: python
  name: python3
---

+++ {"nbgrader": {"schema_version": 3, "solution": false, "grade": false, "locked": true, "task": false, "grade_id": "cell-1d52bcff7a53e531"}}

# Livraisons d'ours en peluche

::::{admonition} Exercice

Une entreprise produit des ours en peluche dans trois usines : 

 * $A_1$ en produit 300 par semaine
 * $A_2$ en produit 500 par semaine
 * $A_3$ en produit 100 par semaine
 
Trois grands magasins font une commande pour la semaine prochaine :

 * $B_1$ commande 100 ours
 * $B_2$ commande 50
 * $B_3$ commande 80
 * $B_4$ commande 300
 * $B_5$ commande 200
 
La logistique fait que chaque usine ne peut livrer que certains magasins :

 * $A_1$ peut livrer $B_1$ et $B_3$
 * $A_2$ peut livrer $B_2$ et $B_4$
 * $A_3$ peut livrer $B_3$, $B_4$, et $B_5$.

L'entreprise d'ours en peluche peut-elle assurer sa commande?

:::{admonition} Indication

Modélisez ci-dessous ce problème sous forme d'un problème de flot que
vous nommerez `F`, calculez en le flot maximal avec l'algorithme de
Ford-Fulkerson et concluez.

:::

::::

```{code-cell} ipython3
---
nbgrader:
  grade: false
  grade_id: cell-31061d257bac5b9d
  locked: true
  schema_version: 3
  solution: false
  task: false
---
from network import Network
from flow import Flow
from ford_fulkerson import maximal_flow
```

```{code-cell} ipython3
---
nbgrader:
  grade: false
  grade_id: cell-5e4d1b93a0a5b0c3
  locked: false
  schema_version: 3
  solution: true
  task: false
---
### BEGIN SOLUTION
N = Network(nodes = ["s","A1","A2","A3","B1","B2","B3","B4","B5","t"],
            edges = [("s","A1", 300), ("s", "A2", 500), ("s", "A3", 100), ("A1", "B1", 500), ("A1", "B3", 500), ("A2", "B2", 500), ("A2", "B4", 500), ("A3", "B3", 500), ("A3", "B4", 500), ("A3", "B5", 500), ("B1", "t", 100), ("B2", "t", 50), ("B3", "t", 80), ("B4", "t", 300), ("B5", "t", 200)])
F = maximal_flow(N, "s", "t")
print(F.global_value())
### END SOLUTION
```

+++ {"tags": ["answer"]}

BEGIN SOLUTION

Oui!

END SOLUTION

+++ {"tags": ["locked"], "grade_id": "cell-9b5d32fa91cacf25"}

La cellule ci-dessous vérifie la valeur du flot maximal de votre
réseau :

```{code-cell} ipython3
:tags: ["test"]
:points: 5

import hashlib
assert hashlib.md5(bytes(F.global_value())).hexdigest() == '67f022b63ce6ae0602b1c26761f4f7ee'
```

+++ {"tags": ["locked"], "grade_id": "conclusion"}

## Conclusion

+++ {"tags": ["locked"], "grade_id": "conclusion1"}

Après cet échauffement sur un petit problème synthétique, vous
aborderez dans la feuille suivante, une application sur des données
réelles.