Examkin

Soru

Zorluk: OrtaKesme Düzlemi (Gomory) Algoritması

Bir tam sayılı programlama modelinin doğrusal gevşetmesi (LP relaxation) çözüldüğünde elde edilen optimal simpleks tablosu aşağıda verilmiştir:

Temel Değişkenx1x_1x2x_2s1s_1s2s_2Çözüm (RHS)
ZZ001/21/25/65/61515
x1x_1102/32/3−1/6-1/67/27/2
x2x_2011/61/61/31/35/25/2

Modele tam sayı kısıtı eklendiğinde, Gomory kesme düzlemi algoritmasına göre x1x_1 temel değişkeninin bulunduğu satırdan elde edilecek olan kesme kısıtı aşağıdakilerden hangisidir?

  1. −23s1−56s2+Sg=−12-\frac{2}{3} s_1 - \frac{5}{6} s_2 + S_g = -\frac{1}{2}Cevap
  2. B
    −23s1+16s2+Sg=−12-\frac{2}{3} s_1 + \frac{1}{6} s_2 + S_g = -\frac{1}{2}
  3. C
    −23s1−56s2+Sg=12-\frac{2}{3} s_1 - \frac{5}{6} s_2 + S_g = \frac{1}{2}
  4. D
    13s1+16s2+Sg=−12\frac{1}{3} s_1 + \frac{1}{6} s_2 + S_g = -\frac{1}{2}
  5. E
    −23s1−56s2+Sg=−72-\frac{2}{3} s_1 - \frac{5}{6} s_2 + S_g = -\frac{7}{2}

Cevap

Kesme kısıtı, x1x_1 satırındaki katsayıların ve çözüm değerinin pozitif kesirsel kısımları kullanılarak −23s1−56s2+Sg=−12-\frac{2}{3} s_1 - \frac{5}{6} s_2 + S_g = -\frac{1}{2} şeklinde oluşturulur.
Doğru cevap, x1x_1 satırındaki tüm katsayıların ve çözüm değerinin kesirsel kısımlarını doğru hesaplayan seçenektir. x1+23s1−16s2=72x_1 + \frac{2}{3} s_1 - \frac{1}{6} s_2 = \frac{7}{2} denkleminde, kesirsel kısımlar şöyledir: Çözüm için 3.5−3=0.53.5 - 3 = 0.5, s1s_1 için 23−0=23\frac{2}{3} - 0 = \frac{2}{3}, s2s_2 için −16−(−1)=56-\frac{1}{6} - (-1) = \frac{5}{6}. Bu değerler ∑fijxj≥fi\sum f_{ij} x_j \geq f_i formülüne yerleştirilip tablo formuna çevrildiğinde −23s1−56s2+Sg=−12-\frac{2}{3} s_1 - \frac{5}{6} s_2 + S_g = -\frac{1}{2} sonucuna ulaşılır.

Adım Adım Çözüm

1
x1x_1 temel değişkenine ait satır denklemini yazınız.
x1+23s1−16s2=72x_1 + \frac{2}{3} s_1 - \frac{1}{6} s_2 = \frac{7}{2}
Kesme kısıtı oluşturulacak temel satırı belirlemek gerekir.
2
Katsayıların ve çözüm değerinin kesirsel kısımlarını (fi=ai−⌊ai⌋f_i = a_i - \lfloor a_i \rfloor) hesaplayınız.
RHS: 72−3=12\frac{7}{2} - 3 = \frac{1}{2} ; s1s_1: 23−0=23\frac{2}{3} - 0 = \frac{2}{3} ; s2s_2: −16−(−1)=56-\frac{1}{6} - (-1) = \frac{5}{6}
Gomory algoritmasında her katsayı kendisinden küçük veya eşit olan en büyük tam sayıdan çıkarılarak pozitif kesirsel kısmı bulunur.
3
Bulunan değerleri ∑fijxj≥fi\sum f_{ij} x_{j} \geq f_{i} eşitsizliğine yerleştiriniz.
23s1+56s2≥12\frac{2}{3} s_1 + \frac{5}{6} s_2 \geq \frac{1}{2}
Kesme kısıtının temel eşitsizlik formu budur.
4
Eşitsizliği simpleks tablosuna eklenecek standart eşitlik formuna (SgS_g gevşek değişkeni ile) dönüştürünüz.
−23s1−56s2+Sg=−12-\frac{2}{3} s_1 - \frac{5}{6} s_2 + S_g = -\frac{1}{2}
Dual simpleks yöntemiyle çözüme devam edebilmek için kısıt bu formda yazılmalıdır.

Anahtar Kavram

Gomory Kesme Düzlemi Algoritması'nda kesme kısıtı, temel olmayan değişkenlerin katsayılarının ve çözüm değerinin kesirsel kısımları kullanılarak oluşturulur; negatif katsayıların kesirsel kısmı a−⌊a⌋a - \lfloor a \rfloor formülüyle her zaman pozitife dönüştürülür.

Daha Fazla Pratik

Bundan sonraki adımda, eklenen bu kısıt ile dual simpleks yöntemini uygulayarak yeni bir pivot işlemi yapılması beklenebilir.
Tahmini Süre:2m 0s
Bu soruyu puanla

Konular

Kesme Düzlemi (Gomory) Algoritması

Bu konudan daha fazla soru