Matemaatiline planeerimine 2014 S  Õppejõud A. Kivinukk
20. Transpordiülesande (TÜ) lahendamine potentsiaalide meetodil

TÜ sihifunktsioon   z = -> min    kitsendustel        kusjuures ülesanne olgu tasakaalustatud, st peab kehtima   
TÜ lahendamise algoritm:
10 Leiame lubatava alglahendi (vt § 18). Peame saama  m + n – 1  baasikomponenti  x i j ,  ülejäänud on nullid.

2 0 Transporditabelis leiame nn potentsiaalid  u i ,  v j ,  nii et baasiruutudes (st ruutudes kus on  x i j   väärtused)  aadressidega  (i, j)  kehtiks   : = c i j + u i  +  v j  = 0.  Leitud potentsiaalid kirjutatakse transporditabeli viimasesse veergu ja ritta, alustamiseks võetakse tavaliselt mingi baasiruudu v j = 0, aga ülejäänud tuleb arvutada  (vt § 19).

3 0  Nüüd arvutatakse kõikides ruutudes   = c i j + u i  +  v j ,  samm  2 0  põhjal baasiruutudes on   = 0 . 
1)	Kui     0  kõikides ruutudes, siis  STOP ja vaadeldud lahend on optimaalne (vt § 19).
2)	Kui leidub ruut, kus   <  0 , siis minnakse samm  4 0  juurde.

4 0  Olgu   = min {  |    <  0 } (st sammul 30 leitud negatiivsetest arvutuslikest veokuludest leitakse vähim ) ja fikseerime ruudu  (i 1, j 1) . 
Saab tõestada, et kui  m + n – 1  baasiruudule lisada üks ruut, siis saadud ruutude hulk sisaldab parajasti ühe tsükli (tsükkel on liikumine mööda ridu ja veerge algusruutu tagasi ; käänakupunkte, kus vahetatakse rida/veergu, nimetatakse tsükli tippudeks, vt § 19). 
Tsükli alguseks võtame ruudu (i 1, j 1)  ja tsükli tipud varustatakse  „+, - “ märkidega (need võib tabelisse märkida) järgmiselt:
(i 1, j 1)  on „+“ tipp, järgmine  (i 1, j 2)  on „-“ tipp, siis  (i 2, j 2)  jälle  „+“ tipp jne kuni eelviimane  (i t , j t)  on „+“ tipp ning lõpuks viimane  (i t, j 1)  on „-“ tipp . 
Märgake, et siin alati paarisarv tippe ja kõrvuti asuvatel tippudel on kord esimesed indeksid võrdsed, siis teised indeksid.

„-“ tippude  (i, j)  hulgast võtame selle, kus asub vähim komponent  x i j    = c  ( c  on selle vähima komponendi väärtus).

5 0  Teeme uue tabeli, kus uued arvutuslikud kulud    ja sinna märgime ka uue lubatava lahendi. Parema, optimaalsele lähema plaani saame, kui  „+“ tippude komponentidele liidame  c  ja  „-“ tippude komponentidest lahutame  c . 
Kuna  c = min x i j   , siis kõik uued arvutatud suurused  x i j   on mittenegatiivsed. 

Uus, parem veoplaan on:  
= c (tsükli esimene ruut) , s.o baasi uus element, kuna see tuli juurde, siis 
välja jäetakse esimene „-“ tipp , kuhu tekkis null (kokku peab ju olema  m + n – 1  baasikomponenti). Ülejäänud baasielemendid  x i j   jäävad endisteks, aga tsükli tippudes on need vastavalt  x i j  + / - c  

Nii tekib uus transporditabel uue lubatava lahendiga ja minnakse samm  2 0 juurde.

Samme  2 0 - 5 0   korratakse kuni saadakse optimaalne lahend , st algoritm lõpeb sammuga  2 0 . Optimaalne lahend saadakse viimasest transporditabelist.