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

Soru 21Soru →

Saf tam sayılı bir doğrusal programlama probleminin doğrusal gevşetilmesi (LP relaxation) simpleks yöntemiyle çözülmüş ve optimal simpleks tablosu aşağıda verilmiştir:

Temel Değişkenler	$x_1$	$x_2$	$s_1$	$s_2$	Sağ Yan ( $b$ )
$Z$	0	0	$1/5$	$2/5$	$22/5$
$x_1$	1	0	$4/5$	$-2/5$	$14/5$
$x_2$	0	1	$-1/5$	$3/5$	$9/5$

Tüm karar değişkenlerinin tam sayı olması gerektiği bilindiğine göre, $x_1$ temel değişkeninin bulunduğu satır kullanılarak oluşturulacak olan Gomory kesme düzlemi kısıtı aşağıdakilerden hangisidir?

s_g - \frac{4}{5} s_1 - \frac{3}{5} s_2 = -\frac{4}{5}

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

s_g - \frac{4}{5} s_1 - \frac{3}{5} s_2 = \frac{4}{5}

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

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

Cevabı ve açıklamayı göster

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

Cevap

Gomory kesme düzlemi kısıtı

s_g - \frac{4}{5} s_1 - \frac{3}{5} s_2 = -\frac{4}{5}

şeklinde ifade edilir.

Doğru cevap olan ifade,

x_1

satırındaki katsayıların doğru ayrıştırılmasıyla elde edilir.

\frac{4}{5}

katsayısı için

f = 4/5

,

-\frac{2}{5}

katsayısı için

f = 3/5

ve sağ yan sabit

\frac{14}{5}

için

f = 4/5

değerleri bulunur. Bu değerler

\sum f_{j} s_{j} \geq f_{b}

kalıbına yerleştirilip

s_g

eklendiğinde beklenen kısıt denklemi oluşur.

Adım Adım Çözüm

1

x_1

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

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

Kesme düzlemi oluşturmak için tam sayı olmayan bir temel değişkenin satırı seçilmelidir.

2

Katsayılar ve sağ yan sabit, tam sayı (

I

) ve negatif olmayan kesirsel (

f

) kısımlarına (

0 \leq f < 1

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

x_1 + (0 + \frac{4}{5}) s_1 + (-1 + \frac{3}{5}) s_2 = 2 + \frac{4}{5}

-\frac{2}{5}

değeri

-1 + \frac{3}{5}

olarak yazılmalıdır çünkü kesirsel kısım negatif olamaz.

3

Kesirsel kısımlar kullanılarak

\sum f_{ij} x_j \geq f_i

eşitsizliği oluşturulur ve standart formuna dönüştürülür.

\frac{4}{5} s_1 + \frac{3}{5} s_2 \geq \frac{4}{5} \Rightarrow s_g - \frac{4}{5} s_1 - \frac{3}{5} s_2 = -\frac{4}{5}

Yeni kısıt, mevcut çözümü dışarıda bırakacak ancak tam sayılı çözümleri koruyacak şekilde eklenir.

Anahtar Kavram

Gomory kesme düzlemi algoritmasında, negatif katsayıların kesirsel kısımları

f = k - \lfloor k \rfloor

formülüyle hesaplanır ve her zaman

0 \leq f < 1

aralığında olmalıdır.

İpuçları

1

x_1

satırındaki her bir katsayıyı tam sayı ve pozitif bir kesir toplamı olarak yazmayı deneyin.

2

Negatif katsayıları ayrıştırırken dikkatli olun; örneğin

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

şeklindedir.

Daha Fazla Pratik

Elde edilen bu kısıt eklendikten sonra bir sonraki adımın neden Dual Simpleks yöntemi olduğunu araştırınız.

Tahmini Süre:2m 0s

Soru 22Soru →

Saf tam sayılı bir doğrusal programlama probleminin doğrusal gevşetilmesi (LP relaxation) simpleks yöntemi ile çözülmüş ve elde edilen optimal simpleks tablosuna ait bir satır aşağıda verilmiştir:

Temel Değişken	$x_1$	$x_2$	$s_1$	$s_2$	Sağ Taraf
$x_1$	1	0	$4/3$	$-1/6$	$17/6$

Buna göre, Gomory kesme düzlemi algoritması kullanılarak tam sayı çözümüne ulaşmak amacıyla modele eklenmesi gereken yeni kısıt denklemi aşağıdakilerden hangisidir?

s_g - \frac{1}{3}s_1 - \frac{5}{6}s_2 = -\frac{5}{6}

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

s_g - \frac{1}{3}s_1 - \frac{5}{6}s_2 = -\frac{1}{6}

s_g + \frac{1}{3}s_1 + \frac{5}{6}s_2 = \frac{5}{6}

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

Cevabı ve açıklamayı göster

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

Cevap

s_g - \frac{1}{3}s_1 - \frac{5}{6}s_2 = -\frac{5}{6}

denklemi doğrudur.

Verilen

x_1

satır denkleminde sağ taraf değerinin (

17/6

) kesirsel kısmı

5/6

,

s_1

katsayısının (

4/3

) kesirsel kısmı

1/3

ve

s_2

katsayısının (

-1/6

) kesirsel kısmı

5/6

olarak hesaplanır. Gomory kısıt denklemi standart olarak

s_g - \sum f_j x_j = -f_0

şeklinde yazıldığından,

s_g - \frac{1}{3}s_1 - \frac{5}{6}s_2 = -\frac{5}{6}

ifadesi doğru sonuca ulaştırır.

Adım Adım Çözüm

1

Seçilen satırdaki katsayıların ve sağ taraf değerinin kesirsel kısımlarını (

f_j

) hesaplayın.

Sağ taraf (

17/6 = 2 + 5/6

) için

f_0 = 5/6

;

s_1

katsayısı (

4/3 = 1 + 1/3

) için

f_1 = 1/3

;

s_2

katsayısı (

-1/6 = -1 + 5/6

) için

f_2 = 5/6

bulunur.

Gomory kesme düzlemi, katsayıların tam sayı olmayan (kesirsel) kısımları üzerine inşa edilir.

2

Gomory kısıt denklemi formülünü (

s_g - \sum f_j x_j = -f_0

) uygulayın.

s_g - (1/3)s_1 - (5/6)s_2 = -5/6

denklemi elde edilir.

Bu kısıt, mevcut sürekli uygun çözüm alanını daraltırken hiçbir tam sayılı çözümü dışarıda bırakmaz.

3

Elde edilen denklemi seçeneklerle karşılaştırarak doğruluğunu teyit edin.

s_g - \frac{1}{3}s_1 - \frac{5}{6}s_2 = -\frac{5}{6}

sonucu doğrulanmıştır.

İşlem hatası yapılmadığından ve negatif katsayıların kesirsel kısımları doğru alındığından emin olunur.

Anahtar Kavram

Gomory Kesme Düzlemi Oluşturma

Alternatif Yöntem

Kısıtı oluştururken önce denklemi tam sayı ve kesirsel kısımlarına ayırıp (

x_1 + (1+1/3)s_1 + (-1+5/6)s_2 = 2 + 5/6

), tam sayıları bir tarafa kesirleri diğer tarafa toplayarak da kontrol edebilirsiniz.

Tahmini Süre:1m 30s

Soru 23Soru →

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

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

\text{Kısıtlar:}

3x_1 + 2x_2 \leq 10

x_1 + 4x_2 \leq 11

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

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

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

x_1 \leq 1

ve

x_1 \geq 2

x_1 < 1

ve

x_1 > 2

x_1 \leq 1,8

ve

x_1 \geq 2

x_2 \leq 2

ve

x_2 \geq 3

x_1 \geq 1

ve

x_1 \leq 2

Cevabı ve açıklamayı göster

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

Cevap

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

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

Adım Adım Çözüm

1

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

x_1 = 1,8

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

2

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

1 ve 2

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

1 < 1,8 < 2

).

