Ders kitabının açık uçlu alıştırmaları. Bunlar çoktan seçmeli sınav sorusu değil — düşünmeni, araştırmanı, kendi cümlelerinle anlatmanı isteyen etkinlikler. Kitabın verdiği örnek yanıtlar kapalı duruyor; önce kendin dene.
Alıştırma 1myders hazırladı
Atama problemleri ile klasik doğrusal programlama modelleri arasındaki temel farkı bölünebilirlik varsayımı açısından karşılaştırınız.
Yanıt / ipucu
Klasik doğrusal programlama problemleri kesirli (bölünebilir) değerler alabilirken, atama problemleri 0-1 tamsayılı karar değişkenleri içerdiği için bölünebilirlik varsayımını sağlamaz ve bu yüzden özel yöntemler gerektirir.
Alıştırma 2myders hazırladı
3 adet makine ve 3 adet iş için olası tüm uygun çözüm sayısını hesaplayarak matris formundaki gösterim mantığını açıklayınız.
Yanıt / ipucu
Uygun çözüm sayısı n! formülü ile bulunur; 3! = 6 farklı çözüm vardır. Matris formunda atanan eşleşmelere 1, atanmayanlara 0 yazılarak her satır ve sütunda sadece bir adet 1 olması sağlanır.
Alıştırma 3myders hazırladı
Amaç fonksiyonu toplam faydayı en büyüklemek olan bir atama problemini, Macar algoritmasını kullanabilmek için nasıl dönüştürebileceğinizi örnek vererek tartışınız.
Yanıt / ipucu
Macar algoritması genellikle en küçükleme (maliyet) için tasarlanmıştır. Bu yüzden fayda matrisindeki tüm değerler -1 ile çarpılarak veya matristeki en büyük değerden çıkarılarak maliyet matrisine dönüştürülmelidir.
Alıştırma 4myders hazırladı
Macar algoritmasının ilk iki adımı olan satır ve sütun indirgeme işlemlerini 3x3'lük hayali bir maliyet matrisi üzerinde uygulayarak adım adım gösteriniz.
Yanıt / ipucu
Önce her satırdaki en küçük elemanı o satırdaki tüm elemanlardan çıkarın. Ardından elde edilen yeni matrisin her sütunundaki en küçük elemanı sütun elemanlarından çıkararak matriste sıfırlar oluşturun.
Alıştırma 5myders hazırladı
Neden her zaman en yüksek puanlı veya en ucuz bireysel göreve atama yapmanın toplam optimum çözümü vermediğini bir ödünleşim (trade-off) kavramı üzerinden açıklayınız.
Yanıt / ipucu
Bireysel olarak en iyi görünen atamayı yapmak, diğer kaynak ve görevlerin kısıtlarını olumsuz etkileyebilir. Bu durum tüm sistemin toplam maliyetini artırabileceği veya toplam faydasını düşürebileceği için bütünsel bir optimizasyon gerekir.
