YÖNEYLEM ARAŞTIRMASI I

4 adımda problemin çözümünü verelim.

1.adım: Tablonun her bir satırındaki en küçük eleman belirlenir ve bu değer ait olduğu satırdaki diğer değerlerden çıkartılarak satır indirgemeli fırsat maliyetleri tablosu elde edilir. Örneğin 1. kişiye P2 verilirse 14 maliyete katlanılacaktır. Fakat aynı kişi 3. projeyi 6 maliyetle yapabilmektedir. Bu durumda 14-6=8 birimlik fırsat maliyeti elde edilmiş olur. Benzer işlemler diğer kişiler içinde yapılır ve aşağıdaki tablo elde edilir.

2.adım: yukarıdaki tablo kullanılarak her bir sütundaki en küçük değer ait olduğu sütundaki diğer değerlerden çıkartılarak sütun indirgemeli fırsat maliyetleri tablosu elde edilir. Bu adımdaki sonuçlar aşağıda verilmiştir.

3.adım: 2. adım sonunda bulunan tablo kullanılarak en az sayıda çizgi ile “0” değerlerinin üzeri çizilir.

Bu tablodan sıfır değerlerini kapatacak şekilde çizilen çizgilerin sayısının iki olduğu görülmektedir. Bu değer de satır sayısına eşit değildir. Dolayısı ile optimum atama bu adımda yapılamaz. Bu durumda, 4. adıma geçilir.

4.adım: 3. adım sonundaki fırsat maliyetleri tablosundan üzeri çizilmeyen değerlerin en küçüğü 2’dir. Bu değer üzeri çizilmeyen değerlerden çıkartılır, üzerinden çift çizgi geçenlere eklenir. Bu işlem sonucu aşağıdaki tabloda görülmektedir.

Bu tablodan “0”ların 3 çizgi ile kapanabileceği görülmektedir. En uygun atama ise,

     Atama            Maliyet

     K1P3                 6

     K2P2                10

     K3P1                 9

    Toplam maliyet=25

Macar yöntemi adım adım uygulanırsa,

Satır en küçüklerinin, satırdaki diğer elemanlardan çıkartılması ile aşağıdaki tablo elde edilir.

Yukarıdaki tablodan sütun enküçüklerinin, sütundaki diğer elemanlardan çıkartılması ile aşağıdaki tablo elde edilir.

Tablodan da görüldüğü üzere “0” değerlerinin en az çizgiyle kapatılır.

Yukarıdaki tabloda çizilen çizgilerin sayısının satır sayısına eşit olduğu görülmektedir. Bu durumda, en uygun atama yapılmıştır.

      Atama             Maliyet

     F1B4                55

     F2B3                80

     F3B2                 100

     F4B1                 65

    Toplam maliyet=300

Atama modelinde amaç, bir etkinliği eniyilemek için kaynak kullanımının bire bir dağıtımını sağlamaktır. Ulaştırma probleminin özel bir hali olan atama problemleri ile genellikle işlerin makinelere dağıtımı, kişilerin işlere tayini, personelin satış bölgelerine dağıtımına benzer durumlarda karşılaşılmaktadır. Kaynaklar ve hedefler arasındaki mal veya hizmet akışı ile ilgili olan ulaştırma problemlerinde, birden fazla hedef noktasına dağıtım yapabilmek mümkündür. Atama problemlerinde ise, bir kaynak noktasından sadece bir hedefe atama yapılabilmekte ve bir hedefe sadece bir kaynak noktası atanabilmektedir.

Ulaştırma problemlerinin taşıdığı genel özellikler şöyle sıralanabilir: Bir mal veya hizmet şeklinde ürün gönderen, m adet üretim merkezi vardır. Üretim merkezlerinin kapasiteleri bilinmektedir. Ürünün gönderildiği n adet tüketim merkezi vardır. Tüketim merkezlerinin talep ettikleri miktarlar bilinmektedir. 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. 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 problemlerinde cevap aranan soru, hangi üretim merkezinden, hangi tüketim merkezine ne kadar ürün taşınacağıdır. Bu soru aynı zamanda karar değişkenlerini tanımlamakta olup, sorunun cevabı ürün dağıtım planını verecektir. Ulaştırma problemlerinde iki temel kısıt vardır: Bir üretim merkezinden tüm tüketim merkezlerine gönderilen toplam ürün miktarı, üretim merkezinin kapasitesini aşamaz. Bir tüketim merkezine bütün üretim merkezlerinden gönderilen toplam ürün miktarı, tüketim merkezinin talebini karşılamalıdır. Bir tüketim merkezine sadece bir üretim merkezinden ürün gönderilebilir gibi bir temel kısıt ise yoktur. Gerektiğinde bir tüketim merkezine birden fazla üretim merkezinden ürün gönderilebilir.

Dengelenmiş ulaştırma modelinin taşıdığı üç önemli özellik vardır: Üretim merkezi sayısı “m” ve talep merkezi sayısı “n” iken, dengelenmiş ulaştırma modelinin bir temel uygun çözümünde en fazla (m + n -1) adet değişken temelde yer alabilir. Her dengelenmiş ulaştırma modelinin en az bir uygun çözümü olup, eniyi çözümü de vardır. Ulaştırma modelinde, sunum ve talep miktarlarına karşı gelen değerler tamsayı ise karar değişkenleri her temel uygun çözümde, dolayısıyla eniyi çözümde tamsayı değer alır.

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

