Examkin

Question

Difficulty: MediumKesme 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}Answer
  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}

Answer

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.

Step-by-Step Solution

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.

Key Concept

Gomory Kesme Düzlemi Oluşturma

Alternative Method

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.
Estimated Time:1m 30s
Rate this question

Topics

Kesme Düzlemi (Gomory) Algoritması

More questions from this topic