Tamsayılı Programlama Practice Questions — KPSS İstatistik

Question 1Question →

Bir üretim tesisinde, belirli bir ürünün üretilmesi için öncelikle $25.000$ TL tutarında bir hazırlık (setup) maliyetine katlanılması gerekmektedir. Hazırlık yapıldıktan sonra üretilen her birim ürünün değişken maliyeti $150$ TL'dir. Tesisin bu ürün için üretim kapasitesi en fazla $2.000$ birimdir.

$x$ : Üretilen ürün miktarı (sürekli değişken)
$y$ : Üretim kararı ( $y=1$ ise üretim yapılacak, $y=0$ ise yapılmayacak)

Buna göre, bu üretim sürecindeki toplam maliyeti minimize etmeyi amaçlayan ve kapasite kısıtını içeren en uygun karma tamsayılı programlama modeli aşağıdakilerden hangisidir?

Min \ Z = 25.000y + 150x

; Kısıt:

x \leq 2.000y

,

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

Min \ Z = 25.000 + 150x

; Kısıt:

x \leq 2.000

,

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

Min \ Z = 25.000y + 150x

; Kısıt:

x \geq 2.000y

,

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

Min \ Z = 150y + 25.000x

; Kısıt:

x \leq 2.000y

,

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

Min \ Z = 25.000y + 150x

; Kısıt:

x \leq 2.000y

,

x \geq 0, 0 \leq y \leq 1

Show answer & explanation

Answer: $Min \ Z = 25.000y + 150x$ ; Kısıt: $x \leq 2.000y$ , $x \geq 0, y \in \{0, 1\}$

Answer

Toplam maliyet fonksiyonunun hazırlık maliyetini ikili değişkenle, değişken maliyeti miktar değişkeniyle ifade ettiği ve kapasite kısıtının miktarı ikili değişkene bağladığı model doğrudur.

Doğru modelde, hazırlık maliyeti (

25.000

) sadece üretim yapıldığında (

y=1

) devreye girer. Ayrıca kapasite kısıtı olan

x \leq 2.000y

, üretim kararı verilmediğinde (

y=0

) üretim miktarını (

x

) sıfıra zorlayarak mantıksal tutarlılığı sağlar. Bu yapı hem sürekli (

x

) hem de tamsayılı (

y

) değişkenleri içerdiği için karma tamsayılı bir modeldir.

Step-by-Step Solution

1

Amaç fonksiyonunu belirleme

Z = 25.000y + 150x

Üretim kararı verilirse (

y=1

) sabit maliyet oluşur, aksi halde (

y=0

) oluşmaz. Değişken maliyet ise üretilen her birim (

x

) için eklenir.

2

Kapasite kısıtını kurma

x \leq 2.000y

Eğer

y=0

ise üretim miktarı

x = 0

olmalıdır. Eğer

y=1

ise

x

değeri kapasite sınırı olan

2.000

birime kadar çıkabilir.

3

Değişken tiplerini tanımlama

x \geq 0

(Sürekli),

y \in \{0, 1\}

(İkili/Binary)

Üretim miktarı süreklilik arz ederken, üretim kararı 'evet' veya 'hayır' şeklinde kesikli bir karardır.

Key Concept

Sabit Hazırlık Maliyetli Modeller (Fixed Charge Models)

Estimated Time:1m 30s

Question 2Question →

Bir tam sayılı programlama modelinin doğrusal gevşetmesi (LP relaxation) çözüldüğünde elde edilen optimal simpleks tablosu aşağıda verilmiştir:

Temel Değişken	$x_1$	$x_2$	$s_1$	$s_2$	Çözüm (RHS)
$Z$	0	0	$1/2$	$5/6$	$15$
$x_1$	1	0	$2/3$	$-1/6$	$7/2$
$x_2$	0	1	$1/6$	$1/3$	$5/2$

Modele tam sayı kısıtı eklendiğinde, Gomory kesme düzlemi algoritmasına göre $x_1$ temel değişkeninin bulunduğu satırdan elde edilecek olan kesme kısıtı aşağıdakilerden hangisidir?

-\frac{2}{3} s_1 - \frac{5}{6} s_2 + S_g = -\frac{1}{2}

-\frac{2}{3} s_1 + \frac{1}{6} s_2 + S_g = -\frac{1}{2}

-\frac{2}{3} s_1 - \frac{5}{6} s_2 + S_g = \frac{1}{2}

\frac{1}{3} s_1 + \frac{1}{6} s_2 + S_g = -\frac{1}{2}

-\frac{2}{3} s_1 - \frac{5}{6} s_2 + S_g = -\frac{7}{2}

Show answer & explanation

Answer: $-\frac{2}{3} s_1 - \frac{5}{6} s_2 + S_g = -\frac{1}{2}$

Answer

Kesme kısıtı,

x_1

satırındaki katsayıların ve çözüm değerinin pozitif kesirsel kısımları kullanılarak

-\frac{2}{3} s_1 - \frac{5}{6} s_2 + S_g = -\frac{1}{2}

şeklinde oluşturulur.

Doğru cevap,

x_1

satırındaki tüm katsayıların ve çözüm değerinin kesirsel kısımlarını doğru hesaplayan seçenektir.

x_1 + \frac{2}{3} s_1 - \frac{1}{6} s_2 = \frac{7}{2}

denkleminde, kesirsel kısımlar şöyledir: Çözüm için

3.5 - 3 = 0.5

,

s_1

için

\frac{2}{3} - 0 = \frac{2}{3}

,

s_2

için

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

. Bu değerler

\sum f_{ij} x_j \geq f_i

formülüne yerleştirilip tablo formuna çevrildiğinde

-\frac{2}{3} s_1 - \frac{5}{6} s_2 + S_g = -\frac{1}{2}

sonucuna ulaşılır.

Step-by-Step Solution

1

x_1

temel değişkenine ait satır denklemini yazınız.

x_1 + \frac{2}{3} s_1 - \frac{1}{6} s_2 = \frac{7}{2}

Kesme kısıtı oluşturulacak temel satırı belirlemek gerekir.

2

Katsayıların ve çözüm değerinin kesirsel kısımlarını (

f_i = a_i - \lfloor a_i \rfloor

) hesaplayınız.

RHS:

\frac{7}{2} - 3 = \frac{1}{2}

;

s_1

:

\frac{2}{3} - 0 = \frac{2}{3}

;

s_2

:

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

Gomory algoritmasında her katsayı kendisinden küçük veya eşit olan en büyük tam sayıdan çıkarılarak pozitif kesirsel kısmı bulunur.

3

Bulunan değerleri

\sum f_{ij} x_{j} \geq f_{i}

eşitsizliğine yerleştiriniz.

\frac{2}{3} s_1 + \frac{5}{6} s_2 \geq \frac{1}{2}

Kesme kısıtının temel eşitsizlik formu budur.

4

Eşitsizliği simpleks tablosuna eklenecek standart eşitlik formuna (

S_g

gevşek değişkeni ile) dönüştürünüz.

-\frac{2}{3} s_1 - \frac{5}{6} s_2 + S_g = -\frac{1}{2}

Dual simpleks yöntemiyle çözüme devam edebilmek için kısıt bu formda yazılmalıdır.

Key Concept

Gomory Kesme Düzlemi Algoritması'nda kesme kısıtı, temel olmayan değişkenlerin katsayılarının ve çözüm değerinin kesirsel kısımları kullanılarak oluşturulur; negatif katsayıların kesirsel kısmı

a - \lfloor a \rfloor

formülüyle her zaman pozitife dönüştürülür.

Practice More

Bundan sonraki adımda, eklenen bu kısıt ile dual simpleks yöntemini uygulayarak yeni bir pivot işlemi yapılması beklenebilir.

Estimated Time:2m 0s

Question 3Question →

Bir yatırım planlama probleminde değerlendirilen $x_1, x_2, x_3$ ve $x_4$ projeleri için (proje seçilirse 1, seçilmezse 0 değerini alan karar değişkenleri) aşağıdaki kısıtlar belirlenmiştir:

