Repetăm ​​această operațiune până când scurgerea este marcată. Dacă fluxul rămâne neetichetat, atunci debitul găsit este maxim, iar setul de arce care leagă vârfurile marcate cu cele nemarcate formează o tăietură minimă.

3. Lăsați stocul să fie etichetat (j+, ε(t)), Apoi f(j,t)înlocui cu f(j,t)+ε(t). Dacă stocul este marcat (j-, ε(t)), Acea f(j,t)înlocui cu f(j,t)-ε(t). Să mergem sus j. Dacă j are un semn (i+, ε(j)), apoi înlocuim f(i,j) pe f(i,j)+ε(t), si daca (i-, ε(j)), f(j,i)înlocui cu f(j,i)-ε(t). Să mergem sus i. Repetăm ​​această operație până ajungem la sursă s. Schimbarea debitului se oprește, toate marcajele sunt șterse și treceți la pasul 2

EXEMPLU 3.14.

M 4K

SARCINĂ. Găsiți cel mai mare flux din rețea

ALGORITM

Să notăm vârful s= x 0 . Toate celelalte sunt x i.

Etapa 1.

1. Alegeți orice cale ale cărei arce nu sunt saturate.

2. Creștem cantitatea de curgere de-a lungul acestei căi cu una până când nu există un arc saturat în ea.

Continuăm procesul de creștere a debitului până când se construiește debitul complet, adică. orice cale va conține cel puțin un arc saturat.

Etapa 2.

2. Dacă х i este deja un vârf marcat, atunci se marchează (+i) toate vârfurile neetichetate la care merg arcele nesaturate de la х i, iar cu indicele (–i) toate vârfurile nemarcate de la care merg arcele cu flux diferit de zero. la х i.

3. Dacă în urma acestui proces este marcat un vârf t, apoi între sȘi t există o cale ale cărei toate vârfurile sunt marcate cu numerele vârfurilor anterioare. Creștem debitul în toate arcurile acestei căi cu unul dacă, atunci când trecem de la s La t orientarea arcului coincide cu direcția de mișcare și se reduce cu unu dacă arcul are orientarea opusă. Să trecem la pasul 1.

4. Când vârful t este imposibil de marcat procesul este terminat și fluxul rezultat este cel mai mare flux al rețelei.

NOTĂ. Puteți trece la etapa 2 fără a finaliza prima etapă (vezi exemplul 3.16).

EXEMPLU 3.15.

9

SOLUŢIE:

S-a găsit un flux complet pe o anumită rețea de transport. Arcurile saturate sunt evidențiate

În această rețea, puteți marca și vârful final, iar rezultatul marcajului va fi același. Schimbând fluxul, obținem o rețea în care este imposibil să se marcheze vârful final, deci debitul din acesta este cel mai mare și egal cu 10.

EXEMPLU 3.16.

8 2 1

Un flux incomplet a fost găsit pe o anumită rețea de transport

Să marchem rețeaua și să creștem fluxul în ea conform algoritmului. Primim

În această rețea, puteți marca și vârful final, iar rezultatul marcajului va fi același. Schimbând fluxul, obținem o rețea în care este imposibil să se marcheze vârful final, deci debitul din acesta este cel mai mare și egal cu 6.

Secțiunea IV. PROGRAMARE DINAMICĂ.

Programarea dinamică este utilizată pentru a găsi soluții optime în mai multe etape. De exemplu, planificarea pe termen lung pentru înlocuirea echipamentelor; activităţile industriei de-a lungul unui număr de ani. Utilizează principiul optimității, conform căruia orice soluție parțială nouă trebuie să fie optimă în raport cu starea atinsă.

Este mai bine să rezolvi o problemă simplă de mai multe ori decât să rezolvi una dificilă o singură dată.

PROBLEMA 1. Despre traseul cel mai avantajos între două puncte.

Este necesară construirea unei căi care să leagă două puncte A și B, dintre care al doilea se află la nord-est de primul. Pentru simplitate, să presupunem că trasarea unei căi constă dintr-o serie de pași, iar la fiecare pas ne putem deplasa fie spre nord, fie spre est. Apoi orice cale este o linie întreruptă în trepte, ale cărei segmente sunt paralele cu una dintre axele de coordonate. Costurile de construire a fiecăreia dintre aceste secțiuni sunt cunoscute.

