YÖNEYLEM ARAŞTIRMASI I - Deneme Sınavı - 2

Dengelenmiş ulaştırma modeline bir başlangıç temel uygun çözüm bulmak için en çok kullanılan üç yöntem vardır. Bu yöntemler,

olarak sıralanabilir.

Macar algoritması ile ilk önce her satırdaki en küçük Cij seçilip, diğer atama giderlerinden bu değer çıkartılarak, satırlara göre indirgenmiş tablo bulunur. Yanıt D seçeneğidir.

Ulaştırma tablosu üzerinden çözüm işlemlerini yürütebilmek için, modelin dengelenmiş olması gerekmektedir. Bir ulaştırma modeli dengelenmemiş ise, yapay kaynak ya da yapay hedef noktası eklentisiyle, model dengelenmiş hale dönüştürülebilir. Bu durumda eklenen yapay noktanın sunum ya da talep miktarı, toplam sunum ile toplam talep arasındaki fark kadar olur. Yapay noktalara karşı gelen birim taşıma maliyetleri ise aksi belirtilmedikçe sıfır olarak alınır. Bazen yapay kaynak noktasına ait taşıma maliyetlerine sıfır yerine, belirlenen ceza maliyetleri de verilebilmektedir.

Ulaştırma tablosu üzerindeki bir hücreden başlayarak, yine aynı hücrede sona eren, köselerinde en az dört farklı hücrenin sıralandığı kapalı güzergaha döngü, çevrim veya yörünge denmektedir. Bir güzergahın döngü oluşturması için izleyen şartların sağlanması gerekir:

Macar algoritması ile atama problemini çözebilmek için, aşağıdaki koşulların sağlanması gerekir:

Dağıtım merkezleri i, depolar j indisi ile ifade edildiğinden ve 1. dağıtım merkezi sorulduğundan, Xij ifadesinde i yerine 1 konulacaktır. i dağıtım merkezi 3 depoya birden elindeki maksimum ürün sayısı olan 100 ürünü gönderecektir. 3. deponun talep miktarı 65 olup, taleplerini iki adet dağıtım merkezinden karşılayacak olup, bu kısıtları ifade eden denklemler aşağıdaki gibi yazılır:

Yanıt E seçeneğidir.

Tablonun en kuzeybatısında yer alan X11 hücresi seçilir ve o hücreye alabileceği maksimum değer olan "125" atanır. Daha sonra ilk sütun kapatılır. Kuzeybatıda kalan X12 hücresine alabileceği en büyük değer olan "80" değeri atanır. Benzer şekilde 2. sütun da kapatıldıktan sonra, kuzeybatıda kalan X13 hücresine alabileceği en yüksek değer olan "20" atanır ve ilk satır kapatılır. Daha sonra en kuzeybatıda kalan X23 hücresine "75" değeri atanır ve ikinci satır ve üçüncü sütun da kapatıldıktan sonra, X34 hücresine de "100" değeri atanır.  

Yanıt B seçeneğidir.

Talep miktarları toplamı 500 olduğu için, sunum miktarlarının toplamının da 500 olması gerekir ki, cevap 175 olacaktır.  Böylelikle modeldeki talep ve sunum miktarları eşit olacaktır. Doğru cevap A seçeneğidir.

Modelde talep miktarı 500, sunum miktarı 400 olduğundan dolayı, talebin karşılanması için eksik kalan 100 birimlik miktar yapay kaynaktan karşılanacaktır. 

Yanıt B seçeneğidir.

En küçük maliyetli hücre X21 olup, maksimum atama miktar olan 10 ataması yapılır. Daha sonra sırasıyla X32, X23, X33 ve X13 hücrelerine alabilecekleri maksimum değerler atanır. Toplam maliyet;

10*0 + 10*1 + 5*6 + 3*2 + 2*5 = 56

Yanıt C seçeneğidir.

Her biri bir düğüm olarak gösterilen si kapasitesine sahip m adet kaynak noktası ve her biri dj talebine sahip n adet hedef noktası vardır. Düğümleri birleştiren oklar, kaynaklarla hedefler arasında mümkün olan taşıma rotalarını göstermektedir. (i, j) bağlantısı, i. kaynaktan j. hedefe ürün gönderilebildiği anlamına gelmekte, taşıma maliyeti ve taşıma miktarı olmak üzere iki tür bilgi içermektedir. Amaç, mevcut kaynakları kullanarak tüm talebi karşılayacak şekilde en küçük maliyetli dağıtım planının bulunmasıdır.

Ulaştırma problemlerinin taşıdığı genel özellikler aşağıdaki gibi sıralanabilir: 1. Bir mal veya hizmet şeklinde ürün gönderen, m adet üretim merkezi vardır. Üretim merkezlerinin kapasiteleri bilinmektedir. 2. Ürünün gönderildiği n adet tüketim merkezi vardır. Tüketim merkezlerinin talep ettikleri miktarlar bilinmektedir. 3. Bir üretim merkezinden bir tüketim merkezine gönderilen her 1 birim ürün için ortaya çıkan birim taşıma (gönderme) maliyeti bilinmekte olup, toplam taşıma maliyeti taşınan miktarla doğru orantılı olarak değişmektedir. 4. Dağıtımı yapılacak mal veya hizmet olarak tanımlanmış ürün, bütün üretim ve tüketim merkezleri için aynı birim ve türde tanımlıdır.