- Proje 1 ( $x_1$ ) seçilirse, Proje 2 ( $x_2$ ) de mutlaka seçilmelidir.
- Proje 3 ( $x_3$ ) ve Proje 4 ( $x_4$ ) arasından en fazla biri seçilebilir.

Buna göre, bu mantıksal kısıtları temsil eden doğrusal eşitsizlik takımı aşağıdakilerden hangisidir?

x_1 \leq x_2

ve

x_3 + x_4 \leq 1

x_1 \geq x_2

ve

x_3 + x_4 \leq 1

x_1 \leq x_2

ve

x_3 + x_4 \geq 1

x_1 + x_2 \leq 1

ve

x_3 + x_4 \leq 1

x_1 \leq x_2

ve

x_3 + x_4 = 1

Show answer & explanation

Answer: $x_1 \leq x_2$ ve $x_3 + x_4 \leq 1$

Answer

Doğru modelleme

x_1 \leq x_2

ve

x_3 + x_4 \leq 1

şeklinde olmalıdır.

Mantıksal olarak 'A ise B' koşulu

x_A \leq x_B

eşitsizliği ile modellenir. Çünkü

x_A=1

olduğunda

x_B

değerinin de 1 olması matematiksel olarak zorunlu kılınır. 'En fazla biri' kısıtı ise toplamın 1 değerini aşamayacağını gösteren

x_3 + x_4 \leq 1

ifadesi ile doğru bir şekilde temsil edilir.

Step-by-Step Solution

1

Koşullu kısıtın (

x_1 \rightarrow x_2

) analizi

x_1 \leq x_2

Eğer

x_1 = 1

ise eşitsizlik

1 \leq x_2

halini alır ve

x_2

değerini 1 olmaya zorlar. Eğer

x_1 = 0

ise

0 \leq x_2

olur, bu durumda

x_2

hem 0 hem de 1 değerini alabilir. Bu durum tam olarak '1 seçilirse 2 de seçilmeli' mantığını karşılar.

2

Seçim kısıtının ('en fazla k') analizi

x_3 + x_4 \leq 1

'En fazla biri' ifadesi, seçilen projelerin toplam sayısının 1'den büyük olamayacağını belirtir. Bu durumda toplam ya 0 (hiçbiri seçilmedi) ya da 1 (yalnızca biri seçildi) olabilir.

Key Concept

0-1 Tamsayılı Programlamada Mantıksal Koşulların Modellenmesi

Hints

1

Karar değişkenlerinin sadece 0 veya 1 değerini alabildiğini unutmayın ve mantıksal cümleleri deneme yanılma yoluyla test edin.

2

'

x_1

seçilirse' demek

x_1=1

demektir. Bu durumda eşitsizliğin

x_2

'yi de 1 yapıp yapmadığını kontrol edin.

3

'En fazla k tane' kısıtı her zaman 'Toplam

\leq k

' şeklinde ifade edilir.

Practice More

Benzer şekilde 'A seçilmezse B de seçilmemelidir' veya 'A ve B aynı anda seçilemez' gibi kısıtların modelleme farklarını inceleyebilirsiniz.

Alternative Method

Mantıksal kısıtları doğrulamak için her bir durum (0,0), (0,1), (1,0), (1,1) için eşitsizliğin sağlanıp sağlanmadığını gösteren bir tablo oluşturulabilir.

Estimated Time:1m 30s

Question 4Question →

Saf tam sayılı bir programlama modelinin doğrusal gevşetmesi çözüldüğünde elde edilen optimal simpleks tablosunda $x_1$ temel değişkeninin yer aldığı satır şu şekildedir:

Temel Değişken	$x_1$	$x_2$	$s_1$	$s_2$	Sağ Taraf
$x_1$	$1$	$0$	$7/4$	$-1/2$	$11/4$

Buna göre, Gomory kesme düzlemi algoritması kullanılarak bu satırdan elde edilecek olan kesme kısıtı aşağıdakilerden hangisidir?

\frac{3}{4} s_1 + \frac{1}{2} s_2 \geq \frac{3}{4}

\frac{3}{4} s_1 - \frac{1}{2} s_2 \geq \frac{3}{4}

\frac{3}{4} s_1 + \frac{1}{2} s_2 \leq \frac{3}{4}

\frac{1}{4} s_1 + \frac{1}{2} s_2 \geq \frac{3}{4}

\frac{3}{4} s_1 + \frac{1}{2} s_2 \geq \frac{1}{4}

Show answer & explanation

Answer: $\frac{3}{4} s_1 + \frac{1}{2} s_2 \geq \frac{3}{4}$

Answer

Gomory kesme kısıtı

\frac{3}{4} s_1 + \frac{1}{2} s_2 \geq \frac{3}{4}

şeklindedir.

Doğru cevap olan seçenekte,

7/4

katsayısı

1 + 3/4

olarak,

-1/2

katsayısı

-1 + 1/2

olarak ve

11/4

sağ taraf sabiti

2 + 3/4

olarak doğru ayrıştırılmıştır. Gomory kuralına göre

\sum f_j x_j \geq f_0

yapısı uygulandığında

\frac{3}{4} s_1 + \frac{1}{2} s_2 \geq \frac{3}{4}

ifadesine ulaşılır.

Step-by-Step Solution

1

Değişken katsayılarını ve sağ taraf sabitini tam sayı (

I

) ve pozitif kesirsel (

f

) kısımlarına ayırın.

7/4 = 1 + 3/4 \rightarrow f_{s1} = 3/4

-1/2 = -1 + 1/2 \rightarrow f_{s2} = 1/2

11/4 = 2 + 3/4 \rightarrow f_{RHS} = 3/4

Gomory kısıtı, denklemin kesirsel kısımlarının toplamının sağ tarafın kesirsel kısmından büyük veya eşit olması kuralına dayanır.

2

Elde edilen kesirsel kısımları kullanarak kısıt denklemini oluşturun.

3/4 s_1 + 1/2 s_2 \geq 3/4

Değişkenlerin katsayılarının kesirsel kısımları ile çarpımlarının toplamı, sağ tarafın kesirsel kısmına eşit veya ondan büyük olmalıdır.

Key Concept

Gomory kesme düzlemi algoritmasında kesme kısıtı oluşturulurken, negatif katsayıların kesirsel kısmı belirlenirken katsayıdan küçük veya eşit olan en büyük tam sayı (taban değer) çıkarılmalıdır (

f = a - \lfloor a \rfloor

).

Question 5Question →

Aşağıdaki 0-1 tamsayılı programlama problemi Balas (Kapalı Sayımlama) algoritması ile çözülmektedir:

\text{Minimize } Z = 5x_1 + 3x_2 + 8x_3

Kısıtlar:

x_1 + x_2 + x_3 \geq 2

2x_1 - x_2 + 4x_3 \geq 5

x_1, x_2, x_3 \in \{0, 1\}

Algoritmanın belirli bir aşamasında mevcut en iyi çözüm değerinin (incumbent) $Z^* = 10$ olduğu ve $x_1 = 0$ kısmi atamasının yapıldığı düğüme (alt probleme) gelindiği varsayıldığında, bu düğüm için aşağıdakilerden hangisi söylenebilir?

Düğüm, kısıtların sağlanması mümkün olmadığı (uygun çözüm bulunmadığı) için kapatılır.

Düğümden elde edilebilecek potansiyel amaç fonksiyonu değeri

Z^* = 10

değerinden küçük olduğu için dallanmaya devam edilir.

Kısmi çözüm kısıtları zaten sağladığı için bu düğüm bir 'tam çözüm' olarak işaretlenir.

Düğüm, amaç fonksiyonu alt sınırı mevcut en iyi çözüm olan 10 değerini aştığı için budanır.

Düğüm, doğrusal programlama gevşetmesi tamsayılı sonuç verdiği için kapatılır.

