Doğrusal Programlamada Atama Problemi: Giriş ve Atama Modeli

Atama problemi, çeşitli kaynakların çeşitli aktivitelere birebir tahsis edilmesiyle ilgilenen özel bir tür doğrusal programlama problemidir. Bu şekilde, sürece dahil olan maliyet veya zamanın minimum, kar veya satışın maksimum olduğu şekilde yapar. Her ne kadar orada problemler simpleks metodu veya ulaşım metodu ile çözülebilir, ancak atama modeli bu problemler için daha basit bir yaklaşım sunar.

Bir fabrikada, bir denetim otoritesinde altı işçi ve altı işten kovulabilir. Hangi işçiye hangi işin verilmesi gerektiğine karar vermesi gerekecek. Sorun bire bir temel oluşturur. Bu bir atama problemidir.

1. Atama Modeli:

Burada n kolaylıklar olduğunu ve n işlerin bu durumda n atamanın olacağı açık olduğunu varsayalım. Her tesis veya çalışan, her işi birer birer yapabilir. Ancak, kârın en üst düzeye çıkarılması ya da maliyet ya da zamanın asgariye indirilmesi için atamanın yapılması gereken belli bir prosedür olmalıdır.

Tabloda _Coj, 4. işin çalışana atanmasının maliyeti olarak tanımlanmaktadır. Burada, satır sayısı sütun sayısına eşit olduğunda bunun özel bir taşıma problemi olduğu belirtilebilir.

Matematiksel Formülasyon:

Bir Atama probleminin herhangi bir temel uygulanabilir çözümü, (n - 1) değişkenlerinin sıfır, n'nin iş sayısı veya tesis sayısı olduğu (2n - 1) değişkenlerinden oluşur. Bu yüksek yozlaşma nedeniyle, sorunu her zamanki taşıma yöntemiyle çözersek, karmaşık ve zaman alıcı bir iş olacaktır. Böylece bunun için ayrı bir teknik elde edilir. Mutlak yönteme geçmeden önce sorunu formüle etmek çok önemlidir.

Diyelim ki x _jj, olarak tanımlanmış bir değişkendir.

1. iş, makine veya tesise verilirse

0 işi, makine veya tesise atanmamışsa 0.

Şimdi sorun bire bir temel oluşturduğundan veya bir iş bir tesise veya makineye verilecekse.

Toplam atama maliyeti

Yukarıdaki tanım, matematiksel modele şu şekilde geliştirilebilir:

X _ij > 0 (i, j = 1, 2, 3… n) 'i belirlemek için

Kısıtlamalara tabi

ve _xj, sıfır veya birdir.

Problemi Çözme Yöntemi (Macar Tekniği):

Küçültme türünün nesnel işlevini düşünün. Bu Atama probleminin çözümünde aşağıdaki adımlar yer almaktadır,

1. İlk satırdan başlayarak verilen masraf tablosunun her satırındaki en küçük masraf öğesini bulun. Şimdi, bu en küçük eleman o sıranın her elemanından çıkarılır. Böylece, bu yeni tablonun her satırında en az bir sıfır alacağız.

2. Masayı kurduktan sonra (adım 1 ile) masanın sütunlarını alın. İlk sütundan başlayarak, her sütundaki en küçük maliyet öğesini bulun. Şimdi bu en küçük elemanı o sütunun her elemanından çıkarın. Adım 1 ve adım 2'yi gerçekleştirdikten sonra, azaltılmış maliyet tablosundaki her bir sütunda en az bir sıfır alacağız.

3. Şimdi, indirgenmiş tablo için atamalar aşağıdaki şekilde yapılır.

(i) Satırlar, tam olarak tek (bir) sıfır bulunan satır bulunana kadar art arda incelenir. Bu tek sıfıra, etrafına kare zero koyarak atama yapılır ve karşılık gelen sütunda, diğer tüm sıfırlar (x) çarpılır, çünkü bunlar bu sütunda başka bir atama yapmak için kullanılmaz. Her satır için adım uygulanır.

(ii) 3. Adım (i) şimdi aşağıdaki gibi sütunlarda gerçekleştirilir: - sütunlar, tam olarak bir sıfır bulunan bir sütun bulunana kadar art arda incelenir. Şimdi, kareyi etrafına koyarak bu tek sıfıra atama yapılır ve aynı anda karşılık gelen satırlardaki diğer tüm sıfırlar çarpılır (x) her sütun için adım yapılır.

(iii) Adım 3, (i) ve 3 (ii), tüm sıfırlar işaretleninceye veya çarpılana kadar tekrarlanır. Şimdi, işaretli sıfırların sayısı veya yapılan atamalar satır veya sütunların sayısına eşitse, optimum çözüm elde edilmiştir. Herhangi bir atama olmadan her bir sütun veya sütunlarda tam olarak tek bir atama yapılacaktır. Bu durumda 4. adıma geçeceğiz.

4. Bu aşamada, 3. adımda elde edilen matristeki tüm sıfırları kaplamak için gereken minimum satır sayısını (yatay ve dikey) çizin. Aşağıdaki prosedür kabul edilir:

(i) Onay işareti (

(ii) Şimdi onay işareti (

(iii) Şimdi işaretlenmemiş ve işaretlenmiş sütunlarda atamaları olan tüm satırları işaretleyin.

(iv) Tüm adımlar yani (4 (i), 4 (ii), 4 (iii), daha fazla satır veya sütun işaretlenene kadar tekrar edilir.

(v) Şimdi işaretlenmemiş tüm satırlardan ve işaretli sütunlardan geçen düz çizgiler çizin. Bir nxn matrisinde, her zaman 'n' çizgisinden daha azının aralarında bir çözüm yoksa tüm sıfırları kapsayacağı da fark edilebilir.

5. 4. adımda, çizilen satır sayısı n veya satır sayısına eşitse, o zaman değilse optimum çözümdür, o zaman 6. adıma gidin.

6. Tüm ele geçen öğeler arasından en küçük olanı seçin. Şimdi, bu eleman ele geçen tüm elemanlardan çıkarılır ve iki çizginin kesişiminde bulunan elemana eklenir. Bu yeni ödevlerin matrisidir.

7. Atamaların sayısı, satır sayısına veya sütun sayısına eşit oluncaya kadar (3) adımındaki prosedürü tekrarlayın.