Examkin

Saf Tamsayılı Programlama Modelleri

9 questions

Question 1Question →

İki farklı ürünün (x1x_1 ve x2x_2) üretim miktarlarını optimize etmek isteyen bir işletme için aşağıdaki saf tamsayılı programlama modeli oluşturulmuştur:

Maksimum Z=3x1+4x2\text{Maksimum } Z = 3x_1 + 4x_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 modele göre elde edilebilecek optimal amaç fonksiyonu değeri (Z) aşağıdakilerden hangisidir?

Show answer & explanation

Answer: 12

Answer

Modelin optimal amaç fonksiyonu değeri 12'dir.
12 değeri, (0,3)(0, 3) tamsayı noktası kullanılarak elde edilir. Bu nokta 2(0)+3=3≤62(0) + 3 = 3 \leq 6 ve 2(0)+3(3)=9≤92(0) + 3(3) = 9 \leq 9 kısıtlarını tam olarak sağlar. Diğer uygun tamsayı noktaları ((1,2)(1, 2) gibi) daha düşük ZZ değerleri üretmektedir.

Step-by-Step Solution

1
Doğrusal programlama gevşetmesini (LP relaxation) çözün.
x1=2,25x_1 = 2,25, x2=1,5x_2 = 1,5 ve Z=12,75Z = 12,75
Tamsayı kısıtı olmaksızın çözümün üst sınırını belirlemek için gereklidir.
2
Uygun bölge içindeki tamsayı noktalarını listeleyin.
(0,0),(1,0),(2,0),(3,0),(0,1),(1,1),(2,1),(0,2),(1,2),(0,3)(0,0), (1,0), (2,0), (3,0), (0,1), (1,1), (2,1), (0,2), (1,2), (0,3)
Saf tamsayı modelinde çözüm bu noktalardan biri olmak zorundadır.
3
Kritik tamsayı noktaları için amaç fonksiyonu değerlerini hesaplayın.
Z(0,3)=12Z(0,3) = 12, Z(1,2)=11Z(1,2) = 11, Z(2,1)=10Z(2,1) = 10, Z(3,0)=9Z(3,0) = 9
En büyük Z değerini veren noktayı bulmak için karşılaştırma yapılır.

Key Concept

Saf Tamsayılı Programlama

Hints

1
Önce tamsayı kısıtını dikkate almadan modeli bir doğrusal programlama problemi gibi çözün.
2
Bulduğunuz LP çözümünün (12,7512,75) tamsayılı çözüm için bir üst sınır olduğunu unutmayın. Çözüm 12,75'ten küçük veya eşit olmalıdır.
3
x2x_2 katsayısı amaç fonksiyonunda daha yüksek olduğu için x2x_2'yi mümkün olduğunca büyük seçmeyi deneyin.

Practice More

Eğer değişkenlerden biri tamsayı diğeri reel sayı olsaydı çözüm nasıl değişirdi?
Estimated Time:1m 30s
Question 2Question →

Bir belediye, iki farklı tipte hizmet aracı (Süpürme Aracı - x1x_1 ve Çöp Kamyonu - x2x_2) satın almayı planlamaktadır. Araçların hizmet kapasitesi ve maliyet kısıtları doğrultusunda oluşturulan saf tamsayılı programlama modeli aşağıda verilmiştir:

Maksimum Z=3x1+4x2\text{Maksimum } Z = 3x_1 + 4x_2
Kısıtlar:
2x1+x2≤62x_1 + x_2 \leq 6
2x1+3x2≤92x_1 + 3x_2 \leq 9
x1,x2≥0 ve x1,x2∈Zx_1, x_2 \geq 0 \text{ ve } x_1, x_2 \in \mathbb{Z}

Buna göre, bu saf tamsayılı programlama modelinin en iyi (optimum) amaç fonksiyonu değeri (ZZ) kaçtır?

Show answer & explanation

Answer: 12

Answer

Modelin optimum tamsayılı amaç fonksiyonu değeri 12'dir.
Verilen kısıtlar altında tamsayı kısıtına uyan en iyi nokta (0,3)(0, 3) koordinatlarıdır. Bu noktada birinci kısıt 2(0)+3=3≤62(0) + 3 = 3 \leq 6 ve ikinci kısıt 2(0)+3(3)=9≤92(0) + 3(3) = 9 \leq 9 olarak sağlanır. Amaç fonksiyonu değeri ise 3(0)+4(3)=123(0) + 4(3) = 12 olur. Diğer tüm tamsayılı uygun noktalar (1,21,2 veya 2,12,1 gibi) daha düşük ZZ değerleri üretmektedir.

