Ulaştırma ve Atama Modelleri

Ulaştırma problemi, belirlenmiş kaynaklardan belirli sayıdaki varış noktalarına yapılacak taşımanın toplam maliyetinin en küçüklemesini amaçlayan doğrusal bir eniyileme problemidir. En iyi çözümde, varış noktalarındaki taleplerin tümü karşılanmalı ve kaynaktakilerin tümü gönderilmiş olmalıdır.

Gönderilecek miktarlar ancak sıfırdan büyük veya sıfıra eşit (sıfır olmaası gönderinin olmadığı manasına gelir) olabileceği için karar değişkenlerine ait değerler negatif olamaz. Bu durum modelin negatif olmama koşuluna karşılık gelmektedir. Diğer kısıtlar, varış noktalarındaki taleplerinin tümünün karşılanmasına ve kaynak noktalarındaki nesnelerinin tümünün taşınmasına ilişkin kısıtlardır.

Gönderimler yapıldığında toplam talep tam olarak karşılanıyor ve toplam arz tamamen tükeniyorsa toplam arz toplam talebe eşittir:

Bu yapıya dengelenmiş ulaştırma modeli adı verili

En az bir temel değişkenin sıfır değeri aldığı çözüme dejenere (veya, bozulmuş) temel uygun çözüm adı verilir.

Modelin genel formunda, m + n adet kısıtlayıcıya ait denklemler lineer bağımlıdır: En az bir denklem, diğer denklemlerin doğrusal bir bileşimi olarak ifade edilebilir. Dengelenmiş ulaştırma modelinin lineer cebirsel bir özelliği, bağımsız denklem sayısının m + n – 1 olmasıdır.
Bu sebeple, böyle bir modelin temel uygun çözümü m + n – 1 adet temel değişken içerir. 3 adet kaynak ve 4 adet varış noktası bulunan bir modelin en iyi çözümünde, 6 (3 + 4 – 1) adet değer atanmış karar değişkeni bulunmalıdır

1. Başlangıç için bir temel uygun çözüm belirlenir,
2. Simpleks yöntemi uyarınca belirlenen temel uygun çözüm için eniyilik sınaması yapılır. Eldeki çözüm, en iyi çözüm ise ardıştırma işlemi bitirilir; en iyi çözüm değilse bir sonraki adıma geçilir.
3. Ardıştırma işlemiyle bir sonraki temel uygun çözüme geçilir ve 2. adıma geri dönülür.

1. Kuzey-batı köşe yöntemi,
2. En küçük maliyet yöntemi,
3. Vogel’in yakınsama (VAM) yöntemi.

Bu yönteme göre ilk temel değişken, ulaştırma tablosunun sol-üst köşesinde yer alan değişkendir. Bu değişkene atanacak değer, ilk satır ve sütuna denk gelen arz ve talep arasından küçük olanıdır. Böylece, seçilen değişkene alabileceği en büyük değer atanmış olmaktadır. Atama yapıldıktan sonra, atama yapılan satırdaki arz tamamen tüketilemediyse, atama yapılan değişkenin sağındakine geçilir ve atama yapılır. İlk satırın ikinci sütunundaki bu değişkene yapılacak atamanın yöntemi ilkiyle aynıdır. Eğer yapılan ilk atamada, atama yapılan sütundaki talep tamamen tüketilemediyse, atama yapılan değişkenin altındakine geçilir ve atama yapılır. İlk sütunun ikinci satırındaki bu değişkene yapılacak atamanın yöntemi ilkiyle aynıdır. Bu süreç, sağ alt köşede atanacak bir şey kalmayana dek sürdürülür. Bu yöntem en basit, fakat en düşük performanslı başlangıç yöntemidir

Bu yöntemde, en iyi çözüme yakınsak bir başlangıç temel uygun çözümü bulmak adına değişkenlerin maliyetleri kıyaslanır. Kuzey-batı köşe yönteminden farklı olarak, en küçük maliyet yönteminde en düşük ulaştırma maliyetine sahip güzergâh seçilerek başlanır. Bu yöntemde, en düşük maliyetli birden çok güzergâh varsa, aralarından herhangi biri seçilebilmektedir. Seçilen değişkene atanacak değer, satır ve sütun sonu değerleri arasından küçük olanıdır. Bir değişkene değer ataması yapıldıktan sonra, atanan değer ilgili satır ve sütun sonu değerlerinden çıkarılır. Değişkene atanan değer, satırdaki arzı veya sütundaki talebi tümüyle karşıladığında, ilgili satır veya sütun boylu boyunca renkli boyanır. Renkli boyanan satır ve sütunlar, bir sonraki değer atamasında değerlendirme dışı bırakılır. Değer en küçük maliyetli değişkenlere yapılan atama işlemi, en sona kalan satır veya sütun değerleri tümüyle karşılanana kadar sürdürülür.