Show answer & explanation

Answer: Düğüm, kısıtların sağlanması mümkün olmadığı (uygun çözüm bulunmadığı) için kapatılır.

Answer

Düğüm, kısıtların sağlanması mümkün olmadığı (uygun çözüm bulunmadığı) için kapatılır.

Verilen

x_1 = 0

ataması altında ikinci kısıt

-x_2 + 4x_3 \geq 5

halini almaktadır. Bu kısıtta

x_2

ve

x_3

değişkenleri 0 veya 1 değerlerini alabildiğinden, sol tarafın ulaşabileceği en büyük değer (en iyimser durum)

x_2=0

ve

x_3=1

iken 4'tür.

4 \geq 5

ifadesi matematiksel olarak imkansız olduğu için bu düğümden hiçbir uygun çözüm elde edilemez ve Balas algoritması gereği düğüm kapatılır.

Step-by-Step Solution

1

Kısmi atama değerini kısıtlarda yerine koyun.

x_1 = 0

için ikinci kısıt:

2(0) - x_2 + 4x_3 \geq 5 \Rightarrow -x_2 + 4x_3 \geq 5

.

Düğümün olanaklılığını test etmek için sabitlenen değişkenlerin etkisini görmek gerekir.

2

Kısıtın sol tarafının alabileceği maksimum değeri hesaplayın.

-x_2 + 4x_3

ifadesi için

x_2=0

ve

x_3=1

seçildiğinde maksimum değer

-0 + 4(1) = 4

olur.

Değişkenler 0 veya 1 değerini alabildiği için kısıtın en iyimser durumda bile sağlanıp sağlanamayacağı kontrol edilir.

3

Hesaplanan maksimum değeri kısıt sağ tarafı ile karşılaştırın.

4 < 5

olduğu için kısıt hiçbir

x_2, x_3 \in \{0, 1\}

kombinasyonu için sağlanamaz.

Maksimum değer bile sınırı aşamıyorsa bu dal üzerinde uygun bir çözüm bulunması imkansızdır.

4

Algoritma kararını belirleyin.

Düğüm 'uygunsuzluk' (infeasibility) nedeniyle budanır (kapatılır).

Balas algoritmasında kısıt sağlanamıyorsa o dalın taranmasına devam edilmez.

Key Concept

Balas Algoritmasında Budama (Fathoming) Kriterleri

Question 6Question →

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

Maksimum \quad Z = 3x_1 + 2x_2

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 model grafik çözüm yöntemi ile çözüldüğünde, amaç fonksiyonunun alabileceği en büyük (optimal) değer aşağıdakilerden hangisidir?

9

9,75

10

8

6

Show answer & explanation

Answer: 9

Answer

Modelin optimal tamsayılı çözümünde amaç fonksiyonu değeri 9 olarak bulunur.

Verilen kısıtlar altında tamsayı koordinatlı noktalar incelendiğinde, (3,0) noktası her iki kısıtı da sağlar (

2(3)+0=6 \leq 6

ve

2(3)+3(0)=6 \leq 9

) ve

3(3)+2(0)=9

değeriyle en yüksek amaç fonksiyonu sonucunu verir.

Step-by-Step Solution

1

Doğrusal gevşetme (LP relaxation) çözümünü bulun.

x_1 = 2,25

,

x_2 = 1,5

ve

Z = 9,75

.

Tamsayı kısıtı olmadan en iyi çözümün nerede olduğunu anlamak için kısıt doğrularının kesişim noktası hesaplanır.

2

Uygun çözüm alanı içerisindeki tamsayı noktalarını belirleyin.

Uygun noktalar: (0,0), (1,0), (2,0), (3,0), (0,1), (1,1), (2,1), (0,2), (1,2), (0,3).

Grafik üzerinde kısıtların (2x1 + x2 ≤ 6 ve 2x1 + 3x2 ≤ 9) sınırladığı bölgedeki tamsayı koordinatları taranır.

3

Aday tamsayı noktalarını amaç fonksiyonunda (

Z = 3x_1 + 2x_2

) yerine koyun.

(3, 0) için

Z = 9

; (2, 1) için

Z = 8

; (1, 2) için

Z = 7

; (0, 3) için

Z = 6

.

En büyük Z değerini veren tamsayı koordinatı optimal çözümü temsil eder.

Key Concept

Tamsayılı programlamada grafik çözüm, doğrusal gevşetme çözümünden (LP relaxation) daha küçük (maksimizasyon için) veya eşit bir amaç değeri üretir ve çözüm mutlaka uygun alan içindeki bir tamsayı noktasıdır.

Question 7Question →

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

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

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 modele göre elde edilebilecek optimal amaç fonksiyonu değeri (Z) aşağıdakilerden hangisidir?

12

12,75

11

13

10

Show answer & explanation

Answer: 12

Answer

Modelin optimal amaç fonksiyonu değeri 12'dir.

12 değeri,

(0, 3)

tamsayı noktası kullanılarak elde edilir. Bu nokta

2(0) + 3 = 3 \leq 6

ve

2(0) + 3(3) = 9 \leq 9

kısıtlarını tam olarak sağlar. Diğer uygun tamsayı noktaları (

(1, 2)

gibi) daha düşük

Z

değerleri üretmektedir.

Step-by-Step Solution

1

Doğrusal programlama gevşetmesini (LP relaxation) çözün.

x_1 = 2,25

,

x_2 = 1,5

ve

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

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

,

Z(1,2) = 11

,

Z(2,1) = 10

,

