Ünite 5: Atama Problemleri

Örnek 5.1: Askeri Atama

Ahmet, Mehmet ve Hasan isimli 3 askerin yazı işleri, haberleşme ve bilgisayar yazılımı görevlerine atanması problemidir. Test sonuçlarına göre en yüksek faydayı sağlamak hedeflenmiştir.

Faktöriyel Hesaplama

n adet görev ve atanacak sayısı için n! adet çözüm vardır. 3 asker için 3! = 6 farklı atama seçeneği mevcuttur.

En Yüksek Fayda İhlali

Tablo 5.4'te, her askerin en yüksek puanlı göreve atanması durumunda haberleşme görevine iki askerin atanması sonucu kısıt ihlal edilmiştir.

Alternatif Çözüm Varlığı

Örnek 5.1'de 24 faydalılık değerini sağlayan iki farklı atama planı bulunmuş, bu durum alternatif çözüm olarak adlandırılmıştır.

Anahtar Kavramlar

Atama Problemin adet kaynağın n adet göreve, her kaynak bir göreve gelecek şekilde atanması problemidir. Örnek: 3 askerin 3 farklı göreve atanması.

Uygun ÇözümHer kaynağın sadece bir göreve ve her görevin sadece bir kaynağa atandığı kısıtları sağlayan atama planıdır. Örnek: Tablo 5.2'deki 1 ve 0'lardan oluşan matris.

Faydalılık DeğeriAtanan kaynakların ilgili görevlerdeki performans puanlarının toplamıdır. Örnek: 5+7+2=14 toplam fayda.

n Faktöriyel (n!)n adet kaynak ve görev için oluşturulabilecek toplam farklı uygun çözüm sayısıdır. Örnek: 3 kaynak için 3x2x1=6 çözüm.

Amaç FonksiyonuToplam maliyeti en küçüklemeyi veya toplam faydayı en büyüklemeyi hedefleyen matematiksel ifadedir. Örnek: Min f(x) = ΣΣ cij xij.

Karar Değişkeni (xij)i. kaynağın j. göreve atanıp atanmadığını gösteren 0 veya 1 değerini alan değişkendir. Örnek: x12=1 ise Ahmet haberleşmeye atanmıştır.

0-1 ProgramlamaKarar değişkenlerinin sadece 0 veya 1 değerini alabildiği matematiksel model türüdür. Örnek: Atama probleminin matematiksel yapısı.

Bölünebilirlik VarsayımıDoğrusal programlamada değişkenlerin küsuratlı değerler alabilmesidir; atama probleminde bu varsayım geçerli değildir.

Macar AlgoritmasıAtama problemlerinde en iyi çözümü bulmak için kullanılan, matris indirgeme temelli bir çözüm yöntemidir. Örnek: Örnek 5.2'deki çözüm süreci.

Satır İndirgemeMaliyet matrisindeki her satırın en küçük değerinin, o satırdaki tüm değerlerden çıkarılması işlemidir.

Sütun İndirgemeSatır indirgeme sonrası her sütunda en az bir sıfır yoksa, sütunların en küçük değerinin sütun elemanlarından çıkarılmasıdır.

Alternatif ÇözümEn iyi amaç fonksiyonu değerini sağlayan birden fazla uygun atama planının bulunmasıdır. Örnek: Tablo 5.6'daki çözüm.

Ödünleşim (Trade-off)En yüksek faydayı sağlayan ancak kısıtları ihlal eden çözümden, en az kayıpla kısıtları sağlayan çözüme geçiş yapmaktır.

Parametre (cij)i. kaynağın j. görevi yapma maliyeti veya faydasıdır. Örnek: Tablo 5.1'deki puanlar.

İndis KümeleriProblemi tanımlayan kaynak (i) ve görev (j) kümeleridir. Örnek: i=1,...,n ve j=1,...,n.

En Küçükleme ProblemiAmaç fonksiyonunun maliyet veya süre gibi değerleri minimize etmeye çalıştığı problemdir.

