İŞL404U-SAYISAL KARAR VERME TEKNİKLERİ
Ünite 4: Ulaştırma ve Atama Modelleri
Giriş
Doğrusal programlara simpleks yönteminin uygulanması, simpleks tablolarının kâğıt üzerinde çözümüyle sınırlı değildir. Simpleks algoritması bütüncül bir yaklaşıma dayanır ve bu sebeple sahip olduğu kavramsal özelliklere dayanarak çeşitli çözüm yöntemleri türetilebilmektedir. Belirli türde doğrusal programlar için türetilen bu çözüm yöntemleriyle, simpleks tablolarıyla kâğıt üzerinde çözüme göre daha az çaba harcanmaktadır.
Ulaştırma Modeli
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. Modelin bileşenleri:
m adet kaynak noktasından gönderilmesi gereken nesnelerin miktarları………….a1, a2, …, am
n adet varış noktasında karşılanacak olan nesnelerin miktarı………………………... b1, b2, …, bn’dir.
cij………………………………kaynak noktası i’den varış noktası j’ye bir adet nesnenin gönderim maliyetidir.
Problemin karar değişkenleri her bir kaynak-varış noktası ikilisi xij için gönderim yapılacak nesnelerin miktarıdır. Birim başına taşıma maliyetleri (cij) ve gönderimi yapılacak nesnelerin miktarı m × n boyutlu kitabın 91. sayfasındaki matrisler ile ifade edilebilir. Burada görülen Matris 1 ve Matris 2’de i. satır, sırasıyla, i. kaynak noktasından yapılan gönderilerin taşıma maliyetlerini ve miktarlarını ifade eder. Benzer şekilde j. sütün, sırasıyla, j. varış noktasına yapılan gönderilerin taşıma maliyetlerini ve miktarlarını verir. Gönderilecek miktarlar ancak sıfırdan büyük veya sıfıra eşit olabileceği için karar değişkenlerine ait değerler negatif olamaz. Bu durum modelin negatif olmama koşuluna karşılık gelmektedir.
• Eğer j. sütundaki xij değerlerinin toplamı bj ’ye eşit ise j. varış noktasındaki talebin tümü karşılanmış olmaktadır. • Eğer i. satırdaki xij değerlerinin toplamı ai’ye eşit ise i. kaynak noktasındaki arzın tümü tüketilmiş olmaktadır.
Problemin amacı, i. kaynak noktalarından j. varış noktalarına her bir gönderim faaliyetinden doğan maliyetlerin toplamı olan toplam ulaştırma maliyetini en küçüklemektir. Ulaştırma probleminin genel formu:
Enk Z = c11 x11 + c12 x12 + … + c1n x1n + … + cm1 xm1 + cm2 xm2 + … + cmn xmn
Gönderimler yapıldığında toplam talep tam olarak karşılanıyor ve toplam arz tamamen tükeniyorsa toplam arz toplam talebe eşittir:
! a ! b !!! i = !!! j
Bu yapıya dengelenmiş ulaştırma modeli adı verilir. Bazı durumlarda, ulaştırma problemleri daha az kısıtlayıcı
olabilmektedir; örneğin, kaynaklardaki toplam arz, varış noktalarındaki toplam talepten fazla olabilir. Bu gibi durumlarda, toplam arzın toplam talebi aşan kısmını sanal olarak karşılayacak bir kukla (diğer adıyla, yapay) varış noktası tanımlanmalıdır. Probleme yapılan bu eklemeyle, model dengelenir ve ulaştırma modelinin yukarıda verilen genel formuna uygun hâle gelir.
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. Ulaştırma problemi bakış açısına göre, kısıtları sağlayan en düşük toplam ulaştırma maliyetine ancak m + n – 1 adet kaynak-varış noktası rotasından gönderim yapılarak ulaşılabilir. Ulaştırma modelinin çözümü için simpleks yöntemiyle aynı adımlar izlenir:
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.
Ulaştırma Modeli Çözüm Yöntemi
Yöntem üç adımdan oluşur:
1. Temel alınacak bir noktanın belirlenmesidir. Bu nokta başlangıç için seçilen bir temel uygun çözümdür. Çözümü başlatmak için çeşitli yöntemler geliştirilmiştir. 2. Eldeki çözümün en iyi çözüm olup olmadığının irdelenmesidir. 3. İkinci adımdan sonra koşullu olarak uygulanır: a. Eğer ikinci adımda, eldeki çözümün en iyi çözüm olmadığı saptanırsa, üçüncü adıma geçilir. b. Üçüncü adım, temele giren değişkeni içeren yeni bir temel uygun çözümün elde edilmesidir. Bulunan yeni çözümle ikinci adım tekrarlanır. En iyi çözüm elde edilene kadar ikinci ve üçüncü adımlar ardıştırılır.
Yöntemin daha iyi anlaşılması için kitabın 93. Sayfasında yer alan Örnek 4.1’i inceleyiniz.
Başlangıç için Temel Uygun Çözümün Bulunması
Ulaştırma probleminin çözüm yöntemi, sonraki adımda kullanılmak üzere bir temel uygun çözümün belirlenmesiyle başlar. Temel uygun çözümünde m + n – 1 adet temel değişken bulunan dengeli ulaştırma modelinde, kısıtlayıcılara ait denklem sayısı m + n’dir.
Temel uygun çözümdeki temel değişkenleri elde ederken, ilk olarak değişkenlerden biri keyfi olarak temel değişken seçilir ve değer ataması yapılır. Diğer temel değişkenlere ait değerler ise, ilk atama yapılan değişkene göre belirlenir. Değer ataması, seçilen değişkene arz ve talep
kısıtları altında alabileceği en büyük değerin verilmesidir. Değer atanacak değişkenin seçimi için çeşitli yöntemler bulunmaktadır:
1. Kuzey-batı köşe yöntemi, 2. En küçük maliyet yöntemi 3. Vogel’in yakınsama (VAM)
Kuzey-batı köşe yöntemi: İlk 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. 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. 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öntem ile ilgili tablo kitabın 96. Sayfasında Tablo 4.3’de verilmiştir.
En küçük maliyet yöntemi: 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öntem kitabınızın 97. Sayfasında yer alan Tablo 4.4 de ayrıntılı olarak anlatılmaktadır.
Vogel’in Yakınsama Yöntemi (VAM): Bu yöntemde, doğrudan doğruya ulaşım maliyetlerini dikkate almak yerine, ceza maliyeti kavramı türetilmiştir. 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. Bu yöntem, bir değişkene değer atamanın fırsat maliyetini dikkate aldığı için, doğrudan doğruya en düşük ulaştırma maliyetine göre atama yapmaktan daha düşük amaç fonksiyonu değerine sahip bir başlangıç çözümü doğuracağı iddiasındadır.
Kitabınızın 98. Sayfasında yer alan Tablo 4.5’i inceleyiniz.
En İyilik Sınaması
En iyilik sınaması için ikillik özelliklerinden faydalanan MODI yöntemi kullanılmaktadır. 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 adımları:
1. Her bir satır için ui ve her bir sutün için vj olmak üzere 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ın değ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 >=0 ise, 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.
Modelin açıklaması kitabınızın 99.sayfasında yer alan Tablo 4.6 da ayrıntılı bir şekilde verilmiştir.
Ardıştırma
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. 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. 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.
En İyilik Sınamasında Alternatif Yönetim: Atlama Taşı 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. Atlama taşı yönteminin adımları:
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.
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 Modeli
Genel olarak bir çalışan yalnızca bir iş yapar ve bir görev yalnızca bir çalışana verilir. 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. Konu ile ilgili kitabınızın 107. Sayfasında yer alan Örnek 4.2’yi inceleyiniz.