Atama Problemi Nedir?

Atama problemi, klasik bir kombinatoryal optimizasyon problemidir: işçiler ve görevler kümesi verildiğinde, her biri ilişkili bir maliyetle, toplam maliyeti en aza indiren bire bir eşleştirmeyi bulun. Planlama, lojistik, kaynak tahsisi ve operasyon araştırması gibi alanlarda doğal olarak ortaya çıkar — iki grubu mümkün olan en verimli şekilde eşleştirmeniz gereken herhangi bir durum.

Problem Macar algoritması (Munkres algoritması olarak da adlandırılır) ile çözülür; 1950'lerde geliştirilen verimli bir yöntemdir. Her permütasyonu değerlendirmesi gereken kaba kuvvet yaklaşımlarından farklı olarak, Macar algoritması optimal çözümü polinom zamanda bulur ve bunu orta ölçekli matrisler için bile pratik hale getirir.

Araç Açıklaması

Her işçiyi her göreve atama maliyetini temsil eden bir maliyet matrisi girin, ardından optimal atamayı anında bulmak için Çöz düğmesine tıklayın. Araç, toplam maliyeti en aza indiren işçi-görev çiftlerini vurgular ve sonucu optimal toplam maliyet ile birlikte açık bir tabloda görüntüler.

Örnekler

Giriş matrisi (3 işçi × 3 görev):

Görev 1 Görev 2 Görev 3
İşçi 1 400 150 400
İşçi 2 400 450 600
İşçi 3 300 225 300

Optimal atamalar:

İşçi Görev Maliyet
İşçi 1 Görev 2 150
İşçi 2 Görev 1 400
İşçi 3 Görev 3 300

Toplam maliyet: 850

Özellikler

  • Düzenlenebilir matris — işçileri, görevleri ve maliyetleri doğrudan tabloda yeniden adlandırmak için herhangi bir hücreye veya sütun başlığına tıklayın
  • Yapılandırılabilir boyut — 2×2'den 8×8'e kadar matrisleri destekler
  • Anında sonuçlar — Macar algoritması tarayıcıda sunucu gidiş-dönüşü olmadan çalışır

Nasıl Çalışır?

Araç, atama problemini optimal olarak çözmek için Munkres (Macar) algoritmasını kullanır. Girdilerinizden bir maliyet matrisi oluşturur, bir dizi satır ve sütun indirgeme adımı uygular ve tam bir optimal atama belirlenene kadar yinelemeli olarak sıfırların maksimum eşleşmesini bulur. Zaman karmaşıklığı $O(n^3)$'tür; burada $n$ matris boyutudur.

Kare olmayan matrisler için (daha fazla işçi veya görev), algoritma her işçi ve her görevin eşleştirilmesi için matrisi sıfırlarla doldurur.

Seçenekler Açıklandı

  • İşçi sayısı / satırlar — maliyet matrisinde kaç satır görüneceğini kontrol eder (2–8)
  • Görev sayısı / sütunlar — maliyet matrisinde kaç sütun görüneceğini kontrol eder (2–8)
  • Maliyet matrisi hücreleri — belirli bir işçiyi belirli bir göreve atama maliyetini girin; herhangi bir sayısal değer kabul edilir

Sınırlamalar

  • Matris boyutu 8×8 ile sınırlıdır (64 hücre)
  • Algoritma toplam maliyeti en aza indirir; maksimize etmek için (örneğin, kâr matrisleri için), değerleri girmeden önce olumsuzlayın
  • Sayısal olmayan hücre değerleri sıfır olarak kabul edilir