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ı
Bir kargo firmasının dağıtım rotasını optimize etmek ile bir yatırımcının bütçesine göre en karlı projeleri seçmesi problemlerini karşılaştırarak, her birinin hangi özel tamsayılı programlama modeline (TSP, Sırt Çantası vb.) karşılık geldiğini gerekçeleriyle açıklayınız.
Yanıt / ipucu
Dağıtım rotası problemi, tüm noktalara birer kez uğrayıp başlangıca dönmeyi amaçladığı için Gezgin Satıcı Problemi (TSP) ile modellenir. Yatırım seçimi ise belirli bir bütçe (kapasite) sınırı dahilinde en yüksek getiriyi hedeflediği için Sırt Çantası Problemi yapısındadır.
Alıştırma 2myders hazırladı
Doğrusal programlama gevşetmesi (relaxation) yönteminde, gevşetilmiş modelin amaç fonksiyonu değerinin orijinal tamsayılı modelin değerine göre nasıl bir sınır oluşturduğunu maksimizasyon ve minimizasyon senaryoları için ayrı ayrı tartışınız.
Yanıt / ipucu
Maksimizasyon problemlerinde gevşetilmiş modelin optimal değeri, orijinal tamsayılı model için bir üst sınır (daha büyük veya eşit) oluşturur. Minimizasyon problemlerinde ise gevşetilmiş modelin optimal değeri, tamsayılı model için bir alt sınır (daha küçük veya eşit) görevi görür.
Alıştırma 3myders hazırladı
Gevşetilmiş doğrusal programlama modelinin optimal çözümünde elde edilen kesirli değerleri doğrudan en yakın tamsayıya yuvarlamanın ne tür riskler barındırdığını örnek senaryolar üzerinden araştırıp açıklayınız.
Yanıt / ipucu
Yuvarlama yöntemi, elde edilen yeni noktanın modeldeki kısıtları ihlal etmesine ve çözümün uygunsuz (geçersiz) hale gelmesine yol açabilir. Ayrıca, kısıtlar sağlansa bile ulaşılan tamsayılı çözüm optimal noktadan çok uzak ve verimsiz olabilir.
Alıştırma 4myders hazırladı
Bir havayolu şirketinin uçuşlarına kabin memuru atama senaryosunu düşünerek, bu durumun neden bir 'Küme Örtme Problemi' olarak modellendiğini ve buradaki temel amacın ne olduğunu açıklayınız.
Yanıt / ipucu
Bu problemde amaç, tüm uçuşların (örtülmesi gereken küme) kabin memurları tarafından en az bir kez kapsanmasını sağlamaktır. Model, tüm uçuş görevlerinin eksiksiz yerine getirilmesini en az sayıda personel veya en düşük maliyetle gerçekleştirmeyi hedefler.
Alıştırma 5myders hazırladı
Dal-Sınır (Branch and Bound) algoritmasının çalışma mantığını inceleyerek; dallandırma (branching), sınırlandırma (bounding) ve budama (pruning) adımlarının çözüme ulaşmadaki rollerini kısaca özetleyiniz.
Yanıt / ipucu
Dallandırma, kesirli değişkenleri alt ve üst tamsayı sınırlarına göre iki yeni alt probleme ayırır; sınırlandırma, her daldaki çözümlerle amaç fonksiyonunun sınırlarını belirler; budama ise mevcut en iyi çözümden daha kötü sonuç veren veya uygun çözümü olmayan dalları eleyerek arama uzayını daraltır.