3

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

x_1 \leq 1

ve

x_1 \geq 2

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

Anahtar Kavram

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

İpuçları

1

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

2

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

Tahmini Süre:1m 30s

Soru 24Soru →

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

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

\text{Kısıtlar:}

x_1 + x_2 \leq 4,5

x_1 \leq 3,2

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

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

31,5

32,1

24,0

31,0

Uygun çözüm yoktur

Cevabı ve açıklamayı göster

Cevap: 31,5

Cevap

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

Dallandırma işlemi sonucunda

x_1 \leq 3

kısıtı modele eklenir. Bu durumda

x_1

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

x_1 = 3

değeri ilk kısıtta (

x_1 + x_2 \leq 4,5

) yerine yazıldığında

x_2 \leq 1,5

elde edilir. Amaç fonksiyonu

8(3) + 5(1,5)

işleminden 31,5 olarak hesaplanır.

Adım Adım Çözüm

1

Alt problemin kısıtlarını belirleme

x_1 + x_2 \leq 4,5

,

x_1 \leq 3,2

ve

x_1 \leq 3

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

2

Kısıtları sadeleştirme

x_1 + x_2 \leq 4,5

ve

x_1 \leq 3

x_1 \leq 3

kısıtı,

x_1 \leq 3,2

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

3

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

x_1 = 3

için

x_2 = 4,5 - 3 = 1,5

bulunur.

x_1

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

x_2

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

4

Amaç fonksiyonunu hesaplama

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

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

Anahtar Kavram

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

Daha Fazla Pratik

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

Tahmini Süre:1m 30s

Soru 25Soru →

Balas’ın Kapalı Sayımlama (Additive) algoritması ile çözülen bir $0-1$ tamsayılı minimizasyon probleminde, o ana kadar elde edilen en iyi uygun çözümün amaç fonksiyonu değeri $Z^* = 15$ olarak kaydedilmiştir. Algoritmanın bir aşamasında incelenen bir düğümdeki (kısmi çözüm) atanmış değişkenlerin maliyet katsayıları toplamı $12$ ’dir. Bu düğümde serbest durumda bulunan üç değişkenin maliyet katsayıları ise sırasıyla $4, 5$ ve $7$ ’dir. Yapılan teknik incelemede, kısıtların tamamının sağlanabilmesi için bu serbest değişkenlerden en az birinin $1$ değerini almasının zorunlu olduğu saptanmıştır.

Buna göre, incelenen bu düğümün durumu ile ilgili aşağıdakilerden hangisi doğrudur?

Atanmış değişkenlerin maliyeti (

12

), mevcut en iyi çözümden (

15

) küçük olduğu için dallandırma işlemine mutlaka devam edilmelidir.

Kısmi çözüm henüz uygun bir çözüm üretmediği için bu düğüm sadece "uygunsuzluk" (infeasibility) kriteri gerçekleşirse budanabilir.

Kısıtları sağlamak için gereken en küçük ek maliyetle dahi toplam maliyet

16

(

12 + 4

) olacağı ve bu değer

Z^* = 15

’ten büyük olduğu için düğüm budanmalıdır.

Elde edilen

12

değeri

15

’ten küçük olduğundan, serbest değişkenlere uygun değerler atanarak

12

değerinden daha küçük bir amaç fonksiyonu sonucuna ulaşılabilir.

Algoritma kuralları gereği, serbest değişkenlerin tamamı

1

yapılarak kısıtların sağlanıp sağlanmadığı kontrol edilmeden budama kararı verilemez.

Cevabı ve açıklamayı göster

Cevap: Kısıtları sağlamak için gereken en küçük ek maliyetle dahi toplam maliyet $16$ ( $12 + 4$ ) olacağı ve bu değer $Z^* = 15$ ’ten büyük olduğu için düğüm budanmalıdır.

Cevap

Kısıtları sağlamak için gereken en düşük maliyet eklendiğinde (

12 + 4 = 16

) elde edilen alt sınır mevcut en iyi çözümden (

15

) büyük olduğu için düğüm budanmalıdır.

Balas'ın Kapalı Sayımlama algoritmasında, bir düğümden (kısmi çözüm) elde edilebilecek en iyi sonuç bile mevcut en iyi çözümden (

Z^*

) daha kötüyse, o dalın daha fazla incelenmesine gerek kalmaz ve budama işlemi yapılır. Soruda kısıtların sağlanması için en az bir değişkenin seçilmesi gerektiği belirtilmiştir. En ucuz seçenek olan

4

birimlik maliyet eklendiğinde bile toplam maliyet

16

olmaktadır.

16 > 15

olduğu için bu dal kesinlikle elenmelidir.

Adım Adım Çözüm

1

Mevcut durumun analizi

Z^* = 15

, mevcut maliyet

= 12

, serbest değişken katsayıları

= \{4, 5, 7\}

Algoritmanın budama kriterlerini değerlendirmek için mevcut sınırı ve kısmi çözümün yükünü belirlemek gerekir.

2

Kısıt gereksiniminin belirlenmesi

En az bir serbest değişken

1

olmalıdır.

Kısmi çözümün kısıtları henüz sağlamadığı ve kısıtları sağlamak için ek maliyetin zorunlu olduğu anlaşılmaktadır.

3

Alt sınırın (Z-sınırı) hesaplanması

Minimum maliyet

= 12 + \min(4, 5, 7) = 12 + 4 = 16

Bu daldan elde edilebilecek en iyimser (en düşük maliyetli) çözümün değerini bulmak için en küçük katsayılı serbest değişken seçilir.

4

Budama kriterinin uygulanması

16 > 15

olduğu için düğüm budanır (fathomed).

Hesaplanan alt sınır mevcut en iyi çözümden (üst sınır) daha kötü olduğu için bu dalda daha iyi bir çözüm bulma imkanı kalmamıştır.

Anahtar Kavram

Balas algoritmasında amaç fonksiyonu (Z-sınırı) kriterine göre budama işlemi.