Step-by-Step Solution

1
Gevşetilmiş Doğrusal Programlama (LP) çözümünü belirlemek.
x1=2,25x_1 = 2,25 ve x2=1,5x_2 = 1,5 için Z=12,75Z = 12,75.
Tamsayılı kısıtın kaldırılmasıyla oluşan üst sınırı görmek için gereklidir.
2
Kısıtları sağlayan uygun tamsayılı noktaları (x1,x2x_1, x_2) test etmek.
(0,3),(1,2),(2,1),(3,0)(0,3), (1,2), (2,1), (3,0) gibi noktalar uygundur.
Saf tamsayılı modellerde sadece tamsayı değerli noktalar çözüm kümesine dahildir.
3
Uygun tamsayılı noktalar için amaç fonksiyonu değerlerini hesaplamak.
Z(0,3)=12,Z(1,2)=11,Z(2,1)=10,Z(3,0)=9Z(0,3)=12, Z(1,2)=11, Z(2,1)=10, Z(3,0)=9.
Maksimum değeri veren tamsayılı noktayı bulmak için karşılaştırma yapılır.

Key Concept

Saf tamsayılı programlamada optimum çözüm, her zaman gevşetilmiş doğrusal model çözümünün en yakın tamsayıya yuvarlanmasıyla bulunmaz; tüm uygun tamsayılı noktaların değerlendirilmesi gerekebilir.
Question 3Question →

Bir lojistik firması, AA ve BB tipi olmak üzere iki farklı yük konteyneri taşımayı planlamaktadır. x1x_1 taşınacak AA tipi konteyner sayısını, x2x_2 ise BB tipi konteyner sayısını göstermektedir. Firmanın kapasite kısıtları ve elde edilecek kârı maksimize etmeyi amaçlayan saf tamsayılı programlama modeli aşağıda verilmiştir:

Maks Z=4x1+5x2\text{Maks } Z = 4x_1 + 5x_2
Kısıtlar:
x1+2x2≤10x_1 + 2x_2 \leq 10
4x1+3x2≤244x_1 + 3x_2 \leq 24
x1,x2≥0 ve x1,x2 tamsayıx_1, x_2 \geq 0 \text{ ve } x_1, x_2 \text{ tamsayı}

Buna göre, bu saf tamsayılı programlama modelinin optimal kâr değeri kaçtır?

Show answer & explanation

Answer: 28

Answer

Optimal kâr değeri 28'dir ve bu değer x1=2x_1 = 2, x2=4x_2 = 4 noktasında elde edilir.
Modelde tüm kısıtları sağlayan tamsayı noktaları incelendiğinde, (2,4)(2,4) noktası için x1+2x2=10x_1 + 2x_2 = 10 (tam kapasite) ve 4x1+3x2=20≤244x_1 + 3x_2 = 20 \leq 24 (uygun) şartları sağlanır. Bu noktada amaç fonksiyonu Z=4(2)+5(4)=28Z = 4(2) + 5(4) = 28 değerine ulaşır. Diğer uygun tamsayı noktaları ((3,3)→27(3,3) \rightarrow 27, (0,5)→25(0,5) \rightarrow 25, (6,0)→24(6,0) \rightarrow 24) bu değerden daha küçüktür.

Step-by-Step Solution

1
Doğrusal programlama (LP) gevşetmesi çözümünü belirle.
x1+2x2=10x_1 + 2x_2 = 10 ve 4x1+3x2=244x_1 + 3x_2 = 24 doğrularının kesişim noktası (3,6;3,2)(3,6; 3,2) ve Z=30,4Z = 30,4.
Tamsayılı çözümün üst sınırını ve aday noktaların yerini belirlemek için önce sürekli çözüm bulunur.
2
Kesişim noktası civarındaki uygun tamsayı noktalarını değerlendir.
(3,3),(4,2),(2,4)(3,3), (4,2), (2,4) ve (0,5)(0,5) gibi noktalar kısıtlar çerçevesinde kontrol edilir.
Saf tamsayılı modellerde çözüm, sürekli çözümün en yakınındaki uygun tamsayı koordinatlarından biridir.
3
(2,4)(2,4) noktasının uygunluğunu ve kâr değerini hesapla.
2+2(4)=10≤102 + 2(4) = 10 \leq 10 ve 4(2)+3(4)=20≤244(2) + 3(4) = 20 \leq 24 (Uygun). Z=4(2)+5(4)=28Z = 4(2) + 5(4) = 28.
Seçilen noktanın her iki kısıtı da sağlayıp sağlamadığı test edilir.
4
(3,3)(3,3) noktasının kâr değeri ile karşılaştır.
3+2(3)=9≤103 + 2(3) = 9 \leq 10 ve 4(3)+3(3)=21≤244(3) + 3(3) = 21 \leq 24 (Uygun). Z=4(3)+5(3)=27Z = 4(3) + 5(3) = 27.
En büyük kârı veren noktanın optimal olduğunu teyit etmek için diğer adaylar karşılaştırılır.