EXEMPLU 4.1. Găsiți calea minimă de la A la B.

Ultimul pas este realizarea T.V. Înainte de ultimul pas, am putea fi în puncte de unde am putea ajunge la T.V. într-un singur pas. Există două astfel de puncte (sistemul ar putea fi într-una din două stări). Pentru fiecare dintre ele, există o singură opțiune pentru a ajunge la t.V: pentru unul - deplasați-vă spre est; pentru celălalt – spre nord. Să scriem costurile 4 și 3 în fiecare caz.

4

Acum să optimizăm penultimul pas. După pasul anterior, am putea ajunge în unul dintre cele trei puncte: C 1, C 2, C 3.

Pentru punctul C 1, există un singur control (să-l marchem cu o săgeată) - deplasați-vă spre est, iar costurile vor fi 2 (la acest pas) + 4 (la următorul pas) = ​​6. În mod similar, pentru articolul C 3 costurile vor fi 2+3=5. Pentru t.C 2 există două comenzi: mergi spre est sau spre nord. În primul caz, costurile vor fi 3+3=6, iar în al doilea caz – 1+4=5. Aceasta înseamnă că controlul optim condiționat este să mergi spre nord. Să-l marchem cu o săgeată și să introducem costurile corespunzătoare.

Răspuns: x 1 =1; x 3 =0; x 3 =4; W=3,5

ALGORITM GENERALIZAT

1. Descrieți sistemul. Adică, aflați ce parametri caracterizează starea sistemului controlat înainte de fiecare pas. Este important să puteți seta sarcina corect și „modest”, fără a o supraîncărca cu detalii inutile, simplificând pe cât posibil descrierea sistemului controlat.

2. Împărțiți operația în pași (etape). Toate restricțiile rezonabile impuse conducerii trebuie luate în considerare aici. Pasul trebuie să fie suficient de mic, astfel încât procedura de optimizare a controlului pasului să fie destul de simplă; iar pasul, în același timp, să nu fie prea mic pentru a nu face calcule inutile care complică procedura de găsire a soluției optime, dar să nu conducă la o modificare semnificativă a optimului funcției obiectiv.

3. Aflați setul de comenzi de pas x i pentru fiecare pas și restricțiile impuse acestora.

4. Determinați ce câștig aduce controlul x i la pasul i, dacă înainte de aceasta sistemul era în starea S, adică. notează funcțiile de plată:

w i =f i (S, x i)

5. Determinați cum se modifică starea sistemului sub influența controlului x i la prima etapă, adică. scrieți funcții de schimbare a stării.

S / =φ i (S, x i)

6. Notați principala ecuație de programare dinamică recurentă, exprimând câștigul optim condiționat printr-o funcție deja cunoscută

W i (S)= max(f i (S, x i)+W i+1 (φ i (S, x i)))

7. Efectuați optimizarea condiționată a ultimului pas, făcând diverse ipoteze despre modul în care s-a încheiat penultimul pas și pentru fiecare dintre aceste ipoteze găsiți controlul condiționat (selectat în funcție de condiția ca pasul să se încheie cu ceva) optim la ultimul pas.

W m (S)= max(f m (S, x m))

8. Efectuați optimizarea condiționată, începând de la penultimul pas și terminând cu primul pas (backing back).

9. Efectuați optimizarea controlului necondiționat, „citind” recomandările corespunzătoare la fiecare pas: luați controlul optim găsit în primul pas și schimbați starea sistemului, găsiți controlul optim pentru starea găsită în a doua etapă etc. până la ultimul pas.

PRINCIPIUL OPTIMALITATII. Oricare ar fi starea sistemului înainte de pasul următor, este necesar să alegeți controlul la acest pas, astfel încât câștigul la acest pas plus câștigul optim la toate etapele ulterioare să fie maxim.

Principiul programării dinamice nu presupune ca fiecare pas să fie optimizat separat, independent de ceilalți. Ce rost are să alegem un control a cărui eficacitate este maximă la un anumit pas, dacă acest pas ne va lipsi de posibilitatea de a câștiga bine la pașii ulterioare?

În practică, există cazuri când o operațiune trebuie să fie planificată pentru o perioadă de timp nedefinită. Modelul pentru un astfel de caz este un proces controlat în pași infiniti, în care toți pașii sunt egali. Aici funcția câștigătoare și funcția de schimbare a stării nu depind de numărul pasului.

