Examkin

Soru

Zorluk: OrtaKesme Düzlemi (Gomory) Algoritması

Bir tam sayılı programlama probleminin doğrusal gevşetilmesi (LP relaxation) sonucunda elde edilen optimal simpleks tablosunda x1x_1 temel değişkenine ait satır bilgisi aşağıda verilmiştir:

Temel Değişkenx1x_1x2x_2s1s_1s2s_2Çözüm (bb)
x1x_1103/23/2−2/3-2/35/25/2

Problemdeki tüm değişkenlerin tam sayı olması gerektiği bilindiğine göre, x1x_1 satırı kullanılarak oluşturulacak olan Gomory kesme düzlemi kısıtı aşağıdakilerden hangisidir?
(sgs_g: Kesme düzlemi için eklenen yeni aylak değişken)

  1. sg−12s1−13s2=−12s_g - \frac{1}{2} s_1 - \frac{1}{3} s_2 = -\frac{1}{2}Cevap
  2. B
    sg−12s1+23s2=−12s_g - \frac{1}{2} s_1 + \frac{2}{3} s_2 = -\frac{1}{2}
  3. C
    sg−12s1−13s2=12s_g - \frac{1}{2} s_1 - \frac{1}{3} s_2 = \frac{1}{2}
  4. D
    sg−32s1+23s2=−52s_g - \frac{3}{2} s_1 + \frac{2}{3} s_2 = -\frac{5}{2}
  5. E
    sg+12s1+13s2=−12s_g + \frac{1}{2} s_1 + \frac{1}{3} s_2 = -\frac{1}{2}

Cevap

Gomory kesme düzlemi kısıtı sg−12s1−13s2=−12s_g - \frac{1}{2} s_1 - \frac{1}{3} s_2 = -\frac{1}{2} şeklindedir.
Doğru cevapta, s1s_1 katsayısının kesirsel kısmı 1/21/2, s2s_2 katsayısının kesirsel kısmı (−2/3-2/3 için) 1/31/3 ve çözüm değerinin kesirsel kısmı 1/21/2 olarak doğru belirlenmiş ve standart kısıt formunda (sg−∑fjsj=−fis_g - \sum f_j s_j = -f_i) yerine yazılmıştır.

Adım Adım Çözüm

1
x1x_1 satırı denklemini yazınız.
x1+32s1−23s2=52x_1 + \frac{3}{2}s_1 - \frac{2}{3}s_2 = \frac{5}{2}
Kesme düzlemi oluşturmak için temel değişkenin bulunduğu satır denklemi temel alınır.
2
Katsayıları tam sayı ve pozitif kesirsel kısımlara (0≤f<10 \leq f < 1) ayırınız.
s1s_1 için: 32=1+12\frac{3}{2} = 1 + \frac{1}{2}; s2s_2 için: −23=−1+13-\frac{2}{3} = -1 + \frac{1}{3}; Çözüm için: 52=2+12\frac{5}{2} = 2 + \frac{1}{2}
Gomory yönteminde her katsayı aij=⌊aij⌋+fija_{ij} = \lfloor a_{ij} \rfloor + f_{ij} şeklinde ayrıştırılır.
3
Kesirsel kısımları kullanarak kısıt denklemini oluşturunuz.
12s1+13s2≥12\frac{1}{2}s_1 + \frac{1}{3}s_2 \geq \frac{1}{2}
Kesme düzlemi genel formu ∑fijsj≥fi\sum f_{ij}s_j \geq f_i şeklindedir.
4
Kısıtı simpleks tablosuna uygun standart forma dönüştürünüz.
sg−12s1−13s2=−12s_g - \frac{1}{2} s_1 - \frac{1}{3} s_2 = -\frac{1}{2}
Aylak değişken (sgs_g) eklenerek denklemin sağ tarafı negatif yapılarak dual simpleks adımına hazırlanır.

Anahtar Kavram

Gomory Kesme Düzlemi Algoritması'nda negatif katsayıların kesirsel kısımları hesaplanırken katsayıdan küçük en büyük tam sayı (taban değer) çıkarılır.
Bu soruyu puanla

Konular

Kesme Düzlemi (Gomory) Algoritması

Bu konudan daha fazla soru