Tamsayılı Programlama Alıştırma Soruları — KPSS İstatistik

Soru 1Soru →

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

Cevabı ve açıklamayı göster

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

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

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

Tahmini Süre:1m 30s

Soru 2Soru →

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}

Cevabı ve açıklamayı göster

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

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

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.

Daha Fazla Pratik

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

Tahmini Süre:2m 0s

Soru 3Soru →

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

Cevabı ve açıklamayı göster

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

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

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

İpuçları

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.

Daha Fazla Pratik

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.

Alternatif Yöntem

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.

Tahmini Süre:1m 30s

Soru 4Soru →

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}

Cevabı ve açıklamayı göster

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

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

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

).

Soru 5Soru →

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.

Cevabı ve açıklamayı göster

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

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

Balas Algoritmasında Budama (Fathoming) Kriterleri

Soru 6Soru →

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

Cevabı ve açıklamayı göster

Cevap: 9

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

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.

Soru 7Soru →

İ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

Cevabı ve açıklamayı göster

Cevap: 12

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

Saf Tamsayılı Programlama

İpuçları

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.

Daha Fazla Pratik

Eğer değişkenlerden biri tamsayı diğeri reel sayı olsaydı çözüm nasıl değişirdi?

Tahmini Süre:1m 30s

Soru 8Soru →

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

Cevabı ve açıklamayı göster

Cevap: 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).

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

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

Daha Fazla Pratik

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.

Tahmini Süre:1m 30s

Soru 9Soru →

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

Cevabı ve açıklamayı göster

Cevap: $\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$

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

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

Daha Fazla Pratik

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

Tahmini Süre:1m 30s

Soru 10Soru →

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}

Cevabı ve açıklamayı göster

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

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

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

0 \leq f < 1

) değerler olarak tanımlanır.

Tahmini Süre:2m 0s

Soru 11Soru →

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

Cevabı ve açıklamayı göster

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

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

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

Daha Fazla Pratik

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

Tahmini Süre:1m 30s

Soru 12Soru →

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

Cevabı ve açıklamayı göster

Cevap: 12

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

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.

Soru 13Soru →

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}

Cevabı ve açıklamayı göster

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

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

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.

Soru 14Soru →

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

Cevabı ve açıklamayı göster

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

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

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

İpuçları

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.

Daha Fazla Pratik

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

x_A = x_B

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

Tahmini Süre:1m 30s

Soru 15Soru →

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

Cevabı ve açıklamayı göster

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

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

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

Tahmini Süre:1m 30s

Soru 16Soru →

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

Cevabı ve açıklamayı göster

Cevap: 26

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

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.

Tahmini Süre:1m 30s

Soru 17Soru →

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.

Cevabı ve açıklamayı göster

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

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

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

Soru 18Soru →

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.

Cevabı ve açıklamayı göster

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

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

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

İpuçları

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.

Daha Fazla Pratik

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.

Tahmini Süre:1m 30s

Soru 19Soru →

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}

Cevabı ve açıklamayı göster

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

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

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

a - \lfloor a \rfloor

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

İpuçları

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.

Daha Fazla Pratik

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

Tahmini Süre:1m 30s

Soru 20Soru →

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

Cevabı ve açıklamayı göster

Cevap: İ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.

Cevap

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

Adım Adım Çözüm

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.

Anahtar Kavram

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

Daha Fazla Pratik

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

Tahmini Süre:1m 30s

Tamsayılı Programlama

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Daha Fazla Pratik

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

İpuçları

Daha Fazla Pratik

Alternatif Yöntem

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

İpuçları

Daha Fazla Pratik

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Daha Fazla Pratik

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Daha Fazla Pratik

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Daha Fazla Pratik

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

İpuçları

Daha Fazla Pratik

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar