Examkin

Soru

Zorluk: Çok zorKesme Düzlemi (Gomory) Algoritması

Maksimizasyon amaçlı saf tam sayılı bir doğrusal programlama probleminin doğrusal gevşetilmesi (LP relaxation) simpleks yöntemiyle çözülmüş ve optimal tabloya ulaşılmıştır. Bu tabloda amaç fonksiyonu satırı (ZZ) ile x2x_2 temel değişkenine ait satır denklemleri aşağıda verilmiştir:

Z+3x3+4x4=40Z + 3x_3 + 4x_4 = 40
x2−35x3+74x4=133x_2 - \frac{3}{5}x_3 + \frac{7}{4}x_4 = \frac{13}{3}

(Burada x3x_3 ve x4x_4 temel olmayan değişkenlerdir.)

Bu probleme x2x_2 satırı temel alınarak bir Kesme Düzlemi (Gomory) kısıtı (sgs_g aylak değişkeni ile) üretilip optimal tabloya eklenmiştir.

Buna göre, yeni kısıt eklendikten sonra optimalliği yeniden sağlamak için uygulanacak dual simpleks algoritmasının ilk adımında, temelden çıkacak ve temele girecek değişkenler sırasıyla aşağıdakilerden hangisidir?

  1. Temelden çıkacak: sgs_g, Temele girecek: x4x_4Cevap
  2. B
    Temelden çıkacak: sgs_g, Temele girecek: x3x_3
  3. C
    Temelden çıkacak: x2x_2, Temele girecek: x4x_4
  4. D
    Temelden çıkacak: x2x_2, Temele girecek: x3x_3
  5. E
    Yeni kısıt eklendiğinde tablo primal olarak uygun kaldığından dual simpleks uygulanmaz, çözüm tamamlanmıştır.

Cevap

Temelden çıkacak olan değişken sgs_g, temele girecek olan değişken ise x4x_4'tür.
Kesme düzlemi (Gomory) algoritmasında, aija_{ij} katsayılarının kesirsel kısımları fij=aij−⌊aij⌋f_{ij} = a_{ij} - \lfloor a_{ij} \rfloor ile hesaplanır. 13/313/3'ün kesri 1/31/3; −3/5-3/5'in kesri 2/52/5 ve 7/47/4'ün kesri 3/43/4'tür. Oluşturulan kısıt sg−25x3−34x4=−13s_g - \frac{2}{5}x_3 - \frac{3}{4}x_4 = -\frac{1}{3} şeklindedir. Sağ tarafı negatif olan sgs_g temelden çıkar. Giren değişken ise ZZ satırı katsayıları ile kesme düzleminin negatif katsayıları arasındaki oran testinden (min⁡(3/0.4,4/0.75)=min⁡(7.5,5.33)\min(3/0.4, 4/0.75) = \min(7.5, 5.33)) minimum değeri veren x4x_4'tür.

Adım Adım Çözüm

1
x2x_2 satırındaki sabit değerin ve değişken katsayılarının kesirsel kısımlarını (ff) hesaplayın.
Sabit değer 13/313/3: 13/3=4+1/3  ⟹  f0=1/313/3 = 4 + 1/3 \implies f_0 = 1/3
x3x_3 katsayısı −3/5-3/5: ⌊−3/5⌋=−1  ⟹  f3=−3/5−(−1)=2/5\lfloor -3/5 \rfloor = -1 \implies f_3 = -3/5 - (-1) = 2/5
x4x_4 katsayısı 7/47/4: ⌊7/4⌋=1  ⟹  f4=7/4−1=3/4\lfloor 7/4 \rfloor = 1 \implies f_4 = 7/4 - 1 = 3/4
Gomory kesme düzlemi oluşturulurken, katsayıların formülü aij=⌊aij⌋+fija_{ij} = \lfloor a_{ij} \rfloor + f_{ij} şeklindedir. Negatif katsayıların kesirsel kısımları bulunurken alt tamsayıya yuvarlama kuralına dikkat edilmelidir.
2
Kesme düzlemi kısıtını oluşturun ve sgs_g aylak değişkenini ekleyerek tablo formatına getirin.
Gomory kısıtı formülü: ∑fijxj≥f0\sum f_{ij} x_j \ge f_0
25x3+34x4≥13\frac{2}{5}x_3 + \frac{3}{4}x_4 \ge \frac{1}{3}
Bunu ≤\le formatına çevirip aylak değişken (sgs_g) eklersek:
−25x3−34x4+sg=−13-\frac{2}{5}x_3 - \frac{3}{4}x_4 + s_g = -\frac{1}{3}
Simpleks tablosuna eklenebilmesi için eşitsizliğin denklem haline getirilmesi ve bir temel değişken (sgs_g) barındırması gerekir.
3
Dual simpleks yöntemiyle temelden çıkacak değişkeni belirleyin.
Temelden çıkacak değişken sgs_g'dir.
Yeni kısıt eklendiğinde sgs_g değişkeninin çözüm değeri −1/3-1/3 olmuştur. Dual simplekste sağ taraf sabiti en negatif olan temel değişken, çözümden çıkarılır.
4
Dual simpleks oran testini uygulayarak temele girecek değişkeni belirleyin.
Oranlar min⁡{cj∣agj∣}\min \{ \frac{c_j}{|a_{gj}|} \} formülüyle (agj<0a_{gj} < 0 için) hesaplanır.
x3x_3 için oran: 3∣−2/5∣=30.4=7.5\frac{3}{|-2/5|} = \frac{3}{0.4} = 7.5
x4x_4 için oran: 4∣−3/4∣=40.75=5.33\frac{4}{|-3/4|} = \frac{4}{0.75} = 5.33
Minimum oran x4x_4'e (5.335.33) aittir.
Dual simpleks yönteminde, amaç fonksiyonundaki optimalliğin bozulmaması için Z satırı katsayılarının, temelden çıkacak satırdaki negatif katsayıların mutlak değerlerine oranı hesaplanır ve en küçük oranı veren değişken temele sokulur.

Anahtar Kavram

Gomory Kesme Düzlemi Üretimi ve Dual Simpleks Algoritması
Bu soruyu puanla

Konular

Kesme Düzlemi (Gomory) Algoritması

Bu konudan daha fazla soru