Soru 26Soru →

Bir yerel yönetim, iki farklı bölgeden (Bölge A ve Bölge B) en fazla birinde yeni bir atık geri dönüşüm tesisi kurmayı planlamaktadır. Tesislere dair maliyet ve kapasite verileri aşağıda sunulmuştur:

Parametre	Bölge A	Bölge B
Sabit Kurulum Maliyeti	$1.000.000$ TL	$1.500.000$ TL
Ton Başına İşletme Maliyeti	$50$ TL	$40$ TL
Maksimum Kapasite (Ton)	$5.000$	$7.000$

Belediyenin toplamda en az $4.000$ ton atık işlemesi gerekmektedir. İşlenen atık miktarı ton cinsinden süreklilik gösterebilmektedir. $x_A, x_B \geq 0$ işlenen atık miktarını; $y_A, y_B \in \{0, 1\}$ ise tesisin kurulma durumunu ( $1$ : kuruldu, $0$ : kurulmadı) temsil etmektedir.

Buna göre, toplam maliyeti minimize eden doğru karma tamsayılı programlama modeli aşağıdakilerden hangisidir?

\min Z = 1.000.000y_A + 1.500.000y_B + 50x_A + 40x_B

x_A + x_B \geq 4.000

x_A \leq 5.000y_A

x_B \leq 7.000y_B

y_A + y_B \leq 1

x_A, x_B \geq 0; y_A, y_B \in \{0, 1\}

\min Z = 1.000.000y_A + 1.500.000y_B + 50x_A + 40x_B

x_A + x_B \geq 4.000

x_A \leq 5.000y_A

x_B \leq 7.000y_B

y_A + y_B = 1

x_A, x_B \geq 0; y_A, y_B \in \{0, 1\}

\min Z = 50x_A + 40x_B

x_A + x_B \geq 4.000

x_A \leq 5.000

x_B \leq 7.000

x_A, x_B \geq 0

(tamsayı)

\min Z = 1.000.000y_A + 1.500.000y_B + 50x_A + 40x_B

x_A + x_B \leq 4.000

x_A \leq 5.000y_A

x_B \leq 7.000y_B

y_A + y_B \geq 1

x_A, x_B \geq 0; y_A, y_B \in \{0, 1\}

\min Z = 1.000.000x_A + 1.500.000x_B

x_A + x_B \geq 4.000

x_A, x_B \in \{0, 1\}

Cevabı ve açıklamayı göster

Cevap: $\min Z = 1.000.000y_A + 1.500.000y_B + 50x_A + 40x_B$
$x_A + x_B \geq 4.000$
$x_A \leq 5.000y_A$
$x_B \leq 7.000y_B$
$y_A + y_B \leq 1$
$x_A, x_B \geq 0; y_A, y_B \in \{0, 1\}$

Cevap

Doğru model, amaç fonksiyonunda hem sabit maliyetleri (

1.000.000y_A + 1.500.000y_B

) hem de değişken maliyetleri (

50x_A + 40x_B

) toplayan, kurulum yapılmadığında üretimi engelleyen (

x \leq Ky

) ve tesis seçimini 'en fazla bir' (

y_A + y_B \leq 1

) olarak sınırlayan yapıdır.

Karma tamsayılı programlama modellerinde, bir aktivitenin gerçekleşmesi (tesis kurulması gibi) bir 'evet/hayır' kararı gerektirir ve bu karar değişkeni (

y

) ile süreklilik arz eden miktar değişkeni (

x

) birbirine

x \leq K \cdot y

eşitsizliği ile bağlanır. Doğru cevapta hem bu mantıksal bağ kurulmuş, hem de maliyet fonksiyonu ve seçim kısıtlaması doğru ifade edilmiştir.

Adım Adım Çözüm

1

Amaç fonksiyonunun oluşturulması

\min Z = 1.000.000y_A + 1.500.000y_B + 50x_A + 40x_B

Toplam maliyet, tesisin açılması durumunda katlanılan sabit maliyet ile her bir ton atık için oluşan değişken maliyetin toplamıdır.

2

Talep ve kapasite kısıtlarının tanımlanması

x_A + x_B \geq 4.000

;

x_A \leq 5.000y_A

;

x_B \leq 7.000y_B

En az

4.000

ton işlenmesi gerekir. Ayrıca

y=0

ise

x=0

olmasını sağlayan mantıksal bağlantı kurulmalıdır.

3

Seçim ve değişken türü kısıtlarının eklenmesi

y_A + y_B \leq 1

;

y \in \{0, 1\}

;

x \geq 0

'En fazla bir' ifadesi toplamın

1

veya

0

olabileceğini gösterir. Miktarlar sürekli, seçimler ise kesiklidir (binary).

Anahtar Kavram

Sabit Maliyetli Karma Tamsayılı Modelleme (Fixed Charge Problem)

Daha Fazla Pratik

Mantıksal kısıtlardan 'Bağımlı Kararlar' (A seçilirse B de seçilmeli) durumunun modellemesini inceleyin.

Tahmini Süre:2m 0s

Soru 27Soru →

Saf tam sayılı bir doğrusal programlama modelinin doğrusal gevşetilmesi (LP relaxation) simpleks yöntemi ile çözülmüş ve elde edilen optimal tablo aşağıda sunulmuştur:

Temel Değ.	$Z$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	Sağ Yan
$Z$	1	0	0	2	1.5	0.5	25.5
$x_1$	0	1	0	1	0.2	-0.4	4.0
$x_2$	0	0	1	0	2.4	-1.2	3.6

Tablodaki tüm değişkenlerin tam sayı olması gerektiği bilindiğine göre, $x_2$ temel değişkeninin bulunduğu satır kullanılarak oluşturulacak Gomory kesme düzlemi (cut) kısıtı aşağıdakilerden hangisidir?

s_g - \frac{2}{5}x_4 - \frac{4}{5}x_5 = -\frac{3}{5}

s_g - \frac{2}{5}x_4 - \frac{1}{5}x_5 = -\frac{3}{5}

s_g - \frac{2}{5}x_4 - \frac{4}{5}x_5 = \frac{3}{5}

s_g - \frac{2}{5}x_4 + \frac{4}{5}x_5 = -\frac{3}{5}

s_g - \frac{2}{5}x_4 + \frac{1}{5}x_5 = -\frac{3}{5}

Cevabı ve açıklamayı göster

Cevap: $s_g - \frac{2}{5}x_4 - \frac{4}{5}x_5 = -\frac{3}{5}$

Cevap

Doğru kısıt denklemi

s_g - \frac{2}{5}x_4 - \frac{4}{5}x_5 = -\frac{3}{5}

şeklindedir.

Doğru yanıt olan ifadede,

x_2

satırındaki

2.4

katsayısı

2 + 0.4

,

-1.2

katsayısı

-2 + 0.8

ve sağ yan değeri olan

3.6

ise

3 + 0.6

