Tamsayılı Programlama Practice Questions — KPSS İstatistik — Page 4

Question 61Question →

Bir kamu hastanesi, laboratuvarlarında kullanılmak üzere özel bir dezenfektan çözeltisinin kendi tesislerinde üretimine geçip geçmeme kararı alacaktır.

- Hastane bu çözeltiyi üretmeye karar verirse, kimyasal reaksiyon stabilitesi gereği ayda en az $500$ litre, tesis kapasitesi gereği ise en fazla $2000$ litre üretim yapmak zorundadır.
- Üretim yapılmaması kararı alınırsa, üretim miktarı tam olarak sıfır olacaktır.

Dezenfektan çözeltisinin aylık üretim miktarını litre cinsinden $x$ sürekli değişkeni ile ve üretim yapma kararını $y$ sıfır-bir (ikili) değişkeni ile ifade ettiğimiz bir Karma Tamsayılı Programlama (MIP) modelinde, bu durumu doğru bir şekilde ifade eden kısıt seti aşağıdakilerden hangisidir?

x - 500y \geq 0

;

x - 2000y \leq 0

;

y \in \{0, 1\}

;

x \geq 0

x \geq 500

;

x - 2000y \leq 0

;

y \in \{0, 1\}

;

x \geq 0

x - 500y \leq 0

;

x - 2000y \geq 0

;

y \in \{0, 1\}

;

x \geq 0

x - 500y \geq 0

;

x \leq 2000

;

y \in \{0, 1\}

;

x \geq 0

x - 500y \geq 0

;

x - 2000y \leq 0

;

y \geq 0

ve tamsayı ;

x \geq 0

Show answer & explanation

Answer: $x - 500y \geq 0$ ; $x - 2000y \leq 0$ ; $y \in \{0, 1\}$ ; $x \geq 0$

Answer

Modeli doğru ifade eden kısıt seti:

x - 500y \geq 0

;

x - 2000y \leq 0

;

y \in \{0, 1\}

;

x \geq 0

kısıtlarını içeren seçenektir.

Karma Tamsayılı Programlama (MIP) modellerinde 'ya belirtilen aralıkta değer al ya da sıfır ol' şeklindeki yarı-sürekli (semi-continuous) durumlar, sınır değerlerinin bir sıfır-bir değişkeni ile çarpılmasıyla modellenir. Doğru seçenekte yer alan

x \geq 500y

(yani

x - 500y \geq 0

) ve

x \leq 2000y

(yani

x - 2000y \leq 0

) eşitsizlikleri bu mantığı tam olarak karşılar.

y=1

iken

500 \leq x \leq 2000

aralığı geçerli olur,

y=0

iken ise

0 \leq x \leq 0

(dolayısıyla

x=0

) durumu zorunlu kılınır.

Step-by-Step Solution

1

Karar değişkenlerinin türlerini ve sınırlarını belirleme.

x

sürekli bir değişkendir (

x \geq 0

).

y

ise evet/hayır kararını temsil ettiği için ikili (sıfır-bir) değişkendir (

y \in \{0, 1\}

).

Üretim miktarı kesirli olabilen bir sürekli değeri ifade ederken, üretime geçme kararı mantıksal bir seçimdir.

2

Üretim yapılması (

y=1

) durumundaki kısıtları matematiksel olarak ifade etme.

Üretim varsa miktar

500

ile

2000

arasında olmalıdır:

500 \leq x \leq 2000

.

Soruda belirtilen minimum reaksiyon stabilitesi ve maksimum tesis kapasitesi sınırlarıdır.

3

Üretim yapılmaması (

y=0

) durumundaki kısıtı ifade etme.

Üretim yoksa miktar sıfır olmalıdır:

x = 0

.

Karar verilmediğinde herhangi bir üretim gerçekleşemez.

4

İki durumu tek bir kısıt setinde birleştirmek için

x

sınırlarını

y

ile çarpma (Büyük-M tekniğinin yarı sürekli versiyonu).

Alt sınır için:

x \geq 500y

. Üst sınır için:

x \leq 2000y

.

y=1

iken

500 \leq x \leq 2000

olur.

y=0

iken

0 \leq x \leq 0

olur ki bu da doğrudan

x=0

eşitliğini sağlar.

5

Elde edilen eşitsizlikleri standart forma (değişkenler solda, sabitler sağda) dönüştürme.

x - 500y \geq 0

ve

x - 2000y \leq 0

denklemleri elde edilir.

Doğrusal ve tamsayılı programlama modellerinde kısıtlar genellikle standart formda yazılır.

Key Concept

Karma Tamsayılı Programlama Modellerinde Yarı Sürekli Değişken (Semi-continuous Variable) Modellemesi

Question 62Question →

Bir kamu kurumu, e-devlet veri tabanı altyapısını güçlendirmek amacıyla yüksek performanslı yeni bir bulut sunucu sistemine geçiş yapıp yapmamayı değerlendirmektedir. Sistemin aktif hale getirilmesi kararı verilirse $50.000$ TL tutarında sabit bir kurulum (lisans) maliyeti katlanılacaktır. Sistem kurulduktan sonra, bu sunucu üzerinden işlenen her bir terabayt (TB) veri için $15$ TL değişken işlem maliyeti oluşacaktır. Sistemin altyapısı gereği, kurulum yapıldığında bu sunucuda en fazla $10.000$ TB veri işlenebilmektedir. Kurulum yapılmazsa bu sunucuda herhangi bir veri işlenmesi mümkün değildir (işlenen veri miktarı sıfır olmalıdır).

Sistemin kurulup kurulmama kararını $y$ ( $y \in \{0, 1\}$ ) ve işlenen veri miktarını TB cinsinden bir sürekli değişken olan $x$ ( $x \ge 0$ ) ile gösteren, toplam maliyeti en küçüklemeyi amaçlayan karma tamsayılı programlama modeli aşağıdakilerden hangisinde doğru formüle edilmiştir?

\min Z = 15x + 50000y

;

x - 10000y \le 0

;

x \ge 0

(sürekli),

y \in \{0, 1\}

\min Z = 15x + 50000y

;

x - 10000y \ge 0

;

x \ge 0

(sürekli),

y \in \{0, 1\}

\min Z = 15x + 50000y

;

x \le 10000

;

x \ge 0

(sürekli),

y \in \{0, 1\}

\min Z = 15x + 50000y

;

x - 10000y \le 0

;

x \ge 0, y \ge 0

(her ikisi de sürekli)

\min Z = 15x + 50000y

