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 optimal simpleks tablosunda tam sayı değer alması gereken x2x_2 temel değişkenine ait satır aşağıdaki gibi elde edilmiştir:

x2+74s1−13s2=115x_2 + \frac{7}{4}s_1 - \frac{1}{3}s_2 = \frac{11}{5}

Buna göre, Gomory kesme düzlemi algoritması kullanılarak bu satırdan türetilecek olan yeni kısıt (kesme düzlemi) denklemi aşağıdakilerden hangisidir?

  1. sg−34s1−23s2=−15s_g - \frac{3}{4}s_1 - \frac{2}{3}s_2 = -\frac{1}{5}Cevap
  2. B
    sg−34s1−13s2=−15s_g - \frac{3}{4}s_1 - \frac{1}{3}s_2 = -\frac{1}{5}
  3. C
    sg−34s1−23s2=15s_g - \frac{3}{4}s_1 - \frac{2}{3}s_2 = \frac{1}{5}
  4. D
    sg−14s1−23s2=−15s_g - \frac{1}{4}s_1 - \frac{2}{3}s_2 = -\frac{1}{5}
  5. E
    sg−74s1+13s2=−115s_g - \frac{7}{4}s_1 + \frac{1}{3}s_2 = -\frac{11}{5}

Cevap

Doğru cevap sg−34s1−23s2=−15s_g - \frac{3}{4}s_1 - \frac{2}{3}s_2 = -\frac{1}{5} denklemi ile verilen seçenektir.
Kesme düzlemi oluşturulurken satırdaki her bir katsayının tam sayı kısmından sonra gelen pozitif kesirsel kısmı alınır. 11/511/5 için 1/51/5, 7/47/4 için 3/43/4 ve −1/3-1/3 için (−1+2/3-1 + 2/3 olduğu için) 2/32/3 değerleri doğru şekilde seçilip sg−(kesirsel katsayılar)=−(sag˘ taraf kesri)s_g - (\text{kesirsel katsayılar}) = -(\text{sağ taraf kesri}) kalıbına yerleştirildiğinde doğru sonuca ulaşılır.

Adım Adım Çözüm

1
Katsayıların ve sağ taraf değerinin kesirsel kısımlarını (fijf_{ij}) belirleyin.
115=2+15→f20=15\frac{11}{5} = 2 + \frac{1}{5} \rightarrow f_{20} = \frac{1}{5}; 74=1+34→f21=34\frac{7}{4} = 1 + \frac{3}{4} \rightarrow f_{21} = \frac{3}{4}.
Gomory kısıtı sadece katsayıların pozitif kesirsel kısımları üzerinden kurulur.
2
Negatif katsayının kesirsel kısmını 0≤f<10 \leq f < 1 olacak şekilde hesaplayın.
−13=−1+23→f22=23-\frac{1}{3} = -1 + \frac{2}{3} \rightarrow f_{22} = \frac{2}{3}.
Negatif sayıların kesirsel kısmı, kendisinden küçük olan en yakın tam sayıdan farkı alınarak bulunur.
3
Kesme düzlemi denklemini sg−∑fijxj=−fi0s_g - \sum f_{ij} x_j = -f_{i0} formunda yazın.
sg−34s1−23s2=−15s_g - \frac{3}{4}s_1 - \frac{2}{3}s_2 = -\frac{1}{5}
Yeni eklenen aylak değişken (sgs_g) ile kısıt denkleme dönüştürülür.

Anahtar Kavram

Gomory Kesme Düzlemi kısıtı, optimal tablodaki tamsayı olmayan bir satırın tüm katsayılarının pozitif kesirsel kısımları (fijf_{ij}) kullanılarak ∑fijxj≥fi0\sum f_{ij} x_j \geq f_{i0} şeklinde oluşturulur.
Tahmini Süre:1m 30s
Bu soruyu puanla

Konular

Kesme Düzlemi (Gomory) Algoritması

Bu konudan daha fazla soru