Examkin

Soru

Zorluk: OrtaKesme Düzlemi (Gomory) Algoritması

Saf tam sayılı bir doğrusal programlama modelinin doğrusal gevşetilmesi (LP relaxation) simpleks yöntemi ile çözülmüş ve elde edilen optimal tablo aşağıda sunulmuştur:

Temel Değ.ZZx1x_1x2x_2x3x_3x4x_4x5x_5Sağ Yan
ZZ10021.50.525.5
x1x_101010.2-0.44.0
x2x_200102.4-1.23.6

Tablodaki tüm değişkenlerin tam sayı olması gerektiği bilindiğine göre, x2x_2 temel değişkeninin bulunduğu satır kullanılarak oluşturulacak Gomory kesme düzlemi (cut) kısıtı aşağıdakilerden hangisidir?

  1. sg−25x4−45x5=−35s_g - \frac{2}{5}x_4 - \frac{4}{5}x_5 = -\frac{3}{5}Cevap
  2. B
    sg−25x4−15x5=−35s_g - \frac{2}{5}x_4 - \frac{1}{5}x_5 = -\frac{3}{5}
  3. C
    sg−25x4−45x5=35s_g - \frac{2}{5}x_4 - \frac{4}{5}x_5 = \frac{3}{5}
  4. D
    sg−25x4+45x5=−35s_g - \frac{2}{5}x_4 + \frac{4}{5}x_5 = -\frac{3}{5}
  5. E
    sg−25x4+15x5=−35s_g - \frac{2}{5}x_4 + \frac{1}{5}x_5 = -\frac{3}{5}

Cevap

Doğru kısıt denklemi sg−25x4−45x5=−35s_g - \frac{2}{5}x_4 - \frac{4}{5}x_5 = -\frac{3}{5} şeklindedir.
Doğru yanıt olan ifadede, x2x_2 satırındaki 2.42.4 katsayısı 2+0.42 + 0.4, −1.2-1.2 katsayısı −2+0.8-2 + 0.8 ve sağ yan değeri olan 3.63.6 ise 3+0.63 + 0.6 şeklinde ayrıştırılmıştır. Buradan elde edilen 0.4x4+0.8x5≥0.60.4x_4 + 0.8x_5 \geq 0.6 kısıtı, sgs_g aylak değişkeni eklenerek düzenlenen sg−2/5x4−4/5x5=−3/5s_g - 2/5x_4 - 4/5x_5 = -3/5 formuna tam olarak uymaktadır.

Adım Adım Çözüm

1
x2x_2 temel değişkeninin bulunduğu satırı denklem formunda yazın.
x2+2.4x4−1.2x5=3.6x_2 + 2.4x_4 - 1.2x_5 = 3.6
Kesme düzlemi oluşturmak için ilgili satırın matematiksel ifadesi gereklidir.
2
Katsayıları ve sağ yan değerini tam sayı ve pozitif kesirsel kısımlara (0≤f<10 \leq f < 1) ayırın.
2.4=2+0.42.4 = 2 + 0.4, −1.2=−2+0.8-1.2 = -2 + 0.8 ve 3.6=3+0.63.6 = 3 + 0.6
Gomory kuralına göre fj=aj−⌊aj⌋f_j = a_j - \lfloor a_j \rfloor işlemi uygulanmalıdır. Özellikle −1.2−(−2)=0.8-1.2 - (-2) = 0.8 işlemine dikkat edilmelidir.
3
Kesirsel kısımları kullanarak ∑fjxj≥fi\sum f_j x_j \geq f_i eşitsizliğini kurun.
0.4x4+0.8x5≥0.60.4x_4 + 0.8x_5 \geq 0.6
Gomory kesmesi, mevcut kısıtın tamsayılı çözümleri dışlamadan gevşetilmiş alanı daraltan kısımdır.
4
Eşitsizliği standart simpleks formuna (sgs_g aylak değişkeni ekleyerek) dönüştürün.
0.4x4+0.8x5−sg≤0.60.4x_4 + 0.8x_5 - s_g \leq 0.6 veya sg−0.4x4−0.8x5=−0.6s_g - 0.4x_4 - 0.8x_5 = -0.6
Simpleks tablosuna eklenebilmesi için kısıtın eşitlik formunda ifade edilmesi gerekir.
5
Ondalık sayıları kesirli ifadelere çevirin.
0.4=2/50.4 = 2/5, 0.8=4/50.8 = 4/5, 0.6=3/50.6 = 3/5
Akademik ve sınav formatına uygun gösterim için kesirli ifadeler kullanılır.

Anahtar Kavram

Gomory kesme düzlemi algoritmasında, negatif katsayıların kesirsel kısmı belirlenirken katsayıdan küçük en büyük tam sayı çıkarılır (f=a−⌊a⌋f = a - \lfloor a \rfloor).

Alternatif Yöntem

Ondalık sayılarla işlem yapmak yerine tüm satırı payda eşitleyerek kesirlere çevirip (x2+12/5x4−6/5x5=18/5x_2 + 12/5x_4 - 6/5x_5 = 18/5) ardından pay kısmında modüler aritmetik mantığıyla (pozitif kalan verecek şekilde) bölme yapmak hata payını azaltabilir.
Tahmini Süre:1m 30s
Bu soruyu puanla

Konular

Kesme Düzlemi (Gomory) Algoritması

Bu konudan daha fazla soru