En Büyükleme ProblemiAmaç fonksiyonunun verimlilik veya fayda gibi değerleri maksimize etmeye çalıştığı problemdir.

Eş Değer DönüşümEn büyükleme problemini en küçükleme formuna çevirmek için kullanılan -1 ile çarpma yöntemidir.

İterasyonAlgoritmanın çözüm yolunda yaptığı her bir döngü veya adım grubudur. Örnek: Örnek 5.4'teki 2. ve 3. iterasyonlar.

Kesişim NoktasıMacar algoritmasında çizgilerin kesiştiği hücrelerdeki değerlere en küçük değerin eklendiği noktadır.

Çizilmemiş ElemanlarMacar algoritmasında satır ve sütun çizgilerinin dışında kalan, işlem görmemiş hücre değerleridir.

Atama MatrisiKaynaklar ve görevler arasındaki atama durumlarını 0 ve 1'lerle gösteren tablo yapısıdır.

Diğer Önemli Bilgiler

Araştır 5.1: Lojistik Mezunları

Mert, Gül, Zeren ve Onur isimli 4 mezunun Planlama, Depo, İK ve Tedarik Zinciri pozisyonlarına atanması problemidir.

Macar Algoritması Kökeni

Atama problemlerini çözmek için geliştirilen, maliyet matrisi üzerinde satır/sütun indirgeme yapan sistematik bir yöntemdir.

En Büyükleme Dönüşümü

Enb f(x) = -Enk(-f(x)) formülü, en büyükleme problemlerini en küçükleme algoritmasıyla çözmeyi sağlar.

Örnek 5.2: Makine Yerleştirme

4 makinenin 4 farklı yere yerleştirilmesinde toplam mesafenin en küçüklenmesi problemidir. En küçük mesafe 20 olarak bulunmuştur.

Örnek 5.3: Proje Ekipleri

A, B, C ve D ekiplerinin 4 farklı projeye atanmasında etkinlik derecesini en büyükleme problemidir.

Örnek 5.4: 5x5 Atama Problemi

5 atanacak ve 5 görev içeren, maliyet verileri üzerinden Macar algoritmasının 3 iterasyonla çözüldüğü kapsamlı örnektir.

Macar Algoritması Adım 3

Sıfırları kapatan çizgi sayısı n'e eşitse en iyi çözüme ulaşılmıştır. Değilse iterasyona devam edilir.

Çizgi Kesişim Kuralı

Çizgilerin kesiştiği kutucuklardaki elemanlara en küçük değer eklenir, tek çizgi ile çizilenler değişmez.

0-1 Programlama Kısıtı

Atama probleminde değişkenler sadece 0 veya 1 olabildiği için doğrusal programlama varsayımlarını (bölünebilirlik) ihlal eder.

Atama Problemi vs Ulaştırma

İkisi de yöneylem araştırması problemidir ancak atama problemi ulaştırma probleminin özel bir durumudur (n=n).

Alternatif Çözüm Maliyeti

Örnek 5.4'te iki farklı atama planı da 54 maliyet değerini vererek alternatif en iyi çözümü oluşturmuştur.

Sınavda Dikkat Et

Atama problemlerinde n! kuralını unutmayın; n kaynak ve n görev varsa çözüm sayısı n faktöriyeldir.
Macar algoritmasında en büyükleme problemini en küçüklemeye çevirirken -1 ile çarpma veya en büyük değerden çıkarma kuralını karıştırmayın.
Çizgi sayısı n'e eşit değilse algoritma bitmez; iterasyonlara devam etmeniz gerektiğini hatırlayın.
Kesişim noktalarındaki değerlere en küçük değeri eklemeyi, çizilmemişlerden ise çıkarmayı unutmayın; bu işlem matrisin sıfır yapısını değiştirir.
Atama matrisinde her satır ve sütunda tam olarak bir adet 1 olması gerektiğini kontrol edin; bu kısıt ihlal edilirse çözüm uygun değildir.
Alternatif çözümlerin var olabileceğini göz ardı etmeyin; aynı maliyeti veren farklı sıfır dizilimleri olabilir.