Examkin

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

6 questions

Question 1Question →

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?

Show answer & explanation

Answer: 9

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.
Question 2Question →

Bir işletme, iki farklı ürünün üretim miktarını optimize etmek için aşağıdaki tam sayılı doğrusal programlama modelini kurmuştur:

MaksimumZ=8x1+5x2Maksimum \quad Z = 8x_1 + 5x_2
Kısıtlar:
x1+x2≤4,5x_1 + x_2 \leq 4,5
2x1+x2≤62x_1 + x_2 \leq 6
x1,x2≥0 ve tam sayıx_1, x_2 \geq 0 \text{ ve tam sayı}

Bu model grafik çözüm yöntemi ile çözüldüğünde, tam sayılı en iyi (optimum) amaç fonksiyonu değeri aşağıdakilerden hangisidir?

Show answer & explanation

Answer: 26

Answer

Modelin tam sayılı en iyi çözüm değeri 26 olarak bulunur.
Modelin doğrusal gevşetme optimumu (1,5;3)(1,5; 3) olup Z=27Z=27 değerini verir. Ancak değişkenlerin tam sayı olması istendiğinden, uygun bölge içerisindeki tam sayı koordinatları incelenir. (2,2)(2, 2) noktası her iki kısıtı da sağlar (2+2≤4,52+2 \leq 4,5 ve 2(2)+2≤62(2)+2 \leq 6) ve 8(2)+5(2)=268(2)+5(2)=26 değeriyle bölgedeki en yüksek tam sayılı amaç fonksiyonu değerini sunar.

Step-by-Step Solution

1
Doğrusal gevşetme (LP relaxation) çözümünün bulunması.
x1=1,5x_1 = 1,5 ve x2=3x_2 = 3 noktasında Z=27Z = 27.
Tam sayı kısıtı olmadan kısıt doğrularının kesişim noktası belirlenir.
2
Uygun çözüm bölgesi içerisindeki tam sayılı noktaların test edilmesi.
Uygun noktalar: (0,0),(1,0),(2,0),(3,0),(0,1),(1,1),(2,1),(0,2),(1,2),(2,2),(0,3),(1,3),(0,4)(0,0), (1,0), (2,0), (3,0), (0,1), (1,1), (2,1), (0,2), (1,2), (2,2), (0,3), (1,3), (0,4).
Grafik yöntemiyle belirlenen bölge sınırları içindeki tüm tam sayı koordinatları aday çözümlerdir.
3
Aday noktalarda amaç fonksiyonu değerlerinin hesaplanması.
Z(3,0)=24Z(3,0) = 24, Z(1,3)=23Z(1,3) = 23, Z(2,2)=26Z(2,2) = 26, Z(0,4)=20Z(0,4) = 20.
En yüksek ZZ değerini veren nokta optimum tam sayılı çözümdür.

Key Concept

Tam sayılı programlama modellerinde grafik çözümde, doğrusal gevşetme çözümünün yuvarlanması her zaman uygun veya en iyi sonucu vermez; bölge içindeki tam sayılı noktalar ayrı ayrı değerlendirilmelidir.
Estimated Time:1m 30s
Question 3Question →

Bir karar verici, iki değişkenli bir tamsayılı programlama problemini grafik yöntemle çözmek istemektedir. Probleme ait matematiksel model aşağıda verilmiştir:

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

Buna göre, bu tamsayılı programlama modelinin optimum amaç fonksiyonu (ZZ) değeri aşağıdakilerden hangisidir?

Show answer & explanation

Answer: 15

Answer

Optimum tamsayılı amaç fonksiyonu değeri 15'tir.
Verilen modelde doğrusal gevşetme noktası (2,33;2,33)(2,33; 2,33) olup amaç değeri 16,3316,33'dür. Ancak tamsayı kısıtı nedeniyle bu çözüm geçerli değildir. Bölge içindeki en yakın tamsayı noktaları test edildiğinde (3,1)(3,1) noktası hem birinci kısıtı (2(3)+1=7≤72(3)+1=7 \leq 7) hem de ikinci kısıtı (3+2(1)=5≤73+2(1)=5 \leq 7) sağlamaktadır. Bu noktadaki amaç değeri olan 15, diğer tüm uygun tamsayı noktalarından daha büyüktür.

Step-by-Step Solution