Z(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,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

x_2

katsayısı amaç fonksiyonunda daha yüksek olduğu için

x_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 8Question →

0-1 tamsayılı programlama problemlerinin çözümünde kullanılan Balas'ın Kapalı Sayımlama (Additive) algoritması, standart bir minimizasyon modelini esas alır. Bir problemin çözümü sırasında aşağıdaki kısıtın sağlanması gerekmektedir:

2x_1 + 3x_2 + 6x_3 \geq 7

Algoritmanın bir adımında $x_3 = 0$ olarak sabitlendiği bir kısmi çözüm (düğüm) incelenmektedir. Buna göre, bu düğümün algoritma tarafından 'kapalı' (fathomed) olarak işaretlenmesinin temel gerekçesi aşağıdakilerden hangisidir?

Kalan serbest değişkenlere en uygun değerler (1) verilse dahi kısıtın sağlanmasının mümkün olmaması (Uygunsuzluk).

Kısmi çözümdeki amaç fonksiyonu değerinin, mevcut en iyi tamsayılı çözümden (üst sınır) daha küçük olması.

Kısıtın mevcut değişken değerleriyle (

x_3=0, x_1=0, x_2=0

) halihazırda sağlanmış olması.

Kısmi çözümde tamsayılı olmayan bir sonucun elde edilmesi ve dallandırmanın sona ermesi.

Kısıttaki tüm katsayıların pozitif olması nedeniyle amaç fonksiyonunun sınırsız olması.

Show answer & explanation

Answer: Kalan serbest değişkenlere en uygun değerler (1) verilse dahi kısıtın sağlanmasının mümkün olmaması (Uygunsuzluk).

Answer

Düğümün kapatılma gerekçesi, kalan serbest değişkenlerin kısıtı en çok destekleyen değerleri alması durumunda bile kısıtın sağlanamamasıdır.

Balas algoritmasında bir dalın kapatılması için üç temel kriter vardır: Uygun bir çözümün bulunması, dalın mevcut en iyi çözümden daha kötü sonuç vereceğinin kanıtlanması veya dalın kısıtları sağlamasının matematiksel olarak imkansız olması. Soruda

x_3=0

olarak sabitlendiğinde, kısıtı en çok destekleyen

x_1=1

ve

x_2=1

atamaları bile sol tarafı ancak 5 yapabilmektedir. 5 değeri kısıtın gerektirdiği 7 değerinden küçük olduğu için bu dalda hiçbir uygun çözüm bulunamaz ve dal kapatılır.

Step-by-Step Solution

1

Kısmi çözümdeki değişken değerini kısıt denklemine yerleştirin.

2x_1 + 3x_2 + 6(0) \geq 7 \Rightarrow 2x_1 + 3x_2 \geq 7

Düğümün uygunluğunu test etmek için sabitlenen değerlerin etkisini görmek gerekir.

2

Kalan serbest değişkenler (

x_1, x_2

) için sol tarafın alabileceği maksimum değeri hesaplayın.

x_1=1

ve

x_2=1

için

2(1) + 3(1) = 5

0-1 programlamada bir kısıtın sağlanma şansı, katsayısı pozitif olan değişkenlere 1 verilerek kontrol edilir.

3

Elde edilen maksimum değeri kısıtın sağ tarafındaki değerle (RHS) kıyaslayın.

5 < 7

Sol tarafın alabileceği en büyük değer bile kısıtı sağlamaya yetmemektedir.

4

Algoritma kuralına göre kararı belirleyin.

Düğüm 'Uygunsuzluk' (Infeasibility) nedeniyle kapatılır (fathomed).

Bu daldan gidilerek elde edilecek hiçbir çözüm kısıtı sağlayamayacağı için dallandırma durdurulur.

Key Concept

Balas (Kapalı Sayımlama) algoritmasında uygunsuzluk testi (Fathoming by infeasibility)

Practice More

Benzer bir problemi kısıt yönünü değiştirerek (küçük eşittir) çözmeyi deneyin ve bu sefer serbest değişkenlere 0 verilerek kısıtın en iyi şekilde nasıl desteklendiğini analiz edin.

Estimated Time:1m 30s

Question 9Question →

Bir işletme $A$ ve $B$ ürünlerini üretmeyi planlamaktadır. $x_A$ ve $x_B$ sırasıyla bu ürünlerin üretim miktarlarını (sürekli değişken), $y_A$ ve $y_B$ ise bu ürünlerin üretilip üretilmeme kararını ( $1$ : üretiliyor, $0$ : üretilmiyor) temsil eden ikili (binary) değişkenlerdir.

Ürünlere ait maliyet ve kapasite bilgileri aşağıdaki tabloda verilmiştir:

Ürün	Sabit Kurulum Maliyeti (TL)	Birim Değişken Maliyet (TL)	Maksimum Kapasite (Birim)
A	$5.000$	$20$	$1.000$
B	$3.000$	$15$	$800$

İşletme politikası gereği, ** $B$ ürününün üretilebilmesi için $A$ ürününün de mutlaka üretiliyor olması** gerekmektedir.

Bu işletmenin toplam maliyetini minimize eden amaç fonksiyonu ve belirtilen kısıtları içeren karma tamsayılı programlama modeli aşağıdakilerden hangisidir?

\min Z = 5000y_A + 20x_A + 3000y_B + 15x_B

x_A \leq 1000y_A

x_B \leq 800y_B

y_B \leq y_A

\min Z = 5000y_A + 20x_A + 3000y_B + 15x_B

x_A \leq 1000y_A

x_B \leq 800y_B

y_A \leq y_B

\min Z = 5000 + 20x_A + 3000 + 15x_B

x_A \leq 1000

x_B \leq 800

y_B \leq y_A

\min Z = 5000y_A + 20x_A + 3000y_B + 15x_B

x_A \leq 1000y_A

x_B \leq 800y_B

y_A + y_B \leq 1

\min Z = 5000y_A + 20x_A + 3000y_B + 15x_B

y_A \leq 1000x_A

y_B \leq 800x_B

y_B \leq y_A

Show answer & explanation

Answer: $\min Z = 5000y_A + 20x_A + 3000y_B + 15x_B$
$x_A \leq 1000y_A$
$x_B \leq 800y_B$
$y_B \leq y_A$

Answer

Toplam maliyeti minimize eden amaç fonksiyonu ile kapasite ve bağımlılık mantığını doğru kuran model seçilmelidir.

Doğru modelde, amaç fonksiyonu hem sabit hem de değişken maliyetleri içerir. Kapasite kısıtları (

x \leq My

), üretimin yapılmadığı durumda sürekli değişkenin değerini sıfıra zorlar. Mantıksal bağımlılık kısıtı olan

y_B \leq y_A

, eğer

y_B=1

ise

y_A

'nın

0

olamayacağını (mutlaka

1

olması gerektiğini) garanti altına alır.

Step-by-Step Solution

1

Amaç fonksiyonunun oluşturulması

\min Z = 5000y_A + 20x_A + 3000y_B + 15x_B

Sabit maliyetler ancak üretim kararı (

y=1

) verildiğinde maliyete eklenmelidir.

2

Sabit maliyet (kapasite) kısıtlarının yazılması

x_A \leq 1000y_A

ve

x_B \leq 800y_B

Eğer üretim yapılmıyorsa (

y=0

), üretim miktarının (

x

) da 0 olmasını sağlar; üretim yapılıyorsa kapasite üst sınırını belirler.

3

Koşullu mantıksal kısıtın eklenmesi

y_B \leq y_A

"B için A şart" ifadesi,

y_B=1

olduğunda

y_A

'nın da

1

olmasını zorunlu kılar.

Key Concept

Sabit maliyetli problemler ve koşullu mantıksal kısıtların karma tamsayılı programlamada modellenmesi.

Practice More

Mantıksal kısıtları 'ya A ya da B' (either-or) senaryoları üzerinde çalışarak pekiştirebilirsiniz.

Estimated Time:1m 30s

Question 10Question →

Tam sayılı bir programlama probleminin doğrusal gevşetilmiş (LP relaxation) hali simpleks yöntemiyle çözülmüş ve optimal tablo şu şekilde elde edilmiştir:

Temel	$x_1$	$x_2$	$s_1$	$s_2$	Çözüm
$Z$	0	0	1	2	20
$x_1$	1	0	$-5/4$	$1/2$	$11/4$
$x_2$	0	1	$3/4$	$1/4$	$9/4$

Bu problemde tüm değişkenlerin tam sayı olması gerektiği bilindiğine göre, tablodaki $x_1$ satırı kullanılarak oluşturulacak Gomory kesme kısıtı (cut constraint) aşağıdakilerden hangisidir? ( $s_g$ yeni eklenen aylak değişkendir.)

s_g - \frac{3}{4} s_1 - \frac{1}{2} s_2 = -\frac{3}{4}

s_g + \frac{1}{4} s_1 - \frac{1}{2} s_2 = -\frac{3}{4}

s_g - \frac{3}{4} s_1 - \frac{1}{2} s_2 = \frac{3}{4}

s_g - \frac{5}{4} s_1 + \frac{1}{2} s_2 = -\frac{11}{4}

s_g - \frac{1}{4} s_1 - \frac{1}{2} s_2 = -\frac{1}{4}

Show answer & explanation

Answer: $s_g - \frac{3}{4} s_1 - \frac{1}{2} s_2 = -\frac{3}{4}$

Answer

s_g - \frac{3}{4} s_1 - \frac{1}{2} s_2 = -\frac{3}{4}

kısıtı doğrudur.

Kesme kısıtı oluşturulurken kullanılan katsayıların

[0, 1)

aralığındaki kesirli kısımları doğru şekilde tespit edilmiştir.

-\frac{5}{4}

değeri

-2 + \frac{3}{4}

şeklinde yazıldığında kesirli kısım

\frac{3}{4}

olur. Benzer şekilde

\frac{11}{4}

için

\frac{3}{4}

ve

\frac{1}{2}

için

\frac{1}{2}

değerleri kullanılarak standart formdaki denklem elde edilmiştir.

Step-by-Step Solution

1

x_1

temel değişkeninin bulunduğu satır denklemi yazılır.

x_1 - \frac{5}{4} s_1 + \frac{1}{2} s_2 = \frac{11}{4}

Kesme kısıtı oluşturulacak kaynak satırı belirlemek.

2

Katsayılar ve sağ yan değer, tam sayı (

k

) ve

0 \leq f < 1

olacak şekilde kesirli kısım (

f

) toplamı olarak ayrıştırılır.

RHS:

\frac{11}{4} = 2 + \frac{3}{4}

(

f_0 = \frac{3}{4}

);

s_1

katsayısı:

-\frac{5}{4} = -2 + \frac{3}{4}

(

f_1 = \frac{3}{4}

);

s_2

katsayısı:

\frac{1}{2} = 0 + \frac{1}{2}

(

f_2 = \frac{1}{2}

).

Gomory kesmesi için katsayıların kesirli kısımlarını elde etmek.

3

Gomory kesme eşitsizliği

\sum f_j x_j \geq f_0

formunda oluşturulur.

\frac{3}{4} s_1 + \frac{1}{2} s_2 \geq \frac{3}{4}

Temel değişkenin tamsayılık kısıtını ihlal eden bölgeyi budamak.

4

Eşitsizlik, yeni bir aylak değişken (

s_g

) eklenerek standart forma dönüştürülür.

s_g - \frac{3}{4} s_1 - \frac{1}{2} s_2 = -\frac{3}{4}

Tabloya yeni kısıtı ekleyip Dual Simpleks yöntemiyle çözüme devam etmek.

Key Concept

Gomory kesme düzlemi algoritmasında, kesirli kısımlar her zaman negatif olmayan (

0 \leq f < 1

) değerler olarak tanımlanır.

Estimated Time:2m 0s

Question 11Question →

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

Bir belediye, iki farklı tipte hizmet aracı (Süpürme Aracı - $x_1$ ve Çöp Kamyonu - $x_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:

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

Kısıtlar:

2x_1 + x_2 \leq 6

2x_1 + 3x_2 \leq 9

x_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 ( $Z$ ) kaçtır?

10

11

12

12,75

13

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)

koordinatlarıdır. Bu noktada birinci kısıt

2(0) + 3 = 3 \leq 6

ve ikinci kısıt

2(0) + 3(3) = 9 \leq 9

olarak sağlanır. Amaç fonksiyonu değeri ise

3(0) + 4(3) = 12

olur. Diğer tüm tamsayılı uygun noktalar (

1,2

veya

2,1

gibi) daha düşük

Z

değerleri üretmektedir.

Step-by-Step Solution

1

Gevşetilmiş Doğrusal Programlama (LP) çözümünü belirlemek.

x_1 = 2,25

ve

x_2 = 1,5

için

Z = 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ı (

x_1, x_2

) test etmek.

(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)=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 13Question →

Bir tam sayılı programlama probleminin doğrusal gevşetilmesi (LP relaxation) sonucunda elde edilen optimal simpleks tablosunda $x_1$ temel değişkenine ait satır bilgisi aşağıda verilmiştir:

Temel Değişken	$x_1$	$x_2$	$s_1$	$s_2$	Çözüm ( $b$ )
$x_1$	1	0	$3/2$	$-2/3$	$5/2$

Problemdeki tüm değişkenlerin tam sayı olması gerektiği bilindiğine göre, $x_1$ satırı kullanılarak oluşturulacak olan Gomory kesme düzlemi kısıtı aşağıdakilerden hangisidir?
( $s_g$ : Kesme düzlemi için eklenen yeni aylak değişken)

s_g - \frac{1}{2} s_1 - \frac{1}{3} s_2 = -\frac{1}{2}

s_g - \frac{1}{2} s_1 + \frac{2}{3} s_2 = -\frac{1}{2}

s_g - \frac{1}{2} s_1 - \frac{1}{3} s_2 = \frac{1}{2}

s_g - \frac{3}{2} s_1 + \frac{2}{3} s_2 = -\frac{5}{2}

s_g + \frac{1}{2} s_1 + \frac{1}{3} s_2 = -\frac{1}{2}

Show answer & explanation

Answer: $s_g - \frac{1}{2} s_1 - \frac{1}{3} s_2 = -\frac{1}{2}$

Answer

Gomory kesme düzlemi kısıtı

s_g - \frac{1}{2} s_1 - \frac{1}{3} s_2 = -\frac{1}{2}

şeklindedir.

Doğru cevapta,

s_1

katsayısının kesirsel kısmı

1/2

,

s_2

katsayısının kesirsel kısmı (

-2/3

için)

1/3

ve çözüm değerinin kesirsel kısmı

1/2

olarak doğru belirlenmiş ve standart kısıt formunda (

s_g - \sum f_j s_j = -f_i

) yerine yazılmıştır.

Step-by-Step Solution

1

x_1

satırı denklemini yazınız.

x_1 + \frac{3}{2}s_1 - \frac{2}{3}s_2 = \frac{5}{2}

Kesme düzlemi oluşturmak için temel değişkenin bulunduğu satır denklemi temel alınır.

2

Katsayıları tam sayı ve pozitif kesirsel kısımlara (

0 \leq f < 1

) ayırınız.

s_1

için:

\frac{3}{2} = 1 + \frac{1}{2}

;

s_2

için:

-\frac{2}{3} = -1 + \frac{1}{3}

; Çözüm için:

\frac{5}{2} = 2 + \frac{1}{2}

Gomory yönteminde her katsayı

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

şeklinde ayrıştırılır.

3

Kesirsel kısımları kullanarak kısıt denklemini oluşturunuz.

\frac{1}{2}s_1 + \frac{1}{3}s_2 \geq \frac{1}{2}

Kesme düzlemi genel formu

\sum f_{ij}s_j \geq f_i

şeklindedir.

4

Kısıtı simpleks tablosuna uygun standart forma dönüştürünüz.

s_g - \frac{1}{2} s_1 - \frac{1}{3} s_2 = -\frac{1}{2}

Aylak değişken (

s_g

) eklenerek denklemin sağ tarafı negatif yapılarak dual simpleks adımına hazırlanır.

Key Concept

Gomory Kesme Düzlemi Algoritması'nda negatif katsayıların kesirsel kısımları hesaplanırken katsayıdan küçük en büyük tam sayı (taban değer) çıkarılır.

Question 14Question →

Bir belediye, gelecek yıl için planladığı 5 farklı altyapı projesi ( $x_1, x_2, x_3, x_4, x_5$ ) arasından seçim yapacaktır. Karar değişkenleri, ilgili proje seçilirse 1, seçilmezse 0 değerini almaktadır. Belediye yönetimi projelerle ilgili şu kısıtlamaları belirlemiştir:

* $x_1$ ve $x_2$ projelerinden tam olarak biri seçilmelidir.
* $x_3$ projesi seçilirse, $x_4$ projesi de mutlaka seçilmelidir.
* $x_3, x_4$ ve $x_5$ projeleri arasından en fazla iki proje seçilebilir.

Buna göre, bu mantıksal koşulları ifade eden kısıtlar kümesi aşağıdakilerden hangisidir?

x_1 + x_2 = 1; \quad x_3 \leq x_4; \quad x_3 + x_4 + x_5 \leq 2

x_1 + x_2 \leq 1; \quad x_3 \leq x_4; \quad x_3 + x_4 + x_5 \leq 2

x_1 + x_2 = 1; \quad x_3 \geq x_4; \quad x_3 + x_4 + x_5 \leq 2

x_1 + x_2 = 1; \quad x_3 \leq x_4; \quad x_3 + x_4 + x_5 \geq 2

x_1 + x_2 = 1; \quad x_3 + x_4 = 1; \quad x_3 + x_4 + x_5 \leq 2

Show answer & explanation

Answer: $x_1 + x_2 = 1; \quad x_3 \leq x_4; \quad x_3 + x_4 + x_5 \leq 2$

Answer

Doğru modelleme

x_1 + x_2 = 1, x_3 \leq x_4

ve

x_3 + x_4 + x_5 \leq 2

şeklindedir.

Doğru cevap olan kısıtlar kümesi, problemin tüm mantıksal önermelerini karşılamaktadır. 'Tam olarak biri' ifadesi için eşittir (= 1), 'Eğer 3 ise 4' bağımlılığı için

x_3 \leq x_4

ve 'En fazla iki' sınırı için küçük-eşittir (\leq 2) operatörleri kullanılmıştır.

Step-by-Step Solution

1

Karşılıklı dışlayan ve zorunlu seçim (Tam olarak biri) kısıtını belirleme

x_1 + x_2 = 1

İki projeden sadece birinin seçilmesi gerektiğinde toplamları 1'e eşitlenir.

2

Koşullu seçim (Eğer-ise) kısıtını modelleme

x_3 \leq x_4

x_3

seçildiğinde (

x_3=1

),

x_4

değişkeninin 1 olmasını zorunlu kılar (

1 \leq x_4

).

x_3

seçilmezse (

x_3=0

),

x_4

serbest kalır (0 veya 1).

3

n proje arasından en fazla k tanesinin seçimi kısıtını yazma

x_3 + x_4 + x_5 \leq 2

Seçilen projelerin toplamı, üst sınır olan k değerinden (2) küçük veya eşit olmalıdır.

Key Concept

Sıfır-Bir (0-1) Tamsayılı Programlamada Mantıksal Kısıtların Modellenmesi

Hints

1

'Tam olarak biri' kısıtı, değişkenlerin toplamının 1 olması gerektiğini hatırlatır.

2

Eğer

x_A \rightarrow x_B

koşulu varsa,

x_A

seçildiğinde

x_B

de 1 olmaya zorlanmalıdır. Bu

x_A \leq x_B

ile sağlanır.

Practice More

Karşılıklı bağımlı projeler için

x_A = x_B

kısıtının nasıl kullanıldığını inceleyebilirsiniz.

Estimated Time:1m 30s

Question 15Question →

Bir kamu kurumu, siber güvenlik altyapısını güçlendirmek amacıyla 5 farklı güvenlik modülü ( $x_1, x_2, x_3, x_4, x_5$ ) arasından seçim yapacaktır. Karar değişkenleri, ilgili modül seçilirse 1, seçilmezse 0 değerini almaktadır. Kurumun projeye yönelik belirlediği kısıtlar şunlardır:

- 1 numaralı modül seçilirse, 2 numaralı modülün de mutlaka seçilmesi gerekmektedir.
- İlk dört modül arasından en fazla 3 tanesi seçilebilmektedir.
- 3 ve 5 numaralı modüllerden tam olarak birinin seçilmesi zorunludur.

Bu şartları sağlayan tamsayılı programlama kısıt kümesi aşağıdakilerden hangisidir?

x_1 \leq x_2; \quad x_1 + x_2 + x_3 + x_4 \leq 3; \quad x_3 + x_5 = 1

x_1 \geq x_2; \quad x_1 + x_2 + x_3 + x_4 \leq 3; \quad x_3 + x_5 = 1

x_1 \leq x_2; \quad x_1 + x_2 + x_3 + x_4 \geq 3; \quad x_3 + x_5 = 1

x_1 \leq x_2; \quad x_1 + x_2 + x_3 + x_4 \leq 3; \quad x_3 + x_5 \leq 1

x_2 \leq x_1; \quad x_1 + x_2 + x_3 + x_4 = 3; \quad x_3 + x_5 \geq 1

Show answer & explanation

Answer: $x_1 \leq x_2; \quad x_1 + x_2 + x_3 + x_4 \leq 3; \quad x_3 + x_5 = 1$

Answer

x_1 \leq x_2

,

x_1 + x_2 + x_3 + x_4 \leq 3

ve

x_3 + x_5 = 1

ifadelerini içeren kısıt kümesi doğrudur.

Doğru cevap, problemin tüm mantıksal şartlarını karşılayan kısıt kümesidir. '1 ise 2' şartı

x_1 \leq x_2

ile sağlanır (eğer

x_1=1

ise

x_2

en az 1 olmalıdır, yani 1 olur). 'En fazla 3' şartı toplamın

\leq 3

olmasıyla, 'tam olarak bir' şartı ise toplamın 1'e eşitlenmesiyle ifade edilir.

Step-by-Step Solution

1

Koşullu önermeyi modelle

x_1 \leq x_2

'1 seçilirse 2 de seçilmeli' ifadesi,

x_1=1

olduğunda

x_2

'nin 0 olamayacağını garanti etmelidir.

2

Kapasite/sayı kısıtını modelle

x_1 + x_2 + x_3 + x_4 \leq 3

'En fazla' kısıtı, ilgili değişkenlerin toplamının belirlenen sayıdan küçük veya eşit olması gerektiğini ifade eder.

3

Tamamlayıcı/seçim kısıtını modelle

x_3 + x_5 = 1

'Tam olarak birinin seçilmesi' durumu, iki değişkenden birinin 1, diğerinin 0 olmasını gerektiren bir eşitlik kısıtıdır.

Key Concept

0-1 Tamsayılı Programlamada Mantıksal Kısıtlar

Estimated Time:1m 30s

Question 16Question →

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

Maksimum \quad Z = 8x_1 + 5x_2

Kısıtlar:

x_1 + x_2 \leq 4,5

2x_1 + x_2 \leq 6

x_1, x_2 \geq 0 \text{ ve tam sayı}

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

23

26

27

31

24

Show answer & explanation

Answer: 26

Answer

Modelin tam sayılı en iyi çözüm değeri 26 olarak bulunur.

Modelin doğrusal gevşetme optimumu

(1,5; 3)

olup

Z=27

değerini verir. Ancak değişkenlerin tam sayı olması istendiğinden, uygun bölge içerisindeki tam sayı koordinatları incelenir.

(2, 2)

noktası her iki kısıtı da sağlar (

2+2 \leq 4,5

ve

2(2)+2 \leq 6

) ve

8(2)+5(2)=26

değeriyle bölgedeki en yüksek tam sayılı amaç fonksiyonu değerini sunar.

Step-by-Step Solution

1

Doğrusal gevşetme (LP relaxation) çözümünün bulunması.

x_1 = 1,5

ve

x_2 = 3

noktasında

Z = 27

.

Tam sayı kısıtı olmadan kısıt doğrularının kesişim noktası belirlenir.

2

Uygun çözüm bölgesi içerisindeki tam sayılı noktaların test edilmesi.

Uygun noktalar:

(0,0), (1,0), (2,0), (3,0), (0,1), (1,1), (2,1), (0,2), (1,2), (2,2), (0,3), (1,3), (0,4)

.

Grafik yöntemiyle belirlenen bölge sınırları içindeki tüm tam sayı koordinatları aday çözümlerdir.

3

Aday noktalarda amaç fonksiyonu değerlerinin hesaplanması.

Z(3,0) = 24

,

Z(1,3) = 23

,

Z(2,2) = 26

,

Z(0,4) = 20

.

En yüksek

Z

değerini veren nokta optimum tam sayılı çözümdür.

Key Concept

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

Estimated Time:1m 30s

Question 17Question →

0-1 tamsayılı programlama problemlerinin çözümünde kullanılan Balas'ın Kapalı Sayımlama (Additive) algoritmasıyla ilgili olarak, bir düğümün (kısmi çözümün) 'budanması' veya 'kapatılması' süreci hakkında aşağıda verilen ifadelerden hangisi yanlıştır?

Kısmi çözümde yer alan tüm serbest değişkenlere 0 değeri atandığında kısıtların tamamı sağlanıyorsa, bu dal üzerinden daha iyi bir sonuç elde edilemeyeceği için budama yapılır.

Serbest değişkenlerin kısıtları sağlamaya en yardımcı olacak değerleri (genellikle 1) atanmasına rağmen en az bir kısıt hala ihlal ediliyorsa, bu daldan uygun çözüm gelmeyeceği için kapatılır.

Mevcut kısmi çözümün amaç fonksiyonu değeri, halihazırda elde edilmiş olan en iyi uygun çözümün değerinden (

Z^*

) büyük veya ona eşitse dal budanır.

Algoritmanın 'toplanabilirlik' özelliğini koruması için amaç fonksiyonu katsayılarının negatif olması ve problemin her zaman maksimizasyon tipinde olması gerekir.

Budama işlemi; bir düğümden elde edilebilecek potansiyel en iyi çözümün, mevcut en iyi çözümden daha iyi olamayacağının kesinleştiği durumlarda uygulanır.

Show answer & explanation

Answer: Algoritmanın 'toplanabilirlik' özelliğini koruması için amaç fonksiyonu katsayılarının negatif olması ve problemin her zaman maksimizasyon tipinde olması gerekir.

Answer

Balas algoritması standart olarak minimizasyon problemlerine uygulanır ve amaç fonksiyonu katsayılarının negatif olmaması (sıfırdan büyük veya eşit olması) şartı aranır.

Balas'ın Kapalı Sayımlama (Additive) algoritması, 0-1 tamsayılı programlama problemlerini çözmek için tasarlanmış bir algoritmadır. Bu algoritmanın en temel gereksinimi, problemin minimizasyon formunda olması ve amaç fonksiyonundaki tüm katsayıların (c_j) negatif olmaması (

c_j \geq 0

) şartıdır. Bu şart sağlandığında, bir değişkenin çözüme 1 olarak dahil edilmesi amaç fonksiyonu değerini asla azaltmaz (sadece artırır veya sabit bırakır), bu da 'toplanabilirlik' özelliğini ve etkili budama yapılmasını sağlar. Dolayısıyla katsayıların negatif olması gerektiği yönündeki ifade yanlıştır.