şeklinde ayrıştırılmıştır. Buradan elde edilen

0.4x_4 + 0.8x_5 \geq 0.6

kısıtı,

s_g

aylak değişkeni eklenerek düzenlenen

s_g - 2/5x_4 - 4/5x_5 = -3/5

formuna tam olarak uymaktadır.

Adım Adım Çözüm

1

x_2

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

x_2 + 2.4x_4 - 1.2x_5 = 3.6

Kesme düzlemi oluşturmak için ilgili satırın matematiksel ifadesi gereklidir.

2

Katsayıları ve sağ yan değerini tam sayı ve pozitif kesirsel kısımlara (

0 \leq f < 1

) ayırın.

2.4 = 2 + 0.4

,

-1.2 = -2 + 0.8

ve

3.6 = 3 + 0.6

Gomory kuralına göre

f_j = a_j - \lfloor a_j \rfloor

işlemi uygulanmalıdır. Özellikle

-1.2 - (-2) = 0.8

işlemine dikkat edilmelidir.

3

Kesirsel kısımları kullanarak

\sum f_j x_j \geq f_i

eşitsizliğini kurun.

0.4x_4 + 0.8x_5 \geq 0.6

Gomory kesmesi, mevcut kısıtın tamsayılı çözümleri dışlamadan gevşetilmiş alanı daraltan kısımdır.

4

Eşitsizliği standart simpleks formuna (

s_g

aylak değişkeni ekleyerek) dönüştürün.

0.4x_4 + 0.8x_5 - s_g \leq 0.6

veya

s_g - 0.4x_4 - 0.8x_5 = -0.6

Simpleks tablosuna eklenebilmesi için kısıtın eşitlik formunda ifade edilmesi gerekir.

5

Ondalık sayıları kesirli ifadelere çevirin.

0.4 = 2/5

,

0.8 = 4/5

,

0.6 = 3/5

Akademik ve sınav formatına uygun gösterim için kesirli ifadeler kullanılır.

Anahtar Kavram

Gomory kesme düzlemi algoritmasında, negatif katsayıların kesirsel kısmı belirlenirken katsayıdan küçük en büyük tam sayı çıkarılır (

f = a - \lfloor a \rfloor

).

Alternatif Yöntem

Ondalık sayılarla işlem yapmak yerine tüm satırı payda eşitleyerek kesirlere çevirip (

x_2 + 12/5x_4 - 6/5x_5 = 18/5

) ardından pay kısmında modüler aritmetik mantığıyla (pozitif kalan verecek şekilde) bölme yapmak hata payını azaltabilir.

Tahmini Süre:1m 30s

Soru 28Soru →

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

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

\text{Kısıtlar:}

x_1 + x_2 \leq 6

9x_1 + 5x_2 \leq 45

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

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

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

41,00

41,25

39,00

32,00

45,00

Cevabı ve açıklamayı göster

Cevap: 41,00

Cevap

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

Dallandırma kuralına göre

x_1 \geq 4

kısıtı modele eklendiğinde,

x_1

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

4

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

x_2

değişkeni en fazla

1,8

değerini alabilir.

8(4) + 5(1,8)

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

Adım Adım Çözüm

1

x_1 \geq 4

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

Yeni kısıtlar:

x_1 \geq 4

,

x_1 + x_2 \leq 6

ve

9x_1 + 5x_2 \leq 45

.

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

2

Eklenen kısıtlar altında

x_2

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

x_1 = 4

için:

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

ve

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

.

Maksimizasyon probleminde,

Z

fonksiyonunun katsayıları pozitif olduğundan

x_1

ve

x_2

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

x_2

için en dar kısıt

1,8

değeridir.

3

Bulunan

(x_1, x_2)

değerlerini amaç fonksiyonunda yerine koyun.

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

.

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

Anahtar Kavram

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

Daha Fazla Pratik

Bu düğümden sonra

x_2 = 1,8

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

Tahmini Süre:1m 30s

Soru 29Soru →

Saf tam sayılı bir doğrusal programlama probleminin doğrusal gevşetilmesi (LP relaxation) simpleks yöntemi ile çözülmüş ve elde edilen optimal simpleks tablosunda, tamsayı değer alması gereken $x_2$ temel değişkenine ait satır aşağıdaki gibi belirlenmiştir:

x_2 + \frac{5}{6}s_1 - \frac{1}{3}s_2 = \frac{17}{6}

Buna göre, Gomory kesme düzlemi algoritması kullanılarak bu satırdan türetilecek olan kesme kısıtı (Gomory kesisi) aşağıdakilerden hangisidir? ( $s_g$ , yeni eklenen aylak değişkendir.)

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

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

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

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

s_g - \frac{5}{6}s_1 - \frac{1}{3}s_2 = -\frac{17}{6}

Cevabı ve açıklamayı göster

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

Cevap

Gomory kesme kısıtı denklemi

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

şeklindedir.

Verilen satırda sağ taraf sabiti olan

17/6

değerinin kesirsel kısmı

5/6

,

s_1

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

5/6

ve

-1/3

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

-1 + 2/3

olduğu için)

2/3

olarak bulunur. Formülde yerine yazıldığında

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

ifadesine ulaşılır.

Adım Adım Çözüm

1

Temel değişken satırındaki tüm katsayıları ve sağ taraf sabitini tam ve kesirsel kısımlarına (

0 \leq f < 1

) ayırın.

\frac{17}{6} = 2 + \frac{5}{6} \Rightarrow f_{i0} = \frac{5}{6}

\frac{5}{6} = 0 + \frac{5}{6} \Rightarrow f_{s1} = \frac{5}{6}

-\frac{1}{3} = -1 + \frac{2}{3} \Rightarrow f_{s2} = \frac{2}{3}

Gomory algoritmasında kısıtlar sadece değişkenlerin kesirsel kısımları kullanılarak oluşturulur.

2

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

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

) uygulayın.

s_g - (\frac{5}{6})s_1 - (\frac{2}{3})s_2 = -\frac{5}{6}

Bu formül, tamsayı kısıtını sağlayan en sıkı doğrusal kesmeyi üretir.

Anahtar Kavram

Gomory kesme kısıtı oluşturulurken negatif katsayıların kesirsel kısımları, katsayıdan küçük veya eşit olan en büyük tamsayı çıkarılarak (

f = a - \lfloor a \rfloor

) pozitif bir değer olarak hesaplanmalıdır.

Soru 30Soru →

Saf tam sayılı bir doğrusal programlama probleminin doğrusal gevşetilmesi (LP relaxation) simpleks yöntemi ile çözülmüş ve elde edilen optimal simpleks tablosunda $x_1$ temel değişkenine ait satır şu şekilde belirlenmiştir:

Temel Değişken	$x_1$	$x_2$	$s_1$	$s_2$	Sağ Taraf
$x_1$	1	0	$\frac{7}{3}$	$-\frac{5}{6}$	$\frac{13}{4}$

