Examkin

Soru

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

Aşağıda bir tamsayılı programlama modeli verilmiştir:

MaksimumZ=3x1+2x2Maksimum \quad Z = 3x_1 + 2x_2
Kısıtlar:
2x1+x2≤62x_1 + x_2 \leq 6
2x1+3x2≤92x_1 + 3x_2 \leq 9
x1,x2≥0 ve tamsayıx_1, x_2 \geq 0 \text{ ve tamsayı}

Bu model grafik çözüm yöntemi ile çözüldüğünde, amaç fonksiyonunun alabileceği en büyük (optimal) değer aşağıdakilerden hangisidir?

  1. 9Cevap
  2. B
    9,75
  3. C
    10
  4. D
    8
  5. E
    6

Cevap

Modelin optimal tamsayılı çözümünde amaç fonksiyonu değeri 9 olarak bulunur.
Verilen kısıtlar altında tamsayı koordinatlı noktalar incelendiğinde, (3,0) noktası her iki kısıtı da sağlar (2(3)+0=6≤62(3)+0=6 \leq 6 ve 2(3)+3(0)=6≤92(3)+3(0)=6 \leq 9) ve 3(3)+2(0)=93(3)+2(0)=9 değeriyle en yüksek amaç fonksiyonu sonucunu verir.

Adım Adım Çözüm

1
Doğrusal gevşetme (LP relaxation) çözümünü bulun.
x1=2,25x_1 = 2,25, x2=1,5x_2 = 1,5 ve Z=9,75Z = 9,75.
Tamsayı kısıtı olmadan en iyi çözümün nerede olduğunu anlamak için kısıt doğrularının kesişim noktası hesaplanır.
2
Uygun çözüm alanı içerisindeki tamsayı noktalarını belirleyin.
Uygun noktalar: (0,0), (1,0), (2,0), (3,0), (0,1), (1,1), (2,1), (0,2), (1,2), (0,3).
Grafik üzerinde kısıtların (2x1 + x2 ≤ 6 ve 2x1 + 3x2 ≤ 9) sınırladığı bölgedeki tamsayı koordinatları taranır.
3
Aday tamsayı noktalarını amaç fonksiyonunda (Z=3x1+2x2Z = 3x_1 + 2x_2) yerine koyun.
(3, 0) için Z=9Z = 9; (2, 1) için Z=8Z = 8; (1, 2) için Z=7Z = 7; (0, 3) için Z=6Z = 6.
En büyük Z değerini veren tamsayı koordinatı optimal çözümü temsil eder.

Anahtar Kavram

Tamsayılı programlamada grafik çözüm, doğrusal gevşetme çözümünden (LP relaxation) daha küçük (maksimizasyon için) veya eşit bir amaç değeri üretir ve çözüm mutlaka uygun alan içindeki bir tamsayı noktasıdır.
Bu soruyu puanla

Konular

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

Bu konudan daha fazla soru