Yöneylem Araştırması 1 Deneme Sınavı Sorusu #729423
Şekilde kaynak-hedef atama problemi görülmektedir. Her kaynağın bir hedefe atanması zorunludur ve her kaynak yalnız bir hedefe atanabilir. Dengelenmemiş bir atama problemi olduğunun ve en iyi çözümü için, yapay hedef ya da kaynak eklemesi yapılacağına dikkat ediniz. Problem, macar algoritması ile çözüldüğünde en uygun çözüm aşağıdakilerden hangisidir?
|
1. kaynak - 1. hedef 2. kaynak - 3. hedef 3. kaynak - 4. hedef |
|
1. kaynak - 2. hedef 2. kaynak - 3. hedef 3. kaynak - 4. hedef |
|
1. kaynak - 1. hedef 2. kaynak - 2. hedef 3. kaynak - 4. hedef |
|
1. kaynak - 3. hedef 2. kaynak - 1. hedef 3. kaynak - 4. hedef |
|
1. kaynak - 3. hedef 2. kaynak - 4. hedef 3. kaynak - 2. hedef |
Probleme yapay kaynak ataması yapılacağına dikkat ediniz. Her satırdan en küçük maliyet çıkartıldığında,
3 4 2 0
4 3 6 0
10 0 3 7
0 0 0 0 tablosuna ulaşılır.
Her sütundan en küçük değerler çıkarıldığında tekrar aynı tabloya ulaşılır. 0 değerlerinin üstü çizgi ile kapatılması için 3 çizgi yeteceğinden dolayı,üzerinde çizgi olmayan değerlerden en küçük değer çıkarılır.
1 2 0 0
2 1 4 0
10 0 3 7
0 0 0 0 tablosuna ulaşılır. 4 çizgi ile 0 değerleri kapatılabildiği için 1. kaynak 3. hedefe, 2. kaynak 4. hedefe ve 3. kaynak 2. hedefe atanır. 4. sonradan eklenen yapay kaynak 1. hedefe atandığı için, 1. hedefe hiçbir kaynağın atanmadığı görülür.
Yanıt E seçeneğidir.
Yorumlar
- 0 Yorum