YÖNEYLEM ARAŞTIRMASI I

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.

Karar değişkenlerinin negatif değer almaması yanında, temel kısıtların dışında özel kısıtı olmayan problemlerinde, toplam taşıma maliyeti de miktarla doğru orantılı olarak değişiyorsa, problemin çözümü için geliştirilen matematiksel model bir doğrusal karar modeli olur

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

Dengelenmiş ulaştırma modelinde ü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.

Northwest corner method 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. Ulaştırma tablosunun kuzeybatı (en sol üst) köşesinden güneydoğu köşesine doğru hücrelere değer atanır. Her adımda tablodaki bir satır veya sütun işlem dışı bırakılarak, tablo daraltılır

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:
1. İki ardışık hücre, aynı satırda ya da aynı sütunda yer almalıdır.
2. Dizideki son hücre, ilk hücreyle ortak bir satır ya da sütuna sahip olmalıdır.
3. Üç ardışık hücre aynı satır ya da sütunda bulunmamalıdır

Ulaştırma tablosu üzerinde yer alan bir temel uygun çözümün, en iyi çözüm olup olmadığını sınamak için atlama taşı veya MODI yöntemi kullanılabilir. Eniyilik sınaması ile, eğer eniyi çözüme erişilmemiş ise temel girecek değişken belirlenir. Bir değişkenin temele alınması, ulaştırma tablosu üzerindeki boş hücrelerden birisine değer atanması anlamına gelir. Bu durumda satır ve sütun yönlü dengenin sağlanması için, dağıtım yapılmamış bir hücreye bir birim dağıtım yapılması halinde, bunun bulunduğu satırda ve sütunda dağıtım yapılmış birer hücreden birer birim azaltma yapılmalıdır. Ulaştırma modelinde bir değişken temele alındığında, temelden hangi değişkenin çıkıp, temeldeki değişkenlerin hangi değerleri alacaklarını kolaylıkla hesaplamak için döngü kavramından yararlanılır.

Xij: Santral i‘de üretilen ve Şehir j’ye gönderilen elektrik miktarı (milyon kwh). Bu  sepeble   olur.

Bu problemde başlama hücresi 1. kaynaktan 1  nolu hedefe 120 birim tahsis etmeyi mümkün kılar. 1. kaynağın kapasitesinin 120 birim olması nedeniyle rota üzerinden gönderilecek mümkün olan en büyük miktar budur. 1 nolu hedefe 150 birim kabul edilecekken, 1. kaynak üretebileceği miktar olan 120 birimden daha fazlasını gönderemez. 1 nolu hedef için geriye kalan 30 birim bir sonraki hücre olan 2. kaynaktan 1 nolu hedefe yüklemeyi gerektirir. 2 nolu kaynak için geriye kalan 80-30=50 birim ise sağdaki hücreye yüklenir. 2 nolu hedefin kapasitesi 70 birim olmasına rağmen buraya en fazla 50 birim yüklenmiştir. Geriye kalan 70-50=20 birim bir sonraki kaynak olan 3. kaynağa yüklenir. 3 nolu kaynak için kapasite 80 olmasına rağmen  80-20=60 birim bir sonraki hedef olan 3. hedefe yüklenmiştir. Böylelikle yükleme işlemi tamamlanmış olur. Bu noktada tüm kısıtlar sağlanmış olur.

Toplam taşıma maliyeti=120*8+30*15+50*10+20*9+60*10=2690

Atama modelinde amaç, genellikle toplam maliyeti enküçüklemek için kaynak kullanımının bire bir dağıtımının yapılmasıdır. İşçilerin işlere atanması ya da işe en uygun kişi seçimi, atama modeliyle çözülebilecek bir konudur. Aslında atama modeli, kaynakları işçiler, hedefleri de işler olan özel bir ulaştırma modelidir. Her bir kaynaktaki sunum miktarı ve her bir hedefteki talep miktarı sürekli olarak “1” e eşittir. Problemin oluştuğu sistemin özel yapısının gerektirdiği kısıtlar dışında, problemin iki temel kısıtı vardır:

Çözüm için önce satır-tarzı fırsat kayıpları elde

edilir. Bunun için her elemanın en yüksek ortalama iş bağlantısını gerçekleştirdiği bölge esas alınır.

Bundan sonraki adımda; fırsat kayıplarının sütunlardaki minimum değerlerini tespit ederek tamamlanır.

Optimum Atama

Satır Elemanı  Bölge

       1                E

       2                C

       3                B

       4                D

       5                A

Toplam İş = 20 (1)+16 (1)+16 (1)+18(1)+13(1)=83.

Atama modelinde amaç, genellikle toplam maliyeti enküçüklemek için kaynak kullanımının bire bir dağıtımının yapılmasıdır. İşçilerin işlere atanması ya da işe en uygun kişi seçimi, atama modeliyle çözülebilecek bir konudur. Aslında atama modeli, kaynakları işçiler, hedefleri de işler olan özel bir ulaştırma modelidir. Her bir kaynaktaki sunum miktarı ve her bir hedefteki talep miktarı sürekli olarak “1” e eşittir. Problemin oluştuğu sistemin özel yapısının gerektirdiği kısıtlar dışında, problemin iki temel kısıtı vardır:

Bu problemde başlama hücresi 1. kaynaktan 1  nolu hedefe 100 birim tahsis etmeyi mümkün kılar. 1. kaynağın kapasitesinin 100 birim olması nedeniyle rota üzerinden gönderilecek mümkün olan en büyük miktar budur. 1 nolu hedefe 300 birim kabul edilecekken, 1. kaynak üretebileceği miktar olan 100 birimden daha fazlasını gönderemez. 2 nolu hedef için 200 birim 2 nolu kaynak tarafından karşılanır. Geriye kalan 300-200=100 birim ise bir sonraki hedefe yüklenir. 3 nolu hedef için geriye kalan 200-100=100 birim de 3 nolu kaynak tarafından yüklenir. 1 nolu hedef için geriye kalan 300-100=200 ise 3 nolu kaynak tarafından karşılanır. Bu noktada tüm kısıtlar sağlanmış olur.

Toplam taşıma maliyeti=100*5+200*4+100*3+200*9+100*5=3900

Yükleme yapılmış hücreler için  eşitliklerini yazalım.

Bu eşitlikleri çözmek için bilinmeyenlerden yalnız birine sıfır değerini vermek yeterlidir. U1=0 olsun.