Key Concept

Saf tamsayılı programlama modellerinde, optimal çözüm her zaman sürekli optimal çözümün (LP gevşetmesi) yuvarlanmasıyla bulunmaz; uygun bölge içindeki en iyi tamsayı koordinatı aranmalıdır.
Estimated Time:2m 0s
Question 4Question →

Bir kamu kurumu, denetim faaliyetlerini yürütmek amacıyla iki farklı uzmanlık grubundan ekipler oluşturacaktır. x1x_1 birinci grup ekip sayısını, x2x_2 ise ikinci grup ekip sayısını temsil etmektedir. Kurumun toplam verimliliğini maksimize etmeyi amaçlayan saf tamsayılı programlama modeli aşağıda verilmiştir:

Maks Z=4x1+5x2\text{Maks } Z = 4x_1 + 5x_2
Kısıt:\text{Kısıt:}
2x1+2x2≤72x_1 + 2x_2 \leq 7
x1,x2≥0 ve tamsayıx_1, x_2 \geq 0 \text{ ve tamsayı}

Buna göre, bu modelin en iyi (optimal) çözümü aşağıdakilerden hangisidir?

Show answer & explanation

Answer: x1=0,x2=3x_1 = 0, x_2 = 3

Answer

Modelin en iyi çözümü x1=0x_1 = 0 ve x2=3x_2 = 3 olarak belirlenmiştir.
Değişkenlerin x1=0x_1 = 0 ve x2=3x_2 = 3 olduğu çözümde, kısıt denklemi (0+6≤70+6 \leq 7) sağlanmakta ve amaç fonksiyonu en yüksek tamsayı değeri olan 15'e ulaşmaktadır.

Step-by-Step Solution

1
Kısıt bölgesindeki tamsayı noktaları belirle.
x1+x2≤3,5x_1 + x_2 \leq 3,5 olduğu için toplamları 3 veya daha küçük olan tamsayı ikilileri: (0,0), (1,0), (2,0), (3,0), (0,1), (0,2), (0,3), (1,1), (1,2), (2,1).
Saf tamsayılı programlamada sadece tamsayı değerli koordinatlar aday çözümdür.
2
Aday noktalar için amaç fonksiyonu değerlerini hesapla.
Z(0,3)=4(0)+5(3)=15Z(0,3) = 4(0) + 5(3) = 15; Z(1,2)=4(1)+5(2)=14Z(1,2) = 4(1) + 5(2) = 14; Z(2,1)=4(2)+5(1)=13Z(2,1) = 4(2) + 5(1) = 13; Z(3,0)=4(3)+5(0)=12Z(3,0) = 4(3) + 5(0) = 12.
En büyük Z değerini veren nokta optimal çözümdür.
3
Sonuçları karşılaştır.
Z=15Z=15 en yüksek değerdir.
Maksimum verimlilik bu noktada elde edilir.

Key Concept

Saf tamsayılı programlama modellerinde çözüm kümesi sadece tamsayı koordinatlardan oluşur ve en iyi çözüm genellikle doğrusal programlama gevşetmesinin yuvarlanmış hali olmayabilir.

Practice More

Değişkenlerden sadece birinin tamsayı olması durumunda 'Karma Tamsayılı Programlama' yöntemlerini inceleyebilirsiniz.
Estimated Time:45s
Question 5Question →

Bir kamu kütüphanesi, yeni açılacak okuma salonuna iki farklı tipte çalışma masası yerleştirmeyi planlamaktadır. A tipi bir masa (x1x_1) 5 öğrenci kapasiteli, B tipi bir masa (x2x_2) ise 8 öğrenci kapasitelidir. Salonun alan ve bütçe imkanları doğrultusunda oluşturulan kısıtlayıcı denklem 3x1+5x2≤163x_1 + 5x_2 \leq 16 olarak belirlenmiştir. Bu problemde masa sayılarının negatif olmayan tam sayılar olması gerektiği bilindiğine göre, toplam öğrenci kapasitesini maksimize eden saf tamsayılı programlama modelinin optimal amaç fonksiyonu değeri kaçtır?

Show answer & explanation

Answer: 26

Answer

Optimum tamsayı çözümü sağlayan kapasite değeri 26'dır.
Yapılan incelemede, kısıt denklemi olan 3x1+5x2≤163x_1 + 5x_2 \leq 16 eşitsizliğini sağlayan tamsayı ikilileri arasında en yüksek amaç değerini 26 ile (2,2)(2,2) noktası vermektedir. Bu noktada 3(2)+5(2)=163(2)+5(2)=16 olduğu için kapasite tam kullanılır ve amaç değeri 5(2)+8(2)=265(2)+8(2)=26 olur.

Step-by-Step Solution

1
Amaç fonksiyonunu ve kısıtları matematiksel olarak tanımlayın.
MaxZ=5x1+8x2Max Z = 5x_1 + 8x_2
Kısıt: 3x1+5x2≤163x_1 + 5x_2 \leq 16
Değişkenler: x1,x2∈Z+x_1, x_2 \in \mathbb{Z}^+
Saf tamsayılı programlama modelinin kurulması için değişkenlerin tamsayı kısıtı eklenmelidir.
2
Doğrusal programlama gevşetmesini (LP Relaxation) çözerek bir üst sınır belirleyin.
3x1+5x2=163x_1 + 5x_2 = 16 doğrusunda x2=0x_2=0 için x1≈5,33x_1 \approx 5,33; x1=0x_1=0 için x2=3,2x_2 = 3,2. Amaç fonksiyonu eğimi doğrultusunda LP optimumu (5,33,0)(5,33, 0) noktasında Z=26,67Z = 26,67 olur.
Tamsayılı çözümün amaç fonksiyonu değeri, gevşetilmiş modelin değerinden büyük olamaz.
3
Uygun bölge içerisindeki tamsayı noktalarını (aday çözümleri) test edin.
(5,0)→Z=25(5,0) \rightarrow Z=25
(4,0)→Z=20(4,0) \rightarrow Z=20
(2,2)→Z=10+16=26(2,2) \rightarrow Z=10+16=26
(0,3)→Z=24(0,3) \rightarrow Z=24
(3,1)→Z=15+8=23(3,1) \rightarrow Z=15+8=23
Saf tamsayılı modellerde optimum nokta her zaman gevşetilmiş çözümün en yakınındaki tamsayı noktası olmayabilir.
4
En yüksek ZZ değerine sahip tamsayı noktasını seçin.
x1=2x_1=2 ve x2=2x_2=2 değerleri kısıtı (3(2)+5(2)=16≤163(2)+5(2)=16 \leq 16) sağlar ve Z=26Z=26 sonucunu verir.
Tüm adaylar arasında en yüksek çıktı bu noktada gerçekleşir.

Key Concept

Saf tamsayılı programlama modellerinde optimum çözüm, doğrusal programlama gevşetmesinin uygun bölgesi içindeki tamsayı koordinatlı noktalardan biridir ve her zaman 'en yakın' tamsayıya yuvarlayarak bulunamaz.
Question 6Question →

Bir üretim atölyesi, sınırlı kaynaklarını kullanarak x1x_1 ve x2x_2 ürünlerinden üretmeyi planlamaktadır. Her iki ürünün de üretim miktarlarının tam sayı olması zorunludur. Modele ait amaç fonksiyonu ve kapasite kısıtı şu şekildedir:

Maks Z=60x1+80x2\text{Maks } Z = 60x_1 + 80x_2
Kısıt: x1+x2≤2,2\text{Kısıt: } x_1 + x_2 \leq 2,2
x1,x2∈{0,1,2,… }x_1, x_2 \in \{0, 1, 2, \dots\}

Buna göre, bu saf tamsayılı programlama modelinin en iyi (optimal) amaç fonksiyonu değeri kaçtır?

Show answer & explanation

Answer: 160

Answer