Burada $s_1$ ve $s_2$ aylak değişkenleri temsil etmektedir. Gomory kesme düzlemi algoritması uyarınca, bu satırdan türetilecek olan yeni kesme kısıtı (Gomory kesiği) aşağıdakilerden hangisidir? ( $s_g$ yeni eklenen kesme değişkenidir.)

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

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

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

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

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

Cevabı ve açıklamayı göster

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

Cevap

Gomory kesme kısıtı denklemi

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

şeklindedir.

Gomory kesme kısıtı oluşturulurken satırdaki her bir katsayı

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

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

0 \leq f_{ij} < 1

olmalıdır. Verilen satırda

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

olduğundan

f_{11} = \frac{1}{3}

;

-\frac{5}{6} = -1 + \frac{1}{6}

olduğundan

f_{12} = \frac{1}{6}

ve sağ taraf

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

olduğundan

f_{i0} = \frac{1}{4}

bulunur. Gomory kısıtı

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

formülüyle yazıldığında

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

denklemi elde edilir.

Adım Adım Çözüm

1

Optimal tablodaki satırın katsayılarını tam sayı ve pozitif kesirli kısımlarına ayrıştırın.

x_1 + (2 + \frac{1}{3})s_1 + (-1 + \frac{1}{6})s_2 = 3 + \frac{1}{4}

Gomory kesiği oluşturulurken her bir katsayının

a = \lfloor a \rfloor + f

formuna (burada

0 \leq f < 1

) getirilmesi gerekir.

2

Katsayıların ve sağ tarafın kesirli kısımlarını (

f

) belirleyin.

f_{s1} = \frac{1}{3}

,

f_{s2} = \frac{1}{6}

,

f_{RHS} = \frac{1}{4}

Kesirli kısımlar kısıtın katsayılarını oluşturur. Negatif katsayılar için:

-\frac{5}{6} = -1 + \frac{1}{6}

olduğundan kesirli kısım

\frac{1}{6}

'dır.

3

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

formülünü uygulayın.

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

Bu formül, tam sayı olmayan çözümün dışlanmasını sağlayan en sıkı doğrusal kesiği üretir.

Anahtar Kavram

Gomory kesme düzlemi algoritmasında, bir satırdan kısıt üretilirken katsayıların 'en küçük pozitif kesirli kısımları' (proper fractional parts) kullanılır.

Soru 31Soru →

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

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

Kısıtlar:

x_1 + 2x_2 \leq 10

4x_1 + 3x_2 \leq 24

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

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

24

25

27

28

30,4

Cevabı ve açıklamayı göster

Cevap: 28

Cevap

Optimal kâr değeri 28'dir ve bu değer

x_1 = 2

,

x_2 = 4

noktasında elde edilir.

Modelde tüm kısıtları sağlayan tamsayı noktaları incelendiğinde,

(2,4)

noktası için

x_1 + 2x_2 = 10

(tam kapasite) ve

4x_1 + 3x_2 = 20 \leq 24

(uygun) şartları sağlanır. Bu noktada amaç fonksiyonu

Z = 4(2) + 5(4) = 28

değerine ulaşır. Diğer uygun tamsayı noktaları (

(3,3) \rightarrow 27

,

(0,5) \rightarrow 25

,

(6,0) \rightarrow 24

) bu değerden daha küçüktür.

Adım Adım Çözüm

1

Doğrusal programlama (LP) gevşetmesi çözümünü belirle.

x_1 + 2x_2 = 10

ve

4x_1 + 3x_2 = 24

doğrularının kesişim noktası

(3,6; 3,2)

ve

Z = 30,4

.

Tamsayılı çözümün üst sınırını ve aday noktaların yerini belirlemek için önce sürekli çözüm bulunur.

2

Kesişim noktası civarındaki uygun tamsayı noktalarını değerlendir.

(3,3), (4,2), (2,4)

ve

(0,5)

gibi noktalar kısıtlar çerçevesinde kontrol edilir.

Saf tamsayılı modellerde çözüm, sürekli çözümün en yakınındaki uygun tamsayı koordinatlarından biridir.

3

(2,4)

noktasının uygunluğunu ve kâr değerini hesapla.

2 + 2(4) = 10 \leq 10

ve

4(2) + 3(4) = 20 \leq 24

(Uygun).

Z = 4(2) + 5(4) = 28

.

Seçilen noktanın her iki kısıtı da sağlayıp sağlamadığı test edilir.

4

(3,3)

noktasının kâr değeri ile karşılaştır.

3 + 2(3) = 9 \leq 10

ve

4(3) + 3(3) = 21 \leq 24

(Uygun).

Z = 4(3) + 5(3) = 27

.

En büyük kârı veren noktanın optimal olduğunu teyit etmek için diğer adaylar karşılaştırılır.

Anahtar Kavram

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

Tahmini Süre:2m 0s

Soru 32Soru →

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

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

\text{Kısıtlar:}

x_1 + x_2 \leq 5

4x_1 + 7x_2 \leq 28

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

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

24

25

26,75

27

27,67

Cevabı ve açıklamayı göster

Cevap: 27

Cevap

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

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

Z=27,67

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

x_2

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

x_2 \leq 2

kolunda

(3,2)

tamsayılı çözümü ve

Z=27

değeri elde edilir. Diğer kol olan

x_2 \geq 3

incelendiğinde ise en iyi değerin

Z=26,75

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

Adım Adım Çözüm

1

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

x_1 = 2,33

(7/3),

x_2 = 2,67

(8/3) ve

Z = 27,67

(83/3)

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

2

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

x_2

değişkeni üzerinden

x_2 \leq 2

ve

x_2 \geq 3

dalları oluşturulur.

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

3

x_2 \leq 2

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

x_1 = 3, x_2 = 2

ve

Z = 27

(Tamsayılı çözüm)

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

4

x_2 \geq 3

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

x_1 = 1,75, x_2 = 3

ve

Z = 26,75

Bu daldaki en iyi çözümün

Z

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

5

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

Z = 27

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

Anahtar Kavram

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

Daha Fazla Pratik

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

Alternatif Yöntem

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

Tahmini Süre:2m 30s

Soru 33Soru →

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

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

\text{Kısıt:}

2x_1 + 2x_2 \leq 7

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

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

x_1 = 0, x_2 = 3

x_1 = 0, x_2 = 3,5

x_1 = 1, x_2 = 2

x_1 = 3, x_2 = 0

x_1 = 2, x_2 = 2

Cevabı ve açıklamayı göster

Cevap: $x_1 = 0, x_2 = 3$

Cevap

Modelin en iyi çözümü

x_1 = 0

ve

x_2 = 3

olarak belirlenmiştir.

Değişkenlerin

x_1 = 0

ve

x_2 = 3

olduğu çözümde, kısıt denklemi (

0+6 \leq 7

) sağlanmakta ve amaç fonksiyonu en yüksek tamsayı değeri olan 15'e ulaşmaktadır.

Adım Adım Çözüm