Secțiunea V. MODELARE SIMULARE

Rezolvați problema găsirii debitului maxim într-o rețea de transport folosind algoritmul Ford-Fulkerson și construiți o secțiune de rețea S.
Date inițiale:
Având în vedere o rețea S(X,U)
- sursa rețelei; - dren de rețea, unde ∈X; ∈X.
Valorile capacității arcului sunt specificate în direcția de orientare a arcului: de la indicele i la indicele j.

r = 39; r = 44; r = 33; r = 53; r = 10;
r = 18; r = 95; r = 16; r = 23; r = 61;
r = 81; r = 71; r = 25; r = 15; r = 20

1. Setați un debit zero pe rețea (pe toate arcurile, valoarea debitului este 0). Debitul zero este debitul inițial permis în rețea. Valoarea debitului pe fiecare arc va fi indicată în afara capacității arcului.). Valoarea debitului egală cu „0” nu este specificată.
2. Selectați în rețea (arbitrar) o cale care duce de la vârful x0 la vârful x7:
X0-X1-X4-X6-X7
3. Găsiți și crește debitul cu această cantitate. Edge X1-X4 este marcat ca considerat.


4. Alegeți o altă cale, de exemplu: X0-X2-X5-X7, găsiți și crește debitul cu această cantitate. Edge X0-X2 este marcat ca considerat.


5. Alegeți o altă cale, de exemplu: X0-X3-X2-X5-X7, găsiți și măriți debitul cu această cantitate. Edge X3-X2 este marcat ca considerat.


6. Nu mai există căi de la X0 la X7, să însumăm creșterea debitului: 25+10+20=55.
Concluzie: debitul maxim este de 55.

2) Construiți o secțiune a rețelei S.
Procedura de „marcare a vârfurilor”.
Stare inițială: toate nodurile sunt neetichetate.
Vârfului X0 i se atribuie o etichetă. Toate vârfurile pentru care arcul nu este saturat li se atribuie semne (cercuri roșii)


Definim arce tăiate minime: acestea sunt arce ale căror începuturi sunt la vârfuri marcate și ale căror sfârșite sunt la vârfuri neetichetate.
Acestea sunt arcurile:
Astfel, tăierea minimă a acestei rețele
Calculul valorii debitului maxim

La planificarea distribuției raționale a produselor în rețeaua de distribuție, este necesară coordonarea capacității canalului cu nevoile clienților și cu capacitatea fabricii de producție. Această clasă de probleme se rezolvă prin găsirea debitului maxim.

Să considerăm o rețea de distribuție (Fig. 4.21), în care punctele 0 (intrarea, de exemplu, depozitul unui producător de produse finite) și P (ieșire, centre de distribuție, depozite ale organizațiilor de comerț cu ridicata și cu amănuntul, consumatori) și fiecare arc (segment) puncte de legătură i Și j, se asociaza numarul dij > 0, numit debitului arcuri. Valoarea debitului caracterizează cantitatea maximă admisă de flux de material care poate trece de-a lungul arcului corespunzător pe unitatea de timp.

Orez. 4.21.

Cantitatea de produse care trec de-a lungul unui arc de la i inainte de j , îl vom numi un flux de-a lungul arcului ( i ,j ) și notat cu . Este evident că

Dacă luăm în considerare că întregul flux de material care intră în punctul intermediar al rețelei trebuie să iasă complet din acesta, obținem

Din cerința naturală de egalitate a fluxurilor la intrare și la ieșire avem

Vom numi valoarea lui Z valoarea debitului în rețea și vom pune problema maximizării Z în condițiile de mai sus.

Găsirea debitului maxim se reduce la găsirea debitului tăieturii minime.

Să luăm în considerare un algoritm de căutare universal sub formă de matrice.

Etapa inițială a algoritmului constă în construirea unei matrice D 0, în care sunt introduse valorile de debit (pentru un arc neorientat luăm valorile simetrice ale elementelor matricei).

Principalii pași ai algoritmului sunt găsirea unei anumite căi și corectarea fluxului de-a lungul acestei căi.

Când găsim o cale, folosim un proces de marcare. Marcam cu simbolul * rândul și coloana zero a matricei (intrare în rețea). În a 0-a linie căutăm , marcați coloanele corespunzătoare cu indici

