Dal-Sınır (Branch and Bound) Algoritması Practice Questions — KPSS İstatistik

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

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

\text{Kısıtlar:}

x_1 + x_2 \leq 5,2

2x_1 + x_2 \leq 9

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

Bu problemin doğrusal programlama gevşetmesi (LP relaxation) çözüldüğünde optimal çözüm $x_1 = 3,8$ ve $x_2 = 1,4$ olarak bulunmuştur. Dal-Sınır (Branch and Bound) algoritmasında "en büyük kesirsel kısım" (most fractional part) kuralı uygulandığında, ilk dallandırma adımı hangi değişken üzerinden ve hangi kısıtlarla gerçekleştirilmelidir?

x_1

değişkeni;

x_1 \leq 3

ve

x_1 \geq 4

x_2

değişkeni;

x_2 \leq 1

ve

x_2 \geq 2

x_1

değişkeni;

x_1 < 3

ve

x_1 > 4

x_1

değişkeni;

x_1 \geq 3

ve

x_1 \leq 4

x_1

değişkeni;

x_1 \leq 3,8

ve

x_1 \geq 3,8

Show answer & explanation

Answer: $x_1$ değişkeni; $x_1 \leq 3$ ve $x_1 \geq 4$

Answer

Dallandırma, kesirsel kısmı en büyük olan

x_1

değişkeni üzerinden

x_1 \leq 3

ve

x_1 \geq 4

kısıtları eklenerek yapılmalıdır.

Verilen gevşetilmiş çözümde

x_1 = 3,8

değerinin kesirsel kısmı (

0,8

),

x_2 = 1,4

değerinin kesirsel kısmından (

0,4

) daha büyüktür. Bu durumda en büyük kesirsel kısım kuralına göre

x_1

değişkeni seçilir. Değişkenin tamsayı olması gerektiğinden,

3,8

değerini dışarıda bırakacak şekilde

x_1 \leq 3

ve

x_1 \geq 4

kısıtları ile iki yeni alt problem (dal) oluşturulur.

Step-by-Step Solution

1

Gevşetilmiş çözümdeki değişkenlerin kesirsel kısımlarını belirleme

x_1 = 3,8

için kesirsel kısım

0,8

;

x_2 = 1,4

için kesirsel kısım

0,4

bulunmuştur.

Dallandırma kuralını uygulamak için her değişkenin tamsayıdan ne kadar uzak olduğu hesaplanmalıdır.

2

En büyük kesirsel kısma sahip değişkeni seçme

0,8 > 0,4

olduğu için

x_1

değişkeni seçilmiştir.

"En büyük kesirsel kısım" kuralı, tamsayı çözümden en uzak olan veya dallandığında çözüm alanını en çok etkilemesi beklenen değişkeni seçmeyi hedefler.

3

Dallandırma kısıtlarını oluşturma

x_1 \leq \lfloor 3,8 \rfloor \Rightarrow x_1 \leq 3

ve

x_1 \geq \lceil 3,8 \rceil \Rightarrow x_1 \geq 4

kısıtları elde edilmiştir.

Tamsayı olmayan bölgeyi (

3 < x_1 < 4

) çözüm kümesinden çıkarmak için değişkenin alt ve üst tamsayı değerleri yeni kısıtlar olarak atanır.

Key Concept

Dal-Sınır Algoritmasında Dallandırma Kuralı

Practice More

Elde edilen bu dallardan hangisinin daha önce inceleneceğini belirlemek için 'en iyi sınır' (best bound) kuralını inceleyebilirsiniz.

Estimated Time:1m 30s

Question 2Question →

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

\text{Maksimum } Z = 10x_1 + 15x_2

\text{Kısıtlar:}

3x_1 + 2x_2 \leq 10

x_1 + 4x_2 \leq 11

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

Bu problemin Dal-Sınır (Branch and Bound) algoritması ile çözümünde, başlangıç düğümündeki doğrusal programlama gevşetmesi sonucunda optimal çözüm $x_1 = 1,8$ ve $x_2 = 2,3$ olarak bulunmuştur.

