-
Transporta uzdevums priekšmetā "Transporta vadības diskrētie modeļi"
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.…
Transporta uzdevums risināšana. Mūsu uzdevumā vajag atrast optimālo plānošanu transporta tiklam ar minimālam izmaksām. Transporta tikls sastāv no ražotajiem vai noliktavas, tas skaits n = 3, un no patērētājiem, tas skits m = 4. Ar burtu i apzīmēsim kāda ražotāja numuru (indeksu), i var pieņemt vērtības no 1 līdz n. Ar burtu j apzīmēsim patērētāja kārtas numuru (j = 1, 2, 3.....m). Katram ražotajam vai noliktavai piemīt sava ražotspēja ai. Bet katram patērētājam savukārt nepieciešams noteiktais produkcijas daudzums bj. Transportējot produkciju no ražotāja patērētājam, rodas noteiktie transporta izdevumi par produkcijas vienības pārsūtīšanu no i-tā ražotāja j-tām patērētājam (apzīmēsim tos ar ci,j). Optimālajā produkcijas piegādes plānā, transporta izdevumiem jābūt vis mazākiem, kā arī visu patērētāju pieprasījumiem jābūt apmierinātiem. Tāpēc jāatrod optimālu preces piegādāšanas plānu no noliktavām (ražotājiem) pie patērētājiem, lai visas patērētāju prasības būtu apmierinātas un transportēšanas patēriņi būtu minimāli. Šo uzdevumu var atrisināt, pielietojot minimālas plūsmas atrašanas algoritmu. Secinājumi. Varu secināt, ka arī transporta nozarē datoru pielietošana atviegloja darbu, vajag tikai pareizi nokodēt programmu, un tā ļaus taupīt dažus stundas. Darbs bija izpildīts pilnībā, un paredzēti darba mērķi bija sasniegti.
