MACAR YÖNTEMI: NELERDEN OLUŞUR, ÖRNEK - DUDAS - 2026

Macar yöntem size maliyetini en aza indirmek istediğinizde tahsis problemlerde kullanılan bir algoritmadır. Yani birden fazla kişiyi çeşitli faaliyetlere en düşük maliyetle atayarak minimum maliyeti bulmak için kullanılır. Her aktivite farklı bir kişiye atanmalıdır.

Tahsis problemi, amacın bir dizi işi birden çok kişi tarafından tamamlamanın maliyetini veya süresini en aza indirgemek olan özel bir doğrusal programlama problemidir.

Kaynak: Pixabay.com

Tahsis sorununun önemli özelliklerinden biri, bir makineye (veya projeye) yalnızca bir işin (veya çalışanın) atanmasıdır.

Bu yöntem Macar matematikçi D. Konig tarafından geliştirilmiştir. Bu nedenle Macar atama problemleri yöntemi olarak bilinir. Kuhn-Munkres tahsis algoritması olarak da bilinir.

İki aşamadan oluşan bu yöntem uygulanarak herhangi bir tahsis problemi kolaylıkla çözülebilir:

- İlk aşama ile sıra küçültme ve kolon küçültme işlemi yapılır.

- İkinci aşamada çözüm, yinelemeli olarak optimize edilir.

Macar yöntemi nedir?

Macar yöntemi dört adımdan oluşur. İlk iki adım yalnızca bir kez yürütülürken, 3. ve 4. adımlar, optimum bir tahsis bulunana kadar tekrar edilir.

Yalnızca negatif olmayan öğeler içermesi gereken, n x n sıralı bir kare matris girdi verileri olarak kabul edilir.

Belirli bir problem için, matristeki satır sayısı sütun sayısına eşit değilse, duruma bağlı olarak bir kukla satır veya bir kukla sütun eklenmelidir. Bu sahte hücreler için tahsis maliyetleri her zaman sıfır olarak tahsis edilir.

Adım 1: Her satırın minimumlarını çıkarın

Dizideki her satır için, en düşük değere sahip öğe seçilir ve o satırdaki her öğeden çıkarılır.

Adım 2: Her bir sütundan minimum değerleri çıkarın

Benzer şekilde, en düşük değere sahip öğe her sütun için seçilir ve o sütundaki her öğeden çıkarılır.

3. Adım: Tüm sıfırları minimum sayıda satırla kapatın

2. adımdan kaynaklanan matristeki tüm sıfırlar, minimum sayıda yatay ve dikey çizgi kullanılarak, satırlar veya sütunlar ile kaplanmalıdır.

Tüm sıfırları kaplamak için toplam n satır gerekiyorsa, burada n, matrisin n çarpı n boyutuna eşittir, sıfırlar arasında optimum bir tahsis elde edilecek ve bu nedenle algoritma duracaktır.

Aksi takdirde, dizideki tüm sıfırları kapatmak için n'den az satır gerekiyorsa, 4. adıma geçin.

4.Adım: Fazladan sıfırlar oluşturun

3. adımda yapılan satırlardan biri tarafından kapsanmayan matrisin (k olarak adlandırılır) en küçük öğesi seçilir.

K'nin değeri, çizgilerle kapsanmayan tüm öğelerden çıkarılır. Ardından, iki çizginin kesişimiyle kapsanan tüm öğelere ka değeri eklenir.

Tek bir satırın kapsadığı öğeler olduğu gibi bırakılır. Bu adımı gerçekleştirdikten sonra 3. adıma dönersiniz.

Optimal tahsis

Algoritma 3. adımda durdurulduktan sonra, her satır ve her sütunda yalnızca bir sıfır seçilecek şekilde bir dizi sıfır seçilir.

Bu seçim sürecinde bir satırda veya sütunda tek bir sıfır yoksa, o zaman bu sıfırlardan biri seçilecektir. Bu sütun veya satırdaki kalan sıfırlar, diğer atamalar için de aynı şekilde tekrarlanarak kaldırılır.