1
Doğrusal programlama gevşetmesinin (tamsayı kısıtı olmadan) çözümünü bulun.
x1=2,33x_1 = 2,33 ve x2=2,33x_2 = 2,33 noktası elde edilir. Bu noktada Z=16,33Z = 16,33 olur.
Tamsayılı çözümün üst sınırını belirlemek ve grafik üzerinde araştırma yapılacak bölgeyi daraltmak için gereklidir.
2
Uygun çözüm bölgesi içerisindeki tamsayı koordinatlı noktaları belirleyin.
Bölge içindeki uç tamsayı noktaları (3,1)(3,1), (2,2)(2,2) ve (1,3)(1,3)'tür.
Tamsayılı modellerde grafik çözüm, uygun bölge içindeki tam koordinatlı noktalardan birinde gerçekleşir.
3
Belirlenen noktaları amaç fonksiyonunda yerine koyarak en büyük değeri seçin.
Z(3,1)=4(3)+3(1)=15Z(3,1) = 4(3) + 3(1) = 15, Z(2,2)=14Z(2,2) = 14 ve Z(1,3)=13Z(1,3) = 13. En büyük değer 15'tir.
Maksimizasyon probleminde en yüksek amaç fonksiyonu değerini veren uygun tamsayı noktası optimum çözümdür.

Key Concept

Tamsayılı programlamada grafik çözüm yöntemi, doğrusal gevşetme çözümünün yakınındaki uygun tamsayı noktalarının araştırılmasına dayanır.

Hints

1
Önce tamsayı kısıtı yokmuş gibi kısıt doğrularının kesişim noktasını bulun.
2
Kesişim noktası olan (2,33; 2,33) çevresindeki (3,1), (2,2), (1,3) gibi tamsayı koordinatları kısıtlarda yerine koyun.
Estimated Time:1m 30s
Question 4Question →

Bir lojistik firması, araç filosu için iki farklı tipte (A ve B) yeni taşıma aracı almayı planlamaktadır. Firmanın bu alımlar için garaj kapasitesi ve bütçe sınırları bulunmaktadır. A tipi araç sayısını x1x_1 ve B tipi araç sayısını x2x_2 ile gösteren ve günlük taşıma kapasitesini maksimize etmeyi amaçlayan tamsayılı programlama modeli aşağıda formüle edilmiştir:

MaksimumZ=3x1+4x2Maksimum \quad Z = 3x_1 + 4x_2
Kısıtlar:
2x1+4x2≤17(Bu¨tc¸e kısıtı)2x_1 + 4x_2 \leq 17 \quad \text{(Bütçe kısıtı)}
4x1+2x2≤19(Garaj kısıtı)4x_1 + 2x_2 \leq 19 \quad \text{(Garaj kısıtı)}
x1,x2≥0 ve tamsayıx_1, x_2 \geq 0 \text{ ve tamsayı}

Bu problemin grafik çözüm yöntemi ile elde edilen tamsayılı optimum çözümünde amaç fonksiyonu (ZZ) değeri kaçtır?

Show answer & explanation

Answer: 18

Answer

Tamsayılı optimum çözüm değeri 18'dir.
Tamsayılı programlama modellerinde grafik çözüm uygulanırken, doğrusal programlama bölgesinin içindeki tamsayı noktaları araştırılır. Bu problemde doğrusal programlamanın kesişim noktası (3.5, 2.5) olup Z=20.5 değerini verir. Ancak değişkenler tamsayı olmalıdır. Bu noktaya yakın tamsayı koordinatları test edildiğinde; (4, 2) ve (3, 3) noktalarının kısıtları ihlal ettiği görülür. Uygun çözüm alanı içinde kalan tamsayı noktalarından (3, 2) noktasında Z=17, (2, 3) noktasında ise Z=18 değeri elde edilir. Amaç maksimizasyon olduğu için en iyi tamsayılı çözüm Z=18'dir.

Step-by-Step Solution

1
Problemin tamsayı kısıtları göz ardı edilerek doğrusal programlama (DP) gevşetmesinin optimum noktasını hesapla.
2x1+4x2=172x_1 + 4x_2 = 17 ve 4x1+2x2=194x_1 + 2x_2 = 19 denklemlerinin ortak çözümünden x1=3.5x_1 = 3.5 ve x2=2.5x_2 = 2.5 bulunur. Bu noktada Z=20.5Z = 20.5'tir.
Grafik yöntemde tamsayılı çözümü ararken, öncelikle sürekli (kesirli) çözüm alanının tepe noktasını bulmak, hangi tamsayı noktalarını incelememiz gerektiği konusunda yön gösterir.
2
DP optimumuna (3.5, 2.5) yakın olan ve kısıtları sağlayan (uygun) tamsayı noktalarını belirle.
(3,2)(3, 2) noktası kısıtları sağlar (14≤1714 \leq 17 ve 16≤1916 \leq 19). (2,3)(2, 3) noktası kısıtları sağlar (16≤1716 \leq 17 ve 14≤1914 \leq 19). Yuvarlama ile elde edilebilecek (4,2)(4, 2) ve (3,3)(3, 3) gibi diğer noktalar ise kısıtları sağlamaz (uygun değildir).
Tamsayılı programlamada çözüm, uygun bölgenin içindeki veya sınırındaki tamsayı koordinatlı noktalarda aranmalıdır. Kesirli çözümü basitçe yuvarlamak genellikle kısıtları ihlal eder.
3
Belirlenen uygun tamsayı noktalarında amaç fonksiyonu (ZZ) değerlerini karşılaştırarak maksimum olanı seç.
(3,2)(3, 2) noktası için Z=3(3)+4(2)=17Z = 3(3) + 4(2) = 17. (2,3)(2, 3) noktası için Z=3(2)+4(3)=18Z = 3(2) + 4(3) = 18. Maksimum değer 18'dir.
Mümkün olan tüm uygun tamsayı çözümleri arasından, amaç fonksiyonunu en çoklaştıran değer optimum tamsayılı çözümdür.

