Elimizde arz ve talebi sağlayan bir dağıtım var. Soru şu: daha ucuzu
var mı? MODI bunu tek tek denemeden yanıtlar.
1 · u ve v değerleri
Her temel hücre (miktar taşınan hücre) için şu denklem yazılır:
ui + vj = cij
Denklem sayısı bilinmeyen sayısından bir eksiktir, bu yüzden
u₁ = 0 alınır ve kalanlar zincirleme çözülür. Temel hücre sayısının
tam m + n − 1 olması gerekmesinin sebebi budur: daha azı zinciri
koparır, daha fazlası çelişki üretir.
2 · Fırsat maliyeti
dij = cij − (ui + vj)
Temel dışı her hücre için hesaplanır. dij, o hücreye
bir birim taşımanın toplam maliyeti ne kadar değiştireceğidir.
Hepsi negatif değilse hiçbir değişiklik iyileştirme sağlamaz — çözüm
optimaldir.
3 · Kapalı döngü
En negatif d'ye sahip hücre girer. O hücreden başlayıp yalnızca
temel hücrelerden geçen, yatay/dikey dönüşümlü kapalı bir döngü
kurulur. Döngüde sırayla artı ve eksi konumlar oluşur: giren hücreye
eklenen miktar, arz ve talep dengesini bozmamak için zincirleme telafi
edilir.
θ, eksi konumlardaki en küçük miktardır — daha fazlası negatif
taşıma üretirdi. Artı konumlara θ eklenir, eksi konumlardan θ çıkarılır;
θ'yı veren hücre temelden çıkar. Temel hücre sayısı yine
m + n − 1'de kalır.
Neden simpleks değil?
Ulaştırma problemi bir doğrusal programlama modelidir ve simpleksle de
çözülebilir — bu uygulamanın simpleks sayfası
onu çözer. Ama kısıt matrisinin özel yapısı sayesinde MODI aynı işi tablo
üzerinde, çok daha az işlemle yapar. Aslında MODI, bu özel yapıya
uyarlanmış bir simpleks: u ve v dual değişkenler, dij ise
indirgenmiş maliyettir.