Step-by-Step Solution

1

Algoritmanın standart formunu analiz et.

Balas algoritması

\min Z = \sum c_j x_j

formundaki modeller için geliştirilmiştir.

Toplanabilirlik (additive) özelliği,

c_j \geq 0

olduğunda değişkenlerin çözüme dahil edilmesinin amaç fonksiyonu değerini azaltmayacağını garanti eder.

2

Budama (fathoming) kriterlerini gözden geçir.

Düğüm şu 3 durumda kapatılır: 1. Uygun bir çözümün bulunması (tüm serbest değişkenler 0 iken kısıtların sağlanması), 2. Uygunsuzluğun saptanması (fizibilite testi), 3. Mevcut en iyi çözümden daha iyi sonuç alınamayacağının anlaşılması (sınır testi).

Bu kriterler arama ağacında gereksiz dalların incelenmesini engeller.

3

Yanlış olan seçeneği belirle.

Amaç fonksiyonu katsayılarının negatif olması gerektiği ve problemin maksimizasyon olması gerektiği ifadesi algoritmanın temel varsayımıyla çelişir.

Negatif katsayılar varsa

x_j = 1 - y_j

dönüşümü yapılarak katsayılar pozitif hale getirilmelidir.

Key Concept

Balas algoritmasında standart form (minimizasyon ve pozitif katsayılar) budama (fathoming) mantığının temelini oluşturur.

