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 tablosuna ait bir satır aşağıda verilmiştir:

Temel Değişkenx1x_1x2x_2s1s_1s2s_2Sağ Taraf
x1x_1104/34/3−1/6-1/617/617/6

Buna göre, Gomory kesme düzlemi algoritması kullanılarak tam sayı çözümüne ulaşmak amacıyla modele eklenmesi gereken yeni kısıt denklemi aşağıdakilerden hangisidir?

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

Cevap

sg−13s1−56s2=−56s_g - \frac{1}{3}s_1 - \frac{5}{6}s_2 = -\frac{5}{6} denklemi doğrudur.
Verilen x1x_1 satır denkleminde sağ taraf değerinin (17/617/6) kesirsel kısmı 5/65/6, s1s_1 katsayısının (4/34/3) kesirsel kısmı 1/31/3 ve s2s_2 katsayısının (−1/6-1/6) kesirsel kısmı 5/65/6 olarak hesaplanır. Gomory kısıt denklemi standart olarak sg−∑fjxj=−f0s_g - \sum f_j x_j = -f_0 şeklinde yazıldığından, sg−13s1−56s2=−56s_g - \frac{1}{3}s_1 - \frac{5}{6}s_2 = -\frac{5}{6} ifadesi doğru sonuca ulaştırır.

Adım Adım Çözüm

1
Seçilen satırdaki katsayıların ve sağ taraf değerinin kesirsel kısımlarını (fjf_j) hesaplayın.
Sağ taraf (17/6=2+5/617/6 = 2 + 5/6) için f0=5/6f_0 = 5/6; s1s_1 katsayısı (4/3=1+1/34/3 = 1 + 1/3) için f1=1/3f_1 = 1/3; s2s_2 katsayısı (−1/6=−1+5/6-1/6 = -1 + 5/6) için f2=5/6f_2 = 5/6 bulunur.
Gomory kesme düzlemi, katsayıların tam sayı olmayan (kesirsel) kısımları üzerine inşa edilir.
2
Gomory kısıt denklemi formülünü (sg−∑fjxj=−f0s_g - \sum f_j x_j = -f_0) uygulayın.
sg−(1/3)s1−(5/6)s2=−5/6s_g - (1/3)s_1 - (5/6)s_2 = -5/6 denklemi elde edilir.
Bu kısıt, mevcut sürekli uygun çözüm alanını daraltırken hiçbir tam sayılı çözümü dışarıda bırakmaz.
3
Elde edilen denklemi seçeneklerle karşılaştırarak doğruluğunu teyit edin.
sg−13s1−56s2=−56s_g - \frac{1}{3}s_1 - \frac{5}{6}s_2 = -\frac{5}{6} sonucu doğrulanmıştır.
İşlem hatası yapılmadığından ve negatif katsayıların kesirsel kısımları doğru alındığından emin olunur.

Anahtar Kavram

Gomory Kesme Düzlemi Oluşturma

Alternatif Yöntem

Kısıtı oluştururken önce denklemi tam sayı ve kesirsel kısımlarına ayırıp (x1+(1+1/3)s1+(−1+5/6)s2=2+5/6x_1 + (1+1/3)s_1 + (-1+5/6)s_2 = 2 + 5/6), tam sayıları bir tarafa kesirleri diğer tarafa toplayarak da kontrol edebilirsiniz.
Tahmini Süre:1m 30s
Bu soruyu puanla

Konular

Kesme Düzlemi (Gomory) Algoritması

Bu konudan daha fazla soru