Eğer algoritma gereği ilk dallandırma işlemi $x_1$ değişkeni üzerinden yapılacaksa, bu düğümden türetilecek iki yeni alt problem için modele eklenmesi gereken kısıtlar aşağıdakilerden hangisidir?

x_1 \leq 1

ve

x_1 \geq 2

x_1 < 1

ve

x_1 > 2

x_1 \leq 1,8

ve

x_1 \geq 2

x_2 \leq 2

ve

x_2 \geq 3

x_1 \geq 1

ve

x_1 \leq 2

Show answer & explanation

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

Answer

Dallandırma işlemi için x1 değişkenine eklenmesi gereken kısıtlar x1 ≤ 1 ve x1 ≥ 2 şeklindedir.

Doğru cevap, x1 değişkeninin mevcut kesirli değeri olan 1,8'i kapsayan tamsayılar 1 ve 2 olduğu için, bu değeri dışarıda bırakacak şekilde x1 ≤ 1 ve x1 ≥ 2 kısıtlarının eklenmesidir. Bu sayede arama uzayı ikiye bölünür ve 1 ile 2 arasındaki tamsayı olmayan bölge elenmiş olur.

Step-by-Step Solution

1

Dallandırma değişkeninin mevcut değerini belirle.

x_1 = 1,8

Dallandırma kuralı, tamsayı olması gereken ancak kesirli çıkan değişken üzerinden uygulanır.

2

Değişkenin değerini kapsayan ardışık iki tamsayıyı (taban ve tavan değerleri) bul.

1 ve 2

1,8 değeri 1 ile 2 tamsayıları arasındadır (

1 < 1,8 < 2

).

3

Alt problemleri oluşturacak eşitsizlikleri formüle et.

x_1 \leq 1

ve

x_1 \geq 2

Dal-Sınır algoritması, kesirli bölgeyi dışarıda bırakmak için değişkeni tamsayı sınırlarına zorlayan iki ayrı dal oluşturur.

Key Concept

Dal-Sınır algoritmasında dallandırma (branching) kuralı, kesirli değerin en yakın alt tamsayısından küçük-eşit ve en yakın üst tamsayısından büyük-eşit kısıtlarının eklenmesine dayanır.

Hints

1

Dallandırma yapılırken amaç, kesirli çıkan değişkenin değerini (1,8) içine alan tamsayı olmayan aralığı yok etmektir.

2

Değişkenin değerinden (1,8) küçük olan en büyük tamsayıyı ve büyük olan en küçük tamsayıyı belirleyin.

Estimated Time:1m 30s

Question 3Question →

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

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

\text{Kısıtlar:}

x_1 + x_2 \leq 4,5

x_1 \leq 3,2

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

Bu problemin doğrusal programlama gevşetmesi (LP relaxation) çözüldüğünde optimal sonuçlar $x_1 = 3,2$ , $x_2 = 1,3$ ve $Z = 32,1$ olarak bulunmuştur. Dal-Sınır (Branch and Bound) algoritması uygulanarak $x_1$ değişkeni üzerinden dallandırma yapıldığında, $x_1 \leq 3$ kısıtının eklendiği alt problemin doğrusal programlama gevşetmesine göre optimal amaç fonksiyonu değeri ( $Z$ ) aşağıdakilerden hangisidir?

31,5

32,1

24,0

31,0

Uygun çözüm yoktur

Show answer & explanation

Answer: 31,5

Answer

Yeni kısıt altında hesaplanan optimal amaç fonksiyonu değeri 31,5'tir.

Dallandırma işlemi sonucunda

x_1 \leq 3

kısıtı modele eklenir. Bu durumda

x_1

değişkeninin alabileceği en büyük değer 3 olur.

x_1 = 3

değeri ilk kısıtta (

x_1 + x_2 \leq 4,5

) yerine yazıldığında

x_2 \leq 1,5

elde edilir. Amaç fonksiyonu

8(3) + 5(1,5)

işleminden 31,5 olarak hesaplanır.

Step-by-Step Solution

1

Alt problemin kısıtlarını belirleme

x_1 + x_2 \leq 4,5

,

x_1 \leq 3,2

ve

x_1 \leq 3

Dallandırma işlemi seçilen değişkenin tamsayı olmayan değerini içine almayan iki yeni kısıt kümesi oluşturur.

2

Kısıtları sadeleştirme

x_1 + x_2 \leq 4,5

ve

x_1 \leq 3

x_1 \leq 3

kısıtı,

x_1 \leq 3,2

kısıtını kapsadığı için daha dar bir bölge tanımlar ve üsttekini gereksiz kılar.

3

Yeni uygun çözüm bölgesinde Z değerini maksimize etme

x_1 = 3

için

x_2 = 4,5 - 3 = 1,5

bulunur.

x_1

katsayısı daha yüksek olduğu için sınır değerine (3) eşitlenerek

x_2

değeri kısıt üzerinden hesaplanır.

4

Amaç fonksiyonunu hesaplama

Z = 8(3) + 5(1,5) = 24 + 7,5 = 31,5

Bulunan değişken değerleri amaç fonksiyonunda yerine konur.

Key Concept

Dal-Sınır algoritmasında bir düğümün gevşetilmiş çözümü, eklenen tamsayı kısıtları altında yeniden hesaplanır.

Practice More

x1 >= 4 kısıtının neden uygun çözüm içermediğini (infeasible) kısıt doğruları üzerinden inceleyiniz.

Estimated Time:1m 30s

Question 4Question →

Bir tamsayılı programlama problemi Dal-Sınır (Branch and Bound) algoritması kullanılarak çözülmektedir. Problemin modeli şu şekildedir:

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

\text{Kısıtlar:}

x_1 + x_2 \leq 6

9x_1 + 5x_2 \leq 45

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

Algoritmanın ilk adımında doğrusal programlama gevşetmesi çözülmüş ve başlangıç çözümü $x_1 = 3,75$ ve $x_2 = 2,25$ ( $Z = 41,25$ ) olarak bulunmuştur. Algoritmanın standart kuralları gereği $x_1$ değişkeni üzerinden dallandırma (branching) yapılmasına karar verilmiştir.

Buna göre, $x_1 \geq 4$ kısıtının eklendiği yeni alt problemin (düğümün) optimum amaç fonksiyonu değeri ( $Z$ ) kaçtır?

41,00

41,25

39,00

32,00

45,00

Show answer & explanation

Answer: 41,00

Answer

Eklenen kısıt altında bu alt problemin optimum amaç fonksiyonu değeri 41,00'dir.

Dallandırma kuralına göre

x_1 \geq 4

kısıtı modele eklendiğinde,

x_1

değişkeni amaç fonksiyonu katsayısı daha büyük olduğu için sınır değerinde (

4

) sabitlenir. Bu durumda kısıtlar altında

x_2

değişkeni en fazla

1,8

değerini alabilir.

8(4) + 5(1,8)

işlemi sonucunda bu düğüme ait amaç fonksiyonu değeri 41 olarak bulunur.

Step-by-Step Solution

1

x_1 \geq 4

kısıtını modele ekleyerek alt problemi tanımlayın.

Yeni kısıtlar:

x_1 \geq 4

,

x_1 + x_2 \leq 6

ve

9x_1 + 5x_2 \leq 45

.

Dallandırma işlemi, gevşetilmiş çözümdeki tamsayı olmayan değişkenin alt ve üst tam sayı sınırlarını kısıt olarak eklemektir.

2

Eklenen kısıtlar altında

x_2

değişkeninin alabileceği en büyük değeri belirleyin.

x_1 = 4

için:

4 + x_2 \leq 6 \Rightarrow x_2 \leq 2

ve

9(4) + 5x_2 \leq 45 \Rightarrow 5x_2 \leq 9 \Rightarrow x_2 \leq 1,8

.

Maksimizasyon probleminde,

Z

fonksiyonunun katsayıları pozitif olduğundan

x_1

ve

x_2

değişkenlerinin mümkün olan en büyük değerleri alması gerekir.

x_2

için en dar kısıt

