YBS401U-YÖNEYLEM ARAŞTIRMASI
Ünite 5: Atama Problemleri
Atama Probleminin Tanımı ve Uygun Çözümleri
Atama problemleri, bir planlama periyodunda yapılması planlanan işleri, farklı fiyat veya verimlilik göstergesi ile yapabilecek farklı kişilere veya şirketlere, toplam verimliliği en büyükleyecek atamanın gerçekleştirilmesi problemi olarak tanımlanmaktadır.
Atama problemi, Yöneylem Araştırmasının çok özel problemlerinden biri olup, işlerin çalışanlara atanması, çalışanların iş yerlerine atanması, makinelerin uygun yerlere yerleştirilmesi, işlerin zamana göre planlanması, derslerin dersliklere atanması, şoförlerin araçlara atanması ve bunun gibi birçok problemin çözülmesi için kullanılabilmektedir.
Atama problemleri, genellikle “Atanacaklar” ve “Görevler” terimleri üzerine oluşturulmakta ve şu özellikleri içermektedir:
1. Atanacakların sayısı görevlerin sayısına eşit olmalıdır (bu sayı genellikle n ile ifade edilir). 2. Her atanacak sadece bir göreve atanmalıdır. 3. Her görev sadece bir atanacak tarafından gerçekleştirilmelidir. 4. i. atanacağın j. göreve atanmasından elde edilecek verimlilik değeri cij ile gösterilecektir. Bu durumda problemin amaç fonksiyonunun en büyüklenmesi istenecektir. cij sayıları problemin tanımlanma şekline göre faydalılığı (en büyükleme), maliyeti (en küçükleme), zamanı, uzaklığı da gösterebilmektedir. Toplam verimliliği en yüksek kılan bir uygun atama, problemin en iyi çözümü olarak kabul edilecektir
(Kitabınızın 130. sayfasında yer alan Örnek 5.1 çözümüne bakınız).
Bir atama probleminde en yüksek toplam faydalılık (veya verimlilik) değerine karşı gelen bir atama örneği her zaman en iyi atama örneği olamayabilir. En iyi atamanın bulunabilmesi için sadece uygun atamalar içerisinde amaç fonksiyonuna en iyi değeri sağlayan atamanın seçilmesi gerekmektedir.
Bir atama probleminde en yüksek toplam faydalılık (veya verimlilik) değerine karşı gelen birden fazla uygun atama örneği varsa, bunların her birine alternatif çözümler denir.
Atama Probleminin Matematiksel Modeli
Ele alınan bir matematiksel modelinin oluşturulmasında kolaylık sağlayacak ve dahası bu modelin kolay anlaşılmasını da sağlayacak kurallar:
• Probleme ait verilerin bir parametre kümesi şeklinde tanımlanması ve parametrelerin tanımlanması için kullanılan indis kümelerinin belirlenmesi. • Karar değişkenlerinin belirlenmesi ve açık bir şekilde tanımlanması.
• Parametre ve karar değişkenlerini tanımlarken, aynı indislerin hep aynı parametre ve aynı karar değişkenleri için kullanılması. • Problemin sözel tanımının kullanılarak, amaç fonksiyonu veya amaç fonksiyonlarının ve kısıtlarının, karar değişkenleri ve parametreler kullanılarak matematiksel olarak formüle edilmesi.
Atama problemine ait indis kümeleri ve parametreler:
• Atanacaklar: i = 1, ..., n; • Görevler: j = 1, ..., n; • cij = i. atanacağın j. göreve atanmasının maliyeti. Örneğin, i. atanacağın j. görevi yapma maliyeti
Atama problemine ait karar değişkenleri:
• xij = {1, eğer i. atanacak j. göreve atanırsa; 0, diğer durumlardan}
Problemin sözel tanımında, cij parametreleri, i atanacağın j görevi yapma maliyeti olarak tanımlandığından, amaç fonksiyonumuz toplam maliyetin en küçüklenmesi olarak ifade edilmelidir.
Problemin amaç fonksiyonu aşağıdaki şekilde formüle edilir:
En küçükle
! 𝑓(𝑥) = 𝑐!"𝑥!" !!!
Atama problemin tanımında talep edilen, “her atanacak sadece bir göreve atanmalı” ve “her bir görev sadece bir atanacak tarafından yapılmalı” koşullarının matematiksel ifadesi:
Her atanacak sadece bir göreve atanmalı:
!
𝑥!" = 1, ℎ𝑒𝑟 𝑗 = 1, . . . , 𝑛. !!!
Bu eşitlik, her bir j = 1, ..., n görevi için, tüm atanacaklar içinde sadece bir tane i indisine karşı gelen xij değişkeninin 1 değeri almasına izin verecek, diğerlerinin değeri 0 olacaktır.
Her bir görev sadece bir atanacak tarafından yapılmalı koşulu aşağıdaki şekilde ifade edilebilir:
!
𝑥!" = 1, ℎ𝑒𝑟 𝑖 = 1, . . . , 𝑛. !!!
Bu eşitlik, her bir i = 1, ..., n atanacağı için, tüm görevler içinde sadece bir tane j indisine karşı gelen xij değişkeninin 1 değeri almasına izin verecek, diğerlerinin değeri 0 olacaktır.
Atama problemin karar değişkenleri sadece 0 veya 1 değeri alabildiğinden, bu problem bir doğrusal programlama problemi değildir, sebebi ise bir doğrusal
programlama probleminin karar değişkenlerinin sağlaması gereken “Bölünebilirlik Varsayımının” sağlanmamasıdır. Karar değişkenlerinin bu özelliğinden dolayı, Atama problemi 0 – 1 programlama problemi olarak adlandırılmaktadır.
Atama probleminde herhangi bir “(atanacak-görev)” veya eşdeğer bir şekilde bir (i, j) çifti incelendiğinde, her bir i atanacağı için sadece bir j değerinde ve tersine her bir j görevi için sadece bir i değerinde, xij karar değişkeni 1 değerini alacak ve sadece bu (i, j) çiftlerine karşı gelen cij değerleri amaç fonksiyonuna katkı sağlayacaktır. Bu yüzden toplam “katkı” (faydalılık veya maliyet) sadece xij = 1 durumları için hesaplanmış olacaktır.
(Kitabınızın 134. sayfasında Örnek 5.1’deki problemin matematiksel model ile çözümüne bakınız).
Atama Probleminin Çözümü İçin Macar Algoritması
Macar algoritması, bu bölümde açıklanan şekli ile amaç fonksiyonu en küçükleme olan atama problemlerinin çözümünü bulmak için tasarlanmıştır. Fakat bu algoritmayı aşağıdaki geçiş formülü kullanılarak kolaylıkla en büyükleme problemlerini çözmek için de uyarlayabiliriz.
En büyükleme ve en küçükleme problemleri arasında eş değer dönüşüm formülü:
Enb f(x) = –Enk (– f (x)) veya – Enb f(x) = Enk (– f (x))
Macar Algoritması
1. Her satırdaki en küçük sayı (maliyeti) o satırın tüm diğer sayılarından (maliyetlerinden) çıkartılır. Bu işleme satır indirgeme işlemi denir. Böylece, “0”lar içeren bir tablo elde edilir. 2. Eğer oluşmuş tablo her satır ve her sütununda en az bir tane 0 elemana sahip değilse, o zaman her sütundaki en küçük sayı o sütunun diğer sayılarından çıkartılır. Bu işleme sütun indirgeme denir. Bu şekilde her satırında ve her sütununda “0”lar olan bir tablo elde edilir. 3. Satır ve sütun indirgeme işlemi yapılmış tablodaki sıfırlar en az sayıda yatay ve dikey çizgilerle kapatılır. Eğer bu çizgilerin sayısı satır veya sütun sayısına eşit ise, en iyi çözüme ulaşılmış demektir. Eğer çizgi sayısı satır ve sütun sayısından az ise algoritmaya aşağıdaki adımla devam edilir. 4. Doğrularla çizilmiş tablodaki çizilmemiş elemanlardan en küçük olanı diğer çizilmemiş tüm elemanlardan çıkartılır, üzeri tek çizgi ile çizilen satır ve sütundaki elemanlar değişmez, fakat bu en küçük sayı, çizgilerin kesiştiği kutucuktaki elemanlara eklenir. Böylece, yeni bir tablo elde edilir ve 3. adımdaki gibi sıfırlar en az sayıda yatay ve dikey çizgilerle kapatılır. Bu şekilde, tablodaki “0”lar satır veya sütuna eşit sayıda çizgilerle kapatıldığında algoritma
sonlandırılır. Algoritma sonlandırıldığında en iyi atama, sıfır elemanların bulunduğu kutucuklara atama yapılarak gerçekleştirilir.
Sütun indirgeme işleminden sonra elde edilen tabloda her satır ve sütunda birden fazla sıfır olduğu durumlarda atamanın, problemin temel koşullarından biri olan her makine bir yere ve her bir yere de bir makine atanmalı koşulunu dikkate alarak gerçekleştirilmesi gerekmektedir.
(Kitabınızın 138, 139 ve 140. sayfasında yer alan Örnek 5.2, Örnek 5.3 ve Örnek 5.4 çözümlerine bakınız).