1

Kısıt bölgesindeki tamsayı noktaları belirle.

x_1 + x_2 \leq 3,5

olduğu için toplamları 3 veya daha küçük olan tamsayı ikilileri: (0,0), (1,0), (2,0), (3,0), (0,1), (0,2), (0,3), (1,1), (1,2), (2,1).

Saf tamsayılı programlamada sadece tamsayı değerli koordinatlar aday çözümdür.

2

Aday noktalar için amaç fonksiyonu değerlerini hesapla.

Z(0,3) = 4(0) + 5(3) = 15

;

Z(1,2) = 4(1) + 5(2) = 14

;

Z(2,1) = 4(2) + 5(1) = 13

;

Z(3,0) = 4(3) + 5(0) = 12

.

En büyük Z değerini veren nokta optimal çözümdür.

3

Sonuçları karşılaştır.

Z=15

en yüksek değerdir.

Maksimum verimlilik bu noktada elde edilir.

Anahtar Kavram

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

Daha Fazla Pratik

Değişkenlerden sadece birinin tamsayı olması durumunda 'Karma Tamsayılı Programlama' yöntemlerini inceleyebilirsiniz.

Tahmini Süre:45s

Soru 34Soru →

Bir kamu kurumunda kurulacak olan bir çalışma komisyonu için belirlenen 3 aday ( $x_1, x_2$ ve $x_3$ ) arasından bütçe kısıtları nedeniyle en fazla iki adayın seçilmesine karar verilmiştir.

Adayların seçilmesi durumunda karar değişkenlerinin 1, seçilmemesi durumunda 0 değerini aldığı varsayıldığında; bu mantıksal kısıtı ifade eden matematiksel model aşağıdakilerden hangisidir?

x_1 + x_2 + x_3 \leq 2

x_1 + x_2 + x_3 \geq 2

x_1 + x_2 + x_3 = 2

x_1 + x_2 + x_3 \leq 1

x_1 + x_2 + x_3 = 3

Cevabı ve açıklamayı göster

Cevap: $x_1 + x_2 + x_3 \leq 2$

Cevap

En fazla iki adayın seçilmesini sağlayan

x_1 + x_2 + x_3 \leq 2

kısıtıdır.

Sıfır-bir tamsayılı programlama modellerinde, belirli bir küme içerisinden seçilecek eleman sayısına üst sınır getirilmek istendiğinde (en fazla k kadar), değişkenlerin toplamının bu sınıra küçük-eşit (

\leq

) olması sağlanır. Bu soruda toplam 3 aday arasından en fazla 2 kişi seçilebileceği için toplam 2'den büyük olamaz.

Adım Adım Çözüm

1

Karar değişkenlerinin tanımlanması

x_i \in \{0, 1\}

(1: Seçildi, 0: Seçilmedi)

0-1 tamsayılı programlama modellerinde seçim durumları ikili değişkenlerle ifade edilir.

2

Mantıksal koşulun matematiksel dile çevrilmesi

Seçilenlerin toplamı

\leq

İzin verilen üst sınır

'En fazla' (at most) ifadesi matematikte küçük-eşit (

\leq

) sembolü ile gösterilir.

3

Kısıtın yazılması

x_1 + x_2 + x_3 \leq 2

Toplam seçilecek kişi sayısının 2'yi aşmaması gerektiği için toplam 2'den küçük veya 2'ye eşit olmalıdır.

Anahtar Kavram

Sıfır-Bir (0-1) Tamsayılı Programlamada 'n içerisinden en fazla k' kısıtı

Alternatif Yöntem

Değişkenlere değer vererek test edilebilir: Eğer üçü de seçilirse (

1+1+1=3

) kısıt

3 \leq 2

olur ki bu yanlıştır; bu da kısıtın doğru çalıştığını kanıtlar.

Tahmini Süre:45s

Soru 35Soru →

Kamuya ait bir enerji üretim santralinin günlük operasyon maliyetlerini minimize etmek amacıyla bir karma tamsayılı programlama modeli kurulmak istenmektedir. Santralin devreye alınması durumunda $8.000$ TL tutarında bir sabit hazırlık maliyeti söz konusudur. Santral çalıştırıldığında üretilen her $1$ MW elektrik için değişken maliyet $100$ TL olarak hesaplanmıştır. Teknik kısıtlar nedeniyle santral, eğer çalıştırılırsa en az $50$ MW, en fazla $500$ MW elektrik üretebilmektedir.

$x$ : Üretilen elektrik miktarı (MW) (sürekli değişken)
$y$ : Santralin çalışma durumu ( $1$ : çalışıyor, $0$ : çalışmıyor) (binary değişken)

Buna göre, toplam maliyeti ( $Z$ ) minimize eden amaç fonksiyonu ve kapasite kısıtlarını içeren matematiksel model aşağıdakilerden hangisidir?

\min Z = 8000y + 100x

;

x \leq 500y, \ x \geq 50y, \ y \in \{0, 1\}, \ x \geq 0

\min Z = 8000 + 100x

;

50 \leq x \leq 500, \ x \geq 0

\min Z = 8000y + 100x

;

x \leq 500, \ x \geq 50y, \ y \in \{0, 1\}, \ x \geq 0

\min Z = 8000y + 100x

;

x + y \leq 500, \ x + y \geq 50, \ y \in \{0, 1\}, \ x \geq 0

\min Z = 8000x + 100y

;

x \leq 500y, \ x \geq 50y, \ y \in \{0, 1\}, \ x \geq 0

Cevabı ve açıklamayı göster

Cevap: $\min Z = 8000y + 100x$ ; $x \leq 500y, \ x \geq 50y, \ y \in \{0, 1\}, \ x \geq 0$

Cevap

Doğru model, toplam maliyeti

\min Z = 8000y + 100x

olarak tanımlayan ve üretim miktarını

50y \leq x \leq 500y

kısıtları ile çalışma durumuna bağlayan ifadedir.

Karma tamsayılı programlama modellerinde, bir aktivitenin yapılıp yapılmadığını temsil eden binary değişken (

y

), aktivitenin seviyesini temsil eden sürekli değişkenin (

x

) sınırlarını belirlemek için kullanılır. Bu soruda, tesisin çalışma durumu

y=1

olduğunda

8000

TL sabit maliyet amaç fonksiyonuna eklenir ve üretim miktarı

50 \leq x \leq 500

aralığında sınırlandırılır. Tesis kapalıyken (

y=0

) ise maliyet sıfır olur ve kısıtlar

0 \leq x \leq 0

haline gelerek üretimi engeller.

Adım Adım Çözüm

1

Karar değişkenlerinin ve maliyetlerin belirlenmesi

Amaç fonksiyonu bileşenleri: Sabit maliyet

8.000y

ve değişken maliyet

100x

olarak belirlenir.

Maliyet fonksiyonunu oluşturmak için sabit ve değişken unsurların doğru değişkenlerle çarpılması gerekir.