1,8

değeridir.

3

Bulunan

(x_1, x_2)

değerlerini amaç fonksiyonunda yerine koyun.

Z = 8(4) + 5(1,8) = 32 + 9 = 41

.

Alt problemin (düğümün) sınır değerini (upper bound) bulmak için optimum nokta hesaplanır.

Key Concept

Dal-Sınır algoritmasında her bir dallandırma işlemi, tamsayı olmayan bölgeyi dışarıda bırakacak şekilde arama uzayını daraltan yeni kısıtlar ekleyerek alt problemler oluşturur.

Practice More

Bu düğümden sonra

x_2 = 1,8

değeri üzerinden yapılacak dallandırmanın sonuçlarını inceleyerek tamsayı çözüme ulaşmaya çalışın.

Estimated Time:1m 30s

Question 5Question →

Bir kamu kurumunun lojistik planlamasında kullanılmak üzere aşağıdaki tamsayılı programlama modeli oluşturulmuştur:

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

\text{Kısıtlar:}

x_1 + x_2 \leq 5

4x_1 + 7x_2 \leq 28

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

Bu problem Dal-Sınır (Branch and Bound) algoritması ile çözüldüğünde, elde edilecek en iyi tamsayılı çözümün amaç fonksiyonu değeri ( $Z$ ) kaçtır?

24

25

26,75

27

27,67

Show answer & explanation

Answer: 27

Answer

En iyi tamsayılı çözümün amaç fonksiyonu değeri 27'dir.

Problemin DP gevşetmesi çözüldüğünde

Z=27,67

bulunur. En büyük kesirsel kısma sahip olan

x_2

(2,67) üzerinden dallandırma yapıldığında,

x_2 \leq 2

kolunda

(3,2)

tamsayılı çözümü ve

Z=27

değeri elde edilir. Diğer kol olan

x_2 \geq 3

incelendiğinde ise en iyi değerin

Z=26,75

olduğu görülür. 27 değeri 26,75'ten büyük olduğu için en iyi tamsayılı çözüm 27'dir.

Step-by-Step Solution

1

Doğrusal Programlama (DP) gevşetmesini çözün.

x_1 = 2,33

(7/3),

x_2 = 2,67

(8/3) ve

Z = 27,67

(83/3)

Algoritmanın başlangıç noktasını (kök düğüm) belirlemek için tamsayı kısıtları kaldırılır.

2

En büyük kesirsel kısma sahip değişken üzerinden dallandırma yapın.

x_2

değişkeni üzerinden

x_2 \leq 2

ve

x_2 \geq 3

dalları oluşturulur.

Değişkenlerin tamsayı olmasını sağlamak için kesirsel değerler sınırlandırılır.

3

x_2 \leq 2

dalını (Düğüm 1) çözün.

x_1 = 3, x_2 = 2

ve

Z = 27

(Tamsayılı çözüm)

Bu dalda ulaşılan en iyi çözüm tüm değişkenleri tamsayı olan uygun bir noktadır.

4

x_2 \geq 3

dalını (Düğüm 2) çözün.

x_1 = 1,75, x_2 = 3

ve

Z = 26,75

Bu daldaki en iyi çözümün

Z

değeri (26,75), halihazırda bulunan tamsayılı çözümden (27) küçük olduğu için bu dal budanır.

5

Sonuçları karşılaştırarak optimumu belirleyin.

Z = 27

Elde edilen en büyük tamsayılı amaç fonksiyonu değeri çözüm olarak kabul edilir.

Key Concept

Dal-Sınır algoritmasında, bir düğümün üst sınırı (maksimizasyon için) mevcut en iyi tamsayılı çözümden küçükse, o dal daha iyi bir sonuç üretemeyeceği için budanır.

Practice More

Karışık tamsayılı (mixed-integer) programlama modellerinde sadece tamsayı olması istenen değişkenler üzerinden dallandırma yapıldığını unutmayın.

Alternative Method