En iyi amaç fonksiyonu değeri 160'tır.
Verilen modelde x1+x2≤2,2x_1 + x_2 \leq 2,2 kısıtı ve tam sayı olma zorunluluğu altında, değişkenlerin toplamı en fazla 2 olabilir. En yüksek katsayıya sahip değişken olan x2x_2 değerini maksimuma çıkardığımızda (x2=2,x1=0x_2=2, x_1=0), amaç fonksiyonu 80×2=16080 \times 2 = 160 değerine ulaşır ve bu, kısıtlar dahilindeki en yüksek tam sayılı değerdir.

Step-by-Step Solution

1
Modelin kısıtını ve değişken yapısını inceleme
Tüm karar değişkenlerinin (x1,x2x_1, x_2) tam sayı olması gerektiği saptanmıştır.
Soruda 'saf tamsayılı programlama modeli' ifadesi kullanıldığı ve değişkenlerin tam sayı kümesine ait olduğu belirtildiği için.
2
Kısıtı sağlayan uygun tam sayılı noktaları (çözüm kümesini) belirleme
x1+x2≤2,2x_1 + x_2 \leq 2,2 kısıtını sağlayan tam sayı çiftleri: (0,0),(1,0),(2,0),(0,1),(0,2),(1,1)(0,0), (1,0), (2,0), (0,1), (0,2), (1,1) noktalarıdır.
Karar değişkenleri negatif olamaz ve toplamları 2,2'yi aşmamalıdır.
3
Uygun noktalar için amaç fonksiyonu (Z=60x1+80x2Z = 60x_1 + 80x_2) değerlerini hesaplama
(2,0)→Z=120(2,0) \rightarrow Z = 120; (0,2)→Z=160(0,2) \rightarrow Z = 160; (1,1)→Z=140(1,1) \rightarrow Z = 140 olarak hesaplanır.
Hangi tam sayılı kombinasyonun en yüksek karı verdiğini belirlemek için.
4
Optimal çözümü seçme
En büyük ZZ değeri x1=0,x2=2x_1=0, x_2=2 noktasında 160 olarak bulunur.
Maksimizasyon probleminde en büyük amaç fonksiyonu değeri en iyi çözümü temsil eder.

Key Concept

Saf tamsayılı modellerde çözüm uzayı sadece tam sayılı noktalardan oluşur ve çözüm aranırken tamsayılılık kısıtı asla ihlal edilmemelidir.

Hints

1
Değişkenlerin tam sayı olması gerektiğini unutmayın; yani toplam üretim 2,2 olamaz, en fazla 2 olabilir.

Practice More

Kısıtın x1+x2≤2,8x_1 + x_2 \leq 2,8 ve katsayıların 100x1+90x2100x_1 + 90x_2 olduğu bir durumda optimal çözümün nasıl değişeceğini inceleyebilirsiniz.
Estimated Time:45s
Question 7Question →

Saf tamsayılı bir doğrusal programlama probleminin çözümünde Kesme Düzlemi (Gomory) algoritması kullanılmaktadır. Doğrusal programlama gevşetmesinin (LP relaxation) optimal simpleks tablosunda, temel değişkenlerden olan x2x_2'nin bulunduğu satır aşağıdaki denklemi vermektedir:

x2+75x3−34x4=176x_2 + \frac{7}{5}x_3 - \frac{3}{4}x_4 = \frac{17}{6}

Problemdeki tüm değişkenlerin (x1,x2,x3,x4x_1, x_2, x_3, x_4) negatif olmayan tamsayılar olması gerektiğine göre, bu satırdan elde edilecek Gomory kesme düzlemi (kesirli kesme) eşitsizliği aşağıdakilerden hangisidir?

Show answer & explanation

Answer: 25x3+14x4≥56\frac{2}{5}x_3 + \frac{1}{4}x_4 \ge \frac{5}{6}

Answer

Gomory kesme düzlemi algoritmasında kesirli kısımlar ayrıştırılarak elde edilen eşitsizlik 25x3+14x4≥56\frac{2}{5}x_3 + \frac{1}{4}x_4 \ge \frac{5}{6} olmalıdır.
Gomory kesme düzlemi oluşturulurken tüm katsayılar aij=⌊aij⌋+fija_{ij} = \lfloor a_{ij} \rfloor + f_{ij} şeklinde tam ve negatif olmayan kesirli kısımlarına ayrılır (0≤fij<10 \le f_{ij} < 1). Burada en çok hata yapılan nokta negatif sayıların kesirli kısmını bulmaktır. −3/4-3/4 sayısının bir alt tam kısmı −1-1'dir, dolayısıyla kesirli kısmı −3/4−(−1)=1/4-3/4 - (-1) = 1/4 olur. 7/57/5'in kesirli kısmı 2/52/5, sağ taraf sabiti olan 17/617/6'nın kesirli kısmı ise 5/65/6'dır. Standart Gomory kesmesi formülü ∑fijxj≥fi\sum f_{ij} x_j \ge f_i şeklindedir. Buna göre doğru eşitsizlik 25x3+14x4≥56\frac{2}{5}x_3 + \frac{1}{4}x_4 \ge \frac{5}{6} olarak bulunur.

