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, tamsayı değer alması gereken x2x_2 temel değişkenine ait satır aşağıdaki gibi belirlenmiştir:

x2+56s1−13s2=176x_2 + \frac{5}{6}s_1 - \frac{1}{3}s_2 = \frac{17}{6}

Buna göre, Gomory kesme düzlemi algoritması kullanılarak bu satırdan türetilecek olan kesme kısıtı (Gomory kesisi) aşağıdakilerden hangisidir? (sgs_g, yeni eklenen aylak değişkendir.)

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

Cevap

Gomory kesme kısıtı denklemi sg−56s1−23s2=−56s_g - \frac{5}{6}s_1 - \frac{2}{3}s_2 = -\frac{5}{6} şeklindedir.
Verilen satırda sağ taraf sabiti olan 17/617/6 değerinin kesirsel kısmı 5/65/6, s1s_1 katsayısının kesirsel kısmı 5/65/6 ve −1/3-1/3 katsayısının kesirsel kısmı (−1+2/3-1 + 2/3 olduğu için) 2/32/3 olarak bulunur. Formülde yerine yazıldığında sg−56s1−23s2=−56s_g - \frac{5}{6}s_1 - \frac{2}{3}s_2 = -\frac{5}{6} ifadesine ulaşılır.

Adım Adım Çözüm

1
Temel değişken satırındaki tüm katsayıları ve sağ taraf sabitini tam ve kesirsel kısımlarına (0≤f<10 \leq f < 1) ayırın.
176=2+56⇒fi0=56\frac{17}{6} = 2 + \frac{5}{6} \Rightarrow f_{i0} = \frac{5}{6}
56=0+56⇒fs1=56\frac{5}{6} = 0 + \frac{5}{6} \Rightarrow f_{s1} = \frac{5}{6}
−13=−1+23⇒fs2=23-\frac{1}{3} = -1 + \frac{2}{3} \Rightarrow f_{s2} = \frac{2}{3}
Gomory algoritmasında kısıtlar sadece değişkenlerin kesirsel kısımları kullanılarak oluşturulur.
2
Gomory kesme kısıtı formülünü (sg−∑fijxj=−fi0s_g - \sum f_{ij}x_j = -f_{i0}) uygulayın.
sg−(56)s1−(23)s2=−56s_g - (\frac{5}{6})s_1 - (\frac{2}{3})s_2 = -\frac{5}{6}
Bu formül, tamsayı kısıtını sağlayan en sıkı doğrusal kesmeyi üretir.

Anahtar Kavram

Gomory kesme kısıtı oluşturulurken negatif katsayıların kesirsel kısımları, katsayıdan küçük veya eşit olan en büyük tamsayı çıkarılarak (f=a−⌊a⌋f = a - \lfloor a \rfloor) pozitif bir değer olarak hesaplanmalıdır.
Bu soruyu puanla

Konular

Kesme Düzlemi (Gomory) Algoritması

Bu konudan daha fazla soru