Examkin

Question

Difficulty: MediumKesme Düzlemi (Gomory) Algoritması

Doğrusal gevşetmesi (LP relaxation) çözülmüş olan bir tam sayılı programlama modelinin optimal simpleks tablosundan alınan ve x2x_2 temel değişkenine ait olan satır denklemi aşağıda verilmiştir:

x2+23x3−34x4=75x_2 + \frac{2}{3}x_3 - \frac{3}{4}x_4 = \frac{7}{5}

Bu denklemde x3x_3 ve x4x_4 temel dışı değişkenlerdir. Problemin saf tam sayılı bir model olduğu bilindiğine göre, bu satırdan elde edilecek olan Gomory kısıtı (kesmesi) aşağıdakilerden hangisidir? (sgs_g: Gomory aylak değişkeni)

  1. sg−23x3−14x4=−25s_g - \frac{2}{3}x_3 - \frac{1}{4}x_4 = -\frac{2}{5}Answer
  2. B
    sg−23x3+34x4=−25s_g - \frac{2}{3}x_3 + \frac{3}{4}x_4 = -\frac{2}{5}
  3. C
    sg−23x3−14x4=−35s_g - \frac{2}{3}x_3 - \frac{1}{4}x_4 = -\frac{3}{5}
  4. D
    sg−23x3−34x4=−25s_g - \frac{2}{3}x_3 - \frac{3}{4}x_4 = -\frac{2}{5}
  5. E
    sg+23x3+14x4=−25s_g + \frac{2}{3}x_3 + \frac{1}{4}x_4 = -\frac{2}{5}

Answer

Gomory kısıtı sg−23x3−14x4=−25s_g - \frac{2}{3}x_3 - \frac{1}{4}x_4 = -\frac{2}{5} şeklindedir.
Denklemin sağ tarafındaki 7/57/5 değerinin kesirsel kısmı 2/52/5 olup kısıtın sağ tarafı −2/5-2/5 olmalıdır. Temel olmayan değişkenlerden x3x_3'ün katsayısı 2/32/3 pozitif olduğu için kesirsel kısmı doğrudan 2/32/3 olur. x4x_4'ün katsayısı −3/4-3/4 negatif olduğu için kesirsel kısmı −3/4−(−1)=1/4-3/4 - (-1) = 1/4 olarak hesaplanır. Formüle yerleştirildiğinde doğru kısıt elde edilir.

Step-by-Step Solution

1
Satır denklemindeki katsayıları ve sağ taraf değerini belirleyin.
a23=23a_{23} = \frac{2}{3}, a24=−34a_{24} = -\frac{3}{4}, b2=75b_2 = \frac{7}{5}
Kesirsel kısımların hesaplanması için temel olmayan değişkenlerin katsayıları ve RHS değeri gereklidir.
2
Her bir değerin kesirsel kısmını (f=a−⌊a⌋f = a - \lfloor a \rfloor) hesaplayın.
f20=75−⌊75⌋=1.4−1=0.4=25f_{20} = \frac{7}{5} - \lfloor \frac{7}{5} \rfloor = 1.4 - 1 = 0.4 = \frac{2}{5}; f23=23−⌊23⌋=23−0=23f_{23} = \frac{2}{3} - \lfloor \frac{2}{3} \rfloor = \frac{2}{3} - 0 = \frac{2}{3}; f24=−34−⌊−34⌋=−0.75−(−1)=0.25=14f_{24} = -\frac{3}{4} - \lfloor -\frac{3}{4} \rfloor = -0.75 - (-1) = 0.25 = \frac{1}{4}
Gomory algoritmasında negatif katsayılar için kesirsel kısım, sayının kendisinden kendisinden küçük en büyük tam sayının çıkarılmasıyla bulunur.
3
Bulunan değerleri sg−∑fijxj=−fi0s_g - \sum f_{ij}x_j = -f_{i0} formülünde yerine koyun.
sg−(23)x3−(14)x4=−25s_g - (\frac{2}{3})x_3 - (\frac{1}{4})x_4 = -\frac{2}{5}
Bu formül, tamsayılı olmayan çözümü eleyen ve uygun tamsayılı bölgeyi daraltan yeni bir kısıt oluşturur.

Key Concept

Gomory kesme düzlemi oluşturulurken, katsayıların kesirsel kısımları her zaman negatif olmayan (0≤f<10 \leq f < 1) değerler olmalıdır. Özellikle negatif katsayılarda f=a−floor(a)f = a - \text{floor}(a) kuralına dikkat edilmelidir.
Rate this question

Topics

Kesme Düzlemi (Gomory) Algoritması

More questions from this topic