1. Situatia reala
O companie foloseste o echipa de agenti AI specializati pentru a executa cereri ale clientilor. Fiecare agent are competente specifice si poate prelua un numar limitat de sarcini intr-un interval de 10 minute. O sarcina trebuie executata integral de un singur agent compatibil. Sistemul trebuie sa execute cat mai multe sarcini, fara sa depaseasca limitele agentilor.
Nu orice agent poate rezolva orice sarcina. O alegere locala, aparent buna, poate bloca o sarcina pe care numai un singur agent o poate rezolva.
Agenti disponibili
Cereri de executat
Competentele si cerintele sunt datele problemei. Compatibilitatea trebuie dedusa de student, nu este deja desenata ca graf.
2. Construirea modelului
Ce entitati devin noduri in reteaua de flux? Bifeaza elementele necesare.
Bifeaza individual arcele care trebuie sa existe. Unele propuneri sunt incompatibile sau au sensul gresit.
| Alege | Arc propus | Semnificatie |
|---|
Introdu capacitatea fiecarui arc selectat. Unitatea este sarcini/10 minute.
| Arc | Capacitate aleasa |
|---|
Verifica separat nodurile, arcele si capacitatile. Poti reveni la orice pas si corecta modelul.
Graful construit de student
Apar numai nodurile si arcele selectate. Arcele au sens; capacitatile sunt cele introduse de tine.
S = sursa; T = destinatia. Modelul corect foloseste arce S → agent, agent → sarcina si sarcina → T.
3. De ce este o problema de flux maxim?
Fiecare unitate de flux reprezinta o sarcina atribuita unui agent compatibil. Capacitatea arcului de la sursa la agent este numarul maxim de sarcini pe care acesta le poate prelua. Capacitatea arcului agent → sarcina este 1 daca agentul este compatibil. Capacitatea arcului sarcina → destinatie este 1, deoarece fiecare sarcina se executa o singura data.
Fluxul maxim determina numarul maxim de sarcini executabile in intervalul ales. Daca fiecare sarcina ar necesita mai multi agenti simultan sau ar avea durate diferite, acest model simplu nu ar mai fi suficient.