Examkin

Soru

Zorluk: OrtaKesme Düzlemi (Gomory) Algoritması

Tam sayılı bir doğrusal programlama probleminin doğrusal gevşetilmesi (LP relaxation) çözüldüğünde elde edilen optimal simpleks tablosu aşağıda verilmiştir:

Temel Değişkenlerx1x_1x2x_2s1s_1s2s_2Sağ Taraf
ZZ001.22.525.8
x1x_1102/3-1/410/3
x2x_201-1/31/27/3

Problemdeki tüm karar değişkenlerinin (x1,x2x_1, x_2) tam sayı olması gerektiği bilinmektedir. Buna göre, x1x_1 değişkeninin tamsayılılık kısıtını sağlamak amacıyla Gomory kesme düzlemi algoritması kullanılarak oluşturulacak kesme kısıtı (cut constraint) aşağıdakilerden hangisidir? (Yeni eklenen aylak değişken sgs_g ile gösterilmiştir.)

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

Cevap

Doğru kısıt sg−23s1−34s2=−13s_g - \frac{2}{3} s_1 - \frac{3}{4} s_2 = -\frac{1}{3} ifadesidir.
Doğru yanıt olan ifadede, x1x_1 satırındaki katsayıların kesirsel kısımları hatasız hesaplanmıştır. Özellikle s2s_2 değişkeninin katsayısı olan −1/4-1/4, en yakın küçük tam sayı olan −1-1'den çıkarılarak 3/43/4 kesir değeri elde edilmiştir. Sağ taraf değerinin kesirsel kısmı olan 1/31/3 ise kısıtın sağ tarafına negatif işaretle aktarılarak standart form oluşturulmuştur.

Adım Adım Çözüm

1
x1x_1 temel değişkeninin bulunduğu satırı denklem olarak yazın.
x1+23s1−14s2=103x_1 + \frac{2}{3} s_1 - \frac{1}{4} s_2 = \frac{10}{3}
Gomory kısıtı, tamsayı olması gereken ancak kesirli değer alan bir temel değişkenin satırından türetilir.
2
Katsayıları ve sağ taraf değerini tam sayı ve kesirsel kısımlara ayırın (f=a−⌊a⌋f = a - \lfloor a \rfloor).
x1x_1 için 1=1+01 = 1 + 0 (f=0f=0); s1s_1 için 23=0+23\frac{2}{3} = 0 + \frac{2}{3} (f=23f=\frac{2}{3}); s2s_2 için −14=−1+34-\frac{1}{4} = -1 + \frac{3}{4} (f=34f=\frac{3}{4}); Sağ taraf için 103=3+13\frac{10}{3} = 3 + \frac{1}{3} (f=13f=\frac{1}{3})
Gomory algoritmasında kesirsel kısım her zaman negatif olmayan (0≤f<10 \leq f < 1) bir değer olmalıdır. Bu yüzden −14-\frac{1}{4} için ⌊−0.25⌋=−1\lfloor -0.25 \rfloor = -1 alınarak kesir 34\frac{3}{4} bulunur.
3
Standart Gomory kesme kısıtı formülünü uygulayın (sg−∑fijxj=−fi0s_g - \sum f_{ij} x_j = -f_{i0}).
sg−23s1−34s2=−13s_g - \frac{2}{3} s_1 - \frac{3}{4} s_2 = -\frac{1}{3}
Bu kısıt, mevcut optimal çözümün tamsayılı olmayan kısımlarını dışarıda bırakırken tüm uygun tamsayılı çözümleri korur.

Anahtar Kavram

Gomory Kesme Düzlemi Algoritması'nda kesirsel kısımların (a−⌊a⌋a - \lfloor a \rfloor) belirlenmesi ve standart formda kısıt yazımı.

İpuçları

1
Gomory kısıtı oluştururken ilgili satırı denklem haline getirin ve katsayıların ondalık/kesir kısımlarına odaklanın.
2
Negatif katsayılara dikkat edin: Bir sayının kesirsel kısmı f=a−⌊a⌋f = a - \lfloor a \rfloor formülüyle bulunur. Örneğin ⌊−0.25⌋=−1\lfloor -0.25 \rfloor = -1 olduğundan kesir 0.750.75 olur.

Daha Fazla Pratik

Bu kısıt eklendikten sonra tablonun dual simpleks yöntemi ile çözülmesi gerektiğini hatırlayın.
Tahmini Süre:1m 30s
Bu soruyu puanla

Konular

Kesme Düzlemi (Gomory) Algoritması

Bu konudan daha fazla soru