Kuzeybatı köşe yöntemi ile başlangıç çözüm bulma, başlangıç temel uygun çözümü oluşturmak için en basit ve hızlı olan yöntemdir. Bu yöntemde, taşıma maliyetleri göz önüne alınmaz. Birim taşıma maliyetlerini esas alan en küçük maliyet yönteminde, her seferinde daraltılmış tabloda en düşük maliyetli olan hücreye atama yapılır. Atama yapılacak hücrenin seçimi haricinde, hücrelere atanacak değerin belirlenmesi, sunum ve talep miktarlarının güncellenmesi ve işlem dışı bırakma adımları kuzeybatı köşe yönteminde olduğu gibidir. VAM yöntemi, en düşük maliyet yönteminin geliştirilmiş hali olarak düşünülebilir. Tablo genelinde, birinci öncelikli hücre yerine ikinci öncelikli hücreye dağıtım yapılması halinde birim başına kaçırılacak fırsatları bulup, en büyük fırsatın kaçırılmaması esasına dayanır. Araştırma sonuçları, VAM ile bulunan bir başlangıç temel uygun çözümün, diğer yöntemlere göre daha az ardıştırma ile eniyi çözüme ulaştığını ileri sürmektedir.

Ulaştırma tablosu üzerindeki bir hücreden başlayarak, yine aynı hücrede sona eren, köşelerinde 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: İki ardışık hücre, aynı satırda ya da aynı sütunda yer almalıdır. Dizideki son hücre, ilk hücreyle ortak bir satır ya da sütuna sahip olmalıdır. Üç ardışık hücre aynı satır ya da sütunda bulunmamalıdır.

Seçeneklere baktığımızda istenen kısıtın C seçeneğinde olduğu görülmektedir. C seçeneğindeki ifadede 2-1, 2-2, 2-3 atamalarından sadece bir tanesinin 1 olması istenmektedir. Yani 2. Marangoz ya birinci işe ya ikinci işe ya üçüncü işe atansın istenmektedir. Eğer ikinci marangoz iki veya üç işe birden atanırsa C’deki ifade 1’den büyük değer alacak kısıt sağlanmayacaktır. Bu sebeple bu kısıt marangozun tek bir işe atanmasını sağlamaktadır.

Üçüncü iş ya birinci ya ikinci marangoza atansın kısıtı A seçeneğinde doğru olarak verilmiştir. Çünkü A seçeneğindeki ifadede 1-3 ataması ya da 2-3 atamasından sadece bir tanesi 1 değerini alacaktır. Buna göre ya birinci marangoz ya ikinci marangoz üçüncü işe atanabilecektir.

Burada öncelikle amaç fonksiyonunun en büyükleme mi yoksa en küçükleme mi olduğuna karar verilmelidir. Dikkat edilirse işlemler için süreler söz konusudur ve amaç en kısa sürede bitirmek olmalıdır. Bu sebeple amaç en küçükleme olmalıdır. Xij i bilgisayarının j işine atanması olduğu için amaç fonksiyonu tüm i ve j değerleri için karşı gelen sürelerin çarpımlarının toplanması şeklinde olmalıdır.

Mağaza j indisi ile ifade edildiğinden ve 2. mağaza sorulduğundan, Xij ifadesinde j yerine 2 konulacaktır. i için hem 1 hem 2 nolu depolardan gelen ürünler olduğu için i yerine de 1 ve 2 konularak, 2. mağazanın talep miktarı 40 olarak ifade edildiğinden iki depodan da gelen ürünlerin toplamı en az 40 olmalı ifadesini belirten kısıt şu şekilde yazılır.

  

Yanıt A 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 "5" atanır. Daha sonra ilk satırdaki bir alt hücresi olan X21'e yapılabilecek maksimum atama olan "5" değeri atanır. Daha sonra sırasıyla X22 hücresine "8", X32 hücresine "2", X33 hücresine de "10" değerleri atanır. Toplam maliyet

5*1 + 5*0 + 8*4 + 2*1 + 10*5= 89 olarak bulunur.

Yanıt C seçeneğidir.

m sunum merkezi sayısı, n ise talep merkezi sayısıdır. Her problemin yapısına göre farklı değerler alabilirler. Eşit olmak gibi bir zorundalıkları kesinlikle yoktur. Yanıt D seçeneğidir.

En küçük maliyetli hücrelerden atama yapmaya başlamak, en küçük maliyet yöntemi ile başlangıç çözümü bulmanın temel prensibidir.

Birinci öncelikli hücre yerine ikinci öncelikli hücreye dağıtım yapılması halinde birim başına kaçırılacak fırsatları bulup, en büyük fırsatın kaçırılmaması esasına dayanır. Yanıt B seçeneğidir.

Bir güzergahın döngü oluşturması için izleyen şartların sağlanması gerekir: İki ardışık hücre, aynı satırda ya da aynı sütunda yer almalıdır, dizideki son hücre, ilk hücreyle ortak bir satır ya da sütuna sahip olmalıdır ve üç ardışık hücre aynı satır ya da sütunda bulunmamalıdır.

Yanıt E seçeneğidir.

MODI yönteminin ilk adımı, ulaştırma tablosunda her satıra karşı gelen üretim merkezi için bir Ui çarpanı, her sütuna karşı gelen tüketim merkezi için de bir Vj çarpanı tanımlamak ve bulmaktır.

MODI yöntemi gereği aşağıdaki işlemler yapılır.

u1+v1=9  ..  u1=0, v1=9

u1+v2=5  ..  u1=0, v2=5 

u1+v4=6  ..  u1=0, v4=6 

u2+v1=9 ..  u2=0, v1=9 

u3+v2=4 ..  u3=-1, v2=5 

u3+v3=3 ..  u3=-1, v3=4

Yanıt C seçeneğidir.