Examkin

Question

Difficulty: MediumTamsayı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. 9Answer
  2. B
    9,75
  3. C
    10
  4. D
    8
  5. E
    6

Answer

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.

Step-by-Step Solution

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.

Key Concept

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.
Rate this question

Topics

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

More questions from this topic