Tek bir sıfır ataması yoksa, birden fazla çözüm vardır. Ancak, farklı atamalar için maliyet aynı kalacaktır.

Eklenen tüm kukla satırlar veya sütunlar kaldırılır. Bu son matriste seçilen sıfırlar bu nedenle orijinal matriste gereken ideal atamaya karşılık gelir.

Misal

Dört işçi (T1, T2, T3, T4) tarafından gerçekleştirilmesi gereken dört faaliyetin (A1, A2, A3, A4) olduğu bir şirket düşünelim. Çalışan başına bir etkinlik atanmalıdır.

Aşağıdaki matris, belirli bir çalışanı belirli bir faaliyete atamanın maliyetini gösterir. Amaç, bu dört faaliyetten oluşan görevin toplam maliyetini en aza indirmektir.

Adım 1: Her satırın minimumlarını çıkarın

Her satırda minimum değere sahip öğeyi o satırdaki diğer öğelerden çıkararak başlarsınız. Örneğin ilk sıradaki en küçük eleman 69'dur. Bu nedenle ilk sıradaki her bir elemandan 69 çıkarılır. Ortaya çıkan matris:

Adım 2: Her bir sütundan minimum değerleri çıkarın

Aynı şekilde, her sütunun minimum değerine sahip eleman, o sütunun diğer elemanlarından çıkarılır ve aşağıdaki matris elde edilir:

3. Adım: Tüm sıfırları minimum sayıda satırla kapatın

Şimdi matristeki tüm sıfırları örtmek için gereken minimum çizgi sayısını (yatay veya dikey) belirleyeceğiz. Tüm sıfırlar 3 satır kullanılarak kapatılabilir:

Gereken satır sayısı üç olduğu ve matrisin boyutundan (n = 4) küçük olduğu için 4. adıma devam ediyoruz.

4.Adım: Fazladan sıfırlar oluşturun

Çizgilerin kaplamadığı en küçük eleman seçilir, değeri 6'dır. Bu değer kapsanmayan tüm elemanlardan çıkarılır ve bu aynı değer iki çizginin kesiştiği tüm elemanlara eklenir. Bu, aşağıdaki matrisle sonuçlanır:

Macar yönteminde belirtildiği gibi, üçüncü adımın tekrar gerçekleştirilmesi gerekir.

3. Adım (tekrarlayın)

Yine matristeki tüm sıfırları örtmek için gereken minimum satır sayısı belirlenir. Bu sefer dört satır gereklidir:

Gereken satır sayısı matrisin boyutuna (n = 4) eşit 4 olduğu için, matristeki sıfırlar arasında optimal bir tahsisimiz vardır. Bu nedenle algoritma durur.

Optimal tahsis

Yöntemin belirttiği gibi, aşağıdaki sıfırlardan yapılan seçim, optimal bir atamaya karşılık gelir:

Bu sıfır seçimi, orijinal maliyet matrisinde aşağıdaki optimum tahsise karşılık gelir:

Bu nedenle, işçi 1 etkinlik 3, işçi 2, etkinlik 2, işçi 3, etkinlik 1 ve işçi 4 etkinlik 4 gerçekleştirmelidir. Bu optimum atamanın toplam maliyeti 69 + 37 + 11 + 23 = 140.

Referanslar

1. Macar Algoritması (2019). Macar algoritması. Hungarianalgorithm.com adresinden alınmıştır.
2. Çalışma (2019). Atama Problemlerini Çözmek İçin Macar Algoritmasını Kullanma. Alındığı kaynak: study.com.
3. Bilgelik İşleri (2018). Ödev Problemini Çözmek İçin Macar Yöntemi - Yönetim için Kantitatif Teknikler. Alınan: wisdomjobs.com.
4. Geeks için Geeks (2019). Atama Problemi için Macar Algoritması. Geeksforgeeks.org sitesinden alınmıştır.
5. Karleigh Moore, Nathan Landman (2019). Macar Maksimum Eşleştirme Algoritması. Parlak. Brilliant.org'dan alınmıştır.