2

Amaç fonksiyonunun oluşturulması

\min Z = 8000y + 100x

Toplam maliyetin minimize edilmesi istenmektedir ve sabit maliyet sadece

y=1

olduğunda aktiftir.

3

Kapasite kısıtlarının mantıksal yapıya oturtulması

x \leq 500y

ve

x \geq 50y

eşitsizlikleri elde edilir.

Tesis çalışmıyorsa (

y=0

) üretimin sıfır olması, çalışıyorsa (

y=1

) ise üretimin 50 ile 500 MW arasında olması bu kısıtlarla garanti edilir.

Anahtar Kavram

Sabit Hazırlık (Fixed Charge) Maliyetli Karma Tamsayılı Modeller

İpuçları

1

Sabit maliyetin sadece santral çalıştığında (

y=1

) devreye girmesi gerektiğini düşünün.

2

Tesis kapalıyken (

y=0

) üretimin (

x

) zorunlu olarak sıfıra eşitlenmesi için

x \leq Max \cdot y

kalıbını kullanın.

3

Alt ve üst sınırların her ikisinin de

y

değişkeni ile çarpıldığı

50y \leq x \leq 500y

yapısı, santralin çalışma aralığını tam olarak yansıtır.

Daha Fazla Pratik

Mantıksal kısıtların (ya A ya B projeleri gibi) MIP modellerine nasıl dahil edildiğini çalışmak konuyu pekiştirecektir.

Tahmini Süre:1m 30s

Soru 36Soru →

Bir kamu kurumu, dijital dönüşüm süreci kapsamında "Elektronik Belge Yönetimi" ( $x_1$ ) ve "Dijital Arşiv" ( $x_2$ ) projelerinden en az birini hayata geçirmek zorundadır. Projelerin seçilmesi durumunda karar değişkeninin 1, seçilmemesi durumunda 0 değerini aldığı varsayıldığında; bu mantıksal zorunluluğu ifade eden kısıt denklemi aşağıdakilerden hangisidir?

x_1 + x_2 \geq 1

x_1 + x_2 \leq 1

x_1 + x_2 = 1

x_1 \leq x_2

x_1 + x_2 \geq 2

Cevabı ve açıklamayı göster

Cevap: $x_1 + x_2 \geq 1$

Cevap

İki projeden en az birinin seçilmesi durumunu ifade eden matematiksel kısıt

x_1 + x_2 \geq 1

şeklindedir.

Toplamın 1'den büyük veya eşit olması (

x_1 + x_2 \geq 1

), projelerden birinin seçilmesi (toplamın 1 olması) veya her ikisinin birden seçilmesi (toplamın 2 olması) durumlarını kapsar. Bu durum, 'en az bir' ifadesinin matematiksel karşılığıdır.

Adım Adım Çözüm

1

Karar değişkenlerinin olası değerlerini analiz etme

İki adet 0-1 değişkeni için

(x_1, x_2)

kombinasyonları:

(0,0), (0,1), (1,0), (1,1)

şeklindedir.

Mantıksal kısıtın hangi durumları dışlaması gerektiğini belirlemek için tüm olasılıklar görülmelidir.

2

"En az bir" koşulunu uygulama

Sadece

(0,0)

durumu (hiçbirinin seçilmemesi) istenmemektedir. Diğer üç durum

(0,1), (1,0), (1,1)

uygundur.

Soruda belirtilen zorunluluk, sistemin tamamen boş (seçimsiz) kalmasını engeller.

3

Uygun durumları matematiksel eşitsizliğe dökme

0+1=1

,

1+0=1

ve

1+1=2

değerleri her durumda 1'den büyük veya eşittir. Bu nedenle

x_1 + x_2 \geq 1

.

Toplamın 1 veya daha fazla olması, en az bir projenin seçildiğini garanti eder.

Anahtar Kavram

Sıfır-bir tamsayılı programlamada 'en az k' tane seçim yapma mantığı, değişkenlerin toplamının k değerinden büyük veya eşit olmasıyla (

\sum x_i \geq k

) modellenir.

Daha Fazla Pratik

Üç proje arasından tam olarak ikisinin seçilmesi gereken durumu modellemeyi deneyin.

Tahmini Süre:45s

Soru 37Soru →

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

24

25

26

26,67

31

Cevabı ve açıklamayı göster

Cevap: 26

Cevap

Optimum tamsayı çözümü sağlayan kapasite değeri 26'dır.

Yapılan incelemede, kısıt denklemi olan

3x_1 + 5x_2 \leq 16

eşitsizliğini sağlayan tamsayı ikilileri arasında en yüksek amaç değerini 26 ile

(2,2)

noktası vermektedir. Bu noktada

3(2)+5(2)=16

olduğu için kapasite tam kullanılır ve amaç değeri

5(2)+8(2)=26

olur.

Adım Adım Çözüm

1

Amaç fonksiyonunu ve kısıtları matematiksel olarak tanımlayın.

Max Z = 5x_1 + 8x_2

Kısıt:

3x_1 + 5x_2 \leq 16

Değişkenler:

x_1, x_2 \in \mathbb{Z}^+

Saf tamsayılı programlama modelinin kurulması için değişkenlerin tamsayı kısıtı eklenmelidir.

2

Doğrusal programlama gevşetmesini (LP Relaxation) çözerek bir üst sınır belirleyin.

3x_1 + 5x_2 = 16

doğrusunda

x_2=0

için

x_1 \approx 5,33

;

x_1=0

için

x_2 = 3,2

. Amaç fonksiyonu eğimi doğrultusunda LP optimumu

(5,33, 0)

noktasında

Z = 26,67

olur.

Tamsayılı çözümün amaç fonksiyonu değeri, gevşetilmiş modelin değerinden büyük olamaz.

3

Uygun bölge içerisindeki tamsayı noktalarını (aday çözümleri) test edin.

(5,0) \rightarrow Z=25

(4,0) \rightarrow Z=20

(2,2) \rightarrow Z=10+16=26

(0,3) \rightarrow Z=24

(3,1) \rightarrow Z=15+8=23

Saf tamsayılı modellerde optimum nokta her zaman gevşetilmiş çözümün en yakınındaki tamsayı noktası olmayabilir.

4

En yüksek

Z

değerine sahip tamsayı noktasını seçin.

x_1=2

ve

x_2=2

değerleri kısıtı (

3(2)+5(2)=16 \leq 16

) sağlar ve

Z=26

sonucunu verir.

Tüm adaylar arasında en yüksek çıktı bu noktada gerçekleşir.

Anahtar Kavram

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

Soru 38Soru →

Bir lojistik firması, yeni bir dağıtım güzergahı açıp açmama kararı aşamasındadır. Eğer güzergah açılırsa $10.000$ TL tutarında sabit bir hazırlık maliyeti oluşacaktır. Güzergahın aktif olması durumunda taşınan her bir birim ürün için ise $200$ TL değişken operasyonel maliyet söz konusudur. Güzergahın açılma durumu $y$ ( $0-1$ tamsayı değişkeni) ve taşınan ürün miktarı $x$ ( $x \geq 0$ sürekli değişken) ile ifade edildiğine göre, bu problemin toplam maliyetini minimize eden amaç fonksiyonu aşağıdakilerden hangisidir?