Step-by-Step Solution

1
Verilen denklemdeki katsayıların ve sağ taraf sabitinin kesirli (ff) kısımlarını belirlemek için a=⌊a⌋+fa = \lfloor a \rfloor + f kuralını uygula.
x3x_3 katsayısı: 75=1+25⇒f3=25\frac{7}{5} = 1 + \frac{2}{5} \Rightarrow f_3 = \frac{2}{5}
Gomory kesme düzlemi oluşturulurken değişken katsayıları, tam sayı ve pozitif kesirli kısımlarına ayrılmalıdır.
2
Negatif katsayılı terimin kesirli kısmını belirle.
x4x_4 katsayısı: −34=−1+14⇒f4=14-\frac{3}{4} = -1 + \frac{1}{4} \Rightarrow f_4 = \frac{1}{4}
Matematiksel olarak kesirli kısım daima pozitif olmalıdır (0≤f<10 \le f < 1). Bu nedenle negatif sayılar bir alt tamsayıya yuvarlanarak (burada −1-1) aradaki fark alınır.
3
Sağ taraf sabitinin kesirli kısmını belirle.
Sabit değer: 176=2+56⇒fb=56\frac{17}{6} = 2 + \frac{5}{6} \Rightarrow f_b = \frac{5}{6}
Eşitsizliğin sınır değerini oluşturmak için çözüm değerinin de tamsayı ve kesirli kısımları ayrılır.
4
Elde edilen kesirli kısımları standart Gomory eşitsizlik formülüne (∑fjxj≥fb\sum f_j x_j \ge f_b) yerleştir.
25x3+14x4≥56\frac{2}{5}x_3 + \frac{1}{4}x_4 \ge \frac{5}{6} eşitsizliği elde edilir.
Temel olmayan değişkenlerin kesirli kısımlarının toplamı, sağ taraf sabitinin kesirli kısmına eşit veya ondan büyük olmalıdır ki temel değişken tamsayı değerini alabilsin.

Key Concept

Gomory Kesme Düzlemi (Kesirli Kesme) Algoritması Formülasyonu
Question 8Question →

Amaç fonksiyonu katsayılarının tamamı tamsayı olan maksimizasyon yönlü saf tamsayılı bir doğrusal programlama problemi, Dal-Sınır (Branch and Bound) algoritması kullanılarak çözülmektedir. Sadece tek bir optimum çözümün bulunmasının hedeflendiği bu problemde, algoritmanın belirli bir aşamasında mevcut en iyi tamsayılı çözümün (alt sınır) amaç fonksiyonu değeri Z=125Z = 125 olarak belirlenmiştir.

Aynı aşamada, henüz dallandırılmamış olan üç farklı aktif düğümün (X, Y ve Z) doğrusal programlama gevşetmesi (LP relaxation) çözülmüş ve aşağıdaki amaç fonksiyonu değerleri elde edilmiştir:

• Düğüm X: ZX=127.4Z_X = 127.4 (En az bir değişken kesirli)
• Düğüm Y: ZY=125.8Z_Y = 125.8 (En az bir değişken kesirli)
• Düğüm Z: ZZ=124.6Z_Z = 124.6 (En az bir değişken kesirli)

Buna göre, algoritmanın karar kuralları işletildiğinde düğümlerin durumu ile ilgili aşağıdaki ifadelerden hangisi kesinlikle doğrudur?

Show answer & explanation

Answer: Düğüm Y'nin üretebileceği herhangi bir tamsayılı çözümün amaç fonksiyonu değeri en fazla 125125 olabileceğinden ve bu değer mevcut alt sınırdan daha iyi bir sonuç vermeyeceğinden Düğüm Y budanmalıdır.

Answer

