Examkin

Soru

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

Bir belediye, gelecek yıl için planladığı 5 farklı altyapı projesi (x1,x2,x3,x4,x5x_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:

* x1x_1 ve x2x_2 projelerinden tam olarak biri seçilmelidir.
* x3x_3 projesi seçilirse, x4x_4 projesi de mutlaka seçilmelidir.
* x3,x4x_3, x_4 ve x5x_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?

  1. x1+x2=1;x3≤x4;x3+x4+x5≤2x_1 + x_2 = 1; \quad x_3 \leq x_4; \quad x_3 + x_4 + x_5 \leq 2Cevap
  2. B
    x1+x2≤1;x3≤x4;x3+x4+x5≤2x_1 + x_2 \leq 1; \quad x_3 \leq x_4; \quad x_3 + x_4 + x_5 \leq 2
  3. C
    x1+x2=1;x3≥x4;x3+x4+x5≤2x_1 + x_2 = 1; \quad x_3 \geq x_4; \quad x_3 + x_4 + x_5 \leq 2
  4. D
    x1+x2=1;x3≤x4;x3+x4+x5≥2x_1 + x_2 = 1; \quad x_3 \leq x_4; \quad x_3 + x_4 + x_5 \geq 2
  5. E
    x1+x2=1;x3+x4=1;x3+x4+x5≤2x_1 + x_2 = 1; \quad x_3 + x_4 = 1; \quad x_3 + x_4 + x_5 \leq 2

Cevap

Doğru modelleme x1+x2=1,x3≤x4x_1 + x_2 = 1, x_3 \leq x_4 ve x3+x4+x5≤2x_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 x3≤x4x_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
x1+x2=1x_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
x3≤x4x_3 \leq x_4
x3x_3 seçildiğinde (x3=1x_3=1), x4x_4 değişkeninin 1 olmasını zorunlu kılar (1≤x41 \leq x_4). x3x_3 seçilmezse (x3=0x_3=0), x4x_4 serbest kalır (0 veya 1).
3
n proje arasından en fazla k tanesinin seçimi kısıtını yazma
x3+x4+x5≤2x_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 xA→xBx_A \rightarrow x_B koşulu varsa, xAx_A seçildiğinde xBx_B de 1 olmaya zorlanmalıdır. Bu xA≤xBx_A \leq x_B ile sağlanır.

Daha Fazla Pratik

Karşılıklı bağımlı projeler için xA=xBx_A = x_B kısıtının nasıl kullanıldığını inceleyebilirsiniz.
Tahmini Süre:1m 30s
Bu soruyu puanla

Konular

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

Bu konudan daha fazla soru