300 Exemple

Problemă de debit maxim

Maximum Flow Problem

Formulați modelul | Încercare și eroare | Rezolvați modelul





Folosiți soluția în excela pentru a găsi debit maxim de la nodul S la nodul T într-o rețea direcționată. Punctele dintr-o rețea se numesc noduri (S, A, B, C, D, E și T). Liniile dintr-o rețea se numesc arce (SA, SB, SC, AC etc.).

Formulați modelul

Modelul pe care îl vom rezolva arată după cum urmează în Excel.





Problemă de debit maxim în Excel

1. Pentru a formula acest lucru problema debitului maxim , răspundeți la următoarele trei întrebări.



A. Care sunt deciziile care trebuie luate? Pentru această problemă, avem nevoie de Excel pentru a găsi fluxul pe fiecare arc. De exemplu, dacă fluxul pe SB este 2, celula D5 este egală cu 2.

b. Care sunt constrângerile asupra acestor decizii? Fluxul net (Flow Out - Flow In) al nodului A, B, C, D și E ar trebui să fie egal cu 0. Cu alte cuvinte, Flow Out = Flow In. De asemenea, fiecare arc are o capacitate fixă. Debitul pe fiecare arc ar trebui să fie mai mic decât această capacitate.

c. Care este măsura generală a performanței pentru aceste decizii? Măsura generală a performanței este debitul maxim, astfel încât obiectivul este de a maximiza această cantitate. Debitul maxim este egal cu Debitul din nodul S.

2. Pentru a face modelul mai ușor de înțeles, creați următoarele intervale denumite .

Nume domeniu Celulele
Din B4: B15
La C4: C15
curgere D4: D15
Capacitate F4: F15
Cerere de aprovizionare K5: K9
MaximumFlow D17

3. Introduceți următoarele funcții.

Inserați funcții

Explicație: SUMIF funcțiile calculează debitul net al fiecărui nod. Pentru nodul A, prima funcție SUMIF însumează valorile din coloana Flow cu un „A” în coloana From (Flow Out). A doua funcție SUMIF însumează valorile din coloana Flow cu un „A” în coloana To (Flow In). Debitul maxim este egal cu valoarea din celula I4, care este debitul din nodul S. Deoarece nodul A, B, C, D și E au un debit net de 0, debitul din nodul S va fi egal cu debitul In al nodului T.

Încercare și eroare

Cu această formulare, devine ușor să analizăm orice soluție de încercare.

1. De exemplu, calea SADT cu un flux de 2. Calea SCT cu un flux de 4. Calea SBET cu un flux de 2. Aceste căi dau un flux total de 8.

Soluție de încercare

cum se introduce o casetă derulantă în Excel

Nu este necesar să utilizați încercarea și eroarea. Vom descrie în continuare cum Excel Solver poate fi folosit pentru a găsi rapid soluția optimă.

Rezolvați modelul

Pentru a găsi soluția optimă, executați pașii următori.

1. În fila Date, în grupul Analize, faceți clic pe Solver.

Faceți clic pe Solver

Notă: nu găsiți butonul Solver? Faceți clic aici pentru a încărca fișierul Supliment de rezolvare .

Introduceți parametrii soluției (citiți mai departe). Rezultatul ar trebui să fie în concordanță cu imaginea de mai jos.

Parametri Solver

Aveți de ales să tastați numele intervalului sau să faceți clic pe celulele din foaia de calcul.

2. Introduceți MaximumFlow pentru obiectiv.

3. Faceți clic pe Max.

4. Introduceți Fluxul pentru schimbarea celulelor variabile.

5. Faceți clic pe Adăugare pentru a introduce următoarea constrângere.

Constrângerea fluxului net

6. Faceți clic pe Adăugare pentru a introduce următoarea constrângere.

Constrângerea capacității

7. Bifați „Faceți ca variabilele fără restricții să nu fie negative” și selectați „Simplex LP”.

8. În cele din urmă, faceți clic pe Rezolvare.

Rezultat:

Rezultate Solver

Soluția optimă:

Rezultatul problemei debitului maxim

Concluzie: calea SADT cu un flux de 2. Calea SCT cu un flux de 4. Calea SBET cu un flux de 2. Calea SCET cu un flux de 2. Calea SACET cu un flux de 1. Calea SACDT cu un debit de 1. Aceste căi dau un debit maxim de 12.

5/7 Finalizat! Aflați mai multe despre solver>
Accesați capitolul următor: ToolPak de analiză



^