Examkin

Soru

Zorluk: ZorSıfır-Bir (0-1) Tamsayılı Programlama Modelleri

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

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

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

  1. I. x1+x2≤2x5x_1 + x_2 \leq 2x_5
    II. x1+x4−x3≤1x_1 + x_4 - x_3 \leq 1    Cevap
  2. B
    I. x1+x2≤x5x_1 + x_2 \leq x_5
    II. x1+x4+x3≤2x_1 + x_4 + x_3 \leq 2
  3. C
    I. x1+x2≥2x5x_1 + x_2 \geq 2x_5
    II. x1+x4−x3≥1x_1 + x_4 - x_3 \geq 1
  4. D
    I. x1+x2+x5≤2x_1 + x_2 + x_5 \leq 2
    II. x1+x4≤x3x_1 + x_4 \leq x_3
  5. E
    I. x1+x2≤2x5x_1 + x_2 \leq 2x_5
    II. x1+x4+x3≤1x_1 + x_4 + x_3 \leq 1

Cevap

Birinci karar için x1+x2≤2x5x_1 + x_2 \leq 2x_5, ikinci karar için x1+x4−x3≤1x_1 + x_4 - x_3 \leq 1 eşitsizliklerini içeren seçenek doğrudur.
Doğru eşleşme, kısıtların x1+x2≤2x5x_1 + x_2 \leq 2x_5 ve x1+x4−x3≤1x_1 + x_4 - x_3 \leq 1 olarak verildiği seçenektir. Birinci ifadede x5=0x_5=0 (Kreş yok) olduğunda x1+x2≤0x_1+x_2 \leq 0 olur ve zorunlu olarak Kütüphane ile Spor Salonu yapılamaz (x1=0,x2=0x_1=0, x_2=0). İkinci ifadede x3=0x_3=0 (Havuz yok) olduğunda denklem x1+x4≤1x_1+x_4 \leq 1 halini alır ve en fazla birinin yapılabileceği şartını tam olarak sağlar.

Adım Adım Çözüm

1
Birinci kararı mantıksal olarak analiz edip eşitsizliğe dönüştürmek.
x1+x2≤2x5x_1 + x_2 \leq 2x_5 eşitsizliği elde edilir.
"Kreş (x5x_5) yapılmazsa (x5=0x_5=0), Kütüphane (x1x_1) ve Spor Salonu (x2x_2) yapılamaz" kuralı, x5=0x_5=0 için x1+x2≤0x_1+x_2 \leq 0 olmasını gerektirir. x5=1x_5=1 için herhangi bir engel olmadığından denklem x1+x2≤2x5x_1+x_2 \leq 2x_5 şeklinde veya x1≤x5x_1 \leq x_5 ve x2≤x5x_2 \leq x_5 olarak yazılabilir.
2
İkinci kararı mantıksal olarak analiz edip eşitsizliğe dönüştürmek.
x1+x4−x3≤1x_1 + x_4 - x_3 \leq 1 eşitsizliği elde edilir.
"Yüzme havuzu (x3x_3) yapılmazsa (x3=0x_3=0), Kütüphane (x1x_1) ve Gençlik Merkezi (x4x_4) en fazla 1 olabilir" kuralı, x3=0x_3=0 iken x1+x4≤1x_1+x_4 \leq 1 olmasını gerektirir. x3=1x_3=1 iken kısıtlama yoktur (x1+x4≤2x_1+x_4 \leq 2). Bu durum x1+x4≤1+x3x_1+x_4 \leq 1 + x_3 denklemi ile genel formda ifade edilir ve düzenlenirse x1+x4−x3≤1x_1 + x_4 - x_3 \leq 1 bulunur.

Anahtar Kavram

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

Konular

Sıfır-Bir (0-1) Tamsayılı Programlama Modelleri

Bu konudan daha fazla soru