Grafik yöntemiyle tamsayılı noktalar (lattice points) belirlenerek amaç fonksiyonu her biri için hesaplanabilir. (0,4), (1,3), (2,2), (3,2), (4,1) ve (5,0) noktaları uygun bölgededir. Bunlar arasında Z değerini en büyük yapan (3,2) noktasıdır.

Estimated Time:2m 30s

Question 6Question →

Aşağıda verilen saf tamsayılı programlama modeli Dal-Sınır (Branch and Bound) algoritması ile çözülmektedir:

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

\text{Kısıtlar:}

2x_1 + 3x_2 \leq 12

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

Algoritmanın başlangıç adımında (kök düğüm) elde edilen doğrusal gevşetme çözümü $x_1 = 2,4$ ve $x_2 = 2,4$ olarak bulunmuştur. $x_1$ değişkeni üzerinden dallanma (branching) yapılmasına karar verilmiştir.

Buna göre, bu dallanma sonucunda oluşturulacak iki yeni alt problemin kısıtları aşağıdakilerden hangisidir?

x_1 \leq 2

ve

x_1 \geq 3

x_1 < 2

ve

x_1 > 3

x_1 \geq 2

ve

x_1 \leq 3

x_1 \leq 2,4

ve

x_1 \geq 2,4

x_1 \leq 3

ve

x_1 \geq 4

Show answer & explanation

Answer: $x_1 \leq 2$ ve $x_1 \geq 3$

Answer

Dallanma kısıtları, değişkenin mevcut kesirli değerini dışarıda bırakacak şekilde en yakın tamsayı sınırları olan küçük-eşit 2 ve büyük-eşit 3 şeklinde belirlenmelidir.

Dal-Sınır algoritmasında, tamsayı olması gereken bir değişkenin doğrusal gevşetme çözümündeki değeri

v

ise, bu düğümden dallanma yapılırken değişkenin bu kesirli değerini içine alan

[\lfloor v \rfloor, \lceil v \rceil]

aralığı çözüm kümesinden atılır. Bu durumda

x_1 = 2,4

için taban değer 2, tavan değer 3'tür. Dolayısıyla yeni kısıtlar

x_1 \leq 2

ve

x_1 \geq 3

olarak belirlenir.

Step-by-Step Solution

1

Dallanma yapılacak değişkenin değerini belirleme

x_1 = 2,4

Soruda dallanmanın

x_1

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

2

Değişken değerinin tamsayı sınırlarını hesaplama

Alt sınır:

\lfloor 2,4 \rfloor = 2

, Üst sınır:

\lceil 2,4 \rceil = 3

Dal-Sınır algoritması kuralı gereği değişkenin bulunduğu aralıktaki tamsayı komşuları bulunur.

3

Yeni kısıtları oluşturma

x_1 \leq 2

ve

x_1 \geq 3

Sürekli olan uygun bölgeyi, kesirli kısmı dışarıda bırakacak şekilde iki ayrık alt bölgeye bölmek için bu kısıtlar eklenir.

Key Concept

Dal-Sınır Algoritması Dallanma Kuralı

Practice More

Karma tamsayılı programlama modellerinde sadece tamsayı olması gereken değişkenler üzerinden dallanma yapıldığını unutmayınız.

Estimated Time:45s

Question 7Question →

Saf tamsayılı bir doğrusal programlama problemi Dal-Sınır (Branch and Bound) algoritması ile çözülmektedir. Bir çözüm adımında, gevşetilmiş (relaxed) çözümden elde edilen sonuçlarda $x_1 = 4,6$ değeri bulunmuştur. Algoritma gereği bu değişken üzerinden yapılacak olan ilk dallandırma (branching) işleminde modele eklenecek yeni kısıtlar aşağıdakilerden hangisidir?

x_1 \leq 4

ve

x_1 \geq 5

x_1 < 4

ve

x_1 > 5

x_1 \geq 4

ve

x_1 \leq 5

x_1 \leq 3

ve

x_1 \geq 5

x_1 \leq 4

ve

x_1 \geq 6

Show answer & explanation

Answer: $x_1 \leq 4$ ve $x_1 \geq 5$

Answer

Dallandırma kuralına göre eklenecek kısıtlar

