Examkin

Soru

Zorluk: Çok zorSıfır-Bir (0-1) Tamsayılı Programlama Modelleri

Sanayi ve Teknoloji Bakanlığı, bölgesel teşvik programı kapsamında 5 farklı ihtisas organize sanayi bölgesi (OSB) projesini (x1,x2,x3,x4,x5x_1, x_2, x_3, x_4, x_5) değerlendirmektedir. Her bir xix_i karar değişkeni, ii. projenin yatırım programına alınması durumunda 11, aksi halde 00 değerini almaktadır.

Bölgesel kalkınma dengelerini gözetmekle görevli planlama komisyonu şu stratejik kuralı belirlemiştir:

'Kuzey bölgesinde planlanan 1, 2 ve 3 numaralı OSB projelerinden hiçbiri yatırım programına alınmazsa, Güney bölgesindeki 4 ve 5 numaralı OSB projelerinin her ikisinin de kesinlikle yatırım programına alınması zorunludur. Ancak Kuzey bölgesindeki projelerden en az biri onaylanırsa, Güney bölgesindeki projelerin seçimi tamamen serbest bırakılacaktır.'

Buna göre, komisyonun bu stratejik kararını tek başına ve eksiksiz olarak ifade eden en uygun sıfır-bir (0-1) tamsayılı programlama kısıtı aşağıdakilerden hangisidir?

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

Cevap

İstenen stratejik durumu sağlayan doğru eşitsizlik 2x1+2x2+2x3+x4+x5≥22x_1 + 2x_2 + 2x_3 + x_4 + x_5 \geq 2 kısıtıdır.
Mantıksal modellemelerde 'A durumu gerçekleşmezse B durumu olmalıdır' koşulu, değişkenler arasına cezalandırıcı (veya dengeleyici) bir katsayı eklenerek çözülür. Doğru kısıtta (2x1+2x2+2x3+x4+x5≥22x_1 + 2x_2 + 2x_3 + x_4 + x_5 \geq 2), Kuzey projelerinin toplamı 00 olduğunda eşitsizlik x4+x5≥2x_4 + x_5 \geq 2 halini alarak 44 ve 55 numaralı projeleri zorunlu kılar. Kuzey projelerinden herhangi biri 11 değerini aldığında ise sol taraftaki toplam en az 22 olacağından, x4x_4 ve x5x_5 değişkenleri sıfır dahi olsa eşitsizlik (2+0+0≥22+0+0 \geq 2) sağlanır ve böylece Güney projelerinin seçimi serbest kalmış olur.

Adım Adım Çözüm

1
Koşulun bağlayıcı olduğu durumu matematiksel olarak ifade et.
Kuzey projelerinden hiçbiri seçilmezse durumu: x1+x2+x3=0x_1 + x_2 + x_3 = 0.
Bu durumda Güney projelerinin ikisi de zorunludur: x4=1x_4 = 1 ve x5=1x_5 = 1, yani x4+x5≥2x_4 + x_5 \geq 2 olmalıdır.
2
Koşulun serbest bıraktığı durumu analiz et.
Kuzey projelerinden en az biri seçilirse durumu: x1+x2+x3≥1x_1 + x_2 + x_3 \geq 1.
Bu durumda x4x_4 ve x5x_5 için hiçbir kısıtlama (zorunluluk) olmamalıdır, yani eşitsizliğin sağladığı minimum değer x4+x5≥0x_4 + x_5 \geq 0 (veya daha küçük bir sayı) olmalıdır.
3
İki durumu tek bir 'Big-M' benzeri mantıksal eşitsizlikte birleştir.
Genel form: x4+x5≥2−M(x1+x2+x3)x_4 + x_5 \geq 2 - M(x_1 + x_2 + x_3).
Buradaki MM katsayısı, x1+x2+x3≥1x_1+x_2+x_3 \geq 1 olduğunda eşitsizliğin sağ tarafını 00 veya altına düşürecek kadar büyük olmalıdır.
4
En uygun MM katsayısını belirle ve denklemi düzenle.
M=2M=2 seçilirse: x4+x5≥2−2(x1+x2+x3)x_4 + x_5 \geq 2 - 2(x_1 + x_2 + x_3).
Terimleri aynı tarafa topladığımızda doğru kısıt olan 2x1+2x2+2x3+x4+x5≥22x_1 + 2x_2 + 2x_3 + x_4 + x_5 \geq 2 elde edilir.

Anahtar Kavram

Sıfır-Bir Tamsayılı Modellerde Şartlı (Mantıksal) Kısıtların Modellenmesi
Tahmini Süre:2m 0s
Bu soruyu puanla

Konular

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

Bu konudan daha fazla soru