Question 18Question →

0-1 tamsayılı programlama problemlerinin çözümünde kullanılan Balas’ın Kapalı Sayımlama (Additive) algoritmasında, bir minimizasyon modeli için belirli bir çözüm aşamasında aşağıdaki kısıt ve kısmi çözüm elde edilmiştir:

Kısmi Çözüm: $x_1 = 1$ , $x_4 = 0$ ( $x_2$ ve $x_3$ değişkenleri serbesttir).
Kısıt: $2x_1 + 4x_2 + x_3 + 5x_4 \geq 8$

Buna göre, bu düğümün (kısmi çözümün) algoritmadaki durumu ile ilgili aşağıdakilerden hangisi söylenebilir?

Serbest değişkenlere atanabilecek en iyi değerlerle dahi kısıt sağlanamayacağı için bu düğüm uygunsuzluk nedeniyle budanır.

Kısmi çözümdeki mevcut değerler kısıtı sağladığı için bir uygun çözüm bulunmuştur ve dal kapatılır.

Kısıt henüz sağlanmamıştır ancak serbest değişkenlerden birine 1 değeri verilerek kısıt sağlanabileceği için dallandırmaya devam edilir.

Amaç fonksiyonu katsayıları pozitif olduğu sürece bu kısıtın sağlanıp sağlanmadığına bakılmaksızın dallandırma yapılır.

