Bu Ünitede Neler Öğrendik?myders hazırladı
Bu bölümde, sıfır-bir tamsayılı programlama problemlerinin özel bir türü olan atama probleminin tanımı ve uygun çözümleri ele alınmıştır. Temel mantığı n adet kaynağın n adet göreve bire bir atanması olan bu problemler, toplam maliyeti en küçüklemek veya toplam faydayı en büyüklemek amacıyla kurulur. Atanan kutucuklara bir, atanmayanlara sıfır yazılarak matris formunda gösterilen bu planların toplam uygun çözüm sayısı n faktöriyel ile hesaplanır. Her zaman en yüksek puanlı göreve atama yapmanın en iyi çözüm olmayabileceği, bu nedenle amaç fonksiyonu ile kısıtlar arasında ödünleşim kurulması gerektiği vurgulanmıştır.
Devamında atama probleminin matematiksel modeli detaylandırılmıştır. İndis kümeleri, parametreler ve sıfır-bir karar değişkenleri tanımlanarak; toplam maliyetin en küçüklenmesi veya toplam faydanın en büyüklenmesi şeklindeki amaç fonksiyonları açıklanmıştır. Modeldeki kısıtların, her kaynağın sadece bir göreve atanması ve her görevin sadece bir kaynak tarafından yapılması kurallarından oluştuğu belirtilmiştir. Karar değişkenlerinin sıfır veya bir değerini alması zorunluluğu nedeniyle bölünebilirlik varsayımını sağlamayan bu yapının bir sıfır-bir programlama problemi olduğu ve standart simpleks yöntemiyle doğrudan çözülemediği ifade edilmiştir.
Son olarak Macar algoritması ile çözüm yöntemine yer verilmiştir. Maliyet matrisi üzerinde satır ve sütun indirgeme işlemleri yapılarak sıfır değerlerinin oluşturulduğu bu özel yöntemde, en büyükleme problemlerinin uygun işlemlerle en küçükleme formuna dönüştürülebildiği gösterilmiştir. Sıfırları kapatacak en az sayıda çizgi çekilmesi, çizgi sayısının n'e eşitlenmesi durumunda çözümün tamamlanması ve n'den az olması durumunda iterasyonların sürdürülmesi adımları açıklanmıştır. Algoritma sonlandığında sıfırların bulunduğu hücrelere atamalar yapılarak en iyi çözüme ulaşıldığı ve alternatif en iyi çözümlerin var olabileceği özetlenmiştir.