Düğüm Y'nin üretebileceği herhangi bir tamsayılı çözümün amaç fonksiyonu değeri en fazla 125 olabileceğinden ve bu değer mevcut alt sınırdan daha iyi bir sonuç vermeyeceğinden Düğüm Y budanmalıdır.
Maksimizasyon yönlü ve katsayıları tamsayı olan bir saf tamsayılı programlama probleminde, herhangi bir tamsayılı çözümün ZZ değeri de mutlaka tamsayı olmak zorundadır. Doğrusal programlama gevşetmesi, o düğümden elde edilebilecek tüm çözümler için aşılmaz bir üst sınır (upper bound) verir. Düğüm Y için bu üst sınır 125.8125.8'dir. Değişkenler tamsayıya zorlandığında, bu daldan elde edilebilecek en büyük ZZ değeri aşağı yuvarlanarak en fazla 125125 olabilir. Algoritma zaten Z=125Z = 125 değerini veren geçerli bir tamsayılı çözüme (mevcut alt sınır) sahiptir. Problemde tek bir optimum çözüm arandığı için, Düğüm Y'den daha iyi bir sonuç (Z≥126Z \ge 126) elde etme olasılığı sıfırdır. Bu yüzden Düğüm Y budanarak (kapatılarak) elenir.

Step-by-Step Solution

1
Maksimizasyon probleminde Dal-Sınır algoritmasının temel budama (fathoming) kurallarını belirleme.
Bir düğümün budanması için doğrusal programlama gevşetmesi (üst sınır) değerinin, mevcut en iyi tamsayılı çözümden (alt sınır) daha kötü veya ona eşit olması gerekir.
Algoritmanın amacı, yalnızca elimizdeki mevcut en iyi çözümden daha üstün (daha iyi) çözümler aramaktır.
2
Saf tamsayılı modelde amaç fonksiyonu katsayılarının tamsayı olmasının matematiksel etkisini analiz etme.
Hem karar değişkenleri hem de amaç fonksiyonu katsayıları tamsayı olduğundan, amaç fonksiyonu ZZ yalnızca tamsayı değerler alabilir.
Tamsayıların doğrusal kombinasyonu her zaman bir tamsayıdır.
3
Düğüm Y'nin üretebileceği maksimum tamsayı değerini hesaplama.
ZY=125.8Z_Y = 125.8 olduğuna göre, değişkenler tamsayı olmaya zorlandığında bu daldan elde edilebilecek en yüksek ZZ değeri ⌊125.8⌋=125\lfloor 125.8 \rfloor = 125'tir.
Doğrusal programlama gevşetmesi, ilgili daldaki tüm olası tamsayılı çözümler için kesin bir üst sınır (upper bound) sağlar.
4
Elde edilen bu üst sınırı mevcut alt sınır ile karşılaştırma.
Düğüm Y'nin üretebileceği maksimum değer (125125), halihazırda elimizde bulunan mevcut en iyi çözüme (Z=125Z = 125) eşittir. Tek bir optimum çözüm arandığı için daha iyi bir çözüm çıkma ihtimali yoktur.
Bu nedenle Düğüm Y dallandırılmadan budanır (kapatılır). Düğüm Z (124.6<125124.6 < 125) zaten budanır. Sadece Düğüm X (⌊127.4⌋=127>125\lfloor 127.4 \rfloor = 127 > 125) dallandırılmaya devam edilir.

Key Concept

Saf Tamsayılı Programlamada Dal-Sınır Algoritması ve Budama Kuralları
Question 9Question →

Bir kamu kurumu, personel atama ve araç tahsis süreçlerini optimize etmek amacıyla saf tamsayılı bir doğrusal programlama modeli kurmuştur. Modelin doğrusal programlama gevşetmesi (LP relaxation) çözüldükten sonra elde edilen nihai simpleks tablosunda, tamsayı değer alması gereken temel değişkenlerden x2x_2'ye ait satır denklemi aşağıda verilmiştir:

x2+25x4−56x5+94x6=235x_2 + \frac{2}{5}x_4 - \frac{5}{6}x_5 + \frac{9}{4}x_6 = \frac{23}{5}

Gomory kesirli kesme (fractional cut) algoritması kullanılarak, bu optimal tablodaki kesirli çözümü ortadan kaldırmak için yeni bir kısıt (kesme düzlemi) üretilecektir.

Buna göre, modele eklenmesi gereken geçerli kesme kısıtı aşağıdakilerden hangisidir?

Show answer & explanation

