Examkin

Soru

Zorluk: OrtaKesme Düzlemi (Gomory) Algoritması

Saf tam sayılı bir doğrusal programlama probleminin doğrusal gevşetilmesi (LP relaxation) simpleks yöntemi ile çözülmüş ve elde edilen optimal simpleks tablosunda x1x_1 temel değişkenine ait satır şu şekilde belirlenmiştir:

Temel Değişkenx1x_1x2x_2s1s_1s2s_2Sağ Taraf
x1x_11073\frac{7}{3}−56-\frac{5}{6}134\frac{13}{4}

Burada s1s_1 ve s2s_2 aylak değişkenleri temsil etmektedir. Gomory kesme düzlemi algoritması uyarınca, bu satırdan türetilecek olan yeni kesme kısıtı (Gomory kesiği) aşağıdakilerden hangisidir? (sgs_g yeni eklenen kesme değişkenidir.)

  1. sg−13s1−16s2=−14s_g - \frac{1}{3}s_1 - \frac{1}{6}s_2 = -\frac{1}{4}Cevap
  2. B
    sg−13s1+56s2=−14s_g - \frac{1}{3}s_1 + \frac{5}{6}s_2 = -\frac{1}{4}
  3. C
    sg−13s1−16s2=14s_g - \frac{1}{3}s_1 - \frac{1}{6}s_2 = \frac{1}{4}
  4. D
    sg+13s1+16s2=−14s_g + \frac{1}{3}s_1 + \frac{1}{6}s_2 = -\frac{1}{4}
  5. E
    sg−23s1−56s2=−34s_g - \frac{2}{3}s_1 - \frac{5}{6}s_2 = -\frac{3}{4}

Cevap

Gomory kesme kısıtı denklemi sg−13s1−16s2=−14s_g - \frac{1}{3}s_1 - \frac{1}{6}s_2 = -\frac{1}{4} şeklindedir.
Gomory kesme kısıtı oluşturulurken satırdaki her bir katsayı aij=⌊aij⌋+fija_{ij} = \lfloor a_{ij} \rfloor + f_{ij} şeklinde ayrıştırılır. Burada 0≤fij<10 \leq f_{ij} < 1 olmalıdır. Verilen satırda 73=2+13\frac{7}{3} = 2 + \frac{1}{3} olduğundan f11=13f_{11} = \frac{1}{3}; −56=−1+16-\frac{5}{6} = -1 + \frac{1}{6} olduğundan f12=16f_{12} = \frac{1}{6} ve sağ taraf 134=3+14\frac{13}{4} = 3 + \frac{1}{4} olduğundan fi0=14f_{i0} = \frac{1}{4} bulunur. Gomory kısıtı sg−∑fijxj=−fi0s_g - \sum f_{ij}x_j = -f_{i0} formülüyle yazıldığında sg−13s1−16s2=−14s_g - \frac{1}{3}s_1 - \frac{1}{6}s_2 = -\frac{1}{4} denklemi elde edilir.

Adım Adım Çözüm

1
Optimal tablodaki satırın katsayılarını tam sayı ve pozitif kesirli kısımlarına ayrıştırın.
x1+(2+13)s1+(−1+16)s2=3+14x_1 + (2 + \frac{1}{3})s_1 + (-1 + \frac{1}{6})s_2 = 3 + \frac{1}{4}
Gomory kesiği oluşturulurken her bir katsayının a=⌊a⌋+fa = \lfloor a \rfloor + f formuna (burada 0≤f<10 \leq f < 1) getirilmesi gerekir.
2
Katsayıların ve sağ tarafın kesirli kısımlarını (ff) belirleyin.
fs1=13f_{s1} = \frac{1}{3}, fs2=16f_{s2} = \frac{1}{6}, fRHS=14f_{RHS} = \frac{1}{4}
Kesirli kısımlar kısıtın katsayılarını oluşturur. Negatif katsayılar için: −56=−1+16-\frac{5}{6} = -1 + \frac{1}{6} olduğundan kesirli kısım 16\frac{1}{6}'dır.
3
sg−∑fijxj=−fi0s_g - \sum f_{ij}x_j = -f_{i0} formülünü uygulayın.
sg−13s1−16s2=−14s_g - \frac{1}{3}s_1 - \frac{1}{6}s_2 = -\frac{1}{4}
Bu formül, tam sayı olmayan çözümün dışlanmasını sağlayan en sıkı doğrusal kesiği üretir.

Anahtar Kavram

Gomory kesme düzlemi algoritmasında, bir satırdan kısıt üretilirken katsayıların 'en küçük pozitif kesirli kısımları' (proper fractional parts) kullanılır.
Bu soruyu puanla

Konular

Kesme Düzlemi (Gomory) Algoritması

Bu konudan daha fazla soru