Serbest değişken sayısı kısıt katsayılarından az olduğu için bu dalda çözüm aranamaz ve algoritma durur.

Show answer & explanation

Answer: Serbest değişkenlere atanabilecek en iyi değerlerle dahi kısıt sağlanamayacağı için bu düğüm uygunsuzluk nedeniyle budanır.

Answer

Serbest değişkenlerin alabileceği en büyük değerler (

x_2=1, x_3=1

) dikkate alındığında bile kısıtın sağlanması mümkün olmadığından, bu düğüm uygunsuzluk (infeasibility) nedeniyle budanır.

Kısmi çözümdeki

x_1=1

ve

x_4=0

değerleri kısıtta yerine yazıldığında, kısıtın sol tarafı

2

değerini alır. Kısıtın sağlanması için serbest olan

x_2

ve

x_3

değişkenlerinin toplamda en az

6

birimlik bir katkı yapması gerekir. Ancak bu değişkenler

0

veya

1

değerini alabildiğinden, yapabilecekleri maksimum katkı

4(1) + 1(1) = 5

birimdir.

5 < 6

olduğu için bu dal üzerinden hiçbir şekilde uygun bir çözüme ulaşılamaz ve düğüm budanır.

Step-by-Step Solution

1

Kısmi çözümdeki sabit değerleri kısıt denkleminde yerine koyun.

2(1) + 4x_2 + x_3 + 5(0) \geq 8 \Rightarrow 2 + 4x_2 + x_3 \geq 8

Mevcut çözümün kısıt üzerindeki etkisini belirlemek için.

2

Kısıtın sağlanması için serbest değişkenlerden beklenen minimum katkıyı hesaplayın.

4x_2 + x_3 \geq 8 - 2 \Rightarrow 4x_2 + x_3 \geq 6

Serbest değişkenlerin karşılaması gereken farkı bulmak için.

3

Serbest değişkenlerin (

x_2, x_3 \in \{0, 1\}

) kısıtın sol tarafına yapabileceği maksimum katkıyı belirleyin.

Maksimum katkı:

4(1) + 1(1) = 5

En iyimser durumda kısıtın sağlanıp sağlanamayacağını test etmek için.

4

Maksimum katkı ile gereken farkı karşılaştırın.

5 < 6

olduğu için kısıt asla sağlanamaz.

Balas algoritması budama kriterini (uygunsuzluk) uygulamak için.

Key Concept

Balas (Kapalı Sayımlama) Algoritmasında Uygunsuzluk Testi

Hints

1

Önce bilinen

x_1

ve

x_4

değerlerini kısıt eşitsizliğinde yerine yazarak sadeleştirme yapın.

2

Sadeleşmiş kısıtın (

4x_2 + x_3 \geq 6

) sağlanması için

x_2

ve

x_3

değişkenlerine 0 veya 1 değerlerinden hangilerini vermeniz gerektiğini düşünün.

3

Eğer serbest değişkenlere en büyük değerlerini (1) verdiğinizde bile kısıt sağlanmıyorsa, bu dalda uygun çözüm aramanın bir anlamı kalmaz.

Practice More

Balas algoritmasında 'uygunluk' (feasibility) nedeniyle budama yapılabilmesi için kısmi çözümdeki değişkenlerin kısıtları sağlaması ve geri kalan serbest değişkenlerin amaç fonksiyonuna katkısının 0 olması (minimizasyon için) gerektiğini hatırlayınız.

Estimated Time:1m 30s

Question 19Question →

