Examkin

Soru

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

Bir kamu kurumu, tesis güvenliğini artırmak amacıyla 4 farklı elektronik güvenlik sistemi (x1,x2,x3,x4x_1, x_2, x_3, x_4) yatırımını değerlendirmektedir. Değerlendirme komisyonu, bütçe ve uyumluluk kriterleri doğrultusunda yatırımlarla ilgili şu kuralı belirlemiştir:

'Eğer 1. sistem (x1x_1) kurulursa, 2. sistem (x2x_2) ve 3. sistemden (x3x_3) en fazla biri kurulabilir. Ancak 1. sistem kurulmazsa, 2. ve 3. sistemlerin kurulumunda herhangi bir kısıtlama aranmayacaktır.'

Sistemlerin kurulması durumunda karar değişkenleri 1, aksi halde 0 değerini almaktadır.

Buna göre, komisyonun belirlediği bu koşulu sağlayan matematiksel model kısıtı aşağıdakilerden hangisidir?

  1. x1+x2+x3≤2x_1 + x_2 + x_3 \leq 2Cevap
  2. B
    x1+x2+x3≤1x_1 + x_2 + x_3 \leq 1
  3. C
    x2+x3≤x1x_2 + x_3 \leq x_1
  4. D
    x1≤x2+x3x_1 \leq x_2 + x_3
  5. E
    x1+x2+x3≥2x_1 + x_2 + x_3 \geq 2

Cevap

Komisyonun belirlediği koşulu sağlayan model kısıtı x1+x2+x3≤2x_1 + x_2 + x_3 \leq 2'dir.
Verilen mantıksal yapı bir 'eğer-ise' koşuludur. Modelin, x1=1x_1=1 olduğunda x2+x3≤1x_2+x_3 \leq 1 sonucunu, x1=0x_1=0 olduğunda ise x2+x3≤2x_2+x_3 \leq 2 (yani hiçbir kısıtlayıcılığı olmayan, serbest) sonucunu vermesi gerekir. Doğru seçenek incelendiğinde; x1=1x_1=1 konulduğunda 1+x2+x3≤2⇒x2+x3≤11 + x_2 + x_3 \leq 2 \Rightarrow x_2 + x_3 \leq 1 eşitsizliğine dönüşerek koşulu tam olarak sağlar. x1=0x_1=0 konulduğunda ise 0+x2+x3≤2⇒x2+x3≤20 + x_2 + x_3 \leq 2 \Rightarrow x_2 + x_3 \leq 2 olur, 0-1 değişkenlerin toplamı zaten en fazla 2 olabileceği için sistemi hiçbir şekilde kısıtlamaz. Dolayısıyla mantıksal koşulu kusursuz olarak temsil eden eşitsizlik budur.

Adım Adım Çözüm

1
Mantıksal koşulu matematiksel eşitsizliğe çevirmek için durum analizi yapın.
1. Durum: x1=1x_1 = 1 ise x2+x3≤1x_2 + x_3 \leq 1 olmalıdır. 2. Durum: x1=0x_1 = 0 ise x2+x3≤2x_2 + x_3 \leq 2 olmalıdır (iki değişkenin toplamı en fazla 2 olabileceği için kısıtlama yoktur).
Sıfır-bir tamsayılı programlamada 'eğer-ise' (if-then) yapılarının alabileceği tüm olası durumları belirlemek, doğru denklemi kurmanın ilk adımıdır.
2
Bu iki durumu tek bir kısıt altında birleştirmek için Büyük-M (Big-M) tekniği mantığını kullanın.
x2+x3≤1+M(1−x1)x_2 + x_3 \leq 1 + M(1 - x_1) denklemini kurun.
Koşullu kısıtlarda sağ taraf sabiti, koşulun gerçekleşip gerçekleşmemesine göre esneklik kazanmalıdır. 1−x11-x_1 ifadesi, x1=1x_1=1 olduğunda 0, x1=0x_1=0 olduğunda 1 değerini üreterek anahtarlama görevi görür.
3
MM değerini belirleyerek denklemi sadeleştirin.
x1=0x_1 = 0 iken kısıtın x2+x3≤1+Mx_2 + x_3 \leq 1 + M olması ve x2+x3x_2 + x_3'ün alabileceği maksimum değerin 2 olması nedeniyle 1+M≥21 + M \geq 2, yani en dar sınırla M=1M=1 seçilir. Denklem x2+x3≤1+1(1−x1)⇒x2+x3≤2−x1⇒x1+x2+x3≤2x_2 + x_3 \leq 1 + 1(1 - x_1) \Rightarrow x_2 + x_3 \leq 2 - x_1 \Rightarrow x_1 + x_2 + x_3 \leq 2 olarak elde edilir.
M değeri kısıtı geçersiz kılacak kadar büyük, ancak çözüm uzayını gereksiz genişletmeyecek kadar küçük (sıkı) seçilmelidir.

Anahtar Kavram

Sıfır-Bir (0-1) Tamsayılı Programlamada Mantıksal Kısıtların Modellenmesi
Tahmini Süre:1m 15s
Bu soruyu puanla

Konular

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

Bu konudan daha fazla soru