Dengeli Ulaştırma Problemini Çözümü

4 min readDec 29, 2021

Ulaştırma problemleri belirli sayıdaki kaynak noktasından belirli sayıdaki hedef noktasına en uygun maliyetle taşımanın nasıl yapılması gerektiği ile ilgili problemlerdir. Ulaştırma problemleri doğrusal programlama problemleri içerisinde ele alınır. Kendine özgü bir yapısı olduğu için ulaştırma problemlerini doğrusal programlama problemleri için kullanılan Simplex algoritması ile çözmek yerine daha pratik çözümler geliştirilmiştir. Bu çözümler iki aşamalıdır. Birinci aşamada olurlu bir başlangıç çözüm bulunur. Başlangıç çözümü için kuzeybatı köşe yöntemi, en küçük maliyetler yöntemi ve Vogel yaklaşım metodu yöntemi kullanılabilir. Başlangıç çözümü bulunan problem için en uygun çözüm atlama taşı yöntemi ile en uygun çözüm bulunabilir.

Bu yazıda örnek bir ulaştırma problemi ele alınacak ve başlangıç çözüm için Vogel yaklaşım yöntemi, en uygun çözüm için de atlama taşı yöntemi kullanılacaktır.

1.1. Örnek Problem

Ele alınan problemin 3 kaynağı ve 4 hedef noktası bulunmaktadır. Kaynak ve hedef noktaları arasındaki maliyetler ile arz ve talep miktarları maliyetler tablosunda verilmiştir.

Bu bilgilere göre problemin Vogel Yaklaşım Yöntemini kullanarak başlangıç çözümünü ve atlama taşı yöntemini kullanarak da en iyi çözümünü bulunuz.

Çözüm

Ulaştırma problemlerini çözümüne başlamadan önce problemin dengeli olup olmamasına bakılmalıdır. Dengeli ulaştırma problemlerinde toplam arz toplam talebe eşittir. Örnek problemde arz ve talep toplamları eşit olduğu için problem dengededir denilir.

VAM yöntemine göre başlangıç çözümünün belirlenmesi işleminde öncelikle tüm satır ve sütunların farkları alınır.

Alınan farklardan en yüksek olan maliyete atama yapılacağı belirtilir.

Örnekte en yüksek maliyet 2. Satırda çıkmıştır. 2. Satırdaki maliyetler 650, 800, 400 ve 600 arasındaki en düşük maliyetli hücre seçilir. Bu hücre 400 maliyeti olan hücredir. Bu hücreye yapılabilecek maksimum atama yani arz ve talepteki minimum değer kadar atama yapılır. Bu nedenle 10 birimlik atama buraya yapılır.

Bu atama ile üçüncü sütundaki hücreler kaldırılır. İlgili talep ve arz miktarları güncellenir.

Tekrar satır sütun farklarına bakılır.

En yüksek 3. Satırda çıktığı için 3. Satırın minimum hücresine yapılabilecek maksimum atama yapılır. Arz ve talep değerleri güncellenir.

Yeni durumdaki satır ve sütun farkları aşağıdaki gibi gelir.

Yeni farklara göre birinci satır seçilir. Buradaki 450 maliyetli hücreye 10 birimlik atama yapılır. Bundan sonraki atamalar sadece 2. Sütunda olacaktır. Bu nedenle en düşük maliyetli hücreye bakmadan geri kalan arz ve talepler dağıtılır.

VAM yöntemine göre başlangıç çözümü bulunmuş oldu. Çözümün geçerli olduğunun tespiti için atama miktarının satır sayısı + sütun sayısı -1 adet olduğu kontrol edilir. Buradaki atama sayısı 6 olduğu için çözüm geçerlidir denilir. Şimdi en iyi çözüm için atlama taşı yöntemine geçilir. Başlangıç çözüm tablosunu temizledikten sonra boş kalan hücreler için maliyetler hesaplanır. Eğer maliyetlerden negatif çıkan olursa buraya atama yapılır. Önce birinci satır birinci sütundaki hücreden başlanır. Hücreden atamaların olduğu hücreler köşe olacak şekilde kapalı bir döngü oluşturulur.

Birinci hücrenin maliyeti;

İkinci hücrenin maliyeti;

Üçüncü ve diğer hücreler;

Sadece d13 negatif çıktığı için bu hücreye atama yapılmalıdır denilir. Eğer birden fazla negatif maliyetli hücre çıksaydı bunlar arasından mutlak değerce yüksek olan alınırdı. Tüm maliyetlerin negatif olmayan değerler çıkması durumunda en iyi çözüme ulaşılmıştır denilirdi. Birinci satır 3. Sütun hücresine atama yapılacaktır. Atama miktarı döngüdeki negatif işaretli hücreler arasından tercih edilir. Negatif 2 ve 10 olduğu için minimum olan 2 tercih edilir. 2 değeri negatif hücrelerden çıkarılır pozitif hücrelere eklenir.

Yeni atamalara göre yeniden boşta kalan hücreler arasında maliyet hesabı yapılır. Bu hesaplara göre yeni maliyetler arasında negatif hücre olmadığı için sonuç optimumdur denilir.