maxFlow
Description
L'action `maxFlow` calcule le flot maximum (maximum flow) d'un graphe . Imaginez que vous soyez un plombier essayant de faire passer le maximum d'eau dans un réseau de tuyaux de tailles différentes, ou un architecte réseau optimisant le trafic de données... c'est exactement ce que fait cette action ! Elle détermine la quantité maximale de 'flux' qui peut voyager d'un nœud source vers un nœud cible (sinkDans un réseau, un sink (puits) est un nœud de destination finale qui absorbe le flux. Il possède une demande nette positive et aucun arc de sortie dans les modèles de flux optimisés.) sans dépasser la capacité (la limite) des liens.
Paramètres Clés
| Nom du paramètre | Description |
|---|---|
| links | Spécifie la table de données d'entrée contenant les informations sur les liens (les 'tuyaux') du graphe. |
| source | Spécifie le nœud de départ (la source) pour les calculs du flot maximum. |
| sink | Spécifie le nœud d'arrivée (la cible ou le puits) pour les calculs du flot maximum. |
| linksVar | Spécifie les noms des variables pour la table des liens (par exemple `from` et `to` pour les extrémités du lien, `upper` pour la capacité maximale, et `lower` pour la capacité minimale). |
| direction | Indique si le graphe d'entrée est dirigé (`DIRECTED`) ou non dirigé (`UNDIRECTED`). |
| outLinks | Spécifie la table de sortie qui contiendra les informations sur les liens ainsi que le flux calculé pour chaque lien. |
| logLevel | Contrôle la quantité d'informations affichée dans le journal SAS (`NONE`, `BASIC`, `MODERATE`, `AGGRESSIVE`). |
Préparation des données
Création d'un réseau de transport (Plomberie de base)
Nous allons créer une table représentant un réseau de liens avec une capacité maximale (`upper`) pour chaque tronçon. Le flux ira de 'S' (Source) vers 'T' (Target/Sink).
| 1 | DATA mycas.LinkSetIn; |
| 2 | LENGTH from $2 to $2; |
| 3 | INPUT from $ to $ upper; |
| 4 | DATALINES; |
| 5 | S A 3 |
| 6 | S B 2 |
| 7 | A B 1 |
| 8 | A T 3 |
| 9 | B T 3 |
| 10 | ; |
| 11 | RUN; |
Exemples d'utilisation
Calcul du flot maximum simple
Dans cet exemple, nous calculons le flux maximal possible entre la source S et le puits T. L'action s'assure qu'aucun lien ne dépasse sa limite `upper`.
| 1 | PROC CAS; |
| 2 | optNetwork.maxFlow / |
| 3 | direction="DIRECTED" |
| 4 | links={name="LinkSetIn"} |
| 5 | linksVar={from="from", to="to", upper="upper"} |
| 6 | SOURCE="S" |
| 7 | sink="T" |
| 8 | outLinks={name="LinkSetOut", replace=true}; |
| 9 | RUN; |
| 10 | QUIT; |
Résultat Attendu :
Flot maximum avec limites inférieures (lower bounds) et journalisation poussée
Un cas plus avancé %%https://go.documentation.sas.com/doc/en/pgmsascdc/v_069/casactnopt/casactnopt_optnetwork_examples.htm%% où nous définissons non seulement une capacité maximale (`upper`), mais aussi une obligation de passage minimale (`lower`). On demande également un niveau de log agressif pour observer le comportement de l'algorithme sous le capot. Idéal pour les ingénieurs réseaux les plus exigeants !
| 1 | DATA mycas.LinkSetInAdv; |
| 2 | LENGTH from $2 to $2; |
| 3 | INPUT from $ to $ lower upper; |
| 4 | DATALINES; |
| 5 | S A 0 5 |
| 6 | S B 1 2 |
| 7 | A B 0 1 |
| 8 | A T 0 4 |
| 9 | B T 0 3 |
| 10 | ; |
| 11 | RUN; |
| 12 | PROC CAS; |
| 13 | optNetwork.maxFlow / |
| 14 | direction="DIRECTED" |
| 15 | links={name="LinkSetInAdv"} |
| 16 | linksVar={from="from", to="to", lower="lower", upper="upper"} |
| 17 | SOURCE="S" |
| 18 | sink="T" |
| 19 | logLevel="AGGRESSIVE" |
| 20 | outLinks={name="LinkSetOutAdv", replace=true} |
| 21 | outNodes={name="NodeSetOutAdv", replace=true}; |
| 22 | RUN; |
| 23 | QUIT; |