și mutați etichetele coloanelor pe rânduri. Apoi luăm al-lea rând marcat, căutăm în el o coloană nemarcată cu , la care potrivim etichetele de index

Transferăm etichetele coloanei pe rânduri și continuăm acest proces până când este marcată a n-a coloană.

Apoi, folosind indici, aflăm calea care a condus la vârful η-lea folosind indici și reducem capacitatea arcelor drumului (elementele matricei) cu V n și crește elementele simetrice cu aceeași cantitate.

Această procedură continuă până la marcare n -topurile nu vor deveni imposibile.

Fluxul maxim poate fi găsit prin scăderea din matricea originală D 0, obţinută după corectarea de mai sus a matricei de capacitate:

Exemplul 4.4

Producția este situată în Moscova. Pentru a distribui produse, compania atrage intermediari care lucrează cu compania prin centre de distribuție la diferite niveluri. În partea europeană a Rusiei există o întreprindere angro 1, deservită de un centru de distribuție central. Întreprinderea de vânzare cu ridicata 2 operează în străinătate apropiată (Ucraina, Belarus) și este deservită de un centru de distribuție regional. Compania are proprii clienți pe piața locală (Moscova și regiunea Moscovei) - retaileri care primesc produse din centrul de distribuție al orașului. Centrele de distribuție regionale și orașe sunt reaprovizionate din centrul de distribuție central.

Să evidențiem un fragment al rețelei de distribuție:

• depozitul de produse finite al unei întreprinderi de producție;
• centru central de distribuție;
• centru regional de distribuție;
• centrul de distribuție al orașului;
• două întreprinderi angro;
• punct de vânzare cu amănuntul deținut de companie;
• consumatori.

Orez. 4.22.

Să desemnăm fiecare legătură a rețelei de distribuție cu un număr și să punem capacitatea deasupra arcurilor. Capacitatea de transfer, în funcție de tipul de legătură, poate fi exprimată în termeni de volumul capacității de producție, nevoia (cererea) planificată a consumatorilor și capacitatea pieței.

Graficul rețelei de distribuție a produselor este prezentat în Fig. 4.23. Să construim o matrice D 0, în care introducem valorile capacităților de debit ale legăturilor rețelei de distribuție (Fig. 4.24).

Orez. 4.23.

Orez. 4.24.

Din rândul zero marchem vârfurile (rândurile-coloane) 1, 2 și 3 cu indici μ = 0 și V, egal cu 30,10 și 10.

Din linia marcată 1, marcați vârfurile 4 și 5 cu indici μ = 1 și V4 = min (30,15) = 15, V5 = min (30,10) = 10.

Din linia 3 se marchează vârful 6 și, în final, din linia 4 – vârful 7 (Fig. 4.25).

Orez. 4.25.

Mergând înapoi de-a lungul μ găsim calea: până la vârful 7 de la 4, până la vârful 4 de la 1, până la vârful 1 de la 0; elemente de reglare D 0 pe valoarea debitului V7 = 15.

Următorul pas oferă o cale cu flux 5 (Fig. 4.26).

Orez. 4.26.

Următorul pas oferă rezultatul prezentat în Fig. 4.27.

Orez. 4.27.

Nu mai este posibilă marcarea. De aici obținem matricea debitului maxim (Fig. 4.28).

Orez. 4.28.

Ca urmare a aplicării algoritmului de găsire a debitului maxim în rețea, rezultatele prezentate în Fig. 4.29. Perechile de numere din paranteze prezentate pe arcele graficului indică debitul maxim al arcului și volumul recomandat de bunuri furnizate rețelei.

Algoritm pentru calcularea debitului maxim în rețele

Iterare. PASUL 2. Selectarea rutelor independente în rețea și determinarea fluxurilor în acestea. La fel de M 1 ia traseul( v și =V 1 , V 2 , V 5 , v s =V 7), considerat în exemplul 1. Pentru el A(M 1) = 10.

De asemenea, este ușor să izolați independent M 1 traseu M 2 = (v și =V 1 , V 3 , V 6 , v s =V 7). Să calculăm debitul maxim pentru acesta și să ajustăm debitul arcurilor: A(M 2)= min{d 13 ,d 36 ,d 67 } = min{45, 40, 30} = 30. d 13¢ =d 13 - 30 = 15,d 36 ¢ =d 36 - 30 = 10,d 67 ¢ =d 67 - 30 = 0.