;

x - 10000y \le 0

;

x \in \{0, 1\}, y \in \{0, 1\}

(her ikisi de ikili)

Show answer & explanation

Answer: $\min Z = 15x + 50000y$ ; $x - 10000y \le 0$ ; $x \ge 0$ (sürekli), $y \in \{0, 1\}$

Answer

Amaç fonksiyonunun sabit ve değişken maliyetleri doğru ağırlıklarla topladığı, kapasite ve ön koşul ilişkisinin

x - 10000y \le 0

mantıksal kısıtıyla birbirine bağlandığı ve değişkenlerin türünün doğru (x sürekli, y ikili) ifade edildiği modeldir.

Doğru modelde maliyet maksimizasyonu önlenmiş (Min Z), x'in ancak y'nin 1 olması durumunda pozitif değer alabileceğini güvence altına alan bağlayıcı kısıt (

x - 10000y \le 0

) doğru yazılmış ve problemin doğası gereği değişkenlerden yalnızca birinin sıfır-bir kısıtına tabi olduğu, diğerinin sürekli bırakıldığı (Karma model prensibi) hatasız uygulanmıştır.

Step-by-Step Solution

1

Amaç fonksiyonunu belirlemek.

Min Z = 15x + 50000y

Toplam maliyet, veri miktarı başına 15 TL ile sistemin kurulum kararını yansıtan 50.000 TL'nin toplamından oluşur.

2

Mantıksal ön koşul ve kapasite kısıtını oluşturmak.

x <= 10000y => x - 10000y <= 0

Sistem kurulmazsa (y=0) işlenen veri sıfır (x<=0) olmalı, kurulursa (y=1) veri miktarı en fazla 10.000 olmalıdır. Bu bağlantı eşitsizlikle ifade edilmelidir.

3

Değişkenlerin uzayını (türünü) tanımlamak.

x >= 0 (sürekli) ve y elemandır {0, 1} (ikili/kesikli)

İşlenen veri (TB) kesirli değerler alabilen sürekli bir miktar, sistemin kurulum kararı ise var/yok mantığıyla çalışan sıfır-bir tamsayı değeridir.

Key Concept

Karma Tamsayılı (MIP) Modellerde Mantıksal (Sabit Maliyet) Kısıtlarının Formülasyonu

Question 63Question →

Bir büyükşehir belediyesi, kısıtlı bütçesiyle 5 farklı sosyal donatı projesini değerlendirmektedir. Projeler sırasıyla Kütüphane ( $x_1$ ), Spor Salonu ( $x_2$ ), Yüzme Havuzu ( $x_3$ ), Gençlik Merkezi ( $x_4$ ) ve Kreş ( $x_5$ ) olarak belirlenmiş olup, her bir karar değişkeni $x_j \in \{0, 1\}$ 'dir ( $j=1,2,3,4,5$ ).

Belediye meclisinin aldığı yatırım kararları şöyledir:
I. Kreş projesi hayata geçirilmezse, Kütüphane ve Spor Salonu projelerinin hiçbirisi yapılamaz.
II. Yüzme Havuzu projesi inşa edilmediği takdirde, Kütüphane ve Gençlik Merkezi projelerinden en fazla bir tanesi inşa edilebilir.

Buna göre, belediye meclisi kararlarını doğru bir şekilde ifade eden 0-1 tamsayılı programlama kısıtları aşağıdakilerden hangisinde birlikte verilmiştir?

I.

x_1 + x_2 \leq 2x_5

II.

x_1 + x_4 - x_3 \leq 1

I.

x_1 + x_2 \leq x_5

II.

x_1 + x_4 + x_3 \leq 2

I.

x_1 + x_2 \geq 2x_5

II.

x_1 + x_4 - x_3 \geq 1

I.

x_1 + x_2 + x_5 \leq 2

II.

x_1 + x_4 \leq x_3

I.

x_1 + x_2 \leq 2x_5

II.

x_1 + x_4 + x_3 \leq 1

Show answer & explanation

Answer: I. $x_1 + x_2 \leq 2x_5$
II. $x_1 + x_4 - x_3 \leq 1$

Answer

Birinci karar için

x_1 + x_2 \leq 2x_5

, ikinci karar için

x_1 + x_4 - x_3 \leq 1

eşitsizliklerini içeren seçenek doğrudur.

Doğru eşleşme, kısıtların

x_1 + x_2 \leq 2x_5

ve

x_1 + x_4 - x_3 \leq 1

olarak verildiği seçenektir. Birinci ifadede

x_5=0

(Kreş yok) olduğunda

x_1+x_2 \leq 0

olur ve zorunlu olarak Kütüphane ile Spor Salonu yapılamaz (

x_1=0, x_2=0

). İkinci ifadede

x_3=0

(Havuz yok) olduğunda denklem

x_1+x_4 \leq 1

halini alır ve en fazla birinin yapılabileceği şartını tam olarak sağlar.

Step-by-Step Solution

1

Birinci kararı mantıksal olarak analiz edip eşitsizliğe dönüştürmek.

x_1 + x_2 \leq 2x_5

eşitsizliği elde edilir.

"Kreş (

x_5

) yapılmazsa (

x_5=0

), Kütüphane (

x_1

) ve Spor Salonu (

x_2

) yapılamaz" kuralı,

x_5=0

için

x_1+x_2 \leq 0

olmasını gerektirir.

x_5=1

için herhangi bir engel olmadığından denklem

x_1+x_2 \leq 2x_5

şeklinde veya

x_1 \leq x_5

ve

x_2 \leq x_5

olarak yazılabilir.

2

İkinci kararı mantıksal olarak analiz edip eşitsizliğe dönüştürmek.

x_1 + x_4 - x_3 \leq 1

eşitsizliği elde edilir.

"Yüzme havuzu (

x_3

) yapılmazsa (

x_3=0

), Kütüphane (

x_1

) ve Gençlik Merkezi (

x_4

) en fazla 1 olabilir" kuralı,

x_3=0

iken

x_1+x_4 \leq 1

olmasını gerektirir.

x_3=1

iken kısıtlama yoktur (

x_1+x_4 \leq 2

). Bu durum

x_1+x_4 \leq 1 + x_3

denklemi ile genel formda ifade edilir ve düzenlenirse

x_1 + x_4 - x_3 \leq 1

bulunur.

Key Concept

0-1 tamsayılı programlamada koşullu (önermeli) durumların kısıt denklemlerine dönüştürülmesi.

Question 64Question →

