Transport (Ulaşım) Problemleri

Kaynaklardan hedefe minimum maliyetle taşımacılık olarak tanımlanabilir. Amaç minimum maliyet veya maksimim kârlılık ile faaliyetin gerçekleştirilmesidir.

Atama yöntemleri:

• Kuzey batı köşesi
• En küçük değerli göz
  • En küçük değerli satır
  • En küçük değerli sütun
  • En küçük değerli hücre
• VAM yöntemi

Optimizasyon yöntemleri:

• Atama taşı yöntemi
• MODI yöntemi

Atama yöntemleri

Kuzey batı köşesi

Tablonun sol üst hücresinden başlayarak tabloyu doldurmak.

Çözüm:

toplam~maliyet=5100+8200+4100+7100+5*200=4300

En küçük değerli satır yöntemi

İlk satırdan başlayarak minimum maliyetli hücrelere maksimum atama yaparak ilerliyoruz.

En küçük değerli sütun yöntemi

İlk sütundan başlayarak minimum maliyetli hücrelere maksimum atama yaparak ilerliyoruz.

En küçük değerli hücre yöntemi

Tüm tablodaki minimum maliyetli hücreden başlayarak maksimum atama yaparak ilerliyoruz.

VAM yöntemi

• Her satır ve sütun için; en düşük maliyetli iki hücre arasındaik farklar hesaplanır
• Tüm satır ve sütunlardaki en büyük farka sahip satır ya da sütun seçilir
• Seçilen satır/sütundaki en düşük maliyetli hücreye maksimum atama yapılır
• Tamamı atanmış olan satır/sütun silinir
• Geriye kalan satır/sütunlar için fark yeniden hesaplanır
  2. adımdan itibaren işlemler tekrarlanır.

Optimizasyon yöntemleri

Atama taşı yöntemi

• Bir atama yöntemi ile tablo oluşturulur.
• Yükleme yapılmamış boş hücreler için kapalı hatlar oluşturulur. Bunun için yatay ve düşey yönde ve saat yönününü tersine hareket edilir.
• Sırayla değerlere (+) ve (-) işaretler atanır.
• İşaretler dikkate alınarak hücrelerin maliyet değerleri ile ilerleme indeksleri hesaplanır.
• İlerleme indeks değerlerinin tamamı büyük veya eşit sıfır ise çözüm optumumdur. Aksi halde, negatif değerler arasından mutlak değerce en büyük olan seçilir. Bu hücrenin kapalı hattı üzerinde (-) değerlerin en küçüğü seçilerek bu değer tüm (-) değerlerden çıkarılırken tüm (+) değerlere eklenir.

 \begin{align*} &DB=DB-DA-EA-EB\\ &DC=DC-DA-EA-EB-FB-FC\\ &EC=EC-EB-FB-FC\\ &FA=FA-FB-EB-EA \end{align*}

 \begin{align*} &DB=+4-5+8-4=3\\ &DC=+3-5+8-4+7-5=4\\ &EC=+3-4+7-5=1\\ &FA=+9-7+4-8=-2\leq0 \end{align*} 

Tüm değerlerimiz pozitif değil. Bu durumda negatif değer olan FA yı seçiyoruz.

eksi olana hücrelerden (minimum olan değeri) çıkartıp, artı olan hücrelere ekliyoruz. Burada EA ve FB hücreleri eksidir. Çıkarılacak değer min(100,200) = 100 ‘dür. Bu durumda yeni değerler aşağıdaki gibi olacaktır.

Değerleri değiştirdikten sonra tablomuz

Yeniden kapalı hatlarımızı hesaplıyoruz.

 \begin{align*} &DB=DB-DA-EA-EB\\ &DC=DC-DA-FA-FC\\ &EC=EC-EA-FA-FC\\ &FB=FB-EB-EA-FA \end{align*} 

\begin{align*} &DB=+4-5+8-4=3\\ &DC=+3-5+9-5=2\\ &EC=+3-8+9-5=-1\leq0\\ &FB=+7-4+8-9=2 \end{align*}

 \begin{align*} &DB=DB-DA-FA-FC-EC-EB\\ &DC=DC-DA-FA-FC\\ &EA=EA-FA-FC-EC\\ &FB=FB-FC-EC-EB \end{align*} 

 \begin{align*} &DB=+4-5+9-5+3-4=2\\ &DC=+3-5+9-5=2\\ &EA=+8-9+5-3=1\\ &FB=+7-5+3-4=1 \end{align*} 

Tüm değerler pozitif olduğu için sonuç optimumdur.

MODI Yöntemi

• Dolu hücreleriçin R_i+K_j=c_{ij} denklemleri belirlenir.
• R_1=0 alınır.
• R_i ve K_j değerleri hesaplanır.
• Boş hücreler için ilerleme indeksi c_{ij}-R_i-K_j ile hesaplanır.
• Maksimum negatif indeks seçilerek Atlama Taşı yönteminde olduğu gibi optimum çözüm bulunana kadar devam edilir.

 \begin{align*} &R_i:~i~satırına~ait~değer\\ &K_j:~j~sütununa~ait~değer\\ &c_{ij}~:~i.~satır~ve~j.~sütundaki~hücrenin~maliyeti \end{align*} 

Örnek:

R’lerin ve K’ların hesaplanması:

 R_1+K_1=5\\ R_2+K_1=8\\ R_2+K_2=4\\ R_3+K_2=7\\ R_3+K_3=5 

 R_1=0;R_2=3;R_3=6;\\ K_1=5;K_2=1;K_3=-1; 

Boş hücrelerin ilerleme indeksini hesaplıyoruz.

 \begin{align*} &DB=4-0-1=3\\ &DC=3-0-(-1)=4\\ &EC=3-3-(-1)=1\\ &FA=9-6-5=-2\leq0\\ \end{align*} 

Bu çözüm optimum değildir. Bundan sonraki uygulayacağımız adımlar atlama taşı yöntemine benzerdir.

Yeni tablomuz aşağıdaki gibidir.

Yeniden K ve R leri hesapladık

 R_1+K_1=5\\ R_2+K_1=8\\ R_2+K_2=4\\ R_3+K_1=9\\ R_3+K_3=5 

 R_1=0;R_2=3;R_3=4;\\ K_1=5;K_2=1;K_3=1; 

 \begin{align*} &DB=4-0-1=3\\ &DC=3-0-1=2\\ &EC=3-3-1=-1\leq0\\ &FB=7-4-1=2\\ \end{align*} 

Bu adımda da çözümümüz optimum değildir.

 R_1+K_1=5\\ R_2+K_2=4\\ R_2+K_3=3\\ R_3+K_1=9\\ R_3+K_3=5 

 R_1=0;R_2=2;R_3=4;\\ K_1=5;K_2=2;K_3=1; 

 \begin{align*} &DB=4-0-2=2\\ &DC=3-0-1=2\\ &EA=8-2-5=1\\ &FB=7-4-2=1\\ \end{align*} 

 Toplam~maliyet:5100+4200+3100+9200+5*100=3900