Tam sayılı bir doğrusal programlama probleminin doğrusal gevşetilmesi (LP relaxation) çözüldüğünde elde edilen optimal simpleks tablosu aşağıda verilmiştir:

Temel Değişkenler	$x_1$	$x_2$	$s_1$	$s_2$	Sağ Taraf
$Z$	0	0	1.2	2.5	25.8
$x_1$	1	0	2/3	-1/4	10/3
$x_2$	0	1	-1/3	1/2	7/3

Problemdeki tüm karar değişkenlerinin ( $x_1, x_2$ ) tam sayı olması gerektiği bilinmektedir. Buna göre, $x_1$ değişkeninin tamsayılılık kısıtını sağlamak amacıyla Gomory kesme düzlemi algoritması kullanılarak oluşturulacak kesme kısıtı (cut constraint) aşağıdakilerden hangisidir? (Yeni eklenen aylak değişken $s_g$ ile gösterilmiştir.)

s_g - \frac{2}{3} s_1 - \frac{3}{4} s_2 = -\frac{1}{3}

s_g - \frac{2}{3} s_1 + \frac{1}{4} s_2 = -\frac{1}{3}

s_g - \frac{2}{3} s_1 - \frac{3}{4} s_2 = -\frac{10}{3}

s_g + \frac{1}{3} s_1 - \frac{1}{2} s_2 = -\frac{1}{3}

s_g + \frac{2}{3} s_1 + \frac{3}{4} s_2 = \frac{1}{3}

Show answer & explanation

Answer: $s_g - \frac{2}{3} s_1 - \frac{3}{4} s_2 = -\frac{1}{3}$

Answer

Doğru kısıt

s_g - \frac{2}{3} s_1 - \frac{3}{4} s_2 = -\frac{1}{3}

ifadesidir.

Doğru yanıt olan ifadede,

x_1

satırındaki katsayıların kesirsel kısımları hatasız hesaplanmıştır. Özellikle

s_2

değişkeninin katsayısı olan

-1/4

, en yakın küçük tam sayı olan

-1

'den çıkarılarak

3/4

kesir değeri elde edilmiştir. Sağ taraf değerinin kesirsel kısmı olan

1/3

ise kısıtın sağ tarafına negatif işaretle aktarılarak standart form oluşturulmuştur.

Step-by-Step Solution

1

x_1

temel değişkeninin bulunduğu satırı denklem olarak yazın.

x_1 + \frac{2}{3} s_1 - \frac{1}{4} s_2 = \frac{10}{3}

Gomory kısıtı, tamsayı olması gereken ancak kesirli değer alan bir temel değişkenin satırından türetilir.

2

Katsayıları ve sağ taraf değerini tam sayı ve kesirsel kısımlara ayırın (

f = a - \lfloor a \rfloor

).

x_1

için

1 = 1 + 0

(

f=0

);

s_1

için

\frac{2}{3} = 0 + \frac{2}{3}

(

f=\frac{2}{3}

);

s_2

için

-\frac{1}{4} = -1 + \frac{3}{4}

(

f=\frac{3}{4}

); Sağ taraf için

\frac{10}{3} = 3 + \frac{1}{3}

(

f=\frac{1}{3}

)

Gomory algoritmasında kesirsel kısım her zaman negatif olmayan (

0 \leq f < 1

) bir değer olmalıdır. Bu yüzden

-\frac{1}{4}

için

\lfloor -0.25 \rfloor = -1

alınarak kesir

\frac{3}{4}

bulunur.

3

Standart Gomory kesme kısıtı formülünü uygulayın (

s_g - \sum f_{ij} x_j = -f_{i0}

).

s_g - \frac{2}{3} s_1 - \frac{3}{4} s_2 = -\frac{1}{3}

Bu kısıt, mevcut optimal çözümün tamsayılı olmayan kısımlarını dışarıda bırakırken tüm uygun tamsayılı çözümleri korur.

Key Concept

Gomory Kesme Düzlemi Algoritması'nda kesirsel kısımların (

a - \lfloor a \rfloor

) belirlenmesi ve standart formda kısıt yazımı.

Hints

1

Gomory kısıtı oluştururken ilgili satırı denklem haline getirin ve katsayıların ondalık/kesir kısımlarına odaklanın.

2

Negatif katsayılara dikkat edin: Bir sayının kesirsel kısmı

f = a - \lfloor a \rfloor

formülüyle bulunur. Örneğin

\lfloor -0.25 \rfloor = -1

olduğundan kesir

0.75

olur.

Practice More

Bu kısıt eklendikten sonra tablonun dual simpleks yöntemi ile çözülmesi gerektiğini hatırlayın.

Estimated Time:1m 30s

Question 20Question →

$0-1$ tamsayılı programlama problemlerinin çözümünde kullanılan Balas’ın Kapalı Sayımlama (Additive) algoritmasında, standart bir minimizasyon problemi ele alınmaktadır. Algoritmanın belirli bir adımında, bir kısmi çözümün (düğümün) dallandırılması incelenirken; mevcut serbest değişkenlerin tamamı kısıtları sağlamaya en fazla katkıda bulunacak şekilde ( $0$ veya $1$ ) değerlendirilse dahi kısıtlardan en az birinin sağlanamadığı tespit edilmiştir. Bu durum ortaya çıktığında algoritmanın işleyişine göre aşağıdakilerden hangisi uygulanmalıdır?

İlgili dalda uygun bir çözüm bulunması mümkün olmadığı için düğüm kapatılır (budanır) ve geri dönülür.

Serbest değişkenler arasından yeni bir dallandırma değişkeni seçilerek alt düğümlere geçilir.

Mevcut kısmi çözüm, o ana kadarki en iyi çözüm (üst sınır) olarak kaydedilir.

Kısıtın yönü tersine çevrilerek algoritma bir sonraki iterasyona aktarılır.

Algoritma tamamen sonlandırılır ve problemin uygun bir çözümü olmadığına karar verilir.

Show answer & explanation

Answer: İlgili dalda uygun bir çözüm bulunması mümkün olmadığı için düğüm kapatılır (budanır) ve geri dönülür.

Answer

İlgili dalda uygun bir çözüm bulunması mümkün olmadığı için düğüm kapatılır (budanır) ve geri dönülür.

Doğru cevap, Balas algoritmasındaki 'uygunsuzluk nedeniyle kapatma' kriterini ifade etmektedir. Algoritmanın minimizasyon standart formunda, kısıtlar

\geq

şeklindedir. Eğer eldeki serbest değişkenlerin kısıtı sağlamaya yönelik en büyük katkısı bile (pozitif katsayılar için değişkeni

1

, negatifler için

0

yaparak) mevcut yetersizliği gideremiyorsa, o daldan devam etmenin bir anlamı kalmaz ve dal budanır.

Step-by-Step Solution

1

Kısmi çözümdeki serbest değişkenlerin kısıtlar üzerindeki etkisi analiz edilir.

Serbest değişkenlerin kısıtı sağlamaya en çok yardım eden değerleri belirlenir.

Düğümün kapatılıp kapatılmayacağına karar vermek için 'en iyi durum' testi yapılmalıdır.

2

Kısıtın sağlanabilirliği (feasibility check) kontrol edilir.

En iyi durumda bile kısıt ihlalinin devam ettiği görülür.

Eğer en iyi olasılıkta bile kısıt sağlanamıyorsa, o daldan uygun çözüm çıkma şansı sıfırdır.

3

Kapalı sayımlama mantığı gereği 'budama' işlemi uygulanır.

Düğüm 'uygunsuzluk' nedeniyle kapatılır.

Algoritmanın gereksiz dalları eleyerek hızlanması sağlanır.

Key Concept

Balas algoritmasında uygunsuzluk (infeasibility) nedeniyle budama kriteri.

Practice More

Balas algoritmasında 'üst sınır (Z*) yardımıyla budama' kriterini de incelemek, konunun tam anlaşılmasını sağlar.

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

Practice More

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Hints

Practice More

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

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Hints

Practice More

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

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

Hints

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