x_1 \leq 4

ve

x_1 \geq 5

şeklinde olmalıdır.

Dal-Sınır algoritmasında, bir değişken

v

gibi kesirli bir değer aldığında, mevcut çözüm bölgesini tamsayı olmayan kısmı (

\lfloor v \rfloor < x < \lceil v \rceil

) dışarıda bırakacak şekilde ikiye bölmemiz gerekir.

x_1 = 4,6

için alt tamsayı sınırı 4, üst tamsayı sınırı ise 5'tir. Bu nedenle

x_1 \leq 4

ve

x_1 \geq 5

kısıtları eklenerek iki yeni alt problem oluşturulur.

Step-by-Step Solution

1

Tamsayılı olması gereken ancak kesirli sonuç veren değişkenin belirlenmesi

x_1 = 4,6

Dal-Sınır algoritmasında dallandırma, tamsayı kısıtını sağlamayan değişkenler üzerinden yapılır.

2

Değişken değerini çevreleyen ardışık tamsayıların bulunması

\lfloor 4,6 \rfloor = 4

ve

\lceil 4,6 \rceil = 5

Değişkenin alabileceği olası tamsayı değerleri kesirli kısmın hemen altındaki ve üstündeki değerlerdir.

3

Kesirli bölgeyi dışarıda bırakacak eşitsizliklerin yazılması

x_1 \leq 4

ve

x_1 \geq 5

Bu iki kısıt,

4 < x_1 < 5

aralığındaki uygun olmayan tüm kesirli değerleri (4,6 dahil) çözüm kümesinden çıkarırken tamsayı noktaları korur.

Key Concept

Dal-Sınır Algoritmasında Dallandırma Kuralı

Estimated Time:45s

Question 8Question →

İki karar değişkenli ( $x_1, x_2 \geq 0$ ) bir saf tamsayılı maksimizasyon problemi, Dal-Sınır (Branch and Bound) algoritması kullanılarak çözülmektedir. Kök düğümde (P0) doğrusal programlama gevşetmesinin optimum çözümü $x_1 = 4,5$ , $x_2 = 5,5$ ve amaç fonksiyonu değeri $Z = 144,5$ olarak hesaplanmıştır.

Algoritmanın ilerleyen adımlarında sırasıyla aşağıdaki düğümler ve çözümler elde edilmiştir:

