Examkin

Soru

Zorluk: ZorTamsayılı Modellerde Grafik Çözüm Yöntemi

Bir teknoloji firması, akıllı ev sistemleri için A ve B olmak üzere iki farklı model güvenlik kamerası üretmektedir. Üretim sürecinde bu kameralar optik montaj ve yazılım testi olmak üzere iki aşamadan geçmektedir. Firmanın günlük kârını en çoklamak amacıyla kurduğu tamsayılı doğrusal programlama modeli aşağıda verilmiştir:

MaksimumZ=4x1+5x2Maksimum \quad Z = 4x_1 + 5x_2
Kısıtlar:
3x1+2x2≤143x_1 + 2x_2 \leq 14
x1+4x2≤15x_1 + 4x_2 \leq 15
x1,x2≥0 ve tamsayıx_1, x_2 \geq 0 \text{ ve tamsayı}

(Burada x1x_1 ve x2x_2 sırasıyla A ve B model kameraların günlük üretim miktarlarını temsil etmektedir.)

Buna göre, bu problemin tamsayılı grafik çözüm yöntemi ile incelenmesi sonucunda elde edilecek maksimum ZZ (kâr) değeri aşağıdakilerden hangisidir?

  1. A
    25.9
  2. B
    27
  3. C
    24
  4. 23Cevap
  5. E
    22

Cevap

Doğru değer 23'tür.
Tamsayılı grafik çözüm yönteminde amaç, kısıtların oluşturduğu uygun poligon içindeki en yüksek amaç fonksiyonu (Z) değerini veren tamsayı koordinatlarını bulmaktır. Kesirli kesişim noktası (2.6, 3.1)'e komşu tamsayı noktalar incelendiğinde, (3, 3) noktası kısıtları ihlal ederken (2, 3) noktası alanı ihlal etmez ve Z değerini 23 yapar. Kısıtları sağlayan diğer tamsayı noktalarında (örneğin (3, 2) için Z=22) daha yüksek bir kâr elde edilememektedir.

Adım Adım Çözüm

1
Doğrusal programlama (LP) gevşetmesinin optimum noktasını bulmak için kısıtların kesişim noktasını hesapla.
3x_1 + 2x_2 = 14 ve x_1 + 4x_2 = 15 denklemleri ortak çözüldüğünde x_1 = 2.6 ve x_2 = 3.1 elde edilir.
Grafik çözüm yönteminde tamsayılı noktalar, sürekli (kesirli) çözümün etrafındaki uygun alanda aranır.
2
LP gevşetmesi için Z değerini hesapla.
Z = 4(2.6) + 5(3.1) = 10.4 + 15.5 = 25.9
Tamsayı kısıtı olduğu için 25.9 değeri doğrudan alınamaz, ancak optimum tamsayı çözümünün bu değerden küçük veya buna eşit olacağı bir üst sınır (bound) olarak bilinir.
3
Kesişim noktası (2.6, 3.1) etrafındaki tamsayılı noktaların uygun çözüm alanında (kısıtları sağlayıp sağlamadığı) olup olmadığını kontrol et.
Yuvarlama sonucu oluşan (3, 3) noktası 1. kısıtı (3*3 + 2*3 = 15 > 14) ihlal eder. Alt yuvarlama olan (2, 3) noktası 1. kısıtı (12 <= 14) ve 2. kısıtı (14 <= 15) sağlar. (3, 2) noktası da her iki kısıtı sağlar.
Tamsayılı programlamada sadece kısıt doğrusunun altında kalan uygun poligon alanı içindeki tamsayı koordinatları geçerlidir.
4
Uygun tamsayılı noktalar için amaç fonksiyonu (Z) değerlerini karşılaştır.
(2, 3) noktası için Z = 4(2) + 5(3) = 23. (3, 2) noktası için Z = 4(3) + 5(2) = 22.
En büyük (maksimum) Z değerini veren uygun tamsayı noktası, problemin kesin çözümüdür.

Anahtar Kavram

Tamsayılı Modellerde Grafik Çözüm Yöntemi
Bu soruyu puanla

Konular

Tamsayılı Modellerde Grafik Çözüm Yöntemi

Bu konudan daha fazla soru