Key Concept

Tamsayılı Programlamada Grafik Çözüm ve Yuvarlama Hataları
Question 5Question →

Bir mobilya atölyesi, masa (xx) ve sandalye (yy) üretiminden elde edeceği toplam kârı en çoklamak istemektedir. Üretim sürecindeki işçilik ve hammadde kısıtları göz önüne alınarak problemin matematiksel modeli şu şekilde oluşturulmuştur:

Amaç Fonksiyonu:
MaksZ=8x+5yMaks \quad Z = 8x + 5y
Kısıtlayıcı Fonksiyonlar:
x+y≤6x + y \leq 6
9x+5y≤459x + 5y \leq 45
x,y≥0 ve tamsayıx, y \geq 0 \text{ ve tamsayı}

Buna göre, problemin grafik yöntem kullanılarak çözülmesi durumunda bulunacak en uygun (optimum) ZZ değeri kaçtır?

Show answer & explanation

Answer: 40

Answer

Problemin tamsayı kısıtları altındaki optimum çözümü (5,0)(5, 0) noktasında gerçekleşir ve elde edilecek maksimum ZZ değeri 4040'tır.
Doğrusal programlama gevşetmesinin optimum noktası (3,75;2,25)(3,75 ; 2,25) olup amaç fonksiyonu değeri 41,2541,25'tir. Ancak değişkenlerin tamsayı olması gerektiğinden, bu noktanın etrafındaki uygun tamsayı koordinatları incelenmelidir. Standart yuvarlama işlemi ile ulaşılan (4,2)(4, 2) noktası 9(4)+5(2)=46>459(4)+5(2)=46 > 45 olduğundan kısıtı ihlal eder ve uygun çözüm bölgesinde değildir. Bölge içindeki (3,3)(3, 3) noktası için Z=8(3)+5(3)=39Z = 8(3)+5(3)=39 bulunurken, uygun alanın sağ alt köşesindeki (5,0)(5, 0) noktasında kısıtlar sağlanır (5+0≤65+0 \leq 6 ve 9(5)+0≤459(5)+0 \leq 45) ve Z=8(5)+5(0)=40Z = 8(5)+5(0)=40 değeri elde edilir. Maksimum tamsayı değeri 4040'tır.

Step-by-Step Solution

1
Kısıt doğrularının kesişim noktasının (LP gevşetme optimumunun) bulunması
İki denklem (x+y=6x+y=6 ve 9x+5y=459x+5y=45) ortak çözülerek x=3,75x=3,75 ve y=2,25y=2,25 bulunur.
Grafik çözümünde amaç fonksiyonu doğrusunun en dışa itildiği köşe noktası belirlenir.
2
Bulunan kesirli noktanın tamsayıya yuvarlanarak uygunluğunun test edilmesi
En yakın tamsayı olan (4,2)(4, 2) noktası denendiğinde 9(4)+5(2)=46≤459(4) + 5(2) = 46 \leq 45 eşitsizliğini sağlamadığı, yani çözüm alanının dışında kaldığı görülür.
Tamsayılı programlamada en yakın tamsayıya yuvarlamak her zaman uygun ve optimum çözümü vermez.
3
Uygun çözüm alanındaki alternatif tamsayı noktalarının değerlendirilmesi
(3,3)(3, 3) noktası için Z=39Z=39, (4,1)(4, 1) noktası için Z=37Z=37 ve (5,0)(5, 0) noktası için Z=40Z=40 hesaplanır.
Amaç fonksiyonunu (Z=8x+5yZ=8x+5y) en çoklayan ve tüm kısıtları sağlayan en iyi tamsayı kombinasyonunun bulunması gerekir.

Key Concept

Tamsayılı Programlama Modellerinde Grafik Çözüm ve LP Gevşetmesi Optimizasyonu

Alternative Method

Grafik çizmek yerine, kısıtları sağlayan tüm makul tamsayı ikililerini (x, y) sınır koşullarına göre (örneğin x=0'dan 5'e kadar) tek tek deneyerek Z değerini hesaplamak (tam sayımlama yaklaşımı).
Estimated Time:2m 0s
Question 6Question →

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?

Show answer & explanation

Answer: 23

Answer

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.

Step-by-Step Solution

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.

Key Concept

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