- P1 Düğümü (P0'dan $x_1 \leq 4$ dalı): $x_1 = 4$ , $x_2 = 5,8$ ve $Z = 142,8$
- P2 Düğümü (P0'dan $x_1 \geq 5$ dalı): $x_1 = 5$ , $x_2 = 4$ ve $Z = 140$
- P3 Düğümü (P1'den $x_2 \leq 5$ dalı): $x_1 = 3,5$ , $x_2 = 5$ ve $Z = 138,5$
- P4 Düğümü (P1'den $x_2 \geq 6$ dalı): Uygun çözüm alanına sahip değildir.

Bu bilgilere göre, algoritmanın güncel durumu ve P3 düğümü için verilecek karar aşağıdakilerden hangisinde doğru olarak ifade edilmiştir?

P2 düğümünde ilk tamsayılı çözüm elde edildiği için algoritma anında sonlandırılır ve diğer düğümlerin durumuna bakılmaksızın

Z=140

değeri optimum kabul edilir.

P3 düğümünün amaç fonksiyonu değeri (

Z=138,5

), mevcut en iyi tamsayılı çözümden (

Z=140

) küçük olduğu için budanır; incelenecek aktif düğüm kalmadığından

Z=140

kesin optimum olur.

P3 düğümü tamsayılı çözüm vermediğinden algoritma devam etmeli ve

x_1 = 3,5

değeri için kısıtlar

x_1 < 3

ve

x_1 > 4

şeklinde tanımlanarak yeni dallandırma yapılmalıdır.

P2 düğümündeki çözüm, kök düğümün gevşetilmiş üst sınır değerine (

Z=144,5

) ulaşamadığı için budanır ve P3 düğümünden standart dallandırma işlemlerine devam edilir.

Kök düğümde (P0) elde edilen gevşetilmiş çözüm değerlerinin en yakın tamsayıya yuvarlanmasıyla elde edilecek sonuç optimum kabul edileceği için, algoritma dallandırma yapmadan P0 üzerinden sonlanır.

Show answer & explanation

Answer: P3 düğümünün amaç fonksiyonu değeri ( $Z=138,5$ ), mevcut en iyi tamsayılı çözümden ( $Z=140$ ) küçük olduğu için budanır; incelenecek aktif düğüm kalmadığından $Z=140$ kesin optimum olur.

Answer

P3 düğümünün amaç fonksiyonu değeri (

Z=138,5

), mevcut en iyi tamsayılı çözümden (

Z=140

) küçük olduğu için budanır; incelenecek aktif düğüm kalmadığından

Z=140

kesin optimum olur.

Maksimizasyon problemlerinde Dal-Sınır algoritması, bulduğu her tamsayılı çözümü (P2 düğümündeki

Z=140

) bir alt sınır olarak kabul eder. Aktif düğümlerden elde edilen gevşetilmiş Z değeri bu alt sınırdan küçük veya eşitse (P3 düğümündeki

138,5 < 140

), o dalın daha iyi bir çözüm üretme ihtimali kalmadığı için dallandırma durdurulur ve budanır. Tüm açık dallar kapandığında (P4 uygunsuz, P3 bound yedi, P2 zaten tamsayı), algoritma iterasyonu tamamlar ve elimizdeki en iyi tamsayılı çözüm (

Z=140

) global optimum olur.

Step-by-Step Solution

1

Algoritmadaki mevcut en iyi tamsayılı çözümü (alt sınırı) belirle.

P2 düğümünde

x_1=5, x_2=4

tamsayı değerleri elde edilmiştir ve

Z=140

olmuştur. Maksimizasyon probleminde ilk tamsayılı çözüm bir alt sınır (Lower Bound) oluşturur: LB = 140.

Mevcut en iyi tamsayılı çözüm, diğer düğümlerin dallandırılıp dallandırılmayacağına karar vermek için bir eşik değeri görevi görür.

2

P4 düğümünün durumunu değerlendir.

P4 düğümünde uygun çözüm olmadığı (infeasible) belirtilmiştir. Bu nedenle bu dal tamamen kapatılır (budanır).

Uygun çözüm alanı olmayan bir düğümden tamsayılı çözüm elde edilemez.

3

P3 düğümünün durumunu sınırlandırma (bound) kuralı ile değerlendir.

P3 düğümünde

Z = 138,5

'tir. Maksimizasyon probleminde bu daldan elde edilebilecek maksimum tamsayılı çözüm en fazla 138,5 (hatta ondan küçük) olabilir. Ancak elimizde zaten

Z=140

veren bir çözüm vardır.

138,5 < 140

olduğundan P3 düğümü dallandırılmaz ve budanır.

Bir düğümün amacı, mevcut en iyi tamsayılı çözümden daha iyi bir sonuç potansiyeli taşımaması durumunda sınırlandırma (fathoming by bound) kuralıyla elenmesidir.

4

Algoritmanın genel durumunu kontrol et.

P0'ın dalları olan P1 ve P2 incelenmiştir. P2 tamsayılıdır. P1'in dalları olan P3 (sınır nedeniyle) ve P4 (uygunsuzluk nedeniyle) budanmıştır. Açıkta (aktif) dallandırılacak hiçbir düğüm kalmamıştır.

Tüm aktif düğümler budandığında veya tamsayılı optimum çözüme ulaştığında algoritma sonlanır.

Key Concept

Dal-Sınır (Branch and Bound) Algoritmasında Budama Kuralları ve Optimum Çözüm Koşulu

Estimated Time:3m 0s

Question 9Question →

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 10Question →

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 11Question →

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 12Question →

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

Dal-Sınır (Branch and Bound) Algoritması

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Practice More

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Hints

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Practice More

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Practice More

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Practice More

Alternative Method

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Practice More

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

Hints

Practice More