Answer: 25x4+16x5+14x6≥35\frac{2}{5}x_4 + \frac{1}{6}x_5 + \frac{1}{4}x_6 \geq \frac{3}{5}

Answer

Modelden elde edilecek doğru Gomory kesme kısıtı 25x4+16x5+14x6≥35\frac{2}{5}x_4 + \frac{1}{6}x_5 + \frac{1}{4}x_6 \geq \frac{3}{5} olmalıdır.
Gomory kesirli kesme (fractional cut) algoritmasında, her katsayı aij=⌊aij⌋+fija_{ij} = \lfloor a_{ij} \rfloor + f_{ij} kuralıyla kendisinden küçük en büyük tamsayı (floor) ve pozitif kesirli kısmına (fijf_{ij}) ayrılır. Kesme kısıtı ∑fijxj≥fi\sum f_{ij} x_j \geq f_i temel formülü ile oluşturulur. Denklemdeki x4x_4 katsayısının kesirli kısmı 25\frac{2}{5}'tir. Negatif olan x5x_5 katsayısı −56-\frac{5}{6} için; ⌊−56⌋=−1\lfloor -\frac{5}{6} \rfloor = -1 işlemiyle kesirli kısım −56−(−1)=16-\frac{5}{6} - (-1) = \frac{1}{6} bulunur. x6x_6 katsayısı 94=2+14\frac{9}{4} = 2 + \frac{1}{4} olduğundan kesirli kısmı 14\frac{1}{4}'tür. Eşitliğin sağ tarafı 235=4+35\frac{23}{5} = 4 + \frac{3}{5} yapılarak fi=35f_i = \frac{3}{5} olarak belirlenir. Tüm kesirli bileşenler ∑fijxj≥fi\sum f_{ij} x_j \geq f_i denklemine yerleştirildiğinde doğru kısıt 25x4+16x5+14x6≥35\frac{2}{5}x_4 + \frac{1}{6}x_5 + \frac{1}{4}x_6 \geq \frac{3}{5} olarak çıkar.

Step-by-Step Solution

1
Kesme düzleminde kullanılmak üzere denklemdeki her bir değişkenin katsayısının pozitif kesirli kısmını (fijf_{ij}) belirleme
x4x_4 katsayısı 25\frac{2}{5} için f4=25f_4 = \frac{2}{5}, x5x_5 katsayısı −56-\frac{5}{6} için ⌊−56⌋=−1\lfloor -\frac{5}{6} \rfloor = -1 olduğundan f5=−56−(−1)=16f_5 = -\frac{5}{6} - (-1) = \frac{1}{6}, x6x_6 katsayısı 94\frac{9}{4} için ⌊94⌋=2\lfloor \frac{9}{4} \rfloor = 2 olduğundan f6=94−2=14f_6 = \frac{9}{4} - 2 = \frac{1}{4} olarak hesaplanır.
Gomory algoritması, değişkenlerin katsayılarını en büyük alt tamsayı ile arasındaki pozitif farka (aij=⌊aij⌋+fija_{ij} = \lfloor a_{ij} \rfloor + f_{ij}) ayırarak yeni bir kısıt üretir.
2
Eşitliğin sağ tarafındaki sabit değerin pozitif kesirli kısmını (fif_i) belirleme
Sağ taraf değeri 235=4.6\frac{23}{5} = 4.6 olduğundan ⌊4.6⌋=4\lfloor 4.6 \rfloor = 4 bulunur ve kesirli kısım fi=235−4=35f_i = \frac{23}{5} - 4 = \frac{3}{5} olarak elde edilir.
Kesme kısıtının sağ tarafı (RHS), optimal simpleks tablosundaki mevcut çözüm değerinin kesirli kısmından oluşturulmalıdır.
3
Gomory kesirli kesme kısıtı formülünü (∑fijxj≥fi\sum f_{ij} x_j \geq f_i) uygulama
Bulunan fijf_{ij} ve fif_i değerleri formüle yerleştirildiğinde 25x4+16x5+14x6≥35\frac{2}{5}x_4 + \frac{1}{6}x_5 + \frac{1}{4}x_6 \geq \frac{3}{5} kısıtı türetilir.
Bu eşitsizlik, mevcut LP gevşetmesinin optimal çözüm alanını daraltırken tamsayılı uygun çözüm bölgesini tamamen koruyan geçerli bir kesme düzlemidir.

Key Concept

Gomory Kesirli Kesme Algoritması
Estimated Time:2m 0s