Livraisons d’ours en peluche

Contenu

Livraisons d’ours en peluche#

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?

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.

from network import Network
from flow import Flow
from ford_fulkerson import maximal_flow

### 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

BEGIN SOLUTION

Oui!

END SOLUTION

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

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

Conclusion#

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.

Contenu