Macar yöntemi, doğrusal programlamaya dayalı bir optimizasyon probleminde maliyetlerin minimize edilmesini sağlayan bir algoritmadır.
Macar yönteminin amacı, en uygun kişiler tarafından yapılması gereken bir dizi görevin minimum maliyetini bulmaktır.
Otomatikleştirilebilen bir dizi adımı gerçekleştirmek için doğrusal programlama (PL) kullanır. Bu nedenle, istatistiksel yazılım R (diğerlerinin yanı sıra) gibi araçlar, bu optimizasyon problemleri için birkaç çok faydalı pakete sahiptir.
Macar yönteminin kökeni
Yaratıcısı, 1955'te Macar matematikçi (dolayısıyla adı) Harold W. Kuhn'du. Bir başka matematikçi olan James Munkres, 1957'de revize etti. Bu evrim ile Munkres veya Kuhn-Munkres tahsis algoritması gibi başka isimler aldı. .
Öte yandan, bu yöntemin hem Yahudiler hem de Macarlar olan Dénes König ve Jenő Egerváry adlı iki yazarda bir emsali vardır. İlki, bu algoritmanın dayandığı grafik teorisini geliştirdi. İkinci genelleştirilmiş König teoremi ve Kuhn'un yöntemi geliştirmesine izin verdi.
Macar yönteminin adımları
İzlenecek adımlar, bir elektronik tablo kullanarak Macar yöntemini basit bir şekilde gerçekleştirmeyi sağlar. Ayrıca göstereceğimiz bu şema, son örnekte detaylı olarak geliştireceğimiz süreci global bir şekilde görmemizi sağlayacaktır.
- Ön adım olarak, bir dizi projeye (sütunlar) kişileri (satırları) atamanız gerekir. Ayrıca her projenin kimin tarafından gerçekleştirildiğine bağlı olarak farklı maliyetlerini hesaplamak ve bu bilgilerle bir matris (C) oluşturmak gerekir.
- (C) matrisinde her satırın minimum değerini ararız. Bunu satırdaki tüm elemanlardan çıkarıyoruz ve aynı işlemi sütunlarla yapıyoruz. Önceki işlemlerin sonuçlarıyla birlikte yeni bir matris (C`) görünecektir.
- Ardından, görevleri ve projeleri en düşük maliyetle seçmemizi sağlayan «eşitlikler grafiğini» oluşturuyoruz. Optimum, sonucu sıfır olan öğeler olacaktır. Birden fazla satıra sıfır değeri atanmış bir elemanın olmadığı doğruysa algoritma sona erer.
- Aksi takdirde, yeni bir atama yapılmalıdır. Örnekte göreceğimiz gibi, bir dizi değişikliğin uygulandığı yeni bir matris yapılır. Grafiği yeniden oluşturuyoruz ve her satırda ve tekrarlanmayan konumlarda en az bir sıfır olan bir matris elde edene kadar devam ediyoruz.
- Bu bilgiyle, sorunu optimize eden kişilere ve projelere (sıfırlar) zaten sahibiz. Bir görev önceki satırda zaten atanmışsa, sonraki satırda atılır. Minimum maliyeti hesaplamak için, bu sıfırların konumunda görünen başlangıç matrisinin maliyetlerini ekliyoruz.
Macar yöntemi örneği
Macar yönteminin basit bir örneğine bakalım. Üç çalışanımız olduğunu ve üç projeye atanmaları gerektiğini düşünelim. Her hücrede başlangıç matrisini (C) ve maliyet değerlerini oluşturuyoruz. Bunun için şirkette bulunan bilgileri kullanmanız gerekir. Bütün bunları yaptıktan sonra işleme başlıyoruz. Bir elektronik tablo yardımcı olabilir.
Her satırın minimumlarını hesaplıyoruz ve bunları o satırın elemanlarından çıkarıyoruz ve aynısını sütunlar için yapıyoruz (1. ve 2. adımlar). Ortaya çıkan matriste (C`) tüm sıfırları kaplayacak ve sırayla birbirini kesecek şekilde çizgiler çiziyoruz (3. adım). İki satır olduğunu görüyoruz, ancak satır veya sütun sayısının en büyük değeri üç. Devam etmeliyiz.
Şimdi ortaya çıkan sayıların en küçüğünü seçiyoruz, bu örnekte iki (koyu mavi). Onu öncekilerden çıkarırız ve çizgilerin kesiştiği yerde bulunanlara ekleriz. Bizim durumumuzda iki tane daha var (E3, T1). Yeni bir matrisle kaldık (4. adım). Çizgileri yeniden çizip sayıyoruz. Satır veya sütun sayısıyla aynı olan üç satır vardır. Algoritma tamamlandı.
En az sıfıra sahip satır veya sütunla başlıyoruz (E1, T1). Bir görev zaten atanmışsa yeniden atanamaz, örneğin E2 ile bu görev E1'e atandığından T1'in ilk sıfırını kullanamazsınız. Macar yönteminde toplam maliyet, seçilen sıfırlarla (adım 5) aynı konumda bulunan orijinal matrisin (Adım 1) maliyetlerinin toplamı olacaktır.