Bu yöntemde, doğrudan doğruya ulaşım maliyetlerini dikkate almak yerine, ceza
maliyeti kavramı türetilmiştir. VAM yönteminde, atama yapılacak değişkenin seçimi için öncelikle her satırın veya sütunun ceza maliyeti hesaplanmaktadır. Bir satırın ceza maliyeti, aynı satırdaki en düşük iki ulaştırma maliyeti arasındaki farktır. Aynı kural sütunlar için de geçerlidir: bir sütunun ceza maliyeti, aynı
sütundaki en düşük iki ulaştırma maliyeti arasındaki farktır.
Atama yapılacak değişkenin seçimi için satırlara ve sütunlara ait ceza puanları arasından en büyük olan satır veya sütun belirlenir. Sonrasında, belirlenen satır (veya duruma göre, sütun) elemanlarından en düşük ulaştırma maliyetine sahip olan karar değişkeni seçilir. Eğer aynı ceza maliyetine sahip birden çok satır
veya sütun varsa, bunların arasından biri keyfî olarak belirlenebilir. Benzer koşul seçilen satır veya sütun elemanlarının ulaştırma maliyetleri için de geçerlidir: aynı ulaştırma maliyetine sahip değişkenler varsa bunların arasından keyfî bir seçim yapılabilir. Seçilen değişkene atanacak değer ilgili satır ve sütunun, arz
ve talep değerleri arasından küçük olanıdır. Yöntemin geri kalanı en küçük maliyet yöntemindeki gibidir.
Değer atama işlemi, bir önceki atanan değere göre güncellenmiş satır ve sütun sonu değerleriyle tekrarlanır. Değişkene atanan değer, satırdaki arzı veya sütundaki talebi tümüyle karşıladığında, ilgili satır veya sütun boylu boyunca renkli boyanır. Renkli boyanan satır ve sütunlar, bir sonraki değer atamasında değerlendirme dışı bırakılır. Değer atama işlemi, en sona kalan satır veya sütun değerleri tümüyle karşılanana kadar sürdürülür.

En iyilik sınamasında uygulanan yöntemin adı MODI'dir. Simpleks çarpanları veya u-v yöntemi adıyla da bilinen MODI, simpleks yönteminin ulaştırma modeli için uyarlanmış bir çeşididir. Bu yöntemle bir temel uygun çözümün en iyi çözüm olup olmadığı sınanabilir ve eğer en iyi çözüm değilse modele girecek olan değişken belirlenebilir. MODI yöntemi aşağıdaki adımları izlemektedir:
1. Her bir satır için ui ve her bir sutün için vj olmak üzere ulaştırma tablosunun kenarına simpleks çarpanları tanımlanır.
2. Her bir temel değişken xij için ui+ vj= cij eşitlikleri yazılır.
3. Tanımlanan çarpanlardan birine sıfır değeri atanır ve denklemler sistemindeki diğer çarpanlarındeğeri bulunur.
4. Her bir temel dışı değişken için cij – (ui+ vj) formülüne ait değerler belirlenir.
5. Dördüncü adımda belirlenen değerlerin hepsi sıfıra eşit veya sıfırdan büyükse, eldeki temel uygun çözüm en iyi çözümdür.
6. Beşinci adımdaki sınamaya göre eldeki çözüm en iyi çözüm değilse, negatifler arasından en küçük değere sahip değişken temel giren değişken olarak belirlenir.

Eğer eldeki temel uygun çözüm en iyi çözüm değil ise, ardıştırma yöntemiyle bir sonraki temel uygun çözüme geçilir. Yeni çözümde temele giren değişken bir önceki adımda belirlenmişti. Ardıştırma işleminin sonucunda, modele giren değişken, temelden çıkan değişken olarak adlandırılan mevcut bir temel değişken ile değiştirilmiş olur. Ardışık çözüme, yeni değişkeni temel değişkene çeviren zincirleme bir işlemler dizisiyle ulaşılır. Temele giren değişkenden başlayan ve mevcut temel değişkenlere doğru ilerleyen ardışık bir değer güncelleme işleminden sonra mevcut temel değişkenlerden biri sıfır değerini alır. Sıfır değerini alan bu değişken, temelden çıkmış olur.

Dairesel bir rota çizen bir değer uyarlaması izlendiğinde, tekrarlı olarak ortaya çıkan kısıtlayıcılara ilişkin bu uyumsuzluklar, tek bir çevrimde dengelenebilir. Bu yapıdaki değer uyarlamasının adımları şu şekildedir:
1. Temele giren değişkenden, aynı satır veya sütun boyunda yer alan bir temel değişkene doğru çizgi çizilmeye başlanır.
2. Her seferinde bir temel değişkenden dönüş yapacak şekilde, mümkün olan en kısa daire tamamlanır.
3. Çizilen dairenin her bir köşesine sırayla + ve – işareti verilir. İşaretlemeye + işaretiyle, temele giren değişkenin bulunduğu köşeden başlanır.
4. İşaretlenen köşelerdeki değişkenlere ait en düşük değer belirlenir.
5. Bu değer, her bir köşedeki değişken değeriyle işleme sokulur: Eğer köşenin işareti + ise değer eklenir, – ise değer çıkarılır.