II iterație. PASUL 2. Ca singura cale independentă pe care o luăm M 3 = (v și =V 1 , V 4 , V 2 , V 5 , v s =V 7). Pentru el:

A(M 3)= min{d 14 ,d 42 ,d 25 ,d 57 } = min{15, 10, 10, 15} = 10.

d 14¢ =d 14 - 10 = 5,d 42¢ =d 42 - 10 = 0,d 25 ¢ =d 25 - 10 = 0,d 57 ¢ =d 57 - 10 = 5.

PASUL 4. Corecția rețelei. Debit maxim A(M 3) scade din arcurile traseului M 13 . Rezultatul este dat în Fig. 1.16 b.

Dacă în rețea sunt specificate mai multe surse, aceasta se completează prin introducerea unei noi surse comune, care este conectată la sursele originale prin arce cu capacitate nelimitată. Apoi problema este rezolvată folosind algoritmul obișnuit. Fluxurile necesare prin sursele originale vor fi fluxuri de-a lungul arcelor nou adăugate care intră în ele dintr-o nouă sursă comună. Faceți același lucru dacă în rețea există mai multe scurgeri.

Planificarea rețelei

Orice sarcină de proiectare sau construcție a unui obiect destul de complex ( proiect) poate fi împărțit într-un număr de etape componente mai mici. Timpul întregului proiect depinde de alegerea corectă a secvenței acestor pași.

Întreaga gamă de acțiuni pentru implementarea proiectului este prezentată ca un set evenimenteȘi lucrări. Evenimentele sunt numite etape individuale ale unui proiect. Munca este procesul de finalizare. Întregul complex de evenimente și lucrări necesare finalizării proiectului poate fi reprezentat sub forma unei rețele bipolare G =({v și, v z} , V, X), în care:

si tot evenimente marcat de un set de vârfuri V, evidenţiate printre ei eveniment inițial v și(începutul lucrului) și eveniment final v z(finalizarea întregului proiect), definesc vârfurile interne ale rețelei evenimente intermediare- etapele care trebuie parcurse pe parcursul implementării proiectului,

b) totul muncă sunt indicate prin arce care leagă perechi de evenimente - vârfuri.

Reprezentarea grafică a acestei rețele se numește diagrama rețelei. Pentru a indica secvența acțiunilor, introduceți și diagrama de rețea opere fictive, care nu sunt asociate cu efectuarea niciunei acțiuni. Lucrările corespunzătoare sunt indicate prin arce întrerupte.

Ca exemplu, luați în considerare organizarea unei anumite producții. Proiectul necesită următoarele lucrări:

I) cercetare de marketing, II) cercetare pre-proiectare a echipamentelor, III) organizarea unei rețele de vânzare, IV) realizarea unei campanii de publicitate, V) elaborarea specificațiilor tehnice pentru echipamente de producție, VI) elaborarea documentației tehnice pentru spațiile de producție și comunicații, VII) achiziționarea de echipamente standard, VIII) proiectarea și fabricarea echipamentelor nestandard, IX) construcția instalațiilor de producție și instalarea comunicațiilor, X) instalarea echipamentelor standard, XI) instalarea echipamentelor nestandard, XII) punerea în funcțiune.

Aceste lucrări le vom nota în diagrama de rețea prin arce cu numere corespunzătoare.

Evenimentele din acest proiect vor fi următoarele:

1) începerea lucrărilor (eveniment inițial), 2) finalizarea cercetării de marketing, 3) finalizarea cercetării pre-proiect, 4) organizarea unei rețele de vânzări, 5) organizarea unei campanii de publicitate, 6) pregătirea specificațiilor tehnice pentru producție echipamente, 7) finalizarea elaborării documentației tehnice pentru spațiile de producție și comunicații, 8) finalizarea achiziției de echipamente standard, 9) finalizarea proiectării și fabricației echipamentelor nestandardizate, 10) finalizarea construcției instalațiilor de producție și instalarea comunicațiilor, 11) finalizarea lucrărilor de instalare a echipamentelor și punerea în funcțiune,

12) finalizarea proiectului (eveniment final).

Asociem nodurile cu numere corespunzătoare evenimentelor. Programul rețelei pentru proiect este prezentat în Fig. 1.17:

Fig.1.17. Programul rețelei proiectului