Transporta uzdevums priekšmetā "Transporta v... / ID: 493934

Autors: Gowa (5)

Vērtējums:

Publicēts: 18.01.2011.

Valoda: Latviešu

Līmenis: Augstskolas

Literatūras saraksts: Nav

Atsauces: Nav

Izvērst priekšskatu

Darba fragmentsAizvērt

Algoritms
0.solis.
Saksim ar nulles plūsmu, t.i. visām šķautnēm plūsmas lielums ir vienāds ar 0: (e) = 0 e E.
1.solis.
Konstruējam inkrementālo grafu, kurš satur taisnas šķautnēs {e} un apgrieztas šķautnes {ē}, kurām ir pretējais virziens. Visam šķautnēm definējam garumus (kurus interpretē kā transportēšanas izmaksas). Taisna šķautne eksistē, ja (e) < β(e). Apgriezta šķautne eksistē, ja (e) > 0.
2. solis.
Pēc izmaksām atradām īsāku (lētāko) ceļu inkrementālajā grafā no avota v līdz notecei u. Ja ceļa nav, tad jau eksistējoša plūsma ir maksimālā plūsma. Citā gadjumā pāriet uz 3. soli.
3. solis.
Katrai e un ē no inkrementāla grafa atradām iespējamu pieaugumu (e):
(e) = (e) - (e), ja e ir taisna šķautne,
(ē) = (e), ja ē ir apvērsta šķautne.
= min((e); (ē))
4. solis. Plūsmas palielinājums.
Izmainām plūsmas lielumus šķautnēm, kuras pieder atrastam īsākam ceļam: ja šķautne ir taisna, tad palielinām plūsmas lielumu: (e) = (e) + ; ja šķautne ir apgriezta, tad samazinām plūsmas lielumu: (e) = (e) - .
Programma beidz savu darbu, ja 2. soli nevaram atrast ceļu.…