Atlama taşı olarak adlandırılan bu sınama yöntemi, mevcut temel uygun çözümdeki temel dışı değişkenlerin her birini sırayla temele giren değişken kabul ederek, tüm alternatif temel uygun çözümleri türetir. Temel dışı xij değişkenini içeren yeni bir temel uygun çözümü türetmek için MODI yönteminde de kullanılan dairesel değer uyarlamaları kullanılır. Tümü türetilmiş olan alternatif temel uygun çözümler arasında, daha düşük taşıma maliyetine sahip rotalardan oluşan bir çözüm olup olmadığı araştırılır.

Bunun için, her bir temele giren değişken alternatifi xij için meydana gelecek birim değişim miktarı dij hesaplanır. Değişim miktarı dij, i-j rotasında taşıma yapılması halinde, toplam taşıma maliyetinde meydana gelen değişimi gösterir.

Yöntem 5 aşamalıdır:

1. Mevcut temel uygun çözümdeki temel dışı değişkenler belirlenir.
2. Her bir temel dışı değişken xij’nin temel girdiği bir dairesel çevrim oluşturulur:
    2a. Temele giren değişkenden, aynı satır veya sütundaki temel değişkene çizgi çizilir.
    2b. Temel değişkenden dönüş yapacak şekilde, mümkün olan en kısa çevrim
tamamlanır.
    2c. Dairenin başlangıcından itibaren her bir köşeye sırayla + ve – işareti verilir.
3. Her bir temel dışı değişken için, + ve – işaretlerine göre birim taşıma maliyetlerinin toplanmasıyla değişim miktarı dij’ler hesaplanır.
4. Tüm dij’ler arasında negatif yoksa, eldeki temel uygun çözüm en iyi çözümdür.
5. Dördüncü adıma göre, eldeki çözüm en iyi çözüm değilse negatifler arasından en küçük değere sahip değişken temel giren değişken olarak belirlenir.

“Atama” terimiyle, bir grup çalışana birtakım iş veya görevlerin atanması kastedilmektedir. Genel olarak bir çalışan yalnızca bir iş yapar ve bir görev
yalnızca bir çalışana verilir. Buna benzer olarak, bir atama modelinde, yalnızca bir varış noktasına gönderim yapan kaynak noktaları ve yalnızca bir kaynaktan gönderim yapılan varış noktaları bulunmaktadır. Bu modeldeki gönderiler yalnızca bir birimlik gönderilerdir. Atama modeli, kaynak noktaları (çalışanlar) ve varış noktalarının (görevler) eşit sayıda olduğu ve noktalar arası gönderilerin (görev atamaları) yalnızca bir birimle sınırlı olduğu bir ulaştırma modelidir.

Atama modelinin karar değişkenleri sadece bir veya sıfır değeri alabilir. Çalışan ve görev sayısı n olan bir atama modelinde karar değişkeni xij, 1 değeri aldığında i’inci görevin j’inci çalışana atandığı anlaşılmaktadır. Eğer bu değişken 0 değeri alırsa, i’inci görevin j’inci çalışana atamasının yapılmadığı anlaşılır.

Eğer bir atama probleminde çalışanların veya görevlerin sayısı birbirine eşit değil ise, aynı ulaştırma modelinin dengelenmesinde olduğu gibi yapay değişkenin eklenmesi gerekir.

Atama modelinin çözümünde uygulanan Macar algoritmasının adımları aşağıda sıralanmıştır:
1. Atama probleminin maliyet matrisindeki her bir satırın en küçük değeri belirlenir. Her bir satıra ait en küçük değer, ilgili satırdaki tüm değerlerden çıkarılır.
2. Birinci adımda elde edilen matristeki her bir sütunun en küçük değeri belirlenir. Her bir sütuna ait en küçük değer, ilgili sütundaki tüm değerlerden çıkarılır.
3. Sıfır değeri bulunan satır ve sütunlar karalanır (veya üstü çizilir). Bunu yaparken en az sayıda satır ve sütun karalanmalıdır.
4. Karalanmış satır ve sütunların sayısı n olduğunda eldeki matristen en iyi çözüm elde edilebilir. Bu durumda 5. adıma geçilir. Eğer karalanmış satır ve sütunların sayısı n değil ise yani en iyi çözüm elde edilemeyecekse 6. adıma geçilir.
5. Matriste sıfır değeri alan elemanların koordinatlarına göre atama yapılarak en iyi çözüme ulaşılır. Atamada, satır veya sütun boyunca yalnızca bir tane olan sıfır değerli elemana öncelik verilir. Her bir satır ve sütunda yalnızca bir atama yapılmış olmalıdır.
6. Karalanmamış satır ve sütun değerlerinden en küçük olan belirlenir. Belirlenen değer, karalanmış olmayan satır ve sütunlardan çıkarılır, karalanmış satır ve sütunların kesişim yerlerine eklenir. 3. adıma geri dönülür.