Examkin

Soru

Zorluk: ZorSaf Tamsayılı Programlama Modelleri

Bir kamu kurumu, personel atama ve araç tahsis süreçlerini optimize etmek amacıyla saf tamsayılı bir doğrusal programlama modeli kurmuştur. Modelin doğrusal programlama gevşetmesi (LP relaxation) çözüldükten sonra elde edilen nihai simpleks tablosunda, tamsayı değer alması gereken temel değişkenlerden x2x_2'ye ait satır denklemi aşağıda verilmiştir:

x2+25x4−56x5+94x6=235x_2 + \frac{2}{5}x_4 - \frac{5}{6}x_5 + \frac{9}{4}x_6 = \frac{23}{5}

Gomory kesirli kesme (fractional cut) algoritması kullanılarak, bu optimal tablodaki kesirli çözümü ortadan kaldırmak için yeni bir kısıt (kesme düzlemi) üretilecektir.

Buna göre, modele eklenmesi gereken geçerli kesme kısıtı aşağıdakilerden hangisidir?

  1. 25x4+16x5+14x6≥35\frac{2}{5}x_4 + \frac{1}{6}x_5 + \frac{1}{4}x_6 \geq \frac{3}{5}Cevap
  2. B
    25x4+56x5+14x6≥35\frac{2}{5}x_4 + \frac{5}{6}x_5 + \frac{1}{4}x_6 \geq \frac{3}{5}
  3. C
    25x4−56x5+94x6≥35\frac{2}{5}x_4 - \frac{5}{6}x_5 + \frac{9}{4}x_6 \geq \frac{3}{5}
  4. D
    25x4+16x5+14x6≤35\frac{2}{5}x_4 + \frac{1}{6}x_5 + \frac{1}{4}x_6 \leq \frac{3}{5}
  5. E
    25x4+16x5+14x6≥25\frac{2}{5}x_4 + \frac{1}{6}x_5 + \frac{1}{4}x_6 \geq \frac{2}{5}

Cevap

Modelden elde edilecek doğru Gomory kesme kısıtı 25x4+16x5+14x6≥35\frac{2}{5}x_4 + \frac{1}{6}x_5 + \frac{1}{4}x_6 \geq \frac{3}{5} olmalıdır.
Gomory kesirli kesme (fractional cut) algoritmasında, her katsayı aij=⌊aij⌋+fija_{ij} = \lfloor a_{ij} \rfloor + f_{ij} kuralıyla kendisinden küçük en büyük tamsayı (floor) ve pozitif kesirli kısmına (fijf_{ij}) ayrılır. Kesme kısıtı ∑fijxj≥fi\sum f_{ij} x_j \geq f_i temel formülü ile oluşturulur. Denklemdeki x4x_4 katsayısının kesirli kısmı 25\frac{2}{5}'tir. Negatif olan x5x_5 katsayısı −56-\frac{5}{6} için; ⌊−56⌋=−1\lfloor -\frac{5}{6} \rfloor = -1 işlemiyle kesirli kısım −56−(−1)=16-\frac{5}{6} - (-1) = \frac{1}{6} bulunur. x6x_6 katsayısı 94=2+14\frac{9}{4} = 2 + \frac{1}{4} olduğundan kesirli kısmı 14\frac{1}{4}'tür. Eşitliğin sağ tarafı 235=4+35\frac{23}{5} = 4 + \frac{3}{5} yapılarak fi=35f_i = \frac{3}{5} olarak belirlenir. Tüm kesirli bileşenler ∑fijxj≥fi\sum f_{ij} x_j \geq f_i denklemine yerleştirildiğinde doğru kısıt 25x4+16x5+14x6≥35\frac{2}{5}x_4 + \frac{1}{6}x_5 + \frac{1}{4}x_6 \geq \frac{3}{5} olarak çıkar.

Adım Adım Çözüm

1
Kesme düzleminde kullanılmak üzere denklemdeki her bir değişkenin katsayısının pozitif kesirli kısmını (fijf_{ij}) belirleme
x4x_4 katsayısı 25\frac{2}{5} için f4=25f_4 = \frac{2}{5}, x5x_5 katsayısı −56-\frac{5}{6} için ⌊−56⌋=−1\lfloor -\frac{5}{6} \rfloor = -1 olduğundan f5=−56−(−1)=16f_5 = -\frac{5}{6} - (-1) = \frac{1}{6}, x6x_6 katsayısı 94\frac{9}{4} için ⌊94⌋=2\lfloor \frac{9}{4} \rfloor = 2 olduğundan f6=94−2=14f_6 = \frac{9}{4} - 2 = \frac{1}{4} olarak hesaplanır.
Gomory algoritması, değişkenlerin katsayılarını en büyük alt tamsayı ile arasındaki pozitif farka (aij=⌊aij⌋+fija_{ij} = \lfloor a_{ij} \rfloor + f_{ij}) ayırarak yeni bir kısıt üretir.
2
Eşitliğin sağ tarafındaki sabit değerin pozitif kesirli kısmını (fif_i) belirleme
Sağ taraf değeri 235=4.6\frac{23}{5} = 4.6 olduğundan ⌊4.6⌋=4\lfloor 4.6 \rfloor = 4 bulunur ve kesirli kısım fi=235−4=35f_i = \frac{23}{5} - 4 = \frac{3}{5} olarak elde edilir.
Kesme kısıtının sağ tarafı (RHS), optimal simpleks tablosundaki mevcut çözüm değerinin kesirli kısmından oluşturulmalıdır.
3
Gomory kesirli kesme kısıtı formülünü (∑fijxj≥fi\sum f_{ij} x_j \geq f_i) uygulama
Bulunan fijf_{ij} ve fif_i değerleri formüle yerleştirildiğinde 25x4+16x5+14x6≥35\frac{2}{5}x_4 + \frac{1}{6}x_5 + \frac{1}{4}x_6 \geq \frac{3}{5} kısıtı türetilir.
Bu eşitsizlik, mevcut LP gevşetmesinin optimal çözüm alanını daraltırken tamsayılı uygun çözüm bölgesini tamamen koruyan geçerli bir kesme düzlemidir.

Anahtar Kavram

Gomory Kesirli Kesme Algoritması
Tahmini Süre:2m 0s
Bu soruyu puanla

Konular

Saf Tamsayılı Programlama Modelleri

Bu konudan daha fazla soru