Majandusmatemaatika IIE eksami kordamisküsimused
7. Transpordiül võrgul on üks erijuht. Antud graafikakaarte läbilaskevõimete ja veomaksumuste korral
tuleb leida kaupluste vajadusi rahuldav veoplaan, mille maksumus on minimaalne. On välja töötatud
spetsiaalsed algoritmid, mis erinevad potentsiaalide meetodist ja arvestavad selle ül eripära.
Teoreem: Transpordiül ja tema duaalülesande lubatavad lahendid x*, u*, v* on optimaalsed tarajasti siis kui
on täidetud järgmised tingimused:
(cij ui*-vj*)xij*=0 (1)
i=1,...,m, j=1,...,n .
Kui mingis lahtris on vedu xij 0, siis potentsiaalid rahuldavad võrrandit ui+vj=cij ja avaldis (1) võrdub 0-ga.
Veo puudumisel on samuti avalid (1) täidetud. Optimaalsuseks on vaja, et potentsiaalid rahuldaksid duaalül
kitsendusi. Tähistame c^ij= ui+vj , siis need kitsendused on samaväärsed c^ij-cij 0. Viimased võrratused on
täidetud kui =max (c^ij-cij )=0, i=1,...,m , j=1,...,n
annaabi.ee 