Bir kamu kurumunun tedarik zinciri ağında kullanılacak depo sayısını ve kapasitesini belirlemek amacıyla aşağıdaki saf tamsayılı maksimizasyon doğrusal programlama modeli kurulmuştur:

\text{Maksimum } Z = 5x_1 + 8x_2

Kısıtlar:

x_1 + x_2 \leq 6

5x_1 + 9x_2 \leq 45

x_1, x_2 \geq 0 \text{ ve tamsayı}

Bu model Dal-Sınır (Branch and Bound) algoritması kullanılarak çözülmektedir. Başlangıç (kök) düğümünün doğrusal programlama gevşetmesi çözüldüğünde optimum çözüm $x_1 = 2.25$ , $x_2 = 3.75$ ve amaç fonksiyonu değeri $Z = 41.25$ olarak bulunmuştur. Algoritmanın kuralı gereği, ilk dallanma işlemi kesirsel kısmı en büyük olan değişken üzerinden yapılacaktır.

İlk dallanma işlemi sonucunda elde edilen alt problemlerin (düğümlerin) çözülmesiyle birlikte, algoritmanın güncel durumu ve sınır (bound) değerleri hakkında aşağıdakilerden hangisi doğrudur?

x_2

değişkeni üzerinden

x_2 \leq 3

ve

x_2 \geq 4

kısıtları ile iki alt düğüm oluşturulur;

x_2 \leq 3

kısıtlı düğümde

Z=39

değerli tamsayılı çözüm bulunarak alt sınır (lower bound)

39

olarak güncellenir,

x_2 \geq 4

kısıtlı düğüm ise

Z=41

değerini verdiğinden incelenmeye devam edilir.

x_2

değişkeni üzerinden dallanma yapılarak modele

x_2 < 4

ve

x_2 > 3

kısıtları eklenir; her iki düğümde de henüz tamsayılı çözüm elde edilemediği için problemin alt sınırı (lower bound) başlangıçtaki

-\infty

değerinde kalır.

Dallanma, amaç fonksiyonuna katkısı olan ancak daha küçük değere sahip olan

x_1

değişkeni üzerinden yapılarak modele

x_1 \leq 2

ve

x_1 \geq 3

kısıtları eklenir; kök düğümdeki

41.25

değeri tüm algoritma için kesin alt sınır (lower bound) olarak kabul edilir.

Algoritma kuralı gereği

x_2

değişkeni seçilir ancak maksimizasyon problemi olduğu için modele sadece kısıt yönünü daraltan

x_2 \leq 3

kısıtı eklenir,

x_2 \geq 4

kısıtı uygun çözüm alanını büyüteceği gerekçesiyle dikkate alınmaz.

Gevşetilmiş çözümdeki değerler en yakın tamsayılara yuvarlanarak doğrudan

x_1=2

ve

x_2=4

noktası optimum kabul edilir ve algoritma sonlandırılarak amaç fonksiyonu değeri

Z=42

olarak belirlenir.

Show answer & explanation

Answer: $x_2$ değişkeni üzerinden $x_2 \leq 3$ ve $x_2 \geq 4$ kısıtları ile iki alt düğüm oluşturulur; $x_2 \leq 3$ kısıtlı düğümde $Z=39$ değerli tamsayılı çözüm bulunarak alt sınır (lower bound) $39$ olarak güncellenir, $x_2 \geq 4$ kısıtlı düğüm ise $Z=41$ değerini verdiğinden incelenmeye devam edilir.

Answer

İlk dallanma

x_2

değişkeni üzerinden yapılarak

x_2 \leq 3

ve

x_2 \geq 4

alt problemleri oluşturulur.

x_2 \leq 3

düğümünde tamsayılı

Z=39

çözümü bulunarak alt sınır (lower bound) güncellenir.

x_2 \geq 4

düğümü ise

Z=41

(ve kesirli

x_1

) değerini verdiği için incelenmeye devam edilir.

Doğru yaklaşımda algoritma kesirsel değeri en yüksek olan değişkeni seçer (

x_2=3.75

).

x_2 \leq 3

ve

x_2 \geq 4

dalları oluşturulur.

x_2 \leq 3

eklendiğinde sistem çözülürse

x_1=3

bulunur ve tamsayılı

(3,3)

noktasında amaç fonksiyonu

Z=39

çıkar. Bu maksimizasyon problemi için referans alt sınırı (LB) oluşturur.

x_2 \geq 4

dalı çözüldüğünde ise

x_1=1.8

ile

Z=41

üst sınır değeri (UB) üretilir. Çıkan

41

değeri, tamsayılı en iyi çözümümüz olan

39

'dan büyük olduğu için algoritma bu dalın budanamayacağına (kapatılamayacağına) hükmeder ve incelemeye devam eder.

Step-by-Step Solution

1

Dallanma yapılacak değişkenin seçilmesi.

x_1

'in kesirsel kısmı

0.25

,

x_2

'nin kesirsel kısmı

0.75

'tir. Kural gereği

x_2

değişkeni seçilir.

Dal-Sınır algoritmasında daha hızlı yakınsama sağlamak için genellikle kesirsel kısmı 0.5'e en yakın veya en büyük olan değişken dallanma için seçilir.

2

Birinci alt problemin (

x_2 \leq 3

) oluşturulması ve çözülmesi.

5x_1 + 9(3) \leq 45 \Rightarrow 5x_1 \leq 18 \Rightarrow x_1 \leq 3.6

ve

x_1 + 3 \leq 6 \Rightarrow x_1 \leq 3

. Maksimum

x_1

değeri

3

olur.

(3, 3)

noktasında

Z = 5(3) + 8(3) = 39

bulunur.

Dallanan kısıt doğrusal programlama modeline eklenir ve maksimizasyon yönünde optimum köşe noktası hesaplanır.

3

Tamsayılı çözümün değerlendirilmesi.

(3, 3)

noktası tümüyle tamsayılıdır. Maksimizasyon probleminde geçerli bir tamsayılı çözüm bulunduğunda, bu değer mevcut alt sınır (Lower Bound) olarak kabul edilir. Yeni alt sınır:

LB = 39

.

Optimum tamsayılı çözüm en kötü ihtimalle bu değerde olacaktır.

4

İkinci alt problemin (

x_2 \geq 4

) oluşturulması ve çözülmesi.

5x_1 + 9(4) \leq 45 \Rightarrow 5x_1 \leq 9 \Rightarrow x_1 \leq 1.8

.

(1.8, 4)

noktasında