Ulaştırma tablosu, üretim merkezleri satırlarda, tüketim merkezleri sütunlarda olmak üzere m×n sayıda hücresi olan bir tablodur. Üretim ve tüketim merkezlerinin kesiştiği her bir hücre, bir karar değişkenine karşı gelir. Her hücrenin sağ veya sol üst köşesine birim taşıma maliyetleri yazılır. Üretim merkezlerinin kapasiteleri, satırların en sağında; tüketim merkezlerinin talepleri de sütunların altında yer alır.

Eğer bir ulaştırma modelinin toplam sunum miktarı toplam talep miktarına eşit ise, “dengelenmiş ulaştırma modeli”, eşit değilse “dengelenmemiş ulaştırma modeli” olarak adlandırılır.

Ulaştırma tablosu üzerinden çözüm işlemlerini yürütebilmek için, modelin dengelenmiş olması gerekmektedir. Bir ulaştırma modeli dengelenmemiş ise, yapay kaynak ya da yapay hedef noktası eklentisiyle, model dengelenmiş hale dönüştürülebilir. Bu durumda eklenen yapay noktanın sunum ya da talep miktarı, toplam sunum ile toplam talep arasındaki fark kadar olur. Yapay noktalara karşı gelen birim taşıma maliyetleri ise aksi belirtilmedikçe sıfır olarak alınır. Bazen yapay kaynak noktasına ait taşıma maliyetlerine sıfır yerine, belirlenen ceza maliyetleri de verilebilmektedir.

Ulaştırma problemleri için geliştirilmiş çözüm algoritmasının başlıca üç adımı bulunmaktadır: 1. Bir başlangıç temel uygun çözümün bulunması. 2. Eniyilik sınamasının yapılması. 3. Eniyi çözüme erişilmemişse izleyen temel uygun çözümün bulunarak ikinci adıma dönülmesi.

VAM yöntemi ile ulaştırma probleminin çözümü için her satır ve sütun için ceza puanları hesaplanır. Satır cezaları sırasıyla 0, 7, 2 ikeni sütun cezaları da, 4, 1, 1, 5 olur. En büyük ceza miktarı ikinci satırda bulunduğundan ikinci satırdaki en küçük maliyetli hücreye X23 hücresine, 20 ataması yapılır ve ikinci satırdaki değerler tablodaki ceza puanlarını ikinci kez hesaplarken dikkate alınmaz. Ceza paunları birinci ve üçüncü satır için 0 ve 3 iken, sütunlar için sırasıyla 4, 1, 5, 5 olur. Dolayısıyla üçüncü sütunu seçip, en küçük maliyetli kalan X33 hücresine 5 ataması yapılır. İşlemler benzer şekilde devam ettirildiğinde tekrar ceza puanları hesaplanır, bir sonraki atamanın dördüncü sütuna yapılacağı görülür. Sırasıyla 31 hücresine 10, X11 hücresine 15 ve X12 hücresine 5 ataması yapılır. Yanıt D seçeneğidir.

Ulaştırma modelinde talep ve sunum kısıtlarını sağlayan herhangi bir çözüm, sıfırdan büyük eşit olma koşuluna da uyuyorsa problem için uygun bir çözümdür.

Enküçük maliyet yönteminin adımları aşağıdaki şekilde sıralanabilir:

1. Tablo genelinde en düşük maliyete sahip olan ve sayısal bir değer atanmamış (i, j) hücresi seçilir. En düşük maliyetli birden fazla hücre varsa, herhangi biri ele alınabilir. 2. Bu hücreye, i. satırdaki sunum ve j. sütundaki talep değerleri göz önüne alınarak, mümkün olan enbüyük değer atanır. 3. Atanan miktar, i. satırın sunum ve j. sütunun talep değerlerinden çıkarılarak, Si ve dj değerleri güncellenir. 4. Sıfır değerine karşı gelen satır veya sütundan sadece birisi işlem dışı bırakılarak tablo daraltılır. 5. İşlem dışı bırakılmamış sadece bir satır veya sütun kaldığında algoritma sonlanır. Kalan miktarlar son satır veya sütundaki uygun yerlere atanır. Aksi halde birinci adıma dönülür.

Atlama Taşı Yöntemi ile Eniyilik Sınaması; Bu yöntem, mevcut çözümdeki temel dışı değişkenlerin temele alınması halinde, amaç fonksiyonunda ne kadar artış ya da azalma olacağının hesaplanmasına dayanır. Temeldışı değişkenler, ulaştırma tablosu üzerinde bir değer atanmamış boş hücrelerdir.

Atlama taşı yönteminin bir dezavantajı, tüm boş hücreler için döngü bulma ve değişim değeri hesaplama zorunluluğudur.