Yöneylem Araştırması Deneme Sınavı Sorusu #850678

I. Her satırdaki en küçük cij seçilip, diğer atama giderlerinden bu değer çıkartılarak, satırlara göre indirgenmiş tablo bulunur.

II. Tablo üzerinde sıfır değerini alan tüm ögelerden geçen en az sayıda dikey ya da yatay doğrular çizilir. 

III. İndirgenmiş tablonun her sütunundaki en küçük cij seçilip, diğer ögelerden bu değer çıkartılarak, tablo indirgenir.

IV. Üzerinden doğru geçmeyen satır veya sütundaki en küçük öge seçilerek, doğrular dışında kalmış diğer ögelerden bunun değeri çıkartılır, doğruların kesim noktalarındaki ögelere eklenir. 

V. Her doğru üzerinde sıfır değerli hücreler esas alınarak, her i için yalnız bir j olmak üzere, eniyi çözüme karşı gelen xij değerleri yazılıp, eniyi çözüm bulunur.

Yukarıya göre Macar algoritması ile çözüm adımlarının doğru sırası aşağıdaki seçeneklerden hangisinde bulunmaktadır?


I, II, III, IV, V

I, II, III, V, IV

I, III, IV, II, V

I, III, II, IV, V

I, III, II, V, IV


Yanıt Açıklaması:

Bir atama modelinin Macar algoritması ile çözüm adımları aşağıda
verilmektedir:
1. Her satırdaki en küçük cij seçilip, diğer atama giderlerinden bu değer çıkartılarak, satırlara göre indirgenmiş tablo bulunur.
2. İndirgenmiş tablonun her sütunundaki en küçük cij seçilip, diğer ögelerden bu değer çıkartılarak, tablo bir kez daha indirgenir.
3. Tablo üzerinde sıfır değerini alan tüm ögelerden geçen en az sayıda dikey ya da yatay doğrular çizilir. Eğer bulunan doğru sayısı = n ise, eniyi çözüme ulaşılmış olup adım beşe, değilse izleyen adıma geçilir.
4. Üzerinden doğru geçmeyen satır veya sütundaki en küçük öge seçilerek, doğrular dışında kalmış diğer ögelerden bunun değeri çıkartılır, doğruların kesim noktalarındaki ögelere eklenir. Üçüncü adıma dönülür.
5. Her doğru üzerinde sıfır değerli hücreler esas alınarak, her i için yalnız bir j olmak üzere, eniyi çözüme karşı gelen xij değerleri yazılıp, eniyi çözüm bulunur.

Yorumlar
  • 0 Yorum