\min Z = 10.000y + 200x

\min Z = 10.000x + 200y

\min Z = 10.200(x + y)

\min Z = 10.000 + 200x

\min Z = 10.000y + 200

Cevabı ve açıklamayı göster

Cevap: $\min Z = 10.000y + 200x$

Cevap

Toplam maliyeti minimize eden amaç fonksiyonu

10.000y + 200x

şeklindedir.

Karma tamsayılı programlamada 'sabit maliyet' (hazırlık maliyeti), faaliyetin yapılıp yapılmadığını gösteren bir ikili (0-1) değişkenle (

y

) çarpılır. 'Değişken maliyet' ise faaliyetin miktarını temsil eden sürekli değişkenle (

x

) çarpılır. Bu iki maliyetin toplamı olan

10.000y + 200x

ifadesi doğru amaç fonksiyonudur.

Adım Adım Çözüm

1

Sabit maliyet bileşenini belirlemek

10.000y

Sabit maliyetler sadece ilgili faaliyet (güzergah açma) gerçekleştiğinde (

y=1

) ödenir, aksi halde (

y=0

) ödenmez.

2

Değişken maliyet bileşenini belirlemek

200x

Değişken maliyetler, faaliyetin hacmi veya miktarı (

x

) arttıkça artan maliyetlerdir.

3

Amaç fonksiyonunu birleştirmek

Z = 10.000y + 200x

Toplam maliyet, sabit ve değişken maliyet kalemlerinin toplamından oluşur ve minimize edilmesi hedeflenir.

Anahtar Kavram

Karma Tamsayılı Programlamada Sabit Maliyetli (Fixed Charge) Modeller

Alternatif Yöntem

Mantıksal kontrol yöntemi: Eğer

y=0

ise (hat açılmazsa) toplam maliyetin

0

olması gerekir. Seçeneklerde

y=0

ve

x=0

yazıldığında sadece doğru olan model

0

sonucunu verir.

Tahmini Süre:45s

Soru 39Soru →

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

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

\text{Kısıtlar:}

2x_1 + 3x_2 \leq 12

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

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

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

x_1 \leq 2

ve

x_1 \geq 3

x_1 < 2

ve

x_1 > 3

x_1 \geq 2

ve

x_1 \leq 3

x_1 \leq 2,4

ve

x_1 \geq 2,4

x_1 \leq 3

ve

x_1 \geq 4

Cevabı ve açıklamayı göster

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

Cevap

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

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

v

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

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

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

x_1 = 2,4

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

x_1 \leq 2

ve

x_1 \geq 3

olarak belirlenir.

Adım Adım Çözüm

1

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

x_1 = 2,4

Soruda dallanmanın

x_1

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

2

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

Alt sınır:

\lfloor 2,4 \rfloor = 2

, Üst sınır:

\lceil 2,4 \rceil = 3

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

3

Yeni kısıtları oluşturma

x_1 \leq 2

ve

x_1 \geq 3

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

Anahtar Kavram

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

Daha Fazla Pratik

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

Tahmini Süre:45s

Soru 40Soru →

Balas'ın Kapalı Sayımlama (Additive) algoritması ile çözülen bir $0-1$ tamsayılı minimizasyon probleminde, tüm amaç fonksiyonu katsayılarının negatif olmadığı ( $c_j \geq 0$ ) bilinmektedir. Algoritmanın herhangi bir adımında, incelenen bir düğümdeki kısmi çözümün amaç fonksiyonu değeri ( $Z_{kısmi}$ ), o ana kadar elde edilmiş en iyi uygun çözümün değerine ( $Z^*$ ) eşit veya bu değerden büyükse ( $Z_{kısmi} \geq Z^*$ ), bu düğümün durumu hakkında aşağıdakilerden hangisi söylenebilir?

Düğüm kapalı sayımlanır (budanır) çünkü bu daldan daha iyi bir çözüm gelmesi mümkün değildir.

Düğümden dallandırmaya devam edilir çünkü henüz atanmamış serbest değişkenler amaç değerini küçültebilir.

Düğüm uygun bir çözüm olarak kabul edilir ve tüm algoritma o anda sonlandırılır.

Kısmi çözümün kısıtları sağlayıp sağlamadığına bakılmaksızın yeni bir

Z^*

değeri olarak atanır.

Düğümdeki serbest değişkenlerin tamamına 0 değeri verilerek kısıtların uygunluğu kontrol edilir.

Cevabı ve açıklamayı göster

Cevap: Düğüm kapalı sayımlanır (budanır) çünkü bu daldan daha iyi bir çözüm gelmesi mümkün değildir.

Cevap

Mevcut kısmi çözümün amaç değeri halihazırdaki en iyi çözüm değerine eşit veya ondan büyükse, katsayıların pozitif olması nedeniyle bu daldan daha iyi bir sonuç elde edilemez ve düğüm kapalı sayımlanır (budanır).

Balas algoritmasında amaç fonksiyonu katsayıları negatif olmayacak şekilde düzenlenir. Bir minimizasyon probleminde, bir dalın (düğümün) o ana kadarki maliyeti halihazırda bulduğumuz en iyi çözümün maliyetini geçmişse, o daldan devam ederek daha küçük bir maliyet elde etmemiz matematiksel olarak imkansızdır. Bu duruma algoritma literatüründe 'kapalı sayımlama' veya 'budama' denir.

Adım Adım Çözüm

1

Balas algoritmasının standart formunu hatırla.

Problem minimizasyon yapısındadır ve tüm

c_j \geq 0

katsayılarına sahiptir.

Algoritmanın temel işleyişi katsayıların negatif olmaması üzerine kuruludur.

2

Amaç fonksiyonu değerinin değişimini analiz et.

Yeni değişkenlerin çözüme dahil edilmesi (1 atanması), amaç değerini (

Z

) sadece artırabilir veya sabit bırakabilir.

Katsayılar

c_j \geq 0

olduğu için

Z

değeri azalmaz.

3

Sınır (Bound) kontrolü yap.

Eğer

Z_{kısmi} \geq Z^*

ise, bu daldan gelecek hiçbir çözüm mevcut en iyi çözümü (

Z^*

) iyileştiremez.

Daha iyi bir çözüm bulunma ihtimali kalmadığı için bu dalın incelenmesi durdurulur (kapalı sayımlama).

Anahtar Kavram

Balas Algoritmasında Budama (Fathoming) Kriteri

Tamsayılı Programlama

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

Alternatif Yöntem

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

İpuçları

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

Alternatif Yöntem

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

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Daha Fazla Pratik

Alternatif Yöntem

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

Alternatif Yöntem

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