Z = 5(1.8) + 8(4) = 41

bulunur.

Diğer dal incelenmeden optimum çözüm kesinleştirilemez.

5

Düğümlerin budanma (fathoming) durumunun kontrol edilmesi.

İkinci alt problemin amaç fonksiyonu değeri (

Z=41

), mevcut alt sınırdan (

LB=39

) daha büyük olduğu için budanamaz ve

x_1

değişkeni kesirli (

1.8

) olduğu için dallanmaya bu düğümden devam edilir.

Eğer bir düğümün üst sınırı, mevcut en iyi tamsayılı çözümden küçük veya ona eşit olsaydı budanırdı. Ancak burada potansiyel olarak daha iyi bir çözüm barındırdığı için inceleme sürdürülmelidir.

Key Concept

Dal-Sınır algoritmasında maksimizasyon problemleri için düğüm oluşturma, doğrusal gevşetme çözümleriyle tamsayılı alt sınır (lower bound) bulma ve budama (fathoming) şartlarının analizi.

Question 65Question →

Bir kamu enerji şirketi, bir bölgeye güneş ( $S$ ) ve rüzgâr ( $W$ ) santralleri kurmayı planlamaktadır. Bu karar problemi için değişkenler şu şekilde tanımlanmıştır:

• $y_S$ : Güneş santrali kurulursa $1$ , aksi halde $0$ değerini alan ikili değişken,
• $y_W$ : Rüzgâr santrali kurulursa $1$ , aksi halde $0$ değerini alan ikili değişken,
• $x_S$ : Güneş santralinden üretilecek enerji miktarı (MW),
• $x_W$ : Rüzgâr santralinden üretilecek enerji miktarı (MW).

Sistemin kısıtlarına ilişkin kural ve gereksinimler şunlardır:
I. Güneş santralinin maksimum üretim kapasitesi $120$ MW, rüzgâr santralinin maksimum üretim kapasitesi ise $150$ MW'tır. Enerji üretimi ancak ilgili santralin kurulması durumunda gerçekleşebilir.
II. Bölgenin asgari $80$ MW olan toplam enerji talebi bu iki santral tarafından karşılanmak zorundadır.
III. Rüzgâr santrali, sadece güneş santrali kurulduğu takdirde inşa edilebilecektir (Güneş santrali olmadan rüzgâr santrali kurulamaz, ancak güneş santrali tek başına kurulabilir).

Buna göre, bu problemi tanımlayan karma tamsayılı programlama (MIP) modeline ait kısıt kümesi aşağıdakilerden hangisinde doğru ve eksiksiz olarak verilmiştir?

x_S \leq 120 y_S

;

x_W \leq 150 y_W

;

y_S \leq y_W

;

x_S + x_W \geq 80

;

y_S, y_W \in \{0, 1\}, x_S, x_W \geq 0

x_S \geq 120 y_S

;

x_W \geq 150 y_W

;

y_W \leq y_S

;

x_S + x_W \geq 80

;

y_S, y_W \in \{0, 1\}, x_S, x_W \geq 0

x_S \leq 120 y_S

;

x_W \leq 150 y_W

;

y_W \leq y_S

;

x_S + x_W \geq 80

;

y_S, y_W \in \{0, 1\}, x_S, x_W \geq 0

x_S \leq 120 y_S

;

x_W \leq 150 y_W

;

y_S + y_W \leq 1

;

x_S + x_W \geq 80

;

y_S, y_W \in \{0, 1\}, x_S, x_W \geq 0

x_S \leq 120

;

x_W \leq 150

;

y_W \leq y_S

;

x_S + x_W \geq 80

;

y_S, y_W \in \{0, 1\}, x_S, x_W \geq 0

Show answer & explanation

Answer: $x_S \leq 120 y_S$ ; $x_W \leq 150 y_W$ ; $y_W \leq y_S$ ; $x_S + x_W \geq 80$ ; $y_S, y_W \in \{0, 1\}, x_S, x_W \geq 0$

Answer

Karma tamsayılı modelde, sürekli değişkenlerin ikili değişkenlerle kapasite sınırlarına doğru bağlandığı ve rüzgâr santralinin güneş santraline olan mantıksal ön koşulunun

y_W \leq y_S

şeklinde ifade edildiği kısıt kümesi doğru cevaptır.

Doğru formülasyonda; üretim miktarları, kurulum karar değişkenleri ile

x \leq M \cdot y

formatında doğru biçimde sınırlandırılmıştır (

x_S \leq 120 y_S

ve

x_W \leq 150 y_W

). Ayrıca 'rüzgâr sadece güneş kurulursa inşa edilebilir' mantıksal önermesi,

y_W

ikili değişkeninin ancak

y_S=1

iken

1

olabileceğini şart koşan

y_W \leq y_S

eşitsizliği ile hatasız modellenmiştir. Talep kısıtı ve değişken tanımları da bütünüyle uygundur.

Step-by-Step Solution

1

Sürekli ve ikili değişkenler arasındaki kapasite (bağlantı) kısıtlarının oluşturulması.

x_S \leq 120 y_S

ve

x_W \leq 150 y_W

Enerji üretiminin (

x

) ancak o santral kurulduğunda (

y=1

) gerçekleşebilmesi için, sürekli değişkenin üst sınırı ilgili ikili değişkenle çarpılmalıdır.

y=0

iken

x=0

olmaya zorlanır.

2

Ön koşul (mantıksal bağımlılık) kısıtının oluşturulması.

y_W \leq y_S

Rüzgâr santralinin (

y_W

) kurulabilmesi güneş santralinin (

y_S

) kurulmasına bağlıdır. Güneş santrali yoksa (

y_S=0

), rüzgâr santrali olamaz (

y_W=0

). Güneş santrali varsa (

y_S=1

), rüzgâr santrali olabilir veya olmayabilir (

y_W \le 1

).

3

Talep kısıtının oluşturulması ve değişken yapılandırmasının tanımlanması.

x_S + x_W \geq 80

ve

y_S, y_W \in \{0, 1\}, x_S, x_W \geq 0

Bölgenin toplam enerji ihtiyacı asgari

80

MW olduğundan iki santralin üretim toplamı bu değere eşit veya büyük olmalıdır. Karar değişkenlerinin doğası gereği kurulumlar ikili, üretimler sürekli ve negatif olmayan değişkenlerdir.

Key Concept

Karma Tamsayılı Modellerde Mantıksal ve Kapasite Kısıtlarının Kurulması

Question 66Question →

