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öntemiyle çözülmüş ve optimal simpleks tablosu aşağıda verilmiştir:

Temel Değişkenlerx1x_1x2x_2s1s_1s2s_2Sağ Yan (bb)
ZZ001/51/52/52/522/522/5
x1x_1104/54/5−2/5-2/514/514/5
x2x_201−1/5-1/53/53/59/59/5

Tüm karar değişkenlerinin tam sayı olması gerektiği bilindiğine göre, x1x_1 temel değişkeninin bulunduğu satır kullanılarak oluşturulacak olan Gomory kesme düzlemi kısıtı aşağıdakilerden hangisidir?

  1. sg−45s1−35s2=−45s_g - \frac{4}{5} s_1 - \frac{3}{5} s_2 = -\frac{4}{5}Cevap
  2. B
    sg−45s1+25s2=−45s_g - \frac{4}{5} s_1 + \frac{2}{5} s_2 = -\frac{4}{5}
  3. C
    sg−45s1−35s2=45s_g - \frac{4}{5} s_1 - \frac{3}{5} s_2 = \frac{4}{5}
  4. D
    sg−15s1−25s2=−15s_g - \frac{1}{5} s_1 - \frac{2}{5} s_2 = -\frac{1}{5}
  5. E
    sg+45s1+35s2=−45s_g + \frac{4}{5} s_1 + \frac{3}{5} s_2 = -\frac{4}{5}

Cevap

Gomory kesme düzlemi kısıtı sg−45s1−35s2=−45s_g - \frac{4}{5} s_1 - \frac{3}{5} s_2 = -\frac{4}{5} şeklinde ifade edilir.
Doğru cevap olan ifade, x1x_1 satırındaki katsayıların doğru ayrıştırılmasıyla elde edilir. 45\frac{4}{5} katsayısı için f=4/5f = 4/5, −25-\frac{2}{5} katsayısı için f=3/5f = 3/5 ve sağ yan sabit 145\frac{14}{5} için f=4/5f = 4/5 değerleri bulunur. Bu değerler ∑fjsj≥fb\sum f_{j} s_{j} \geq f_{b} kalıbına yerleştirilip sgs_g eklendiğinde beklenen kısıt denklemi oluşur.

Adım Adım Çözüm

1
x1x_1 temel değişkeninin bulunduğu satır denklemi yazılır.
x1+45s1−25s2=145x_1 + \frac{4}{5} s_1 - \frac{2}{5} s_2 = \frac{14}{5}
Kesme düzlemi oluşturmak için tam sayı olmayan bir temel değişkenin satırı seçilmelidir.
2
Katsayılar ve sağ yan sabit, tam sayı (II) ve negatif olmayan kesirsel (ff) kısımlarına (0≤f<10 \leq f < 1) ayrıştırılır.
x1+(0+45)s1+(−1+35)s2=2+45x_1 + (0 + \frac{4}{5}) s_1 + (-1 + \frac{3}{5}) s_2 = 2 + \frac{4}{5}
−25-\frac{2}{5} değeri −1+35-1 + \frac{3}{5} olarak yazılmalıdır çünkü kesirsel kısım negatif olamaz.
3
Kesirsel kısımlar kullanılarak ∑fijxj≥fi\sum f_{ij} x_j \geq f_i eşitsizliği oluşturulur ve standart formuna dönüştürülür.
45s1+35s2≥45⇒sg−45s1−35s2=−45\frac{4}{5} s_1 + \frac{3}{5} s_2 \geq \frac{4}{5} \Rightarrow s_g - \frac{4}{5} s_1 - \frac{3}{5} s_2 = -\frac{4}{5}
Yeni kısıt, mevcut çözümü dışarıda bırakacak ancak tam sayılı çözümleri koruyacak şekilde eklenir.

Anahtar Kavram

Gomory kesme düzlemi algoritmasında, negatif katsayıların kesirsel kısımları f=k−⌊k⌋f = k - \lfloor k \rfloor formülüyle hesaplanır ve her zaman 0≤f<10 \leq f < 1 aralığında olmalıdır.

İpuçları

1
x1x_1 satırındaki her bir katsayıyı tam sayı ve pozitif bir kesir toplamı olarak yazmayı deneyin.
2
Negatif katsayıları ayrıştırırken dikkatli olun; örneğin −25=−1+35-\frac{2}{5} = -1 + \frac{3}{5} şeklindedir.

Daha Fazla Pratik

Elde edilen bu kısıt eklendikten sonra bir sonraki adımın neden Dual Simpleks yöntemi olduğunu araştırınız.
Tahmini Süre:2m 0s
Bu soruyu puanla

Konular

Kesme Düzlemi (Gomory) Algoritması

Bu konudan daha fazla soru