Bir üretim planlaması için oluşturulan iki değişkenli saf tamsayılı maksimizasyon problemi aşağıda verilmiştir:

\text{Maksimum } Z = 3x_1 + 4x_2

\text{Kısıtlar:}

2x_1 + x_2 \leq 6

2x_1 + 3x_2 \leq 9

x_1, x_2 \geq 0 \text{ ve tamsayı}

Bu problem Dal-Sınır (Branch and Bound) algoritması kullanılarak çözülmektedir. Başlangıç (kök) düğümünde tamsayı kısıtları gevşetilerek çözülen doğrusal programlama modelinin optimal çözümü $x_1 = 2,25$ , $x_2 = 1,5$ ve amaç fonksiyonu değeri $Z = 12,75$ olarak bulunmuştur.
Algoritmanın standart işleyişine göre, tamsayı olmayan değişkenler arasından en büyük kesirli kısma sahip olan değişken seçilerek ilk dallanma yapılacaktır.

Buna göre, kök düğümden yapılan bu dallanma işlemi sonucunda elde edilecek iki yeni alt düğümün gevşetilmiş (relaxed) amaç fonksiyonu ( $Z$ ) değerleri aşağıdakilerden hangisinde doğru olarak verilmiştir?

x_2 \leq 1

dalı için

Z = 10,75

ve

x_2 \geq 2

dalı için

Z = 14,75

x_1 \leq 2

dalı için

Z = 12,67

ve

x_1 \geq 3

dalı için

Z = 9,0

x_2 \leq 1

dalı için

Z = 11,5

ve

x_2 \geq 2

dalı için

Z = 12,5

x_2 \leq 1

dalı için

Z = 11,5

ve

x_2 \geq 1

dalı için

Z = 12,75

x_2 \leq 1

dalı için

Z = 10,0

ve

x_2 \geq 2

dalı için

Z = 11,0

Show answer & explanation

Answer: $x_2 \leq 1$ dalı için $Z = 11,5$ ve $x_2 \geq 2$ dalı için $Z = 12,5$

Answer

Doğru değerler

x_2 \leq 1

dalı için

Z = 11,5

ve

x_2 \geq 2

dalı için

Z = 12,5

'tir.

Doğru dallanma kuralı uygulanarak en büyük kesirli kısma sahip olan

x_2

değişkeni seçilmiş ve

x_2 \leq 1

ile

x_2 \geq 2

dalları oluşturulmuştur. Her iki dal için doğrusal programlama modeli yeni kısıtlarla yeniden çözüldüğünde sırasıyla

Z=11,5

ve

Z=12,5

değerlerine ulaşılır.

Step-by-Step Solution

1

Dallanma değişkenini belirleme

x_1

'in kesirli kısmı

0,25

ve

x_2

'nin kesirli kısmı

0,50

'dir.

Algoritma kuralı gereği en büyük kesirli kısma sahip olan değişken (

x_2

) üzerinden dallanma yapılır.

2

Dallanma kısıtlarını oluşturma

İki yeni alt düğüm için

x_2 \leq 1

ve

x_2 \geq 2

kısıtları elde edilir.

x_2=1,5

tamsayı olmadığı için bir alt tamsayıya yuvarlanarak sol dal, bir üst tamsayıya yuvarlanarak sağ dal oluşturulur.

3

x_2 \leq 1

dalı için problemi çözme

Mevcut kısıtlarda

x_2=1

alındığında dar kısıt

2x_1 + 1 \leq 6 \Rightarrow x_1 \leq 2,5

olur. Bu dal için

Z = 3(2,5) + 4(1) = 11,5

bulunur.

Amaç fonksiyonunu maksimize etmek için kısıtların izin verdiği en büyük değerler olan

x_1=2,5

ve

x_2=1

seçilir.

4

x_2 \geq 2

dalı için problemi çözme

Mevcut kısıtlarda

x_2=2

alındığında dar kısıt

2x_1 + 6 \leq 9 \Rightarrow x_1 \leq 1,5

olur. Bu dal için

Z = 3(1,5) + 4(2) = 12,5

bulunur.

Tüm kısıtları aynı anda sağlayan en uygun değerler olan

x_1=1,5

ve

x_2=2

belirlenir.

Key Concept

Dal-Sınır Algoritmasında Düğüm Değerlendirme

Question 67Question →

Bir mobilya atölyesi, masa ( $x$ ) ve sandalye ( $y$ ) ü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:

Maks \quad Z = 8x + 5y

Kısıtlayıcı Fonksiyonlar:

x + y \leq 6

9x + 5y \leq 45

x, y \geq 0 \text{ ve tamsayı}

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

39

40

41,25

42

45

Show answer & explanation

Answer: 40

Answer

Problemin tamsayı kısıtları altındaki optimum çözümü

(5, 0)

noktasında gerçekleşir ve elde edilecek maksimum

Z

değeri

40

'tır.

Doğrusal programlama gevşetmesinin optimum noktası

(3,75 ; 2,25)

olup amaç fonksiyonu değeri

41,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)

noktası

9(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)

noktası için

Z = 8(3)+5(3)=39

bulunurken, uygun alanın sağ alt köşesindeki

(5, 0)

noktasında kısıtlar sağlanır (

5+0 \leq 6

ve

9(5)+0 \leq 45

) ve

Z = 8(5)+5(0)=40

değeri elde edilir. Maksimum tamsayı değeri

40

'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=6

ve

9x+5y=45

) ortak çözülerek

x=3,75

ve

y=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)

noktası denendiğinde

9(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)

noktası için

Z=39

,

(4, 1)

noktası için

Z=37

ve

(5, 0)

noktası için

Z=40

hesaplanır.

Amaç fonksiyonunu (

Z=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 68Question →

Bir kamu kurumunun bütçe kısıtları altındaki yatırım projelerinin seçimi için oluşturulan ve Balas'ın Kapalı Sayımlama (Additive) algoritması ile çözülen bir $0-1$ tamsayılı minimizasyon modelinde, çözüm ağacının belirli bir düğümünde 1. ve 5. projelere onay verilmiş ( $x_1 = 1$ ve $x_5 = 1$ ), 2., 3. ve 4. projelerin durumu ise henüz karara bağlanmamıştır ( $x_2, x_3, x_4$ serbest değişkendir).

Modelin kaynak kullanım kısıtlarından birinin matematiksel ifadesi şöyledir:

4x_1 - 3x_2 + 5x_3 - 2x_4 + 2x_5 \le -4

Buna göre, Balas algoritmasının bu kısıtı değerlendirmesi ve ilgili düğüm için vereceği algoritmik karar aşağıdakilerden hangisidir?

Serbest değişkenlerin alabileceği en elverişli değerler dahi kısıt eşitsizliğini sağlamaya yetmediğinden, bu düğüm uygunsuzluk (infeasibility) gerekçesiyle budanır.

Kısıtın sağlanabilmesi için katsayıları negatif olan

x_2

ve

x_4

değişkenlerine zorunlu olarak

1

atanarak bu düğüm üzerinden dallanma işlemine devam edilir.

Mevcut atamalar sonucunda eşitsizliğin sol tarafı pozitif bir değer aldığı için, uygunluk testi bırakılarak doğrudan amaç fonksiyonu sınır (bound) testine geçilir.

Serbest değişkenlerden katsayısı en büyük ve pozitif olan

x_3

değişkenine öncelikle

0

değeri atanarak kısıt ihlali giderilmeye çalışılır ve alt dallara geçilir.

Mevcut atamalar eşitsizliği sağlamadığı için kısıt yönü tersine çevrilir ve düğüm budanmadan çözüm araştırmasına aynı daldan devam edilir.

Show answer & explanation

Answer: Serbest değişkenlerin alabileceği en elverişli değerler dahi kısıt eşitsizliğini sağlamaya yetmediğinden, bu düğüm uygunsuzluk (infeasibility) gerekçesiyle budanır.

Answer

Serbest değişkenlerin alabileceği en elverişli değerler dahi kısıt eşitsizliğini sağlamaya yetmediğinden, bu düğüm uygunsuzluk (infeasibility) gerekçesiyle budanır.

Balas algoritmasında (Kapalı Sayımlama) bir düğümün uygun bir çözüm üretip üretemeyeceği, serbest değişkenlere eşitsizliği en elverişli hale getirecek değerler verilerek test edilir.

4x_1 - 3x_2 + 5x_3 - 2x_4 + 2x_5 \le -4

kısıtında

x_1 = 1

ve

x_5 = 1

atandığında, eşitsizlik

-3x_2 + 5x_3 - 2x_4 \le -10

halini alır. Eşitsizlik yönü

\le

olduğu için sol tarafı en küçük yapmak hedeflenir. Negatif katsayılı olanlara

1

(

x_2=1, x_4=1

), pozitif katsayılı olana

0

(

x_3=0

) verdiğimizde sol tarafın alabileceği en küçük değer

-5

olur.

-5

değeri

-10

'dan küçük veya eşit olmadığı için, bu kısıt serbest değişkenlerin alacağı hiçbir değerle sağlanamaz. Kesin kısıt ihlali söz konusu olduğundan düğüm uygunsuzluk (infeasibility) gerekçesiyle algoritmada derhal budanır.

Step-by-Step Solution

1

Mevcut atamaları kısıt denkleminde yerine koyun.

4(1) - 3x_2 + 5x_3 - 2x_4 + 2(1) \le -4

işlemi yapılarak

6 - 3x_2 + 5x_3 - 2x_4 \le -4

elde edilir.

Serbest değişkenlerin sağlaması gereken kalan eşitsizliği bulmak için sabitlenmiş değerler denkleme yansıtılır.

2

Eşitsizliği sadeleştirin.

Sabit olan

6

karşı tarafa atıldığında

-3x_2 + 5x_3 - 2x_4 \le -10

eşitsizliğine ulaşılır.

Serbest değişkenlerin hedef eşik değerini tam olarak görmek için matematiksel sadeleştirme yapılır.

3

Sol tarafı minimize edecek en elverişli

0-1

atamalarını belirleyin.

Sol tarafın en küçük değeri alabilmesi için katsayısı negatif olan değişkenlere

1

(

x_2 = 1, x_4 = 1

), katsayısı pozitif olan değişkenlere

0

(

x_3 = 0

) atanır. Bu durumda sol taraf:

-3(1) + 5(0) - 2(1) = -5

olur.

Bir düğümün uygun bir çözüm üretme ihtimalini test etmek için, "küçük eşittir" (

\le

) kısıt yönüne göre sol taraf matematiksel olarak elde edilebilecek en küçük değere çekilir.

4

Elde edilen minimum değeri eşitsizliğin sağ tarafı ile karşılaştırın.

Bulunan en küçük değer olan

-5

, eşitsizliğin sağ tarafındaki

-10

değerinden küçük veya eşit değildir (

-5 \not\le -10

).

Serbest değişkenler kullanılarak kısıtı sağlamak adına yapılabilecek en iyi atama bile eşitsizliği sağlayamıyorsa, bu düğümden türetilecek hiçbir çözüm uygun (feasible) olamaz ve düğüm uygunsuzluktan dolayı budanır.

Key Concept

Balas Algoritmasında Uygunsuzluk (Infeasibility) Budama Kriteri

Question 69Question →

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:

Maksimum \quad Z = 4x_1 + 5x_2

Kısıtlar:

3x_1 + 2x_2 \leq 14

x_1 + 4x_2 \leq 15

x_1, x_2 \geq 0 \text{ ve tamsayı}

(Burada $x_1$ ve $x_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 $Z$ (kâr) değeri aşağıdakilerden hangisidir?

25.9

27

24

23

22

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

Question 70Question →

Afet yönetimi alanında faaliyet gösteren bir STK, kısıtlı kaynaklarını en verimli şekilde değerlendirebilmek amacıyla karar değişkenleri $x_1$ (arama-kurtarma ekibi) ve $x_2$ (sağlık destek aracı) olan bir saf tamsayılı doğrusal programlama modeli tasarlamıştır.

Kurulan modelin amaç fonksiyonu $\text{Maksimum } Z = 7x_1 + 5x_2$ şeklindedir ve kısıtlar şöyledir:
$4x_1 + 3x_2 \leq 25$
$2x_1 + x_2 \leq 10$
$x_1, x_2 \geq 0$ ve tamsayı.

Modelin tamsayı kısıtları gevşetildiğinde kök düğümün (root node) optimum çözümü $x_1 = 2.5$ , $x_2 = 5$ ve $Z = 42.5$ olarak bulunmuştur.
Bu problemi Dal-Sınır (Branch and Bound) algoritmasıyla çözerken, algoritmanın ilk aşamasında modele $x_1 \geq 3$ kısıtı eklenerek yeni bir alt düğüm oluşturulmuştur.

Buna göre, oluşturulan bu yeni alt düğümün doğrusal programlama problemi çözüldüğünde elde edilecek çözümün durumu ve amaç fonksiyonu ( $Z$ ) değeri aşağıdakilerden hangisidir?

Kesirli bir çözüm bulunur ve dallanmaya devam edilir,

Z = \frac{128}{3}

Tamsayılı bir çözüm bulunur ve bu dal budanır (fathomed),

Z = 41

Kısıtları sağlayan uygun bir çözüm alanı yoktur (İnfeasible), dal budanır

Tamsayılı bir çözüm bulunur ve bu dal budanır,

Z = 46

Kesirli bir çözüm bulunur ve dallanmaya devam edilir,

Z = 42.5

Show answer & explanation

Answer: Tamsayılı bir çözüm bulunur ve bu dal budanır (fathomed), $Z = 41$

Answer

Eklenen

x_1 \geq 3

kısıtı altında model çözüldüğünde en iyi tamsayılı çözüm olan

(3, 4)

noktası elde edilir ve dal budanır,

Z = 41

olur.

Düğümün modeli çözülürken

x_1 \geq 3

bölgesi incelendiğinde, maksimizasyon problemi olduğundan

x_1

'in

3

sınırında

x_2

'nin alabileceği maksimum değer aranır.

2x_1 + x_2 \leq 10

kısıtı

x_2 \leq 4

sınırını,

4x_1 + 3x_2 \leq 25

kısıtı ise

x_2 \leq 13/3

sınırını getirir. En kısıtlayıcı sınır

x_2 \leq 4

olduğundan optimum nokta

x_1=3

,

x_2=4

olur. Bu değerlerin ikisi de tamsayı olduğundan algoritma bu dalı 'tamsayılı çözüm bulundu' diyerek budar ve Z=41 adayı kaydedilir.

Step-by-Step Solution

1

Oluşturulan yeni alt düğümün (node) modelini tanımla.

Maksimum

Z = 7x_1 + 5x_2

Kısıtlar:

4x_1 + 3x_2 \leq 25

,

2x_1 + x_2 \leq 10

, ve eklenen yeni kısıt

x_1 \geq 3

.

Dal-Sınır algoritmasında her yeni düğüm, bir önceki düğümün kısıtlarına dallanma kısıtının eklenmesiyle oluşur.

2

Amaç fonksiyonunu maksimize etmek için

x_1

'in alabileceği en küçük sınır değeri olan

x_1 = 3

değerini mevcut kısıtlarda yerine koyarak

x_2

için üst sınırları hesapla.

1. Kısıt için:

4(3) + 3x_2 \leq 25 \Rightarrow 12 + 3x_2 \leq 25 \Rightarrow 3x_2 \leq 13 \Rightarrow x_2 \leq 4.33

2. Kısıt için:

2(3) + x_2 \leq 10 \Rightarrow 6 + x_2 \leq 10 \Rightarrow x_2 \leq 4

x_1

artarken

x_2

'nin kapasite kısıtları nedeniyle alabileceği maksimum değeri bulmak gereklidir.

3

Elde edilen

x_2

sınırlarından en kısıtlayıcı olanı seçerek düğümün optimum noktasını belirle.

x_2 \leq 4

eşitsizliği daha kısıtlayıcıdır. Maksimum Z için

x_1 = 3

ve

x_2 = 4

seçilir.

Tüm kısıtların aynı anda sağlanması (uygun çözüm bölgesi) için en dar sınırın (minimum üst sınırın) geçerli olması gerekir.

4

Bulunan

(3, 4)

noktasında amaç fonksiyonu değerini hesapla ve düğümün durumunu (tamsayılılık kontrolü) değerlendir.

Z = 7(3) + 5(4) = 21 + 20 = 41

. Hem

x_1

hem de

x_2

tamsayı olduğu için dal 'tamsayılılık' gerekçesiyle budanır (fathomed).

Dal-sınır yönteminde, çözümü tamsayı çıkan düğümler dallandırılmaya devam edilmez; bunlar olası optimum çözüm (incumbent) adayı olarak kaydedilir.

Key Concept

Dal-Sınır Algoritmasında Alt Düğüm (Node) Değerlendirmesi ve Budama

Alternative Method

Grafik çözüm yöntemi kullanılarak da bu sonuca ulaşılabilir. Koordinat sisteminde kısıtlar çizilip

x_1 = 3

doğrusunun sağında kalan uygun çözüm bölgesinin köşeleri incelendiğinde,

(3,4)

noktasının bölgedeki en iyi tamsayılı köşe olduğu kolayca görülebilir.

Estimated Time:2m 0s

Question 71Question →

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 = 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: $Z_X = 127.4$ (En az bir değişken kesirli)
• Düğüm Y: $Z_Y = 125.8$ (En az bir değişken kesirli)
• Düğüm Z: $Z_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?

Düğüm Y'nin amaç fonksiyonu değeri (

125.8

), mevcut alt sınırdan (

125

) büyük olduğu için daha iyi bir tamsayılı çözüm bulma ihtimaline karşı Düğüm Y dallandırılmaya devam edilmelidir.

Düğüm X'in amaç fonksiyonu değeri en yüksek olduğu için, bu düğümdeki kesirli değişkenler doğrudan en yakın tamsayıya yuvarlanarak yeni alt sınır

127

olarak güncellenmelidir.

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.

Düğüm Z'nin amaç fonksiyonu değeri mevcut alt sınırdan küçük olsa da, dallandırma kısıtları eklendikçe amaç fonksiyonu değeri artabileceği için Düğüm Z aktif tutulmalıdır.

Düğümlerin tamamında en az bir değişken kesirli çıktığı için problemin uygun bir saf tamsayılı çözümü olmadığı kararına varılarak algoritma derhal sonlandırılmalıdır.

Show answer & explanation

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.

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

Z

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.8

'dir. Değişkenler tamsayıya zorlandığında, bu daldan elde edilebilecek en büyük

Z

değeri aşağı yuvarlanarak en fazla

125

olabilir. Algoritma zaten

Z = 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 \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

Z

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.

Z_Y = 125.8

olduğuna göre, değişkenler tamsayı olmaya zorlandığında bu daldan elde edilebilecek en yüksek

Z

değeri

\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 (

125

), halihazırda elimizde bulunan mevcut en iyi çözüme (

Z = 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 < 125

) zaten budanır. Sadece Düğüm X (

\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 72Question →

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 $x_2$ 'ye ait satır denklemi aşağıda verilmiştir:

x_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?

\frac{2}{5}x_4 + \frac{1}{6}x_5 + \frac{1}{4}x_6 \geq \frac{3}{5}

\frac{2}{5}x_4 + \frac{5}{6}x_5 + \frac{1}{4}x_6 \geq \frac{3}{5}

\frac{2}{5}x_4 - \frac{5}{6}x_5 + \frac{9}{4}x_6 \geq \frac{3}{5}

\frac{2}{5}x_4 + \frac{1}{6}x_5 + \frac{1}{4}x_6 \leq \frac{3}{5}

\frac{2}{5}x_4 + \frac{1}{6}x_5 + \frac{1}{4}x_6 \geq \frac{2}{5}

Show answer & explanation

Answer: $\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ı

\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ı

a_{ij} = \lfloor a_{ij} \rfloor + f_{ij}

kuralıyla kendisinden küçük en büyük tamsayı (floor) ve pozitif kesirli kısmına (

f_{ij}

) ayrılır. Kesme kısıtı

\sum f_{ij} x_j \geq f_i

temel formülü ile oluşturulur. Denklemdeki

x_4

katsayısının kesirli kısmı

\frac{2}{5}

'tir. Negatif olan

x_5

katsayısı

-\frac{5}{6}

için;

\lfloor -\frac{5}{6} \rfloor = -1

işlemiyle kesirli kısım

-\frac{5}{6} - (-1) = \frac{1}{6}

bulunur.

x_6

katsayısı

\frac{9}{4} = 2 + \frac{1}{4}

olduğundan kesirli kısmı

\frac{1}{4}

'tür. Eşitliğin sağ tarafı

\frac{23}{5} = 4 + \frac{3}{5}

yapılarak

f_i = \frac{3}{5}

olarak belirlenir. Tüm kesirli bileşenler

\sum f_{ij} x_j \geq f_i

denklemine yerleştirildiğinde doğru kısıt

\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ı (

f_{ij}

) belirleme

x_4

katsayısı

\frac{2}{5}

için

f_4 = \frac{2}{5}

,

x_5

katsayısı

-\frac{5}{6}

için

\lfloor -\frac{5}{6} \rfloor = -1

olduğundan

f_5 = -\frac{5}{6} - (-1) = \frac{1}{6}

,

x_6

katsayısı

\frac{9}{4}

için

\lfloor \frac{9}{4} \rfloor = 2

olduğundan

f_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 (

a_{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ı (

f_i

) belirleme

Sağ taraf değeri

\frac{23}{5} = 4.6

olduğundan

\lfloor 4.6 \rfloor = 4

bulunur ve kesirli kısım

f_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ü (

\sum f_{ij} x_j \geq f_i

) uygulama

Bulunan

f_{ij}

ve

f_i

değerleri formüle yerleştirildiğinde

\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

Question 73Question →

Bir tamsayılı programlama problemi Dal-Sınır (Branch and Bound) algoritması kullanılarak çözülmektedir. Problemin doğrusal programlama gevşetmesi (LP Relaxation) sonucunda elde edilen ilk çözümde $x_1 = 2,25$ ve $x_2 = 1,60$ değerleri bulunmuştur. Algoritma gereği $x_2$ değişkeni üzerinden dallandırma yapılmasına karar verilmiştir.

Buna göre, bu çözüm düğümünden ( $P_0$ ) türetilecek olan iki yeni alt probleme eklenmesi gereken kısıtlar aşağıdakilerden hangisidir?

x_2 \leq 1

ve

x_2 \geq 2

x_2 < 1

ve

x_2 > 2

x_2 \leq 1

ve

x_2 \geq 1

x_2 = 1

ve

x_2 = 2

x_2 \leq 2

ve

x_2 \geq 3

Show answer & explanation

Answer: $x_2 \leq 1$ ve $x_2 \geq 2$

Answer

Dallandırma kısıtları, tamsayı olmayan değişken değerini kapsayan ardışık iki tamsayı kullanılarak

x_2 \leq 1

ve

x_2 \geq 2

şeklinde oluşturulmalıdır.

Dal-Sınır algoritmasında, tamsayı olması gereken bir değişkenin gevşetilmiş çözümdeki değeri

v

ise, dallandırma işlemi bu değeri dışarıda bırakacak şekilde

x \leq \lfloor v \rfloor

ve

x \geq \lceil v \rceil

kısıtlarının eklenmesiyle gerçekleştirilir.

x_2 = 1,60

için bu sınırlar

1

ve

2

olduğundan, doğru kısıtlar

x_2 \leq 1

ve

x_2 \geq 2

olur.

Step-by-Step Solution

1

Dallandırma yapılacak değişkenin gevşetilmiş değerini belirleme

x_2 = 1,60

Soruda dallandırmanın

x_2

değişkeni üzerinden yapılacağı belirtilmiştir.

2

Değerin alt ve üst tamsayı sınırlarını hesaplama

Alt tamsayı:

\lfloor 1,60 \rfloor = 1

; Üst tamsayı:

\lceil 1,60 \rceil = 2

Dal-Sınır algoritması, tamsayı olmayan bölgeyi çözüm dışı bırakmak için değişkenin değerini çevreleyen tamsayıları kullanır.

3

Yeni kısıtları formüle etme

x_2 \leq 1

ve

x_2 \geq 2

Mevcut uygun çözüm bölgesini ikiye bölerek tamsayı olmayan

1,60

değerini ortadan kaldırmak için bu iki kısıt alt problemlere eklenir.

Key Concept

Dal-Sınır (Branch and Bound) Algoritmasında Dallandırma Kuralı

Hints

1

Dallandırma işlemi, değişkenin tamsayı olmayan değerini içine alan tamsayı aralığını (

1 < 1,60 < 2

) bölmeyi hedefler.

2

Değişkenin değerini (

1,60

) bir altındaki tamsayıya yuvarlayarak üst sınırı, bir üstündeki tamsayıya yuvarlayarak alt sınırı oluşturmalısınız.

3

Elde edilen

1,60

değeri için eklenmesi gereken kısıtlar

x_2 \leq \text{Aşağı Yuvarla}(1,60)

ve

x_2 \geq \text{Yukarı Yuvarla}(1,60)

şeklindedir.

Practice More

Dallandırma yapıldıktan sonra alt problemlerde elde edilen

Z

değerlerinin, ana problemin

Z

değerinden daha büyük olamayacağını (maksimizasyon için) hatırlayınız.

Estimated Time:1m 30s

Tamsayılı Programlama

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Alternative Method

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Alternative Method

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Hints

Practice More